Distributed Consensus Algorithm

There is only one consensus protocol, and that's “Paxos” — all other approaches are just broken versions of Paxos

世界上只有一種共識協(xié)議馏谨，就是 Paxos，其他所有共識算法都是 Paxos 的退化版本示姿。

—— Mike Burrows析砸，Inventor of Google Chubby

問題產(chǎn)生的背景

Paxos 問題是指分布式的系統(tǒng)中存在故障（fault），但不存在惡意（corrupt）節(jié)點場景（即可能消息丟失或重復，但無錯誤消息）下的共識達成（Consensus）問題南捂。因為最早是 Leslie Lamport 用 Paxon 島的故事模型來進行描述而命名。

• 少數(shù)服從多數(shù)鳖眼，最終達成一致意見。
• 基于消息傳遞且具有高度容錯特性的一致性算法嚼摩，是目前公認的解決分布式一致性問題最有效的算法之一钦讳。
• Paxos 是第一個被證明的共識算法，其原理基于 兩階段提交 并進行擴展枕面。

Paxos 算法分為核心算法和完整算法兩部分愿卒。Paxos 算法的核心部分解決了分布式領(lǐng)域當中非常重要的基礎問題，也就是共識問題潮秘；完整算法是用來實現(xiàn)狀態(tài)機的算法琼开。

兩個比較明顯的缺點：

1. 難以理解
2. 工程實現(xiàn)更難。

共識問題

不嚴格地說枕荞，共識問題就算多個進程對一個值達成一致柜候，每個進程都可以提議（propose）一個自己想要的值，但是最終只有一個值會被選中躏精，并且所有進程對這個選中的值達成一致渣刷。

共識算法注意點

• 可以是任意多個進程
• 所有進程都可以提議一個值
• 所有進程都可以學習到被選中的值

共識算法的要求

共識算法有兩個要求，安全要求和存活要求

安全要求是指：

• 只有一個被提議的值可能被選中
• 只有唯一的一個值被選中
• 只有一個值實際已經(jīng)被選中矗烛，一個進程才能學習到這個值

存活要求是指：某個被提議的值最終一定會被選中辅柴，并且如果一個值被選中，那么一個進程最終能夠?qū)W習到這個值瞭吃。

Paxos共識算法

算法的角色

作為現(xiàn)在共識算法設計的鼻祖碌嘀，以最初論文的難懂（算法本身并不復雜）出名。算法中將節(jié)點分為三種類型：

• proposer：提出一個提案歪架，等待大家批準為結(jié)案股冗。往往是客戶端擔任該角色；
• acceptor：負責對提案進行投票和蚪。往往是服務端擔任該角色魁瞪；
• learner：被告知結(jié)案結(jié)果穆律，并與之統(tǒng)一，不參與投票過程导俘÷驮牛可能為客戶端或服務端。

在多副本狀態(tài)機中旅薄，每個副本同時具有Proposer辅髓、Acceptor、Learner三種角色少梁。

Paxos-Roles

并且洛口，算法需要滿足 safety 和 liveness 兩方面的約束要求（實際上這兩個基礎屬性是大部分分布式算法都該考慮的）：

• safety：保證決議結(jié)果是對的，無歧義的凯沪，不會出現(xiàn)錯誤情況第焰。

  • 決議（value）只有在被 proposers 提出的 proposal 才能被最終批準；
  • 在一次執(zhí)行實例中妨马，只批準（chosen）一個最終決議挺举，意味著多數(shù)接受（accept）的結(jié)果能成為決議；

• liveness：保證決議過程能在有限時間內(nèi)完成烘跺。

  • 決議總會產(chǎn)生湘纵，并且 learners 能獲得被批準（chosen）的決議。

基本過程包括 proposer 提出提案滤淳，先爭取大多數(shù) acceptor 的支持梧喷，超過一半支持時，則發(fā)送結(jié)案結(jié)果給所有人進行確認脖咐。一個潛在的問題是 proposer 在此過程中出現(xiàn)故障铺敌，可以通過超時機制來解決。極為湊巧的情況下屁擅，每次新的一輪提案的 proposer 都恰好故障适刀，系統(tǒng)則永遠無法達成一致（概率很小）煤蹭。

Paxos 能保證在超過的正常節(jié)點存在時笔喉，系統(tǒng)能達成共識。

讀者可以試著自己設計一套能達成共識的方案硝皂，會發(fā)現(xiàn)在滿足各種約束情況下常挚，算法自然就會那樣設計。

考慮的場景

單個提案者+多接收者

