Distributed Consensus Algorithm

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

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

—— Mike Burrows，Inventor of Google Chubby

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

Paxos 問(wèn)題是指分布式的系統(tǒng)中存在故障（fault），但不存在惡意（corrupt）節(jié)點(diǎn)場(chǎng)景（即可能消息丟失或重復(fù)，但無(wú)錯(cuò)誤消息）下的共識(shí)達(dá)成（Consensus）問(wèn)題。因?yàn)樽钤缡?Leslie Lamport 用 Paxon 島的故事模型來(lái)進(jìn)行描述而命名。

• 少數(shù)服從多數(shù)，最終達(dá)成一致意見(jiàn)。
• 基于消息傳遞且具有高度容錯(cuò)特性的一致性算法，是目前公認(rèn)的解決分布式一致性問(wèn)題最有效的算法之一。
• Paxos 是第一個(gè)被證明的共識(shí)算法，其原理基于 兩階段提交 并進(jìn)行擴(kuò)展。

Paxos 算法分為核心算法和完整算法兩部分。Paxos 算法的核心部分解決了分布式領(lǐng)域當(dāng)中非常重要的基礎(chǔ)問(wèn)題，也就是共識(shí)問(wèn)題；完整算法是用來(lái)實(shí)現(xiàn)狀態(tài)機(jī)的算法。

兩個(gè)比較明顯的缺點(diǎn)：

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

共識(shí)問(wèn)題

不嚴(yán)格地說(shuō)，共識(shí)問(wèn)題就算多個(gè)進(jìn)程對(duì)一個(gè)值達(dá)成一致，每個(gè)進(jìn)程都可以提議（propose）一個(gè)自己想要的值，但是最終只有一個(gè)值會(huì)被選中，并且所有進(jìn)程對(duì)這個(gè)選中的值達(dá)成一致。

共識(shí)算法注意點(diǎn)

• 可以是任意多個(gè)進(jìn)程
• 所有進(jìn)程都可以提議一個(gè)值
• 所有進(jìn)程都可以學(xué)習(xí)到被選中的值

共識(shí)算法的要求

共識(shí)算法有兩個(gè)要求，安全要求和存活要求

安全要求是指：

• 只有一個(gè)被提議的值可能被選中
• 只有唯一的一個(gè)值被選中
• 只有一個(gè)值實(shí)際已經(jīng)被選中，一個(gè)進(jìn)程才能學(xué)習(xí)到這個(gè)值

存活要求是指：某個(gè)被提議的值最終一定會(huì)被選中，并且如果一個(gè)值被選中，那么一個(gè)進(jìn)程最終能夠?qū)W習(xí)到這個(gè)值。

Paxos共識(shí)算法

算法的角色

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

• proposer：提出一個(gè)提案，等待大家批準(zhǔn)為結(jié)案。往往是客戶端擔(dān)任該角色；
• acceptor：負(fù)責(zé)對(duì)提案進(jìn)行投票。往往是服務(wù)端擔(dān)任該角色；
• learner：被告知結(jié)案結(jié)果，并與之統(tǒng)一，不參與投票過(guò)程?？赡転榭蛻舳嘶蚍?wù)端。

在多副本狀態(tài)機(jī)中，每個(gè)副本同時(shí)具有Proposer、Acceptor、Learner三種角色。

Paxos-Roles

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

• safety：保證決議結(jié)果是對(duì)的，無(wú)歧義的，不會(huì)出現(xiàn)錯(cuò)誤情況。

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

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

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

基本過(guò)程包括 proposer 提出提案，先爭(zhēng)取大多數(shù) acceptor 的支持，超過(guò)一半支持時(shí)，則發(fā)送結(jié)案結(jié)果給所有人進(jìn)行確認(rèn)。一個(gè)潛在的問(wèn)題是 proposer 在此過(guò)程中出現(xiàn)故障，可以通過(guò)超時(shí)機(jī)制來(lái)解決。極為湊巧的情況下，每次新的一輪提案的 proposer 都恰好故障，系統(tǒng)則永遠(yuǎn)無(wú)法達(dá)成一致（概率很?。?。

Paxos 能保證在超過(guò)的正常節(jié)點(diǎn)存在時(shí)，系統(tǒng)能達(dá)成共識(shí)。

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

考慮的場(chǎng)景

單個(gè)提案者+多接收者

