從 Paxos 到 Raft，分佈式一致性算法解析

後臺服務架構經過了集中式、SOA、微服務和服務網格四個階段，目前互聯網界大都使用微服務和服務網格。服務從集中式、中心化向分佈式、去中心化不斷演進，服務也變得更靈活，能夠自動擴縮容、快速版本迭代等。但是分佈式架構也將集中式下一些問題放大，比如通信故障、請求三態（成功、失敗、超時）、節點故障等，這些問題會導致一系例數據不一致的問題，也是計算機領域的老大難問題。本文將與大家一起學習分佈式一致性算法，因作者水平有限，若文中有不正處，還請多多指導。文章作者：董友康，騰訊 PCG 研發工程師。

理論是指導業界實現的綱領，也是提煉了多年研究的精華，在分佈式一致性領域，最主要的指導理論是 CAP 和 BASE 兩個。

1. CAP 理論

CAP 理論是 Eric Brewer 教授在 2000 年提出 的，是描述分佈式一致性的三個維度，分別是指：

（1）一致性（Consistency）

每次讀操作都能保證返回的是最新數據；在分佈式系統中，如果能針對一個數據項的更新執行成功後，所有的請求都可以讀到其最新的值，這樣的系統就被認爲具有嚴格的一致性。

（2）可用性（Availablity）

任何一個沒有發生故障的節點，會在合理的時間內返回一個正常的結果，也就是對於每一個請求總能夠在有限時間內返回結果。

（3）分區容忍性（Partition-torlerance）

當節點間出現網絡分區，照樣可以提供滿足一致性和可用性的服務，除非整個網絡環境都發生了故障。那麼，什麼是網絡分區呢？分區是系統中可能發生的故障之一，可能有節點暫時無法提供服務：發生了像 長時間 GC、CPU 死循環、鏈接池耗盡或者是網絡通信故障等問題。

CAP 指出，一個分佈式系統只能滿足三項中的兩項而不可能滿足全部三項。舉例來看：如下圖所示，假設有五個節點：n1~n5 ，因網絡分區故障被分成兩組：[n1、n2] 和 [n3~n5]，那麼當 n1 處理客戶端請求時（爲了支持 "容忍網絡分區"，即支持 P）：

  1. 如果要保證 C(一致性)，那麼它需要把消息複製到所有節點，但是網絡分區導致無法成功複製到 n3~n5，所以它只能返回 "處理失敗" 的結果給客戶端。（這時系統就處於不可用狀態，即喪失了 A） 

  2. 如果要保證可用性 A，那麼 n1 就只能把消息複製到 n2，而不用複製到 n3~n5(或者無視複製失敗 / 超時)，但 n3 同時也可能在處理客戶端請求，n3 也爲了保證 A 而做了同樣的處理。那麼 [n1、n2]和 [n3~n5] 的狀態就不一致了，於是就喪失了 C(一致性)。

  3. 如果不容忍網絡分區，則 P（分區容忍性）不能滿足。

既然 CAP 理論無法全部滿足，爲了指導工業實現，就需要降低標準，因此出現了 BASE 理論。

2. BASE 理論

BASE 理論是 eBay 的架構師 Dan Pritchett 提出的，它的思想是：“即使無法做到強一致性，但每個應用都可以根據自身的業務特點，採用適當的方式來使系統達到最終一致性” 。

BASE 理論有三項指標：

BASE 理論面向的是大型高可用、可擴展的分佈式系統。BASE 通過犧牲強一致性來獲得可用性，並允許數據短時間內的不一致，但是最終達到一致狀態。

接下來，我們一起學習經典的分佈式算法。

二、經典分佈式算法

1. PAXOS 算法

Paxos 算法是 Leslie Lamport 在 1990 年提出的，經典且完備的分佈式一致性算法。Leslie 大佬也在這個算法中展示了他不同常人的智商。

該算法的目標是：在不同的節點間，對一個 key 的取值達成共識（同一個值）。

（1）角色

協議將系統中的節點分爲三種角色：Proposer（提案者）、Acceptor（決議者）、Leaner（學習者），他們的具體職責爲：

（2）約束條件推導

本小節將通過推導來引出 Paxos 算法的約束條件，故事靈感來自於分佈式理論：深入淺出 Paxos 算法【1】，在原文基礎上優化了可讀性。

https://my.oschina.net/u/150175/blog/2992187

