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

什麼是一致性協議？

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

什麼是一致性協議？

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

什麼是一致？

大白話就是內容完全相同唄。以存儲場景舉例，假設有三個磁盤文件，大小爲 1M ，如果三個文件 1M 的數據都完全相同，那麼這可以說這文件的數據是一致的。

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

有兩個最出名的一致性協議：paxos 和 raft 。數學上已經嚴格證明了 paxos 的正確性，只要嚴格遵守它協議的約束，就能保證在分佈式的惡劣環境下多副本數據的一致。我們來看一下吧！

paxos 協議

paxos 是 Leslie Lamport 大神於 1990 年提出的一致性協議。它解決的問題是一個分佈式系統如何就某個值（決議）達成一致。

劃重點：paxos 協議本質是確定一個值。

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

• Proposer：提議發起者

• Acceptor：提議接受者

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

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

第二定律：投票滿足多數纔算成功（並且如果任意兩次投票都存在多數派，則多數派的交集不爲空）；

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

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

paxos 到底能做啥？這個我們存儲系統有啥關係？它爲啥那麼難懂？

paxos 難就難在於它沒告訴大家，這個東西能用來做啥，映射不到現實，就無法產生共鳴。

我們先接受一個事實：paxos 的本質是確定一個值，且一旦這個值確定之後，後續無論怎麼投票，無論發生什麼，這個值保持不變。

那我就比以前更懵逼了！怎麼越說越糊塗了了，說好的做一個分佈式存儲服務嗎？存儲服務應該允許可以寫入任何數據，且可以 Update 的嘛。

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

paxos 的工程化

我們下面嘗試將 paxos 工程化，將它具現化到現實的工程實現。

 1   確定一個值，有啥用？

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

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

paxos 本質：確定一個值，現在把這裏面參與的角色打包起來，Proposer，Acceptor，Proposal 等等組成的抽象的集合：paxos instance，稱爲 paxos 實例：

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

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

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

 2   確定多個值有啥用？

接着上面，我們現在有了一系列永遠無法被修改了值序列，有啥用？存儲服務的基本特點是允許存儲任何數據，並且能夠增刪改。

哪還有啥用？

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

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

我們應用這些日誌就能得到一致性的輸出。所以我們還缺個啥？

狀態機嘛。

 3   加個狀態機就起飛了

什麼是狀態機？

狀態機全稱爲有限狀態機。它接收條件的觸發，由一種狀態轉變爲新的狀態。初始狀態相同，輸入的一系列事件相同，那麼它最終的狀態一定相同。

這可太常見了，比如 rocksdb，leveldb 等等 lsm 存儲，它們數據先寫 append log ，通過重放日誌到達的系統狀態一定是一致的。

這種狀態機的應用模式可不僅限於存儲服務。

到這，我相信童鞋們已經很豁然開朗了，只要我們通過 paxos  來產生分佈式一致的有序的操作日誌，加上狀態機的配合，實現一個分佈式存儲服務必然不是問題。

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

 4   活鎖的問題怎麼解決？

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

這帶來了非常大的靈活，每一個 Proposer 都可以遞交協議（寫入數據），但由於最終只能確定一個值，那麼這會導致非常多的無效功，這期間是使用類似樂觀鎖來解決那些衝突的提議。

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

怎麼解決？

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

 5   paxos 工程化小結

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

1. paxos 本質是確定一個值，把參與確定這個值的角色打包稱爲一組實例（ paxos instance ）；2. 不同實例之間決議互不干擾。多組 paxos 實例確定多個值，形成一組操作序列，也是就日誌 ；

2. 日誌 + 狀態機 可以成爲任何有意義的工程系統；

3. 爲了解決遞交提案混亂可能引發的效率問題（比如活鎖），可以通過指定 Leader 角色來解決；

慢着，這個工程化方向咋這麼眼熟呢？

這不就是 raft ！

raft 協議

終於到了 raft 協議，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 是一種日誌複製的一致性算法。

看懂了嗎？raft 的着眼點就是 日誌 + 狀態機 的方向。

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

如下圖：

圖裏交代了關鍵模塊：

1. 客戶端（ Client ）：就是用戶嘛，寫入數據的就是它嘍；

2. 一致性模塊（ Consensus Module ）：負責寫入 log，並且把 log 複製到其他節點；

3. 狀態機（ State Machine ）：輸入 log ，推進變更系統狀態；

raft 確實比 paxos 簡單啊，因爲它已經把實現程序交互的樣子都畫出來了。

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

1. raft 就是管理日誌複製的算法；

2. 日誌 + 狀態機 就能落地一個一致性的系統應用；

3. 集羣角色有分類，Leader 作爲唯一的寫入點，所有日誌複製是 Leader 到 Follower 單項傳輸；

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

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

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

