現在はClouderaの社員であり、ZooKeeperのコミッタでもあるHenry RobinsonによるPaxosの優しい解説。ランポートの"Paxos made simple"に比べてもとても優しいが、何となく"Paxos made simple"を読んでいることを前提としているような省略があり、両方を交互に読むことを訳者としてはお勧めする。訳者はこれだけでは一部理解できなかった。
合意プロトコル： Paxos
Henry Robinson / ヘンリー・ロビンソン
今日、誰かのPaxosアルゴリズムについての記述無しに2つの分散システムについてのアーティクルを読むことは不可能だろう。
GoogleはChubbyにそれを使い、Yahooはそれに少し似ているものをZooKeeperに使っている。それはまるで究極の合意アルゴリズムだと考えられているようだ。またそれはとんでもなく理解するのが難しいという評判で、巧妙で、複雑なアルゴリズムで、選ばれた少数の人のみに正確に理解されるという。
これは同時に正しくもあり、間違ってもいる。Paxosはその振舞い全体を理解するのが微妙に難しい。
しかしアルゴリズム自体はかなり直感的だ。そして確かに比較的シンプルだ。このアーティクルでは筆者は基本的なPaxosがどのように振る舞うかを以前の2 phase commitと3 phase commitのアーティクルを参照しながら説明しようと思う。
終わりにより詳細を学びたい人のために参考文献一覧を含めておいた。
なぜ他の合意アルゴリズム？
もし貴方が私の以前の3PCのアーティクルを読んだのであれば、なぜ他の合意アルゴリズムを必要とするのか不思議に思うだろう。3PCは2PCの持つ主な問題、シングルノードの障害によりブロックされる傾向を取り除いた。実際に私が伸べた唯一の3PCが持ちうる問題は、もしネットワークが2つに分割された時、両方のパーティションが未完了のプロトコルインスタンスを復帰させ異なる結論に導き、ネットワークが再度マージされた時に不安定な状態をもたらすことだ。
これは本当に、さらにもう1つの合意アルゴリズムの根拠を示すのに十分に重大な問題だろうか？
それとも他にもまだ知られていない問題があるのだろうか？
最初の質問に対する答はたぶんイエスだろう。それは貴方がどれだけプロトコルに対して融通が効かないかによる。2つ目に対する答は明確にイエスだ。3PCはノードがクラッシュして停止に至る場合にはとてもうまく働く。障害に出くわした場合にプロトコルを永遠にほっておく。これはフェイルストップ故障モデルと呼ばれ我々が毎日見かける障害の数々を確かに説明する。しかし特にネットワークシステムではノードの壊れ方はこの通りとは限らない。そうではなく、障害に出くわしたとき、クラッシュしてそして障害から回復し、放置したポイントから喜んで実行を始める。(安定したストレージにより障害の間状態を保存することにより、再開したノードがクラッシュした時点からプロトコルを再開できない理由は全く無いことを思い出せ)
これはフェイルリカバー故障モデルだ。フェイルストップよりもより一般的で、そのため取扱いが少しだけよりトリッキーだ。
これがどのように問題になるかを理解するため、3PCのコーディネータが全ての参加者より(全員が返信を送ったのにも拘らず)'prepared-to-commit'を受け取る前に落ちたら何が起こるか想像してみよう。障害の間、リカバリーのコーディネータは引き継ぎを期待されるだろう。そして説明されたシナリオに従い、プロトコルを結論に向かい導くだろう。リカバリーのコーディネータは参加者に質問を行い、既にコミットの準備が整ったか確認し、参加者に実行を命令し、トランザクションをコミットする。
同時に落ちたコーディネータが復帰し、離れた時点から再開する。'prepared-to-commit'を参加者全員から受け取っていないことに気付き、タイムアウトとして、全ての参加者にトランザクションの'abort'メッセージを伝える。しかしこのメッセージはリカバリーのコーディネータにより送られたコミットメッセージと交互に送信され、あるノードはコミットメッセージを最初に受取り、別のノードは'abort'を受け取る。結果は不安定な状態となり、幾らかのノードはコミットするが、他は行わない。
あなたはまだこれが現実の問題を表しているのか納得できないかもしれない。なぜ落ちたコーディネータは自身が落ちたことに気づかないのか？そして自身をプロトコルから消去しないのか？ 答は障害を検知することはたとえ自分自身のことであっても常に簡単ではないためだ。このケースでの"障害"は実際にはコーディネータが決められた時間内に返答するのに失敗した(それがリカバリーのコーディネータに引き継がさせた)のであり、マシンクラッシュである必然性は無い。重い処理量はコーディネータのメッセージ処理に対し任意の長い間の遅れを生じさせ得る。同様にネットワークの通信量が重い場合に、任意の時間メッセージの送信を遅らせることが有り得る。同期的なネットワークモデルではリモートホストがメッセージを処理し、返答を行うことができる時間の量に限界がある。非同期モデルではそのような限界は無い。非同期性が引き起こす鍵となる問題はタイムアウトが障害検知の代理としてもはや信頼できないことだ。ホストの実行がただ遅く、それが死んだと宣言するその瞬間に返信しようとしている可能性が常にある。同様にノードが死んでいるのかどうかを、リカバリーメカニズムが邪魔されるのを防ぐために判断することは誰にも不可能である。
フェイルリカバーモデルは同期モデルには存在しない、非同期ネットワークにて起こりうる障害を巧妙に説明する。
私が説明した3PCはこれらの障害に対して回復力がない。実際にクラッシュストップな障害モデルの同期的なネットワークのみにてうまく働く。実際のネットワークはこのようなものではない。マシンは重い負荷にさらされ、パケットは失なわれ、複製され、遅延し、一般的にネットワークのタイミングについて多くを語ることはできない。
従ってこれらの問題に対処するために、他の合意アルゴリズムを必要とする。
この時点がレスリーランポートが彼のPaxosプロトコルを携えて現れた場所だ。
それは1990年台に発見され、高名を得た。
Paxosは非同期ネットワークに対して大抵回復力を持つ初めての正しいプロトコルだ。
FLP impossibilityのコンテキストにおいては、どんなプロトコルも非同期ネットワークでの実行は正しくないことを思い出せ。
Paxosは非同期性に耐え、良い行いが回復されるまで待つ。3PCのいくつかの変異のように正確性を犠牲にしない。
Paxosは活性、すなわち停止の保障、をネットワークが非同期的振舞いをする時に犠牲にする。
同期が戻った時のみ停止する。
合意プロトコル開発の主なイベントは大いに単純化すれば以下のように要約される。
- ジム・グレーと他は1970年代に2PCを提案した。問題は同期的ネットワークでも1つのノードの障害でブロック状態が発生した。
- デール・スキーンと他は1980年代初期にブロッキングを防ぐためには余分に3番目のフェーズが必要であることを示した。3PCは明らかな必然的帰結だ。しかし正確さを証明できない。実際に幾らかのネットワーク状態の下で不正確さを被る。
- レスリー・ランポートがPaxosを提案した。それはいつかは同期する非同期ネットワークにおいて正確さを証明可能で、参加者の過半数が有効であればブロッキングを起こさず(つまりn/2の障害に耐える)、最も良好なケースでは最小のメッセージ遅延であることが証明可能である。
Paxosの詳細
用語解説
Paxosプロトコルのインスタンス中の登場人物は2PCや3PCに近いものがある。
1つのノードが"proposer"を演じる。プロトコルの初期化に対し責任を持つ。
同時に1つのノードのみが"proposer"を演じる。もし2つかそれ以上のノードが"proposer"を選択したとき、多くの場合、プロトコルはただ1つのノードのみがproposerを演じることを続けるまでは停止できない。繰返しになるが、正確さのために停止性を犠牲にしている
残りのノードはPaxosの用語でacceptorと呼ばれ,提案された値についての意思統一を協力して行う
acceptorはproposerの提案に対し、何らかの理由で拒否する以外は原則的に賛成し、返信として未来にその提案を承認することを約束する。この約束は他のproposerから来る提案を誤って承認することはないことを保障し、とりわけ元のproposerの最新の提案のみを受け入れることを確約する
"承認"とはここではacceptorがその提案に対し最終的な提案だと認知しコミットすることを意味する。
一度acceptorの過半数が同じ提案を承認すればPaxosプロトコルは停止することができ、提案された値はそれに興味を持つノードに対し配布されたと見做す。(これらは"listner"と呼ばれる)
プロトコル
基本的にはPaxosは2PCにとても良く似ている。proposerは'prepare'リクエストを複数のacceptorに送る。複数のacceptorがそれらの提案を受け入れる合意を示したとき、proposerはcommitリクエストを複数のacceptorに投げる。最終的にacceptorはproposerに対しcommitリクエストの成否を告げる。一旦、十分な数のacceptorが値にcommitしたことをproposerに伝えたならばプロトコルは停止する。しかし、acceptorが提案を受け入れる時とproposerがどんな値を承認する側に続けてリクエストできるかという細部にPaxosの悪魔が宿る
Paxosは2つの重要なメカニズムを2PCに加えている。1つは提案に順序付けを行うことで例えば2つの提案のうちどちらを承認するべきかが決定できることだ。二つ目の改善点はacceptorの過半数が承認を決定したことを示したときに提案が受け入れられたと考えることだ。2PCはこれと異なり全てのacceptorが同意した時だけ提案が承認される。
このことは2PCをblockingの特徴へと導く。1つの故障したノードにより、proposerが絶対に来ない返信を待つことにより、プロトコルが絶対に停止しない。Paxosはそうではなく、半数に近いノードが落ちても良く、返信に失敗してもかまわずにプロトコルは正しく続く。
順序番号
全ての提案には任意のproposerが作成できると考えられるユニークな順序番号でタグ付けされる。
この順序番号は提案を完全に順序付けるために用いられ、全てのacceptorはどの提案が前でどれが後かを知ることができる。提案が来た時にacceptorは受け取った中でどの提案が最も大きな番号を持つか確認する。
もし新しい提案が現在最も大きな提案の後に順序付けられた場合、acceptorは新しい提案より前に位置付けられる提案は1つも承認しないことを保障する'promise'を返す。
別の場合として、新しい提案が現在の最も大きな提案より前に順序付けられる場合、acceptorはそれをリジェクトし、現在のプロポーザルの順序番号を返す。
これがproposerに対して次回の提案にて十分に大きな順序番号を当て推量ではなく、選択可能にする。
この順序付けが用いられることで、どんな順でprepareリクエストを持つメッセージが来ようとも、Acceptorはそれ以上のコミュニケーション無しにどれに対して同意するか暫定的に承認することを可能にする。
これが異なるホストに対しメッセージが異なる順で到着する可能性という非同期システムの作為に対処するのを手助けする。
どうやって全ての提案がユニークな番号付けがされたか確認できるだろうか？ 最も簡単な方法は全てのProposerが互いに重ならない順序番号の集合から番号を選択することだ。具体的な1つの現実的方法は順序番号とアドレスのペアを作ることだ。ここでアドレスはProposerのユニークなネットワークアドレスの値だ。このペアは完全に順序があり、同時に全てのProposerが十分に大きな順序番号を選ぶことにより、他人よりも大きな値を付けることが可能だ。
過半数
単純な1つの事実がなぜ全てのacceptorから同意を得ること無しにプロトコルが正しいと呼べるのか理解することを手助けする。任意の2つの過半数のacceptorの集合は最低でも1つの共通なacceptorを持つ。
従ってもし2つの提案が過半数のacceptorの集合により同意されたとしたら、最低でも1つのacceptorは両方に同意したことになる。これは例えばある別の提案が作られたとき、第3の過半数集合には以前の2つの提案の両方を見たacceptorが含まれているか、またはそれぞれ別々の提案を見た2つのacceptorが含まれていることを示す。
これはプロトコルがどの段階にいようとも、実行に影響を与えるかもしれない全ての提案の完全な状態をリカバーするのに十分な情報が存在していることを意味する。
集団として、あるacceptorの過半数は完全な情報を得るだろう。そして正当な提案のみが承認されることを保障する。
正当な提案
proposerがacceptorの過半数からprepareメッセージに対するレスポンスを受け取ったら、proposerは続行可能で、acceptorに対し提案した値をcommitするよう要請することができる。再びこれは2PCにとても良く似ている。例外も再びであるが、例外としてproposerが正当に提案できる値に制約がある。複数のproposerがある時点で同時に値を提案する可能性があることを思い出して欲しい。可能な限り最小の過半数のacceptorに対してproposerが自分の提案にcommitした時点で、1つのacceptorが落ちたケースを想定しよう。過半数の承認による確定メッセージはproposerに届かない。したがってプロトコルは停止しない。2つ目のproposerが次に値を提案することを試すだろう。それは過半数にacceptされる。なぜならば2つ目のproposerはそのリクエストを最初のリクエストよりも後ろに順序付けているからだ。
2つ目のproposerは自分の提案をcommitする。過半数のacceptorはそれに返事する。2つ目のproposerはプロトコルが完了したと認識する。この時、落ちたacceptorはリカバー可能で、最終の承認メッセージを最初のproposerに送ることができる。そして最初のproposerはプロトコルが完了したと認識する。もし最初と次のproposerの両者が異なる値を提案していると正確性が侵される。これは問題である。
この実行は非同期なネットワークでは防ぎようがない。従って残された道はどうにかして両方のproposerが同じ値を提案したことを確認することである。これは上記の問題を、全てのacceptorにてcommitされた値がどのproposerにより提案されたかに関わらず同じであることを確認することにより、防ぐことが可能だ。
全ての提案された値が同じであること確認することは簡単だ。
acceptorがprepareリクエストに返信する時、既に承認した提案の内で最も大きな順序番号の提案の値と共に返信する。
proposerはするとこの値がcommitされたかどうかを尋ねることのみに束縛される。
このようにしてプロトコルはproposerに対して他の完了した提案について情報を与え、それに対し自分が元々提案した値ではなく、他が完了した値をcommitするように強制する。
このことが我々の合意に関する要件に対し何ら違反しないことに注意せよ。
我々は結果としてどの値がcommitされるか気にしない。proposerもまたその値がどこかのproposerにより元々提案されていれば、気にしない。acceptorはprepareリクエストに対し同意または拒否のレスポンスをすることにより意見を表明することを許されている。
しかし一度過半数が値を承認することに同意すれば、その値こそが承認される値となる。
acceptorの過半数に全てのprepareリクエストに返信させることにより、Paxosはprepareリクエストに返信した全ての過半数のacceptorの集合が、以前に同意された個々のproposalを知っているacceptorからの返信を持っていることを確実にする。その結果、proposerがcommitフェーズを開始する前に、それ以前に承認された提案の内、最も大きな番号の提案の値がいくつであるのか知っていることが保障される
これが帰納的に全ての承認された提案は同じ値に対するものであることを保障する
順序番号がここでも役に立つ。Acceptorは提案に対し同意する時、現在の提案より小さい番号の提案は全て承認しないことを約束する。これによりあるproposerの小さな順序番号の提案がより大きな番号の提案が同意される間に承認される問題が起こるのを防ぐ。(より大きな順序番号の提案を持つproposerが全ての以前に承認された値について聞いている間に。) そして異なる値がcommitされることも防ぐのだ。
正確なプロトコル
形式ばらずに説明するが、プロトコル中の各担当者が実行しなければならないステップは以下になる。
PROPOSERS
- 番号nを付けた提案をacceptorの過半数に提示する。acceptorの過半数が返信するのを待つ。
- もしacceptorの過半数が同意(agree)を返信する時、acceptorは同時に彼らが既に承認した任意の提案の値を送り返してくる。それらの値の1つを取り、commitメッセージを提案の番号とその値と共に送る。もし以前に一度も値が承認されていない場合、自分自身のものを使用する。別の場合として過半数が'reject'を返したり、返信に失敗した場合に提案を中止し、最初からやり直す
- もし過半数がcommitリクエストに対し'accepted'メッセージを返したなら、プロトコルは終了したと見做す。そうでない場合、proposalを中止し、最初からやり直す
ACCEPTORS
障害耐性
Paxosは2PCよりも障害耐性が高い。全員の賛成でなく過半数を用いることはacceptorの半数までの障害に耐えうることを意味する。f台の障害に耐えるには2f+1台のacceptorを必要とする。もしProposerが障害で落ちた場合、別のProposerを用意しそれ自身の提案を発行することによりプロトコルを引き継ぐことが可能だ。もしオリジナルのProposerが復帰したとしても以前にacceptされた値のみcommitするルールと、既知の番号よりも大きな番号の提案のみ同意するというルールにより2つのProposerが一貫性を犯すことなく共存できることを保障する。
Paxosが失敗する場合もあることを知るのは簡単だ。2つのProposerが同時にアクティブである時、それらがより大きな番号の提案を巡って対決することがあり、交互に以前の提案より一つ大きな番号の提案を発行する場合がある。この状態が解決されるまで、そして一人のリーダーが合意されるまで、Paxosプロトコルが停止しない場合がある。
これは活性を妨害する。しかしながら、やがてPaxosはネットワークの状態が落着き、2つのProposerがお互いを確認し、どちらかに譲った時点で正しい状態に戻るだろう。(これが総意を得るのとは全く異なることに注意すること。一方のProposerが他方のProposerの提案がcommitされるように十分に長い間、身を引く必要がある。)
他にもPaxosが失敗する場合がある。Acceptorは自身が同意した最も大きな番号の提案とacceptした任意の提案の値の記録を安定したストレージに保持する必要がある。仮にそのストレージがクラッシュした場合に、Acceptorはプロトコル内にてその実行を駄目にしてしまう恐れのため役割を果たせない。(それが既に確認した提案に対して効果的に嘘をつくことによって。)
これはある種のBizantine Failureだ。Acceptorがプロトコルから逸脱する。一般的なBizantine Failureに対する耐性は複雑で明確にすることが難しい。(確実な方法はBizantineに落ちる可能性のあるf台のAcceptorに対し、別のf台をより多くの投票が行われるよう追加することだ。)
(Bizantine Failureは分散システムの用語でノードが嘘を付く可能性のある問題)
効率
理想的に正しいPaxosの実行ではメッセージカウントは低い。最初のフェーズでProposerはf+1のメッセージを送り、f+1のリプライを受け取る。これが次のフェーズでも続けられ、合計で4f+4のメッセージとなり、内メッセージの遅延は4つとなる。しかし、もし1つのAcceptorが障害を起こせば、プロトコルが提案の再提出が必要となるために完了するのにより長い時間が掛かる。そうではなくそのProposerがそのメッセージを2f+1台のAcceptor全てに放送したならば、それはプロトコルが遅延するまでにf+1台が失敗しなければならないことを暗示する。
もちろんもしProposerが落ちたなら次の間に遅延が発生する。
- 他のProposerが引き継ぐのを決めるまで
- 新しいProtocolのインスタンスが実行されるまで
障害が連続して発生したり、Proposerが既に記述されたとおりに決闘モードに入ってしまうとメッセージの数は偶発的に大きくなることがある。しかしネットワークが安定した状態に戻ればプロトコルの完了までの遅延はやはり4メッセージの遅れとなる。
またacceptorや恐らくproposerでもディスクへの書込コストを計算に入れなければならない。ディスク上での遅延はネットワーク上の遅延よりも非常に大きく成り得る。プロトコルはディスクの書込がレスポンスが送られる前に完了した場合のみに正しい。従ってディスクへの書込もクリティカルな要因である。
結論
このアーティクルはPaxosによる同意プロトコルの基本を説明した。また最初は無原則に見えたり、混乱の原因となるデザイン上の決定について論理的根拠を上げた。
Paxosには理想的環境にてメッセージの遅延を少くしたり、起動時間を少くするための最適化手法がいくつかある。それについてはいずれ別のアーティクルにて説明したい。
次の締め括りの後に、完全ではないが、このプロトコルをより深く知りたい人のために参考文献を挙げておく。
終章：Paxosの歴史
Paxosの歴史は普通の分散プロトコルに比べ比較的華やかだ。Leslie Lamportは1980年代の終わりにこのアルゴリズムを発見した。元々、Paxosの安全性と活動性の属性を満たすアルゴリズムは存在しないという逆の結論を証明しようという試みから産まれた。彼が努力すればする程、その結果はまるで彼から逃げていくようで、その努力は彼が実際にうまくいくプロトコルを作成したことが明かになるまで続いた。
その後、彼は論文を書き"Transaction on Computer Systems (TOCS)"に提出した。もしその論文が無味乾燥な物だったらこの話はそこで終わっただろう。しかし、Lamportは彼の研究を太古のPaxos島のとても怠惰な議会における、議案の投票上での同意形成の問題を解くことで表現した。Lamportはそれ以前に彼の研究をビサンチン将軍問題の論文にてアナロジーを通じて記述していた。同様のアプローチがここでも成功すると考えた。だが査読者はPaxos関連の記述を取り除くことを望んだ。Lamportはそれに従わず、論文を彼のキャビネットに押し込んでしまった。
そのプロトコルは口コミにて段々と評判を上げていった。さらにDe PriscoやLynch、Lampsonによるずっと正当な形式でのより長い論文を通して評価を上げた。Lamportは元の論文を最初の提出から役8年後に再提出を行い、TOCSは二度目は元々の形式にほぼ近い形にて出版した。
出版された論文はコンピュータネットワークとの関連を明確にした。そして既に難解なアルゴリズムを理解するのを難しくする余計な非直接的な記述を整理し、その表現により不明瞭になるのを直した。(冗談の部分であり、通常の理論計算機科学の論文にて歓迎される変更である。)
それでもその論文は一般に理解するのが難しいと思われた。Nancy Lynchといった著名人が論文を難しいと思うのだから我々一般人がその文脈を理解するのに失敗しても気を落とさずにすむだろう。その後、Lamportは"Paxos Made Simple (簡単にしたPaxos)"の出版をする気になった。とても短い論文でその調子はPaxosの作戦があまり成功しなかったことによる著者の失望とは矛盾していた。
Paxosアルゴリズムは、普通の言葉で語れば、とても簡単です。
それ以来、Paxosはよく知られるように成った。その評判の原因はGoogleの中心に積まれたChubbyにも向けられるだろう。このプロトコルを正しく実現するのはGoogleの"Paxos Made Live (Paxosを実現する)"に説明されているとおりに難しい。元のプロトコルには幾らかのバリエーションが作成された。恐らく最も重要なのは多重Paxosで、メッセージの複雑さを削減するためにリクエスト同士が連結することを可能にしている。
(Lamport自身から観た出来事の完全な記述が彼のWebページに存在する。)
http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos
参考文献
The Part-time Parliament
オリジナルの論文。プロトコルを理解してしまえばこのプレゼンをきっと楽しめるでしょう。"Made Simple"が省略した正確性に関する証明を含んでいます。
Paxos Made Live
Googleからのこの論文は論理的なアルゴリズムと実際のシステムとのギャップの架け橋となります。Paxosの実装においてあなたが想像もしないいくらかの考慮すべき現実的問題が記述されています。もしあなたがPaxosを使用するシステムを構築したいならこの論文を先に読むべきです。
Cheap Paxos and Fast Paxos
この2つの論文はオリジナルのプロトコルにいくつかの最適化を施します。
Consensus on Transaction Commit
このLamportとJim Grayによる短い論文は2PCが障害に耐性の無い退化したPaxosであることを示します。これは面白いPaxosへのイントロであり動機付けとなります。私がそうでした。
