Mercurial > hg > Papers > 2019 > ikki-sigos

title: 分散ネットワークChristieによるBlockchainの実装
author: Takahiro Ikki, Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay

## 研究目的

- コンピュータのデータの不整合の主な原因は、誤作動や複数人によるデータの同時書き込みによって発生し、特に分散環境下で問題となる。
- 分散ネットワークシステムであるブロックチェーンでは、データの分散に伴うデータ不整合の検知が可能な仕組みとなっている。
- 当研究室で開発中のGearsOSの分散システムの技術として, ブロックチェーンが使用できるか調査したい.
- 将来的にGearsOSに組み込む予定のある分散フレームワークChristieに分散フレームワークを実装することにした。

<!--
# OS の拡張性と信頼性の両立

-->

## Christie
- Christieは当研究室で開発している、信頼性を重視した分散フレームワークである.
- 現在はjava上で開発されているが、別言語で構成されたGearsOSに組み込む予定があるため,それに向けて書き換え可能な構成となっている。
- ChristieではデータをGearという単位で分割して記述を行う。
  - CodeGear(以下CG)
    - スレッドやクラスに相当し、javaの継承を用いて記述する。keyに全てのDGが格納された際に動作する。
  - DataGear(以下DG)
    - DGは変数に相当し、CG内でアノテーションを用いてデータを取り出せる。
  - CodeGearManager(以下CGM)
    - ノードに相当し, DG, CG, DataGearManagerの管理をする.
  - DataGearManager(以下DGM)
    - DGを管理するものであり, putという操作にて変数(DG)をkeyに格納する。


    ## Christieのコード例
    ```code
    package christie.example.HelloWorld;

    import christie.codegear.CodeGearManager;
    import christie.codegear.StartCodeGear;

    public class StartHelloWorld extends StartCodeGear {

        public StartHelloWorld(CodeGearManager cgm) {
            super(cgm);
        }

        public static void main(String[] args){
            CodeGearManager cgm = createCGM(10000); #ポート番号を指定してCGMを立ち上げ。
            cgm.setup(new HelloWorldCodeGear()); #立ち上げたCGMへCGを待ちあわせる。
            cgm.getLocalDGM().put("helloWorld","hello"); #key "helloWorld"にhelloをput
            cgm.getLocalDGM().put("helloWorld","world");
        }
    }

    ```
    ```
    ChristieDaemon.listen: bind to /0:0:0:0:0:0:0:0:10000
    hello world
    ```
    <!--
    - 立ち上げ後はManager名を指定してDataSegmentAPI用いてDSのやり取りを行うため、プログラマはManager名を意識することでLocalへの操作もRemoteへの操作も同様に扱える。
    -->

<!--

## Christieの言語概念
- CGはスレッド, クラスに相当し, javaの継承を用いて記述する.
- DGは変数データに相当し, CG内でアノテーションを用いて変数データを取り出せる.
- CGMはノードであり, DG, CG, DGMを管理する.
- DGMはDGを管理するものであり, putという操作により, 変数データ(DG)を格納できる.
  - DGMにはLocalDGMとRemoteDGMが存在する。LocalDGMは各ノード固有のデータベースである。RemoteDSMは他ノードのLocalDGMに対応するproxyであり、接続しているノードの数だけ存在する。
  - DGMのput操作を行う際にはLocalとRemoteのどちらかを選ぶ.Localであれば、LocalのCGMが管理するDGMに対しDGを格納し, Remoteの場合は接続したRemoteさきのCGMのDGMにDGを格納する.

-->

## DGM
- DGMは分散システムの肝となる他のノード間とのデータのやり取りの際に重要となる。
- DGMにはLocalDGMとRemoteDGMが存在する。
  - LocalDGM
    - LocalなDGMのプールのkeyにデータの書き込みを行う。
  - RemoteDSM
    - Localに存在する、他のノードのLocalDGMに対応するプールのkeyにデータを書き込みする。接続しているノードの数だけ存在する。
- DGMのput操作を行う際にはLocalとRemoteのどちらかを選ぶ.Localであれば、LocalのCGMが管理するDGMへ、 Remoteの場合は接続したRemote先のCGMのDGMにDGを格納する.

<div style="text-align: center;">
  <img src="../paper/images/remote_datasegment.svg" alt="MetaGear" width="400">
</div>

<!--
- RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。
-->

