Raft — 分散合意
複数ノードが同じログを同じ順序で持ち続けるためのアルゴリズムを作る。書き込みを受け付けるのは 1 人のリーダーだけにして、合意をリーダーのログを配る問題に単純化する。あるエントリは過半数のノードに複製できた位置までを確定とみなし、確定したものは二度と消えない。リーダーになれるのは自分以上に新しいログを持つ者だけで、古いログの持ち主を選ばない安全性になる。リーダーが落ちても選挙で次が立つ。
この章で作るもの
分散はなぜ難しいかの章で見た「部分故障」「split brain」「過半数」を、実際に動く合意アルゴリズムにする。題材は Raft。分散合意で最も読みやすい設計とされ、etcd・Consul・TiKV などが採用している。
順に見ていく。
- 強いリーダー: 書き込みを受け付けるのは常に1人のリーダーだけ。ログはリーダーから追従者へ一方向に流れる。交通整理を1点に集めることで、合意を「リーダーのログを配る」問題に単純化する
- 過半数で確定(commit): あるエントリが過半数のノードに複製できたら「確定」。確定したものは二度と消えない
- 選挙の安全性: リーダーになれるのは、自分以上に新しいログを持つ者だけ。これで確定済みエントリが新リーダーに必ず引き継がれる
設計: 純粋状態機械
実装に入る前に、この実装の設計の勘所を1つ。ノードを「純粋状態機械」として書く。ノードは入口 Step(メッセージ) と時計 Tick() の2つだけで動き、内部で時刻を読んだり通信したりしない。時間の経過すら外から Tick() で刻む。
入力 純粋ロジック 出力
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Step(msg) │─────────▶│ Raft の状態 │─────────▶│ 送るメッセージ │
│ Tick() │ 駆動 │ term/log/... │ 結果 │ 適用するエントリ│
└──────────┘ └──────────────┘ └──────────────┘
▲ 時計も通信も │
│ 内部に持たない ▼
ドライバ(cluster.go / 実ネットワーク)が時計・配送・永続化を担当なぜこうするか。合意アルゴリズムのバグは「特定のタイミングでメッセージが交錯したときだけ」出ることが多い。実時間の sleep やゴルーチンに頼ると、そのタイミングを再現できずデバッグできない。ロジックを時間から切り離せば、選挙の競合も分断も1プロセス・決定的に再現できる(etcd/raft が採る設計)。テストのシミュレータ cluster.go は、この Step/Tick を叩いてメッセージを配送するだけの薄い層になる。
リーダー選出
まず「1人のリーダーを選ぶ」ところから。各ノードは常に3つの役割のどれか、すなわち Follower(追従者)・Candidate(候補者)・Leader(指導者)のいずれかになる。そして任期(term) という単調増加の論理時刻を持つ。任期は「第何代のリーダーの治世か」を表す番号で、全メッセージに乗る。
選挙タイムアウト 過半数の票
┌────────┐ (音沙汰なし) ┌─────────┐ 獲得 ┌────────┐
│Follower │───────────────▶│Candidate │──────▶│ Leader │
└────────┘ └─────────┘ └────────┘
▲ より高い任期を見た / 心拍を受けた │ │ 心拍を送り続ける
└──────────────────────────────────┘ │ (自分の治世を主張)
▲ │
└──────── より高い任期のリーダーが現れたら降格 ┘投票には安全性の核がある。票を投じる条件は「(a) その任期でまだ誰にも入れていない」かつ「(b) 候補者のログが自分と同じか新しい」。この (b) が「古いログの持ち主をリーダーにしない」を保証し、確定済みのエントリが選挙で消えるのを防ぐ。
func (r *Raft) logUpToDate(index, term uint64) bool {
myTerm := r.log.lastTerm()
return term > myTerm || (term == myTerm && index >= r.log.lastIndex())
}任期が優先で、同じ任期なら長い方が新しい。たった2行だが、これが Raft の安全性を支える1本の柱になっている。
選挙タイムアウトを散らす理由
全員が同時に立候補すると票が割れて誰も過半数を取れない(split vote)。Raft はこれを、選挙タイムアウトをノードごとにランダムに散らすことで避ける。基準値の1〜2倍の範囲でばらつかせると、たいてい誰か1人が先にタイムアウトして、他が追随する前に票を集めきれる。豪華な仕組みではなく「時間をずらすだけ」で解決するのが Raft の設計の妙。
PreVote: 割り込みを防ぐ
素朴な選挙には穴がある。分断から戻ってきたノードや、構成変更で外されたノードは、心拍が来ないので延々とタイムアウトし、任期をどんどん吊り上げながら選挙を仕掛ける。その高い任期を見た正当なリーダーは、ルール上いったん降格せざるを得ず、クラスタが無用に乱される。
対策が PreVote(仮投票)。立候補する前に、任期を上げずに「もし立候補したら勝てそうか?」だけを先に問う。過半数の感触が得られて初めて、本番の任期を上げて立候補する。あわせてリーダーリース、すなわち「現リーダーから最近声を聞いている間は、割り込みの投票要求を無視する」ルールを入れると、外されたノードの高任期は誰にも相手にされず、任期が上がらない。デモの「孤立ノードを放置しても既存リーダーが乱れない」挙動はこれで実現している。
動かす
下は5ノードの Raft クラスタ。起動すると誰かが立候補してリーダー(緑)になり、心拍で治世を維持する。「書き込みを追加」でエントリが積まれ、リーダーから各ノードへ複製されていく様子(セルが埋まる → 過半数に届くと緑=確定)が見える。
起動中。しばらくすると誰かがリーダーに立候補する
ログ複製
リーダーが決まったら、書き込みをログとして全ノードに配る。リーダーは各追従者に AppendEntries(心拍も兼ねる)を送る。ここに整合性の仕掛けがある。エントリを送るとき、その直前の位置 (prevIndex, prevTerm) を一緒に送り、追従者はそこが自分のログと一致して初めて受け取る。
リーダー: [1:a][1:b][2:c][2:d] 送信: prev=(位置2,任期1) + [2:c][2:d]
追従者A : [1:a][1:b][2:c] 位置2は任期1で一致 → 受理。末尾に 2:d
追従者B : [1:a][1:b][1:x] 位置2は任期1で一致だが位置3(1:x)が違う
→ 2:c で上書き、以降を貼り直す
追従者C : [1:a] 位置2が無い → 拒否。リーダーは prev を1つ戻して再送この「一致するまで遡って、そこから上書き」の繰り返しで、どれだけ食い違った追従者のログも最終的にリーダーと一致する。リーダーのログが唯一の正で、追従者は自分の食い違う部分を捨ててそれに合わせる。
コード読みどころ: どこまでを「確定」とするか
複製しただけでは確定ではない。リーダーは過半数のノードに複製できた位置までを commit(確定)とする。各追従者がどこまで複製できたか(match)を集め、降順に並べて過半数番目を取れば、それが「過半数が到達している最大位置」。
func (r *Raft) maybeCommit() bool {
// 全メンバの複製済み位置を集める(自分は末尾まで持っている)
matches := make([]uint64, 0, len(r.peers))
for id := range r.peers {
if id == r.id {
matches = append(matches, r.log.lastIndex())
} else if pr := r.prog[id]; pr != nil {
matches = append(matches, pr.match)
} else {
matches = append(matches, 0)
}
}
// 降順に並べ、過半数番目の値 = 「過半数が到達している最大位置」
sort.Slice(matches, func(i, j int) bool { return matches[i] > matches[j] })
mci := matches[r.quorum()-1]
if mci <= r.log.committed {
return false
}
if t, ok := r.log.term(mci); !ok || t != r.term {
return false // 現任期のエントリでなければ確定しない(図8対策)
}
r.log.commitTo(mci)
return true
}読みどころは最後の t != r.term の一行。過半数に複製されても、それが『前の任期』のエントリなら確定させない。 これは Raft 論文の図8が示す落とし穴への対策。
時点1: L1 が位置2(任期2)を node1,2 に複製(2/3=過半数)…でもまだ確定させない
時点2: L1 が落ち、node3 が任期3でリーダーに。node3 は位置2を持たない
→ もし時点1で確定扱いにしていたら、確定済みが消える事故になる
Raft のルール: 現任期(任期3)のエントリを1つ commit できたら、
それに連なる過去の位置も一緒に確定 → 二度と覆らない「複製された数」だけを見ると覆りうる。「現任期のエントリが1つでも確定に達したら、その手前も芋づるで確定」とすることで、確定は不可逆になる。ここは Raft のいちばん微妙で、いちばん大事な部分。
分断と split brain
分散はなぜ難しいかの章で「素朴な設計は分断で split brain を起こす」と言った。Raft では起きない。デモの**「ネットワークを分断」**を押すと、現リーダーを含む少数派(2台)と多数派(3台)に割れる。
- 少数派のリーダー: 書き込みを受け付けても、複製できるのは自分含め2台。過半数(3)に届かないので commit が進まない(セルが緑にならない)。宙に浮いたまま
- 多数派: リーダーからの心拍が途絶えて選挙が起き、新しいリーダーが立つ。3台あるので書き込みを確定できる
┌ 少数派 2台 ┐ ✂ ┌──── 多数派 3台 ────┐
│ 旧L F │ │ 新L F F │
│ 書込→2台止まり│ │ 書込→3台で確定 ○ │
│ commit 進まず✕│ │ 治世が正になる │
└────────────┘ └─────────────────┘
復旧 → 旧L は新Lの高い任期を見て降格。少数派は多数派のログに上書きされる**「分断を復旧」**を押すと、少数派の旧リーダーは多数派の新リーダー(より高い任期)を見て追従者に降格し、宙に浮いていた書き込みは捨てられて、全ノードのログが多数派のものに揃う。過半数ルールひとつで、2人のリーダーがいてもデータは食い違わない。これが分散はなぜ難しいかの章で予告した「過半数が効く」の実物。
遅れすぎた追従者: スナップショット
ログは書き込みのたびに伸び続ける。放っておくとメモリもディスクも食い潰すので、適用済みの前半を1枚の「状態の写し(スナップショット)」に畳んで捨てる(ログ圧縮)。
問題は、長く落ちていた追従者が復帰したとき。必要な過去のエントリが既に圧縮で消えていると、通常の AppendEntries では追いつかせられない。そこでリーダーは、エントリの代わりにスナップショットそのものを送る(InstallSnapshot)。追従者はそれを丸ごと受け取って一気に追いつく。実装では、送りたい起点が圧縮済みだったら自動で写し送信に切り替える。
メンバの入れ替え
運用ではノードを足したり外したりしたい。危険なのは、構成を「一気に」切り替えると、切り替えの途中で古い構成と新しい構成が別々に過半数を作ってしまう瞬間が生まれること(=split brain)。
この実装は単一サーバ変更方式を採る。「1回に1台だけ」足す/外す。1台の増減では、古い過半数と新しい過半数が必ず重なるので、2つの多数派が同時に立つ瞬間が生まれない。構成変更自体も1つのログエントリとしてログに流し、他の書き込みと同じ仕組みで全ノードに伝える。原論文の joint consensus(2構成の重ね合わせ)より実装が単純で、学位論文でも推奨されている方式。
設計の観点: キャパシティ見積もり
Raft を「本番規模で使うと何が上限か」を見積もる練習。キャパシティ見積もりの各論は capacity-estimation 編で扱う。
- 書き込みは全部リーダー経由。だから 1クラスタの書き込みスループットはリーダー1台の上限で頭打ち。読みは追従者に散らせても、書きはスケールしない。「書き込み1万QPSが要る」なら1つの Raft クラスタでは足りず、データを分割(シャーディング)して複数の Raft クラスタに分ける(→ consistent hashing の出番)
- 1回の commit の遅延 ≒ リーダー→過半数の追従者の往復(RTT)+ ディスク fsync。地理分散だと RTT が効くので、5台を別リージョンに置くと commit が遅くなる。「低レイテンシが要るなら近くに、耐障害性が要るなら遠くに」のトレードオフ
- 台数の選び方: 2f+1 台で f 台の故障に耐える。5台なら2台まで。増やすほど耐障害性は上がるが、過半数が増える分 commit に必要な応答数も増えて遅くなる。多くの本番は3台か5台に落ち着く(7台以上は遅延が見合わないことが多い)
- ログの肥大: 書き込みQPS × エントリサイズ × スナップショット間隔 が、各ノードのログ用ディスクの見積もり。1KB×1万QPS×60秒 ≒ 600MB/分、なのでスナップショットは頻繁に要る
メリット・デメリットと実例
Raft(強いリーダー型の合意)の性格を中立に。評価軸は「何を優先するか」。一貫性(食い違わないこと)か、書き込みスケールか、レイテンシか。
メリット
- 強い一貫性: 確定したものは全ノードで同一・不可逆。「読んだ値が古い/食い違う」が起きない。設定・メタデータ・ロックなど「絶対に食い違ってはいけないもの」に向く
- 分断に安全: 過半数を割った側は止まる(=間違ったことをしない)。応答し続けること(可用性)を犠牲にして、食い違わないこと(一貫性)を守る
- 理解しやすい: リーダー1点集中で、ログを配るだけ。Paxos より読みやすく実装しやすい
デメリット
- 書き込みがスケールしない: 全書き込みがリーダー1台を通る。台数を増やしても書き込み性能は上がらない(むしろ commit が遅くなる)
- 分断で少数派が止まる: 過半数を失うと、生きている少数派は読み書きできない。可用性が要る用途には不向き
- レイテンシは往復に縛られる: 1書き込みごとに過半数との往復が要る。地理分散では特に効く
実例(裏の取れるもの)
- etcd(CNCF): Kubernetes の全状態を保持する台帳。Raft をそのまま採用。「食い違ってはいけない少量のメタデータ」の典型で、Raft の強みが活きる用途
- TiKV / TiDB(PingCAP): データを範囲(Region)に分割し、Region ごとに独立した Raft グループを走らせることで、単一リーダーの書き込み上限を超えてスケールさせている。上の「設計の観点」で触れたシャーディングの実例
- CockroachDB: 同様にデータ範囲ごとに Raft。地理分散DBで一貫性を保つ
- Consul(HashiCorp): サービスディスカバリと KV ストアの合意層に Raft
一貫性が要らない/可用性最優先の用途では、Raft のような合意を使わず、結果整合(eventual consistency) を選ぶ設計もある(Dynamo 系、Cassandra 等)。「常に食い違わない」と「常に応答する」は、分断している間は原理的に両立できない。この二者択一は CAP 定理という名前で知られている。
裏どり:
- 理解しやすさが設計目標だった: 原論文の題は "In Search of an Understandable Consensus Algorithm"。Paxos と同じ保証を、リーダー選出・ログ複製・安全性の3つに分けて説明できる形にしたこと自体が貢献になっている。アルゴリズムの評価軸に「教えられるか」を置いたのが珍しい
- 選挙タイムアウトはわざとばらす: 全員が同時に立候補すると票が割れて決まらない。だから各ノードが範囲内のランダムな時間だけ待つ。論文の目安は 150〜300ms になる。衝突を確率でほどくという発想は、リトライとバックオフのジッタと同じものになる
- PreVote という補強: 分断された側のノードが立候補を繰り返して term を上げ続けると、復帰したときに正常なリーダーを引きずり下ろしてしまう。立候補する前に「勝てるか」を聞く手順を足すのが対策で、実装では標準的に入っている
- 読みにも合意が要る: リーダーを名乗っていても、既に降ろされている可能性がある。だから古い値を返さない読みには、過半数に自分がまだリーダーかを確認する手順(ReadIndex)か、期限付きのリースが要る。書きだけ守れば済む話ではない
- メンバ変更は1台ずつ: 一度に複数台を入れ替えると、新旧の構成で過半数が重ならなくなり、2人のリーダーが同時に成立しうる。Raft が1台ずつの変更を勧めるのは、重なりを必ず作るためになる
簡略化したこと
- ログの永続化なし: term/vote/log はメモリのみ。実物はディスクに fsync してから応答する。クラッシュ復帰は扱わない(WAL と接続すればここが埋まる)
- メンバ変更は単一サーバ方式のみ: joint consensus は実装しない
- クライアントの重複排除なし: at-least-once。同じ書き込みが2回適用されうる(実物はセッション+シーケンス番号で冪等化)
- 読み取り最適化(ReadIndex / リース読み)なし: 書き込みの合意に集中
実装は distributed/raft/(93%テストカバレッジ、-race 検証済み)。go test ./distributed/raft/ -race で選挙・複製・分断・スナップショット・メンバ変更のテストが動く。
参考資料
- In Search of an Understandable Consensus Algorithm (Raft) — 原論文。図2(全ルールの一覧)と図8(前任期エントリの落とし穴)は必読
- Raft 可視化 — 選挙と複製を動かして見られる公式ビジュアライザ
- Consensus: Bridging Theory and Practice (Ongaro 学位論文) — PreVote・単一サーバ変更・スナップショットの詳細
- etcd/raft — この章の「純粋状態機械」設計の実物。本番品質の Raft ライブラリ