1. Leader 的選舉；

2. 日誌的複製；

3. 正確性的保證（約束條件）；

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

1. 選出一個 Leader ；

2. 把 Leader 的日誌複製分發到 Follower 節點；

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

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

1. 數據怎麼讀寫？

2. 節點擴縮容怎麼搞？

 1   Leader 選舉

角色轉變：

簡單看下 raft 協議中關於 Leader 選舉的部分。下面是角色轉化圖，非常清晰：

圖裏至少能得到這麼幾點知識點：

1. 系統開始每個節點都是從 Follower 角色開始；

2. 定時器超時之後，角色轉變爲 Candidate ，開始競選 Leader；

3. Candidate 如果獲得多數人的支持，那麼選舉成功，角色轉變爲 Leader 。如果選舉失敗，那麼退爲 Follower ；

Leader 選舉成功之後則可以對外提供服務。

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

服務時間線：

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

1. 無 Leader 狀態（選舉中）；

2. 正常狀態（ Leader ）；

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

Leader 選舉的規則？

被多數節點接受並且持久化的的日誌叫做 committed log 。

說實話，Leader 選舉的規則其實就一條：具備完備的 committed 的 log 數據即可。

那怎麼才能選出具有完備數據的節點呢？

這就是 raft 協議裏安全性的內容。投票發起者（ Candidate ）要告訴對方兩個東西：

1. 任期編號；

2. 當前日誌的最新位置；

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

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

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

1. 先比 term ，誰更大誰就新;

• 舉個例子，Follower 節點保存的任期是 4，Candidate 發過來的是 3 ，這種就直接拒絕了；

3. 如果任期相同，那麼就比較 index ，index 誰更大就新;

• 舉個例子，對面發過來的 index 是 7，我本地是的 8 ，那麼就多說了，拒絕；

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

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

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

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

 2   日誌複製

日誌複製有幾個特點：

1. 日誌傳輸爲單向傳輸，Leader 到 Follower ；

2. Leader 永遠不會改寫或者刪除自己的日誌，永遠只做 Append ；

3. 日誌內容一切以 Leader 爲主，哪怕是強制覆蓋 ；

和 paxos 類似，每個日誌槽位的值一旦確定就無法更改，無論怎麼投票，怎麼運轉，這個值不再變更。raft 就這樣連續的確定值就能形成一個的日誌序列，給到狀態機使用。

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

以這個圖爲例，在不切主的情況下，數據從節點（1）向其他節點發送，補齊數據。

經過狀態機應用，所有的節點最終系統狀態一致：

• x = 4

• y = 7

思考一個問題：如果用戶寫失敗了，系統提供了什麼結果語義？

劃重點：未定義。有可能寫入了，有可能沒寫入。這種場景只能依賴於用戶重試。標準的存儲服務寫失敗語義。

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

場景一：這個時候只把日誌成功複製到節點（3）就掛了。用戶那邊自然是失敗的。節點（1）恢復後，還是又成爲了 Leader ，由於 leader 永遠不會刪改日誌，所以最終還是會把 index 的日誌複製到其他節點，等複製完之後，滿足 quroum 系統狀態就變了就變成 x=4 了。

場景二：一條日誌沒寫入，那麼系統狀態就還是 x=5 ；

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

關於 raft 日誌複製，有個規則不得不提：Leader 永遠不能 commit 非自己任期的日誌。哪怕已經滿足 quorum 。

爲什麼會有這個限定 ？

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

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

1. a 時刻：Leader 爲 S1（ 黑框的爲 Leader ），它有着最新的日誌 index:2 ，雖然最新的 index:2 並沒有 committed（複製到多數），只複製到了 S2 ；

2. b 時刻：S1 掛了，S5 被選舉爲 Leader ，任期爲 3 ，並且 Client 還遞交了一個寫入；

3. c 時刻：S5 掛了，S1 被重新選舉爲 Leader ，任期爲 4，這個時候它複製日誌，把 index:2 的日誌複製給了 S1，S2，S3 ，這是滿足了 quorum （但注意了，這個系統千萬不能認爲 commit 了，且往後看）。並且 Client 還遞交了一個寫入在 index:3 的位置；

4. d 時刻：S1 掛了，S5 被重新選舉爲 Leader（S2，S3，S4 都會投票），於是把 index:2 的日誌強制覆蓋到所有節點；

5. e 時刻：這個時刻是一種假設，假設說，S1 在 c 時刻的時候在掛掉之前把任期 4，index:3 的日誌複製到多數節點，那結果又不一樣了。這種場景系統可以認爲 index:3 被 commit 了，index:2 則是被間接 commit 了；

看到了嗎？

