分布式共識(shí) - Raft 算法

這篇具有很好參考價(jià)值的文章主要介紹了分布式共識(shí) - Raft 算法。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

本文由 SnailClimbopen in new window 和 Xieqijunopen in new window 共同完成。

介紹

Raft協(xié)議由Diego Ongaro和John Ousterhout（斯坦福大學(xué)）開發(fā)，Diego于2014年獲得了博士學(xué)位。Raft的設(shè)計(jì)是為了更好地理解如何實(shí)現(xiàn)一致性，考慮到它的前身Paxos算法，由Lesli Lamport開發(fā)，非常難以理解和實(shí)現(xiàn)。因此，Diego的論文標(biāo)題為“尋找可理解的一致性算法”。在Raft之前，Paxos被認(rèn)為是實(shí)現(xiàn)一致性的圣杯。

# 1 背景

當(dāng)今的數(shù)據(jù)中心和應(yīng)用程序在高度動(dòng)態(tài)的環(huán)境中運(yùn)行，為了應(yīng)對(duì)高度動(dòng)態(tài)的環(huán)境，它們通過額外的服務(wù)器進(jìn)行橫向擴(kuò)展，并且根據(jù)需求進(jìn)行擴(kuò)展和收縮。同時(shí)，服務(wù)器和網(wǎng)絡(luò)故障也很常見。

因此，系統(tǒng)必須在正常操作期間處理服務(wù)器的上下線。它們必須對(duì)變故做出反應(yīng)并在幾秒鐘內(nèi)自動(dòng)適應(yīng)；對(duì)客戶來說的話，明顯的中斷通常是不可接受的。

幸運(yùn)的是，分布式共識(shí)可以幫助應(yīng)對(duì)這些挑戰(zhàn)。

# 1.1 拜占庭將軍

在介紹共識(shí)算法之前，先介紹一個(gè)簡(jiǎn)化版拜占庭將軍的例子來幫助理解共識(shí)算法。

假設(shè)多位拜占庭將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們?nèi)绾芜_(dá)成是否要進(jìn)攻的一致性決定？

解決方案大致可以理解成：先在所有的將軍中選出一個(gè)大將軍，用來做出所有的決定。

舉例如下：假如現(xiàn)在一共有 3 個(gè)將軍 A，B 和 C，每個(gè)將軍都有一個(gè)隨機(jī)時(shí)間的倒計(jì)時(shí)器，倒計(jì)時(shí)一結(jié)束，這個(gè)將軍就把自己當(dāng)成大將軍候選人，然后派信使傳遞選舉投票的信息給將軍 B 和 C，如果將軍 B 和 C 還沒有把自己當(dāng)作候選人（自己的倒計(jì)時(shí)還沒有結(jié)束），并且沒有把選舉票投給其他人，它們就會(huì)把票投給將軍 A，信使回到將軍 A 時(shí)，將軍 A 知道自己收到了足夠的票數(shù)，成為大將軍。在有了大將軍之后，是否需要進(jìn)攻就由大將軍 A 決定，然后再去派信使通知另外兩個(gè)將軍，自己已經(jīng)成為了大將軍。如果一段時(shí)間還沒收到將軍 B 和 C 的回復(fù)（信使可能會(huì)被暗殺），那就再重派一個(gè)信使，直到收到回復(fù)。

# 1.2 共識(shí)算法

共識(shí)是可容錯(cuò)系統(tǒng)中的一個(gè)基本問題：即使面對(duì)故障，服務(wù)器也可以在共享狀態(tài)上達(dá)成一致。

共識(shí)算法允許一組節(jié)點(diǎn)像一個(gè)整體一樣一起工作，即使其中的一些節(jié)點(diǎn)出現(xiàn)故障也能夠繼續(xù)工作下去，其正確性主要是源于復(fù)制狀態(tài)機(jī)的性質(zhì)：一組Server的狀態(tài)機(jī)計(jì)算相同狀態(tài)的副本，即使有一部分的Server宕機(jī)了它們?nèi)匀荒軌蚶^續(xù)運(yùn)行。

