Raft協議精解

Raft協議精解

來自專欄 碼洞

RaftServer的基本結構

1. Raft伺服器支持多個客戶端並發連接
2. 一致性模塊負責接收客戶端的消息，追加到本地日誌中
3. 一致性模塊負責複製日誌到其它伺服器節點
4. 本地日誌commit成功後立即應用到狀態機
5. 客戶端可以直接查詢本地狀態機的狀態

日誌序列的重要變數

1. firstLogIndex/lastLogIndex標識當前日誌序列的起始位置，如果日誌不做壓縮處理，也就是沒有快照模塊的話，那麼firstLogIndex就是零值。
2. commitIndex表示當前已經提交的日誌，也就是成功同步到majority的日誌位置的最大值
3. applyIndex是已經apply到狀態機的日誌索引，它的值必須小於等於commitIndex，因為只有已經提交的日誌才可以apply到狀態機

伺服器重要的狀態變數

1. 每個伺服器都有自己的日誌序列，日誌序號索引從1開始，因為0有特殊意義，表示伺服器剛剛初始化還沒有包含任何日誌。日誌序列非常重要，是它決定了狀態機的狀態。
2. 每個伺服器都必須有當前的任期號，從零開始，以後逐漸單嚮往上遞增。伺服器重啟後需要知道當前的任期號才可以正確的很其它節點交流，所以任期號是必須持久化的。
3. 如果給候選節點投票了，要記錄下被投票的候選節點ID。如果節點在選舉期間給了一個候選人投票後突然宕機重啟了，如果沒有記下這個值，就很可能會重複投票，又給另一個節點投票去了。這就會導致集群存在多個Leader，也就是集群分裂。
4. 當前已經提交的日誌索引位置，伺服器初始化時這個值是零表示還沒有任何日誌被提交。這個位置之前的所有日誌都可以安全地應用到狀態機中而不用當心會被覆蓋。
5. 當前已經被應用到狀態機的日誌索引位置，它一般和提交索引保持一致。因為一旦提交索引前進了，那麼新的已經提交的日誌就會立即應用到狀態機中，而不應該有任何延時。
6. Leader需要記錄自身日誌和所有的Follower日誌的匹配位置matchIndex。matchIndex之前的日誌Leader和Follower都是一致的。同時還需要記錄下一個即將需要同步給Follower的日誌位置。處於matchIndex和nextIndex之間的日誌就是哪些正在同步中的日誌，是Leader已經向Follower發過去的AppendEntries消息還沒有得到成功回應的日誌列表，用一個高大上的辭彙來描述那就是inflight logs。

為什麼commitIndex和applyIndex可以不用持久化呢？

這個和日誌複製的機制有關係。首先對於選舉，PK的條件不是拼這兩個索引值的大小，PK的是最後一條日誌的任期號和日誌的長度。Leader當選後進行第一次日誌複製時，會和Follower進行若干次日誌的匹配過程，最終可以得到Leader和各自Follower的日誌匹配的matchIndex值。處於majority節點列表的matchIndex的最小值就是當前Leader的commitIndex。所以commitIndex值是完全可以動態計算出來的。

如果所有的日誌都保留不截斷的話，伺服器重啟時applyIndex應該等於零。然後重放一下所有的已經提交的日子就可以得到當前的狀態機。如果日誌截斷有快照的話，applyIndex應該正好是日誌序列的頭部位置，這個位置一般是存儲在快照元信息裡面的，它是持久化在磁碟中的。

選舉階段候選人請求投票RPC

