分布式基石｜最難 paxos 和最易 raft ？

什么是一致性協(xié)議？

注意，今天是大白話隨便聊聊，目的是直白的了解 raft 是什么，不用太摳理論定義。

什么是一致性協(xié)議？

字面理解就是讓某些東西保持一致的協(xié)議嘛。

什么是一致？

大白話就是內(nèi)容完全相同唄。以存儲場景舉例，假設(shè)有三個磁盤文件，大小為 1M ，如果三個文件 1M 的數(shù)據(jù)都完全相同，那么這可以說這文件的數(shù)據(jù)是一致的。

一致性還分了不同的等級，如線性、因果、最終一致性等等，而且如果站在不同的系統(tǒng)層面來看，承諾的一致性也會有所不同。這些今天都不重要，重要的是我們知道了：一致性協(xié)議就是用來達(dá)到一致的協(xié)議唄。

有兩個最出名的一致性協(xié)議：paxos 和 raft 。數(shù)學(xué)上已經(jīng)嚴(yán)格證明了 paxos 的正確性，只要嚴(yán)格遵守它協(xié)議的約束，就能保證在分布式的惡劣環(huán)境下多副本數(shù)據(jù)的一致。我們來看一下吧！

paxos 協(xié)議

paxos 是 Leslie Lamport 大神于 1990 年提出的一致性協(xié)議。它解決的問題是一個分布式系統(tǒng)如何就某個值（決議）達(dá)成一致。

劃重點：paxos 協(xié)議本質(zhì)是確定一個值。

論文《The part-time parliarment》提到的 paxos 里面有兩個重要角色：

• Proposer：提議發(fā)起者
• Acceptor：提議接受者

它們的操作對象就是：提議（ Proposal ） = 提議的值 提議編號。里面有三大"定律"，滿足這三大約束條件，那么就能保證一致性：

第一定律：每輪的投票編號唯一；

第二定律：投票滿足多數(shù)才算成功（并且如果任意兩次投票都存在多數(shù)派，則多數(shù)派的交集不為空）；

第三定律：如果一輪編號為 Bbal 的投票，多數(shù)派中任意一位成員曾投過 Bbal 編號小的票（B'），那么 Bdec == B'dec；

上面就是 paxos 最核心的內(nèi)容，但是說實話，每一個字都看得懂，但是連起來就不知道啥意思？

paxos 到底能做啥？這個我們存儲系統(tǒng)有啥關(guān)系？它為啥那么難懂？

paxos 難就難在于它沒告訴大家，這個東西能用來做啥，映射不到現(xiàn)實，就無法產(chǎn)生共鳴。

我們先接受一個事實：paxos 的本質(zhì)是確定一個值，且一旦這個值確定之后，后續(xù)無論怎么投票，無論發(fā)生什么，這個值保持不變。

那我就比以前更懵逼了！怎么越說越糊涂了了，說好的做一個分布式存儲服務(wù)嗎？存儲服務(wù)應(yīng)該允許可以寫入任何數(shù)據(jù)，且可以 Update 的嘛。

確定一個不能變的值有啥用？

paxos 的工程化

我們下面嘗試將 paxos 工程化，將它具現(xiàn)化到現(xiàn)實的工程實現(xiàn)。

1 確定一個值，有啥用？

回到最開始的問題，確定一個值對我們有啥用？

我們來簡要發(fā)散下 paxos 工程化的思路。

paxos 本質(zhì)：確定一個值，現(xiàn)在把這里面參與的角色打包起來，Proposer，Acceptor，Proposal 等等組成的抽象的集合：paxos instance，稱為 paxos 實例：

劃重點：每個實例必須是完全獨立，投票互不干涉，即可。

一個 instance 確定一個值，多個 instance 確定多個值。

這些值不斷的被確定（永不更改），形成了一個值序列，這有啥用？

2 確定多個值有啥用？

接著上面，我們現(xiàn)在有了一系列永遠(yuǎn)無法被修改了值序列，有啥用？存儲服務(wù)的基本特點是允許存儲任何數(shù)據(jù)，并且能夠增刪改。

哪還有啥用？

這一個個值序列像不像一個東西：日志！

這個跟 rocksdbdb，leveldb 的 wal 日志是不是差不多意思了？

我們應(yīng)用這些日志就能得到一致性的輸出。所以我們還缺個啥？

