深入淺出raft共識演算法

Raft是什麼

1.歷史背景

在講Raft前，有必要提一下Paxos演算法，Paxos演算法是Leslie Lamport於1990年提出的基於消息傳遞的一致性演算法。然而，由於演算法難以理解，剛開始並沒有得到很多人的重視。其後，作者在八年後，也就是1998年在ACM上正式發表，然而由於演算法難以理解還是沒有得到重視。而作者之後用更容易接受的方法重新發表了一篇論文《Paxos Made Simple》。

可見，Paxos演算法是有多難理解，即便現在放到很多高校，依然很多學生、教授都反饋Paxos演算法難以理解。同時，Paxos演算法在實際應用實現的時候也是比較困難的。這也是為什麼會有後來Raft演算法的提出。

Raft是實現分散式共識的一種演算法，主要用來管理日誌複製的一致性。它和Paxos的功能是一樣，但是相比於Paxos，Raft演算法更容易理解、也更容易應用到實際的系統當中。而Raft演算法也是聯盟鏈採用比較多的共識演算法。

備註：區塊鏈分為：公有鏈、聯盟鏈和私有鏈

Follower（群眾）

被動接收Leader發送的請求。所有的節點剛開始的時候是處於Follower狀態。

Candidate（候選人）

由Follower向Leader轉換的中間狀態

Leader（領導）

負責和客戶端交互以及日誌複製（日誌複製是單向的，即Leader發送給Follower），同一時刻最多只有1個Leader存在。

三種狀態的轉換關係如下，下一節的Raft工作機制會具體講到。

我們知道，在一個分散式系統資料庫中，如果每個節點的狀態一致，每個節點都執行相同的命令序列，那麼最終他們會得到一個一致的狀態。也就是和說，為了保證整個分散式系統的一致性，我們需要保證每個節點執行相同的命令序列，也就是說每個節點的日誌要保持一樣。所以說，保證日誌複製一致就是Raft等一致性演算法的工作了。

複製狀態機架構

這裡就涉及Replicated State Machine（複製狀態機），如上圖所示。在一個節點上，一致性模塊（Consensus Module，也就是分散式共識演算法）接收到了來自客戶端的命令。然後把接收到的命令寫入到日誌中，該節點和其他節點通過一致性模塊進行通信確保每個日誌最終包含相同的命令序列。一旦這些日誌的命令被正確複製，每個節點的狀態機（State Machine）都會按照相同的序列去執行他們，從而最終得到一致的狀態。然後將達成共識的結果返回給客戶端，如下圖所示。

在分散式系統中，「時間同步」是一個很大的難題，因為每個機器可能由於所處的地理位置、機器環境等因素會不同程度造成時鐘不一致，但是為了識別「過期信息」，時間信息必不可少。

Raft演算法中就採用任期（Term）的概念，將時間切分為一個個的Term（同時每個節點自身也會本地維護currentTerm），可以認為是邏輯上的時間，如下圖。

每一任期的開始都是一次領導人選舉，一個或多個候選人（Candidate）會嘗試成為領導（Leader）。如果一個人贏得選舉，就會在該任期（Term）內剩餘的時間擔任領導人。在某些情況下，選票可能會被評分，有可能沒有選出領導人（如t3），那麼，將會開始另一任期，並且理科開始下一次選舉。Raft 演算法保證在給定的一個任期最少要有一個領導人。

在Raft演算法中，有兩個timeout機制來控制領導人選舉：

一個是選舉定時器（eletion timeout）：即Follower等待成為Candidate狀態的等待時間，這個時間被隨機設定為150ms~300ms之間

另一個是headrbeat timeout：在某個節點成為Leader以後，它會發送Append Entries消息給其他節點，這些消息就是通過heartbeat timeout來傳送，Follower接收到Leader的心跳包的同時也重置選舉定時器。

Raft演算法可以分為如下3個部分：

（1）一開始，所有節點都是以Follower角色啟動，同時啟動選舉定時器（時間隨機，降低衝突概率）

（2）如果一個節點發現在超過選舉定時器的時間以後一直沒有收到Leader發送的心跳請求，則該節點就會成為候選人，並且一直處於該狀態，直到下列三種情況之一發生：

該節點（Candidate）贏得選舉

其他節點贏得選舉

一段時間後沒有任何一台伺服器贏得選舉（進入下一輪Term的選舉，並隨機設置選舉定時器時間）