如果系統(tǒng)中限定只有某個(gè)特定節(jié)點(diǎn)是提案者，那么一致性肯定能達(dá)成（只有一個(gè)方案，要么達(dá)成，要么失?。Ｌ岚刚咧灰盏搅藖?lái)自多數(shù)接收者的投票，即可認(rèn)為通過(guò)，因?yàn)橄到y(tǒng)中不存在其他的提案。

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

多個(gè)提案者+單個(gè)接收者

限定某個(gè)節(jié)點(diǎn)作為接收者。這種情況下，共識(shí)也很容易達(dá)成，接收者收到多個(gè)提案，選第一個(gè)提案作為決議，拒絕掉后續(xù)的提案即可。

缺陷也是容易發(fā)生單點(diǎn)故障，包括接收者故障或首個(gè)提案者節(jié)點(diǎn)故障。

以上兩種情形其實(shí)類似主從模式，雖然不那么可靠，但因?yàn)樵砗?jiǎn)單而被廣泛采用。

當(dāng)提案者和接收者都推廣到多個(gè)的情形，會(huì)出現(xiàn)一些挑戰(zhàn)。

多個(gè)提案者+多個(gè)接收者

既然限定單提案者或單接收者都會(huì)出現(xiàn)故障，那么就得允許出現(xiàn)多個(gè)提案者和多個(gè)接收者。問(wèn)題一下子變得復(fù)雜了。

一種情況是同一時(shí)間片段（如一個(gè)提案周期）內(nèi)只有一個(gè)提案者，這時(shí)可以退化到單提案者的情形。需要設(shè)計(jì)一種機(jī)制來(lái)保障提案者的正確產(chǎn)生，例如按照時(shí)間、序列、或者大家猜拳（出一個(gè)數(shù)字來(lái)比較）之類?？紤]到分布式系統(tǒng)要處理的工作量很大，這個(gè)過(guò)程要盡量高效，滿足這一條件的機(jī)制非常難設(shè)計(jì)。

另一種情況是允許同一時(shí)間片段內(nèi)可以出現(xiàn)多個(gè)提案者。那同一個(gè)節(jié)點(diǎn)可能收到多份提案，怎么對(duì)他們進(jìn)行區(qū)分呢？這個(gè)時(shí)候采用只接受第一個(gè)提案而拒絕后續(xù)提案的方法也不適用。很自然的，提案需要帶上不同的序號(hào)。節(jié)點(diǎn)需要根據(jù)提案序號(hào)來(lái)判斷接受哪個(gè)。比如接受其中序號(hào)較大（往往意味著是接受新提出的，因?yàn)榕f提案者故障概率更大）的提案。

如何為提案分配序號(hào)呢？

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

此外，提案者即便收到了多數(shù)接收者的投票，也不敢說(shuō)就一定通過(guò)。因?yàn)樵诖诉^(guò)程中系統(tǒng)可能還有其它的提案。

算法的選擇值和學(xué)習(xí)值的過(guò)程

共識(shí)算法分為兩個(gè)過(guò)程，即選擇一個(gè)值和學(xué)習(xí)一個(gè)值，具體如下：

• 在選擇一個(gè)值的過(guò)程中，一組 proposer 中每一個(gè) proposer 都可以提議任意一個(gè)值給一組 acceptor ，這組 acceptor 會(huì)從所有的 proposer 提議的值中選出唯一的一個(gè)值。
• 在學(xué)習(xí)一個(gè)值的過(guò)程中，learner 從 acceptor 中學(xué)習(xí)到被選中的值

選擇值具體過(guò)程

選擇值過(guò)程是一個(gè)二階提交的過(guò)程，第一階段選擇提議編號(hào)，第二階段接受提議的值。

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

• 1.2：如果一個(gè) acceptor 收到一個(gè)提議消息，并且 n 大于本地承諾過(guò)的提議編號(hào)，則用 n 更新本地承諾過(guò)的提議編號(hào)。如果有接受過(guò)其他的提議，則將提議的編號(hào)和值一起返回，如果沒(méi)有返回提議的編號(hào)和 null；

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

• 如果在所有的這些 promise 消息中有攜帶提議的，則用提議編號(hào)最大的提議中的值

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

• 2.2: 如果一個(gè) acceptor 收到確認(rèn)消息，且 n 大于本地承諾過(guò)的編號(hào)，則接受提議中的值，并持久化存儲(chǔ)。

  
  
  Paxos-chooseValueProcess1
  
  

  從這個(gè)過(guò)程可以看出，acceptor3、acceptor4、acceptor5 接收到 (2, X) 的提議后，會(huì)接受這個(gè)提議。5 個(gè) acceptor 最終接受的提議是不同的，有 (1, X) 以及 (2, X)。但是其中的值是相同的，也就是對(duì)值達(dá)成了共識(shí)，不要求提議編號(hào)也一致。

