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に組み込む予定があるため,それに向けて書き換え可能な構成となっている.
- コーディングをする上に置いて以下の概念が存在する。
  - CodeGear(以下CG)
    - スレッド、クラスに相当し、javaの継承を用いて記述する。
  - CodeGearManager(以下CGM)
    - DGは変数データに相当し、CG内でアノテーションを用いて変数データを取り出せる。
  - DataGear(以下DG)
  - DataGearManager(以下DGM)
<!--
## 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
- RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。
- 立ち上げ後はManager名を指定してDataSegmentAPI用いてDSのやり取りを行うため、プログラマはManager名を意識することでLocalへの操作もRemoteへの操作も同様に扱える。

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

## 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.setup(new HelloWorldCodeGear());
        cgm.getLocalDGM().put("helloWorld","hello");
        cgm.getLocalDGM().put("helloWorld","world");
    }
}

```

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

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

## 静的Topology
- 静的Toopologyはdotファイルを与えることでノード関係を下の図のようにする。
- 静的Topologyはdotファイルのノード数と同等のTopologyNodeがあって初めて、CodeGearが実行される。
```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="300">
</div>

## ブロックチェーンのトランザクション
- ブロックチェーンはP2Pにてネットワーク間が動作している。つまり、ブロックチェーンにはサーバー、クライアントの区別がなく全てのノードが平等である。
- ブロックチェーンにおけるブロックは複数のトランザクションをまとめたものである。ブロックの構造は使用するコンセンサスにより変わるが基本的には、previous block hash, merkle root hash, timeが含まれるBlockHeaderとTransactionListにより構成される。

## BlockHeader
- BlockHeaderには、前のブロックをハッシュ化したもの、トランザクションをまとめたmarkle treeのrootのhash、そのブロックを生成したtimeとなっている。
- previous block hashは、前のブロックのパラメータを並べてhash化したものである。
- 上記のものがそれぞれ連なっていることによって下の図のようなブロック繋がっている。そのため一つが更新されたらそのあとにつながるブロック全てを更新しなければならなくなる。
<div style="text-align: center;">
　<img src="../paper/images/chain.svg" alt="MetaGear" width="600">
</div>

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

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


## コンセンサスアルゴリズム
- 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	Tue, 28 May 2019 17:51:38 +0900
parents	cd438764f55c
children	e7239fe266f0