Raft是一個分布式系統(tǒng)的一致性算法，它不像Paxos那么難懂，實現(xiàn)比Paxos簡單許多，性能與Paxos相當，在Etcd，Consul里面等都有廣泛運用。之前在容器服務(wù)化的時候用到Consul，順帶看了Raft算法的論文，然后為了練手Go語言做了mit6.824分布式系統(tǒng)課程的lab2。由于實驗里面隨機選舉時間和模擬的節(jié)點crash導(dǎo)致的異?？赡茉谀氵\行上百次才會出現(xiàn)，實現(xiàn)后要測試多次以保證測試通過。我的Raft算法的實現(xiàn)代碼在這里 6.824-2017-raft，多有參考其他代碼，見README。6.824課程的lab1是完成一個簡化版的MapReduce，實現(xiàn)比較簡單，代碼見 6.824-2017-mapreduce。如有錯誤，懇請指正。

1 概述

分布式系統(tǒng)的一致性算法就是指一組機器協(xié)同工作，即便其中有某些機器宕機了，系統(tǒng)還能正常對外提供服務(wù)。以前通常都喜歡用Paxos來講解一致性算法，但是Paxos本身很復(fù)雜，代碼實現(xiàn)也很難，于是催生了Raft這個更加簡單易懂的一致性算法，難得的是，它的效果跟Paxos差不多。

為了易于理解，Raft采用了算法分解(分為leader選舉，日志復(fù)制以及安全性)和減少狀態(tài)的方式。與以往一致性算法不同的是，Raft有一些特別的地方：

強Leader。Raft使用了一個強Leader特性，日志復(fù)制只能從Leader節(jié)點復(fù)制到其他節(jié)點。
Leader選舉。Raft使用了一個隨機超時來選舉Leader，以確保選舉不會失敗。
成員變化。Raft使用了聯(lián)合一致性方法來實現(xiàn)成員配置變化時保證服務(wù)不受影響。

2 復(fù)制狀態(tài)機

一致性算法是在復(fù)制狀態(tài)機的背景下提出來的。在復(fù)制狀態(tài)機中，集群中的服務(wù)器從相同的狀態(tài)中生成同樣的副本，即使其中有些服務(wù)器宕機了，客戶端還是可以繼續(xù)執(zhí)行操作，復(fù)制狀態(tài)機可以用來解決分布式系統(tǒng)中許多容錯問題。大型分布式系統(tǒng)中通常擁有一個集群leader，比如GFS，HDFS等通常使用一個單獨的復(fù)制狀態(tài)機管理leader選舉和配置信息以應(yīng)對leader的崩潰。此外，使用復(fù)制狀態(tài)機的還有Chubby以及ZooKeeper等。

復(fù)制狀態(tài)機通過復(fù)制日志實現(xiàn)，如下圖所示。每個服務(wù)器都會存儲一份日志，日志存儲的是一系列命令，而服務(wù)器的狀態(tài)機會按順序執(zhí)行這些日志中的命令。每份日志中以同樣的順序存儲了同樣的命令，而狀態(tài)機以同樣的順序執(zhí)行這些相同的命令。每臺服務(wù)器的狀態(tài)機都是確定的，它們以同樣的順序執(zhí)行同樣的命令，最終的狀態(tài)和輸出也必然是一樣的。

復(fù)制狀態(tài)機圖示

保持復(fù)制日志的一致性就是一致性算法的工作了。服務(wù)器上的一致性模塊接收客戶端命令并添加命令到它的日志中。它與其他服務(wù)器通信以保證每個日志最終都以相同的順序包含相同的命令，即便過程中有服務(wù)器宕機了。一旦客戶端命令正確的復(fù)制了，每個服務(wù)器的狀態(tài)機按照日志中順序處理這些命令，并將輸出返回給客戶端。最終，這些服務(wù)器看起來就像是一臺高可用的狀態(tài)機。

應(yīng)用到實際系統(tǒng)中的一致性算法通常具備下面幾個特性：

