Raft算法

前段時間一直在學習mit的分布式課程 Distributed Systems ，仔細閱讀了raft論文，但是中間又跑去搞docker了，所以一直沒有整理raft相關的文章，今天就來總結一下。

文章中沒有多少詳細的圖片，但是大家可以邊看文章邊看 Raft演示動畫

之前介紹的Paxos算法一直都是分布式一致性協議的標準，但是Paxos難以理解，更難以理解。于是Stanford的教授提出了Raft協議，它是一個為真實世界應用建立的協議，主要注重協議的落地性和可理解性。這里有Raft的 論文 ，大家有興趣可以自行閱讀一下。

Raft是為了managing a replicated log。Raft會首先選舉一個leader,然后讓這個leader來管理replicated log。Raft將consensus問題(也就是一致性問題)劃分成三個相互獨立的子問題：

• leader election
• log replication
• safety

Raft basis

任何時間每個server都處于下列三個狀態之一：leader,follower,或在candidate之一。在正常狀態下，整個集群只會有一個leader并且其他所有server都處于followers狀態下。followers是被動的，它們只會對leader的request進行反應。第三個狀態candidate是用來選舉新的leader的。

Raft以Term來劃分運行時間，你可以將其理解為任期。Term以連續的整數來命名，每個Term都以一個election開始。在一次選舉中，一個或多個candidate試圖成為leader。如果一個candidate贏得了election,那么它就成為leader。如果一次election中沒有candidate獲勝，那么就進行下一個Term,重新進行election。每個Term最多只有一leader，否則進入下一個Term,這樣Term就可以作為一個logical clock。

Raft服務器通過RPC來交互，只需要兩個RPC操作，RequestVote RPCs and AppendEntries RPCs。RequestVote用于選舉而AppendEntries用于leader發送請求進行relicate log entries和心跳。

Leader election

Raft通過心跳機制來觸發leader selection。當一個服務器啟動時，默認位于followers狀態，并且一直持續知道它一直接受到leader的RPC請求。leader會周期性發送心跳給所有的followers。如果follower一段時間內沒有接受到心跳，那么就認為當前沒有leader應該開始leader selection。

開始election后，server將其Term進行加一，然后轉變成candidate狀態，并且給其他所有server發送RequestVote RPC請求來進行vote。這個過程一直持續到：server自己贏得election,其他的server贏得election,或者這個Term期間沒有server獲勝，進入下一個Term。

candidate收到半數以上server的vote就贏得了election。每個server在一個Term中只會vote一次。server基于first-come-and-first-serve的規則來進行投票。一旦某個candidate贏得了election, 就變成了leader,并且開始周期性發送心跳。

當等待投票時，candidate受到了其他candidate發送的AppendEntries PRC請求,如果candiate發現在包含在請求當中的Term數值大于或則等于自己的Term數值，那么該candiate主動退回到follower狀態，否在拒絕該請求，繼續保持candidate狀態。

當很多server變成candidate狀態進行election時，選舉失敗的可能性就很高了。那么每個candiate會推遲隨機時間之后進入下一個Term并進行新的election。以此來避免大量的選舉失敗的情況發生。

Log replication

一旦一個leader被選舉成功，它就開始處理client請求。每個client請求都包含一個需要被replicated state machine處理的命令，leader將這些命令當作一個新的entry添加到log中。然后給follower發送AppendEntries RPCs請求來復制這個log entry。當一個entry被safely relicated(在下一小結中會講解)，leader就會將entry交給state machine進行執行，并且將結果返回。

當一個log entry可以被安全的交給state machine處理時，我們認為它是committed的。Raft保證所有committed的log entry一定是持久化的，并且一定被state machine執行。Log entry是committed一旦該entry在大多數follower上被replicated。一旦一個entry被committed,那么在它之前的所有log也是committed的。Leader會隨時關注最大的committed的log的index,并在AppendEntries RPCs請求中攜帶該信息，這樣follower就能知道哪些entry被committed，它們就會將其提交給自己的state machine來執行。

