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。 ### **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發起，用于日志復制和心跳機制。 ### 參考文檔 * [尋找一種易于理解的一致性算法（擴展版）](https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md) * [一致性算法Raft詳解](http://www.solinx.co/archives/415?utm_source=tuicool&utm_medium=referral) * [Raft 為什么是更易理解的分布式一致性算法](https://www.cnblogs.com/mindwind/p/5231986.html)