1. 候選人需要攜帶自己的任期號，供目標節點比較。同時要提供節點ID，因為投票的節點需要記錄被投票的節點ID，就是前文中的voteFor欄位。
2. 候選人需要攜帶自身日誌序列的最後一條日誌的任期和索引號，供目標節點進行日誌的比較。
3. 如果候選人的任期號比自己還小，那麼就拒絕投票
4. 如果自己在當期任期已經投票了，那麼也必須拒絕投票。同一任期內不得重複投票，否則會導致多個Leader的產生，也就是集群分裂
5. 否則比較尾部日誌的任期號和索引值，如果候選人的日誌更新一些，那就支持投票。否則就拒絕投票。
6. 拒絕投票一般不是不響應投票請求，而是快速地給予一個狀態為failure的響應。還需要攜帶投票者的任期號，以便候選人能跟上時代（更新自己的任期號）。
7. 所謂日誌的update-to-date，指的是最後一條的任期號是否更大，如果一樣大的話，最後一條的日誌序號是否更大。

日誌複製階段Leader的日誌同步請求

1. 日誌同步需要攜帶Leader的任期號和Leader的節點ID。之所以要攜帶節點ID，是因為Follower可以告知客戶端Leader是哪個節點，因為客戶端第一次來連的時候可能是選擇了任意一個節點。
2. 日誌同步需要攜帶需要同步的日誌列表以及日誌列表前面最後一條日誌的索引prevLogIndex和任期號prevLogTerm。Follower需要這兩個值來和自己的本地日誌進行比對。
3. 日誌同步需要攜帶Leader的日誌提交索引值，如果這個值比本地日誌的提交索引值要大，那就將本地的這個值往前進。提交索引值之前的所有日誌就可以安全的apply到狀態機了。
4. 如果同步請求的任期號比Follower的任期號還小，那就直接拒絕，並帶上自己的任期號，以便Leader進行跟上時代（更新自己的任期號）。
5. 如果Follower本地日子的prevLogIndex位置處沒有日誌或者對應的term不匹配，那就拒絕同步。同時將日誌在不匹配的位置處進行截斷，後面的所有日誌統統剁掉。
6. Leader收到了Follower的拒絕時，如果響應的任期號比Leader本身還大，那麼Leader理解退職變身Follower。如果響應的任期號不超過Leader，Leader就將同步的日誌列表往前挪一個位置，再重試同步請求。
7. Follower如果在prevLogIndex處日誌的term和請求消息中的prevLogTerm匹配，那麼就將消息中的日誌追加到自身的日誌序列上，這個時候就可以向Leader響應成功了。
8. Leader收到成功響應後，更新內部記錄節點的matchIndex值，然後再前進全局的commitIndex值，並將最近剛剛成功提交的日誌應用到狀態機中。

基本規則

1. 隨意日誌同步的持續進行，commitIndex也一直在前進。已經commit的日誌要及時apply到狀態機，applyIndex要緊跟者commitIndex往前走。以免客戶端從狀態機中查詢數據時數據不太實時。
2. 如果收到的任意RPC消息中任期號大於當前節點的任期號，那麼立即跟新當前的任期號，並轉換角色為Follower。任期號小了，意味著落伍了。原因可能是網路分區後又恢復了，例如下圖中的灰色節點。

1. Follower是被動的，只會從candidate和leader接受RPC消息，而不是主動發出。
2. 如果長時間收不到任何任何RPC消息，就會轉變成candidate，參與選舉。
3. 節點一旦變成candidate，立即參與選舉。增加自己的任期號，給自己投票，向其它節點發送RequestVote RPC消息進行拉票。
4. candidate收到大多數節點的投票後，立即變成Leader。
5. 如果期間收到了其它節點發來的AppendEntries日誌同步請求，立即轉變成Follower。表名新的leader誕生了，選舉塵埃落定。
6. 如果選舉超時沒有形成多數派，那就重新開始選舉過程。
7. Leader一旦當選，立即向其它節點同步一個心跳消息(no-op)。這是為了確保當前沒有提交的日誌也能儘快得到提交。Leader只會追加日誌序列，剛當選時已經存在的日誌序列，Leader會努力將它們同步到所有節點，如果Follower存在的日誌和Leader有衝突，就會被抹平。最終Leader和Follower的日誌就會完全一致。
8. Leader收到客戶端請求後，首先追加到本地日誌序列，待日誌成功apply到狀態機後才向客戶端響應。
9. 如果Leader當前的日誌序列增長了(lastLogIndex > nextIndex)，立即向所有的Follower發送日誌同步消息。
10. 如果Follower成功響應，那麼就及時跟新matchIndex和nextIndex值。
11. 如果Follower失敗響應，那麼遞減nextIndex值重新同步。這是Leader採用後退重試法進行日誌同步的細節。
12. 如果存在majority的matchIndex前進了，Leader的本地日誌序列的commitIndex和applyIndex也要跟著前進。