當followers crash或則網絡丟包時，leader會一直發送AppendEntries RPCs直到所有followers都存儲了entry。

每個Log entry都有其唯一標識，entry中包括了 leader Term，index和要執行的comand。index是指entry在Log中的位置。Raft通過Log Machine Property來維護Log的合理性：

• 如果兩個entries在不同的logs中(存儲在不同的server上)擁有相同的index和term,那么他們包含相同的command。
• 如果兩個entries在不同的logs中擁有相同的index和term,那么他們之前的entries也都是一致或在內容相同的。
  第一條規定保證leader每個Term中的每個index最多只能創建一個entry。而第二條規定使得followers在處理AppendEntries RPCs請求時要進行一致性檢測。leader在AppendEntries請求中帶上了自己logs中排在新entry之前的那個entry的index和term,如果follower在自己的logs中找不到該entry,那么就拒絕添加new entry。這樣就保證了第二條規定不會被違反。
  正常情況下，leader和followers的logs都是一致的，但是當一系列的leader crash，followers crash和election之后，followers的logs可能會被當前leader的logs多出一些entry,也可能會少一些entry。在Raft中，leader通過強迫followers的logs復制leader的logs來保持一致性。這就意味著follower logs中的沖突的entry會被重寫。

為了一致化logs,leader的logs需要和follower的logs進行對比，找出它們之間最后一條相同的entry。然后將follower logs中那條entry之后的所有entry刪除，并發送leader logs中那條entry之后的entry給follower。這些行為都發生在AppendEntries RPCs的一致性檢查過程中。

leader會每個follower維護一個nextIndex來記錄發送給這個follower的下一條log entry的index。nextIndex初始化為leader logs的最后一條entry之后的index。如果follower的logs和leader的logs不一致，那么AppendEntries RPCs的一致性檢查就會失敗。leader發現自己的請求被follower拒絕了，那么就減少該follower的nextIndex然后再次發送AppendEntries請求。最終nextIndex就會變成二者log中最后一個一致的entry的index。當上述情況發生之后，AppendEntries請求就會成功，就會刪除follower中多的entry和添加缺少的entry。

Safety

這一小節主要描述在leader election過程中的一些限定。這些限定保證任何一個Term的leader的logs都包含了之前Term中所有committed的entry。這也是所謂的Leader Completeness Property。

Election限制

Raft規定：在election過程中，new leader本身必須有之前Term中所有committed的log entry。也就是說每次election成功的leader必然包含之前所有的committed的log entry。這樣保證了log的單向流動，一定是從leader到follower。

Raft通過election vote過程來保證上述限制。一個candidate必須得到集群中多于半數的server的vote，而每個committed的log entry一定也會存在于多于半數的server的logs中。也就是說在RequestVote RPC中包含了candidate自己logs中最后一個committed的log信息，接受到該請求的server會將其和自己log中最后一個committed的log進行對比，如果自己的log晚于candiate的，那么就同意該candiate成為leader,否在拒絕。這樣的話，沒有包含所有committed log entry的candidate就一定不會得到超過半數的server的vote。Raft根據entry的term和index來確定每個entry的先后順序。較大term的log entry比較新，如果log entry的term一致，那就是越大的index約新。

Committing entries from previous terms

如果舊的leader在committing an entry時crash了，那么新的leader是否需要重新commit這個entry呢？但是為了簡化，Raft重來不會提交之前Term的log entry。沒有被committed的log entry就會被重寫。

Followers and candidate crashs

如果followers或在candidate在接受到RPC之前crash，leader會一直重試發送RPC。如果是在接受處理之后crash，沒有發送回復，leader也是會重復發送RPC,但是因為RPC都是冪等的，所以不會造成額外的影響。

后記

Raft的應用十分廣泛，比如etcd項目就是使用Raft來保證分布式一致性的，之后我也想去研究一下etcd中Raft的實現，畢竟之前都是理論。

 

來自：http://remcarpediem.com/2017/07/25/Raft算法/