如果系統(tǒng)中限定只有某個特定節(jié)點是提案者稽物，那么一致性肯定能達成（只有一個方案奄毡，要么達成，要么失敱椿颉）吼过。提案者只要收到了來自多數(shù)接收者的投票锐秦，即可認為通過，因為系統(tǒng)中不存在其他的提案盗忱。

但一旦提案者故障酱床，則系統(tǒng)無法工作。

多個提案者+單個接收者

限定某個節(jié)點作為接收者趟佃。這種情況下扇谣，共識也很容易達成，接收者收到多個提案闲昭，選第一個提案作為決議罐寨，拒絕掉后續(xù)的提案即可。

缺陷也是容易發(fā)生單點故障序矩，包括接收者故障或首個提案者節(jié)點故障鸯绿。

以上兩種情形其實類似主從模式，雖然不那么可靠簸淀，但因為原理簡單而被廣泛采用瓶蝴。

當提案者和接收者都推廣到多個的情形，會出現(xiàn)一些挑戰(zhàn)啃擦。

多個提案者+多個接收者

既然限定單提案者或單接收者都會出現(xiàn)故障囊蓝，那么就得允許出現(xiàn)多個提案者和多個接收者饿悬。問題一下子變得復雜了令蛉。

一種情況是同一時間片段（如一個提案周期）內(nèi)只有一個提案者，這時可以退化到單提案者的情形狡恬。需要設計一種機制來保障提案者的正確產(chǎn)生珠叔，例如按照時間、序列弟劲、或者大家猜拳（出一個數(shù)字來比較）之類祷安。考慮到分布式系統(tǒng)要處理的工作量很大兔乞，這個過程要盡量高效汇鞭，滿足這一條件的機制非常難設計。

另一種情況是允許同一時間片段內(nèi)可以出現(xiàn)多個提案者庸追。那同一個節(jié)點可能收到多份提案霍骄，怎么對他們進行區(qū)分呢？這個時候采用只接受第一個提案而拒絕后續(xù)提案的方法也不適用淡溯。很自然的读整，提案需要帶上不同的序號。節(jié)點需要根據(jù)提案序號來判斷接受哪個咱娶。比如接受其中序號較大（往往意味著是接受新提出的米间，因為舊提案者故障概率更大）的提案强品。

如何為提案分配序號呢？

一種可能方案是每個節(jié)點的提案數(shù)字區(qū)間彼此隔離開屈糊，互相不沖突的榛。為了滿足遞增的需求可以配合用時間戳作為前綴字段。

此外另玖，提案者即便收到了多數(shù)接收者的投票困曙，也不敢說就一定通過。因為在此過程中系統(tǒng)可能還有其它的提案谦去。

算法的選擇值和學習值的過程

共識算法分為兩個過程慷丽，即選擇一個值和學習一個值，具體如下：

• 在選擇一個值的過程中鳄哭，一組 proposer 中每一個 proposer 都可以提議任意一個值給一組 acceptor 要糊，這組 acceptor 會從所有的 proposer 提議的值中選出唯一的一個值。
• 在學習一個值的過程中妆丘，learner 從 acceptor 中學習到被選中的值

選擇值具體過程

選擇值過程是一個二階提交的過程锄俄，第一階段選擇提議編號，第二階段接受提議的值勺拣。

• 1.1：一個 proposer 生成一個新的提議編號 n奶赠，n 大于上一次使用的提議編號。并且發(fā)送 prepare(n) 消息給大多數(shù) acceptor

• 1.2：如果一個 acceptor 收到一個提議消息药有，并且 n 大于本地承諾過的提議編號毅戈，則用 n 更新本地承諾過的提議編號。如果有接受過其他的提議愤惰，則將提議的編號和值一起返回苇经，如果沒有返回提議的編號和 null；

• 2.1：如果一個 proposer 收到大多數(shù) acceptor 回復的承諾編號為 n 的 promise 消息宦言，則構(gòu)建一個新的提議扇单，提議編號為 n，提議值為 v奠旺。v 按照如下規(guī)則確定：

• 如果在所有的這些 promise 消息中有攜帶提議的蜘澜，則用提議編號最大的提議中的值

• 如果在所有的這些 promise 消息中沒有攜帶提議的，則可以用 proposer 自己要提議的值响疚。這個 proposer 給這些 acceptor 中的每一個節(jié)點都發(fā)送確認消息

