分布式一致性算法Raft

　　Paxos自1990年提出以后，相當長時間內幾乎已成為分布式一致性算法的代名詞。但因其難以理解和實現，目前知名實現僅有Chubby、Zookeeper、libpaxos幾種，其中Zookeeper使用的ZAB對Paxos做了大量改進。為此，2013年斯坦福的Diego Ongaro、John Ousterhout，提出了新的更易理解和實現的一致性算法，即Raft。
?
　　Raft和Paxos均只要保證n/2+1節點正常，即可服務。相比Paxos，其優勢即為易于理解和實現。Raf將算法分解為：選擇領導者、日志復制、安全性等幾個子問題。它的流程即為：開始時在集群中選舉出Leader負責日志復制的管理，Leader接收來自客戶端的事務請求（日志），并將它們復制給集群中的其他節點，然后通知集群中的其他節點提交日志，Leader負責保證其他節點與它的日志同步。當Leader宕機時，集群其他節點重新發起選舉，選出的新的Leader。
?

角色

?
　　Raft涉及三種角色：
　　Leader：即領導者，負責處理來自客戶端的請求，管理日志復制、以及與Follower保持心跳以維持其領導者地位。
　　Follower：即追隨者，負責響應來自Leader的日志復制請求，響應來自Candidate的選舉請求。初始時所有節點均為Follower。
　　Candidate：即候選者，負責發起選舉投票，Raft啟動后或Leader宕機后，一個節點從Follower轉為Candidate，并發起選舉，選舉成功后，由Candidate轉為Leader。
?
　　如下為Raft角色狀態轉換圖：
?

?

Term（任期）

?
　　在Raft中使用了Term（任期）的概念，一輪選舉即為一個Term（任期），一個Term中僅能產生一個Leader。Term使用連續遞增的編號表示，初始時所有Follower的Term均為1。其中某個Follower定時器到期觸發選舉，其狀態轉換為Candidate，此時Term加1變為2，然后開始選舉，有如下幾種可能：
?
　　1、如果當前Term為2的任期內沒有選舉出Leader或出現異常，Term遞增為3，并開始新一輪選舉。
　　2、此輪Term為2的任期內選舉出Leader后，如果Leader宕機，此時其他Follower轉為Candidate，Term遞增，并發起新的選舉。
　　3、如果Leader或Candidate發現自己的Term比其他Follower小時，Leader或Candidate轉為Follower，Term遞增。
　　4、如果Follower發現自己的Term比其他Follower小時，更新Term與其他Follower保持一致。
?
　　每次Term遞增都將發生新一輪選舉，在Raft正常運行過程中，所有節點Term均一致。如果節點不發生故障，一個Term（任期）會一直保持下去，當某節點收到的請求中Term比當前Term小時拒絕請求。
?

選舉

?
　　初始時所有節點均為Follower，且定時器時間不同。某個節點定時器觸發選舉后，Term遞增，該節點由Follower轉換為Candidate，向其他節點發起投票請求（RequestVote RPC）。有如下幾種可能：
?
　　1、收到過半數節點（n/2+1）投票，由Candidate轉換為Leader，向其他節點發送心跳以維持領導者地位。
　　2、如果收到其他節點發送的AppendEntries RPC請求，且該節點Term大于當前節點Term，即發現了新的有效領導者，轉換為Follower，否則保持Candidate拒絕該請求。
　　3、選舉超時，Term遞增，重新發起選舉。
?
　　每輪Term期間，每個節點均只能投票1次，如果多個Candidate均沒有接收到過半數投票，則每個Candidate Term遞增，重啟定時器并重新發起選舉。因定時器時間隨機，因此不會多次出現多個Candidate同時發起投票的問題。
?

日志復制

?
　　保證節點的一致性，就要保證所有節點都按順序執行相同的操作序列，日志復制目的即為此。
?
　　1、Leader接收到客戶端事務請求（即日志），先將日志追加到本地Log中，并通過AppendEntries RPC復制給其他Follower。
　　2、Follower接收到日志后，追加到本地Log中，并向Leader發送ACK消息。
　　3、Leader收到過半數Follower的ACK消息后，將日志置為已提交并正式提交日志，通知客戶端，并發送AppendEntries RPC請求通知Follower提交日志。
?

安全性

?
　　1、每個Term期間只能選舉一個Leader。
　　2、Leader不會刪除或覆蓋已有日志條目，只會追加。
　　3、如果相同索引位置的日志條目Term任期號相同，那么認為從頭到這個索引位置均相同。
　　4、如果某個日志條目在某任期內提交，那么這個日志條目必然出現在更大的Term任期號的所有領導中。
　　5、如果Leader在某索引位置的日志條目已提交，那么其他節點相同索引位置不會提交不同的日志條目。
?

RequestVote RPC和AppendEntries RPC

?
　　Raft中節點通信使用兩種RPC，即RequestVote RPC和AppendEntries RPC：
　　RequestVote RPC：即請求投票，由Candidate在選舉期間發起。
　　AppendEntries RPC：即附加條目RPC，由Leader發起，用于日志復制和心跳機制。
?

參考文檔

?
　　尋找一種易于理解的一致性算法（擴展版）
　　一致性算法Raft詳解
　　Raft 為什么是更易理解的分布式一致性算法
?

后記

?
　　本文總結的Raft，及之前文章中的Paxos、2PC、3PC均為基于非拜占庭容錯的分布式一致性算法，即除考慮消息的丟失、超時、亂序，但不考慮消息被篡改。從下個文章起，將總結基于拜占庭容錯的分布式一致性算法，該算法在比特幣、以太坊、及其他區塊鏈產品中廣泛使用。