我對Raft的理解 - Two

我們已對 Raft Leader 選舉進行了理解，Leader 一旦被選舉出來，對外提供服務，對內協調日誌複製。日誌複製是 Raft 共識演算法最核心的部分，我們逐步遞進的去理解 Raft 是如何通過添加限制條件來保證日誌能夠被正確的複製。

Slide 11

每個節點都維護了一份私有的日誌的拷貝，節點存在宕機的風險，為了保證宕機後能夠恢復日誌，日誌需要持久化存儲在類似磁碟等介質中。日誌由一組日誌項組成，每個日誌項（Log Entry）包含三部分：Index、Term 和 Command。Index 指示了日誌項在日誌中的索引，它是日誌項的附加屬性，類似數組元素下標；Term 指示了日誌項被創建時 Leader 所處的任期；Command 指示了日誌項包含的操作。

Slide 11 中有一個 Leader，4 個 Follower，Leader 需要將日誌項正確的複製到 Follower。注意，Leader 的目標並不在於將所有的日誌項都複製到 Follower，而在於複製已經 Committed 的日誌項。Committed 是 Raft 中另一個非常重要的概念，需要好好理解。那麼什麼樣的日誌可以被認為是 Committed 的？我們先給出一個定義：如果某個日誌項已經被複制到了大多數節點，那麼就可以認為該日誌項是 Committed 了，Raft 需要保證，已經 Committed 的日誌項會永遠存在於大部分節點的日誌中。不過，目前這個定義並不能保證日誌被正確的複製，還需要添加限制條件。

按照目前對 Committed 的定義，日誌項 1 至日誌項 7 已經被 Leader 複製到了大部分節點，因此可以認為前 7 項日誌項已經 Committed 了。Committed 的日誌項可以被狀態機執行，而只有被狀態機執行，才能響應客戶端。

Slide 12

Raft 反覆強調演算法的可理解性，在日誌複製的過程中，Raft 將問題再次分解：Leader 正常運行時的日誌複製和 Leader 變更後的日誌複製。Leader 正常運行時的日誌複製比較簡單，分為以下幾個步驟。

• 客戶端向 Leader 發送指令，如果客戶端向 Follower 發送了指令，Follower 會將請求重定向至 Leader。
• Leader 創建日誌項並 Append 至日誌中。
• Leader 向 Follower 發送 AppendEntries 消息，消息中包含了任期 Term 和指令（消息內容會在下文擴展）。
• Follower 收到 AppendEntries 消息後，也會將日誌 Append 至自己的日誌中，然後響應 Leader。
• 如果 Leader 收到了大多數 Follower 的響應，說明日誌項已經被複制到大多數節點了，即日誌項已 Committed，Leader 將指令傳遞給狀態機執行，並將結果返回給客戶端。然後，Leader 向 Follower 發送 AppendEntries 消息，通知 Follower 該日誌項已經 Committed，Follower 在收到消息後也會將指令傳遞給狀態機執行。

如果 Follower 宕機，或者響應特別慢怎麼辦？Raft 會不斷重試 RPC 請求直到成功。但是這對 Raft 的性能並不會有影響，因為 Leader 只需要收到大多數 Follower 的響應即可。

Slide 13

Raft 解決的核心問題是如何安全的複製日誌，使大多數節點都擁有已經 Committed 的日誌。如果日誌能夠達成一致，那麼 Raft 可以做出以下承諾。

• 位於不同節點的兩個日誌項如果有相同的 Index 和 Term，那麼他們有相同的指令。
• 位於不同節點的兩個日誌項如果有相同的 Index 和 Term，那麼該日誌項之前的所有日誌項也是相同的，包括 Index、Term 和指令。

基於以上兩個承諾，可以進一步得出：如果某個日誌項已經是 Committed，那麼該日誌項之前的所有日誌項也已是 Committed 的。可以這麼理解：如果某個日誌項是 Committed 的，那麼說明該日誌項已經被複制到了大多數節點，根據兩個承諾，該日誌項之前的所有日誌項是也都已經被複制到了大多數節點，因此也是 Committed 的。

注意，不要忘記目前我們仍然簡單地認為，只要日誌項被複制到大多數節點上就是 Committed 了，接下來我們會修改日誌項 Committed 的條件。