保證安全。在所有的非拜占庭將軍條件下保證安全，包括網(wǎng)絡(luò)延遲，分區(qū)，丟包，亂序等。
高可用。只要集群中的服務(wù)器有大多數(shù)(超過一半)可用，系統(tǒng)即是可用的。比如5臺服務(wù)器的集群可用允許2臺服務(wù)器宕機而不影響服務(wù)。
不依賴時序保證日志的一致性。錯誤的時鐘和極端的消息延遲在最壞情況下才會導(dǎo)致可用性問題。
在通常情況下，只要集群中大部分服務(wù)器對過程調(diào)用做出響應(yīng)，命令就可以完成，少數(shù)慢服務(wù)器不會影響整體系統(tǒng)性能。

3 Raft算法

Raft算法分為兩部分，領(lǐng)導(dǎo)選舉(Leader Election)和日志復(fù)制(Log Replication)。這里有個很形象的動畫說明Raft算法的實現(xiàn)，關(guān)于成員變更和日志快照這里有篇解釋很好的文章，見深入淺出 Raft - Membership Change
。

3.1 領(lǐng)導(dǎo)選舉

首先了解下Raft中節(jié)點的幾個狀態(tài)：Follower，Candidate，Leader。狀態(tài)變遷如下圖所示。

Raft節(jié)點狀態(tài)變遷圖

處于Follower狀態(tài)的節(jié)點在一個隨機的超時時間(稱之為Election timeout，注意每次都要隨機選擇一個超時時間，這個超時時間通常為150-300毫秒，我在實驗中設(shè)置的是300+ms)內(nèi)沒有收到投票或者日志復(fù)制和心跳包的RPC，則會變成Candidate狀態(tài)。
處于Candidate狀態(tài)的節(jié)點會馬上開始選舉投票。它先投自己一票，然后向其他節(jié)點發(fā)送投票，這個請求稱之為Request Vote RPC。如果獲得了過半的節(jié)點投票，則轉(zhuǎn)成Leader狀態(tài)。如果投票給了其他節(jié)點或者發(fā)現(xiàn)了更新任期(Term)的指令(如更新任期的選舉投票和日志復(fù)制指令)，則轉(zhuǎn)為Follower狀態(tài)。如果選舉超時沒有得到過半投票，則保持Candidate狀態(tài)開始一個新一輪選舉投票。
處于Leader狀態(tài)的節(jié)點會定期發(fā)送(這個時間為HeartbeatTimeout，通常要遠小于選舉超時，實驗中我設(shè)置的位50ms)AppendEntries RPC請求給其他節(jié)點。如果發(fā)現(xiàn)了更新任期的指令，則轉(zhuǎn)為Follower狀態(tài)。

選舉投票需要兩個條件：

條件一：請求投票的節(jié)點的任期必須大于等于本節(jié)點且本節(jié)點還沒有投過票給其他節(jié)點(包括投票給自己)。
條件二：請求投票的節(jié)點的日志必須是包含了最新提交日志的節(jié)點，這是為了保證日志安全增加的限制條件。如何保證請求投票節(jié)點包含了最新提交日志呢？可以比較兩個節(jié)點最后一條日志的任期，如果任期不一樣，則任期大的日志更新；如果任期一樣，則日志更長的更新。

3.2 日志復(fù)制

Raft是強Leader機制，日志只能從Leader復(fù)制到其他節(jié)點。日志項LogEntry包括index，term，command三個元素。其中index為日志索引，term為任期，而command為具體的日志內(nèi)容。日志格式如下圖所示:

Raft日志格式示意圖

通常的日志復(fù)制流程是這樣的:

客戶端發(fā)送請求給Leader。
Leader接收客戶端請求，先將請求命令作為一個日志項(LogEntry)append到自己的log中。
Leader然后在最近的一個Heartbeat timeout時發(fā)送 Append Entries RPC給Follower節(jié)點。
一旦日志提交成功：
- 此時日志處于Uncommitted狀態(tài)，當過半節(jié)點添加log成功后，則Leader提交該日志給狀態(tài)機，返回給客戶端寫入成功。
- 并在接下來的Append Entries RPC中通知其他節(jié)點提交該日志。
- Follower節(jié)點提交日志到自己的狀態(tài)機中。
如果Leader節(jié)點掛了，其他Follower節(jié)點會在超時后重新選舉新的Leader。而如果有宕機或者慢的Follower節(jié)點，則Leader會不斷重試直到成功。