## Annottation
- ChristieではInputDGの指定にはアノテーションを使う。
- アノテーションとはクラスやメソッド、パッケージに対して、付加情報を記述できるJavaのMeta Computationである。
- 先頭に@をつけることで記述する。オリジナルのアノテーションを定義することもでき、Input
される型の変数を直接宣言し、変数名としてkeyを記述する。その上にアノテーションでTakeもしくはPeekを指定する。

```cc
package christie.example.HelloWorld;

import christie.annotation.Take;
import christie.codegear.CodeGear;
import christie.codegear.CodeGearManager;

public class HelloWorldCodeGear extends CodeGear {
    @Take
    String helloWorld;

    @Override
    protected void run(CodeGearManager cgm) {
        System.out.print(helloWorld + " ");
        cgm.setup(new HelloWorldCodeGear());
    }
}

```

## DGのアノテーション
- DGを取り出す際にはCG内で宣言した変数にアノテーションをつける。DGアノテーションには
Take、Peek、TakeFrom、PeekFrom、の4つがある。
  - Take
    - 先頭のDGを読み込み、そのDGを削除する。
  - Peek
    - 先頭のDGを読み込むが、DGが消去されない。そのため特に操作をしない場合、同じデータを参照し続ける。
  - TakeFrom
    - Remote DGM nameを指定することで、その接続先のDGM からTake操作をおこえる。
  - PeekFrom
    - Remote DGM nameを指定することで、その接続先のDGM からPeek操作をおこえる。


## TopologyManager
- TopologyManagerとはTopologyを形成のために、参加を表明したノード、TopologyNodeに名前を与え、必要があればノード同士の配線を行うノードである。
- TopologyManagerのTopology形成方法として、静的Topologyと動的Topologyがある。
  - 動的Topologyは参加を表明したノードに対し、動的にノード同士の関係を作る。例えばTreeを構成する場合、参加したノードから順にrootに近い役割を与え、またCodeGearはノードが参加し、parentに接続された後に実行される。
  - 静的Toopologyはdotファイルを与えることノード関係の構築を行う。

```Code
digraph test {
	node0 -> node1 [label="right"]
	node1 -> node2 [label="right"]
	node2 -> node0 [label="right"]
}
```

<div style="text-align: center;">
　<img src="../paper/images/ring.svg" alt="MetaGear" width="250">
</div>

## ブロックチェーン
- ネットワーク構築方式の一つである。データ情報をまとめたものをブロックと呼び、ブロックが連鎖的につながるっている形となる。
- ノード一つにつき一つのブロックを持ち合わせるが、その間でデータの差異が生じた際に他のノードの総意によって選択し、差異の解消を行う。
- ブロックチェーンはP2P(Peer to Peer)の形にてネットワーク間が動作している。つまり、ブロックチェーンにはサーバー、クライアントの区別がなく全てのノードが対等な関係にある。

## ブロックチェーンのトランザクション
- ブロックチェーンにおけるブロックは複数のトランザクションをまとめたものである。ブロックは基本的に以下の要素によって構成される。
  - BlockHeader
    - previous block
      - 前のブロックのパラメータをハッシュ化したもの
    - hashmerkle root hash
      - トランザションをまとめたハッシュ木のrootのハッシュ
    - time
      - そのブロックが生成されたtime
  - TransactionList
- 上記のものがそれぞれ連なっていることによって下の図のようなブロック繋がっている。
<div style="text-align: center;">
　<img src="../paper/images/chain.svg" alt="MetaGear" width="600">
</div>

<!--
-　しっかり調査する
-->

## Transaction
- トランザクションとはデータのやり取りを行なった記録の最小単位である。トランザクションの構造は次のとおりである。
- TransactionHash
  - トランザクションをハッシュ化したもの。
- data
  - データ
- sendAddress
  - 送り元のアドレス。
- receiveAddress
  - 送り先のアカウントのアドレス。
- signature
  - トランザクションの全体を秘密鍵でハッシュ化したもの。
- トランザクションはノード間で伝搬され、ノードごとに検証される。そして検証を終え、不正なトランザクションであればそれを破棄し、検証に通った場合はTransaction Poolに取り込まれる。

## Blockの動作
- ブロックが生成された場合、知っているノードにそのブロックをマルチキャストする。通信量を抑えるためにブロックを送ったあと、ブロックをシリアライズして送信する場合もある。
- Transactionが失敗したならばそのノードがブロックをブロードキャストする。そしてTransaction PoolというTransactionをためておく場所から、そのブロックに含まれるTransactionを削除する。