接下來我們開始分析，Raft 是如何能夠在複製日誌時始終兌現承諾的？

Slide 14

基於 Raft 在複製日誌時的承諾，我們可以得出重要的一個結論：Index 和 Term 可以唯一確定一個日誌項。也就是說，如果兩個日誌項有相同的 Index 和 Term，那麼這兩個日誌項的指令一定相同。這是因為如果 Term 相同，說明是同一個 Leader 創建的日誌項，而同一個 Leader 在某個 Index 下創建的日誌項一定是相同的。這個結論會貫穿我們對 Raft 剩餘部分的理解。我們現在關注 Raft 是如何實現承諾的。

Leader 在向 Follower 複製日誌時，發送的 AppendEntries 消息內會攜帶待複製日誌項的前一個日誌項的 Index 和 Term。當 Follower 收到消息時，並不是無條件的 Append，而是會校驗消息中的 Index 值和 Term 值是否等於 Follower 最後一個日誌項的 Index 值和 Term 值，只有匹配才會 Append，否則直接拒絕。例如，Slide 14 中 Leader 準備複製 （5，3）日誌項，消息中會附帶上一個日誌項（4，2）至 Follower，Slide 14 描述了兩種可能的情況。

基於 Follower 在 Append 日誌項時會進行校驗，我們嘗試證明 Slide 13 中的兩個承諾：證明過程實際上就是一個歸納的過程，一開始，所有 Follower 的日誌為空時一定是成立，而接下來每次 Append 日誌項都會校驗前一個日誌項是否一致，因此可以保證當前複製成功的日誌項之前的所有日誌項也都是一致的。

注意：目前我們還不考慮 Leader 發生變更，這意味著 Leader 一定擁有所有已經 Committed 的日誌項，那麼如果出現 Leader 變更怎麼辦？我們會繼續理解 Raft，實際上 Raft 在 Leader 選舉時也有限制條件，並不是任意 Candidate 都能贏得選舉。

Slide 15

之前的討論都是基於 Leader 正常運行時的情況，現在我們看看 Leader 發生變更時 Raft 是怎麼處理的。

Slide 15 展示了一種比較混亂的情況，不過我們可以推導 Leader 選舉情況。Term 1 各個節點都運行正常，然後發生了 Leader 變更進入 Term 2， S5 成為了 Leader，接著又發生了 Leader 變更，S5 又成為 Leader，在運行一段時間後 S5 崩潰，S4 成為新的 Leader，然後 S4 又崩潰，S3 成為 Leader，然後 S1 成為 Leader，最後 S2 又成為 Leader。期間很可能發生了網路隔離，S1、S2 和 S3 在一個分區，S4 和 S5 在另一個分區。

注意，我們已經強調過，Raft 的目的是要把已經 Committed 的日誌項到大部分節點，而那些尚未 Committed 的日誌項並不需要複製。如果某個日誌項沒有 Committed，那麼該日誌項對應的客戶端也不會收到響應，客戶端在超時後重試即可。所以，Raft 要做的就是讓新選舉出來的 Leader 包含所有已經 Committed 的日誌項，然後再由 Leader 將 Committed 的日誌項複製到其他節點上。因此，如果 Leader 包含所有已經 Committed 的日誌項，那麼 Leader 就是所謂的 「The Truth」，所以 Leader 只需要把自己的日誌項複製到 Follower 就實現了一致。

按照我們目前對 Committed 的定義，Term 1 中的所有日誌項以及 Term 5 中 Index 等於 3 的日誌項已經是 Committed 的。因此 Raft 要做的就是選舉一個擁有所有 Committed 日誌項的 Candidate 作為 Leader，然後讓 Follower 的日誌和 Leader 一致就可以了。整個過程是非常自然：新選舉出來的 Leader 並不會先和 Follower 進行日誌同步，而是在進行日誌複製時進行校驗，一旦出現不一致再進行日誌的複製。同時，為了和 Leader 達成一致，Follower 勢必會捨棄自己原有的尚未 Committed 的日誌項。

小結：當 Leader 發生變更，Raft 要求新選舉出來的 Leader 必須包含所有已經 Committed 的日誌項，Leader 接下來只需要單純的進行日誌複製。 因此，我們接下來需要理解的問題就是：Raft 是如何保證新選舉出來的 Leader 一定是擁有所有 Committed 日誌項的？

