簡介

Raft是今比較流行的一個分布式選舉算法碰缔。在它出來之前喇颁，業(yè)界只有Paxos一種算法。但是Paxos是非常難以理解初澎，更不用說有統(tǒng)一的算法方案秸应。Raft的出現(xiàn)，就是為了提供一個通俗易懂碑宴，容易實(shí)現(xiàn)的分布式方案软啼。研究論文和相關(guān)源碼已久，寫下此文筆記延柠，希望能對你也有一些啟發(fā)祸挪。

基本原理

Server狀態(tài)

集群的每個機(jī)器可以有3種角色狀態(tài)

• Leader 每個集群只能有一個，處理所有client的請求贞间，日志復(fù)制贿条。
• Follower 普通的Server，完全被動的榜跌，只會對收到的消息進(jìn)行回應(yīng)闪唆。
• Candidate 候選人盅粪，當(dāng)進(jìn)入新一輪選舉的時候钓葫，所有的候選人都會發(fā)起投票。重新選出一個新leader

三者之間的關(guān)系票顾，可以互相轉(zhuǎn)換础浮，如果下圖

raft1.png

1. 最開始，所有的Server都是Follower奠骄。
2. 如果Follower沒有收到心跳豆同，就會變成Candidate
3. Candidate 開始進(jìn)行新一輪的選舉，其中一個成為新的Leader,其余的成為Follower含鳞。
4. Leader如果收到更大的Term（任期）消息影锈，就降級為普通的Follower。

Term

時間劃分為不同的Term（任期）蝉绷。每次導(dǎo)致新的選舉發(fā)生鸭廷，Term就會改變+1.一個Term包括兩個階段：選舉和正常階段。每個服務(wù)器都會保存當(dāng)前的任期Current Term熔吗。用于發(fā)送和接受RPC消息時驗(yàn)證比較辆床。

raft2.png

Log Entry

每一個client操作，對于Leader來說桅狠，都是增加一個Log Entry讼载，然后復(fù)制同步到其他的Server轿秧。包括以下數(shù)據(jù)：

• term Leader收到log時的term
• index log下標(biāo)。log存儲結(jié)構(gòu)是一個List
• command 操作指令

Persistent State 持久化狀態(tài)

每個server都會在本地存儲一些持久化狀態(tài)咨堤，每次在相應(yīng)rpc時先持久化

• currentTerm 當(dāng)前Term菇篡，啟動的時候是0
• voteFor 當(dāng)前term收到的投票
• log[] 日志數(shù)據(jù)

選舉過程

當(dāng)一個Follower沒有收到Leader的心跳時，就會投票開始新一輪的選舉一喘。所以當(dāng)Leader出現(xiàn)故障時逸贾，可能有多個Follower變成Candidate開始投票。這里有個細(xì)節(jié)津滞，就是開始的時間是不同的铝侵，是一個隨機(jī)100-500ms，這樣可以更快速產(chǎn)生新的Leader触徐。

1. 當(dāng)前Term 增加1咪鲜。
2. 狀態(tài)有Follower變成Candidate。
3. 給自己投票撞鹉。
4. 發(fā)送投票信息RequeustVote給所有的Server疟丙，一直重試，直到以下情況之一發(fā)生才停止：
   • 收到大多數(shù)(>=n/2+1)的Server投票給自己鸟雏，然后變成新一輪的Leader享郊，開始發(fā)送心跳AppendEntry給其他的Server。
   • 收到新Leader的RPC孝鹊，狀態(tài)變成Follower
   • 沒有人選舉成功炊琉。增加Term，開始新一輪的選舉又活。

RequeustVote RPC

參數(shù)

• candidateId 投票的candidate
• term candidate當(dāng)前的term
• lastLogIndex 上一個Log的index
• lastLogTerm 上一個Log的term

返回值

• term 當(dāng)前term
• voteGranted 如果是true表示贊同投票

