Preface#

本次介紹的 Raft 算是筆者閱讀 《 In Search of an Understandable Consensus Algorithm 》 論文的筆記。如果夥伴希望深入了解 Raft 概念的話，論文絕對是最詳細的好夥伴。

Leader Election#

Raft 透過 heartbeat 與 randomized election timeout 來維持系統穩定與避免選舉衝突。

所有伺服器啟動時都是以 follower 身分開始，只要 follower 有持續收到來自 leader 或 candidate 的有效 AppendEntries RPC，就會維持在 follower 狀態。

Leader 會定期發送 AppendEntries RPC (no log entries) 最為 heartbeat 訊號，告訴 followers 它還存在並有效。若 follower 在一定時間內未收到任何 RPC (election timout)，則假設 leader 失效並啟動選舉流程。此時，follower 會把自己升級為 candidate 並投票給自己 (currentTerm + 1)，然後平行發送 RequestVote RPC 給 cluster 內其他所有伺服器。

接下來可能發生以下幾種情況 :

1. Candidate 獲得大多數節點的選票 (過半票)
   • 成為 Leader 並立即發送 Heartbeat 取得領導權 + 防止新選舉
   • 每個伺服器同個 term 內只能投給一個 candidate (first-come-first-served)
   • 遵守 Election Safety Property，一個 term 只會有一個 leader
2. 在等待投票期間，Candidate 收到其他伺服器的 AppendEntries RPC (宣稱是 Leader)
   • 若 incoming_term >= currentTerm，則承認該 leader 並回到 follower 狀態
   • 若 incoming_term < currentTerm，則拒絕 RPC 請求，繼續競選
3. 無人獲選 (票數分裂，無人過半)
   • 這種情況下，每個 candidate 都會 election timeout，重新啟動新一輪選舉

為了解決票數分裂的問題，Raft 採用 Randomized Election Timeout :

• 每個伺服器的 election timeout 隨機取自固定區間 150 ~ 300ms
• 導致某一伺服器較早 timeout 後發起選舉並當選

NOTE

AppendEntries RPC 在論文中定義的參數規格 :

Arguments

• term : leader’sterm
• leaderId : so follower can redirect clients
• prevLogIndex : index of log entry immediately preceding new ones
• prevLogTerm : term of prevLogIndex entry
• entries[] : log entries to store (empty for heartbeat)
• leaderCommit : leader’s commitIndex

Results

• term : currentTerm
• success : true if follower contained entry matching prevLogIndex and prevLogTerm

Log Replication#

Logs 組成如下圖，state machine 中的 log entry 會包含 term 和 command :