Raft

現在最も広くデプロイされている合意形成プロトコル——etcd、Consul、TiKV、CockroachDB はすべて Raft を基盤としています。その設計目標は「最強」ではなく、「Paxos よりも理解と実装が容易であること」です。合意形成を、リーダー選出、ログレプリケーション、安全性保証という3つの直交するサブ問題に分解しています。

概要

合意形成が解決すべき課題: 障害が発生したり、メッセージの消失や順序入れ替えが発生したりする可能性のある複数のマシン間で、「一連の操作の順序」について合意に至ることです。これは分散データベース、設定センター、分散ロックの基盤となります。Paxos は理論的にこれを解決しましたが、その難解さと実装の複雑さで有名です（論文著者の Lamport 氏でさえ、後に Paxos Made Simple を補遺として執筆しました）。Diego Ongaro 氏は 2014 年の博士論文において、あえて⁠「理解可能性」⁠そのものを設計目標とし、その成果物が Raft です。

Raft の分解アプローチ: 全体のプロトコルは強力なリーダーを中心に展開されます。すべての書き込みはリーダーを経由し、ログはリーダーからフォロワーへと一方通行で流れます。これにより、合意形成は以下のように独立して理解できる3つのサブ問題に分解されます。

1. リーダー選出⁠——リーダーが故障した場合、どのように新しいリーダーを選出するか
2. ログレプリケーション⁠——リーダーがどのようにしてログを安全に過半数のノードに展開するか
3. 安全性⁠——リーダーが交代しても、すでにコミットされたデータが失われないようにどのように保証するか

ノードは3つの役割しか持たず、状態遷移は1つの図で説明できます。

flowchart LR
    F["🙋 <b>Follower</b><br><small>受動的応答 · ハートビートを待機</small>"]
    C["🗳️ <b>Candidate</b><br><small>term+1 · 全ノードに票を依頼</small>"]
    L["👑 <b>Leader</b><br><small>唯一の書き込みエントリポイント · ハートビートをブロードキャスト</small>"]
    F -->|"選挙タイムアウト:150-300ms<br>ハートビートを受信しない"| C
    C ==>|"過半数の票を獲得 ✓"| L
    C -.->|"新しいリーダーのハートビートを<br>受信し、降伏"| F
    C -.->|"票が分散<br>term+1 で再試行"| C
    L -.->|"より高い term を検知<br>即時退位"| F
    classDef follower fill:#64748b1f,stroke:#64748b,stroke-width:2px
    classDef candidate fill:#d2992226,stroke:#d29922,stroke-width:2px
    classDef leader fill:#4493f826,stroke:#4493f8,stroke-width:2.5px
    class F follower
    class C candidate
    class L leader

時間は任期（term）⁠という区切りに分けられ、term 番号は単調増加し、グローバルな論理クロックとして機能します。各 term においてリーダーは最大1人です。すべての RPC 通信において、双方はまず term を比較し、より高い term を検知すると、直ちにフォロワーに降格して自身を更新します。このルールにより、「古いリーダーがまだ自分自身をリーダーだと信じている」という脳分裂（split-brain）のケースを排除します。

主要なデータ構造

最初の3つ（currentTerm, votedFor, log[]）を永続化する理由: ノード再起動時に votedFor を忘れると、同じ term 内で2回投票してしまう可能性があり、その結果2人のリーダーが誕生する恐れがあります。また、ログを忘れると、すでに確認済みのデータが失われます。

リーダー選出プロセス

各フォロワーはランダム化された選挙タイムアウト⁠（150-300ms）を維持しています。リーダーからの AppendEntries（ハートビートとしても機能）を受信するか、投票を行うとタイマーがリセットされます。タイムアウトに達すると、リーダーが死亡したとみなし、term をインクリメントし、candidate に昇格し、自身に1票を投じ、全ノードに対して RequestVote {term, candidateId, lastLogIndex, lastLogTerm} を送信します。

RequestVote を受信したノードは、以下の3つのルールに基づいて投票するかどうかを決定します。

1. term < currentTerm → 拒否（期限切れの candidate）。
2. 現在の term ですでに他の candidate に投票済み → 拒否（votedFor は一人一票）。
3. candidate のログは、少なくとも自分自身と同じくらい新しくなければならない⁠——最後のログエントリを比較します。lastLogTerm が大きい方が新しく、term が同じ場合は lastLogIndex が大きい方が新しくなります。これを満たさない場合は拒否します。

結果は3つのいずれかになります。過半数の票を獲得すればリーダーとなり、直ちにハートビートをブロードキャストして支配権を宣言します。有効な新しいリーダーのハートビートを受信すればフォロワーに戻ります。タイムアウトで結果が出ず（票の分散）、term をさらにインクリメントして再試行します。⁠ランダムなタイムアウトは票の分散を防ぐための手段です。各ノードのタイムアウト時間が異なるため、ほぼ常に1つのノードが先に发起して選挙に勝ち、実務的には1ラウンドで選出されます。

3番目の投票ルールは安全性の半分を担っています。⁠コミットには過半数のノードの確認が必要であり、選出にも過半数の投票が必要です——2つの過半数集合には必ず共通部分があります⁠。共通部分にあるノードは、すでにコミットされたログを持っており、かつ「自分自身より古いログを持つ者」には投票しないため、当選できるリーダーは必ずすべてのコミット済みログを保持しています。そのため、Raft は Paxos のように選出後に「古い値を補完する」必要がありません。