實(shí)現(xiàn)過程

1. if (term>currentTerm){
    currentTerm = term;
    //如果是（Leader or Candidate） -> Follwer
}
2. if（term==currentTerm）{
    //本輪還沒收到過其他的投票
    if（voteFor==null||voteFor==candidateId）{
        if（candidateLog >=本地的log）{
            贊同本次選舉
            自己不再進(jìn)行本輪主動投票
        }
    }
    
}

日志復(fù)制

當(dāng)前Term如果處于正常狀態(tài)苔咪，那么就可以接受client的請求。

• client向Leader發(fā)送command
• Leader 將command增加到log[]
• Leader 向所有的Follower發(fā)送AppendEntry RPC
• 如果有大多數(shù)（大于一半）的請求有響應(yīng)柳骄，Leader將command提交到自己的狀態(tài)機(jī)团赏，然后返回消息給client。
• Follower 也將command提交到自己的狀態(tài)機(jī)耐薯。
• 如果Follower crash或者很慢響應(yīng)舔清，那么Leader會繼續(xù)重試直到成功

AppendEntries RPC

參數(shù)

• term Leader的當(dāng)前Term
• leaderId Follower可以重新和新Leader交互
• preLogIndex 倒數(shù)第二個Log Index
• preLogTerm 倒數(shù)第二個Log的Term
• entries[] 存儲的log entry
• commitIndex 即將commit的的entry

返回值

• term 當(dāng)前term，用于Leader更新自己的（如果Leader發(fā)現(xiàn)自己的是舊的曲初，就會退回Follower）
• succes 是否成功体谒，如果preLogIndex和preLogTerm在本地能找到

實(shí)現(xiàn)過程

//太舊的Term，說明這個Leader已經(jīng)失效了
if(term<currentTerm){
    return false
}
if（term>currentTerm）{
    currentTerm = term
}
//如果是candidater or leader复斥，重新變成Follower
//如果找不到一個log营密，同時匹配preLogIndex和preLogTerm，return false
//刪除沖突的entry
//添加新的entry
//更新本地的狀態(tài)機(jī)

異常情況

Log一致性

• 如果在不同的Server 有相同的index和term那么表明：
  • 他們存儲相同的Command
  • 在這個log之前的所有entry也是相等的
• 如果一個指定的entry被committed目锭，那么在它之前的所有entry也是committed

基于上面的論證评汰，每次AppendEntries RPC都會帶上當(dāng)前entry的前一個log信息纷捞，包括index和term，如果Follower找不到被去，就說明兩者的log不一致了主儡，需要刪除沖突的，填上新加的惨缆，然后再提交本次需要committed的糜值。

舉個例子

raft3.png

選舉最合適的Leader

當(dāng)一個Log被committed時，它一定是被復(fù)制到大多數(shù)（大于1半）的server坯墨。如果要重新選舉一個Leader寂汇，我們希望Candidate帶上最多的committed entries。

上面RequeustVote RPC 介紹過捣染，要么Term比較大骄瓣，要么log index比較大

if(lastTermVote>lastTermC||
(lastTermVote==lastTermC)&&lastIndexVote>lastIndexC))

服務(wù)器節(jié)點(diǎn)變更

通常情況下，集群里面的服務(wù)器數(shù)量是固定的耍攘。但在實(shí)際生產(chǎn)中榕栏，經(jīng)常需要擴(kuò)容，縮容蕾各，所以服務(wù)器可能不斷變化扒磁。我們來看下Raft是如何解決的

服務(wù)器的配置信息無法直接從舊配置轉(zhuǎn)換為新配置。我們要解決的問題式曲，就是變更期間妨托，同一個任期不能有兩個Leader選舉勝出。為了保證安全检访，配置變更采用兩階段的辦法始鱼。

rafe4.png

