一.Paxos 算法

Paxos 算法誕生于 1990 年，這是一種解決分布式系統(tǒng)一致性的經(jīng)典算法 。但是，由于 Paxos 算法在國際上被公認(rèn)的非常難以理解和實現(xiàn)，因此不斷有人嘗試簡化這一算法。到了2013 年才誕生了一個比 Paxos 算法更易理解和實現(xiàn)的分布式一致性算法--Raft算法（下文會有介紹）

Paxos?算法是基于消息傳遞且具有高度容錯特性的一致性算法，是目前公認(rèn)的解決分布式一致性問題最有效的算法之一，其解決的問題就是在分布式系統(tǒng)中如何就某個值（決議）達成一致?。

在?Paxos?中主要有三個角色，分別為?Proposer提案者、Acceptor表決者、Learner學(xué)習(xí)者。Paxos?算法和?2PC?一樣，也有兩個階段，分別為?Prepare?和?accept?階段。

1. prepare 階段

• Proposer提案者：負(fù)責(zé)提出?proposal，每個提案者在提出提案時都會首先獲取到一個?具有全局唯一性的、遞增的提案編號N，即在整個集群中是唯一的編號 N，然后將該編號賦予其要提出的提案，在第一階段是只將提案編號發(fā)送給所有的表決者。
• Acceptor表決者：每個表決者在?accept?某提案后，會將該提案編號N記錄在本地，這樣每個表決者中保存的已經(jīng)被 accept 的提案中會存在一個編號最大的提案，其編號假設(shè)為?maxN。每個表決者僅會?accept?編號大于自己本地?maxN?的提案，在批準(zhǔn)提案時表決者會將以前接受過的最大編號的提案作為響應(yīng)反饋給?Proposer?。

下面是?prepare?階段的流程圖，你可以對照著參考一下。

2. accept 階段

當(dāng)一個提案被?Proposer?提出后，如果?Proposer?收到了超過半數(shù)的?Acceptor?的批準(zhǔn)（Proposer?本身同意），那么此時?Proposer?會給所有的?Acceptor?發(fā)送真正的提案（你可以理解為第一階段為試探），這個時候?Proposer?就會發(fā)送提案的內(nèi)容和提案編號。

表決者收到提案請求后會再次比較本身已經(jīng)批準(zhǔn)過的最大提案編號和該提案編號，如果該提案編號?大于等于?已經(jīng)批準(zhǔn)過的最大提案編號，那么就?accept?該提案（此時執(zhí)行提案內(nèi)容但不提交），隨后將情況返回給?Proposer?。如果不滿足則不回應(yīng)或者返回 NO 。

當(dāng)?Proposer?收到超過半數(shù)的?accept?，那么它這個時候會向所有的?acceptor?發(fā)送提案的提交請求。需要注意的是，因為上述僅僅是超過半數(shù)的?acceptor?批準(zhǔn)執(zhí)行了該提案內(nèi)容，其他沒有批準(zhǔn)的并沒有執(zhí)行該提案內(nèi)容，所以這個時候需要向未批準(zhǔn)的?acceptor?發(fā)送提案內(nèi)容和提案編號并讓它無條件執(zhí)行和提交，而對于前面已經(jīng)批準(zhǔn)過該提案的?acceptor?來說?僅僅需要發(fā)送該提案的編號?，讓?acceptor?執(zhí)行提交就行了。

而如果?Proposer?如果沒有收到超過半數(shù)的?accept?那么它將會將?遞增?該?Proposal?的編號，然后?重新進入?Prepare?階段?。

對于?Learner?來說如何去學(xué)習(xí)?Acceptor?批準(zhǔn)的提案內(nèi)容，這有很多方式，讀者可以自己去了解一下，這里不做過多解釋。

二.Raft算法?

1 背景

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

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

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

1.1 拜占庭將軍問題

在介紹共識算法之前，先介紹一個簡化版拜占庭將軍的例子來幫助理解共識算法。

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

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

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

1.2 共識算法

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

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

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

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

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

• 安全。確保在非拜占庭條件（也就是上文中提到的簡易版拜占庭）下的安全性，包括網(wǎng)絡(luò)延遲、分區(qū)、包丟失、復(fù)制和重新排序。

• 高可用。只要大多數(shù)服務(wù)器都是可操作的，并且可以相互通信，也可以與客戶端進行通信，那么這些服務(wù)器就可以看作完全功能可用的。因此，一個典型的由五臺服務(wù)器組成的集群可以容忍任何兩臺服務(wù)器端故障。假設(shè)服務(wù)器因停止而發(fā)生故障；它們稍后可能會從穩(wěn)定存儲上的狀態(tài)中恢復(fù)并重新加入集群。

• 一致性不依賴時序。錯誤的時鐘和極端的消息延遲，在最壞的情況下也只會造成可用性問題，而不會產(chǎn)生一致性問題。

• 在集群中大多數(shù)服務(wù)器響應(yīng)，命令就可以完成，不會被少數(shù)運行緩慢的服務(wù)器來影響整體系統(tǒng)性能。

2 基礎(chǔ)

2.1 節(jié)點類型

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

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

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

2.2 任期

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

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

2.3 日志

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

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

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

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

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

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

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

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

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

• 該 Leader 的 term 號大于等于自己的 term 號，說明對方已經(jīng)成為 Leader，則自己回退為 Follower。
• 該 Leader 的 term 號小于自己的 term 號，那么會拒絕該請求并讓該節(jié)點更新 term。

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

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

4 日志復(fù)制

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

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

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

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

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

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

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

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

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

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

5 安全性

5.1 選舉限制

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

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

判斷日志新舊的方式：如果兩個日志的 term 不同，term 大的更新；如果 term 相同，更長的 index 更新。

5.2 節(jié)點崩潰

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

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

5.3 時間與可用性

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

broadcastTime << electionTimeout << MTBF

• broadcastTime：向其他節(jié)點并發(fā)發(fā)送消息的平均響應(yīng)時間；
• electionTimeout：選舉超時時間；
• MTBF(mean time between failures)：單臺機器的平均健康時間；

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

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

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

一般來說，broadcastTime 一般為?0.5～20ms，electionTimeout 可以設(shè)置為?10～500ms，MTBF 一般為一兩個月。

?參考文章：https://github.com/OneSizeFitsQuorum/raft-thesis-zh_cn/blob/master/raft-thesis-zh_cn.md

總結(jié)

以上是生活随笔為你收集整理的Paxos算法和Raft算法---经典的分布式系统一致性问题解决算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。