Raft協議及偽碼決議

• 節點的狀態轉換
  • follower
  • candidate
  • leader
• 偽碼部分
  • 節點初始化(Initialazation)
  • 選舉時其他節點的視角
  • 回到candidate選舉時的視角
  • 訊息如何廣播復制
  • 重要的反復出現的ReplicateLog
  • 節點收到了LogRequest
  • 節點如何追加log，Appendentries
  • 再次回到leader， 如何處理LogResponse
  • leader提交log，Commitlogentries

節點的狀態轉換

首先需要明確，節點只有三種狀態：

• follower
• candidate
• leader

follower

當一個節點剛啟動的時候，或者剛從崩潰中恢復，它只會變成follower，等待來自其他節點的訊息

candidate

當follower有一段時間沒有接收到來自leader或者candidate的訊息，它會開始懷疑leader已經掉線，于是準備開始發起選舉，推舉自己變成leader，

這段時間對于每個節點是隨機設定的，否則所有節點剛啟動的時候都會在同一時間發起選舉，

如何選舉？

概括一下：

1. candidate會增加自己的term，然后邀請其他節點進行投票，
2. 如果candidate接收到比自己更高的term(可能來自于leader或者其他candidate)，那么它會重新變成follower，
3. 如果candidate收到足夠多的投票，那么它會變成leader，

下文都會使用quorum(合法的法定人數)來表示足夠多的投票，表示過半數以上的節點，

4. 如果candidate沒有在計時器(timer)時間范圍內獲得quorum票數的話，選舉超時，它會再次增加term，發起投票邀請，再次進入選舉，

leader

當選了leader后，一般情況下會一直保持這個狀態，除非：

1. leader掉線了，那么它再次上線回重新變成follower，
2. 它接受到了來自其他節點發送的訊息，而他們的term比它更高，那么它也會變成follower，

這種情況可能是由于網路磁區導致其他節點無法與它連接，認為它已經掉線而重新進行了選舉，

偽碼部分

節點初始化(Initialazation)

初始化中需要注意的變數有：
需要持久化的四個變數(他們的值不能因為節點崩潰而丟失)

• currentTerm：節點當前處在的term值
• voteFor：節點把票投給的節點ID值
• log：可以認為是一個陣列，每一個值entry包含了msg和term值，msg表示需要向其他節點廣播復制的訊息，而term表示該條訊息所處的term的值，log通過追加新entry的方式進行增長，如果某條entry已經被quorum數量的節點復制成功，那么這條entry可以被commit，即被提交，
• commitLength：已經被提交的長度
  其他變數可以因為節點崩潰在恢復時被重置，同時假設，每個節點擁有唯一的ID，nodes變數保存了所有節點的ID，系統中的節點數量發生變化不在討論的范疇之內，

前面提到，當follower發現不能與leader進行通信時，會使自己的currentTerm+1，然后將自己設定為candidate，發起選舉，與此同時，它會將票投給自己，因此votedFor的值設定為自己的ID，votesReceived集合中也添加了自己的ID，并且初始化lastTerm，

lastTerm代表節點本地log的最后一條entry的term值，

candidate將構造好的投票資訊msg(由nodeId, currentTerm, log.length, lastTerm組成)發送給其他節點，開啟計時器，進行選舉，

選舉時其他節點的視角

當其他節點收到了投票請求后，會首先對自身的currentTerm與candidate發送過來的currentTerm(用cTerm替代)進行比較：

1. 如果自身currentTerm小于cTerm，那么自己變成follower，更改自己的currentTerm變成cTerm，
2. 如果自身存在log，取出自己最新接收到的entry的term值作為自己的lastTerm，
3. logOk的值當candidate發來的lastTerm(用cLogTerm代替) > lastTerm（candidate的最新的log的term比自己大）或者cLogTerm=lastTerm 但是candidate.log.length >= log.length(candidate雖然與當前node中的最新log的term值相同，但是candidate擁有很多msg)為true，

由3可見，logOk為true的前提是，candidate擁有更新更多的log，

4. 當且僅當currentTerm接受了candidate的cTerm，并且candidate擁有最新的log(logOk為true)，且沒有給其他candidate投票的情況下，可以將自身的voteFor的值設定為candidate的ID值，這種情況下，表示準備將票投給candidate，發送一條granted為true的VoteResponse(由當前節點ID-nodeId, currentTerm, 是否投票給它的granted)訊息回傳給它，否則，回傳一條granted為false的VoteResponse訊息，

回到candidate選舉時的視角

當candidate收到來自其他節點的回復時，判斷：

1. 如果自己仍然還是candidate，并且其他節點的term與自己的一致，也同意投票給自己，將這個節點添加至自己的votesReceived集合中(發起投票時，里面最初只有自己投給自己)，
2. 判斷votesReceived中節點的數量是否已經過半，如果已經過半了，那么將自己設定為leader，currentLeader的值為自己的節點ID，并且取消計時器，遍歷nodes集合中的所有node，更改sentLength和ackLength欄位，執行ReplicateLog函式，

