我對Raft的理解 - One

02-12

重新閱讀了 Raft 論文，結合 John Ousterhout 在斯坦福大學的課程視頻，對 Raft 重新梳理了一遍，並決定用文字記錄下來。

Raft 是一個共識演算法，何為共識演算法？通俗的說，共識演算法的目的就是要實現分散式環境下各個節點上數據達成一致。那麼節點的數據為什麼會出現不一致？原因有很多，例如節點宕機、網路延遲、數據包亂序等等。但是要注意的是，Raft 並不考慮存在惡意的節點的情況，也就是說，不存在主動篡改數據的節點。所以可以理解為：允許節點宕機，但是只要節點沒有宕機，那麼它就是正常工作的。

Slide 1

Raft 是為 Replicated Logs 設計的共識演算法。一條日誌對應於一個指令。可以這麼理解：如果各個節點的日誌在數量和順序都達成一致，那麼節點只需順序執行日誌，就能夠得到一致的結果。注意，真正執行日誌的是狀態機（State Machine），Raft 協調的正是日誌和狀態機。

Slide 2

再次回顧 Replicated Log，Raft 需要實現將日誌完全一致的複製到其他節點，進而創建多副本狀態機（Replicated State Machine），狀態機可以理解為一個確定的應用程序，所謂確定是指只要是相同的輸入，那麼任何狀態機都會計算出相同的輸出。至於如何實現日誌完全一致的複製，則是 Raft 即一致性模塊（Consensus Module）需要做的事。

重新思考，為什麼需要在多個節點維護一份完全一致的日誌？如果只有 1 個節點提供服務，那麼它就會成為整個系統的瓶頸，如果這個節點崩潰了，服務也就不能提供了。所以很自然的，需要讓多個節點能夠提供服務，也就是說，如果提供服務的某個節點崩潰了，系統中其他節點依舊可以提供等價的服務，但是如何做到等價？這就需要系統中的節點維持一致的狀態。注意，實際上並不需要所有的節點同時擁有一致的狀態，只要大多數節點擁有即可。大多數指的是：如果一共存在 3 個節點，允許 1 個幾點不能正常工作；如果一共有 5 個節點，允許 2 個節點不能正常工作。為什麼是大多數？我們將通過接下來的 Slides 進一步理解。

Slide 3

共識演算法通常分為兩類：對稱式共識演算法和非對稱式共識演算法。

對稱式共識演算法指網路中不存在中心節點 Leader，所有的節點都具有相同的地位，節點與節點之間通過互相通信來達成共識，即網路拓撲結構類似 P2P 網路。可想而知，對稱式類的共識協議會非常複雜，但是性能會更好，因為網路中的節點可以同時提供服務。
非對稱式共識演算法會選舉出一個 Leader，剩餘的節點作為 Follower，客戶端只能和 Leader 通信，節點之間的共識通過 Leader 來協調。相比於對稱式共識演算法，非對稱式共識演算法能夠簡化演算法的設計，所有的操作都通過 Leader 完成，Follower 只需被動接受來自 Leader 的消息。

Raft 是一種非對稱的共識演算法，也正是採用了非對稱的設計，Raft 得以將整個共識過程分解：共識演算法正常運行和 Leader 變更。

Slide 4

Raft 論文中多次強調 Raft 的設計是圍繞演算法的可理解性展開，我們將從六個部分對 Raft 進行理解。

Leader 選舉，以及如何檢測異常並進行新一輪的 Leader 選舉。
基本的日誌複製操作，也就是 Raft 正常運行是時的操作。
在 Leader 發生變更時如何保證安全性和一致性，這是 Raft 演算法最關鍵的部分。
如何避免過時的 Leader 帶來的影響，因為一個 Leader 宕機後再恢復仍然會認為自己是 Leader。
客戶端交互，所謂實現線性化語義可以理解為實現冪等性。
配置變更，如何維持在線增刪節點時的安全性和一致性。

Slide 5

Raft 演算法有幾個關鍵屬性，我們需要提前了解。首先是節點的狀態，相比於 Paxos，Raft 簡化了節點可能的狀態，在任何時候，節點可能處於以下三種狀態。

Leader。Leader 負責處理客戶端的請求，同時還需要協調日誌的複製。在任意時刻，最多允許存在 1 個 Leader，也就是說，可能存在 0 個 Leader，什麼時候會出現不存在 Leader 的情況？接下來會說明。
Follwer。在 Raft 中，Follower 是一個完全被動的角色，Follower 只會響應消息。注意，在 Raft 中，節點之間的通信是通過 RPC 進行的。
Candidate。Candidate 是節點從 Follower 轉變為 Leader 的過渡狀態。因為 Follower 是一個完全被動的狀態，所以當需要重新選舉時，Follower 需要將自己提升為 Candidate，然後發起選舉。

Raft 正常運行時只有一個 Leader，剩下的均為 Follower。

