在分布式的世界裡，要說最核心最複雜的功能，一緻性地實現無出其右，之前的Paxos算法堪稱經典，被認為是同類算法中效果最好的，基本上成為分布式一緻性的代名詞，但是paxos算法也是出了名的難理解，而且相當不好實現。本人也花了很多時間、看了很多材料也沒有真正理解。所以基于paxos的思想進行的一緻性算法的簡化和實現就成為了現實的需求，在此背景下，本文的主角raft就出現了。
Raft算法的頭号目标就是容易理解（UnderStandable），這從論文中就可以看出來。當然，Raft增強了可理解性，在性能、可靠性、可用性方面是不輸于Paxos的。建議大家拜讀下作者的論文 Raft論文，下面将詳細說明raft的思想以及實現的過程
正文raft為了實現容易理解的目标，在paxos的基礎上進行的狀态簡化以及問題拆分，将之前複雜的邏輯拆成若幹個子問題，基本上可以總結成下面幾個方面：
首先先說明下Raft算法中節點的角色，分為以下三種：
給出狀态機，協助大家理解：
上面在講解role的時候好幾次說到了一個名詞term，這是raft算法中的一個核心概念，很多的機制都需要依賴term。term通俗來講就是任期，即一個leader正常工作的時間段，如果因為某些原因當前的leader不再是leader時，則該term結束，重新進行選舉，開始新的任期，是不是和現實生活中的選舉很像？
另外term在raft算法中也起到了邏輯時鐘的作用，在raft的實現中起到了重要的作用，此處用一句話先來概括：即term大的優先級高，leader必須是擁有更大的term。用白話理解：就是當前總統和前總統的關系，總統隻能有一個就是當期總統，前總統在當前總統面前就變成選民了。在Raft中，term是個整數型的值，term變化即将term的值加1
leader election process下面就來說說leader選舉的詳細過程，從上面的狀态機可以看出，集群初始化時，大家都是follower，當未發現leader心跳并超時後，則follower變成candidate，并發起leader election。每個candidate的動作如下：
在此過程中會出現三種情況：
上述情況的産生需要滿足下面幾個約束：
上面的前兩種情況比較容易理解，我們重點來說說第三中情況，用一個比較形象的例子來說明選舉過程：
有五個小夥伴要選取一個組長，選舉過程如下：
注：F,C,L分别對應的是follower，candidate和leader角色，在本例中就是組員，候選人和組長；名字是用來區分節點的标識；而括号中的數字則代表着term的值
整個leader election流程就是這樣，是不是很好理解，基本上符合現實生活中的理解。但是上述的流程可能有一個問題，分為以下兩種情況：
上述的兩種情況會影響到leader election的成功率和效率，在設計中應該被規避，面對這兩種情況，Raft給出了自己的解決方案：
當系統有了leader後，系統就進入對外工作期了。客戶端的一切請求來發送到leader，leader來調度這些并發請求的順序，并且保證leader與followers狀态的一緻性。raft中的做法是，将這些請求以及執行順序告知followers。leader和followers以相同的順序來執行這些請求，保證狀态一緻。
下圖就是請求寫入處理的相關流程：
上述流程中，有點類似于兩階段提交（2PC），這種提交方式的好處就是能簡化分布式事務的複雜性，在不直接使用分布式鎖的前提下，能最大程度保證分布式事務的實現。但是這裡和标準的2PC還是有差别的，差别就是這裡leader隻需要多數（majority）的follower答複即可，那麼在這種情況下，raft是怎麼保證一緻性以及數據的完整性，尤其在集群主節點發生故障的時候呢？此處先留下這個問題，後續在safety模塊進行解答
最後看下log長什麼樣子吧：
log由三部分組成：
log為了配合raft實現leader選舉以及狀态同步，需要具備某些特性 ，滿足相關的約束：
上面大部分說的都是正常情況下raft是怎麼工作和運行的，但是一個分布式不僅需要在正常情況下能穩定高效的運行，也需要在任何情況下，系統都不能出現不可逆的錯誤，也不能向客戶端返回錯誤的内容。raft也是如此，上面兩個章節已經說明了為了達到safety目标raft所采取的一些策略和約束，下面就來以幾個典型場景來說明下raft是怎樣容錯的。
follower crashfollower 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再接收到這樣的請求之後，處理如下：
nextIndex=follower傳回來的index 1
matchIndex=follower傳回來的index
nextIndex=follower傳回來的index 1
matchIndex=follower傳回來的index
prevLogIndex=follower傳回來的index
prevLogTerm=從log中得到上述prevLogIndex對應的term
entry[]=從本地log中取prevLogIndex 1到最後的所有log entry
leaderCommit=leader上的commit index
leader crash相對來說比較複雜，需要針對幾個固定場景進行具體分析，詳細參考這篇文章： Leader節點的一緻性保障
leader與follower同步數據在集群出現異常重新選取leader後都需要面臨數據同步的問題，下面這張圖列舉了集中場景：
上面列舉了6鐘follower可能存在的狀态，前兩種follower的數據比leader少，中間兩種follower數據比leader多，最後兩種leader和follower數據有多有少。這裡需要注意一下：
圖中的虛線框代表着uncommitted的log entry；
另外，此時leader的term是8（如果這7個節點是一個集群的話），後續分析中這一點很重要。
具體分析下上述幾種場景中follower狀态産生的原因：
上面的幾種情況雖然不太具備現實意義，但是還是對于我們理解整個raft的各種機制有很大的幫助，建議大家好好梳理下，肯定會有收獲的。
針對上面的所有情況，處理方式就就是，leader選舉時所有的uncommitted的log entry都會回滾（所以圖中所有的uncommitted的log entry其實在term 8 leader選舉後就不存在了，此處畫出來僅僅是為了方便大家理解整個數據和狀态的演變過程），然後當出現了leader與follower不一緻的情況，leader強制follower複制自己的log，複制的過程參加follower crash這一章節
raft算法如何保證leader的數據永遠是最新的且不會丢數據這個問題其實是由上面的幾個majority以及幾個約束共同來完成的：
majority綜上，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每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
