Mercurial > hg > Papers > 2019 > ikki-sigos
diff slide/prosym.md @ 24:a263efdfdab5 default tip
Revise last on 5/29
author | ichikitakahiro <e165713@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 29 May 2019 23:22:31 +0900 |
parents | 8a3b1147329e |
children |
line wrap: on
line diff
--- a/slide/prosym.md Wed May 29 20:25:54 2019 +0900 +++ b/slide/prosym.md Wed May 29 23:22:31 2019 +0900 @@ -148,11 +148,11 @@ ## ブロックチェーン - ネットワーク構築方式の一つである。データ情報をまとめたものをブロックと呼び、ブロックが連鎖的につながるっている形となる。 -- ノード一つにつき一つのブロックを持ち合わせるが、その間でデータの差異が生じた際に他のノードの総意によって選択し、差異の解消を行う。 +- ノードがそれぞれブロックを持つ、その間でデータの差異が生じた際に他のノードの総意によって選択し、差異の解消を行う。 - ブロックチェーンはP2P(Peer to Peer)の形にてネットワーク間が動作している。つまり、ブロックチェーンにはサーバー、クライアントの区別がなく全てのノードが対等な関係にある。 ## ブロックチェーンのトランザクション -- ブロックチェーンにおけるブロックは複数のトランザクションをまとめたものである。ブロックは基本的に以下の要素によって構成される。 +- ブロックは基本的に以下の要素によって構成される。 - BlockHeader - previous block - 前のブロックのパラメータをハッシュ化したもの @@ -191,7 +191,7 @@ ## コンセンサスアルゴリズム - fork - - ブロック生成後にブロードキャストを行うと、ブロック高の同じもしくは高いブロックチェーンにたどり着く状態があり、異なるブロックを持った二つのブロックチェーンのうちどちらかを破棄する必要がある。 + - ブロック生成を行う過程で、異なるブロックを持った二つのブロックチェーンが生成されてしまうことがある。そのうちどちらかを破棄する必要が生じ、この状態をforkと呼ぶ。 - fork状態を解消するために用いられるのがコンセンサスアルゴリズムである。 - ブロックチェーンはパブリックブロックチェーンとコンソーシアムブロックチェーンの場合によってコンセンサスアルゴリズムが変わる。 - パブリックブロックチェーン @@ -200,6 +200,7 @@ - コンソーシアムブロックチェーン - 許可したノードのみが参加できるブロックチェーンである。 +<!-- ## Proof of Work - Proof of Workは次のような問題が生じている場合にもコンセンサスを取ることができる。 - プロセス毎の処理速度が違う。つまりメッセージの返信が遅い場合がある。 @@ -225,14 +226,10 @@ - CPUのリソースを使用する - Transactionが確定するのに時間がかかる。 +--> + ## Paxos -- Paxosはノードの多数決によってコンセンサスをとるアルゴリズムである。 -- Paxosは以下のような問題があっても値を一意に決めることができる。 - - 1,プロセス毎に処理の速度が違う。つまりメッセージの返信が遅い可能性がある。 - - 2,通信にどれだけの時間がかかるかわからず、その途中でメッセージが失われる可能性がある。 - - 3,プロセスは停止する可能性もある。 - -## Paxosの役割ノード +- Paxosはノードの多数決によってコンセンサスをとる分散合意アルゴリズムである。 - Paxosは3つの役割ノードがある。 - proposer - 値を提案するノード。 @@ -241,6 +238,17 @@ - lerner - accepterから値を集計し、過半数以上のaccepterが持っている値を決める。 +## Paxosの利点、特徴 +- Paxosは以下のような問題があっても値を一意に決めることができる。 + - 1,プロセス毎に処理の速度が違う。つまりメッセージの返信が遅い可能性がある。 + - 2,通信にどれだけの時間がかかるかわからず、その途中でメッセージが失われる可能性がある。 + - 3,プロセスは停止する可能性もある。 +- 従来のコンセンサスアルゴリズム(Proof of Workなど)と比較し、 + - CPUにリソースを消費しない。 + - Transactionの確定に時間がかからない。 +- アルゴリズムの形式上、リーダーのノードの一貫性のみを考えることで構成しやすい。 + + ## Paxosの役割定義 - 提案 - 異なる提案ごとにユニークな提案番号と値からなる。提案番号とは、異なる提案を見分けるための識別子であり、単調増加である。 @@ -252,41 +260,40 @@ ## paxosのアルゴリズム - paxosのアルゴリズムは2フューズあり、一つ目のフェーズprepare-promiseと二つ目のフェーズaccept-acceptedの二つに区分される。 - -## paxosのアルゴリズム prepare-promise -- (言葉での説明記入?) +- 単純化としてproposerの数を2、accepterの数を3、lernerの数を1とする。 <div style="text-align: center;"> - <img src="../paper/images/prepare-promise.svg" alt="MetaGear" width="600"> + <img src="../paper/images/paxos2.svg" alt="MetaGear" width="900"> </div> -## paxosのアルゴリズム accept-accepted -- (1)proposerは過半数のacceptorから返事が来たのなら、次の提案をaccepterに送る。これをacceptリクエストという。 - - (a)もし、約束のみ帰って来ているのならば、任意の値vをprepareリクエストで送った提案に設定する。 - - (b)もし、acceptされた提案が帰って来たら、その中で最大の提案番号v'をprepareリクエストで送った提案の値として設定する。 + + +## paxosのアルゴリズム prepare-promise +- paxosのアルゴリズムはprepare-promiseとaccepter-acceptedの2フェーズに分けられる。 +- (1)proposerは提案番号nを設定した提案を過半数以上のaccepterに送る。これをprepareリクエストと呼ぶ。 +- (2)それぞれのaccepterは各proposerからprepareリクエストが来たら + - (a)もし、以前に送られたprepareリクエストの提案番号より、今送られて来たprepareリクエストの方が大きければ、それ以下の提案番号の提案を拒否するという約束を返す。この状態をpromiseしたという。 + - (b)もし値がすでにacceptされていたら、すでにacceptされているという報告を返す。 + +## paxosのアルゴリズム accepter-accepted +- (1))proposerは過半数のacceptorから返事が来たのなら、次の提案をaccepterに送る。これをacceptリクエストという。 + - (a)もし、accepterがpromiseされた状態のままであるならaccepterは提案を(acceptリクエストと同様)を選択し、lernerへacceptされた提案を報告する。 + - (b)もし、acceptされた提案が帰って来たなら、その中で最大の提案番号を持つ提案を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は関数が終わると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に同名の変数がロックされ、実行されない場合がある。 +- デバックが難しい。cgm.setupでCodeGearが実行されるが、keyの待ち合わせで止まり、どこのCGで止まっているのか判断できなくなりやすい。例として、putするkeyのスペルミスでコードの待ち合わせが起こり、CGが実行されず、エラーなども表示されずにwaitすることがあり、誤っている部分が見つけづらい。 <!-- +- Takeの待ち合わせでCGが実行されない。2つのCGで同じ変数をTakeしようとすると、setupされた時点で変数がロックされる。この時、片方のCGはDGがもう全て揃っているのに、全ての変数が揃っていないもう片方のCGに同名の変数がロックされ、実行されない場合がある。 (ロックはおかしい) +- Takefrom,PeekFromの使い方が難しい。TakeFrom,PeekFromは引数でDGMnameを指定する。しかし、DGMの名前を静的に与えるよりも、動的に与えたい場合が多かった。 --> ## 実験 @@ -313,12 +320,6 @@ </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は実験するノードの設定を行う集中制度ノードであり、ブロックチェーンとの相性は良くないが、分散ファイルシステムなどの用途の場合、このような手法の方がノードの管理が可能な利点がある。