爲什麼在 c 時刻一直強調，不要認爲 index:2 滿足了 quorum 就認爲是 committed 的日誌，然後就去 apply 。因爲你一旦這樣做了，d 時刻的場景發生之後，index:2 的日誌是被修改了。

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

這絕對不行。

怎麼辦？

解決很簡單，上面已經講了，在 c 時刻這種場景，就算 index:2 被複制到多數，滿足了 quorum 也不能認爲是 committed （ 沒有 commit 自然就不能 apply ），Leader 只能 commit 自己任期的日誌。前面的日誌將被間接的遞交。

再談談 e 時刻爲什麼把 index:3 的日誌複製到多數之後，就可以認爲 index:2 被 commit 了？

因爲，這樣做了之後，將不可能出現 d 時刻的場景。因爲 S5 的任期只有 3 ！它將不可能成爲 Leader 。

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

 3   狀態機

這部分其實是最簡單的，狀態機做的事情我們叫做 apply 。apply 的內容則是各個業務自行解釋，舉個例子，如下的日誌，這是一個典型的 kv 系統的樣子：

日誌 apply 完之後，系統狀態爲：

x = 4
y = 7

劃重點：日誌裏面的內容由業務自行解釋，raft 只保證日誌複製是完全一致的。

 4   Propose 遞交

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

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

也沒關係，Follower 可以透明轉發給 Leader 。Leader 處理好之後，迴應即可。

劃重點：還是那句話，只由 Leader 來發起，就算髮給了 Follower ，請求也會轉發 Leader。

 5   成員變更

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

1. 單節點變更

2. 多節點變更

場景一：單節點變更

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

劃重點：集羣變更也可以作爲日誌消息。 還是那句話，日誌裏面的內容可以是任何東西，業務自行解釋。raft 只保證它的一致即可。

舉個栗子：

原始集羣 （S1，S2，S3），現在擴容一臺 S4 ，只需要封裝一條 這樣的日誌消息，廣播到集羣裏就可以，等這條消息 commit 了，就可以變更配置了。

場景二：多節點變更

多節點的配置則不能這樣做，爲什麼？

因爲怕一次性來的人太多，直接威脅到原有 Leader 的權威。如下：

比如說，原有集羣 （ S1，S3，S3 ），一次性來了兩個 （ S4，S5 ），這就可能導致某個時刻出現兩個 Leader 的情況：

1. S1，S2 認爲 S1 是 Leader，在原有 3 節點的集羣中，滿足多數，合法 ；

2. S3，S4，S5 認爲 S3 是 Leader ，在新的 5 節點集羣中滿足多數，合法；

那這可不行，這不就腦裂了嘛。一個集羣只能有一個 Leader ，不然就會出現數據混亂的情況。

那怎麼解決這個問題呢？

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

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

1. 最開始集羣配置（ S1，S2，S3 ），我們暫且叫做 C_old ；

2. 遞交兩條集羣變更的日誌，Add S4，Add S5 ，Leader 向所有 S1，S2，S3 廣播日誌；

3. 所有節點（ S1，S2，S3 ）收到這兩條日誌，則代表這兩條日誌被 commit 了，於是 apply 這兩條日誌，apply 的行爲：集羣配置變更爲（ S1，S2，S3，S4，S5 ）&（ S1，S2，S3 ），俗稱 C_old,new ；

4. 在 etcd 中，對應  enter joint 的操作；

5. 開始遞交一個切換配置的日誌消息（ etcd 裏面叫做 ConfChangeV2 ），並且廣播這條配置；

6. 所有節點（ S1，S2，S3，S4，S5 ）收到這條日誌則代表這條日誌被 commit，於是可以 apply 這條日誌，apply 的行爲：集羣配置變更爲（ S1，S2，S3，S4，S5 ），這個配置就是 C_new，至此，配置變更結束；

重點提一下：在 C_old，C_new 階段如果收到寫請求，需要滿足兩份配置的 quorum 同意才能 commit 。

這樣就解決了雙 Leader 的問題。

總結

1. paxos 協議的本質是確定一個值，不同的 instance 確定多個值就成了日誌序列；

2. 日誌 + 狀態機就能實現任何系統，存儲服務只是其一；

3. raft 協議和 paxos 等價，它天然就是 paxos 工程化的一種樣子；

4. Leader 選舉，日誌複製，Leader 的安全性約束是 raft 的三大核心問題；

5. raft 的日誌裏面可以是任何內容，裏面的含義由業務 apply 的時候自行解析；

6. raft 單節點變更可以隨意搞，多節點變更需要用 joint consensus 算法走兩階段變更，才能防止多 Leader 的腦裂情況；

後記

從 paxos 到 raft ，簡單聊聊，爲後面 etcd 的一些分享做鋪墊。點贊、在看 是對奇伢最大的支持。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/C8Mgl9ebMAG0hh6ekoO58w