分布式共識(shí) - Raft 算法,分布式,算法,算法,Raft

圖-1 復(fù)制狀態(tài)機(jī)架構(gòu)

一般通過使用復(fù)制日志來實(shí)現(xiàn)復(fù)制狀態(tài)機(jī)。每個(gè)Server存儲(chǔ)著一份包括命令序列的日志文件，狀態(tài)機(jī)會(huì)按順序執(zhí)行這些命令。因?yàn)槊總€(gè)日志包含相同的命令，并且順序也相同，所以每個(gè)狀態(tài)機(jī)處理相同的命令序列。由于狀態(tài)機(jī)是確定性的，所以處理相同的狀態(tài)，得到相同的輸出。

因此共識(shí)算法的工作就是保持復(fù)制日志的一致性。服務(wù)器上的共識(shí)模塊從客戶端接收命令并將它們添加到日志中。它與其他服務(wù)器上的共識(shí)模塊通信，以確保即使某些服務(wù)器發(fā)生故障。每個(gè)日志最終包含相同順序的請(qǐng)求。一旦命令被正確地復(fù)制，它們就被稱為已提交。每個(gè)服務(wù)器的狀態(tài)機(jī)按照日志順序處理已提交的命令，并將輸出返回給客戶端，因此，這些服務(wù)器形成了一個(gè)單一的、高度可靠的狀態(tài)機(jī)。

適用于實(shí)際系統(tǒng)的共識(shí)算法通常具有以下特性：

安全。確保在非拜占庭條件（也就是上文中提到的簡(jiǎn)易版拜占庭）下的安全性，包括網(wǎng)絡(luò)延遲、分區(qū)、包丟失、復(fù)制和重新排序。
高可用。只要大多數(shù)服務(wù)器都是可操作的，并且可以相互通信，也可以與客戶端進(jìn)行通信，那么這些服務(wù)器就可以看作完全功能可用的。因此，一個(gè)典型的由五臺(tái)服務(wù)器組成的集群可以容忍任何兩臺(tái)服務(wù)器端故障。假設(shè)服務(wù)器因停止而發(fā)生故障；它們稍后可能會(huì)從穩(wěn)定存儲(chǔ)上的狀態(tài)中恢復(fù)并重新加入集群。
一致性不依賴時(shí)序。錯(cuò)誤的時(shí)鐘和極端的消息延遲，在最壞的情況下也只會(huì)造成可用性問題，而不會(huì)產(chǎn)生一致性問題。
在集群中大多數(shù)服務(wù)器響應(yīng)，命令就可以完成，不會(huì)被少數(shù)運(yùn)行緩慢的服務(wù)器來影響整體系統(tǒng)性能。

# 2 基礎(chǔ)

# 2.1 節(jié)點(diǎn)類型

一個(gè) Raft 集群包括若干服務(wù)器，以典型的 5 服務(wù)器集群舉例。在任意的時(shí)間，每個(gè)服務(wù)器一定會(huì)處于以下三個(gè)狀態(tài)中的一個(gè)：

Leader：負(fù)責(zé)發(fā)起心跳，響應(yīng)客戶端，創(chuàng)建日志，同步日志。
Candidate：Leader 選舉過程中的臨時(shí)角色，由 Follower 轉(zhuǎn)化而來，發(fā)起投票參與競(jìng)選。
Follower：接受 Leader 的心跳和日志同步數(shù)據(jù)，投票給 Candidate。

在正常的情況下，只有一個(gè)服務(wù)器是 Leader，剩下的服務(wù)器是 Follower。Follower 是被動(dòng)的，它們不會(huì)發(fā)送任何請(qǐng)求，只是響應(yīng)來自 Leader 和 Candidate 的請(qǐng)求。

分布式共識(shí) - Raft 算法,分布式,算法,算法,Raft

圖-2：服務(wù)器的狀態(tài)

# 2.2 任期

分布式共識(shí) - Raft 算法,分布式,算法,算法,Raft