Slide 16

為了保證 Leader 變更時的安全性，Raft 提出了一個 Safe Property：如果一個 Leader 決定某個日誌項已經是 Committed 的，那麼該日誌項會一直出現在未來 Leader 的日誌中。 Safe Property 其實是和 Slide 15 提到的概念是一致的，即新選舉出來的 Leader 需要包含所有已經 Committed 的日誌項。

為了滿足安全性需求，Leader 需要滿足以下三點。

• Leader 只能 Append 日誌項，不能覆蓋日誌項。需要注意的是，這點僅僅是針對 Leader 的要求，Leader 包含所有已經 Committed 的日誌項，同時 Leader 也可能包含某些尚未 Committed 的日誌項，Raft 要做的是將已經 Committed 的日誌項複製到 Follower，但是如果把 Leader 尚未 Committed 的日誌項複製給 Follower，也是沒有問題的。而一旦下次出現 Leader 變更，上個 Leader 中尚未 Committed 的日誌項也是會被捨棄的。
• 只有在 Leader 中的日誌項才能被 Committed。
• 只有已經 Committed 的日誌項才能被應用到狀態機。

回顧 Slide 15，Raft 要保證新選舉出來的 Leader 必須是包含所有已經 Committed 的日誌項，接下來我們開始分析 Raft 增加了哪些限制條件來實現這一目標。同時，我們也進一步在日誌項 Committed 的定義上增加限制條件。

Slide 17

前文已經說到，新選舉出來的 Leader 應該包含所有 Committed 日誌項，但是實際上很難界定一個日誌項是否是 Committed 的，按照目前對 Committed 的定義，即很難界定一個日誌項是否已經被複制到大部分節點。Slide 17 描述了一種場景：存在三個節點，其中日誌項 5 已經被複制到大多數節點，即日誌項 5 已經是 Committed 的，如果節點 3 突然宕機，需要從剩餘 2 個節點中選舉 Leader，此時日誌項 5 是否已經 Committed 是無法得知的，因為日誌項 5 是否 Committed 取決於節點 3，而節點 3 宕機了。

Raft 採取的策略是：選擇最有可能包含所有 Committed 日誌項的節點作為 Leader。最有可能的含義是指某個節點包含最新且數量最多的日誌項。其中最新體現在節點最後一個日誌項有最大的 Term，數量最多是在最新的基礎上，日誌項的 Index 最大。

現在給 Raft Leader 選舉增加限制條件：Candidate 給其他節點發送的 RequestVote 消息中會同時攜帶 Candidate 最後一個日誌項的 Term 和 Index，其他節點在收到 RequestVote 消息後，如果發現消息中的 Term 大於自己當前的 Term，或者 Term 相同，但是消息中的 Index 更大，那麼可以認為 Candidate 擁有更完整的日誌項，因此就會給 Candidate 投票，否則拒絕投票。

Slide 18

我們以具體的場景進一步理解 Leader 選舉。5 個節點，S1 為 Leader，其餘均為 Follower。S1 將日誌項 4 複製到了 S3，此時日誌項 4 已經是 Committed 了。如果現在出現 Leader 變更，S4 最多能夠獲得來自 S5 的投票，S5 不會獲得任何投票，只有 S1、S2 或 S3 可以贏得選舉，而 S1、S2 和 S3 都是擁有所有已經 Committed 日誌項的節點，所以能夠保證安全性。

Slide 19

再分析一個場景。5 個節點，S1 當選為 Term 2 的 Leader，複製日誌項 2 至 S2後，S1 宕機。在 Term 3，S5 可以獲得來自 S3、S4 和自身的投票併當選為 Leader，S5 創建了 3 個日誌項後宕機。進入 Term 4，S1 可以獲得來自 S2、S3 和 S4 的投票併當選為 Leader，S1 將日誌項 3 複製至 S3 後，日誌項 3 已經在被複制到了大多數節點，那麼此時能否認為日誌項 3 是 Committed 的呢？