狀態(tài)機嘛。

3 加個狀態(tài)機就起飛了

什么是狀態(tài)機？

狀態(tài)機全稱為有限狀態(tài)機。它接收條件的觸發(fā)，由一種狀態(tài)轉(zhuǎn)變?yōu)樾碌臓顟B(tài)。初始狀態(tài)相同，輸入的一系列事件相同，那么它最終的狀態(tài)一定相同。

這可太常見了，比如 rocksdb，leveldb 等等 lsm 存儲，它們數(shù)據(jù)先寫 append log ，通過重放日志到達(dá)的系統(tǒng)狀態(tài)一定是一致的。

這種狀態(tài)機的應(yīng)用模式可不僅限于存儲服務(wù)。

到這，我相信童鞋們已經(jīng)很豁然開朗了，只要我們通過 paxos  來產(chǎn)生分布式一致的有序的操作日志，加上狀態(tài)機的配合，實現(xiàn)一個分布式存儲服務(wù)必然不是問題。

通過不停的確定一個個值，形成一個有序的操作系列，配合狀態(tài)機的應(yīng)用，這，就是 paxos 的工程化方向。

4 活鎖的問題怎么解決？

對于 paxos 來說，Proposer 和 Acceptor 角色是可以重疊的，每個節(jié)點既可以是 Proposer，也可以是 Acceptor ，或者兩者都是。

這帶來了非常大的靈活，每一個 Proposer 都可以遞交協(xié)議（寫入數(shù)據(jù)），但由于最終只能確定一個值，那么這會導(dǎo)致非常多的無效功，這期間是使用類似樂觀鎖來解決那些沖突的提議。

比如說，A 剛遞交一個提案，B 就遞交一個新提案導(dǎo)致 A 的提案被否定了，然后 A 又迅速遞交一個提案，形成了一種類似活鎖的狀態(tài)，這時間就浪費了呀。

怎么解決？

問題根因在于可以提案的點太多，大家都是平等的。那么統(tǒng)一聲音才能解決這個問題。于是Leader 就應(yīng)運而生。通過某種方法指定一個節(jié)點為 Leader ，只有一個節(jié)點能遞交提案，這樣就解決了混亂問題，效率提隨之提升（這就是 Multi-Paxos ）。

5 paxos 工程化小結(jié)

小結(jié)一下，如果要將一個 paxos 工程化落地，衍生了哪些東西：

1. paxos 本質(zhì)是確定一個值，把參與確定這個值的角色打包稱為一組實例（ paxos instance ）；2.不同實例之間決議互不干擾。多組 paxos 實例確定多個值，形成一組操作序列，也是就日志 ；
2. 日志 狀態(tài)機 可以成為任何有意義的工程系統(tǒng)；
3. 為了解決遞交提案混亂可能引發(fā)的效率問題（比如活鎖），可以通過指定 Leader 角色來解決；

慢著，這個工程化方向咋這么眼熟呢？

這不就是 raft ！

raft 協(xié)議

終于到了 raft 協(xié)議，raft 的論文開篇就是這么一段話：

Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos;

raft 證明和 paxos 等價，raft 是一種日志復(fù)制的一致性算法。

看懂了嗎？raft 的著眼點就是 日志 狀態(tài)機 的方向。

劃重點：raft 天生就是 paxos 協(xié)議工程化的一種樣子。

如下圖：

圖里交代了關(guān)鍵模塊：

1. 客戶端（ Client ）：就是用戶嘛，寫入數(shù)據(jù)的就是它嘍；
2. 一致性模塊（ Consensus Module ）：負(fù)責(zé)寫入 log，并且把 log 復(fù)制到其他節(jié)點；
3. 狀態(tài)機（ State Machine ）：輸入 log ，推進變更系統(tǒng)狀態(tài)；

raft 確實比 paxos 簡單啊，因為它已經(jīng)把實現(xiàn)程序交互的樣子都畫出來了。

在 raft 論文里面直接把幾個因素交代清楚了：

1. raft 就是管理日志復(fù)制的算法；
2. 日志 狀態(tài)機 就能落地一個一致性的系統(tǒng)應(yīng)用；
3. 集群角色有分類，Leader 作為唯一的寫入點，所有日志復(fù)制是 Leader 到 Follower 單項傳輸；

說實話，上面的這些知識點都是我們對 paxos 工程化的長時間推導(dǎo)才想明白的。

