在分布式的世界裡，要說最核心最複雜的功能，一緻性地實現無出其右，之前的Paxos算法堪稱經典，被認為是同類算法中效果最好的，基本上成為分布式一緻性的代名詞，但是paxos算法也是出了名的難理解，而且相當不好實現。本人也花了很多時間、看了很多材料也沒有真正理解。所以基于paxos的思想進行的一緻性算法的簡化和實現就成為了現實的需求，在此背景下，本文的主角raft就出現了。

Raft算法的頭号目标就是容易理解（UnderStandable），這從論文中就可以看出來。當然，Raft增強了可理解性，在性能、可靠性、可用性方面是不輸于Paxos的。建議大家拜讀下作者的論文 Raft論文，下面将詳細說明raft的思想以及實現的過程

raft為了實現容易理解的目标，在paxos的基礎上進行的狀态簡化以及問題拆分，将之前複雜的邏輯拆成若幹個子問題，基本上可以總結成下面幾個方面：

• leader election：選取主節點
• log replication：日志備份，數據同步
• safety：為了實現上述兩點而産生的一些約束條件和保障條件

首先先說明下Raft算法中節點的角色，分為以下三種：

• leader：由所有節點選舉，在candidate中産生，負責整個集群的狀态以及元數據管理，當發現更大的term時，轉化為follower
• candidate：由follower在集群選舉時轉化而成，選舉時得到多數選票，則轉化為leader，若發現主節點或者更大的term則轉化為follower
• follower：集群初始化時所有節點的角色都是follower，若未發現leader心跳，則發起leader選舉，并将角色轉化為candidate；leader以及candidate在某些條件下也會轉化成follower

給出狀态機，協助大家理解：

上面在講解role的時候好幾次說到了一個名詞term，這是raft算法中的一個核心概念，很多的機制都需要依賴term。term通俗來講就是任期，即一個leader正常工作的時間段，如果因為某些原因當前的leader不再是leader時，則該term結束，重新進行選舉，開始新的任期，是不是和現實生活中的選舉很像？

另外term在raft算法中也起到了邏輯時鐘的作用，在raft的實現中起到了重要的作用，此處用一句話先來概括：即term大的優先級高，leader必須是擁有更大的term。用白話理解：就是當前總統和前總統的關系，總統隻能有一個就是當期總統，前總統在當前總統面前就變成選民了。在Raft中，term是個整數型的值，term變化即将term的值加1

下面就來說說leader選舉的詳細過程，從上面的狀态機可以看出，集群初始化時，大家都是follower，當未發現leader心跳并超時後，則follower變成candidate，并發起leader election。每個candidate的動作如下：

1. 給自己投一票
2. 向其他節點發起RequestVote RPC來進行拉票
3. 等待其他節點的響應

在此過程中會出現三種情況：

• 該candidate收到了多數（majority）的選票當選了leader，并發送leader心跳告知其他節點，其他節點全部變成follower，集群選主成功
• 該candidate收到了其他節點發來的leader心跳，說明主節點已經選舉成功，該candidate變成follower，集群選主成功
• 一段時間内（election timeout），該candidate未收到超過半數的選票，也未收到leader心跳，則說明該輪選主失敗，重複進行leader election，直到選主成功

上述情況的産生需要滿足下面幾個約束：

• 在每個任期中每個人隻能投出一票：注意是每個任期，任期變了（準确的說法是任期增加了）就可以重新投票
• 投票的規則：candidate肯定投給自己，follower是先到先得
• 當選leader的條件是得到多數（N/2 1）選票：此處的多數選票是為了避免腦裂而出現多leader的情況而進行的約束，保證了整個集群中leader的唯一性
• leader的消息是最新的（其實就是term最大，index也是最大的，後面的log replication模塊進行詳細分析）

上面的前兩種情況比較容易理解，我們重點來說說第三中情況，用一個比較形象的例子來說明選舉過程：

有五個小夥伴要選取一個組長，選舉過程如下：

注：F,C,L分别對應的是follower，candidate和leader角色，在本例中就是組員，候選人和組長；名字是用來區分節點的标識；而括号中的數字則代表着term的值