Leader當選後為什麼要立即同步一個no-op日誌？

圖中S1~S5為集群中的5個節點，粗線框表示當前是leader角色。每個方框表示一條日誌，方框內的數字代表日誌的term。

現在假設沒有no-op日誌，會出現什麼問題

1. (a)圖，S1為Leader，將黃色的日誌2同步到了S2節點，突然就崩潰了
2. (b)圖，S5當選，將藍色的日誌3追加到本地日誌序列，又突然崩潰了
3. (c)圖，S1重新當選，追加了一條紅色的新日誌4到本地，然後又開始同步往期日誌，將黃色的日誌2又同步到了S3.這時黃色的節點2已經同步到了majority，但是還來不及commit，又突然奔潰了。
4. (d1)圖，S5重新當選，並開始同步往期日誌，藍色的日誌3到所有的節點。結果黃色日誌2被抹平了，雖然它已經被同步到了大多數節點。

遇到這種情況就會導致一條日誌雖然被同步到了大多數節點，但是還有被抹去的可能。

如果我們走(d2)圖，leader不去單獨同步往期的日誌，而是通過先同步當前任期內的紅色日誌4到所有節點，就不會導致黃色的節點2被抹去。因為leader會採用後退重試法來將自己的日誌序列同步到所有的Follower。在嘗試同步紅色節點4的過程中連帶黃色的節點2一起同步了。

例子中是因為S1重新當選後立即收到了客戶端的指令才有了紅色的日誌4。但是如果Leader剛剛當選時，客戶端處於閑置狀態沒有向Leader發送任何指令，也就沒有紅色的日誌4，那該怎麼辦呢？

Raft演算法要求Leader當選後立即追加一條no-op的特殊內部日誌，並立即同步到其它節點。這樣就可以連帶往期日誌一起同步了，保障了日誌的安全性。

快照同步和日誌壓縮

當leader和follower之間的日誌差異過大時，採用回退重試法同步日誌效率低下。而且回退重試法要求發送的日誌項包含所有不一致的日誌，可能導致消息過大，導致RPC不能正常進行。

快照RPC是以chunk的形式向Follower發送日誌，類似於HTTP協議的分塊傳送。它通過offset欄位標誌發送的位元組偏移，通過done欄位標誌是否是最後一個消息塊來進行分批傳送。

快照RPC需要告知Follower當前的快照數據截止的日誌索引，這樣下次進行日誌的增量同步時，從這個索引位置開始繼續發送AppendEntries消息將剩下的日誌追上。

快照日誌處理好和當前Follower已存在的日誌序列之間的關係。

如果快照日誌最後一個日誌項目在Follower當中已經存在，那就可以直接向Leader響應成功。因為這時快照數據是多餘的。否則Follower需要將當前所有的日誌序列清空，代之以快照日誌進行覆蓋。

快照是非常消耗資源的操作，所以Leader不能進行的太頻繁。一般是等到日誌序列的大小達到一個閾值後進行。快照類似於Redis的rdb操作，rdb操作完成，aof日誌就可以被截斷，於是日誌瘦身就完成了。

同樣redis的主從日誌同步同raft的日誌同步也是類似的。當主從日誌偏移差距過大時，採用快照同步，快照同步完成後繼續採用增量日誌同步。

關注公眾號「碼洞」，加入我們一起學習Raft協議

推薦閱讀：