圖-3：任期

如圖 3 所示，raft 算法將時(shí)間劃分為任意長(zhǎng)度的任期（term），任期用連續(xù)的數(shù)字表示，看作當(dāng)前 term 號(hào)。每一個(gè)任期的開始都是一次選舉，在選舉開始時(shí)，一個(gè)或多個(gè) Candidate 會(huì)嘗試成為 Leader。如果一個(gè) Candidate 贏得了選舉，它就會(huì)在該任期內(nèi)擔(dān)任 Leader。如果沒有選出 Leader，將會(huì)開啟另一個(gè)任期，并立刻開始下一次選舉。raft 算法保證在給定的一個(gè)任期最少要有一個(gè) Leader。

每個(gè)節(jié)點(diǎn)都會(huì)存儲(chǔ)當(dāng)前的 term 號(hào)，當(dāng)服務(wù)器之間進(jìn)行通信時(shí)會(huì)交換當(dāng)前的 term 號(hào)；如果有服務(wù)器發(fā)現(xiàn)自己的 term 號(hào)比其他人小，那么他會(huì)更新到較大的 term 值。如果一個(gè) Candidate 或者 Leader 發(fā)現(xiàn)自己的 term 過期了，他會(huì)立即退回成 Follower。如果一臺(tái)服務(wù)器收到的請(qǐng)求的 term 號(hào)是過期的，那么它會(huì)拒絕此次請(qǐng)求。

# 2.3 日志

entry：每一個(gè)事件成為 entry，只有 Leader 可以創(chuàng)建 entry。entry 的內(nèi)容為<term,index,cmd>其中 cmd 是可以應(yīng)用到狀態(tài)機(jī)的操作。
log：由 entry 構(gòu)成的數(shù)組，每一個(gè) entry 都有一個(gè)表明自己在 log 中的 index。只有 Leader 才可以改變其他節(jié)點(diǎn)的 log。entry 總是先被 Leader 添加到自己的 log 數(shù)組中，然后再發(fā)起共識(shí)請(qǐng)求，獲得同意后才會(huì)被 Leader 提交給狀態(tài)機(jī)。Follower 只能從 Leader 獲取新日志和當(dāng)前的 commitIndex，然后把對(duì)應(yīng)的 entry 應(yīng)用到自己的狀態(tài)機(jī)中。

# 3 領(lǐng)導(dǎo)人選舉

raft 使用心跳機(jī)制來觸發(fā) Leader 的選舉。

如果一臺(tái)服務(wù)器能夠收到來自 Leader 或者 Candidate 的有效信息，那么它會(huì)一直保持為 Follower 狀態(tài)，并且刷新自己的 electionElapsed，重新計(jì)時(shí)。

Leader 會(huì)向所有的 Follower 周期性發(fā)送心跳來保證自己的 Leader 地位。如果一個(gè) Follower 在一個(gè)周期內(nèi)沒有收到心跳信息，就叫做選舉超時(shí)，然后它就會(huì)認(rèn)為此時(shí)沒有可用的 Leader，并且開始進(jìn)行一次選舉以選出一個(gè)新的 Leader。

為了開始新的選舉，F(xiàn)ollower 會(huì)自增自己的 term 號(hào)并且轉(zhuǎn)換狀態(tài)為 Candidate。然后他會(huì)向所有節(jié)點(diǎn)發(fā)起 RequestVoteRPC 請(qǐng)求， Candidate 的狀態(tài)會(huì)持續(xù)到以下情況發(fā)生：

贏得選舉
其他節(jié)點(diǎn)贏得選舉
一輪選舉結(jié)束，無人勝出

贏得選舉的條件是：一個(gè) Candidate 在一個(gè)任期內(nèi)收到了來自集群內(nèi)的多數(shù)選票（N/2+1），就可以成為 Leader。

在 Candidate 等待選票的時(shí)候，它可能收到其他節(jié)點(diǎn)聲明自己是 Leader 的心跳，此時(shí)有兩種情況：

