Raft將壹致性算法分解為* * *選舉、日誌復制和安全等幾個關鍵模塊。本文將基於raft論文簡要分析Raft算法。
Raft是強勢領袖模式，壹切由領袖主導。例如，日誌只能從領導者復制到其他服務器。所以領袖的選舉是非常重要的壹部分。
首先，介紹了raft算法的三種服務狀態:
壹個集群中任何時候都只能有壹個領導者。
Raft使用心跳機制實現領袖選舉。當服務啟動時，它處於跟隨者角色。需要註意的是，服務於領導的每個心跳的超時時間是隨機的(150-300ms)。
如上圖所示，集群中有A、B、C三個點，超時時間分別為150ms、200ms、300ms。最開始的術語編號都是0，都是跟隨者角色。節點A和leader的心跳超時時間最短，所以先從跟隨者狀態變為候選，增加任期數。首先，他們為自己投票，並將投票信息發送到集群中的其他節點。當節點B和C收到A的投票請求時，接受A的投票請求而不投票給本階段的其他節點，期限為1。此時節點A接受了集群中超過半數節點的投票，以1的任期成為盟主。
申訴是最簡單的選舉過程，有很多概念需要解釋，比如為什麽加班時間不壹樣？什麽是學期編號？投票比較的規則是什麽？
1.術語編號
每個領導人在選舉期間都有自己的任期數，在全世界都是單調遞增的數。每個節點存儲當前領導者的任期號，當處於候選階段時，發起投票時當前任期號將加1。
此外，當壹個節點接收到壹個比它自己的術語更高的請求時，它將把它的術語號更新到壹個更高的術語號。如果當前角色是領導者，它將從領導者角色變為追隨者角色。當接收到壹個項數小於自身的請求時，節點會直接拒絕該請求。
2.投票比較規則
A.先到先服務:壹個節點在壹個任期內只能投票壹次。如果節點A和B都請求節點C投票，如果節點C先投票給A，它將拒絕節點B的投票請求。
b .日誌完整性:如果壹個節點接受的投票信息的日誌小於自己的，它會拒絕投票請求。
C.壹半策略:當壹個節點收到集群中超過壹半節點的投票時，成為該任期的領導者，並向其他節點發送領導者心跳。
D.在等待投票時，候選人可能會從另壹個聲稱是領導者的服務器節點接收AppendEntries RPC。如果領導者的任期數(包含在RPC中)不小於候選人的當前任期數，則候選人將承認領導者的合法地位，並返回追隨者地位。
3.隨機超時
如上所述，每個點與領導的心跳超時時間不同。這樣做的好處是避免分票的情況，快速進行領導人選舉。如果每個節點的超時都壹樣，就很容易分票了。如果每個節點都沒有獲得過半選票，就要進行下壹輪選舉，選舉時間會很長。使用隨機超時機制，正常情況下，壹個時間段內只有壹個節點發起投票請求。
下圖是整個集群中服務角色變化的流程圖。
選舉出首領後，它為客戶端提供服務，將接收到的指令作為新的日誌條目追加到日誌中，然後並行向其他服務器發起AppendEntries RPC，使它們可以復制日誌條目。當日誌條目被安全復制後(超過壹半的節點已被復制)，領導者會將日誌條目應用到其狀態機(狀態機執行指令)，然後將執行結果返回給客戶端。如果跟隨者崩潰或者運行緩慢，或者網絡丟包，* * *會不斷重試AppendEntries RPC(即使已經回復客戶端)，直到所有跟隨者最終存儲完所有日誌。
上圖顯示了日誌的格式，壹個日誌條目包含三個部分。
領導者通過AppendEntries RPC將日誌復制到其他節點。
AppendEntries RPC:
接收器實現:
上訴是AppendeEntries RPC參數的接受過程。引入$ term和leaderId非常簡單，但是prevLogIndex和prevLogTerm的作用是檢查日誌的壹致性。如果跟隨者在其日誌中找不到具有相同索引位置和術語編號的條目，他將拒絕新的日誌條目。壹致性檢查就像壹個歸納步驟:首先，空日誌狀態必須滿足日誌匹配屬性，然後壹致性檢查確保日誌擴展時的日誌匹配屬性。因此，每當AppendEntries RPC成功返回時，領導者就知道跟隨者的日誌必須與自己的日誌相同(從第壹個日誌條目到最新的條目)。
在正常操作期間，領導者和跟隨者的日誌是壹致的，因此AppendEntries RPC的壹致性檢查永遠不會失敗。但是，領導者的崩潰會使日誌處於不壹致的狀態(舊領導者可能沒有完全復制其日誌中的所有條目)。以下情況:
在Raft算法中，領導者通過強制追隨者復制其日誌來解決不壹致性問題。這意味著跟隨者中與領導者沖突的日誌條目將被領導者的日誌條目覆蓋。
領導者為每個追隨者維護nextIndex，指示領導者將發送給追隨者的下壹個日誌條目的索引。當選擇了新的領導者時，領導者將nextIndex的所有值初始化為他的最後壹個日誌條目的索引加上1。如果跟隨者的日誌與領導者的日誌不壹致，那麽AppendEntries RPC中的壹致性檢查下次將會失敗。在被追隨者拒絕後，leaer將減少nextIndex值並重試AppendEntries RPC。最終，nextIndex將使領導者和追隨者的日誌在某個點上壹致。此時，AppendEntries RPC將成功，刪除follower中與leader沖突的所有日誌條目，然後在leader中追加日誌條目(如果有)。壹旦AppendEntries RPC成功，跟隨者的日誌將與領導者的日誌保持壹致，並在學期的剩余時間內保持壹致。
本機簡單介紹壹下raft的領袖選舉和日誌復制。當然，raft還有本文沒有介紹的其他特性。建議閱讀raft的論文，對raft有壹個完整的了解。
我之前關於zab協議的文章分析了zookeeper的ZAB協議，在這裏我比較壹下兩者的異同。
最後/blob/master/raft-zh _ cn.md。