1. 初始狀态大家都是組員，等待組長聯系自己
2. 等待一段時間後（leader heartbeat timeout），昌坦，繼東和呈祥發現沒有組長或者組長掉線了，這三個人就變成了候選人，然後發起了組長選舉的流程
3. 選舉開始後，三個候選人都将自己的任期加1變成了2，然後投了自己一票，而組員曉通選了昌坦，組員溪澤選了呈祥，三個候選人的票數比是2：1：2，未能達到法定的半數以上的多數票，未能選出組長
4. 漫長的等待後（election timeout），昌坦發現自己沒有獲得多數選票，也沒有收到其他候選人當選組長的消息（leader heartbeat），意識到了此次選舉失敗，然後将自己的任期加1變成3，再次發起選舉，組員曉通和溪澤發現該任期中未投票 ，先到先得，直接投給了昌坦，而候選人繼東和呈祥發現昌坦的任期比自己大，則放棄候選人的角色變成了組員并投票給昌坦（此處從候選人變成組員也可能是收到了昌坦當選組長的消息後轉變的，因為組長的當選并不需要全票，隻要達到多數選票即可）
5. 昌坦全票當選組長，并向其他組員通報了自己成為組長的消息，後續所有的組内管理以及消息同步都通過組長昌坦向其他組員傳達

整個leader election流程就是這樣，是不是很好理解，基本上符合現實生活中的理解。但是上述的流程可能有一個問題，分為以下兩種情況：

• 如果在第三階段三個候選人同時發現選舉未成功，同時發起二次選舉，而恰好昌坦和曉通的關系很好，呈祥和溪澤的關系很好（關系好可以理解為網絡近，優先到達，優先獲得投票），則可能出現多次2：1：2，無法達到多數（majority）的情況
• 如果當前的組員不是5個人，而是4個人或者6個人，而候選人是2個，則會出現2：2或者3：3的情況，無法達到多數（majority）的情況

上述的兩種情況會影響到leader election的成功率和效率，在設計中應該被規避，面對這兩種情況，Raft給出了自己的解決方案：

• 節點數盡量是奇數個，盡量保證majority的産生
• 每個candidate的election timeout時間在某一個時間段内随機，如150ms-300ms,這樣能最大程度上避免同時再次發起選舉的概率，某個candidate可以率先發現election timeout然後增加term并重新發起選舉，大概率能獲得多數選票而當選，另外每一次選舉每個candidate都會刷新election timeout，來保證majority的産生

當系統有了leader後，系統就進入對外工作期了。客戶端的一切請求來發送到leader，leader來調度這些并發請求的順序，并且保證leader與followers狀态的一緻性。raft中的做法是，将這些請求以及執行順序告知followers。leader和followers以相同的順序來執行這些請求，保證狀态一緻。

下圖就是請求寫入處理的相關流程：

1. 客戶端向leader提交寫入請求
2. leader接收到客戶端請求後封裝RPC并行将修改發送到follower
3. follower在接收到leader發送的RPC後，回複leader已經收到該請求
4. 在leader接收到多數（majority，含leader）follower的回複後，回複客戶端接收成功，将變更狀态設置為commited，然後将變更寫入到狀态機，此時寫入實際上已經生效，無法回滾
5. leader與follower通信，協助follower完成變更的提交，當變更提交完畢後，follower會将變更寫入到狀态機，此時變更才真正的影響到節點，此時的狀态可以理解為applied。此過程中，可能會出現各種問題，比如說網絡連接超時，命令執行不成功等問題，leader會持續和follower進行通信，保證follower最終完成所有的操作，與leader達成最終一緻性。這種最終一緻性是對内的，對外部的client的透明的，外部的client隻會看到leader上狀态的強一緻性。這種強一緻性和最終一緻性的配合使用，不僅降低了一緻性實現的各種成本，還保證了系統的健壯性，能保證在各種異常情況下的恢複與狀态同步。

上述流程中，有點類似于兩階段提交（2PC），這種提交方式的好處就是能簡化分布式事務的複雜性，在不直接使用分布式鎖的前提下，能最大程度保證分布式事務的實現。但是這裡和标準的2PC還是有差别的，差别就是這裡leader隻需要多數（majority）的follower答複即可，那麼在這種情況下，raft是怎麼保證一緻性以及數據的完整性，尤其在集群主節點發生故障的時候呢？此處先留下這個問題，後續在safety模塊進行解答

最後看下log長什麼樣子吧：

log由三部分組成：

• 序号：代表着命令的執行順序，leader将命令按順序發給follower，follower按順序執行命令，保證數據的一緻性
• term值：将命令按term進行劃分，每個命令都屬于一個term
• 操作命令：真正執行和影響節點狀态的命令

log為了配合raft實現leader選舉以及狀态同步，需要具備某些特性 ，滿足相關的約束：