sentLength和ackLength都可以看做是一個map，key為follower的nodeId， value是一個數值，代表長度，前者代表leader已經發送給某個follower的log長度，后者代表該follower已經確認收到的長度，顯然，當sentLength的值設定為log.length，表明leader假設follower已經擁有和leader一樣多的log，雖然這個假設可能是錯的，但是我們會在后面進行修正，
ReplicateLog也會在后面進行解釋，

3. 如果節點的term大于自身的currentTerm，表明有比自己更高term的節點存在，那么自己重新變成follower，并且更改自己的currentTerm為那個更高的term，取消定時器，終止選舉，

訊息如何廣播復制

當應用發送訊息給集群時，訊息是如何被保存提交的？

1. 如果leader接收了訊息，那么它可以將訊息直接保存到自己的log中，然后修改自己的ackedLength，再遍歷follower呼叫ReplicatedLog進行復制，
2. 如果是follower接收到了訊息，那么它需要通過FIFO佇列，將這個請求發送給leader進行處理，
   與此同時，leader會周期性地向follower復制訊息，即使沒有新的訊息需要進行廣播，這樣不僅可以充當與其他節點之間的心跳鏈接，也可以當做復制給某個follower失敗時的重傳，

重要的反復出現的ReplicateLog

在這里，sentLength派上了用場，利用sentLength將log分割成兩個部分：

• prefixLen：已經發送給follower的log長度
• suffix: 需要發送給follower的log的entry串列，

如果prefixLen = log.length，那么suffix為空，代表沒有新資料要發送給follower，
leader構造了一個LogRequest，包括自身的ID, currentTerm，prefixLen, prefixTerm(已經發送給follower的log的最后一個值log[prefixLen-1]的term), commitLength, suffix發送給follower，

節點收到了LogRequest

這時有兩種情況：

1. 節點可能正在處于candidate狀態，如果接收到的term值大于currentTerm，那么它會取消選舉，將自己變成follower，并設定leader，否則的話，回傳一條接收失敗的LogResponse給發送者，
2. 節點是個普通的follower，
   如果節點的狀態是follower，那么需要判斷logOk，這個值當且僅當當前節點的log長度大于等于prefixLen(當前節點的log不能小于leader認為的已經發送的長度，否則存在log的丟失)，以及如果存在prefixLen，那么leader端的prefixTerm應當與當前節點的最新log的term一致，

Raft保證，如果兩個節點的log在同樣的index包含同樣的term，那么他們在該index以及之前的log都是相同的，

如果節點的term與leader一致，并且logOk為true，那么節點將會執行Appendentries，并且更改自己的ack為prefixLen+suffix.length，作為LogResponse的一部分回傳，

節點如何追加log，Appendentries

follower需要判斷的是，是否已經包含了這個訊息，

1. 如果follower的log長度大于prefixLen，并且suffix的長度不為空，意味著follower中的log可能包含了以前leader的訊息，于是需要找到他們重疊位置的index，
   根據這個index的值，判斷當前log的term和suffix對應的term，如果不相等，意味著需要對當前的log進行截斷，即丟棄prefixLen之后的log，

為什么能在這個地方截斷？因為進入Appendentries的前提是logOk已經為true，此時已經保證prefixLen之前的term已經一致，

2. 將suffix的值追加到log中
3. 如果commitLength小于leader的commit的值，那么將自己沒有提交的log發送給應用，然后增加自己的commitLength，

再次回到leader， 如何處理LogResponse

1. 如果leader發現回傳的term大于自身的term，那么說明有新的leader，所以自身變為follower，
2. 否則，它會檢查其他節點是否已經成功接收訊息并且ack長度大于原來所記載的長度，
   2.1 如果是，那么更新sentLength和ackLength，并且執行Commitlogentries，
   2.2 success為false，表明sentLength需要進行修正，然后重新執行Replicatelog，

logOk不為true，可能是因為prefixLen >= log.length，也可能是因為prefixTerm != log[prefixLen-1].term，

leader提交log，Commitlogentries

leader遍歷所有的log，將有超過半數以上被接收的entry，認為是已經ready的log，
找到最大下標的log，如果term與當前一直，意味著已經可以被認為commit的log長度增加了，并且這些訊息已經被過半節點存盤，可以發送給應用了，

總結：

1. 每一個節點在收到比自己高的term時，會變成follower，
2. leader復制到其他節點時，發送LogRequest，其他節點回傳LogResponse，用來標識是否已經成功復制，
3. leader根據是否有過半的成功LogResponse來判斷訊息是否能夠最終commit

標籤：其他

上一篇：Linux運維實戰：Centos7.6部署wingftpserver

下一篇：如何在Solidity中建立DAO（去中心化自治組織）？