• 2.2: 如果一個 acceptor 收到確認消息鄙信，且 n 大于本地承諾過的編號，則接受提議中的值稽寒，并持久化存儲扮碧。

  
  
  Paxos-chooseValueProcess1
  
  

  從這個過程可以看出，acceptor3、acceptor4慎王、acceptor5 接收到 (2, X) 的提議后蚓土，會接受這個提議。5 個 acceptor 最終接受的提議是不同的赖淤，有 (1, X) 以及 (2, X)蜀漆。但是其中的值是相同的，也就是對值達成了共識咱旱，不要求提議編號也一致确丢。

學習值具體過程

學習值和選擇值類似，也是一個二階提交的過程：

3.1 當 acceptor 接受一個提議后吐限，向所有的 learner 通知這個提議

3.2 如果 learner 收到 acceptor 的通知鲜侥，則接受這個提議。如果 learner 接受從大多數(shù) acceptor 收到的某個提議诸典，則這個 learner 接受提議中的值描函。

Paxos-chooseValueProcess2

從圖中可以看出，learner 消息的數(shù)量是 acceptor 的數(shù)量與 learner 的數(shù)量的乘積狐粱，為了減少消息的數(shù)量舀寓，可以指定一個learner 為 Leader，acceptor 接受提議后肌蜻，向 learner 的 Leader 發(fā)送 learn 消息互墓，Leader 收到大多數(shù)消息后，接受請求中的值再向其他 learner 發(fā)送 learn 消息蒋搜。

詳細流程說明

準備階段

• 一個節(jié)點選擇成為leader篡撵，選擇一個序列號x和值v來創(chuàng)建一個提議P1(x, v)。leader將這個提議發(fā)送給acceptor齿诞，等待大多數(shù)節(jié)點的返回酸休。

• acceptor在收到提議P1(x, v)后骂租，判斷：

  • 如果提議是該acceptor要接受的第一個提議祷杈，回復“同意”，承諾leader該acceptor未來不會接受小于x的請求渗饮。

  • 如果該acceptor之前有接受過提議：

    • 比較x和之間和之前接受的最高序列號的提議但汞，比如P2(y,v2)
    • 如果x<y，回復拒絕和y值
    • 如果x>y互站，回復同意和P2(y, v2)

提交階段

• 如果大多數(shù)的acceptor回復“拒絕”或者沒有回復私蕾，leader取消本次提議。

• 如果大多數(shù)的acceptor回復“同意”胡桃，leader也能知道acceptor已經(jīng)接受的提議踩叭。leader從這些值中任選一個值（如果沒有值被接受，選擇自己的值），發(fā)送“接受請求”消息容贝，帶著提議的序列號和值(x, v)自脯。

• 當acceptor收到“接受請求”消息，如果滿足下面的兩個條件斤富，就發(fā)送“接受”膏潮，否則返回“拒絕”。

  • v和之前接受的某個值相同
  • x是該acceptor所接受提議中序列號的最大值

• 如果leader沒有從大多數(shù)節(jié)點中收到“接受”消息满力，leader取消這次提議然后重新開始焕参；如果leader從大多數(shù)節(jié)點中收到了“接受”消息，本次協(xié)商就結(jié)束了油额。作為優(yōu)化叠纷，leader可以發(fā)送“提交”消息給其他的節(jié)點。

一旦多數(shù)接受了共同的提案值潦嘶，則形成決議讲岁，成為最終確認的提案。

共識算法總結(jié)

整合前面的選擇值和學習值的過程衬以，共識算法一共有如下步驟：

• proposer 向大多數(shù) acceptor 發(fā)起提議編號缓艳。
• acceptor 根據(jù)規(guī)則(編號最大)接受提議編號，并回復 proposer
• proposer 接受到大多數(shù) acceptor 的回復后看峻，再根據(jù)規(guī)則(是否存在已承諾的值)選擇一個值發(fā)送確認消息阶淘。
• acceptor 接受到確認消息后接受消息中的值，并向 learner Leader 發(fā)送 learn 請求
• learn Leader 接受到大多數(shù)的學習請求后互妓，向其他的 learner 發(fā)送學習請求溪窒，同步這個值。

到此冯勉，proposer 提議的值就被同步到所有的 learn 中澈蚌，共識算法結(jié)束。

總結(jié)一下灼狰，其實Paxos算法通過一個決議分為兩個階段（Learn階段之前決議已經(jīng)形成）：

1. 第一階段：Prepare階段宛瞄。Proposer向Acceptors發(fā)出Prepare請求，Acceptors針對收到的Prepare請求進行Promise承諾交胚。
2. 第二階段：Accept階段份汗。Proposer收到多數(shù)Acceptors承諾的Promise后，向Acceptors發(fā)出Propose請求蝴簇，Acceptors針對收到的Propose請求進行Accept處理杯活。

