Raft算法详细介绍
raft是一個共識算法（consensus algorithm），所謂共識，就是多個節點對某個事情達成一致的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。這些年最為火熱的加密貨幣（比特幣、區塊鏈）就需要共識算法，而在分布式系統中，共識算法更多用于提高系統的容錯性，比如分布式存儲中的復制集（replication），在帶著問題學習分布式系統之中心化復制集一文中介紹了中心化復制集的相關知識。raft協議就是一種leader-based的共識算法，與之相應的是leaderless的共識算法。
??本文基于論文In Search of an Understandable Consensus Algorithm對raft協議進行分析，當然，還是建議讀者直接看論文。
??本文地址：https://www.cnblogs.com/xybaby/p/10124083.html
raft算法概覽
??Raft算法的頭號目標就是容易理解（UnderStandable），這從論文的標題就可以看出來。當然，Raft增強了可理解性，在性能、可靠性、可用性方面是不輸于Paxos的。
Raft more understandable than Paxos and also provides a better foundation for building practical systems
?? 為了達到易于理解的目標，raft做了很多努力，其中最主要是兩件事情：
- 問題分解
- 狀態簡化
?? 問題分解是將"復制集中節點一致性"這個復雜的問題劃分為數個可以被獨立解釋、理解、解決的子問題。在raft，子問題包括，leader election，?log replication，safety，membership changes。而狀態簡化更好理解，就是對算法做出一些限制，減少需要考慮的狀態數，使得算法更加清晰，更少的不確定性（比如，保證新選舉出來的leader會包含所有commited log entry）
Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected.
?? 上面的引文對raft協議的工作原理進行了高度的概括：raft會先選舉出leader，leader完全負責replicated log的管理。leader負責接受所有客戶端更新請求，然后復制到follower節點，并在“安全”的時候執行這些請求。如果leader故障，followes會重新選舉出新的leader。
?? 這就涉及到raft最新的兩個子問題： leader election和log replication
leader election
?? raft協議中，一個節點任一時刻處于以下三個狀態之一：
- leader
- follower
- candidate
?? 給出狀態轉移圖能很直觀的直到這三個狀態的區別
??可以看出所有節點啟動時都是follower狀態；在一段時間內如果沒有收到來自leader的心跳，從follower切換到candidate，發起選舉；如果收到majority的造成票（含自己的一票）則切換到leader狀態；如果發現其他節點比自己更新，則主動切換到follower。
?? 總之，系統中最多只有一個leader，如果在一段時間里發現沒有leader，則大家通過選舉-投票選出leader。leader會不停的給follower發心跳消息，表明自己的存活狀態。如果leader故障，那么follower會轉換成candidate，重新選出leader。
term
?? 從上面可以看出，哪個節點做leader是大家投票選舉出來的，每個leader工作一段時間，然后選出新的leader繼續負責。這根民主社會的選舉很像，每一屆新的履職期稱之為一屆任期，在raft協議中，也是這樣的，對應的術語叫term。
?? term（任期）以選舉（election）開始，然后就是一段或長或短的穩定工作期（normal Operation）。從上圖可以看到，任期是遞增的，這就充當了邏輯時鐘的作用；另外，term 3展示了一種情況，就是說沒有選舉出leader就結束了，然后會發起新的選舉，后面會解釋這種split vote的情況。
選舉過程詳解
?? 上面已經說過，如果follower在election timeout內沒有收到來自leader的心跳，（也許此時還沒有選出leader，大家都在等；也許leader掛了；也許只是leader與該follower之間網絡故障），則會主動發起選舉。步驟如下：
- 增加節點本地的?current term?，切換到candidate狀態
- 投自己一票
- 并行給其他節點發送?RequestVote RPCs
- 等待其他節點的回復
?? 在這個過程中，根據來自其他節點的消息，可能出現三種結果
?? 第一種情況，贏得了選舉之后，新的leader會立刻給所有節點發消息，廣而告之，避免其余節點觸發新的選舉。在這里，先回到投票者的視角，投票者如何決定是否給一個選舉請求投票呢，有以下約束：
- 在任一任期內，單個節點最多只能投一票
- 候選人知道的信息不能比自己的少（這一部分，后面介紹log replication和safety的時候會詳細介紹）
- first-come-first-served 先來先得
?? 第二種情況，比如有三個節點A B C。A B同時發起選舉，而A的選舉消息先到達C，C給A投了一票，當B的消息到達C時，已經不能滿足上面提到的第一個約束，即C不會給B投票，而A和B顯然都不會給對方投票。A勝出之后，會給B,C發心跳消息，節點B發現節點A的term不低于自己的term，知道有已經有Leader了，于是轉換成follower。
?? 第三種情況，沒有任何節點獲得majority投票，比如下圖這種情況：
?? 總共有四個節點，Node C、Node D同時成為了candidate，進入了term 4，但Node A投了NodeD一票，NodeB投了Node C一票，這就出現了平票 split vote的情況。這個時候大家都在等啊等，直到超時后重新發起選舉。如果出現平票的情況，那么就延長了系統不可用的時間（沒有leader是不能處理客戶端寫請求的），因此raft引入了randomized election timeouts來盡量避免平票情況。同時，leader-based 共識算法中，節點的數目都是奇數個，盡量保證majority的出現。
log replication
?? 當有了leader，系統應該進入對外工作期了。客戶端的一切請求來發送到leader，leader來調度這些并發請求的順序，并且保證leader與followers狀態的一致性。raft中的做法是，將這些請求以及執行順序告知followers。leader和followers以相同的順序來執行這些請求，保證狀態一致。
Replicated state machines
?? 共識算法的實現一般是基于復制狀態機（Replicated state machines），何為復制狀態機：
If two identical,?deterministic?processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.
?? 簡單來說：相同的初識狀態 + 相同的輸入 = 相同的結束狀態。引文中有一個很重要的詞deterministic，就是說不同節點要以相同且確定性的函數來處理輸入，而不要引入一下不確定的值，比如本地時間等。如何保證所有節點?get the same inputs in the same order，使用replicated log是一個很不錯的注意，log具有持久化、保序的特點，是大多數分布式系統的基石。
??因此，可以這么說，在raft中，leader將客戶端請求（command）封裝到一個個log entry，將這些log entries復制（replicate）到所有follower節點，然后大家按相同順序應用（apply）log entry中的command，則狀態肯定是一致的。
??下圖形象展示了這種log-based replicated state machine
請求完整流程
??當系統（leader）收到一個來自客戶端的寫請求，到返回給客戶端，整個過程從leader的視角來看會經歷以下步驟：
- leader append log entry
- leader issue AppendEntries RPC in parallel
- leader wait for majority response
- leader apply entry to state machine
- leader reply to client
- leader notify follower apply log
??可以看到日志的提交過程有點類似兩階段提交(2PC)，不過與2PC的區別在于，leader只需要大多數（majority）節點的回復即可，這樣只要超過一半節點處于工作狀態則系統就是可用的。
??那么日志在每個節點上是什么樣子的呢
??不難看到，logs由順序編號的log entry組成 ，每個log entry除了包含command，還包含產生該log entry時的leader term。從上圖可以看到，五個節點的日志并不完全一致，raft算法為了保證高可用，并不是強一致性，而是最終一致性，leader會不斷嘗試給follower發log entries，直到所有節點的log entries都相同。
??在上面的流程中，leader只需要日志被復制到大多數節點即可向客戶端返回，一旦向客戶端返回成功消息，那么系統就必須保證log（其實是log所包含的command）在任何異常的情況下都不會發生回滾。這里有兩個詞：commit（committed），apply(applied)，前者是指日志被復制到了大多數節點后日志的狀態；而后者則是節點將日志應用到狀態機，真正影響到節點狀態。
The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers
safety
??在上面提到只要日志被復制到majority節點，就能保證不會被回滾，即使在各種異常情況下，這根leader election提到的選舉約束有關。在這一部分，主要討論raft協議在各種各樣的異常情況下如何工作的。
??衡量一個分布式算法，有許多屬性，如
- safety：nothing bad happens,
- liveness： something good eventually happens.
??在任何系統模型下，都需要滿足safety屬性，即在任何情況下，系統都不能出現不可逆的錯誤，也不能向客戶端返回錯誤的內容。比如，raft保證被復制到大多數節點的日志不會被回滾，那么就是safety屬性。而raft最終會讓所有節點狀態一致，這屬于liveness屬性。
??raft協議會保證以下屬性
Election safety
??選舉安全性，即任一任期內最多一個leader被選出。這一點非常重要，在一個復制集中任何時刻只能有一個leader。系統中同時有多余一個leader，被稱之為腦裂（brain split），這是非常嚴重的問題，會導致數據的覆蓋丟失。在raft中，兩點保證了這個屬性：
- 一個節點某一任期內最多只能投一票；
- 只有獲得majority投票的節點才會成為leader。
??因此，某一任期內一定只有一個leader。
log matching
??很有意思，log匹配特性， 就是說如果兩個節點上的某個log entry的log index相同且term相同，那么在該index之前的所有log entry應該都是相同的。如何做到的？依賴于以下兩點
- If two entries in different logs have the same index and term, then they store the same command.
- If two entries in different logs have the same index and term, then the logs are identical in all preceding entries.
??首先，leader在某一term的任一位置只會創建一個log entry，且log entry是append-only。其次，consistency check。leader在AppendEntries中包含最新log entry之前的一個log 的term和index，如果follower在對應的term index找不到日志，那么就會告知leader不一致。
??在沒有異常的情況下，log matching是很容易滿足的，但如果出現了node crash，情況就會變得負責。比如下圖
??注意：上圖的a-f不是6個follower，而是某個follower可能存在的六個狀態
??leader、follower都可能crash，那么follower維護的日志與leader相比可能出現以下情況
- 比leader日志少，如上圖中的ab
- 比leader日志多，如上圖中的cd
- 某些位置比leader多，某些日志比leader少，如ef（多少是針對某一任期而言）
??當出現了leader與follower不一致的情況，leader強制follower復制自己的log
To bring a follower’s log into consistency with its own, the leader must find the latest log entry where the two logs agree, delete any entries in the follower’s log after that point, and send the follower all of the leader’s entries after that point.
??leader會維護一個nextIndex[]數組，記錄了leader可以發送每一個follower的log index，初始化為eader最后一個log index加1， 前面也提到，leader選舉成功之后會立即給所有follower發送AppendEntries RPC（不包含任何log entry， 也充當心跳消息）,那么流程總結為：
s1 leader 初始化nextIndex[x]為 leader最后一個log index + 1
s2 AppendEntries里prevLogTerm prevLogIndex來自 logs[nextIndex[x] - 1]
s3 如果follower判斷prevLogIndex位置的log term不等于prevLogTerm，那么返回 False，否則返回True
s4 leader收到follower的回復，如果返回值是False，則nextIndex[x] -= 1, 跳轉到s2. 否則
s5 同步nextIndex[x]后的所有log entries
leader completeness vs elcetion restriction
??leader完整性：如果一個log entry在某個任期被提交（committed），那么這條日志一定會出現在所有更高term的leader的日志里面。這個跟leader election、log replication都有關。
- 一個日志被復制到majority節點才算committed
- 一個節點得到majority的投票才能成為leader，而節點A給節點B投票的其中一個前提是，B的日志不能比A的日志舊。下面的引文指處了如何判斷日志的新舊
voter denies its vote if its own log is more up-to-date than that of the candidate.
If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.
??上面兩點都提到了majority：commit majority and vote majority，根據Quorum，這兩個majority一定是有重合的，因此被選舉出的leader一定包含了最新的committed的日志。
??raft與其他協議（Viewstamped Replication、mongodb）不同，raft始終保證leade包含最新的已提交的日志，因此leader不會從follower catchup日志，這也大大簡化了系統的復雜度。
corner case
stale leader
??raft保證Election safety，即一個任期內最多只有一個leader，但在網絡分割（network partition）的情況下，可能會出現兩個leader，但兩個leader所處的任期是不同的。如下圖所示
??系統有5個節點ABCDE組成，在term1，Node B是leader，但Node A、B和Node C、D、E之間出現了網絡分割，因此Node C、D、E無法收到來自leader（Node B）的消息，在election time之后，Node C、D、E會分期選舉，由于滿足majority條件，Node E成為了term 2的leader。因此，在系統中貌似出現了兩個leader：term 1的Node B， term 2的Node E, Node B的term更舊，但由于無法與Majority節點通信，NodeB仍然會認為自己是leader。
??在這樣的情況下，我們來考慮讀寫。
??首先，如果客戶端將請求發送到了NodeB，NodeB無法將log entry 復制到majority節點，因此不會告訴客戶端寫入成功，這就不會有問題。
??對于讀請求，stale leader可能返回stale data，比如在read-after-write的一致性要求下，客戶端寫入到了term2任期的leader Node E，但讀請求發送到了Node B。如果要保證不返回stale data，leader需要check自己是否過時了，辦法就是與大多數節點通信一次，這個可能會出現效率問題。另一種方式是使用lease，但這就會依賴物理時鐘。
??從raft的論文中可以看到，leader轉換成follower的條件是收到來自更高term的消息，如果網絡分割一直持續，那么stale leader就會一直存在。而在raft的一些實現或者raft-like協議中，leader如果收不到majority節點的消息，那么可以自己step down，自行轉換到follower狀態。
State Machine Safety
??前面在介紹safety的時候有一條屬性沒有詳細介紹，那就是State Machine Safety：
State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
??如果節點將某一位置的log entry應用到了狀態機，那么其他節點在同一位置不能應用不同的日志。簡單點來說，所有節點在同一位置（index in log entries）應該應用同樣的日志。但是似乎有某些情況會違背這個原則：
??上圖是一個較為復雜的情況。在時刻(a), s1是leader，在term2提交的日志只賦值到了s1 s2兩個節點就crash了。在時刻（b), s5成為了term 3的leader，日志只賦值到了s5，然后crash。然后在(c)時刻，s1又成為了term 4的leader，開始賦值日志，于是把term2的日志復制到了s3，此刻，可以看出term2對應的日志已經被復制到了majority，因此是committed，可以被狀態機應用。不幸的是，接下來（d）時刻，s1又crash了，s5重新當選，然后將term3的日志復制到所有節點，這就出現了一種奇怪的現象：被復制到大多數節點（或者說可能已經應用）的日志被回滾。
??究其根本，是因為term4時的leader s1在（C）時刻提交了之前term2任期的日志。為了杜絕這種情況的發生：
Raft never commits log entries from previous terms by counting replicas.
Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.
??也就是說，某個leader選舉成功之后，不會直接提交前任leader時期的日志，而是通過提交當前任期的日志的時候“順手”把之前的日志也提交了，具體怎么實現了，在log matching部分有詳細介紹。那么問題來了，如果leader被選舉后沒有收到客戶端的請求呢，論文中有提到，在任期開始的時候發立即嘗試復制、提交一條空的log
Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term.
??因此，在上圖中，不會出現（C）時刻的情況，即term4任期的leader s1不會復制term2的日志到s3。而是如同(e)描述的情況，通過復制-提交 term4的日志順便提交term2的日志。如果term4的日志提交成功，那么term2的日志也一定提交成功，此時即使s1crash，s5也不會重新當選。
leader crash
??follower的crash處理方式相對簡單，leader只要不停的給follower發消息即可。當leader crash的時候，事情就會變得復雜。在這篇文章中，作者就給出了一個更新請求的流程圖。
??我們可以分析leader在任意時刻crash的情況，有助于理解raft算法的容錯性。
總結
??raft將共識問題分解成兩個相對獨立的問題，leader election，log replication。流程是先選舉出leader，然后leader負責復制、提交log（log中包含command）
??為了在任何異常情況下系統不出錯，即滿足safety屬性，對leader election，log replication兩個子問題有諸多約束
leader election約束：
- 同一任期內最多只能投一票，先來先得
- 選舉人必須比自己知道的更多（比較term，log index）
log replication約束：
- 一個log被復制到大多數節點，就是committed，保證不會回滾
- leader一定包含最新的committed log，因此leader只會追加日志，不會刪除覆蓋日志
- 不同節點，某個位置上日志相同，那么這個位置之前的所有日志一定是相同的
- Raft never commits log entries from previous terms by counting replicas.
??本文是在看完raft論文后自己的總結，不一定全面。個人覺得，如果只是相對raft協議有一個簡單了解，看這個動畫演示就足夠了，如果想深入了解，還是要看論文，論文中Figure 2對raft算法進行了概括。最后，還是找一個實現了raft算法的系統來看看更好。
references
https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
https://raft.github.io/
http://thesecretlivesofdata.com/raft/
本文版權歸作者xybaby（博文地址：http://www.cnblogs.com/xybaby/）所有，歡迎轉載和商用，請在文章頁面明顯位置給出原文鏈接并保留此段聲明，否則保留追究法律責任的權利，其他事項，可留言咨詢。
總結
以上是生活随笔為你收集整理的Raft算法详细介绍的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【IDEA插件】这5款IDEA插件，堪称
- 下一篇： youknowiwill用计算机数字,高