該 Leader 的 term 號(hào)大于等于自己的 term 號(hào)，說明對(duì)方已經(jīng)成為 Leader，則自己回退為 Follower。
該 Leader 的 term 號(hào)小于自己的 term 號(hào)，那么會(huì)拒絕該請(qǐng)求并讓該節(jié)點(diǎn)更新 term。

由于可能同一時(shí)刻出現(xiàn)多個(gè) Candidate，導(dǎo)致沒有 Candidate 獲得大多數(shù)選票，如果沒有其他手段來重新分配選票的話，那么可能會(huì)無限重復(fù)下去。

raft 使用了隨機(jī)的選舉超時(shí)時(shí)間來避免上述情況。每一個(gè) Candidate 在發(fā)起選舉后，都會(huì)隨機(jī)化一個(gè)新的選舉超時(shí)時(shí)間，這種機(jī)制使得各個(gè)服務(wù)器能夠分散開來，在大多數(shù)情況下只有一個(gè)服務(wù)器會(huì)率先超時(shí)；它會(huì)在其他服務(wù)器超時(shí)之前贏得選舉。

# 4 日志復(fù)制

一旦選出了 Leader，它就開始接受客戶端的請(qǐng)求。每一個(gè)客戶端的請(qǐng)求都包含一條需要被復(fù)制狀態(tài)機(jī)（Replicated State Mechine）執(zhí)行的命令。

Leader 收到客戶端請(qǐng)求后，會(huì)生成一個(gè) entry，包含<index,term,cmd>，再將這個(gè) entry 添加到自己的日志末尾后，向所有的節(jié)點(diǎn)廣播該 entry，要求其他服務(wù)器復(fù)制這條 entry。

如果 Follower 接受該 entry，則會(huì)將 entry 添加到自己的日志后面，同時(shí)返回給 Leader 同意。

如果 Leader 收到了多數(shù)的成功響應(yīng)，Leader 會(huì)將這個(gè) entry 應(yīng)用到自己的狀態(tài)機(jī)中，之后可以認(rèn)為這個(gè) entry 是 committed 的，并且向客戶端返回執(zhí)行結(jié)果。

raft 保證以下兩個(gè)性質(zhì)：

在兩個(gè)日志里，有兩個(gè) entry 擁有相同的 index 和 term，那么它們一定有相同的 cmd
在兩個(gè)日志里，有兩個(gè) entry 擁有相同的 index 和 term，那么它們前面的 entry 也一定相同

通過“僅有 Leader 可以生成?entry”來保證第一個(gè)性質(zhì)，第二個(gè)性質(zhì)需要一致性檢查來進(jìn)行保證。

一般情況下，Leader 和 Follower 的日志保持一致，然后，Leader 的崩潰會(huì)導(dǎo)致日志不一樣，這樣一致性檢查會(huì)產(chǎn)生失敗。Leader 通過強(qiáng)制 Follower 復(fù)制自己的日志來處理日志的不一致。這就意味著，在 Follower 上的沖突日志會(huì)被領(lǐng)導(dǎo)者的日志覆蓋。

為了使得 Follower 的日志和自己的日志一致，Leader 需要找到 Follower 與它日志一致的地方，然后刪除 Follower 在該位置之后的日志，接著把這之后的日志發(fā)送給 Follower。

Leader 給每一個(gè)Follower 維護(hù)了一個(gè) nextIndex，它表示 Leader 將要發(fā)送給該追隨者的下一條日志條目的索引。當(dāng)一個(gè) Leader 開始掌權(quán)時(shí)，它會(huì)將 nextIndex 初始化為它的最新的日志條目索引數(shù)+1。如果一個(gè) Follower 的日志和 Leader 的不一致，AppendEntries 一致性檢查會(huì)在下一次 AppendEntries RPC 時(shí)返回失敗。在失敗之后，Leader 會(huì)將 nextIndex 遞減然后重試 AppendEntries RPC。最終 nextIndex 會(huì)達(dá)到一個(gè) Leader 和 Follower 日志一致的地方。這時(shí)，AppendEntries 會(huì)返回成功，Follower 中沖突的日志條目都被移除了，并且添加上了所缺少的?Leader 的日志條目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日志就一致了，這樣的狀態(tài)會(huì)保持到該任期結(jié)束。