學(xué)習(xí)值具體過(guò)程

學(xué)習(xí)值和選擇值類似，也是一個(gè)二階提交的過(guò)程：

3.1 當(dāng) acceptor 接受一個(gè)提議后，向所有的 learner 通知這個(gè)提議

3.2 如果 learner 收到 acceptor 的通知，則接受這個(gè)提議。如果 learner 接受從大多數(shù) acceptor 收到的某個(gè)提議，則這個(gè) learner 接受提議中的值。

Paxos-chooseValueProcess2

從圖中可以看出，learner 消息的數(shù)量是 acceptor 的數(shù)量與 learner 的數(shù)量的乘積，為了減少消息的數(shù)量，可以指定一個(gè)learner 為 Leader，acceptor 接受提議后，向 learner 的 Leader 發(fā)送 learn 消息，Leader 收到大多數(shù)消息后，接受請(qǐng)求中的值再向其他 learner 發(fā)送 learn 消息。

詳細(xì)流程說(shuō)明

準(zhǔn)備階段

• 一個(gè)節(jié)點(diǎn)選擇成為leader，選擇一個(gè)序列號(hào)x和值v來(lái)創(chuàng)建一個(gè)提議P1(x, v)。leader將這個(gè)提議發(fā)送給acceptor，等待大多數(shù)節(jié)點(diǎn)的返回。

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

  • 如果提議是該acceptor要接受的第一個(gè)提議，回復(fù)“同意”，承諾leader該acceptor未來(lái)不會(huì)接受小于x的請(qǐng)求。

  • 如果該acceptor之前有接受過(guò)提議：

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

提交階段

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

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

• 當(dāng)acceptor收到“接受請(qǐng)求”消息，如果滿足下面的兩個(gè)條件，就發(fā)送“接受”，否則返回“拒絕”。

  • v和之前接受的某個(gè)值相同
  • x是該acceptor所接受提議中序列號(hào)的最大值

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

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

共識(shí)算法總結(jié)

整合前面的選擇值和學(xué)習(xí)值的過(guò)程，共識(shí)算法一共有如下步驟：

• proposer 向大多數(shù) acceptor 發(fā)起提議編號(hào)。
• acceptor 根據(jù)規(guī)則(編號(hào)最大)接受提議編號(hào)，并回復(fù) proposer
• proposer 接受到大多數(shù) acceptor 的回復(fù)后，再根據(jù)規(guī)則(是否存在已承諾的值)選擇一個(gè)值發(fā)送確認(rèn)消息。
• acceptor 接受到確認(rèn)消息后接受消息中的值，并向 learner Leader 發(fā)送 learn 請(qǐng)求
• learn Leader 接受到大多數(shù)的學(xué)習(xí)請(qǐng)求后，向其他的 learner 發(fā)送學(xué)習(xí)請(qǐng)求，同步這個(gè)值。

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

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

1. 第一階段：Prepare階段。Proposer向Acceptors發(fā)出Prepare請(qǐng)求，Acceptors針對(duì)收到的Prepare請(qǐng)求進(jìn)行Promise承諾。
2. 第二階段：Accept階段。Proposer收到多數(shù)Acceptors承諾的Promise后，向Acceptors發(fā)出Propose請(qǐng)求，Acceptors針對(duì)收到的Propose請(qǐng)求進(jìn)行Accept處理。

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

   
   
   01-technology_C-architecture_C01-archBase_Paxos-ElectionProcess.png

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

• Prepare: Proposer生成全局唯一且遞增的Proposal ID (可使用時(shí)間戳加Server ID)，向所有Acceptors發(fā)送Prepare請(qǐng)求，這里無(wú)需攜帶提案內(nèi)容，只攜帶Proposal ID即可。
• Promise: Acceptors收到Prepare請(qǐng)求后，做出“兩個(gè)承諾，一個(gè)應(yīng)答”。

兩個(gè)承諾

1. 不再接受Proposal ID小于等于（注意：這里是<= ）當(dāng)前請(qǐng)求的Prepare請(qǐng)求。

2. 不再接受Proposal ID小于（注意：這里是< ）當(dāng)前請(qǐng)求的Propose請(qǐng)求。

