✍️ 필사 모드: Raft Consensus 完全ガイド 2025: Leader Election、Log Replication、Safety、etcd/Consul 実戦分析

はじめに: なぜ Raft か

分散合意の根本問題

5 台のサーバーが独立に「現在の残高は?」に答える。ネットワーク分断、サーバー故障、遅い応答、一部リクエストのみが届くなどの状況下でも、すべてのサーバーが同じ状態 を維持しなければならない。これが 分散合意 (Distributed Consensus) 問題である。

Paxos とその苦痛

1989 年に Leslie Lamport が Paxos を発表した。数学的には完璧だったが理解が困難で、Google の Chubby 論文はこう述べている:

"There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system."

実装者はそれぞれの亜種を作り、どれも完全には検証されなかった。

Raft の登場

2014 年 Stanford の Diego Ongaro と John Ousterhout が発表した Raft は唯一の目標で設計された:

「理解可能性 (Understandability) を最優先する」

Raft は Paxos と同じ安全性を提供しつつ、問題を 3 つの独立した小問題に分解する:

1. Leader Election
2. Log Replication
3. Safety

この分解のおかげで Raft は急速に普及した: etcd (Kubernetes バックエンド)、Consul、CockroachDB、TiDB、YugabyteDB、MongoDB、RedPanda、Kafka KRaft。Kubernetes を使っていれば、毎日 Raft に依存している。

1. Raft の基本モデル

ノード状態 (State)

各ノードはちょうど 1 つの状態にある:

Follower  ──timeout──▶  Candidate  ──majority──▶  Leader
   ▲                        │                        │
   └──higher term / leader detected──────────────────┘

• Follower: 受動的。Leader からログを複製。
• Candidate: 選挙中。
• Leader: 唯一の書き込みエントリポイント。ログを追加し複製する。

通常運用では常に 1 Leader + N-1 Followers。

Term: 論理的時間

Term は単調増加の整数。各 Term は選挙フェーズで始まり、通常運用フェーズに続く。高い Term を受けたノードは即座に step down する。

2 つの RPC

Raft は 2 つの RPC のみ使う:

1. RequestVote RPC: Candidate が投票を要求。
2. AppendEntries RPC: Leader がログ複製と heartbeat を送る。

2. Leader Election

選挙タイムアウト

各 Follower はランダム election timeout (通常 150〜300ms) を持つ。タイムアウトすると:

1. Candidate に遷移。
2. currentTerm を +1。
3. 自分に投票。
4. 全 peer に RequestVote RPC を送信。
5. election timer をリセット。

投票条件

RequestVote を受けたノードは以下をすべて満たせば賛成票を投じる:

1. 要求者の term >= currentTerm。
2. この Term でまだ誰にも投票していない (または同じ候補)。
3. 要求者のログが自分と同等以上に up-to-date。

up-to-date チェック: 最後のエントリの Term が大きい方が新しい。同 Term なら index が大きい方が新しい。このルールが Leader Completeness を保証する。

選挙結果 3 種

1. 過半数獲得 → Leader になり、即座に heartbeat 送信。
2. 他の Leader を発見 (同等以上の Term) → Follower に戻る。
3. Split vote / timeout → Term を増やし再挑戦。

Split Vote の回避

各ノードが [150ms, 300ms] のランダムな timeout を持つことで、通常は 1 ノードが先にタイムアウトし単独の Candidate になる。split vote は数学的に稀で、次 Term で解消する。

疑似コード