即便出現(xiàn)網(wǎng)絡(luò)分割，集群中同時存在多個Leader時，也不會有問題。假定5個節(jié)點的集群分割成了3節(jié)點和2節(jié)點兩個大小集群，3節(jié)點大集群因為數(shù)目3過半，可成功提交日志，而節(jié)點數(shù)不夠的小集群沒法成功提交日志。當網(wǎng)絡(luò)恢復(fù)時，因為另外分割的一個大集群已經(jīng)成功提交了日志，最終新的Leader會在大集群中產(chǎn)生(基于選舉投票的條件二保證)并同步到之前分割的小集群節(jié)點中。

關(guān)于日志復(fù)制的幾個要點:

不同的服務(wù)器上面的提交的相同的索引和任期的日志項的command一定相同，而且這個日志項之前的所有日志項都相同。
如果一個日志項被提交，則它之前索引的所有日志項也肯定已經(jīng)提交。
Leader從來都不覆蓋自己的日志。其他狀態(tài)節(jié)點如果出現(xiàn)與當前Leader日志不一致，則需要更新日志，包括寫入新的日志和刪除不一致的日志。
Leader提交過的日志一定會出現(xiàn)將來新的Leader中。
Leader要保證安全的提交日志，必須滿足這兩個提交規(guī)則(見4.3中不安全的情況和4.4安全的情況)：
- 日志條目已經(jīng)復(fù)制到大多數(shù)Follower節(jié)點。
- Leader當前任期的新日志條目至少有一個復(fù)制到了大多數(shù)Follower節(jié)點。

時序和可用性:

Raft的一個特點就是安全性不依賴時序，系統(tǒng)不會因為時序問題而導(dǎo)致錯誤發(fā)生，但是系統(tǒng)的可用性不可避免的會對時序有所依賴。如果服務(wù)器崩潰會導(dǎo)致Candidate節(jié)點選舉不成功而不停的發(fā)起選舉，而Raft必須有一個穩(wěn)定的Leader，否則無法工作。領(lǐng)導(dǎo)選舉是Raft中對時序要求最關(guān)鍵的地方，Raft能夠選舉出并保持一個穩(wěn)定的Leader需要系統(tǒng)滿足如下時序要求：

broadcastTime << electionTimeout << MTBF

其中broadcastTime是指一臺服務(wù)器并行地向集群其他服務(wù)器發(fā)送RPC并接收到響應(yīng)的平均時間，而electionTimeout是選舉超時時間，MTBF則是指單個服務(wù)器發(fā)生故障的平均間隔時間。broadcastTime遠小于electionTimeout可以保證Leader持續(xù)發(fā)送心跳包給Follower節(jié)點以防止Follower節(jié)點發(fā)起選舉，electionTimeout遠小于MTBF是為了保證系統(tǒng)的穩(wěn)定運行。Leader崩潰后，理論上大約只有electionTimeout的時間內(nèi)服務(wù)不可用。

根據(jù)存儲方式的不同，broadcastTime一般設(shè)置為0.5ms到20ms(實驗中設(shè)置心跳間隔略有不同，推薦是100ms左右，我設(shè)置的50ms)，而electionTimeout一般是10-500ms(實驗設(shè)置的是300+ms)。通常服務(wù)器的MTBF一般是幾個月甚至幾年，很容易符合這個要求。

4 Raft日志復(fù)制狀態(tài)分析

4.1 前一條日志相同才能復(fù)制成功

復(fù)制狀態(tài)圖示1

4.2 Leader最新任期有日志已經(jīng)復(fù)制到了大多數(shù)節(jié)點(安全)

復(fù)制狀態(tài)圖示2

如圖所示，S1-S3在任期2已復(fù)制成功了第4條LogEntry，這個時候Leader必須包括第4個LogEntry，因此重新選舉時S4和S5都不能選舉為Leader，第4條日志可以安全提交。

4.3 Leader試圖從一個較老的任期提交日志(不安全)

復(fù)制狀態(tài)圖示3

如上圖所示，這時候如果提交第3條LogEntry是不安全的，因為后續(xù)如果S5選舉為Leader的話會覆蓋S1,S2,S3的第3條日志。

4.4 Leader安全的提交日志

復(fù)制狀態(tài)圖示4