一個(gè)應(yīng)答

不違背以前作出的承諾下，回復(fù)已經(jīng)Accept過(guò)的提案中Proposal ID最大的那個(gè)提案的Value和Proposal ID，沒(méi)有則返回空值。

Multi-Paxos（Paxos 完整算法）

Paxos 共識(shí)算法只能對(duì)一個(gè)值形成決議，決議的形成至少需要兩次網(wǎng)絡(luò)來(lái)回，在高并發(fā)情況下可能需要更多的網(wǎng)絡(luò)來(lái)回，極端情況下甚至可能形成活鎖。如果想連續(xù)確定多個(gè)值，Paxos 共識(shí)算法搞不定了。因此 Paxos 共識(shí)算法幾乎只是用來(lái)做理論研究，并不直接應(yīng)用在實(shí)際工程中。

實(shí)際應(yīng)用中幾乎都需要連續(xù)確定多個(gè)值，而且希望能有更高的效率。Multi-Paxos正是為解決此問(wèn)題而提出。Multi-Paxos基于Paxos 共識(shí)算法做了兩點(diǎn)改進(jìn)：

1. 針對(duì)每一個(gè)要確定的值，運(yùn)行一次Paxos算法實(shí)例（Instance），形成決議。每一個(gè)Paxos實(shí)例使用唯一的Instance ID標(biāo)識(shí)。
2. 在所有Proposers中選舉一個(gè)Leader，由Leader唯一地提交Proposal給Acceptors進(jìn)行表決。這樣沒(méi)有Proposer競(jìng)爭(zhēng)，解決了活鎖問(wèn)題。在系統(tǒng)中僅有一個(gè)Leader進(jìn)行Value提交的情況下，Prepare階段就可以跳過(guò)，從而將兩階段變?yōu)橐浑A段，提高效率。

Paxos 完整算法——Multi Paxos，就是多次運(yùn)行 Paxos 共識(shí)算法，形成多個(gè)實(shí)例的算法。類似于每個(gè)進(jìn)程都會(huì)形成一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè)達(dá)成一致的值。

異常情況處理

腦裂問(wèn)題

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

進(jìn)程1 (Leader 1) 不一定每次都能成功，也會(huì)出現(xiàn)失敗的情況。當(dāng)進(jìn)程1 成為 Leader，提議通過(guò)了一個(gè)值，該值還未被進(jìn)程2(learn) 完全學(xué)習(xí)，這時(shí)進(jìn)程3 也認(rèn)為自己是 Leader 并讓進(jìn)程2 接受了自己的提議(更大的提議編號(hào))，導(dǎo)致進(jìn)程1 同步給進(jìn)程2 的內(nèi)容失效。

空洞處理

各實(shí)例是可以并發(fā)執(zhí)行的，這可能會(huì)導(dǎo)致一個(gè)問(wèn)題：如果在第一個(gè)實(shí)例的值的確認(rèn)過(guò)程中出現(xiàn)消息丟失或者網(wǎng)絡(luò)延時(shí)，第一個(gè)值沒(méi)有被確定。同時(shí) Leader 開(kāi)始了第二個(gè)實(shí)例，并且第二個(gè)實(shí)例的值成功確定，那個(gè)第一個(gè)實(shí)例的值是空的，第二個(gè)實(shí)例的值是確定的，這種情況被成為空洞。

如果 Leader 法西安某個(gè)消息在一定時(shí)間內(nèi)沒(méi)有得到回復(fù)，那么 Leader 可以重發(fā)這個(gè)消息。通過(guò)重發(fā)機(jī)制，空洞最終會(huì)被填補(bǔ)上。

如果是這時(shí)發(fā)生 Leader 切換，則情況會(huì)有所不同。如果舊的 Leader 的提議已經(jīng)被接受，那么新的 Leader 會(huì)繼續(xù)保持這個(gè)提議——新的 Leader 重發(fā)相同的消息；如果舊的 Leader 的提議還沒(méi)有被接受，則新的 Leader 可以提議一個(gè)新的值。不管怎樣，這個(gè)空洞最終都會(huì)被填補(bǔ)上。

Paxos 算法應(yīng)用

A. database replication, log replication等

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

B. naming service

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

