合意アルゴリズム
一部が故障しても、分散した複数ノードが単一の値に合意するためのアルゴリズム（Raft, Paxos）。
概要
合意アルゴリズム（コンセンサスアルゴリズム）は、ネットワークでつながった複数のノード（サーバ）が、一部の故障や通信の遅延がある中でも、ある一つの値について全員が同じ結論に到達するための手順です。「次に処理する命令はこれだ」「この設定値はこの内容だ」といった決定を、バラバラに動く機械の集団が矛盾なく共有するための、分散システムの心臓部と言える技術です。
一台のサーバなら、値を一つ決めるのは単にメモリに書き込むだけで済みます。ところが複数台に同じデータを持たせようとした瞬間（レプリケーション）、「どのノードの言い分が正しいのか」「返事をしないノードは死んだのか、単に遅いだけなのか」といった厄介な問題が一気に噴き出します。合意アルゴリズムは、こうした不確実な世界の上に「全員が同意した唯一の決定」という確固たる土台を作り出します。
代表的な実装が Paxos（ペイパス）と Raft（ラフト）です。Paxos は理論的な正しさで知られる古典ですが理解が難しく、それを「人間が理解できること」を目標に再設計したのが Raft です。ZooKeeper や etcd、Consul といった、多くの分散システムの根幹を支える調停役のソフトウェアが、この種のアルゴリズムを内部で動かしています。
なぜ生まれたか
データを複数台に複製すると可用性は上がりますが、「全員の内容を一致させ続ける」という新しい難題が生まれます。素朴に「全ノードに書き込めたら成功」とすると、一台でも遅かったり落ちていたりすれば書き込みが永久に止まります。逆に「一台でも書ければ成功」とすると、ノードごとに内容が食い違い、どれが正しいのか誰にも分からなくなります。故障がある前提で、それでも一貫した決定を下す方法が必要でした。
さらに厄介なのが、ネットワークが分断される「スプリットブレイン」です。ノード群が二つのグループに分断され、それぞれが「自分たちが正しい本隊だ」と思い込んで別々に書き込みを受け付けてしまうと、復旧後にどちらの更新を残すべきか収拾がつかなくなります。合意アルゴリズムは、この「二つの真実」が同時に成立することを原理的に防ぐために生まれました。その鍵が「過半数（クォーラム）」という考え方です。全体の半分を超えるノードが同意しなければ何も決められないことにすれば、分断された二つのグループが同時に過半数を握ることは決してありえないため、決定は常に一つに保たれます。
詳細
リーダーを一人選ぶ
Raft を例に、仕組みを追ってみましょう。Raft はまず、ノードの中から「リーダー」を一人だけ選び、書き込みの受付をリーダーに一本化します。全員が対等に書き込むと調整が複雑になるため、「決定を下せるのは常に一人」という単純な構造にするのが Raft の設計思想です。
各ノードは「フォロワー」「候補者」「リーダー」のいずれかの状態を持ちます。平常時はリーダーが定期的に心拍（ハートビート）を送り、フォロワーはそれを受けて「リーダーは生きている」と安心しています。ところがリーダーが故障して心拍が途絶えると、あるフォロワーがしびれを切らして「候補者」に変わり、自分への投票を全ノードに呼びかけます。過半数の票を集められたら、そのノードが新しいリーダーになります。
この選挙と、選ばれたリーダーが書き込みを複製していく流れを、時間軸で追ってみます。
リーダーが決まったら、クライアントからの書き込みはすべてリーダーが受け取り、それを「ログ」の新しいエントリとして全フォロワーに複製します。ここで重要なのが確定の条件です。リーダーは、過半数のフォロワーが「書き込めた」と返事した時点で、その項目を「コミット済み（確定）」とみなします。全員の返事を待つ必要はありません。過半数さえ書ければ、たとえ残りが遅くても落ちていても、決定は覆らないからです。この「過半数で確定」という一点が、故障に耐えつつ前に進むための核心です。
分断・障害が起きるとどうなるか
では、ネットワークが分断されたときにスプリットブレインが防がれる様子を見てみましょう。5台のノードが「3台のグループ」と「2台のグループ」に分断されたとします。3台側は過半数（3 ≧ 5の過半数）を満たすため、リーダーを選出して書き込みを続けられます。一方の2台側は、どうやっても過半数に届かないため、たとえリーダーがいてもそのリーダーは書き込みを確定できず、事実上停止します。結果として「書き込みを受け付けられる側」は常に一つだけに保たれ、二つの矛盾する真実が生まれません。
この性質は、CAP定理の言葉で言えば、分断（P）が起きたときに一貫性（C）を守るために可用性（A）を犠牲にする選択にあたります。少数派に取り残されたクライアントは「今は書けません」という応答を受け取ることになりますが、その代わりデータが壊れることは決してありません。多くの合意ベースのシステムは、この「一貫性優先」の側に立っています。
故障からの復旧時も過半数が効きます。落ちていたノードが復帰すると、自分のログが遅れていることを検知し、現リーダーから不足分を受け取って追いつきます。逆に、古いリーダーが分断中に受けていた未確定の書き込みは、復帰後に「過半数に達していなかった」ものとして破棄されます。「確定＝過半数に複製済み」という定義があるおかげで、何を残し何を捨てるかが機械的に決まるのです。
ここまでのリーダー選出・過半数・分断の力学は、実際にノードを落として観察するのが一番の近道です。
ノードをクリック = 停止/復帰。バーは選挙タイムアウトの残り（心拍が届くたびリセット）。
⏳ リーダー不在 — 選挙中…
5ノードが起動しました。最初に選挙タイムアウト（各ノードのバー）が尽きたノードが立候補します。ノードをクリックすると停止/復帰できます。
使いどころとトレードオフ
合意アルゴリズムは、多くの分散システムの「一つだけ正しい答えが要る」場所で使われます。誰がリーダーかを決める、分散ロックの持ち主を決める、クラスタ全体の設定を一貫して配る、といった調停役です。アプリが自前で実装することは稀で、実務では etcd や ZooKeeper のような合意を実装済みのミドルウェアに任せるのが定石です。Kubernetes がクラスタ状態を etcd に保存しているのも、この一貫した調停基盤を利用するためです。
トレードオフは性能です。すべての決定に「過半数への複製と返事の往復」が必要なため、単一ノードへの書き込みよりも必ず遅くなり、ノードを増やすほど1回の合意にかかる調整も増えます。可用性の観点でも、耐えられる故障は「過半数を維持できる範囲」に限られます（5台なら2台まで。3台なら1台まで）。したがって、あらゆるデータに合意を使うのではなく、「絶対に一つに定めたい少量の重要な決定」にだけ使い、大量のデータ本体は別の仕組みで扱う、という役割分担が現実的な設計になります。