分散合意アルゴリズム（Paxos / Raft）
複数台で1つの値に合意する仕組みを原理から理解。Raft のリーダー選出・ログ複製・安全性を追えば、なぜ過半数が必要かまで腹落ちします。
- 1.分散合意＝複数ノードが故障や遅延の中でも“同じ値・同じ順序”に同意すること。Raft はこれをリーダー選出・ログ複製・安全性の3点に分けて設計した。
- 2.過半数(quorum)を要求するのは、任意の2つの多数派が必ず1ノードで重なり、新旧の決定が矛盾しないことを数学的に保証するため。
- 3.Paxos は合意の理論的下地、Raft は同じ安全性を“理解しやすい形”に再構成した実装志向版。両者とも N 台中 floor(N/2)+1 台が生きていれば動く。
分散合意とは何を解く問題か
複数のサーバーが、故障・遅延・メッセージ欠落のある環境で、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つの矛盾する決定が同時に成立しない」ことの保証になります。
過半数の式 floor(N/2)+1 から、3台でも4台でも許容故障は同じ1台です（3台の過半数は2、4台の過半数も…ではなく3。4台は過半数3を保つのに生存3が要るので、耐えられるのはやはり1台だけ）。正確には N 台は floor((N-1)/2) 台の故障に耐えます。3→1台、4→1台、5→2台、7→3台。偶数を1足しても故障耐性が上がらない（むしろ票割れのリスクだけ増える）ため、合意クラスタは奇数台で組むのが定石です。台数とトレードオフは CAP 定理 の議論ともつながります。
Raft：3つの部品で合意を組み立てる
Paxos は合意の正しさを理論的に確立しましたが、難解で実装がばらつきがちでした。Raft は同じ安全性を、理解しやすさ最優先で再設計したアルゴリズムです。鍵は問題をリーダー選出・ログ複製・安全性の3つに明確に分割したことにあります。
各ノードは常に3状態のいずれかを取ります。
| 状態 | 役割 | 振る舞い |
|---|---|---|
| Leader | 唯一の書き込み窓口 | クライアント要求を受け、ログをフォロワーへ複製する |
| Follower | 受動的な複製先 | Leader からのログ/心拍に従う。タイムアウトで候補者へ |
| Candidate | 選挙中の一時状態 | 自分への投票を集め、過半数を得れば Leader へ昇格 |
リーダー選出（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 は一致点まで遡って上書きするため、ログは同一の順序へ収束します。
Raft で「コミット済み」とは、Leader が現在 term のエントリを過半数に複製できた瞬間を指します。過去 term のエントリは、それ単体での複製数では確定せず、現 term の新エントリが過半数に乗ったとき初めて間接的に確定します（古い term のエントリを多数派到達だけで確定とみなすと、後続の選挙で覆りうるため）。試験・面接ではこの「いつコミットか」が頻出ポイントです。
安全性保証（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 の関係
| 観点 | Paxos（Multi-Paxos） | Raft |
|---|---|---|
| 立ち位置 | 合意の理論的基盤・原典 | 同じ安全性を実装向けに再構成 |
| 設計の優先順位 | 最小性・一般性 | 理解しやすさ (understandability) |
| リーダー | 任意・後付けの最適化として導入 | 常時1人を前提に据える |
| ログの扱い | 個別の決定(インスタンス)の集合 | 連続したログとして強く秩序化 |
| 過半数の必要性 | 同じ(quorum 交差が安全性の核) | 同じ |
両者は別物の正しさを持つわけではなく、同じ quorum 交差の原理に立っています。Paxos は「1つの値に合意する」基本形 (Basic Paxos) と、それを連続適用してログを作る Multi-Paxos からなり、強いリーダーは性能上の最適化として登場します。Raft は最初から強いリーダー前提・連続ログ前提にすることで、選挙とログ整合の規則を簡潔にし、実装の取り違えを減らしました。実運用の合意ライブラリ（etcd, Consul など）の多くが Raft を採用するのはこの実装しやすさゆえです。
まとめ
分散合意は故障や遅延の中で全ノードを同じ値・同じ順序に揃える仕組みです。Raft はこれをリーダー選出・ログ複製・安全性の3部品に分け、Paxos と同じ正しさを実装しやすい形にしました。すべての土台は過半数 (quorum)——任意の2つの多数派が必ず交わるから、確定済みの決定は覆らず、二重リーダーも起きません。だからクラスタは奇数台で組み、N 台は floor((N-1)/2) 台の故障に耐えます。合意は安全だが速くはないので、「ズレが許されない一点」に絞って使うのが勘所です。
データベース Article
分散合意アルゴリズム（Paxos / Raft）を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
分散システム
比較で見る軸
難易度: advanced / カテゴリ: データベース / タグ数: 5
導入後に効く点
過半数(quorum)を要求するのは、任意の2つの多数派が必ず1ノードで重なり、新旧の決定が矛盾しないことを数学的に保証するため。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- データベース
- タグ数
- 5
判断チェックリスト
- 自社の用途が「分散システム / 合意アルゴリズム」に近いか確認する。
- 強みである「分散合意＝複数ノードが故障や遅延の中でも“同じ値・同じ順序”に同意すること。Raft はこれをリーダー選出・ログ複製・安全性の3点に分けて設計した。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。