Raft引入了一個過渡狀態(tài)-joint consensus。節(jié)點(diǎn)成員的變更脆贵，Leader會將C-old和C-new都放在joint consensus（也就是下圖的C-old-new）,然后作為一個Log發(fā)送給其他的Follower。其他Follower收到后起暮，可以馬上使用最新的節(jié)點(diǎn)數(shù)據(jù)卖氨，不需要等待log被committed。注意负懦，此時只有C-old里面的集群可以進(jìn)行選舉筒捺。如果此時Leader down，新選出 的Leader在C-old or C-old-new纸厉。 C-new這邊的集群不能單邊決策

rafe5.png

當(dāng)進(jìn)入join consensus之后系吭，Leader會再提交一個新的C-new Log，其他Follower收到這個Log颗品，就可以使用新的配置了肯尺。當(dāng)C-new這個Log被committed沃缘，C-old就沒有用了，不在C-new的節(jié)點(diǎn)可以關(guān)閉则吟』蓖危基于這套流程，在任何時刻氓仲，C-old和C-new不會出現(xiàn)單邊投票的情況水慨。

三個問題

1. 新機(jī)器初始化的時候可能沒有任何存儲日志。如果以這樣的狀態(tài)加入集群敬扛，需要花費(fèi)很長時間才能趕上集群中的其他機(jī)器晰洒，這個期間機(jī)器是不能提交新日志。為了避免不可用的間隙啥箭，Raft在配置變更前引入一個新的階段欢顷，類似Learner的角色，不參與投票捉蚤，只復(fù)制日志抬驴。
2. leader可能不是新配置的機(jī)器。這種情況下缆巧，leader在提交新配置后就降級成Follower
3. 最后一步刪除不在新配置的機(jī)器布持，這些機(jī)器可能干擾中斷集群。它們收不到心跳陕悬，會發(fā)起新的選舉题暖，導(dǎo)致當(dāng)前l(fā)eader回退到Follower。新的leader被選舉出來捉超，但是舊機(jī)器將會再次超時胧卤。這個過程不斷重復(fù)。為了避免這個問題拼岳，servers在確定leader存在的情況下將不理會RequestVote枝誊。如果一個機(jī)器在最小超時時間下收到當(dāng)前term的vote，他將不更新自己的term惜纸，也不參與本次選舉叶撒。這樣做并不會影響正常的選舉。

日志壓縮

隨著集群的運(yùn)行耐版，機(jī)器的日志將會不斷增長祠够。為了保證集群的可用性，需要額外的機(jī)制來刪除日志中過期的日志粪牲」湃浚快照是最簡單的壓縮方法。

每個機(jī)器獨(dú)立進(jìn)行快照，快照只需要覆蓋已經(jīng)提交的日志落君。更多的工作是狀態(tài)機(jī)將自己的當(dāng)前狀態(tài)寫入快照中穿香。Raft中包含了少量的metadata在快照中：

• last included index 日志中最后一條被快照取代的日志的索引（也是狀態(tài)機(jī)應(yīng)用的上一條日志的索引）
• last included term 這條日志對應(yīng)的Term

這些被持久化用來支持AppendEntries的日志一致性檢測，如前面提過叽奥，日志的一致性檢測需要前一條日志的Term和索引扔水。為了支持集群成員變更，快照也包含了最后一條被快照取代的日志所使用的配置朝氓。一旦機(jī)器完成快照魔市，它將可以刪除last included index 之前的所有日志，也包括之前的快照赵哲。

正常情況下待德，機(jī)器都是單獨(dú)的進(jìn)行快照。但是在某些情況下枫夺，leader也會發(fā)送快照到那些落后的機(jī)器上将宪。發(fā)送快照可以是分段發(fā)送的，帶上偏移量橡庞。具體的過程如下所示较坛。

InstallSnapshot RPC

參數(shù)

