分散式一致性演算法 Raft 完整解析：領導者選舉、日誌複制、成員變更與快照

分散式一致性演算法 Raft 完整解析：領導者選舉、日誌複制、成員變更與快照

Raft 將一致性問題分解為三個相對獨立的子問題：**領導者選舉**、**日誌複制**、**安全性**，並透過強領導者模型、任期號、日誌連續性等機制，達成比 Paxos 更易理解、更易工程實現的一致性協議。本文系統整理 Raft 核心機制、流程細節、工程落地要點與常見問題。

核心概念術語

術語	說明
Leader	唯一處理寫入請求的節點，發送心跳/日誌維持權威
Follower	被動接收請求，轉發寫入給 Leader
Candidate	選舉過程中臨時角色，發起 RequestVote
Term (任期)	邏輯時鐘，單調遞增，每次選舉產生新 Term
Log Index	日誌條目序號，從 1 開始單調遞增
Quorum (多數派)	N/2+1 節點，確保任兩個 Quorum 至少有一個交集
Commit Index	已提交的最高日誌索引，可應用到狀態機
Election Timeout	隨機化超時 (150-300ms)，避免選票分裂

Raft 核心原則

1. 強領導者：所有寫入經 Leader，日誌單向流向 Follower。
2. 領導者完整性：Leader 擁有所有已提交日誌，不修改自身日誌，只追加。
3. 日誌匹配：相同 Term+Index 的日誌內容必相同；若某節點應用了 (Term, Index)，其他節點同位置必應用相同日誌。
4. 狀態機安全：同樣輸入序列 → 同樣狀態機狀態。
5. 不依賴物理時鐘：透過邏輯 Term+Index 保證順序。

一、領導者選舉

觸發條件

• Follower 在 electionTimeout 內未收到 Leader 的 AppendEntries (含心跳)。
• 啟動時所有節點為 Follower。

Candidate 流程

1. CurrentTerm++，轉為 Candidate，投自己一票。
2. 併發發送 RequestVote(term, candidateId, lastLogTerm, lastLogIndex) 給所有節點。 3. 等待回應，三種結果：
• ✅ 獲得多數派選票 → 成為 Leader，立即發送空 AppendEntries (心跳) 確立權威。
• ✅ 收到 Term ≥ CurrentTerm 的 AppendEntries/RequestVote → 回退 Follower。
• ⚠️ 超時未達多數派 → 可能選票分裂，CurrentTerm++ 發起新一輪選舉。

Follower 投票規則

1. 若候選人 Term < CurrentTerm → 拒絕。
2. 若尚未投票給他人，且候選人日誌「至少同樣新」 → 投票。
• 比較規則：lastLogTerm 較大者較新；Term 相同則比 lastLogIndex 較大者較新。
3. 每 Term 只投一票，先到先得。

隨機化超時避免活鎖

electionTimeout ∈ [150ms, 300ms] 隨機選取。最先超時的節點最先發起選舉，大概率單獨完成選舉，避免多 Candidate 互搶選票導致無 Leader (Live Lock)。

二、日誌複制

Leader 處理客戶端請求

1. 追加條目到本地日誌 (未提交)。
2. 併發發送 AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit) 給所有 Follower。 3. 等待多數派回應成功。 4. 推進 commitIndex，應用到狀態機，回應客戶端成功。 5. 後續心跳帶上新 leaderCommit，Follower 推進各自 commitIndex 應用。

Follower 處理 AppendEntries

1. Term < CurrentTerm → 回 false。
2. 若 prevLogIndex 處無日誌或 Term 不匹配 → 回 false (日誌不連續)。 3. 衝突處理：刪除 prevLogIndex 之後所有衝突條目，追加 Leader 發送的新條目。 4. 成功 → 回 true，更新 commitIndex = min(leaderCommit, lastNewIndex)。

Leader 重試機制

• 維護每 Follower nextIndex (下一條要發送的索引) 與 matchIndex (已確認匹配的最高索引)。
• AppendEntries 失敗 → nextIndex-- 重試，直到找到匹配點 (指數退避優化：每次退一個 Term)。
• 成功 → 更新 nextIndex = matchIndex + 1。