class RaftNode:
    def start_election(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.id
        self.votes_received = {self.id}
        self.reset_election_timer()
        for peer in self.peers:
            self.send_request_vote(peer)

    def handle_vote_response(self, response):
        if response.term > self.current_term:
            self.become_follower(response.term)
            return
        if response.vote_granted:
            self.votes_received.add(response.voter_id)
            if len(self.votes_received) > len(self.peers) // 2:
                self.become_leader()

    def become_leader(self):
        self.state = "leader"
        self.reset_heartbeat_timer()
        self.send_heartbeats()

3. Log Replication

ログエントリ構造

index:    1     2     3     4     5     6
term:     1     1     1     2     3     3
cmd:    [x=3] [y=1] [x=2] [z=0] [x=9] [y=5]

各エントリは index、term、command を持つ。

複製フロー

1. クライアント要求 → Leader のログに append (uncommitted)。
2. Leader が AppendEntries を Follower に並列送信。
3. 過半数 が成功で commit。
4. Leader が state machine に適用しクライアントに応答。
5. 次の AppendEntries で commitIndex を伝播 → Follower も適用。

AppendEntries RPC

AppendEntries(
    term,
    leaderId,
    prevLogIndex,
    prevLogTerm,
    entries[],
    leaderCommit
)

Follower は prevLogIndex の term が prevLogTerm と一致すれば success を返す。

Log Matching Property

1. 2 つのログに同じ index/term のエントリがあれば、command は同一。
2. 2 つのログに同じ index/term のエントリがあれば、それ以前のすべてのエントリも同一。

AppendEntries の一貫性チェックにより強制される。

不一致の解消

Leader は各 Follower に nextIndex を管理し、AppendEntries が失敗すれば nextIndex を -1 して再試行。一致点を見つけたら Follower の以降のログを Leader のもので上書き。

def send_append_entries(self, follower_id):
    next_idx = self.next_index[follower_id]
    prev_idx = next_idx - 1
    prev_term = self.log[prev_idx].term if prev_idx > 0 else 0
    entries = self.log[next_idx:]
    response = self.rpc(follower_id, "AppendEntries", {
        "term": self.current_term,
        "prev_log_index": prev_idx,
        "prev_log_term": prev_term,
        "entries": entries,
        "leader_commit": self.commit_index,
    })
    if response.success:
        self.next_index[follower_id] = next_idx + len(entries)
        self.match_index[follower_id] = self.next_index[follower_id] - 1
        self.maybe_advance_commit()
    else:
        if response.term > self.current_term:
            self.become_follower(response.term)
        else:
            self.next_index[follower_id] -= 1

4. Safety プロパティ

1. Election Safety

「各 Term で最大 1 人の Leader」。ノードは Term 当たり 1 票のみ、2 つの過半数は同時に存在しない。

2. Leader Append-Only

「Leader はログを上書き/削除せず、追加のみ」。

3. Log Matching

同じ index/term のエントリがあれば、それまでの全エントリが一致する。

4. Leader Completeness

「ある Term で commit されたエントリは、それ以降のすべての Leader に存在する」。RequestVote の up-to-date チェックで保証される: commit 済みは過半数に存在するため、勝者はその過半数以上に up-to-date でなければならず、必ずそのエントリを持つ。

5. State Machine Safety

ある index のエントリを適用したら、他のノードは同 index に別のエントリを適用できない。1〜4 から導出される。

微妙なバグ: 前 Term のエントリ commit

Raft 論文の Figure 8 は有名なコーナーケース: 前 Term のエントリが過半数に複製されても、それだけで commit すると後で上書きされ得る。

解決: Leader は自 Term のエントリのみを commit count 対象にする。現 Term のエントリが commit されれば、副次的に前エントリも Log Matching により commit される。

def maybe_advance_commit(self):
    for n in range(self.commit_index + 1, len(self.log) + 1):
        if self.log[n].term != self.current_term:
            continue
        count = 1
        for peer in self.peers:
            if self.match_index[peer] >= n:
                count += 1
        if count > len(self.peers) // 2:
            self.commit_index = n

5. Cluster Membership Change

素朴な変更の危険性

3 ノード → 5 ノードの切り替えを全ノード同時には適用できない。C_old の過半数と C_new の過半数が重ならなければ、2 人の Leader が同時存在 する。

解決 1: Joint Consensus

Leader が C_old,new (和集合) を log に追加。遷移中の決定は C_old の過半数 AND C_new の過半数 両方を要求。commit 後 C_new を追加。

解決 2: Single Server Change (etcd 方式)

1 回に 1 ノードのみ 追加/削除。過半数は必ず重なる (3 ノードの過半数 2 と 4 ノードの過半数 3 は最低 1 ノード共有)。etcd はこれを採用。

6. Log Compaction (Snapshot)

ログは無限に増やせない。各ノードは独立に snapshot を作る:

Snapshot {
    last_included_index: 5,
    last_included_term:  2,
    state_machine_state: {...}
}

last_included_index 以前は削除。

InstallSnapshot RPC

Follower が遅れすぎて Leader が必要なログを既に捨てていれば、Leader は全 snapshot を送る:

InstallSnapshot(
    term,
    leaderId,
    lastIncludedIndex,
    lastIncludedTerm,
    offset,
    data[],
    done
)

etcd は既定で 10000 エントリごとに snapshot (--snapshot-count)。

7. クライアント相互作用

Linearizable Read

stale な Leader が存在し得る (ネットワーク分離で別 Leader が選出済)。解決策:

1. Read through Log: 読み取りも log にして commit 後応答。安全だが遅い。
2. ReadIndex: 現 commitIndex を記録し heartbeat で Leader 継続を確認してから応答。etcd の既定。
3. Lease Read: 一定期間 Leader を保証。高速、時計同期が必要。

重複要求の防止 (Exactly-Once)

各クライアントに (client_id, sequence_no) を付与し、Leader が state machine に保存。処理済みなら過去結果を返す。

8. 実戦システム分析

etcd

• Go 製 go.etcd.io/raft ライブラリ。Kubernetes の全状態を保存。
• MVCC KV ストア、Watch API、Lease、ポート 2379/2380。
• 3 ノードで書き込み ~10,000 ops/s (fsync 律速)、linearizable read ~40,000 ops/s。
• 推奨クラスタサイズ: 3 または 5。

Consul

HashiCorp の Consul: Raft ベース consistent KV、マルチ DC (各 DC が独自 Raft クラスタ)、DNS サービスディスカバリ。

CockroachDB / TiDB / YugabyteDB

NewSQL はデータを range/region に分割し、それぞれに Raft グループを持つ (Multi-Raft):

• CockroachDB: 64MB range。
• TiKV: 96MB region。
• 最適化: メッセージバッチング、Follower Replication、region merge/split。

MongoDB & Kafka KRaft

MongoDB replica set は "Raft-like" プロトコル。Kafka 2.8+ の KRaft モードは ZooKeeper の代わりに Raft ベース controller quorum でメタデータを管理。

9. パフォーマンス最適化

1. Pipeline AppendEntries — ack を待たずに次を送る。
2. Batching — fsync コストを分担。
3. Parallel Disk Write — log append と follower send を並列化。
4. PreVote — 分断復帰ノードによる不要な Term 増加を防ぐ。
5. Follower Read — stale read を許容するなら Follower が直接応答。
6. Witness Replicas — 投票のみの軽量 replica (CockroachDB)。

10. 運用上よくある問題

Election Storm

症状: Leader が頻繁に交代、スループット ~0。原因: ネットワーク遅延 > election timeout、GC pause、disk I/O ブロック。対策: election-timeout を増やす (etcd 既定 1000ms → 5000ms)、heartbeat-interval を縮める、PreVote 有効化。

ログ無限増加

--snapshot-count を確認、Follower 遅延をモニタ、遅れた Follower を再起動して InstallSnapshot を誘発。

Quorum Loss

3 ノードで 2 ノード故障 → 残り 1 ノードは過半数を形成できず読み取りすら不可。復旧: 残存ノードを単一ノードクラスタとして強制復元 (etcdctl snapshot restore)、新ノードを 1 つずつ追加。予防: 奇数ノード、AZ 分散。

遅いディスク

Raft は write 毎に fsync する:

• HDD: ~10ms → 最大 100 ops/s
• SSD: ~0.1ms → 最大 10,000 ops/s
• NVMe: ~0.01ms → 最大 100,000 ops/s

Raft ノードを 絶対に HDD 上に置かない。

ネットワーク分断

過半数要求で split brain を防ぐ。少数側は読み書き失敗 — Raft は CP システム。

11. Raft vs Paxos vs Zab

Raft 人気の理由

1. 論文に擬似コードと実装ガイド。
2. 状態モデルが明確。
3. 豊富な OSS 実装。
4. 教育向き。

Google 内部は依然 Paxos 優勢だが、外部 OSS では Raft が圧倒的。

12. 自分で実装してみる

学習資料

1. 原論文 "In Search of an Understandable Consensus Algorithm"。
2. raft.github.io インタラクティブ可視化。
3. MIT 6.824 Lab 2 (2A: Election、2B: Replication、2C: Persistence、2D: Snapshot) を Go で実装。

よくあるミス

1. Heartbeat にログを piggyback し忘れ。
2. RPC での term 比較漏れ。
3. 前 Term エントリの commit 判定ミス。
4. persistence 漏れ (currentTerm、votedFor、log は fsync 必須)。
5. timer reset の位置ミス。

クイズで復習

おわりに

Raft は単なるアルゴリズムではなく 研究哲学 である: 「既存が難しいなら、理解可能な新アルゴリズムを作ろう」。

核心アイデア

1. Leader ベース consensus。
2. Term ベースの論理時間。
3. Election Safety を過半数投票で保証。
4. Log Matching を一貫性チェックで保証。
5. Leader Completeness を up-to-date チェックで保証。

kubectl apply → etcd、Consul KV、CockroachDB、Kafka KRaft — 我々は毎日 Raft に依存している。Raft を理解すればこれらの挙動、障害、性能特性が透明になる。

次のステップ

EPaxos、Flexible Paxos、HotStuff、Byzantine Raft。ただしまず自分で Raft を実装しよう。

参考資料

• In Search of an Understandable Consensus Algorithm (2014)
• raft.github.io
• TLA+ Spec
• etcd Raft Library
• MIT 6.824
• Ongaro 博士論文