## コンセンサスアルゴリズム
- fork
  - ブロック生成後にブロードキャストを行うと、ブロック高の同じもしくは高いブロックチェーンにたどり着く状態があり、異なるブロックを持った二つのブロックチェーンのうちどちらかを破棄する必要がある。
- fork状態を解消するために用いられるのがコンセンサスアルゴリズムである。
- ブロックチェーンはパブリックブロックチェーンとコンソーシアムブロックチェーンの場合によってコンセンサスアルゴリズムが変わる。
  - パブリックブロックチェーン
    - 不特定多数のノードが参加するブロックチェーンを指す。
    - 不特定多数のノード間、全体のノードの参加数が変わる状況でコンセンサスの変わるアルゴリズムでなければならない。
  - コンソーシアムブロックチェーン
    - 許可したノードのみが参加できるブロックチェーンである。

## Proof of Work
- Proof of Workは次のような問題が生じている場合にもコンセンサスを取ることができる。
  - プロセス毎の処理速度が違う。つまりメッセージの返信が遅い場合がある。
  - 通信にどれだけの時間がかかるか分からず、その途中でメッセージが途切れる場合がある
  - プロセスは停止する可能性がある。また復旧する場合もある。
  - 悪意ある情報を他のノードが送信する可能性がある。
- Proof of Workに必要なパラメーターは次のとおりである。
  - nonce
    - ブロックのパラメータに含まれる。
  - dificulty
    - Proof of Workの難しさ、正確には一つのブロックを生成する時間の調整。

## Proof of Workのブロック生成手順
- 1, ブロックとnonceを加えたものをハッシュ化する。この際、nonceによって、ブロックのハッシュは全く異なるものとなる。
- 2, ハッシュ化したブロックの先頭から数えた0ビットの数がdifficultyより多ければ、そのブロックにnonceを埋め込み、ブロックを作る。
- 3, 2の条件に当てはまらなければnonceに1を足して１からやり直す。

<div style="text-align: center;">
　<img src="../paper/images/proof-of-work.svg" alt="MetaGear" width="600">
</div>

## Proof of workの欠点
- CPUのリソースを使用する
- Transactionが確定するのに時間がかかる。

## Paxos
- Paxosはノードの多数決によってコンセンサスをとるアルゴリズムである。
- Paxosは以下のような問題があっても値を一意に決めることができる。
  - 1,プロセス毎に処理の速度が違う。つまりメッセージの返信が遅い可能性がある。
  - 2,通信にどれだけの時間がかかるかわからず、その途中でメッセージが失われる可能性がある。
  - 3,プロセスは停止する可能性もある。

## Paxosの役割ノード
- Paxosは3つの役割ノードがある。
  - proposer
    - 値を提案するノード。
  - accepter
    - 値を決めるノード。
  - lerner
    - accepterから値を集計し、過半数以上のaccepterが持っている値を決める。

## Paxosの役割定義
- 提案
  - 異なる提案ごとにユニークな提案番号と値からなる。提案番号とは、異なる提案を見分けるための識別子であり、単調増加である。
- 値(提案)がacceptされる
  - accepterによって値(提案)が決まること。
- 値(提案)が選択(chosen)される
  - 過半数以上のacceptorによって、値がacceptされた場合、それを値(提案)が選択されたと言う。


## paxosのアルゴリズム
- paxosのアルゴリズムは2フューズあり、一つ目のフェーズprepare-promiseと二つ目のフェーズaccept-acceptedの二つに区分される。

## paxosのアルゴリズム prepare-promise
- (言葉での説明記入?)
<div style="text-align: center;">
　<img src="../paper/images/prepare-promise.svg" alt="MetaGear" width="600">
</div>

## paxosのアルゴリズム accept-accepted
- (1)proposerは過半数のacceptorから返事が来たのなら、次の提案をaccepterに送る。これをacceptリクエストという。
    - (a)もし、約束のみ帰って来ているのならば、任意の値vをprepareリクエストで送った提案に設定する。
    - (b)もし、acceptされた提案が帰って来たら、その中で最大の提案番号v'をprepareリクエストで送った提案の値として設定する。
- (2)acceptorはacceptリクエストが来た場合、Promiseした提案よりもacceptリクエストで提案された番号が低ければ、その提案を拒否する。それ以外の場合、acceptする。
<div style="text-align: center;">
　<img src="../paper/images/accept-accepted.svg" alt="MetaGear" width="600">
</div>

## PaxosとProof of Workの比較
- Proof of Workと比較しメッセージ通信量と耐障害性のトレードオフになっている。
- Paxosでコンセンサスを取る際、Proof of Workと比較して次のようなメリットがある。
  - CPUにリソースを消費しない。
  - Transactionの確定に時間がかからない。