提交規則

只有 CurrentTerm 產生的條目 經多數派確認才可提交。舊 Term 條目隨新條目提交間接確認 (圖示參考論文 Figure 8)。

三、日誌壓縮與快照

目的

防止日誌無限增長佔滿磁碟，新節點加入時快速追趕。

快照內容

• 最後已提交條目 (lastIncludedIndex, lastIncludedTerm)
• 狀態機完整狀態資料
• 叢集配置資訊

Leader 發送快照

1. 發現 Follower nextIndex 落後超過閾值 (或新節點加入) → 觸發 InstallSnapshot。
2. 分塊發送 (term, leaderId, lastIncludedIndex, lastIncludedTerm, offset, data[], done)。

Follower 接收快照

1. Term < CurrentTerm → 忽略。
2. 第一塊 → 建立臨時快照檔。 3. 按 offset 寫入資料塊。 4. 最後一塊 → 原子替換舊快照、刪除 lastIncludedIndex 前日誌、載入狀態機。

四、叢集成員變更 (Joint Consensus)

從 C_old 遷移至 C_new，引入過渡配置 C_old-new (Joint Consensus)。

兩階段變更流程

1. Leader 收到變更請求，建立 C_old-new 配置條目，複制至多數派 (需同時在 C_old 和 C_new 達多數派)。
2. C_old-new 提交後，任何節點收到即採用新配置判斷多數派。 3. Leader 建立 C_new 配置條目，複制提交。 4. C_new 提交後，不在 C_new 的節點可安全下線。

關鍵不變量

任意時刻 最多只有一個 Leader。階段 1-3 只有 C_old 節點能當選；階段 4-6 只有含 C_old-new 節點能當選；階段 7-8 只有 C_new 節點能當選。

五、工程落地關鍵參數

參數	建議值	說明
heartbeatInterval	50-100ms	遠小於 electionTimeout
electionTimeout	150-300ms (隨機)	≫ heartbeatInterval，≪ MTBF
maxAppendEntriesSize	1-4 MB	批次複制大小，平衡延遲與頻寬
snapshotThreshold	10k-100k entries	觸發快照的日誌長度
snapshotInterval	30-60min	定期快照間隔

六、常見問題 Q&A

1. Raft 會活鎖嗎？ → 隨機化 electionTimeout 解決。極端網路分割仍可能長時間無 Leader，需外部監控介入。
2. 需要 NTP 同步物理時鐘嗎？ → 不需要，完全依賴邏輯 Term+Index。但需保證 broadcastTime ≪ electionTimeout ≪ MTBF。
3. 如何保證 Leader 有所有已提交日誌？ → 選舉時比較 (lastLogTerm, lastLogIndex)，多數派交集保證至少一個節點有最新日誌。
4. 日誌連續性優缺點？ → 優：邏輯簡單、Leader 不需從 Follower 拉取。缺：落後節點必須循序追趕，網路抖動耐受度較低 (Paxos 允許空洞)。
5. 舊 Term 條目達成多數派卻被覆蓋？ → 可能。Figure 8 展示：Term 2 條目達成多數派，但 Term 3 Leader 未包含該條目，後續 Term 4/5 複制導致被覆蓋。只有 CurrentTerm 條目達成多數派才算真正提交。

七、知名實作參考

• etcd / Consul：基於 Raft (go-raft / raft 库)
• TiKV：Raft + RocksDB，多 Raft Group
• SOFAJRaft：螞蟻金服 Java 實作
• braft：百度 C++ 實作 (brpc 組件)

參考文獻

1. Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (Raft), 2014.
2. Ongaro, Consensus: Bridging Theory and Practice, PhD Thesis, Stanford 2014.
3. Raft 官網：動畫演示、論文、實作清單。

Raft 以「可理解性」為設計目標，將一致性拆解為選舉、複制、安全三模組，配合強領導者、日誌連續、任期號等機制，成為工業界分散式一致性的主流選擇。深入掌握其細節，是構建高可用分散式系統的必修課。