沒想到 raft 論文上來就給整好了，所以我才說，raft 協(xié)議出生就是為了解決工程化的問題的。

raft 把一致性歸納成三個核心問題：

1. Leader 的選舉；
2. 日志的復(fù)制；
3. 正確性的保證（約束條件）；

其實真正要做的就兩個，第三個問題貫穿前兩個事情：

1. 選出一個 Leader ；
2. 把 Leader 的日志復(fù)制分發(fā)到 Follower 節(jié)點；

我們下面來看下這兩個事情是怎么做的。

而用戶則只好奇兩個事情：

1. 數(shù)據(jù)怎么讀寫？
2. 節(jié)點擴縮容怎么搞？

1 Leader 選舉

角色轉(zhuǎn)變：

簡單看下 raft 協(xié)議中關(guān)于 Leader 選舉的部分。下面是角色轉(zhuǎn)化圖，非常清晰：

圖里至少能得到這么幾點知識點：

1. 系統(tǒng)開始每個節(jié)點都是從 Follower 角色開始；
2. 定時器超時之后，角色轉(zhuǎn)變?yōu)?Candidate ，開始競選 Leader；
3. Candidate 如果獲得多數(shù)人的支持，那么選舉成功，角色轉(zhuǎn)變?yōu)?Leader 。如果選舉失敗，那么退為 Follower ；

Leader 選舉成功之后則可以對外提供服務(wù)。

在論文中，為了讓選舉更高效（避免類似活鎖的場景），各個節(jié)點的定時器間隔是隨機值。

服務(wù)時間線：

從時間線來看，可以分為兩部分時間（如下圖）：

1. 無 Leader 狀態(tài)（選舉中）；
2. 正常狀態(tài)（ Leader ）；

每個 Leader 都有自己的任期，注意：無 Leader 的狀態(tài)是停服狀態(tài)。

Leader 選舉的規(guī)則？

被多數(shù)節(jié)點接受并且持久化的的日志叫做 committed log 。

說實話，Leader 選舉的規(guī)則其實就一條：具備完備的 committed 的 log 數(shù)據(jù)即可。

那怎么才能選出具有完備數(shù)據(jù)的節(jié)點呢？

這就是 raft 協(xié)議里安全性的內(nèi)容。投票發(fā)起者（ Candidate ）要告訴對方兩個東西：

1. 任期編號；
2. 當(dāng)前日志的最新位置；

其他節(jié)點（ Follower ）收到這兩個信息會決定要投它一票，還是拒絕它？

劃重點：做這個決定依賴于它的日志是不是比我新（全）。

那怎么判斷誰更新（全）呢？

1. 先比 term ，誰更大誰就新;
• 舉個例子，F(xiàn)ollower 節(jié)點保存的任期是 4，Candidate 發(fā)過來的是 3 ，這種就直接拒絕了；
2. 如果任期相同，那么就比較 index ，index 誰更大就新;
• 舉個例子，對面發(fā)過來的 index 是 7，我本地是的 8 ，那么就多說了，拒絕；

我們看一眼下圖，我們知道 raft 的操作對象就是日志。在 raft 協(xié)議中，每個日志都有唯一的編號：index ，代表了它唯一的槽位。

題外話：這里可以類比上面 paxos 章節(jié)說的 instance 概念。其實每一個日志槽位和其他模塊對象結(jié)合其他就是單獨的 instance ，這一系列的日志對象就類似于 paxos 多實例 instance 確定的值。

每個 index 槽位代表的值一旦確定將永不更改，它們的確認(rèn)不相互影響。

從完備的數(shù)據(jù)來看 committed 的位置在 index：7 這個位置。那么第一個節(jié)點、第三個節(jié)點、第五個節(jié)點都具備完備的數(shù)據(jù)，但是按照協(xié)議跑起來，只有第一個節(jié)點和第三個節(jié)點才有可能會成為 Leader 。因為它們兩個節(jié)點有最新的數(shù)據(jù)（雖然是沒有 commited 的），第五個節(jié)點找它們投票的時候，會被拒絕（它雖然有完備的數(shù)據(jù)，但是不夠新）。

2 日志復(fù)制

日志復(fù)制有幾個特點：