（3）然後這個候選人就會向其他節點發送投票請求（Request Vote），如果得到半數以上節點的同意，就成為Leader（Leader）。如果選舉超時，還沒有Leader選出，則進入下一任期，重新選舉。

（4）完成Leader選舉後，Leader就會定時給其他節點發送心跳包（Heartbeat），告訴其他節點Leader還在運行，同時重置這些節點的選舉定時器。

（1）Client向Leader提交指令（如：SET 5），Leader收到命令後，將命令追加到本地日誌中。此時，這個命令處於「uncomitted」狀態，複製狀態機不會執行該命令。

（2）然後，Leader將命令（SET 5）並發複製給其他節點，並等待其他其他節點將命令寫入到日誌中，如果此時有些節點失敗或者比較慢，Leader節點會一直重試，知道所有節點都保存了命令到日誌中。之後Leader節點就提交命令（即被狀態機執行命令，這裡是：SET 5），並將結果返回給Client節點。

（3）Leader節點在提交命令後，下一次的心跳包中就帶有通知其他節點提交命令的消息，其他節點收到Leader的消息後，就將命令應用到狀態機中（State Machine），最終每個節點的日誌都保持了一致性。

Leader節點會記錄已經交的最大日誌index，之後後續的heartbeat和日誌複製請求（Append Entries）都會帶上這個值，這樣其他節點就知道哪些命令已經提交了，就可以讓狀態機（State Machine）執行日誌中的命令，使得所有節點的狀態機數據都保持一致。

下面我們來看下日誌內容不一致的情況下，Raft演算法如何處理？

如下圖，如果在一個分散式網路中，各個節點的日誌狀態如下。當Leader節點發送日誌複製請求的時，它會帶上上一次的日誌記錄的index和term。

此時Leader節點發送日誌複製請求。此時，A節點收到Leader的請求後，對比Leader節點記錄的上一個日誌記錄的index和term，發現：

index（leader）> index（A）

term（leader）> currentTerm（A）

發現自己的日誌中不存在這個命令，於是拒絕這個請求。此時，Leader節點知道發生了不一致，於是遞減nextIndex，並重新給A節點發送日誌複製請求，直到找到日誌一致的地方為止。然後把Follower節點的日誌覆蓋為Leader節點的日誌內容。

也就是說，Raft演算法對於日誌內容不一致的請求，會採取Leader節點的日誌內容覆蓋Follower節點的日誌內容的做法，先找到兩者日誌記錄第一次不一致的地方，然後一直覆蓋到最新提交的命令位置。

之前的內容討論了 Raft 演算法是如何進行領導選取和複製日誌的。然而，到目前為止這個機制還不能保證每一個狀態機能按照相同的順序執行同樣的指令。例如，當領導人提交了若干日誌條目的同時一個追隨者可能宕機了，之後它又被選為了領導人然後用新的日誌條目覆蓋掉了舊的那些，最後，不同的狀態機可能執行不同的命令序列。

而Raft演算法通過在領導人選舉階段增加一個限制來完善了Raft演算法。這個限制能保證，對於固定任期，任何領導人都擁有之前任期提交的全部日誌命令。Raft演算法通過投票的方式來阻止那些沒有包含全部日誌命令的節點贏得選舉。

一個Candidate節點要成為贏得選舉，就需要跟網路中大部分節點進行通信，這就意味著每一條已經提交的日誌條目最少在其中一台伺服器上出現。如果候選人的日誌至少和大多數伺服器上的日誌一樣新，那麼它一定包含有全部的已經提交的日誌條目。RequestVote RPC 實現了這個限制：這個 RPC包括候選人的日誌信息，如果它自己的日誌比候選人的日誌要新，那麼它會拒絕候選人的投票請求。

那麼，怎麼判斷兩個節點日誌內容比較新呢？其標準如下，Raft演算法通過比較日誌中最後一個命令的索引（index）和任期號（term）來判定哪一個日誌內容比較新。

如果兩個日誌的任期號不同，任期號大的日誌內容更新

如果任期號相同，日誌長的日誌內容更新

下面我們來考慮一個比較極端的情況，出現網路分區的時候，Raft如何保持一致性。

如下圖，我們將分散式網路分割為兩個子網，分別是子網路AB和子網路CDE，此時節點B是Leader節點。