Paxos：故障の中でも1つの値に合意する

この論文が解いた問題

横にスクロール

分散システムでは、複数のサーバーが協調して1つのサービスを動かす。だが個々のサーバーはいつ停止するか分からず、サーバー間をつなぐネットワークもメッセージを失ったり、遅らせたり、届く順序を入れ替えたりする。この不確実さの中で、複数のノードが「ある1つの値」について意見を完全に一致させること、これを分散合意（consensus）と呼ぶ。合意する値は、次に実行すべきコマンドでも、どのノードをリーダーにするかでも構わない。肝心なのは、全員が同一の値を選び、しかも一度選んだ値は決して覆らないことだ。

こう書くと単純に思えるが、実際には難しい。あるノードが値を決めた直後に停止し、その決定を他のノードへ伝えられなかったら。過半数へ問い合わせている最中にネットワークが分断されたら。複数のノードが同時に別々の値を提案したら。こうした故障の組み合わせは無数にあり、素朴なやり方はどこかで矛盾した結論、つまり2つのノードが別々の値を「決定済み」と信じる状態を生んでしまう。

Leslie Lamportは1998年の論文「The Part-Time Parliament」で、この問題に厳密な解を与えた（原案の提出はさらに数年前にさかのぼる）。論文は古代ギリシアの島パクソスの「非常勤の議会」という寓話仕立てで書かれ、議員が出入りを繰り返す、すなわちノードが落ちたり復帰したりする中でも議事録の整合性を保つ様子として合意アルゴリズムを説明した。しかしこの物語形式はあまりに難解で、多くの読者が本質を読み取れなかった。そこでLamportは2001年、寓話を捨てて要点だけを述べた「Paxos Made Simple」を書き直す。この平易版によって、Paxosはようやく広く理解されるようになった。

核心アイデア

Paxosは3種類の役割を定める。値を提案する提案者（proposer）、提案を受け入れるか判断する受理者（acceptor）、決まった値を知る学習者（learner）である。1つのプロセスが複数の役割を兼ねてもよいが、安全性の議論で主役になるのは受理者だ。合意が成立するかどうかは、受理者の過半数（majority quorum）がどう振る舞うかで決まる。

アルゴリズムは2つのフェーズからなる。各提案にはグローバルに一意で単調増加する提案番号が付く。番号は提案の新しさを表し、大きいほど新しい。

第1フェーズでは、提案者がある提案番号を付けたprepare要求を受理者たちへ送る。prepareを受け取った受理者は、それまでに応じたどの番号よりも新しければ、「今後この番号より小さい提案は一切受け付けない」と約束（promise）し、もし既に何らかの値を受理していればその値も一緒に返す。第2フェーズでは、提案者は過半数からpromiseを集められたらaccept要求を送る。このとき提案する値は自由に選べるのではない。もしpromiseの返答の中に既に受理された値があれば、その中で最も新しい番号の値を必ず採用しなければならない。受理者は、約束した番号を破らない限りaccept要求に応じ（accepted）、過半数がacceptedを返した瞬間にその値は決定となる。

提案者 → 受理者たち: prepare(番号=5)
受理者たち → 提案者: promise(番号=5, これまで受理した値=なし)
提案者 → 受理者たち: accept(番号=5, 値=X)
受理者たち → 提案者: accepted(番号=5, 値=X)
→ 過半数がacceptedを返した時点で X に決定

この設計の要は「過半数」という一点にある。受理者が全部で5台なら、過半数は3台だ。そして任意の2つの過半数は、必ず少なくとも1台の受理者を共有する。5台から3台と3台を選べば、どう選んでも最低1台は重なるからだ。この「必ず交わる」性質があるおかげで、ある値が過半数によって決定された後に別の提案者が新しい提案を始めても、その提案者は第1フェーズで必ず、決定に関わった受理者のうち少なくとも1台を通じて、既に決まった値を知ることになる。ルールにより提案者はその値を引き継がざるを得ないので、後続の提案は同じ値を提案する。こうして一度決まった値は決して別の値に覆らない。

この「決まらないことがある」という限界は、Paxosの欠陥ではなく理論上の必然だ。非同期ネットワークで1台でも故障しうるなら、安全性と活性を同時に完全保証する合意アルゴリズムは存在しない。これがFLP不可能性（Fischer・Lynch・Paterson）である。Paxosは安全性を絶対に手放さない代わりに、活性を状況次第とすることで、この不可能性と矛盾なく両立している。

実務では活性を高める工夫として、提案者の中から1人をリーダーとして選ぶ。リーダーだけが提案すれば番号の奪い合いが起きず、安定して合意が進む。さらに、単一の値ではなくログの各スロット、つまり1番目のコマンド、2番目のコマンドと続く各位置ごとに合意を繰り返す形へ拡張したものをMulti-Paxosと呼ぶ。リーダーが安定している間は第1フェーズを省略でき、実質1往復で各コマンドを確定できるため、実システムはほぼこの形で動く。

その後の影響

Paxosは、理論上の興味にとどまらず、現実の大規模システムの土台になった。GoogleはロックサービスChubbyの中核にPaxosを据え、分散データベースSpannerもPaxosベースの複製で強い一貫性を実現している。ほかにも数多くの分散データベースや協調サービスが、Paxosまたはその変種を合意基盤として採用してきた。「1つの値に安全に合意する」という部品が、レプリケーション・リーダー選出・分散ロックといった機能へ横展開されたのである。

一方で、Paxosには「正しいが理解しにくい」という評判がつきまとった。論文の記述と実装の間にも距離があり、Multi-Paxosの細部は各社が手探りで埋めてきた。この理解しにくさそのものを問題と捉えて設計されたのが、後年のRaftである。Raftはリーダー選出・ログ複製・安全性を分かりやすい部品に切り分け、教育と実装のしやすさを最優先に掲げた。安全性の保証という到達点は同じでも、そこへ至る説明の道筋が違う。両者を読み比べると、合意という問題の骨格が立体的に見えてくる（Raftの論文、Raftによる合意）。

まとめ

Paxosは、ノードやメッセージが失われる現実の中でも、複数のノードが1つの値に安全に合意するための古典的アルゴリズムだ。役割を提案者・受理者・学習者に分け、prepareとacceptの2フェーズと過半数合意を組み合わせる。任意の2つの過半数が必ず交わるという単純な事実が、一度決まった値を絶対に覆らせない安全性を支える。決まらないことがある（活性は保証されない）という限界はFLP不可能性と整合し、リーダーを立てたMulti-Paxosが実務の解になる。ChubbyやSpannerを動かし、Raftを生んだこの論文は、分散システムを学ぶ上での出発点である。ほかの論文解説は論文で辿る分散システムから辿れる。