1. 日志傳輸為單向傳輸，Leader 到 Follower ；
2. Leader 永遠(yuǎn)不會改寫或者刪除自己的日志，永遠(yuǎn)只做 Append ；
3. 日志內(nèi)容一切以 Leader 為主，哪怕是強制覆蓋 ；

和 paxos 類似，每個日志槽位的值一旦確定就無法更改，無論怎么投票，怎么運轉(zhuǎn)，這個值不再變更。raft 就這樣連續(xù)的確定值就能形成一個的日志序列，給到狀態(tài)機使用。

這里類比 paxos 的 instance ，其實我們只需要保證每個槽位的投票和數(shù)據(jù)的獨立就和 instance 的是一個效果。

以這個圖為例，在不切主的情況下，數(shù)據(jù)從節(jié)點（1）向其他節(jié)點發(fā)送，補齊數(shù)據(jù)。

經(jīng)過狀態(tài)機應(yīng)用，所有的節(jié)點最終系統(tǒng)狀態(tài)一致：

• x = 4
• y = 7

思考一個問題：如果用戶寫失敗了，系統(tǒng)提供了什么結(jié)果語義？

劃重點：未定義。有可能寫入了，有可能沒寫入。這種場景只能依賴于用戶重試。標(biāo)準(zhǔn)的存儲服務(wù)寫失敗語義。

還是以上圖舉例，就拿 index：8 這個位置的寫入來說，用戶從節(jié)點（1）寫入數(shù)據(jù) x=4。

場景一：這個時候只把日志成功復(fù)制到節(jié)點（3）就掛了。用戶那邊自然是失敗的。節(jié)點（1）恢復(fù)后，還是又成為了 Leader ，由于 leader 永遠(yuǎn)不會刪改日志，所以最終還是會把 index 的日志復(fù)制到其他節(jié)點，等復(fù)制完之后，滿足 quroum 系統(tǒng)狀態(tài)就變了就變成 x=4 了。

場景二：一條日志沒寫入，那么系統(tǒng)狀態(tài)就還是 x=5 ；

所以，用戶寫入失敗的場景，一定要依賴重試。不能對結(jié)果假定。這種假定在存儲系統(tǒng)中通用。

關(guān)于 raft 日志復(fù)制，有個規(guī)則不得不提：Leader 永遠(yuǎn)不能 commit 非自己任期的日志。哪怕已經(jīng)滿足 quorum 。

為什么會有這個限定 ？

看一個 raft 論文中的簡單的例子：

這是一個時間序列，從 a -> b -> c -> d -> e ：

1. a 時刻：Leader 為 S1（ 黑框的為 Leader ），它有著最新的日志 index:2 ，雖然最新的 index:2 并沒有 committed（復(fù)制到多數(shù)），只復(fù)制到了 S2 ；
2. b 時刻：S1 掛了，S5 被選舉為 Leader ，任期為 3 ，并且 Client 還遞交了一個寫入；
3. c 時刻：S5 掛了，S1 被重新選舉為 Leader ，任期為 4，這個時候它復(fù)制日志，把 index:2 的日志復(fù)制給了 S1，S2，S3 ，這是滿足了 quorum （但注意了，這個系統(tǒng)千萬不能認(rèn)為 commit 了，且往后看）。并且 Client 還遞交了一個寫入在 index:3 的位置；
4. d 時刻：S1 掛了，S5 被重新選舉為 Leader（S2，S3，S4 都會投票），于是把 index:2 的日志強制覆蓋到所有節(jié)點；
5. e 時刻：這個時刻是一種假設(shè)，假設(shè)說，S1 在 c 時刻的時候在掛掉之前把任期 4，index:3 的日志復(fù)制到多數(shù)節(jié)點，那結(jié)果又不一樣了。這種場景系統(tǒng)可以認(rèn)為 index:3 被 commit 了，index:2 則是被間接 commit 了；

看到了嗎？

為什么在 c 時刻一直強調(diào)，不要認(rèn)為 index:2 滿足了 quorum 就認(rèn)為是 committed 的日志，然后就去 apply 。因為你一旦這樣做了，d 時刻的場景發(fā)生之后，index:2 的日志是被修改了。

這就導(dǎo)致 index:2 兩次 commit 了不同的 log ！這就違背了一個槽位確定一個值，永不更改的承諾。

這絕對不行。

怎么辦？

