Mímisbrunnr知恵の泉

← 分散システム 一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：Paxos　|　関連：リーダー選出（Bully・Ring）・レプリケーション方式（同期／非同期・リーダー／リーダーレス）

要点（BLUF）

問題設定 ── 強一貫を作る実装可能な合意

線形化可能性と逐次一貫性 の強一貫を、クラッシュ故障下で作りたい。Paxos（Paxos）は正しいが難解。Raftは「まず1人のリーダーを選び、その人がログを配る」という直観的な構造で同じ保証を与えます。

アルゴリズム ── 3つの部分

1. リーダー選出

各ノードは follower / candidate / leader の状態を持ちます。

flowchart LR
    F["follower"] -->|"選挙タイムアウト（リーダーの心拍が途絶える）"| C["candidate"]
    C -->|"過半数の票を獲得"| L["leader"]
    C -->|"他のリーダーを発見/票が割れて再選挙"| F
    L -->|"より新しいタームを発見"| F

follower はリーダーの心拍（heartbeat）が一定時間来ないと candidate になり、term+1 して自分に投票し、RequestVote を全員に送る。過半数を得たら leader。選挙タイムアウトをランダム化して同時立候補（票割れ）を起きにくくします。

2. ログ複製

leader はクライアント要求をログに追記し、AppendEntries で follower に複製。過半数に複製された時点でコミット（その状態機械に適用）。これが状態機械レプリケーション（SMR）です。

3. 安全性（選出制限）

ログが古い candidate には投票しない（RequestVote に最新ログ情報を載せ、受け手は自分より古ければ拒否）。これで「コミット済みエントリを持つノードだけがリーダーになれる」を保証し、確定したログが失われません。

具体例 ── タームと過半数で1人に収束（実機）

ラボ 05-04_raft_election.py。5ノード、ランダム選挙タイムアウトで先頭の1台が候補者になり過半数を集める：

== Raft リーダー選出 (N=5, 過半数=3) ==
選挙タイムアウト(ms): {0: 210, 1: 289, 2: 183, 3: 244, 4: 271}
最初に候補者になるノード: 2
ターム: 1  候補者: 2
投票したノード: [0, 1, 2]  得票: 3
リーダー確定: 2  (過半数 3 を満たす: True)
安全性: 各ノードはターム1で1票のみ -> 同一タームに2人のリーダーは生じない

タイムアウトが最短のノード2が先に候補者になり、自分＋2票で過半数3に到達してターム1のリーダーに確定。各ノードは1タームに1票だけなので、別のノードが同じタームで過半数を取ることはありえません（安全性）。

正しさの観点 ── 安全性と活性

他手法との比較

観点PaxosRaftリーダー選出（Bully・Ring）
安全性原理過半数の重なり過半数の重なり最大IDが勝つ（合意は別途）
リーダー暗黙明示・心拍維持明示・選出のみ
ログ複製別途統合含まない

なぜ分散だと難しいか（直観）

「リーダーを1人に」は簡単そうで、ネットワーク分断で両側が別々にリーダーを立てる（スプリットブレイン）危険がある。Raftは「過半数の票が無ければリーダーになれない」とすることで、分断の少数派側は決してリーダーになれず、二重リーダーを構造的に封じます。少数派は書き込み不能になる（CP、CAP定理）のが代償です。

⚠️ よくある誤解・落とし穴

対応ラボ

distributed-systems-study/labs/05-04_raft_election.py（ターム1で候補者が過半数3票を集め単一リーダーに収束、1ターム1票で二重リーダー不可を確認済み）。

関連

← 第5章 合意 目次