在介紹 paxos 算法協議前，我們先來看一個故事，故事名叫《小明姓什麼》。在孤兒院長大的小明馬上就要步入社會了，但是孤兒院的老師還沒有找到小明的姓氏，因此決定開會解決這個問題。

在會議上，由提案者 P 提出姓氏，然後決議者 A 來決定選擇哪一個。

場景 1: Pa 向 A1 提出 “趙”， Pb 向 A2，A3 提出 “錢”。現在有超過半數的決策者接受了 “錢”，所以最終的決策結果就是 “錢”。

這裏引出了一個基礎的約束條件：

P0. 當集羣中，超過半數的 Acceptor 接受了一個議案，那我們就可以說這個議案被選定了（Chosen）

P0 是完備的條件，但是不實用。

場景 2 ：Pa 向 A1 提出 “趙”， Pb 向 A2 提出 “錢”, Pc 向 A3 提出 “孫”，這樣就出現了三個決議者各執一票，無法形成多數派決議的局面。

因此，必須允許一個決策者能夠接受多個議案，後接受的議案可以覆蓋之前的議案。這樣，Pc 可以向所有決策者提起議案 “孫”，形成一個多數派決議。

但是，現在 Pa Pb 提案者也可以利用重新提案的能力，來重新提出自己的提案，導致形成的共識重新被推翻。會議亂成了一鍋粥。因此還需要新的約束條件來保證會議正常進行。

我們提煉一下問題：在不同版本的提案中，選擇一個固定的值作爲全局決議。

Paxos 算法就是爲解決這種不一致問題而提出的，算法目標有兩個：

首先介紹一個概念 “編號”：編號在算法中是唯一自增的鍵值，假設第一個提出的議案版本是 n1， 接下來提出的第二個議案版本 n2 = n1+1 。有了編號之後，一條提案也變成了（Num， Value）二元組。

爲了達成上述目標，算法提出了一組約束條件：

P1：一個 Acceptor 必須接受它收到的第一個議案。
P2：如果一個值爲 v 的議案被選定了，那麼被選定的更大編號的議案，它的值必須也是 v。
a：如果一個值爲 v 的議案被選定了，那麼 Acceptor 接受的更大編號的議案，它的值必須也是 v。
b：如果一個值爲 v 的議案被選定了，那麼 Proposer 提出的更大編號的議案，它的值必須也是 v。

P2 和 P2a、P2b 理解起來比較費勁。P2 這個約束是爲了解決上述場景 2 中，形成決議後又被推翻覆蓋的問題。有了約束 2 之後，當形成了決議 “孫”，則後續提出的議案的值必須爲 “孫”。

那麼，如何才能滿足 P2 呢，P2a 約束是在場景 2 的問題決策域提出的。爲了能夠滿足 P2a，自然可以在問題的產生域也提出約束， 既 P2b。如果算法能夠滿足 P2b，也就是將解決 “產生一致性問題” 的時機提前。所以，P2b 是 P2a 的充分條件，只要能滿足 P2b，那 P2a 就自動滿足。

那麼，作爲提案者，如何提前知道一個目前的決議（多數派）議案呢？接下來，我們就提出了新的約束 P2c：

P2c: 在所有 Acceptor 中，任意選取半數以上的集合，稱這個集合爲 S。Proposal 新的提案 Pnew （Nnew , Vnew ）必須符合下面兩個條件之一：  1）如果 S 中所有 Acceptor 都沒有接受過議案，那麼 Pnew 的編號保證唯一性和遞增，Pnew 的值可以是任意值。  2）如果 S 中有 Acceptor 曾經接受過議案，找出編號最大的議案 PN (N,V) 。那麼 Pnew 的編號必須大於 N，Pnew 的值必須等於 V。

在 P2c 中，引入了多數派集合 S。根據集合 S 中是否有被接受的議案，來推斷全局節點是否已經形成決議。根據約束 P0，如果一個議案（Nchosen, Vchosen）是被選中的，那麼它必然是被多於半數節點選中的。那麼，在任意一個多數派集合 S 中，一定會存在至少一個節點 A，它的數據中已經決議的議案是（Nchosen, Vchosen）。

反之，如果多數派集合中沒有被決議的議案，表示此時系統中還沒有一個被選定的決議。

看這個例子，假設目前選定了（3， Va）狀態；下次發起提案時，proposer 選定 A3、4、5 作爲集合 S 進行查詢；提出了編號爲 4 的提案，在 P2c 約束條件下，提案必定爲（4，Va）。

因此，滿足 P2c 的算法也滿足 P2b 算法。