解決很簡單，上面已經(jīng)講了，在 c 時刻這種場景，就算 index:2 被復(fù)制到多數(shù)，滿足了 quorum 也不能認(rèn)為是 committed （ 沒有 commit 自然就不能 apply ），Leader 只能 commit 自己任期的日志。前面的日志將被間接的遞交。

再談?wù)?e 時刻為什么把 index:3 的日志復(fù)制到多數(shù)之后，就可以認(rèn)為 index:2 被 commit 了？

因為，這樣做了之后，將不可能出現(xiàn) d 時刻的場景。因為 S5 的任期只有 3 ！它將不可能成為 Leader 。

題外話：etcd 在每次選舉出 Leader 的第一件事就是廣播一條空白消息，原因就在這里。目的是為了間接 commit 掉前任的日志。

3 狀態(tài)機

這部分其實是最簡單的，狀態(tài)機做的事情我們叫做 apply 。apply 的內(nèi)容則是各個業(yè)務(wù)自行解釋，舉個例子，如下的日志，這是一個典型的 kv 系統(tǒng)的樣子：

日志 apply 完之后，系統(tǒng)狀態(tài)為：

x = 4
y = 7
劃重點：日志里面的內(nèi)容由業(yè)務(wù)自行解釋，raft 只保證日志復(fù)制是完全一致的。

4 Propose 遞交

用戶的入口就是從遞交 Propose 開始，由 Leader 接收用戶請求，然后封裝成日志的樣子，經(jīng)過了 commit（ 確定這個值 ）之后就能對外承諾。

思考一個小問題：集群只有一個 Leader ，如果請求發(fā)給了 Follower 呢？難不成 Client 還要專門記錄誰是 Leader ？

也沒關(guān)系，F(xiàn)ollower 可以透明轉(zhuǎn)發(fā)給 Leader 。Leader 處理好之后，回應(yīng)即可。

劃重點：還是那句話，只由 Leader 來發(fā)起，就算發(fā)給了 Follower ，請求也會轉(zhuǎn)發(fā) Leader。

5 成員變更

成員變更一般分為兩種場景：

1. 單節(jié)點變更
2. 多節(jié)點變更

場景一：單節(jié)點變更

這是絕對安全的，因為它不會直接影響 Leader 的地位。這種的處理也簡單。把集群變更的消息作為一條日志廣播到集群，被集群 commit 之后，就可以直接 apply 新配置了。

劃重點：集群變更也可以作為日志消息。 還是那句話，日志里面的內(nèi)容可以是任何東西，業(yè)務(wù)自行解釋。raft 只保證它的一致即可。

舉個栗子：

原始集群 （S1，S2，S3），現(xiàn)在擴容一臺 S4 ，只需要封裝一條 < add S4 > 這樣的日志消息，廣播到集群里就可以，等這條消息 commit 了，就可以變更配置了。

場景二：多節(jié)點變更

多節(jié)點的配置則不能這樣做，為什么？

因為怕一次性來的人太多，直接威脅到原有 Leader 的權(quán)威。如下：

比如說，原有集群 （ S1，S3，S3 ），一次性來了兩個 （ S4，S5 ），這就可能導(dǎo)致某個時刻出現(xiàn)兩個 Leader 的情況：

1. S1，S2 認(rèn)為 S1 是 Leader，在原有 3 節(jié)點的集群中，滿足多數(shù)，合法 ；
2. S3，S4，S5 認(rèn)為 S3 是 Leader ，在新的 5 節(jié)點集群中滿足多數(shù)，合法；

那這可不行，這不就腦裂了嘛。一個集群只能有一個 Leader ，不然就會出現(xiàn)數(shù)據(jù)混亂的情況。

那怎么解決這個問題呢？

通用的做法是 joint consensus 算法。其實這個算法很簡單，就是加一個中間過程，集群配置搞成兩階段切換，過程中要滿足新集群和老集群的同時的 quorum 投票。

這個圖怎么看不懂？我舉個栗子：

1. 最開始集群配置（ S1，S2，S3 ），我們暫且叫做 C_old ；
2. 遞交兩條集群變更的日志，Add S4，Add S5 ，Leader 向所有 S1，S2，S3 廣播日志；
3. 所有節(jié)點（ S1，S2，S3 ）收到這兩條日志，則代表這兩條日志被 commit 了，于是 apply 這兩條日志，apply 的行為：集群配置變更為（ S1，S2，S3，S4，S5 ）