【ラフトアルゴリズム】
Raftアルゴリズム とは？
最終更新:
💡 変更の順序をそろえる、リーダーと過半数の合意
複数ノードで、実行する変更の順序に合意するためのアルゴリズム。リーダー選出とログ複製を分けて設計され、etcdなどで使われます。過半数の意味と、全ノードが常に同じ状態とは限らない理由を解説します。
📌 このページのポイント
- 変更をログに記録し、合意した順序で状態に適用する
- リーダー選出・ログ複製・安全性を分け、理解しやすさを重視して設計された
- 新しい変更の確定には、通常リーダーを含む過半数へのログ保存が必要
- 過半数が互いに通信できないと、新しい書き込みを確定できない
ひよこ Raftは多数決で正しい答えを決めるの？
ペンギン先生 情報の真偽ではなく、「どの変更をどの順序で実行するか」に合意するんだ。各ノードが同じ確定済みのログを順に適用して、食い違う変更を確定しないようにする。全ノードの処理が同時に終わる、という意味ではないよ。
ひよこ 書き込みはどう進む？
ペンギン先生 リーダーが変更をログに記録し、フォロワーへ複製する。現在のリーダーの任期で作られたログなら、リーダーを含む過半数が保存したことを確認して確定できる。3台構成なら2台、5台なら3台だね。単に通信が届いたこととは違うよ。
ひよこ リーダーが止まると？
ペンギン先生 連絡が一定時間来ないフォロワーが候補者となって選挙を始める。ノードは任期ごとに原則1票を投じ、候補者のログが十分新しいかも確認する。過半数の票を得た候補者がリーダーになる。票が割れたら次の選挙が必要になることもあるよ。
ひよこ 過半数の電源が入っていれば続けられる？
ペンギン先生 互いに通信でき、ログの保存なども進むことが必要だよ。ネットワークが分断されて過半数を確保できない側では、新しい書き込みを確定できない。リーダーの切り替え中に一時的に処理が待つこともあるんだ。
ひよこ 実際にはどこで使われる？
もっと詳しく知りたい人へ
古い任期のログも、過半数にあれば確定できる？
Raftでは、過去の任期のログを単に複製台数だけで直接確定することはしません。現在の任期のログを確定することで、その前にあるログも確定します。原論文の5.4.2節は、この制約が必要になる例を説明しています。
悪意あるノードにも対応できる？
原論文のモデルは、停止や復旧などの障害を扱い、ノードが任意の嘘をつくビザンチン障害を前提にしていません。合意したログを同じ状態に適用するには、状態遷移の決定性も必要です。通信・保存・実装の条件を無視して、Raftという名前だけで安全性を保証することはできません。
まとめ：ざっくりこれだけ覚えればOK！
「Raft」って出てきたら「複数ノードが変更の順序に合意する仕組み」と思えばだいたいOK！
📖 おまけ：英語の意味
「Raft Consensus Algorithm」 ＝ Raft合意アルゴリズム
💬 原論文の題名は「In Search of an Understandable Consensus Algorithm」。理解しやすい合意アルゴリズムを目指した設計であることを示しています。