• 回到上文的問題，leader選舉的時候要保證leader上的log是最新的，那最新的概念是什麼？這裡解答下：log最新的概念就是term是最大的且index也是最大的，如圖中的leader，term是4，index是7，都是最大的
• 從初始狀态為空開始，leader将客戶端請求（command）封裝到一個個log entry，将這些log entries複制（replicate）到所有follower節點，然後大家按相同順序應用（apply）log entry中的command，則狀态肯定是一緻的。
• log是append only的file，對于已經committed的命令，log隻會新增，不會修改和删除，這也帶來了另外一個特性，就是如果兩個不同節點在同一位置的日志相同，那麼在此位置之前的所有的值都相同
• 隻有leader的發送的log entry被多數（majority）的節點（包含leader）接收并響應，才會被标識為committed

上面大部分說的都是正常情況下raft是怎麼工作和運行的，但是一個分布式不僅需要在正常情況下能穩定高效的運行，也需要在任何情況下，系統都不能出現不可逆的錯誤，也不能向客戶端返回錯誤的内容。raft也是如此，上面兩個章節已經說明了為了達到safety目标raft所采取的一些策略和約束，下面就來以幾個典型場景來說明下raft是怎樣容錯的。

follower crash處理起來相對簡單，隻要重新上線加入集群後 ，發現了已經存在的leader，直接加入集群并且接收來自leader的消息，然後在leader的指導下完成數據和狀态的同步，在此過程中，leader與follower通信使用的是AppendEntries RPC，借用官方的結構圖：

另外，每個節點上的日志都是通過狀态機（State Machine）進行管理的，節點上applied的command會提交到狀态機進行保存，用于後續節點（leader-follower）之間進行數據和狀态同步，下面是狀态機中狀态相關的結構圖：

從上圖可以看出對于每個follower，leader保持2個屬性，一個就是nextIndex即leader要發給該follower的下一個entry的index，另一個就是matchIndex即follower發給leader的确認index。

實現過程如下：

leader當選成功後，會進行部分屬性的初始化：

nextIndex=leader的log的最大index 1 matchIndex=0

然後開始準備AppendEntries RPC請求的參數：

prevLogIndex=nextIndex-1 prevLogTerm=從log中得到prevLogIndex對應的term

初始化entries數組：

初始化以及成功當選的第一次心跳的時候是空 後續的值是從本地log中取prevLogIndex 1到最後的所有log entry

最後是leaderCommit賦值：

leaderCommit=leader上的commit indexentry

至此，所有參數準備完畢，發送RPC請求到所有的follower,follower再接收到這樣的請求之後，處理如下：

• 重置HeartbeatTimeout
• 檢查傳過來的請求term和當前follower的term，如果當前term大于master的term，則返回false
• 檢查prevLogIndex和prevLogTerm和當前follower的對應index的log是否一緻。檢查的方法就是follower在prevLogIndex這裡是不是有entry，如果有的話，term的值和prevLogTerm是否一緻。這裡可能就是不一緻的，因為初始prevLogIndex和prevLogTerm是leader上log的lastLog，因為網絡等原因，可能還未同步到這個index，如果不一緻的話返回false，同時将該follower上log的lastIndex傳送給leader
• leader接收到上述false之後，會記錄該follower的上述lastIndex

nextIndex=follower傳回來的index 1 matchIndex=follower傳回來的index

• 然後leader會從新按照上述規則，發送新的prevLogIndex、prevLogTerm、和entries數組

nextIndex=follower傳回來的index 1 matchIndex=follower傳回來的index prevLogIndex=follower傳回來的index prevLogTerm=從log中得到上述prevLogIndex對應的term entry[]=從本地log中取prevLogIndex 1到最後的所有log entry leaderCommit=leader上的commit index

• follower檢查prevLogIndex和prevLogTerm和對應index的log是否一緻（目前一緻了）
• 然後follower就開始将entries中的數據全部覆蓋到本地對應的index上，如果沒有則算是添加如果有則算是更新，也就是說和leader的保持一緻
• 最後follower将最後複制的index發給leader,同時返回ok，leader會像上述一樣來更新follower的macthIndex

leader crash相對來說比較複雜，需要針對幾個固定場景進行具體分析，詳細參考這篇文章： Leader節點的一緻性保障

在集群出現異常重新選取leader後都需要面臨數據同步的問題，下面這張圖列舉了集中場景：

上面列舉了6鐘follower可能存在的狀态，前兩種follower的數據比leader少，中間兩種follower數據比leader多，最後兩種leader和follower數據有多有少。這裡需要注意一下：

