Raft合意 — リーダー選出とログ複製

5台のサーバが、故障してもネットワークが切れても「同じ1つのログ」を守り続ける。そのための合意アルゴリズムが Raft です。過半数の多数決だけを頼りに、リーダー選出とログ複製がどう回るのか — 論文どおりの動きをすべてアニメで確かめます。

1. リーダーを1人選ぶ — ランダムタイムアウトと多数決

複製した状態を全台で一致させる王道は、「操作の並び（ログ）」に全員が合意することです。Raft はこれを「まずリーダーを1人決め、書き込みはすべてリーダー経由にする」方式で解きます。リーダーはハートビートを送り続けて生存を知らせ、フォロワーは各自の選挙タイムアウト（ランダムな長さ）が切れるまでにハートビートが来なければ、term（任期番号）を1増やして候補者になり、投票を募ります。過半数の票を集めた者だけがリーダーです。

下のデモで「リーダーを落とす」を押してみてください。ハートビートが途絶え、灰色リング（タイムアウトの経過）が最初に一周したノードが立候補し、再選挙が起きます。

リーダー選出 — タイムアウトが切れた者が立候補する
緑の小さな点＝ハートビート、紫＝投票依頼（RequestVote）、白＝投票。タイムアウトはノードごとにランダムなので、たいてい1台だけが先に立候補して一発で決まります。まれに同時立候補で票が割れても、次のランダムタイムアウトでやり直すだけ。落ちた旧リーダーは数秒後に復帰しますが、より高い term を見て黙って従います。
POINT — 同じ term にリーダーは高々1人 各ノードは 1つの term につき1票しか投じない。そして当選には過半数が要る。どの2つの過半数も必ず1台以上重なるから、同じ term で2人が当選することは数学的にあり得ない。term は「論理的な年号」で単調に増え、自分より高い term を見たら即座に従う（リーダーでも退位する） — この2つが Raft の安全性の土台。
過半数 = ⌊N/2⌋ + 1 N=5 なら 3票。どの2つの過半数も必ず重なるので、同じ term に2人のリーダーは生まれない
ハートビート間隔 ≪ 選挙タイムアウト ～ 一様乱数[T, 2T] ≪ 平均故障間隔 論文の目安は T = 150〜300 ms。ランダムなばらつきが「同時立候補 → 票割れ」をほぼ防ぐ

2. ログ複製 — 「過半数に書けたら確定」

クライアントの書き込みはまずリーダーのログに追記され、AppendEntries でフォロワーへ複製されます。ここが肝心：リーダーに書けた時点ではまだ未確定です。リーダー自身を含めて過半数のサーバに載った瞬間にコミットとなり、初めてクライアントへ成功を返せます。コミット位置（commitIndex）は次のハートビートに載せてフォロワーへ伝わります。

ログ複製 — コミット線は過半数の ACK で進む
破線のセル＝未コミット、実線＋緑塗り＝コミット済み。リーダー行の上の「3/5」は複製できた台数。S5 を遅くしても、残り3台（自分＋2台）がそろえばコミット線は進みます — 全員を待たないのが Raft の速さの理由。遅れた S5 にはあとから追いつかせればよいのです。
注意 — 「リーダーに届いた＝保存された」ではない 過半数に複製される前のエントリは、リーダーが落ちれば消えることがある。だから正しい実装はコミット後にだけ成功を返す。逆に、一度コミットしたエントリは過半数が生きている限り絶対に失われない（当選には過半数の票が要り、投票者は自分よりログが古い候補者を拒否するため、コミット済みエントリを持たない者はリーダーになれない）。
コミット条件: 複製数 ≥ ⌊N/2⌋ + 1（リーダー自身も1台に数える） 5台なら自分＋2台の ACK で確定。最も遅い2台をいつでも見捨てられる設計

3. ネットワーク分断 — 「2人のリーダー」はなぜ事故にならないか

ネットワークが割れて、旧リーダーが少数派に取り残されたとします。旧リーダーは自分が置き去りにされたことに気づけず、書き込みを受け付け続けます — しかし過半数の ACK が集まらないので永遠にコミットできません。一方、多数派側ではタイムアウトから新しい選挙が起き、より高い term のリーダーが誕生してコミットを進めます。分断が直ると、旧リーダーは高い term を見て身を引き、コミットできなかった書き込みはリーダーのログで上書きされます。

分断と復旧 — 少数派のリーダーはコミットできない
分断中に「書き込む」を押すと、少数派の旧リーダー S1 は受け付けはするものの、エントリは破線（未コミット）のまま。多数派側の新リーダーはすぐコミット（実線）します。分断を解消すると、S1 は高い term のハートビートを受けて退位し、未コミット分は赤くフラッシュして新リーダーのログに置き換わります（クライアントにはエラーか再試行として見えます）。

4. ログ不一致の修復 — 後ろから巻き戻して上書き

リーダー交代の混乱で、フォロワーのログには「足りないエントリ」や「余計なエントリ」が残ることがあります。Raft の AppendEntries には直前のエントリの (index, term) が同封されていて、フォロワーは手元のログと一致しなければ拒否します。リーダーは nextIndex を1つ下げて再試行 — 一致点が見つかるまで後ろから巻き戻し、そこから先をリーダーのログで上書きします。これで全ログは必ずリーダーに収束します。

一致性チェックをステップ実行 — 拒否 → 巻き戻し → 上書き
セルの色は term（t1／t2／t3）。フォロワーは term 2 のまま余計なエントリを2件書いてしまった状態です。照合が index 5 で一致した瞬間、それ以降が削除され、リーダーの3件で上書きされます。実装では「食い違った term とその最初の index」をヒントで返し、1 term ぶんまとめて飛ばす高速化が定番です。
一歩先へ — 論文 Figure 8 の罠と実装たち 細かいが重要な規則がもう1つ：リーダーは過去の term のエントリを「複製数が過半数に達した」という理由だけではコミットしない。古いエントリは、現 term のエントリをコミットするときに巻き添えで確定させる（論文 Figure 8 が示す、上書きで「コミット済みが消える」事故を防ぐため）。Raft は Ongaro & Ousterhout の論文（2014）で「Paxos と同等の性能を、理解しやすさを設計目標にして」提案され、etcd・TiKV・Consul など今日の分散基盤の心臓部で動いている。

5. まとめ