從狀態轉換圖可以看到，所有的節點都是從 Follower 開始，如果 Follower 經過一段時間後收不到來自 Leader 的心跳，那麼 Follower 就認為需要 Leader 已經崩潰了，需要進行新一輪的選舉，因此 Follower 的狀態變更為 Candidate。Candidate 有可能被選舉為 Leader，也有可能回退為 Follower，具體情況下文會繼續分析。如果 Leader 發現自己已經過時了，它會主動變更為 Follower，Leader 如何發現自己過時了？我們下文也會分析。

Slide 6

Raft 的另一個關鍵屬性是任期（Term），在分散式系統中，由於節點的物理時間戳都不統一，因此需要一個邏輯時間戳來表明事件發生的先後順序，Term 正是起到了邏輯時間戳的作用。Raft 的運行過程被劃分為一系列 Term，一次 Leader 選舉會開啟一個新的 Term。

因為一次選舉最多允許產生一個 Leader，一次選舉又會開啟一個新的 Term，所以每個 Leader 都會維護自己當前的 Term（Current Term）。注意，Leader 需要持久化存儲 Current Term，當 Leader 宕機後再恢復，Leader 仍然會認為自己是 Leader，除非發現自己已經過時了，如何發現自己過時？依靠的正是 Current Term 的值。

一次 Term 也可能選不出 Leader，這是因為各個 Candidate 都獲得了相同數量的選票，具體細節下文會再闡述。目前我們需要知道的是 Term 在 Raft 中是一個非常關鍵的屬性，Term 始終保持單調遞增，而 Raft 認為一個節點的 Term 越大，那麼它所擁有的日誌就越準確。

Slide 7

需要注意的是，Raft 有需要持久化存儲的狀態，包括 Current Term、VotedFor（下文會解析）和日誌。每個日誌項結構非常簡單，包括日誌所在 Term、Index 和狀態機需要執行的指令。節點之間的 RPC 消息分為兩類，一類為選舉時的消息，另一類為 Raft 正常運行時的消息。具體細節我們會在下文理解。

Slide 8

Raft 中 Leader 和 Follower 之間需要通過心跳消息來維持關係，Follower 一旦在 Election Timeout 後沒有收到來自 Leader 的心跳消息，那麼 Follower 就認為 Leader 已經崩潰了，於是就發起一輪新的選舉。在 Raft 中，心跳消息復用日誌複製消息 AppendEntries 數據結構，只不過不攜帶任何日誌。

Slide 9

現在開始正式理解 Raft 的選舉過程，大部分內容已有所介紹，我們再梳理一遍。

當新的一輪選舉開始時，Follower 首先要自增當前 Term，代表進入新的任期，緊接著變更狀態為 Candidate，每個 Candidate 會先給自己投上一票，然後通過發送 RequestVote RPC 消息呼籲其他節點給自己投票。選舉結果存在三種可能。

Candidate 收到了大多數節點的投票，那麼 Candidate 自然就成為 Leader，然後馬上發送心跳消息維護自己的 Leader 地位，並對外提供服務。
Candidate 在等待來自其他節點的選票的過程中收到了來自 Leader 的心跳消息，Candidate 可以看到當前的心跳消息中包含更新的 Term，就會意識到新的 Leader 已經被選舉出來，於是就自降為 Follower。
各個 Candidate 都獲得了相同數量的選票，那麼每個節點都會繼續等待選票，沒有新的 Leader 產生。等待一定的時間後，重新開啟選舉過程，知道選出新的 Leader。

需要考慮的是 Raft 如何避免重複出現 Candidate 瓜分選票的情況：如果當前輪選舉 Candidate 瓜分了選票，那麼Candidate 會進入下一輪的選舉，但是各個 Candidate 開始選舉的時刻是隨機的。

Slide 10

繼續理解選舉過程，選舉過程需要保證兩個特性：Safety 和 Liveness。

Safety 要求每個 Term 最多只能選舉出一個 Leader，Raft 約束每個節點除了能給自己投一票，也只能給其他節點投一票。因此，如果 Candidate A 已經獲得了大多數選票，由於每個節點只能向外投一票，因此 Candidate B 不可能獲得大多數選票。Safety 特性保證一段時間內只可能存在一個 Leader 提供服務並協調日誌的複製，避免因為存在多個 Leader 導致日誌不一致。
Safety 要求一段時間內最多只能存在一個 Leader，而 Liveness 保證系統最終必須要有要有一個 Candidate 贏得選舉成為 Leader，Leader 無法選舉出來意味著系統不能對外提供服務。Raft 實現 Liveness 的方式很簡單，在 Slide 9 已經提及：當某一輪選舉 Candidate 瓜分了選票，那麼各個節點進入下一輪選舉等待的時間是隨機的，Candidate 隨機等待 [T, 2T]， T 為選舉超時時間，這樣就大大減少了再次瓜分選票的概率。

小結

對 Raft Leader 選舉過程的理解基本結束，Raft 為了提高演算法的可理解性，將問題分解，我們接下來會繼續理解 Raft 的剩餘部分。