3. 第三階段：Learn階段。Proposer在收到多數(shù)Acceptors的Accept之后熬词，標志著本次Accept成功旁钧，決議形成吸重，將形成的決議發(fā)送給所有Learners。

   
   
   01-technology_C-architecture_C01-archBase_Paxos-ElectionProcess.png

Paxos算法流程中的每條消息描述如下：

• Prepare: Proposer生成全局唯一且遞增的Proposal ID (可使用時間戳加Server ID)歪今，向所有Acceptors發(fā)送Prepare請求晤锹，這里無需攜帶提案內(nèi)容，只攜帶Proposal ID即可彤委。
• Promise: Acceptors收到Prepare請求后鞭铆，做出“兩個承諾，一個應答”焦影。

兩個承諾

1. 不再接受Proposal ID小于等于（注意：這里是<= ）當前請求的Prepare請求车遂。

2. 不再接受Proposal ID小于（注意：這里是< ）當前請求的Propose請求。

一個應答

不違背以前作出的承諾下斯辰，回復已經(jīng)Accept過的提案中Proposal ID最大的那個提案的Value和Proposal ID舶担，沒有則返回空值。

Multi-Paxos（Paxos 完整算法）

Paxos 共識算法只能對一個值形成決議彬呻，決議的形成至少需要兩次網(wǎng)絡來回衣陶，在高并發(fā)情況下可能需要更多的網(wǎng)絡來回，極端情況下甚至可能形成活鎖闸氮。如果想連續(xù)確定多個值剪况，Paxos 共識算法搞不定了。因此 Paxos 共識算法幾乎只是用來做理論研究蒲跨，并不直接應用在實際工程中译断。

實際應用中幾乎都需要連續(xù)確定多個值，而且希望能有更高的效率或悲。Multi-Paxos正是為解決此問題而提出孙咪。Multi-Paxos基于Paxos 共識算法做了兩點改進：

1. 針對每一個要確定的值，運行一次Paxos算法實例（Instance）巡语，形成決議翎蹈。每一個Paxos實例使用唯一的Instance ID標識。
2. 在所有Proposers中選舉一個Leader男公，由Leader唯一地提交Proposal給Acceptors進行表決荤堪。這樣沒有Proposer競爭，解決了活鎖問題理澎。在系統(tǒng)中僅有一個Leader進行Value提交的情況下逞力，Prepare階段就可以跳過曙寡，從而將兩階段變?yōu)橐浑A段糠爬，提高效率。

Paxos 完整算法——Multi Paxos举庶，就是多次運行 Paxos 共識算法执隧，形成多個實例的算法。類似于每個進程都會形成一個數(shù)組，數(shù)組中的每個元素都是一個達成一致的值镀琉。

異常情況處理

腦裂問題

Paxos 共識算法會保證即使有多個進程認為自己是 Leader ，也就是出現(xiàn)腦裂的情況，每個實例最終也只能有一個值被選中——每個 Leader 提議值的時候都有提議 id响蓉，而 learn 每次只能接受一個提議 id檬某。

進程1 (Leader 1) 不一定每次都能成功，也會出現(xiàn)失敗的情況钓试。當進程1 成為 Leader装黑，提議通過了一個值，該值還未被進程2(learn) 完全學習弓熏，這時進程3 也認為自己是 Leader 并讓進程2 接受了自己的提議(更大的提議編號)恋谭，導致進程1 同步給進程2 的內(nèi)容失效。

空洞處理

各實例是可以并發(fā)執(zhí)行的挽鞠，這可能會導致一個問題：如果在第一個實例的值的確認過程中出現(xiàn)消息丟失或者網(wǎng)絡延時疚颊，第一個值沒有被確定。同時 Leader 開始了第二個實例信认，并且第二個實例的值成功確定材义，那個第一個實例的值是空的，第二個實例的值是確定的嫁赏，這種情況被成為空洞母截。

如果 Leader 法西安某個消息在一定時間內(nèi)沒有得到回復，那么 Leader 可以重發(fā)這個消息橄教。通過重發(fā)機制清寇，空洞最終會被填補上。

如果是這時發(fā)生 Leader 切換护蝶，則情況會有所不同华烟。如果舊的 Leader 的提議已經(jīng)被接受，那么新的 Leader 會繼續(xù)保持這個提議——新的 Leader 重發(fā)相同的消息持灰；如果舊的 Leader 的提議還沒有被接受盔夜，則新的 Leader 可以提議一個新的值。不管怎樣堤魁，這個空洞最終都會被填補上喂链。