答案是不能，考慮這種場景：當 S1 把 日誌項 3 複製到 S3 後，S1 又宕機了。進入 Term 5，S5 可以獲得來自 S2、S3 和 S4 的投票，因為 S5 的 Term 更大，所以 S5 可以當選為 Leader。當 S5 成為 Leader 之後，S3 將會用自己的日誌項 3 覆蓋 S1、S2 和 S3 的日誌項 3，這將導致覆蓋已經 Committed 的日誌項，顯然不能保證安全性。

我們意識到之前關於 Committed 的定義已經不能夠保證安全性了，所以我們需要給 Committed 的定義增加限制條件。

Slide 20

為 Committed 的定義增加一條新的限制：只有在當前 Term 內創建的新日誌項被複制到大部分節點後，之前 Term 內被複制到大部分節點的日誌項才是 Committed 的。可以這麼理解，如果當前 Term 內的日誌項都已經被複制到了大部分節點，那麼該日誌項之前的日誌項更應該是被複制到了大部分節點。而當前 Term 內的日誌項被複制到大部分節點，又可以保證比當前 Term 低的節點不可能在下次選舉中成為 Leader。

再次回顧上一個不安全的場景：S1 把在 Term 4 內創建的日誌項 4 複製到了大部分節點後，如果 S1 宕機了，S5 是無法獲取大部分投票從而無法成為 Leader。因為日誌項 4 已經被複制到了大部分節點，所以此時才可以認為日誌項 3 已經是 Committed 的。

截止目前，我們梳理完畢 Raft 演算法為了保證安全性給 Leader 選舉 和 Committed 定義增加的限制條件。

Slide 21

通過增加限制條件，我們現在已經可以保證 Raft 的安全性。當 Leader 選舉出來後，有些 Follower 可能缺少日誌項，有些 Follower 可能存在無關的未提交日誌項。注意，Follower 中如果存在 Leader 不存在的日誌項，Follower 並不需要複製給 Leader，因為日誌項未提交說明該日誌項對應的客戶端沒有收到響應，客戶端可以通過重試解決問題。所以，只需要讓 Follower 的日誌和 Leader 保持一致即可。

Slide 22

我們已經知道，為了和 Leader 的日誌一致，Follower 需要刪除不相關的日誌項和填充缺失的日誌項，那麼 Raft 是怎麼實現的呢？Leader 為每個 Follower 維護了一個 NextIndex 標記，NextIndex 的值初始化為 Leader 最後一個日誌項的 Index 加 1。Leader 在向 Follower 發送 AppendEntries 消息時會發現一致性問題，一旦不一致，那麼 NextIndex 減 1。

以 Slide 22 圖例說明，Leader 為每個 Follower 的 NextIndex 值初始化為 11，然後進行日誌複製，Leader 發送 AppendEntries 消息給 Follower，AppendEntries 消息中會攜帶 Leader 的最後一個日誌項的 Index 和 Term，即（10，6）。如果發生衝突，NextIndex 減 1，Leader 會發送攜帶（9，6）的 AppendEntries 消息，直至 Leader 發送攜帶（4，4）的 AppendEntries 消息後，才解決衝突。衝突解決後，Leader 就可以將後續所有的日誌項發送給 Follower。

注意，因為在節點剛當選 Leader 時很可能首先會發送心跳消息（不包含日誌的 AppendEntries 消息）給 Follower，因此我們認為是最後一個日誌項的 Index 和 Term。如果是普通的 AppendEntries 消息（包含日誌），依舊發送包含（10，6）的 AppendEntries 消息給Follower，如果一致那麼消息中的日誌就直接複製給 Follower，如果不一致 NextIndex 減 1。

Slide 23

在進行日誌複製時，當 Leader 通過調整 NextIndex 找到了衝突日誌的起始位置後，就開始複製日誌給 Follower。一旦 Follower 的日誌項被覆蓋，那麼該日誌項之後的所有日誌項都會被捨棄。

以 Slide 23 為例，當 Leader 將 日誌項 4 複製給 Follower 後，Follower 日誌項 4 之後的所有日誌項便是多餘的，可以直接捨棄。

小結

Raft 為了保證日誌複製時的安全性，為 Leader 選舉和日誌項的 Committed 增加了限制條件。通過分析各種場景，我們理解了 Raft 增加這些限制條件的原因，以及這些限制條件為什麼能夠保證安全。