• term Leader的當(dāng)前Term
• leaderId Follower可以重定向到Leader
• lastIncludedIndex 快照替換的最后一條日志記錄的索引
• lastIncludedTerm 快照替換的最后一條日志記錄的索引的Term
• offset 快照中的字節(jié)偏移量
• data[] 數(shù)據(jù)塊，從偏移量開始存儲
• done 是否最后一個塊文件

返回值

• term 當(dāng)前term扒最，用于Leader更新自己

實(shí)現(xiàn)過程

//太舊的Term丑勤，說明這個Leader已經(jīng)失效了
if(term<currentTerm){
    return false
}
if（偏移量==0）{
    創(chuàng)建新的快照文件
}
在快照文件的指定偏移量寫入數(shù)據(jù)
if（！done）{
    return 響應(yīng) 等待更多的塊數(shù)據(jù)
}
保存快照文件吧趣，刪除快照之前的日志
如果存在快照點(diǎn)之后的日志文件法竞，保留這些日志并重放
刪除整個日志文件
使用快照的狀態(tài)來重置狀態(tài)機(jī)，并加載快照中的配置

線性讀

我們之前講過强挫，client的每個操作岔霸，leader都要封裝成一個log，復(fù)制到所有的節(jié)點(diǎn)俯渤。如果只是讀操作呆细，我們其實(shí)是可以提高性能，不進(jìn)行日志復(fù)制的稠诲。但是要避免返回臟數(shù)據(jù)的風(fēng)險侦鹏。因?yàn)長eader節(jié)點(diǎn)響應(yīng)client請求時可能已經(jīng)故障（或者是發(fā)送了網(wǎng)絡(luò)分區(qū)），集群中已經(jīng)選出了新的Leader臀叙，但是此時舊Leader自己還不知道。

Raft在處理只讀請求价卤，除了直接讀取Leader節(jié)點(diǎn)的狀態(tài)信息數(shù)據(jù)劝萤，還需要通過一些額外的操作：

1. Leader節(jié)點(diǎn)必須有關(guān)于已經(jīng)提交日志的最新信息。Leader在任期開始時慎璧，會提交一條空白的log床嫌，這樣確保上一個term的所有l(wèi)og都會被提交跨释。此時Leader擁有所有已經(jīng)被committed的log
2. Leader會記錄只讀請求對應(yīng)的編號readIndex，當(dāng)Leader提交的位置committedIndex達(dá)到或者超過該位置后厌处，即可響應(yīng)只讀請求
3. Leader在處理只讀請求之前必須檢查集群中是否有新的Leader鳖谈。在處理只讀請求之前，讓Leader節(jié)點(diǎn)可以和半數(shù)以上的節(jié)點(diǎn)交換一次心跳阔涉。如果成功缆娃，Leader依然是最新的，readerIndex值也是整個集群中所有節(jié)點(diǎn)能看到的最大提交位置commitIndex瑰排。
4. 隨著日志記錄不斷提交贯要，Leader節(jié)點(diǎn)的提交位置commitIndex最終會超過上述readIndex，此時Leader就可以響應(yīng)client的只讀請求了椭住。

開源項(xiàng)目

1. BRaft 百度開源的c/c++實(shí)現(xiàn)的raft框架
2. JRaft 螞蟻金服開源的Java實(shí)現(xiàn)的raft框架崇渗，參考了BRaft
3. Etcd 內(nèi)部采用raft協(xié)議作為一致性算法，基于Go語言實(shí)現(xiàn)京郑。

參考資料

1. 《Raft論文》 （我的這篇筆記其實(shí)只是這篇偉大論文的拙劣復(fù)述）
2. 《Raft User Study》 （簡潔易懂）
3. 《JRaft 官方文檔》宅广。（里面的原理講得很好，后續(xù)我將寫點(diǎn)源碼筆記）
4. 《etc技術(shù)內(nèi)幕》

后記

哪里有恐懼些举，哪里就有愛跟狱。--《霍亂時期的愛情》2020.2.29