1. 通常的實(shí)現(xiàn)是將服務(wù)的ip/hostname寫(xiě)死在配置中，當(dāng)service發(fā)生故障時(shí)候，通過(guò)手工更改配置文件或者修改DNS指向的方法來(lái)解決。缺點(diǎn)是可維護(hù)性差，內(nèi)部的單元越多，故障率越大。
2. LVS雙機(jī)冗余的方式，缺點(diǎn)是所有單元需要雙倍的資源投入。
   通過(guò)Paxos算法來(lái)管理所有的naming服務(wù)，則可保證high available分配可用的service給client。象ZooKeeper還提供watch功能，即watch的對(duì)象發(fā)生了改變會(huì)自動(dòng)發(fā)notification, 這樣所有的client就可以使用一致的，高可用的接口。

C. config配置管理

1. 通常手工修改配置文件的方法，這樣容易出錯(cuò)，也需要人工干預(yù)才能生效，所以節(jié)點(diǎn)的狀態(tài)無(wú)法同時(shí)達(dá)到一致。
2. 大規(guī)模的應(yīng)用都會(huì)實(shí)現(xiàn)自己的配置服務(wù)，比如用http web服務(wù)來(lái)實(shí)現(xiàn)配置中心化。它的缺點(diǎn)是更新后所有client無(wú)法立即得知，各節(jié)點(diǎn)加載的順序無(wú)法保證，造成系統(tǒng)中的配置不是同一狀態(tài)。

D. membership用戶角色 / access control list

在權(quán)限設(shè)置中，用戶一旦設(shè)置某項(xiàng)權(quán)限比如由管理員變成普通身份，這時(shí)應(yīng)在所有的服務(wù)器上所有遠(yuǎn)程CDN立即生效，否則就會(huì)導(dǎo)致不能接受的后果。

E. 號(hào)碼分配

通常簡(jiǎn)單的解決方法是用數(shù)據(jù)庫(kù)自增ID, 這導(dǎo)致數(shù)據(jù)庫(kù)切分困難，或程序生成GUID, 這通常導(dǎo)致ID過(guò)長(zhǎng)。更優(yōu)雅的做法是利用paxos算法在多臺(tái)replicas之間選擇一個(gè)作為master, 通過(guò)master來(lái)分配號(hào)碼。當(dāng)master發(fā)生故障時(shí)，再用paxos選擇另外一個(gè)master。

F. 原子廣播

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

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

• ABroadcast(v)：廣播動(dòng)作，當(dāng)客戶端想廣播值 v 時(shí)，調(diào)用這個(gè)動(dòng)作。
• v=ADeliver()：投遞動(dòng)作，客戶端通過(guò)這個(gè)動(dòng)作接收其他客戶端提交的值。這個(gè)動(dòng)作一般是一個(gè)回調(diào)，當(dāng)有值要被接受時(shí)，客戶端會(huì)被回調(diào)。

原子廣播的特性——原子廣播保證：如果一個(gè)進(jìn)程調(diào)用了廣播動(dòng)作，那么所有的客戶端的投遞動(dòng)作都會(huì)被回調(diào)，并且調(diào)用順序與調(diào)用廣播的順序一致。

Paxos算法與原子廣播

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

當(dāng)一個(gè) client 調(diào)用 ABroadcast(v) 動(dòng)作時(shí)，這個(gè)請(qǐng)求會(huì)作為一個(gè)提議給到 proposer ，經(jīng)過(guò)大多數(shù) acceptor 達(dá)成共識(shí)后，該值同步給所有的 learner。learner 接受到這個(gè)值后，完成對(duì) aDeliver() 動(dòng)作接口的回調(diào)。

其他

Google 的 Chubby；

Yahoo! 的 ZooKeeper 是一個(gè)開(kāi)源的類 Paxos 實(shí)現(xiàn)。

總結(jié)

Paxos 又分為兩個(gè)算法，Basic Paxos (共識(shí)算法) 和 Multi Paxos (完整算法)。共識(shí)算法包括選擇值和學(xué)習(xí)值兩個(gè)具體過(guò)程，具體步驟可以概況為三個(gè)階段：

• 第一階段：確認(rèn)大多數(shù)節(jié)點(diǎn)可接受提議編號(hào)
• 第二階段：提交提議，同步值給大多數(shù) acceptor
• 第三階段：同步值給所有 learn 節(jié)點(diǎn)

完整算法則是多次運(yùn)行 Paxos 共識(shí)算法，解決共識(shí)算法在工程中的應(yīng)用問(wèn)題。完整算法中的 Leader 也是通過(guò)共識(shí)算法達(dá)成一致。