Raft 合意

Raft はタイムアウト、遅延メッセージ、リーダー交代の中で複製ログの安全を保つ。本課は五サーバーで選挙と現任期のコミットを示し、ネットワークを分割する。少数側も新しい項目を保存できるが、そのコピーだけでコミットはできない。

五人が番号付き台帳を持ち、リーダーが新行を追加する。現任期の行を確定するには三コピーの証拠が必要だ。二冊だけの未コミット記録は、後の正当なリーダーに置き換えられ得る。

仕組み

主な状態は役割、current term、log。役割は Follower、Candidate、Leader、term は選挙の期だ。項目は index と term の組で識別し、4/t5 と 4/t6 は同位置でも別項目となる。

Follower は AppendEntries ハートビートを期待する。選挙タイマーが切れると任期を増やし Candidate となり、自分に投票して RequestVote を送る。各サーバーは一任期一票までで、候補ログが自身以上に新しい場合だけ許可する。最後の項目の任期、次にインデックスで比較し、長さだけでは決めない。五台では三票で当選し、タイムアウトと自票だけではリーダーでない。

Leader は命令をローカルログに追加して AppendEntries を送る。RPC の prevLogIndex と prevLogTerm で共通プレフィックスを確認し、その後の項目を扱う。

保存とコミットは別だ。セルに項目があっても commitIndex はまだ動かない。現任期の項目について Leader が多数の保存を知ると境界を進められる。Follower は後の AppendEntries の leaderCommit で学び、各自更新する。全体同時のスイッチはない。

選挙と複製はともに三対五でも証拠が違う。帯の votes と replicas(index n) を区別し、選挙三票をある項目の三コピーと見なさない。

ステップ実行

Minority partition は健康な状態から 2|3 に分け、両側で一書込を行う。全 RPC の記録ではなく、因果の境界を示す。

1. S1 は任期 5 の Leader、全五台が index 3 までコミット済み。
2. 分割後 S1 は S2 にしか届かないが、自身を Leader と認識する。
3. S1 は set y=7 を受け、未コミット 4/t5 を追加する。
4. S2 が保存して返信する。二コピーでも commitIndex は 3 のまま。
5. 少数側の証拠は 2/5 で止まり、新書込をコミットできない。
6. 二台の証明集合は互いに離れ得るが、三台の多数集合同士は必ず重なると比較する。
7. 反対側の S3 がタイムアウトし、任期 6 で自票を投じる。
8. S4、S5 が許可し、{S3,S4,S5} の 3/5 で S3 が当選する。
9. S3 は set z=8 を同じ index 4、term 6 に追加する。
10. S4 が 4/t6 を保存して確認する。二コピーではまだ足りない。
11. S5 が三つ目を保存し、返信で S3 が多数の証拠を得る。
12. S3 は commitIndex=4 に進め、set z=8 を適用する。
13. 分割が治り、S1 は 4/t5、S3 はコミット済み 4/t6 を持つ。
14. S1 は任期 6 を見て、先に Follower へ退く。
15. 共通なのは 3/t5 までで、index 4 は競合すると確認する。
16. S1 は未コミット 4/t5 を消し、4/t6 を入れ、コミット境界に従って適用する。
17. 少数側の書込は実際に保存されても、コミット履歴には入らなかったと分かる。

Election + commit は短い初回の流れを示す。三つ目の保存、確認の到着、多数証拠の確定、commitIndex の移動を分ける。

重なる多数が必要な理由

固定五台の任意の三台集合二つは少なくとも一台を共有する。Raft はその重なりと一任期一票、ログ新旧検査、現任期コミット規則を組み合わせ、交代を越えて確定プレフィックスを保つ。重なりだけで他規則を代替はできない。

分割中は S1/t5 と S3/t6 の二つのローカルな Leader 表示がある。同任期の二当選者ではない。S1 は新任期を知らず、S3 側だけが多数へ届いて新項目を確定できる。

回復後は先に任期で役割を訂正し、index/term のプレフィックス検査で未確定サフィックスを置換する。クライアントが少数側のローカル追加を成功としたら、後で消える値を確定と誤認する。

サービスへの影響

ローカル append や一 Follower の確認だけでは足りず、多数複製の証拠と任期規則が必要だ。コミット後に返信するサービスも、状態機械への適用まで待つものもある。再試行には要求 ID や重複排除が別途必要で、Raft の順序付けだけで繰り返し呼出が一度だけ実行されるわけではない。

三投票台は一台、五台は二台の利用不能に耐えられるが、残る多数が通信し進行条件を満たす必要がある。五台では二コピーでなく三コピーを待ち、耐障害性、遅延、資源を交換する。制御面やメタデータなど一致した判断が必要な状態に使える。

境界ケース

• 二つの Leader ラベルは別任期のローカル認識であり得る。新メッセージなしで古い認識は消えない。
• 同 index、異 term は競合だ。index だけでは 4/t5 と 4/t6 を見落とす。
• 未コミットコピーは少数側に残ってよい。即消去ではなく、条件を満たさず確定扱いしないことが必要だ。
• S2 が index 3 を保存しても commitIndex=2 の場合があり、後のハートビートが新境界を伝える。
• Election + commit の焦点例は S4、S5 が遅れても、最初の三台で選挙・コミットできる。
• votedFor は任期に属し、新任期で新しい投票を決めても旧任期の二票にはならない。
• 過去任期の項目をコピー数だけで直接コミットしてはいけない。現任期の項目を確定すると、その前のプレフィックスも間接的に確定する。

よくある間違い

• タイムアウトだけで Leader にする。候補は三票を必要とする。
• ローカル追加を committed とする。一コピーは開始点だ。
• 五台の多数を二とする。floor(5/2)+1=3 が必要。
• 全 commitIndex が同時に動くと期待する。境界の知識はローカルだ。
• 分割で全仕事が止まると思う。この例は三台側が進め、二台側の新規コミットが止まる。
• ログを直してから高任期を優先する。任期で役割を先に変え、プレフィックスで内容を決める。
• 保存した全項目が生き残ると思う。保証はコミット履歴で、4/t5 の消去は正しい。
• 五台全員を待つ。二台の遅延が全体を止め、多数を使う設計を失う。

モデルの範囲

五台固定、焦点 RPC を一歩ずつ、期限は決定的で場面内の順序逆転はない。新しいコミット境界を運ぶ二回のハートビートだけを描き、アイドル時のハートビート周期、再送、バッチ、永続化遅延、メンバー変更、pre-vote、joint consensus、ログ圧縮、スナップショットは省く。修復は各 nextIndex の減少を飛ばし共通プレフィックスへ進む。S2 の同じ追従は結末後のプロトコル進行に任せ、再描画しない。投票と現任期コミットは実規則で、時間は証拠を見せるために構成する。