> [!abstract] 概要(abstract 日本語訳) > Raft は複製ログを管理するための合意アルゴリズムである。(multi-)Paxos と等価な結果を生み出し、Paxos と同等の効率を持つが、その構造は Paxos とは異なる。この違いにより Raft は Paxos より理解しやすくなっており、実用システムを構築するためのより良い基盤も提供する。理解しやすさを高めるために、Raft はリーダー選出・ログ複製・安全性といった合意の主要要素を分離し、考慮すべき状態数を削減するためにより強い一貫性を強制する。ユーザースタディの結果は、Raft が Paxos より学生にとって学びやすいことを示している。Raft はまた、クラスタメンバーシップを変更する新しいメカニズムを含んでおり、安全性を保証するために重複多数決を使用する。 ## 論文情報 - **タイトル**: In Search of an Understandable Consensus Algorithm - **著者**: [[Diego Ongaro]]、[[John Ousterhout]]（[[Stanford University]]） - **発表媒体**: 2014 USENIX Annual Technical Conference（USENIX ATC '14） - **発表日**: 2014 年 6 月 19–20 日、Philadelphia, PA - **受賞**: **Best Paper Award** - **URL**: https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro - **拡張版**: http://ramcloud.stanford.edu/raft.pdf（クライアント対話・ログ圧縮を含む） - **形式仕様**: TLA+ による仕様と安全性証明(〜400 行 TLA+・〜3500 語非形式証明)[28] ## 概要 Raft は複製ログ管理のための合意アルゴリズムであり、**理解しやすさを第一設計目標**として生まれた。Paxos の 2 大問題(非常に難解・実用実装への不適切な基盤)を解決するため、問題を「リーダー選出」「ログ複製」「安全性」の 3 サブ問題に分解し、非決定論と状態空間を最小化する設計をとった。Stanford・UC Berkeley 合計 43 名の大学院生を対象としたユーザースタディで、33 名が Raft クイズの得点を Paxos クイズより高く取り（平均差 4.9 点/60 点）、理解しやすさを実証した。 **Figure 1: Replicated state machine architecture** ![[_attachments/atc14-paper-ongaro/fig01-replicated-state-machine.png]] (Figure 1. 複製ステートマシンのアーキテクチャ。コンセンサスモジュールが複製ログを管理し、同一コマンド列を各ステートマシンに適用することで一貫した出力を生み出す。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) ## 問題設定 - **入力**: クライアントからのコマンド列 - **出力**: すべてのサーバーが同一コマンド列を同一順序で適用した決定論的ステートマシンの出力 - **前提**: 非ビザンティン障害のみ想定(ネットワーク遅延・パケット損失・パーティション・クラッシュ)。大多数のサーバーが稼働し通信できれば動作する。5 サーバー構成なら 2 障害耐性。 - **既存問題**: Paxos は理解困難かつ実装基盤として不適切(シングルデクリー分解・ピアツーピアコア・詳細不足の multi-Paxos)。 ## 提案手法 ### アーキテクチャ **強いリーダーモデル**: Raft は選出された唯一のリーダーに複製ログ管理の全責任を与える。ログエントリはリーダーからフォロワーへの一方向にのみ流れる。これにより複製ログ管理が単純化される。 各サーバーはある時点において **Follower**・**Candidate**・**Leader** の 3 状態のいずれかにある。 **Figure 4: Server states** ![[_attachments/atc14-paper-ongaro/fig04-server-states.png]] (Figure 4. サーバーの状態遷移。フォロワーはリーダー・候補者からのリクエストに応答するだけ。タイムアウト → 候補者 → 多数決で勝利 → リーダーへ遷移する。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) **任期（Term）**: Raft は時間を任意長さの任期（term）に分割する。各任期は選挙から始まり、勝者は任期終了まで一人のリーダーが担う。term 番号は論理クロックとして機能し、古いリーダーの検出に使われる。 **Figure 5: Terms** ![[_attachments/atc14-paper-ongaro/fig05-terms.png]] (Figure 5. 時間は任期に分割される。各任期は選挙で始まり、成功すれば単一リーダーが任期末まで管理する。一部の選挙はスプリットボートで失敗し、リーダーなしで任期が終わる。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) ### 安全性保証(Figure 3) **Figure 3: Raft safety properties** ![[_attachments/atc14-paper-ongaro/fig03-raft-safety-properties.png]] (Figure 3. Raft が常に保証する 5 つの安全性。Election Safety・Leader Append-Only・Log Matching・Leader Completeness・State Machine Safety。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) | 保証 | 内容 | |------|------| | Election Safety | 与えられた任期で選出されるリーダーは最大 1 人 | | Leader Append-Only | リーダーは自ログのエントリを上書き・削除しない。追記のみ | | Log Matching | 2 つのログが同じインデックスと任期のエントリを持つなら、そのインデックスまでの全エントリが同一 | | Leader Completeness | あるエントリが任期 T でコミットされたなら、T より大きい全任期のリーダーはそのエントリを持つ | | State Machine Safety | サーバーがあるインデックスのエントリをステートマシンに適用したなら、他のサーバーは同インデックスに異なるコマンドを適用しない | ### アルゴリズム詳細 **Figure 2: Condensed Raft algorithm** ![[_attachments/atc14-paper-ongaro/fig02-raft-algorithm-summary.png]] (Figure 2. Raft 合意アルゴリズムの凝縮した要約(メンバーシップ変更・ログ圧縮を除く)。サーバー状態定義・AppendEntries RPC・RequestVote RPC・サーバールールを一覧化。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) #### サーバー状態 永続状態（全サーバー、RPC 応答前に安定ストレージへ書き込み）: - `currentTerm`: 最新の既知 term（単調増加） - `votedFor`: 現 term で投票した候補者 ID（null 可） - `log[]`: ログエントリ配列（コマンド + term） 揮発状態（全サーバー）: - `commitIndex`: コミット済みと判明した最高ログインデックス - `lastApplied`: ステートマシンに適用済みの最高インデックス 揮発状態（リーダーのみ・選挙後に再初期化）: - `nextIndex[]`: 各フォロワーへ送る次のログエントリインデックス - `matchIndex[]`: 各フォロワーで複製済みと判明した最高インデックス #### リーダー選出 1. フォロワーが `electionTimeout`（150–300 ms）の間リーダーから通信を受け取れない場合、候補者に遷移して選挙を開始する 2. 候補者は term をインクリメント、自身に投票し、全サーバーへ `RequestVote RPC` を並列送信する 3. クラスタ過半数から同一 term 内で票を得た候補者がリーダーになる 4. **スプリットボート解消**: タイムアウトをランダムに設定（固定区間内）することでサーバーを時間的にずらし、通常は単一サーバーのみがタイムアウトして選挙を勝ち取る 5. **投票制限（Election restriction）**: 候補者のログが有権者のログより「up-to-date」（最終エントリの term が新しい、または term 同一なら長い）でなければ票を与えない。これにより Leader Completeness Property を保証する #### ログ複製 1. クライアントリクエストを受けたリーダーは、コマンドをローカルログに追加し `AppendEntries RPC` を全フォロワーへ並列送信する 2. 過半数のサーバーに複製されたエントリは「コミット済み」となる。このコミットは先行するすべてのエントリもコミットする 3. `AppendEntries` は「整合性チェック」を含む: 前エントリの（インデックス, term）が一致しなければフォロワーは拒否する。これにより Log Matching Property を帰納的に保証する 4. 不整合のあるフォロワーログは、リーダーが `nextIndex` をデクリメントしながら一致点を見つけ、以降をリーダーログで上書きすることで修復する **Figure 7: Log inconsistency scenarios** ![[_attachments/atc14-paper-ongaro/fig07-log-inconsistencies.png]] (Figure 7. 新リーダー誕生時にフォロワーログが取りうる 6 種類の不整合シナリオ(a–f)。(a)(b)はエントリ不足、(c)(d)は未コミットの余分エントリ、(e)(f)は両方。リーダーは nextIndex デクリメントで一致点を特定し上書きする。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) #### 前 term のエントリのコミット制限 リーダーは**現 term のエントリのレプリカ数をカウントすることでのみコミット**する。前 term のエントリをレプリカ数カウントでコミットすることはしない（Leader Completeness Property の保証のため）。前 term のエントリは現 term のエントリがコミットされることで Log Matching Property を通じて間接的にコミットされる。 #### クラスタメンバーシップ変更 **ジョイントコンセンサス**（Cold,new）を 2 フェーズとして使用する: 1. リーダーが Cold,new 設定をログエントリとして追加・コミットする。コミット条件は Cold の過半数 AND Cnew の過半数 2. Cold,new のコミット後、Cnew エントリを追加・コミットする 3. Cnew のコミット後、新設定に含まれないサーバーはシャットダウンできる これにより設定変更中も通常クライアントリクエストを継続処理でき、同一 term 内に 2 人のリーダーが存在しえない安全性を保証する。新サーバーはまず非投票メンバーとして参加し、ログが追いついてからメンバーシップ変更を実施する（可用性ギャップの回避）。 ### タイミング要件 ``` broadcastTime ≪ electionTimeout ≪ MTBF ``` - `broadcastTime`: 0.5–20 ms（安定ストレージ技術に依存） - `electionTimeout`: 10–500 ms の範囲から選択（推奨: 150–300 ms） - `MTBF`: 数ヶ月以上（タイミング要件を容易に満たす） ## 新規性 | 問題 | Paxos | Raft の解決策 | |------|-------|---------------| | 難解な理論 | シングルデクリー分解が直感に反する | 問題分解(リーダー選出・ログ複製・安全性)と状態空間削減 | | 実装基盤の欠如 | multi-Paxos の詳細が不足 | 完全な仕様・TLA+ 形式証明・オープンソース実装 | | 分散リーダー選出コスト | リーダー選出は最適化オプションで本質外 | リーダー選出を合意の第一フェーズとして統合、機構を削減 | | 前 term エントリの term 番号変更 | 再複製時に新 term 番号を付与 | エントリは元の term 番号を維持。推論が単純化される | | メンバーシップ変更の複雑さ | Paxos の α ベースアプローチはリーダーなし前提 | ジョイントコンセンサスで追加機構最小化・通常処理継続 | ## 実験設定 - **実装**: RAMCloud コーディネータフェイルオーバー向け複製ステートマシンとして C++ で実装（約 2,000 行、テスト・コメント・空行除く） - **ユーザースタディ**: Stanford Advanced Operating Systems（CS 240）と UC Berkeley Distributed Computing（CS 294-91）の上位学部生・大学院生 43 名 - **手順**: 各学生が Raft 動画と Paxos 動画を視聴し対応クイズを受験（順序はランダム化、前半 Paxos・後半 Raft と前半 Raft・後半 Paxos に約半数ずつ割り振り） - **リーダー選出性能実験**: 5 サーバークラスタ、ブロードキャスト時間約 15 ms、1,000 回の障害試行 - **バイアス軽減**: 同一講師による動画作成、Paxos 動画は Raft 動画より 14% 長い、クイズ難度を難易別にペアリング ## 実験結果 ### 理解しやすさ - 43 名中 33 名が Raft クイズで Paxos より高得点（図 12） - 平均 Raft スコア 25.7 対 Paxos スコア 20.8（60 点満点、差 4.9 点） - 線形回帰モデルではクイズの選択だけで 12.5 点の差を予測（実際の差が小さいのは多数が Paxos の事前経験を持つため） - 41 名中 33 名が「Raft の方が実装しやすい」、41 名中 33 名が「Raft の方が説明しやすい」と回答（図 13） ### リーダー選出性能 **Figure 14: Leader election performance** ![[_attachments/atc14-paper-ongaro/fig14-leader-election-perf.png]] (Figure 14. 障害したリーダーを検知・交代するまでの時間。上グラフ: タイムアウトのランダム性量の影響（5 ms のランダム幅でも中央値 287 ms に改善）。下グラフ: 最小タイムアウトのスケーリング（12–24 ms では中央値 35 ms でリーダー選出）。Source: Adapted from [Ongaro & Ousterhout, ATC'14].) - **ランダム性の効果**: ランダム性ゼロ（150–150 ms）では選挙に 10 秒超かかる場合多数（スプリットボートの連続）。5 ms のランダム幅（150–155 ms）で中央値 287 ms に激減。50 ms のランダム幅（150–200 ms）では最悪ケース 513 ms - **タイムアウト削減の効果**: 12–24 ms のタイムアウトでは中央値 35 ms（最長 152 ms）でリーダー選出を完了する - **推奨設定**: 150–300 ms が保守的で適切。これ以上短くするとハートビート前に他のサーバーが選挙を開始する ## 考察 - **強いリーダーによる単純化**: ログエントリがリーダーからフォロワーへの一方向にのみ流れることで、複製ログの状態空間が大幅に削減される。VR（Viewstamped Replication）や ZooKeeper は選挙プロセス中にもログエントリが双方向に流れる - **ランダム化と理解しやすさ**: ランダム化タイムアウトはランダム性を「状態空間削減」として使う珍しいケース。ランキングシステム等の決定論的アプローチは新たなコーナーケースを生み続けた - **TLA+ による正式検証**: Log Completeness Property を TLA+ 証明システムで機械的証明（型安全性の不変条件は未機械検証）。非形式証明も約 3,500 語の完全版を公開 - **Paxos vs Raft のメッセージ型数**: Raft は 4 種（RequestVote/AppendEntries の要求と応答）。VR と ZooKeeper はそれぞれ 10 種類以上 ## 強み / 弱点・課題 **強み**: - 理解しやすさを設計目標にしたことで実装しやすく、25 以上の独立サードパーティ実装が論文草稿段階で既に存在 - 完全な仕様・形式証明・オープンソース実装(LogCabin)が揃っている - リーダー選出をアルゴリズムに内蔵することで Paxos より機構が少ない - クラスタメンバーシップ変更中も通常処理を継続できる **弱点・課題**: - クライアント対話（線形化可能性の保証・重複コマンド検出）とログ圧縮（スナップショット）はページ数制約のため省略（拡張版 [29] に記載） - 前 term エントリのコミット制限は追加的複雑性を持ち込む（Figure 8 のシナリオ対処） - スプリットブレインシナリオでのリーダー間の重複コマンド処理はクライアント側でのシリアル番号による重複検出が必要 ## 関連 - [[分散コンセンサス]] — Raft の核心概念。Paxos との比較・状態機械アプローチの定義 - [[複製ステートマシン]] — Raft が管理する複製ログのモデル - [[リーダー選出]] — Raft の第一サブ問題。ランダム化タイムアウトによる実装 - [[分散コンセンサス回避]] — Aurora 等がコンセンサスを回避するのは Raft/Paxos のコスト前提が背景 - [[Diego Ongaro]] — 筆頭著者 - [[John Ousterhout]] — 共著者・RAMCloud プロジェクト主導者 ## 出典 - PDF 原本: `.raw/papers/atc14-paper-ongaro.pdf` - USENIX ATC 2014 proceedings, pp. 305–319, ISBN 978-1-931971-10-2