但是也可能存在這種情況，當 proposer 發查詢請求時，還沒有一個被確認的提案，所以發出了 (4, Vb) 提案，這樣還是會破壞 P2b 約束。

因此，當一個議案在提出時（即使已經在發送的半路上了），它必須能夠知道當前已經提出的議案的最大編號。這聽起來很魔幻，畢竟跑在網線上的請求很難被召回。因此，我們提出了新的約束條件；

P3：議案（n，v）在提出前，必須將自己的編號通知給半數以上的 Acceptor。收到通知的 Acceptor 將 n 跟自己之前收到的通知進行比較，如果 n 更大，就將 n 確認爲最大編號。當半數以上 Acceptor 確認 n 是最大編號時，議案（n，v）才能正式提交。

P4：Acceptor 收到一個新的編號 n，在確認 n 比自己之前收到的編號大時，必須承諾不再接受比 n 小的議案。

有了 P3 的約束，則能夠保證兩個不同編號的議案，不可能同時被認爲是最大編號；同時再加上 P4 約束，保證了一個決議者不會對自己接受的議案版本進行回退。
至此，Paxos 算法的約束條件就介紹完了。

（3）協議流程

在 Paxos 中，一個決策過程（Round、Phase）分爲兩個階段：

phase1（準備階段）：

  1. Proposer 向超過半數（n/2+1）Acceptor 發起 prepare 消息 (發送編號)；

  2. 如果 Acceptor 收到一個編號爲 N 的 Prepare 請求，且 N 大於該 Acceptor 已經響應過的所有 Prepare 請求的編號，那麼它就會將它已經接受過的編號最大的提案（如果有的話）作爲響應反饋給 Proposer，同時該 Acceptor 承諾不再接受任何編號小於 N 的提案。否則拒絕返回。

phase2（決議階段或投票階段）：

  1. 如果超過半數 Acceptor 回覆 promise，Proposer 向 Acceptor 發送 accept 消息。注意此時的 V：V 就是收到的響應中編號最大的提案的，如果響應中不包含任何提案，那麼 V 就由 Proposer 自己決定；

  2. Acceptor 檢查 accept 消息是否符合規則，只要該 Acceptor 沒有對編號大於 N 的 Prepare 請求做出過響應，它就接受該提案。

在實際發展中，Paxos 算法也演變出一系列變種：

2. Raft 算法

Paxos 協議從被提出，一直是分佈式一致性算法的標準協議，但是它不易理解，對於工程師來說實現起來很複雜，以至於算法提出近 30 年都沒有一個完全版的實現方案。業界很多實現都是 Paxos-like。

Raft 算法是斯坦福大學 2017 年提出，論文名稱《In Search of an Understandable Consensus Algorithm》，望文生義，該算法的目的是易於理解。Raft 這一名字來源於 "Reliable, Replicated, Redundant, And Fault-Tolerant"（“可靠、可複製、可冗餘、可容錯”）的首字母縮寫。

Raft 使用了分治思想把算法流程分爲三個子問題：選舉（Leader election）、日誌複製（Log replication）、安全性（Safety）三個子問題。

（1）概念介紹

在 Raft 中，節點被分爲 Leader Follower Cabdidate 三種角色：

Term：是有連續單調遞增的編號，每個 term 開始於選舉階段，一般由選舉階段和領導階段組成。

隨機超時時間：Follower 節點每次收到 Leader 的心跳請求後，會設置一個隨機的，區間位於 [150ms, 300ms) 的超時時間。如果超過超時時間，還沒有收到 Leader 的下一條請求，則認爲 Leader 過期 / 故障了。

心跳續命：Leader 在當選期間，會以一定時間間隔向其他節點發送心跳請求，以維護自己的 Leader 地位。

（2）協議流程

a. 選舉流程

當某個 follower 節點在超時時間內未收到 Leader 的請求，它則認爲當前 Leader 宕機或者當前無 Leader，將發起選舉， 既從一個 Follower 變成 Candidate。

這個轉變過程中會發生四件事：

在這個過程中，其他 Follower 節點收到拉票請求後，需要判斷請求的合法性，然後爲第一個到達的合法拉票請求進行投票。投票過程對於 Follower 的約束有三點：

如果一個 Candidate 收到了超過半數的投票，則該節點晉升爲 Leader，會立刻給所有節點發消息，廣而告之，避免其餘節點觸發新的選舉；開始進行日誌同步、處理客戶端請求等。