圖中的虛線框代表着uncommitted的log entry；

另外，此時leader的term是8（如果這7個節點是一個集群的話），後續分析中這一點很重要。

具體分析下上述幾種場景中follower狀态産生的原因：

• 第一種情況比較常見，follower和leader在同一term，就少一個index，這是client剛将數據寫入到leader，leader正常将該數據同步到follower即可
• 第二種情況是follower在term 4就crash或者網絡中斷了，在term 6重新恢複，此時leader隻要通過AppendEntries RPC正常同步即可。
• 第三種情況産生的原因是該follower在term 6的時候是leader，在寫入第三個值的時候，還沒來得及同步給follower，自己就crash或者網絡中斷了，所以最後一個log entry處于uncommitted的狀态
• 第四種情況産生的原因是該follower在term 7的時候是leader，剛當選leader并通知其他follower後就網絡中斷了，自己處于一個局域網中，在client端寫入兩個值後，無法同步給follower，所以最後兩個log entry處于uncommitted的狀态
• 第五種情況産生的原因是該follower在term 4的時候是leader，剛當選leader并通知其他follower後，寫入了兩個值同步給follower并commit後就網絡中斷了，自己處于一個局域網中，在client端繼續寫入兩個值後，無法同步給follower，所以最後兩個log entry處于uncommitted的狀态
• 第六種情況産生的原因是該follower在term 2的時候是leader，剛當選leader并通知其他follower後就網絡中斷了，自己處于一個局域網中，在client端寫入三個值後，無法同步給follower，所以term 2的三個log entry處于uncommitted的狀态；此時網絡突然恢複，進入了term 3，在該term中，該follower參加leader選舉又被選為leader，剛當選leader并通知其他follower後就網絡中斷了，自己處于一個局域網中，在client端寫入三個值後，無法同步給follower，所以term 3的三個log entry處于uncommitted的狀态

上面的幾種情況雖然不太具備現實意義，但是還是對于我們理解整個raft的各種機制有很大的幫助，建議大家好好梳理下，肯定會有收獲的。

針對上面的所有情況，處理方式就就是，leader選舉時所有的uncommitted的log entry都會回滾（所以圖中所有的uncommitted的log entry其實在term 8 leader選舉後就不存在了，此處畫出來僅僅是為了方便大家理解整個數據和狀态的演變過程），然後當出現了leader與follower不一緻的情況，leader強制follower複制自己的log，複制的過程參加follower crash這一章節

這個問題其實是由上面的幾個majority以及幾個約束共同來完成的：

• commit majority：一條消息隻有變成committed狀态才被認為已經提交成功，而committed狀态的前提是該消息已經同步到了majority的節點
• vote majority：某個candidate當選leader的條件就是該candidate獲得到了majori節點的選票

• leader當選的條件是log是最新的

綜上，commit majority代表着最新數據的持有；而vote majority代表着最後的leader會從這裡面産生（candidate肯定會投自己的票，所以也在vote majority之中），而這兩個majority肯定會有1到(N/2 1)個節點是重複的，也就是這些節點既有最新的數據，也有機會成為leader，再看那個約束條件，這個約束條件将vote majority中不具有最新數據的那些節點排除，那麼最後的leader節點一定會在兩個majority重複的節點中産生，而這些節點持有最新的數據，保證了leader的數據永遠是最新的且不會丢數據。

raft與其他協議（Viewstamped Replication、mongodb）不同，raft始終保證leader包含最新的已提交的日志，因此leader不會從follower catchup日志，這也大大簡化了系統的複雜度。

raft将一緻性問題分解成兩個相對獨立的問題，leader election，log replication。流程是先選舉出leader，然後leader負責複制、提交log（log中包含command），為了在任何異常情況下系統不出錯，即滿足safety屬性，對leader election，log replication兩個子問題有諸多約束，在滿足功能和性能的基礎上，盡量簡化模型以及狀态，提高了整個算法的易理解性和易實現性，堪稱經典且實用的算法。

想想 Paxos 算法是 Leslie Lamport 在 1990 年就公開發表在了自己的網站上，想想我們是什麼時候才聽說的？什麼時候才有一個可用的實現？而 Raft 算法是 2013 年發表的，現在可以看到有許多不同語言開源的實現庫了。而且很多raft-like算法在raft的基礎上進行了定制化擴展，用以滿足各種系統需求（如elasticsearch 7中的集群協調子系統中定制化raft的實現），這就是易理解性和易實現性的重要性。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!