合意アルゴリズム
Consensus Algorithm ・ ごういあるごりずむ
一部のノードが故障しても、過半数の同意で複数ノードが一つの決定を共有する手順（Raft・Paxos）。
✦ 30秒で試す — 航海全員の返事を待たずに確定しても、決定は覆らない5台を6台に増やすと、壊れても動き続けられる台数は？予想してみる概要
合意アルゴリズム（コンセンサスアルゴリズム）は、ネットワークでつながった複数のノード（サーバ）が、一部の故障や通信の遅れがある中でも、ある一つの値について全員が同じ結論に到達するための手順です。「次に処理する命令はこれだ」「この設定値はこの内容だ」「いまのリーダーはこのノードだ」といった決定を、バラバラに動く機械の集団が矛盾なく共有するための、分散システムの心臓部と言える技術です。
1台のサーバなら、値を一つ決めるのはメモリに書き込むだけで済みます。ところが複数台に同じデータを持たせた瞬間（レプリケーション）、「どのノードの言い分が正しいのか」「返事をしないノードは死んだのか、遅いだけなのか」といった問題が噴き出します。合意アルゴリズムは、こうした不確かな世界の上に「過半数が同意した、覆らない決定」という土台を作ります。
代表的なのが Paxos（パクソス）と Raft（ラフト）です。Paxos は理論的な正しさで知られる古典ですが、理解と実装が難しいことで有名でした。それを「人間が理解できること」を目標に設計し直したのが Raft です。etcd や Consul は Raft を、ZooKeeper は Paxos に近い独自の手順（Zab）を内部で動かしていて、多くの分散システムの調停役を担っています。
なぜ生まれたか
データを複数台に複製すると可用性は上がりますが、「全員の内容を一致させ続ける」という新しい難題が生まれます。素朴に「全ノードに書き込めたら成功」とすると、1台でも遅かったり落ちていたりすれば書き込みが永久に止まります。逆に「1台にでも書ければ成功」とすると、ノードごとに内容が食い違い、どれが正しいのか誰にも分からなくなります。
さらに厄介なのが、ネットワークが分断される「スプリットブレイン」です。ノード群が二つに分かれ、それぞれが「自分たちが本隊だ」と思い込んで別々に書き込みを受け付けると、復旧後にどちらの更新を残すべきか収拾がつかなくなります。この問題を原理的に防ぐ鍵が「過半数（クォーラム）」です。全体の半分を超えるノードが同意しなければ何も決められないことにすれば、分断された二つのグループが同時に過半数を握ることはありえないので、決定は常に一つに保たれます。
この考え方を厳密なアルゴリズムにしたのが、レスリー・ランポートの Paxos です。1989年に技術報告として書かれ、1998年に論文「The Part-Time Parliament」として発表されました。架空のギリシャの島の議会になぞらえた書き方が難解で、ランポート自身が2001年に「Paxos Made Simple」という平易な解説を書いたほどです。それでも実装では細部の設計が大量に必要で、2014年にスタンフォード大学のディエゴ・オンガロとジョン・オースターハウトが、理解しやすさを第一の目標に据えた Raft を発表しました。リーダーを1人に決め、ログをリーダーから一方向に流す、という単純な構造にしたことで、Raft は多くの実装に採用されました。
背景には理論上の壁もあります。1985年のフィッシャー、リンチ、パターソンの FLP 不可能性定理は、「メッセージの遅延に上限がない非同期のネットワークでは、1台でも止まりうるなら、必ず有限時間で合意に至る決定的なアルゴリズムは存在しない」ことを示しました。止まったのか遅いだけなのかを見分けられない以上、待ち続けるか見切るかしかないからです。そこで Paxos や Raft は、「決定が食い違わないこと（安全性）」はどんな状況でも守り、「いつか決まること（活性）」はタイムアウトが現実的に働く状況で保証する、という割り切りをしています。
詳細
役割は3つ、状態はこう移る
Raft を例に、仕組みを追ってみます。Raft はノードの中から「リーダー」を1人だけ選び、書き込みの受付をリーダーに一本化します。全員が対等に書き込むと調整が複雑になるので、「決定を下せるのはその任期のリーダーだけ」という単純な構造にするのが Raft の設計思想です。各ノードは「フォロワー」「候補者」「リーダー」のいずれかの状態にあり、次のように移り変わります。
時間は「任期（term）」という番号で区切られます。リーダーは定期的に心拍（ハートビート）を送り、フォロワーはそれを受けるたびに選挙タイムアウトをリセットします。心拍が途絶えてタイムアウトが切れたフォロワーは、term を1つ上げて候補者になり、自分に1票を入れてから全ノードに投票を頼みます。各ノードは1つの term につき1票しか投じないので、過半数の票を集められる候補者は、1つの term に多くて1人です。
リーダーが決まったら、クライアントからの書き込みはすべてリーダーが受け取り、それを「ログ」の新しい項目として全フォロワーに複製します。リーダーは、過半数のノード（自分を含む）がその項目を書けたと分かった時点で、項目を「コミット済み（確定）」とみなし、次の心拍で確定した位置をフォロワーに知らせます。全員の返事を待つ必要はありません。この「過半数に届いたら確定」という一点が、故障に耐えつつ前に進むための核心です。
安全性を支える二つの工夫
選挙タイムアウトの長さは、ノードごとに一定の範囲（Raft の論文では150〜300ミリ秒の例）からランダムに選びます。全員が同じ長さだと、リーダーが落ちた瞬間に全員が同時に候補者になり、それぞれが自分に投票して票が割れ、次のタイムアウトでもまた同時に……と、誰も選ばれない状態が続きかねません。ばらつかせておけば、たいていは1台だけが一足先に候補者になり、ほかのノードがまだフォロワーのうちに票を集めきれます。
もう一つが「選挙制限」です。投票を頼まれたノードは、候補者のログが自分より古ければ、term がいくら新しくても票を入れません（最後の項目の term が大きいほうが新しく、同じなら長いほうが新しい）。確定した項目は過半数のノードが持っているので、過半数の票を集められる候補者は、必ずその項目を持っているノードから少なくとも1票をもらわなければなりません。つまり、確定した項目を持たない候補者はリーダーになれず、確定した書き込みは、リーダーが何度代わっても消えません。
分断・障害が起きるとどうなるか
5台のノードが「3台の島」と「2台の島」に分断されたとします。3台の島は過半数を満たすので、リーダーを選び直して書き込みを確定し続けられます。2台の島に古いリーダーが取り残されていても、そのリーダーが受け付けた書き込みは2台にしか複製できず、確定できません。
分断が解けると、古いリーダー N1 は、より新しい term の心拍を受けて自らリーダーを降ります。N1 と N2 のログにある確定していない項目 d は、新しいリーダーのログで上書きされて消えます。過半数に届いていなかったので、誰にも「確定した」とは伝わっておらず、消しても約束は破られません。落ちていたノードが戻ってきたときも同じで、リーダーから足りない項目を受け取って追いつきます。
この性質は、CAP定理の言葉で言えば、分断が起きたときに一貫性を守るために、少数派の側の可用性を諦める選択にあたります。少数派の島に取り残されたクライアントは書き込めませんが、その代わりデータが食い違うことはありません。
ここまでのリーダー選出・過半数での確定・分断の力学は、実際にノードを止め、線を切って確かめるのが一番の近道です。リーダーが決まったら書き込み、次に「リーダーを2台の島に分断」を押して、取り残されたリーダーにも書き込んでから線を戻してみてください。1台だけを孤立させてから戻すと、term だけが大きくなったノードが選挙をかき乱し、それでもログが古いので票をもらえない（選挙制限）様子も見えます。
5台がリーダーを選んでいます（各ノードの下のバーが選挙タイムアウトの残り）。リーダーが決まったら「書き込む」を押し、3台に届いて確定する様子を見てください。ノードを押すと止まり、線を押すと切れます。
使いどころとトレードオフ
合意アルゴリズムは、分散システムの「一つだけ正しい答えが要る」場所で使われます。誰がリーダーかを決める、分散ロックの持ち主を決める、クラスタ全体の設定を一貫して配る、といった調停役です。アプリケーションが自前で実装することはまれで、etcd や ZooKeeper のような、合意を実装済みのミドルウェアに任せるのが定石です。Kubernetes がクラスタの状態を etcd に保存しているのも、この調停基盤を利用するためです。
トレードオフは性能と台数です。すべての決定に「過半数への複製と返事の往復」が必要なので、1台への書き込みより必ず遅くなります。耐えられる故障は過半数を維持できる範囲に限られ、3台なら1台、5台なら2台までです。台数を増やすと耐えられる故障は増えますが、1回の合意で待つ返事も増えます。4台は3台と同じく1台までしか耐えられないので、台数は奇数にするのが普通です。そのため、あらゆるデータに合意を使うのではなく、「絶対に一つに定めたい少量の重要な決定」だけに使い、大量のデータ本体は別の仕組みでレプリケーションする、という役割分担が現実的です。
最後に、Raft や Paxos が想定しているのは「止まる・遅れる・メッセージが消える」故障（クラッシュ故障）で、嘘をつくノードは想定していません。乗っ取られたノードが偽の投票やログを送ってくるような故障（ビザンチン故障）に耐えるには、f 台の裏切りに対して 3f+1 台を用意する PBFT（1999年）のような、より重い別系統のアルゴリズムが必要です。ブロックチェーンの合意は、こちらの系譜にあります。
試問
5台のサーバが、過半数（3台）に複製できた書き込みだけを「確定」させるクラスタです。ノードを押すと止まり、ノードどうしをつなぐ線を押すと切れます。リーダーが決まったら「書き込む」で書き込みを送れます。
5台がリーダーを選んでいます（各ノードの下のバーが選挙タイムアウトの残り）。リーダーが決まったら「書き込む」を押し、3台に届いて確定する様子を見てください。ノードを押すと止まり、線を押すと切れます。