如果一次選舉中，Candidate 在選舉超時時間內沒有收到超過半數的投票，也沒有收到其他 Leader 的請求，則認爲當前 Term 選舉失敗，進入下一個選舉週期。

b. 日誌複製

在瞭解日誌同步前，需要了解 “複製狀態機” 這個概念。

**複製狀態機（Replicated state machines）**是指：不同節點從相同的初始狀態出發，執行相同順序的輸入指令集後，會得到相同的結束狀態。

If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

分佈式一致性算法的實現是基於複製狀態機的。

在 Raft 算法中，節點初始化後具有相同初始狀態。爲了提供相同的輸入指令集這個條件，raft 將一個客戶端請求（command）封裝到一個 log entry 中。Leader 負責將這些 log entries 複製到所有的 Follower 節點，然後節點按照相同的順序應用 commands，達到最終的一致狀態。

當 Leader 收到客戶端的寫請求，到將執行結果返回給客戶端的這個過程，從 Leader 視角來看經歷了以下步驟：

logs 由順序排列的 log entry 組成 ，每個 log entry 包含 command 和產生該 log entry 時的 leader term。從上圖可以看到，五個節點的日誌並不完全一致，raft 算法爲了保證高可用，並不是強一致性，而是最終一致性，leader 會不斷嘗試給 follower 發 log entries，直到所有節點的 log entries 都相同。

在前面的流程中，leader 只需要日誌被複制到大多數節點即可向客戶端返回，而一旦向客戶端返回成功消息，那麼系統就必須保證 log 在任何異常的情況下都不會發生回滾。

這裏推薦兩個 Raft 算法動畫演示，通過動畫能夠對 Raft 算法的選舉和日誌複製過程有直觀清晰的認知。

在動畫演示中，可以通過調整時間流速和時間軸來觀察節點間通信。

也可以通過單擊節點或者請求包來查看節點的具體狀態和請求包的數據。

3. 安全性及約束

（1）選舉安全性

即任一任期內最多一個 leader 被選出。在一個集羣中任何時刻只能有一個 leader。系統中同時有多餘一個 leader，被稱之爲腦裂（brain split），這是非常嚴重的問題，會導致數據的覆蓋丟失。

在 raft 中，通過兩點保證了這個屬性：

（2）日誌 append only

首先，leader 在某一 term 的任一位置只會創建一個 log entry，且 log entry 是 append-only。

其次，一致性檢查。leader 在 AppendEntries 請求中會包含最新 log entry 的前一個 log 的 term 和 index，如果 follower 在對應的 term index 找不到日誌，那麼就會告知 leader 日誌不一致， 然後開始同步自己的日誌。同步時，找到日誌分叉點，然後將 leader 後續的日誌複製到本地。

（3）日誌匹配特性

如果兩個節點上的某個 log entry 的 log index 相同且 term 相同，那麼在該 index 之前的所有 log entry 應該都是相同的。

Raft 的日誌機制提供兩個保證，統稱爲 Log Matching Property：

**（4）Leader 完備性 **

被選舉人必須比自己知道的更多（比較 term 、log index）。

如果一個 log entry 在某個任期被提交（committed），那麼這條日誌一定會出現在所有更高 term 的 leader 的日誌裏面 。選舉人必須比自己知道的更多（比較 term，log index）如果日誌中含有不同的任期，則選最新的任期的節點；如果最新任期一致，則選最長的日誌的那個節點。

選舉安全性中包含了 Leader 完備性

（5）狀態機安全性

狀態機安全性由日誌的一致來保證。在算法中，一個日誌被複制到多數節點纔算 committed， 如果一個 log entry 在某個任期被提交（committed），那麼這條日誌一定會出現在所有更高 term 的 leader 的日誌裏面。

三、總語

    

分佈式算法已經經歷了近 40 年的發展（1982- ），湧現出各種各樣的算法。正如 Chubby 的作者所說：

“這個世界上只有一種一致性算法，那就是 Paxos”

Paxos 算法的貢獻和地位無可替代。理解了 Paxos 算法，再去理解其他算法，則會勢如破竹。
    

Raft 算法以其易於理解和實現的特性，推動分佈式一致性算法進入了廣泛應用階段，不再是工程師心中的那顆拿得起，放不下的硃砂痣。🐶

分佈式一致性算法的前沿理論也在飛速發展着，值得我們繼續學習和關注。

參考資料：

Paxos：

Raft：

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

猜你喜歡