---
title: Raft
url: https://doc.liz6.com/ja/distributed-systems/02-consensus-protocols/01-Raft
locale: ja
area: distributed-systems
tags:
- distributed-systems
- consensus-protocols
date: 2026-06-30
modified: 2026-07-16
description: 'Raftプロトコルの詳細解説: リーダー選出プロセス、ログレプリケーション、コミットの安全性証明、スナップショットとメンバー変更(Joint Consensus)。現在最も広くデプロイされている合意形成プロトコルであり、etcd、Consul、TiKV、CockroachDB すべてがこれを基盤としています。設計目標は Paxos よりも理解と実装が容易であることです。'
---

# Raft

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

## 概要

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

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

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

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

```mermaid
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）のケースを排除します。

## 主要なデータ構造

| 状態 | フィールド | 意味 |
|---|---|---|
| 永続化 (すべての RPC 応答前にディスクに書き込み) | `currentTerm` | このノードが確認した最新の term |
| | `votedFor` | 現在の term で誰に票を投じたか |
| | `log[]` | ログ。各エントリは `{term, index, command}` の形式 |
| 揮発性 | `commitIndex` | すでにコミットされた最後の index |
| | `lastApplied` | 状態マシンに適用された最後の index |
| リーダーのみ (メモリ上) | `nextIndex[]` | 各フォロワーに送信する次の index |
| | `matchIndex[]` | 各フォロワーが複製を完了した index |

最初の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)

```mermaid
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 の違い

| | Raft | Multi-Paxos |
|---|---|---|
| リーダー選出 | 独立したサブ問題。ランダムタイムアウトによって駆動 | レプリケーションと結合されている |
| ログ | 連続した index。ギャップは許可されない | 任意の index。ギャップを許可 |
| コミット済み値の取得 | 当選時に取得済み（投票ルールにより保証） | 選出後に古い値を補完する必要あり |
| メンバー変更 | joint consensus / 単一ノード変更 | 通常は外部メカニズムに依存 |
| 理解可能性 | 明確に3つのサブ問題に分解 | すべて結合されており、全体として理解する必要がある |

Paxos の原始形態と導出については [Paxos](/distributed-systems/02-consensus-protocols/02-Paxos.md) を参照してください。etcd/TiKV などの本番環境システムにおける Raft 上のエンジニアリング上のトレードオフについては[実システム](/distributed-systems/02-consensus-protocols/03-consensus-in-practice.md)を参照してください。なぜ合意形成で過半数派閥を避けられないのか、CAP の制約については [CAP と一貫性モデル](/distributed-systems/01-basic-theory/01-cap-and-consistency-models.md) を参照してください。

## 参考文献

- **論文**: "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, 過半数派閥*