Paxos 算法應用

A. database replication, log replication等

如bdb的數(shù)據(jù)復制就是使用paxos兼容的算法。Paxos最大的用途就是保持多個節(jié)點數(shù)據(jù)的一致性妥泉。

B. naming service

naming service, 如大型系統(tǒng)內(nèi)部通常存在多個接口服務相互調(diào)用椭微。

1. 通常的實現(xiàn)是將服務的ip/hostname寫死在配置中，當service發(fā)生故障時候盲链，通過手工更改配置文件或者修改DNS指向的方法來解決蝇率。缺點是可維護性差迟杂，內(nèi)部的單元越多，故障率越大本慕。
2. LVS雙機冗余的方式排拷，缺點是所有單元需要雙倍的資源投入。
   通過Paxos算法來管理所有的naming服務锅尘，則可保證high available分配可用的service給client监氢。象ZooKeeper還提供watch功能，即watch的對象發(fā)生了改變會自動發(fā)notification, 這樣所有的client就可以使用一致的藤违，高可用的接口忙菠。

C. config配置管理

1. 通常手工修改配置文件的方法，這樣容易出錯纺弊，也需要人工干預才能生效牛欢，所以節(jié)點的狀態(tài)無法同時達到一致。
2. 大規(guī)模的應用都會實現(xiàn)自己的配置服務淆游，比如用http web服務來實現(xiàn)配置中心化傍睹。它的缺點是更新后所有client無法立即得知，各節(jié)點加載的順序無法保證犹菱，造成系統(tǒng)中的配置不是同一狀態(tài)拾稳。

D. membership用戶角色 / access control list

在權(quán)限設置中，用戶一旦設置某項權(quán)限比如由管理員變成普通身份腊脱，這時應在所有的服務器上所有遠程CDN立即生效访得，否則就會導致不能接受的后果。

E. 號碼分配

通常簡單的解決方法是用數(shù)據(jù)庫自增ID, 這導致數(shù)據(jù)庫切分困難陕凹，或程序生成GUID, 這通常導致ID過長悍抑。更優(yōu)雅的做法是利用paxos算法在多臺replicas之間選擇一個作為master, 通過master來分配號碼。當master發(fā)生故障時杜耙，再用paxos選擇另外一個master搜骡。

F. 原子廣播

原子廣播協(xié)議用于把消息向廣播對象進行廣播，并且保證消息能夠被可靠地收到佑女，且所有廣播對象以相同的順序收到记靡。

原子廣播協(xié)議通常被定義包含以下兩個動作：

• ABroadcast(v)：廣播動作，當客戶端想廣播值 v 時团驱，調(diào)用這個動作摸吠。
• v=ADeliver()：投遞動作，客戶端通過這個動作接收其他客戶端提交的值嚎花。這個動作一般是一個回調(diào)寸痢，當有值要被接受時，客戶端會被回調(diào)贩幻。

原子廣播的特性——原子廣播保證：如果一個進程調(diào)用了廣播動作轿腺，那么所有的客戶端的投遞動作都會被回調(diào)两嘴，并且調(diào)用順序與調(diào)用廣播的順序一致丛楚。

Paxos算法與原子廣播

在基于 Paxos 算法的原子廣播的實現(xiàn)中族壳，原子廣播黑盒內(nèi)部由一組進程組成，原子廣播內(nèi)部包含 proposer 和 acceptor 角色趣些，接收廣播回調(diào)(aDeliver)的 client 作為 learner 角色仿荆。

當一個 client 調(diào)用 ABroadcast(v) 動作時，這個請求會作為一個提議給到 proposer 坏平，經(jīng)過大多數(shù) acceptor 達成共識后拢操，該值同步給所有的 learner。learner 接受到這個值后舶替，完成對 aDeliver() 動作接口的回調(diào)令境。

其他

Google 的 Chubby；

Yahoo! 的 ZooKeeper 是一個開源的類 Paxos 實現(xiàn)顾瞪。

總結(jié)

Paxos 又分為兩個算法舔庶，Basic Paxos (共識算法) 和 Multi Paxos (完整算法)。共識算法包括選擇值和學習值兩個具體過程陈醒，具體步驟可以概況為三個階段：

• 第一階段：確認大多數(shù)節(jié)點可接受提議編號
• 第二階段：提交提議惕橙，同步值給大多數(shù) acceptor
• 第三階段：同步值給所有 learn 節(jié)點

完整算法則是多次運行 Paxos 共識算法，解決共識算法在工程中的應用問題钉跷。完整算法中的 Leader 也是通過共識算法達成一致弥鹦。