如上圖所示，此時Leader最新任期4的一個日志條目4已經(jīng)復(fù)制到大多數(shù)節(jié)點S1-S3，此時S5不能選舉成功，日志條目3和4都是安全的。這就印證了前面提到的Leader當前任期的新日志條目至少有一個復(fù)制到了大多數(shù)Follower節(jié)點才能提交。

4.5 Leader變化導(dǎo)致日志不一致

Leader變化導(dǎo)致日志不一致

如上圖所示，Leader變化會導(dǎo)致各節(jié)點日志不一致，則需要做如下處理：

新的Leader需要保證Follower的日志與其一致，F(xiàn)ollower如果有不一致的多余日志要刪除，少了日志則要添加。如下面處理流程圖中的(a)是需要添加缺少的日志，(b)則是要刪除不一致的多余的日志再添加新的日志。
Leader會給每個Follower維護一個nextIndex列表，記錄要發(fā)送給對應(yīng)Follower節(jié)點的下一個日志的索引。
如果Follower復(fù)制日志失敗，Leader需要減小nextIndex并重試。

日志不一致處理流程示意

5 Raft實現(xiàn)需注意的幾個地方

Raft實現(xiàn)需要的數(shù)據(jù)結(jié)構(gòu)在論文中已經(jīng)很完整，如下圖：

Raft實現(xiàn)數(shù)據(jù)結(jié)構(gòu)和流程要點

Leader的心跳和日志復(fù)制都可以作為Append Entries RPC請求發(fā)送，可以簡化代碼。與日志復(fù)制不同的是，心跳RPC的Entries參數(shù)為空。
注意兩個超時。一個是選舉超時，一個是日志復(fù)制(心跳)間隔時間。選舉超時ElectionTimeout和日志復(fù)制間隔HeartbeatTimeout兩個超時時間的選擇，注意復(fù)制間隔必須遠小于選舉超時，即 HeartbeatTimeout << Electiontimeout。我的代碼設(shè)置的選舉超時隨機為(300+Rand(100))ms(原論文要求的是150-300ms，但是實驗里面的意思是要大于300ms比較好，不過設(shè)置為300+ms測試也能通過)，注意選舉超時每次都要隨機，不然可能造成選舉不成功。復(fù)制間隔固定為50ms(論文里面要求是20ms以內(nèi)，實驗里面是要求100ms左右，測試發(fā)現(xiàn)在選舉超時為300+ms的時候心跳間隔為50ms可以測試通過)。
注意加鎖問題，多個協(xié)程共享的數(shù)據(jù)要加鎖訪問rf.mu.Lock()，記得釋放鎖，使用defer rf.mu.Unlock()是個不錯的方案。測試的時候也要記得加上data race的檢測， go test -race。
注意提交日志的時候applyLogs()函數(shù)里面的日志提交部分，commitIndex只要比lastApplied大的日志項都要提交，因為一次可能是提交多個日志的，否則會出錯。
日志數(shù)組rf.log的第一項沒有使用，主要是為了和論文兼容，日志索引從1開始，注意，go語言的數(shù)組第一項如果是nil的話gob編碼解碼會有問題，所以要加個空的LogEntry進去填充。
只要修改了本機要持久存儲的變量，就要調(diào)用rf.persist()進行持久化。每個節(jié)點都要持久存儲的變量有 currentTerm, voteFor, log。
對于優(yōu)化Append Entries RPC次數(shù)的代碼，請參照參考資料3的說明。

6 參考資料

課程的基本框架代碼來自：git://g.csail.mit.edu/6.824-golabs-2017
課程的實驗主頁: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
課程的一個指導(dǎo)頁面： https://thesquareplanet.com/blog/students-guide-to-raft/
Raft算法論文： https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
Raft的一個簡單易懂的動畫，強烈推薦: http://thesecretlivesofdata.com/raft/
Raft的一個js的實現(xiàn)：https://github.com/ongardie/raftscope/blob/master/raft.js
初始版本V1參考過的代碼：https://github.com/yuyang0/mit-6.824.git
修改版本V2狀態(tài)切換部分實現(xiàn)參考了這個: https://github.com/happyer/distributed-computing/blob/master/src/raft/raft.go
Raft算法PPT，復(fù)制日志部分的內(nèi)容和圖基本來自這個PPT-Raft: A Consensus Algorithm for Replicated Logs Diego Ongaro and John Ousterhout Stanford University