# 5 安全性

# 5.1 選舉限制

Leader 需要保證自己存儲(chǔ)全部已經(jīng)提交的日志條目。這樣才可以使日志條目只有一個(gè)流向：從 Leader 流向 Follower，Leader 永遠(yuǎn)不會(huì)覆蓋已經(jīng)存在的日志條目。

每個(gè) Candidate 發(fā)送 RequestVoteRPC 時(shí)，都會(huì)帶上最后一個(gè) entry 的信息。所有節(jié)點(diǎn)收到投票信息時(shí)，會(huì)對(duì)該 entry 進(jìn)行比較，如果發(fā)現(xiàn)自己的更新，則拒絕投票給該 Candidate。

判斷日志新舊的方式：如果兩個(gè)日志的 term 不同，term 大的更新；如果 term 相同，更長(zhǎng)的 index 更新。

# 5.2 節(jié)點(diǎn)崩潰

如果 Leader 崩潰，集群中的節(jié)點(diǎn)在 electionTimeout 時(shí)間內(nèi)沒有收到 Leader 的心跳信息就會(huì)觸發(fā)新一輪的選主，在選主期間整個(gè)集群對(duì)外是不可用的。

如果 Follower 和 Candidate 崩潰，處理方式會(huì)簡(jiǎn)單很多。之后發(fā)送給它的 RequestVoteRPC 和 AppendEntriesRPC 會(huì)失敗。由于 raft 的所有請(qǐng)求都是冪等的，所以失敗的話會(huì)無限的重試。如果崩潰恢復(fù)后，就可以收到新的請(qǐng)求，然后選擇追加或者拒絕 entry。

# 5.3 時(shí)間與可用性

raft 的要求之一就是安全性不依賴于時(shí)間：系統(tǒng)不能僅僅因?yàn)橐恍┦录l(fā)生的比預(yù)想的快一些或者慢一些就產(chǎn)生錯(cuò)誤。為了保證上述要求，最好能滿足以下的時(shí)間條件：

broadcastTime << electionTimeout << MTBF

broadcastTime：向其他節(jié)點(diǎn)并發(fā)發(fā)送消息的平均響應(yīng)時(shí)間；
electionTimeout：選舉超時(shí)時(shí)間；
MTBF(mean time between failures)：?jiǎn)闻_(tái)機(jī)器的平均健康時(shí)間；

broadcastTime應(yīng)該比electionTimeout小一個(gè)數(shù)量級(jí)，為的是使Leader能夠持續(xù)發(fā)送心跳信息（heartbeat）來阻止Follower開始選舉；

electionTimeout也要比MTBF小幾個(gè)數(shù)量級(jí)，為的是使得系統(tǒng)穩(wěn)定運(yùn)行。當(dāng)Leader崩潰時(shí)，大約會(huì)在整個(gè)electionTimeout的時(shí)間內(nèi)不可用；我們希望這種情況僅占全部時(shí)間的很小一部分。

由于broadcastTime和MTBF是由系統(tǒng)決定的屬性，因此需要決定electionTimeout的時(shí)間。

一般來說，broadcastTime 一般為 0.5～20ms，electionTimeout 可以設(shè)置為 10～500ms，MTBF 一般為一兩個(gè)月。文章來源地址http://www.zghlxwxcb.cn/news/detail-830840.html

# 6 參考

https://tanxinyu.work/raft/
https://github.com/OneSizeFitsQuorum/raft-thesis-zh_cn/blob/master/raft-thesis-zh_cn.md
https://github.com/ongardie/dissertation/blob/master/stanford.pdf
https://knowledge-sharing.gitbooks.io/raft/content/chapter5.html
Raft Consensus Algorithm

到了這里，關(guān)于分布式共識(shí) - Raft 算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！