Raft 合意アルゴリズム

使い方

• 「再生」を押すと時間が進みます。最初にタイムアウトしたノードが選挙を始め、過半数の票を集めるとリーダーになります。
• 「クライアントの要求を送る」でリーダーのログにエントリを書きます。過半数のノードに複製されるとコミットされます。
• ノード（図の円か S1〜S5 のボタン）を選んで、停止・再起動・すぐ立候補・島 B への切り離しができます。「リーダーを少数側に」で、リーダーともう 1 台を残りの 3 台から切り離します。
• 「◀」「▶」で 1 つ前 / 次のイベント（メッセージの到着・タイムアウト・送信）に移れます。キーボードでは Space で再生 / 一時停止、← → で 1 つ戻る / 進む、C で要求を送ります。
• 時刻はシミュレーションの中のミリ秒です。選挙のタイムアウトは 150〜300 ms、ハートビートは 50 ms、メッセージが届くまでは 12〜24 ms にしています。

Raft とは

Raft は、複数のサーバー（ノード）が同じ順序の操作のログを持ち続けるための合意アルゴリズムです。一部のノードが止まったりネットワークが分断されたりしても、過半数が動いていればサービスを続けられます。2014 年に「理解しやすさ」を目標に発表され、etcd・Consul・TiKV・CockroachDB などで使われています。

リーダー選挙

• ノードはフォロワー・候補者・リーダーのどれかです。時間は「任期」で区切られ、1 つの任期にリーダーは多くても 1 台です。
• フォロワーは、リーダーからの AppendEntries（エントリがなければハートビート）が一定時間届かないとタイムアウトし、任期を 1 つ上げて候補者になり、ほかのノードに投票を頼みます。タイムアウトの長さを乱数でばらつかせて、同時に立候補しにくくしています。
• 各ノードは 1 つの任期で 1 回だけ、自分よりログが古くない候補者に投票します。過半数の票を集めた候補者がリーダーです。
• 自分より新しい任期のメッセージを受け取ったノードは、その任期のフォロワーに戻ります。分断から戻った古いリーダーは、こうしてリーダーを降ります。

ログの複製とコミット

• リーダーはクライアントの要求を自分のログに書き、AppendEntries でフォロワーに送ります。このとき直前のエントリのインデックスと任期を添え、フォロワーは自分のログと一致しないと断ります。断られたリーダーは送る位置（nextIndex）を 1 つ戻して送り直し、一致するところまでさかのぼってから上書きします。
• 過半数のノードが持つエントリはコミットされ、もう失われません。どの過半数とも必ず 1 台は重なり、ログの古いノードは選挙に勝てないからです。
• ただし、リーダーが数でコミットするのは今の任期に書いたエントリだけです。前の任期のエントリは、今の任期のエントリと一緒にコミットされます（Raft の論文の図 8 の場合を防ぐため）。
• 少数側に残ったリーダーに書いたエントリは、過半数に届かないのでコミットされません。分断が直ると、多数側の新しいリーダーのログで上書きされます。

このアプリでは仕組みを見やすくするために単純化しています。ログの圧縮（スナップショット）・メンバーの変更・リーダーが当選直後に書く空のエントリは扱わず、断られたときの nextIndex は 1 つずつ戻します。