- Paxos自体がリーダー選出に向いているアルゴリズムである。そのため、リーダーを決定し、そのノードのブロックチェーンの一貫性のみをかんがえることができる。

## Christieにおけるブロックチェーンの実装の利点
- データの取り出しが簡単。ChristieはDataGearという単位でデータを保持する。そのためブロックやトランザクションはDataGearに包めばいいため、どう送るか考えなくて済む。
- TopologyManagerでのテストが便利。dotファイルがあれば、TopologyManagerが任意の形でTopologyを作れる。そのため、ノードの配置については理想の環境を作れるため、理想のテスト環境を作ることができる。
- 機能ごとにファイルが実装できるため、見通しが良い。ChristieはCbCのgotoと同じように関数が終わるとsetupによって別の関数に移動する。そのため自然に機能ごとにファイルを作るため、見通しがよくなる。

## Christieにおけるブロックチェーンの実装の欠点
- デバックが難しい。cgm.setupでCodeGearが実行されるが、keyの待ち合わせで止まり、どこのCGで止まっているのか分からないことが多かった。例えばputするkeyのスペルミスでコードの待ち合わせが起こり、CGが実行されず、エラーなども表示されずにwaitすることがある。その時に、どこで止まっているか特定するのが難しい。
- Takefrom,PeekFromの使い方が難しい。TakeFrom,PeekFromは引数でDGMnameを指定する。しかし、DGMの名前を静的に与えるよりも、動的に与えたい場合が多かった。
- Takeの待ち合わせでCGが実行されない。2つのCGで同じ変数をTakeしようとすると、setupされた時点で変数がロックされる。この時、片方のCGはDGがもう全て揃っているのに、全ての変数が揃っていないもう片方のCGに同名の変数がロックされ、実行されない場合がある。

<!--
(ロックはおかしい)
-->

## 実験
- 実際にコンセンサスアルゴリズムPaxosをPC上に分散環境を実装した。分散環境場で動かすため、JobScheduleの一種であるTorque Resource Manager(Torque)を使用した。
- Torqueはjobという単位でプログラムを管理し、リソースを確保できたら実行する。jobはqsubというコマンドを使って複数登録することができる。

## Torque
- Torqueには主に三つのNodeの種類がある。
  - Master Node
    - pds.serverを実行しているノード。他のノードの役割とも併用できる。
  - Submit/Interactive Nodes
    - クライアントがjobを投入したり監視したりするノード。qsubやqstatのようなクライアントコマンドが実行できる。
  - Computer Nodes
    - 投入されたjobを実際に実行するノード。pds.momが実行されており、それによってjobをstart、kill、管理する。

## 実際の実験内容
- KVM上にMaster NOde, Submit/InteractiveNodeの役割を持つVM1台、ComputerNOdesとして15台を用意しjobへ投入。
- 一意の数を決定することが確認できた。
- Lernerが値を選択した後も、提案番号がより大きいものを出力していたが値が覆らなかった。
- 本実験では分かりやすいよう数字で行なったが、タランザクション、ブロックに応用することでブロックチェーンのコンセンサス部分を完成させることができる。

<div style="text-align: center;">
　<img src="../paper/images/kvm.svg" alt="MetaGear" width="600">
</div>


## 実際にPaxosを動かした際の解説
- 単純化としてproposerの数えを2、accepterの数を3、lernerの数を1とする。
<div style="text-align: center;">
　<img src="../paper/images/paxos1.svg" alt="MetaGear" width="900">
</div>

## まとめ
- Paxosの動作は確認できた。トランザクションの速度がノード数にどのように影響されるか調査する必要がある。
- ChristieのTopology Managerは実験するノードの設定を行う集中制度ノードであり、ブロックチェーンとの相性は良くないが、分散ファイルシステムなどの用途の場合、このような手法の方がノードの管理が可能な利点がある。
- 現在、ChristieではBlock,Transaction,Hashの生成、署名、Proof of Workのためのクラスは作られている。しかし、Transactionに置いてまだファイルのデータを入れる機能がない。
- 以上のものを組み合わせれば簡易的なブロックチェーンが作ることができ、Paxosによるブロックチェーンが分散クラスタ上でファイルやり取りをした際のスケーラビリティを計測することができるようになる。
author	ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date	Wed, 29 May 2019 20:25:54 +0900
parents	e7239fe266f0
children	a263efdfdab5