ログレプリケーション (Log Replication)

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: 書き込みリクエスト
    L->>L: ローカルログに追加 (index=N, term=T)
    par 並列レプリケーション
        L->>F1: AppendEntries(prevLogIndex, prevLogTerm, entry)
        L->>F2: AppendEntries(...)
    end
    F1-->>L: ok (matchIndex=N)
    Note over L: 過半数が複製完了 → commitIndex = N
    L->>L: 状態マシンに適用
    L-->>C: 結果を返す
    Note over L,F2: 次の AppendEntries で新しい commitIndex を付帯し、<br>フォロワーが各自適用

AppendEntries には整合性チェックが含まれています。リーダーは各ログエントリの前に、⁠直前のログエントリの index と term（prevLogIndex/prevLogTerm）を付帯して送信します。フォロワーはこれらが一致しない場合、拒否します。リーダーが拒否を受信すると、そのフォロワーの nextIndex を1つ戻して再試行し、両者のログの最後の共通点を見つけるまで繰り返します。その後、⁠フォロワーのそれ以降のすべての内容を自前のログで上書きします。このメカニズムにより、以下の不変条件が保証されます。⁠ある index で term が同じである2つのログは、その index より前の内容が完全に一致している⁠。

コミットが安全である理由

コミットの定義: 1つのログエントリが過半数のノードによって永続化されると、コミットされたものとみなします。重要な不変条件:⁠コミット済みのログは、その後のすべてのリーダーのログに含まれている⁠。

証明の概要: エントリ E がコミットされた → 過半数の集合 S1 に E がある。新しいリーダーが選出された → 過半数の集合 S2 が投票を行った。S1 ∩ S2 は空ではない → 共通部分にあるノードは E を持っており、かつ投票を行った → 投票ルールにより、新しいリーダーのログは少なくともそれと同じくらい新しくなる → 新しいリーダーは必ず E を持っている。∎

微妙な落とし穴（論文 Figure 8）: リーダーは、すでに過半数のノードに展開されていても、⁠古い term のログを直接コミットすることはできません⁠。古い term の過半数複製は、より高い term のログによって上書きされる可能性があるためです。正しい方法は、現在の term のログのみをコミットし、古いログは間接的にコミットすることです。実装上、リーダーが就任後に自身の term の no-op エントリをコミットするのは、この問題を早期に解決するためです。

スナップショットとログ圧縮

ログが無限に増大し続けることは持続不可能です。解決策として、状態マシンの現在の状態を全体としてディスクに書き込み、それ以前のログを破棄します。

1. 状態マシンがスナップショットを生成し、lastIncludedIndex / lastIncludedTerm を記録します。
2. 特定のフォロワーが著しく遅れている場合（nextIndex ≤ lastIncludedIndex、対応するログはすでに削除済み）、リーダーは InstallSnapshot RPC を送信し、フォロワーはスナップショットを使用して自らの状態を置き換えます。
3. log[0..lastIncludedIndex] を安全に削除します。

メンバー変更: Joint Consensus

クラスタを3ノードから5ノードに拡張する場合、設定を一括で切り替えることはできません。切り替え直後、古い設定の過半数（2/3）と新しい設定の過半数（3/5）が互いに交差しない場合、⁠新旧両方でリーダーが選出され⁠、脳分裂が発生します。

Raft の解決策は、2段階の移行プロセスを用い、その間に「結合設定（Joint Configuration）」C(old, new) を挿入することです。

1. フェーズ1: リーダーが C(old, new) をブロードキャストします。その後、すべての決定（選挙を含む）には、⁠古い設定と新しい設定の両方で過半数の承認が必要です。両方の過半数が承認するため、2人のリーダーが誕生することはあり得ません。
2. フェーズ2: C(old, new) がコミットされると、リーダーが C(new) をブロードキャストし、新しい設定の過半数の承認だけでよく、移行が完了します。

リーダーが途中で故障した場合でも、新しいリーダーは C(old, new) または C(new) の下で動作するため、安全性は損なわれません。実務では、etcd はより単純な単一ノード変更を採用しています。これは1回の変更ごとに1ノードずつ追加・削除するもので、新旧の過半数集合は自然に交差するため、joint consensus を必要としません。

Raft と Paxos の違い

Paxos の原始形態と導出については Paxos を参照してください。etcd/TiKV などの本番環境システムにおける Raft 上のエンジニアリング上のトレードオフについては実システムを参照してください。なぜ合意形成で過半数派閥を避けられないのか、CAP の制約については CAP と一貫性モデル を参照してください。

参考文献

• 論文⁠: "In Search of an Understandable Consensus Algorithm" (Ongaro & Ousterhout, 2014) · Ongaro 博士論文（Figure 8 の反例と修正を含む）
• 可視化⁠: raft.github.io（インタラクティブアニメーション、非常に優れている） · thesecretlivesofdata.com/raft
• 実装⁠: etcd/raft (Go, 本番レベル) · hashicorp/raft (Go) · tikv/raft-rs (Rust)

Keywords: Raft, 合意形成プロトコル, leader election, リーダー選出, log replication, ログレプリケーション, term, 任期, split vote, 脳分裂, joint consensus, メンバー変更, snapshot, InstallSnapshot, etcd, TiKV, quorum, 過半数派閥