分散合意アルゴリズム（Paxos / Raft）

分散合意とは何を解く問題か

複数のサーバーが、故障・遅延・メッセージ欠落のある環境で、1つの値（あるいは操作の順序）に全員が同意する——これが分散合意 (consensus) です。レプリケーションされた DB で「次にどのコマンドを適用するか」を全ノードで一致させる、リーダーを1台だけ選ぶ、といった用途の土台になります。

合意アルゴリズムが満たすべき性質は3つです。

• 安全性 (safety): 決して矛盾しない。一度決まった値は覆らず、2つの異なる値が同時に決まることはない。
• 活性 (liveness): いつかは決まる。十分なノードが生きていれば、最終的に合意に到達する。
• 耐故障性: 一部ノードが落ちても全体は止まらない。

ここで前提が重要です。これらのアルゴリズムはノードのクラッシュ（停止故障）には耐えますが、嘘をつくノード（ビザンチン故障）は想定しません。また FLP 不可能性として知られる理論結果から、完全非同期な環境では安全性と活性を同時には保証できないため、Raft も Paxos も「タイムアウト＝ある程度の同期」を仮定して活性を確保します。

なぜ過半数（quorum）なのか

合意の核心は、決定に過半数 (majority / quorum) の同意を要求することです。N 台なら floor(N/2) + 1 台。これは単なる多数決ではなく、安全性そのものを支える鍵です。

理由は集合の重なりにあります。任意の2つの過半数集合を取ると、必ず最低1台は共通します。たとえば 5 台なら過半数は 3 台。{A,B,C} と {C,D,E} は C で重なります。重複が無いような2グループ（各2台以下）は、どちらも過半数になれません。

N=5, 過半数=3
グループ1: {A, B, C}
グループ2: {C, D, E}
            ↑ 必ず1台以上が共通 (ここでは C)

この「任意の2つの多数派は交わる (quorum intersection)」性質が効きます。ある値が過半数に承認されて確定したなら、次に別の決定を試みる過半数の中にもその確定を知るノードが必ず混ざるので、確定済みの値を上書きできません。これが「2つの矛盾する決定が同時に成立しない」ことの保証になります。

Raft：3つの部品で合意を組み立てる

Paxos は合意の正しさを理論的に確立しましたが、難解で実装がばらつきがちでした。Raft は同じ安全性を、理解しやすさ最優先で再設計したアルゴリズムです。鍵は問題をリーダー選出・ログ複製・安全性の3つに明確に分割したことにあります。

各ノードは常に3状態のいずれかを取ります。

リーダー選出（leader election）

時間は term（任期） という単調増加の番号で区切られます。各 term には Leader は高々1人。Follower は一定時間 Leader から心拍 (heartbeat) を受け取らないとタイムアウトし、term を1増やして Candidate になり、自分に投票して他ノードへ投票を要求します。

RequestVote の流れ（term を t→t+1 に上げて立候補）
Candidate ──"term=t+1, 私に投票を"──▶ 各ノード
各ノード: 同じ term でまだ誰にも投票していなければ → 賛成（1 term 1票）
Candidate が過半数の票を得る ──▶ Leader 確定、heartbeat 開始

ポイントは1 term につき各ノードは1票しか投じないこと。過半数の交わり性質から、同一 term で2人の Leader が同時に過半数を得ることは不可能です。これがスプリットブレイン（レプリケーションとシャーディング で触れた二重リーダー問題）を構造的に防ぎます。なお票が割れて誰も過半数に届かない場合は、ランダム化したタイムアウトで次の選挙をずらし、再分裂を避けます。

ログ複製（log replication）

Leader が決まると、クライアントの各コマンドはログのエントリとして末尾に追記され、Leader が AppendEntries で全 Follower へ送ります。あるエントリが過半数のノードに複製された時点で「コミット (committed)」とみなされ、Leader はそれを状態機械に適用して結果を返します。

各エントリは (term, index, command) を持ち、Log Matching 特性を満たします。すなわち「同じ index かつ同じ term のエントリは、内容も、それ以前のログも全て一致する」。Follower は受信時に直前エントリの (term, index) が自分のログと合うかを検査し、食い違えば拒否します。Leader は一致点まで遡って上書きするため、ログは同一の順序へ収束します。

安全性保証（safety）

Raft の正しさは Leader Completeness（リーダー完全性） で締めくくられます。すなわち「ある term でコミットされたエントリは、それ以降の全 term の Leader のログに必ず含まれる」。

これを成立させるのが投票時の制限です。Follower は、要求してきた Candidate のログが自分のログと同じか、より新しい場合だけ投票します（新しさは最終エントリの term、同 term なら index で比較）。

投票条件（Candidate のログが古ければ拒否）
  cand.lastTerm  >  voter.lastTerm                  → 投票OK
  cand.lastTerm == voter.lastTerm
      かつ cand.lastIndex >= voter.lastIndex          → 投票OK
  それ以外                                           → 投票拒否

コミット済みエントリは定義上過半数が持っています。新 Leader も過半数の票が要ります。両者は必ず交わるので、コミット済みエントリを欠いたノードは過半数の票を集められず Leader になれません。よって確定済みのコマンドが失われたり、別の値で上書きされたりすることがない——これが安全性の論理的な背骨です。

Paxos と Raft の関係

横にスクロール

両者は別物の正しさを持つわけではなく、同じ quorum 交差の原理に立っています。Paxos は「1つの値に合意する」基本形 (Basic Paxos) と、それを連続適用してログを作る Multi-Paxos からなり、強いリーダーは性能上の最適化として登場します。Raft は最初から強いリーダー前提・連続ログ前提にすることで、選挙とログ整合の規則を簡潔にし、実装の取り違えを減らしました。実運用の合意ライブラリ（etcd, Consul など）の多くが Raft を採用するのはこの実装しやすさゆえです。

まとめ