Paxos アルゴリズムを使う

秋学期のこと

秋学期は Decentralized systems engineering とか Distributed algorithms のような授業を履修し，分散システム漬けの日々を送りました． 授業では実際に動くP2Pの分散システムをディアゴスティーニ式に作っていく課題が出され（非常に重く，細かい実装のデザインとデバッグで全ての土日が潰れる），講義で習った内容を理解していくというものでした． このシステムのゴールは，ネットワークで接続された，複数の独立したノード間で合意を取るようなシステムの実装を行うというもの． 実装には Paxos アルゴリズム と呼ばれるアルゴリズムを用いました．

Paxos とは

Paxos アルゴリズムとは，超簡単にいうと “信頼できない（ノードに情報が伝わらない可能性がある）ネットワークで，一つの値をみんなで共有する” ものだと思っています． つまり，パケットが途中で失われたりするような環境でも，誰かが提案した値は全員に伝わるか，あるいは否決されるかのどちらかであることを保証するということです．

課題では，分散システムに関する数々の功績を残した Leslie Lamport 氏 ¹ による Paxos Made Simple の内容に基づき，一件のファイルごとの合意をとるということが求められました．

論文によると， Paxos アルゴリズムは以下のような 2 つのフェーズによって合意を形成します:

Phase 1

• 値を提案するノードが，ある提案番号 n を持つ prepare リクエストをブロードキャストする．
• prepare リクエストを受け取ったノードは，提案番号 n と，過去に受け取って返答したリクエストの提案番号を比べる． n がこれまでのどの番号よりも大きい場合， n より小さい提案番号を持つ提案を受け取らないという promise を送り返す．また，これまでにすでに受け入れた値があれば，それも返す．

Phase 2

• 値を提案するノードが，過半数のノードから promise を受け取った場合，　promise に含まれる，他のノードによってすでに受け入れられた値を見る．もし，そのような値があった場合，そのうち提案番号がもっとも大きい値を提案する値 v とする．そのような値がない場合，任意の値を提案する値 v とする．そして，その値 v を提案番号 n の accept リクエストとしてブロードキャストする．
• accept リクエストを受け取ったノードは， Phase 1 と同様に提案番号 n と，過去に受け取って返答したリクエストの提案番号を比べ，過去に promise を送り返したどの提案番号よりも n が大きい時は，その提案を受け入れる．

Paxos の面白いところは，リーダーのようなものをあらかじめ割り当てることなく動作させることができるという点です． これは，値を提案する権利と，提案を受け取る権利の両方をノードに与えることによって達成されます．提案番号をノードごとにユニークなものにしておく（例えば n 個のノードが存在する場合，ノード k は提案番号を k, n+k, 2n+k…, と増やすように決めるなど）ことなどが考えられます．

Paxos を使って Total Order Broadcast を作る

テスト勉強をしている間，ふとこのような Paxos を使った合意は，例えばネットワークやノードが信頼できないような分散システムでの強い一貫性を保証するようなシステムに使えるのではないかと考えました． アイデアはこうです:

• 任意の個数の Paxos のインスタンスを使って，好きなだけ値を合意する．
• Paxos のインスタンスそれぞれに番号を割り当てる．
• 合意した値を Paxos のインスタンス番号順に並び替えることにより，全てのノードにおいて，同一の順序で値を受け取ることができる．

これは total order broadcast (あるいは atomic broadcast) が持つべき条件を満たしています． これは， Paxos は合意アルゴリズムであることから， termination （全ての故障していないプロセスは，いつかはある値に対し合意する）の条件を満たしていることからいえます． これにより，全ての故障していないノードでは，ある時間 t の時点で合意を行っている Paxos のインスタンス全てにおいて合意が形成されるような時間 t’ があるといえ，これにより，各ノードは Paxos のインスタンス番号に従ってメッセージを順番に受け取っていくことができ， total order broadcast (TOB) の total order 条件（全ての故障していないノードが，同一順序でメッセージを受け取ること）が満たされるからです．

このようなアイデアをベースに， Paxos を使用した TOB のライブラリとしてみました (GitHub のリンクはこちら)． なお，学期中の開発での反省点として，それぞれのコンポーネント同士の依存関係が大きく，バグを見つけるのが非常に大変であったということがありました． そこで，今回はメッセージ幅やり取りを行うモジュール， Paxos 本体， Paxos を使って 1 件の合意をとるモジュール，合意アルゴリズムを使って TOB を実装するモジュールのように，インタフェースを用いて，他の部分をモックして細かくテストできるような構成を意識しました．

ノードを落としてみたらどうなるか，実際の環境で動かしてみるとどうかなど，これからいろいろ試してみたいと思います．