摘要：實(shí)際上，它也算是最淺顯易見的分布式算法之一了。一個(gè)分布式算法，有兩個(gè)重要的屬性和，簡(jiǎn)單來(lái)說(shuō)是指那些需要保證永遠(yuǎn)都不會(huì)發(fā)生的事情是指那些最終一定會(huì)發(fā)生的事情在這個(gè)一致性算法中，有三個(gè)參與角色，我們分別用，和來(lái)表示。

用于實(shí)現(xiàn)高容錯(cuò)性分布式系統(tǒng)的Paxos算法，一直以來(lái)總是被認(rèn)為是難以理解的，或許是因?yàn)閷?duì)很多人來(lái)說(shuō)，初始版本就像是”希臘語(yǔ)"一樣（最初的論文是以希臘故事展開的形式）[5]。實(shí)際上，它也算是最淺顯易見的分布式算法之一了。它的核心就是一個(gè)一致性算法——論文[5]中的“synod”算法。在下一個(gè)章節(jié)可以看到，它基本上是根據(jù)一個(gè)一致性算法所必需滿足的條件自然而然地推斷出來(lái)的。最后一個(gè)章節(jié)，我們通過(guò)將Paxos算法作為構(gòu)建一個(gè)實(shí)現(xiàn)了狀態(tài)機(jī)的分布式系統(tǒng)的一致性實(shí)現(xiàn)，來(lái)完整地描述它。這種使用狀態(tài)機(jī)方法的論文[4]應(yīng)該早已廣為人知，因?yàn)樗赡芤呀?jīng)是分布式系統(tǒng)理論研究領(lǐng)域被引用最廣泛的了。

假設(shè)有一組可以提出提案的進(jìn)程集合。一個(gè)一致性算法需要保證：
在這些被提出的提案中，只有一個(gè)會(huì)被選定。
如果沒有提案被提出，則不會(huì)有被選定的提案。
當(dāng)一個(gè)提案被選定后，進(jìn)程應(yīng)該能獲取被選定提案的信息。

對(duì)于一致來(lái)說(shuō)，安全性（Safety）需求是這樣的：
只有被提出的提案才能被選定。
只能有一個(gè)值被選中（chosen），同時(shí)
進(jìn)程不能認(rèn)為某個(gè)提案被選定，除非它真的是被選定的那個(gè)。

我們不會(huì)嘗試去精確地描述活性（Liveness）需求。但是從總體上看，最終的目標(biāo)是保證有一個(gè)提案被選定，并且當(dāng)提案被選定后，進(jìn)程最終也能獲取到被選定提案的信息。
一個(gè)分布式算法，有兩個(gè)重要的屬性：Safety和Liveness，簡(jiǎn)單來(lái)說(shuō)：
Safety是指那些需要保證永遠(yuǎn)都不會(huì)發(fā)生的事情
Liveness是指那些最終一定會(huì)發(fā)生的事情

在這個(gè)一致性算法中，有三個(gè)參與角色，我們分別用Proposer，Acceptor和Learner來(lái)表示。在具體實(shí)現(xiàn)中，一個(gè)進(jìn)程可能充當(dāng)不止一種角色，但是在這里我們并不關(guān)心它們之間的映射關(guān)系。

假設(shè)不同的參與者之間可以通過(guò)發(fā)消息來(lái)進(jìn)行通信，我們使用普通的非拜占庭模式的異步模型：
每個(gè)參與者以任意的速度運(yùn)行，可能會(huì)因停止而執(zhí)行失敗，也可能會(huì)重啟。當(dāng)一個(gè)提案被選定后，所有的參與者都有可能失敗然后重啟，除非這些參與者可以記錄某些信息，否則是不可能存在一個(gè)解法的。
消息在傳輸中可能花費(fèi)任意時(shí)間，可能會(huì)重復(fù)，也可能丟失，但不會(huì)被損壞（不會(huì)被篡改，即不會(huì)發(fā)生拜占庭問(wèn)題）。

選定提案最簡(jiǎn)單的方式就是只有一個(gè)Acceptor存在。Proposer發(fā)送提案給Acceptor，Acceptor會(huì)選擇它接收到的第一個(gè)提案作為被選提案。雖然簡(jiǎn)單，這個(gè)解決方案卻很難讓人滿意，因?yàn)楫?dāng)Acceptor出錯(cuò)時(shí)，整個(gè)系統(tǒng)就無(wú)法工作了。

因此，我們應(yīng)該選擇其他方式來(lái)選定提案，比如可以用多個(gè)Acceptor來(lái)避免一個(gè)Acceptor的單點(diǎn)問(wèn)題。這樣的話，Proposer向一個(gè)Acceptor集合發(fā)送提案，某個(gè)Acceptor可能會(huì)通過(guò)（accept）這個(gè)提案。當(dāng)有足夠多的Acceptor通過(guò)它時(shí)，我們就認(rèn)為這個(gè)提案被選定了。那么怎樣才算是足夠多呢？為了確保只一個(gè)提案被選定，我們可以讓這個(gè)集合大到包含了Acceptor集合中的多數(shù)成員。因?yàn)槿我鈨蓚€(gè)多數(shù)集（majority）至少包含一個(gè)公共成員，如果我們?cè)僖?guī)定一個(gè)Acceptor只能通過(guò)一個(gè)提案，那么就能保證只有一個(gè)提案被選定（這是很多論文都研究過(guò)的多數(shù)集的一個(gè)普通應(yīng)用[3]）。

假設(shè)沒有失敗和消息丟失的情況，如果我們希望在每個(gè)Proposer只能提出一個(gè)提案的前提下仍然可以選出一個(gè)提案來(lái)，這就意味著如下需求：

P1. 一個(gè)Acceptor必須通過(guò)它收到的第一個(gè)提案。

但是這個(gè)需求會(huì)引發(fā)另外的問(wèn)題。如果有多個(gè)提案被不同的Proposer同時(shí)提出，這會(huì)導(dǎo)致雖然每個(gè)Acceptor都通過(guò)了一個(gè)提案，但是沒有一個(gè)提案是由多數(shù)人通過(guò)的。甚至即使只有兩個(gè)提案被提出，如果每個(gè)都被差不多一半的Acceptor通過(guò)了，哪怕只有一個(gè)Acceptor出錯(cuò)都可能導(dǎo)致無(wú)法確定該選定哪個(gè)提案。
比如有5個(gè)Acceptor，其中2個(gè)通過(guò)了提案a，另外3個(gè)通過(guò)了提案b，此時(shí)如果通過(guò)提案b的3個(gè)當(dāng)中有一個(gè)出錯(cuò)了，那么a和b的通過(guò)數(shù)都為2, 這樣就無(wú)法確定了。

P1再加一個(gè)提案被選定需要由半數(shù)以上Acceptor通過(guò)的這個(gè)需求，暗示著一個(gè)Acceptor必須要能通過(guò)不止一個(gè)提案。我們?yōu)槊總€(gè)提案分配一個(gè)編號(hào)來(lái)記錄一個(gè)Acceptor通過(guò)的那些提案，于是一個(gè)提案就包含一個(gè)提案編號(hào)以及它的value值。為了避免造成混淆，需要保證不同的提案具有不同編號(hào)。如何實(shí)現(xiàn)這個(gè)功能依賴于具體的實(shí)現(xiàn)細(xì)節(jié)，在這里我們假設(shè)已經(jīng)實(shí)現(xiàn)了這種保證。當(dāng)一個(gè)具有value值的提案被多數(shù)Acceptor通過(guò)后，我們就認(rèn)為該value被選定了。同時(shí)我們也認(rèn)為該提案被選定了。

我們?cè)试S多個(gè)提案被選定，但是我們必須保證所有被選定的提案具有相同的值value。通過(guò)對(duì)提案編號(hào)的約定，它需要滿足以下保證：
P2. 如果具有value值v的提案被選定了，那么所有比它編號(hào)高的提案的value值也必須是v。

因?yàn)榫幪?hào)是完全有序的，所以條件P2就保證了只有一個(gè)value值被選定這一關(guān)鍵安全性屬性。

一個(gè)提案能被選定，必須要被至少一個(gè)Acceptor通過(guò)，所以我們可以通過(guò)滿足如下條件來(lái)滿足P2:

P2a. 如果一個(gè)具有value值v的提案被選定了，那么被Acceptor通過(guò)的所有編號(hào)比它高的提案的value值也必須是v。

我們?nèi)匀恍枰狿1來(lái)保證有提案會(huì)被選定。因?yàn)橥ㄐ攀钱惒降模粋€(gè)提案可能會(huì)在某個(gè)Acceptor c還沒收到任何提案時(shí)就被選定了。假設(shè)有個(gè)新的Proposer蘇醒了，然后提出了一個(gè)具有不同value值的更高編號(hào)的提案，根據(jù)P1, 需要c通過(guò)這個(gè)提案，但這是與P2a相矛盾的。因此為了同時(shí)滿足P1和P2a，需要對(duì)P2a進(jìn)行強(qiáng)化：

P2b. 如果具有value值v的提案被選定了，那么所有比它編號(hào)更高的被Proposer提出的提案的value值也必須是v。

一個(gè)提案被Acceptor通過(guò)之前肯定是由某個(gè)Proposer提出，因此P2b就隱含P2a，進(jìn)而隱含了P2.

為了發(fā)現(xiàn)如何保證P2b，我們來(lái)看看如何證明它成立。我們假設(shè)某個(gè)具有編號(hào)m和value值v的提案被選定了，需要證明任意具有編號(hào)n（n > m）的提案都具有value值v。我們可以通過(guò)對(duì)n使用數(shù)學(xué)歸納法來(lái)簡(jiǎn)化證明，這樣我們可以在額外的假設(shè)下——即編號(hào)在m..(n-1)之間的提案具有value值v，來(lái)證明編號(hào)為n的提案具有value值v，其中i..j表示從i到j(luò)的集合。因?yàn)榫幪?hào)為m的提案已經(jīng)被選定了，這就意味著存在一個(gè)多數(shù)Acceptor組成的集合C，C中的每個(gè)成員都通過(guò)了這個(gè)提案。結(jié)合歸納的假設(shè)，m被選定意味著：

C中的每一個(gè)Acceptor都通過(guò)了一個(gè)編號(hào)在m..(n-1)之間的提案，并且每個(gè)編號(hào)在m..(n-1)之間的被Acceptor通過(guò)的提案都具有value值v。

由于任何包含多數(shù)Acceptor的集合S都至少包含一個(gè)C中的成員，我們可以通過(guò)保持如下不變性來(lái)確保編號(hào)為n的提案具有value值v：

P2c. 對(duì)于任意v和n，如果一個(gè)編號(hào)為n，value值為v的提案被提出，那么肯定存在一個(gè)由多數(shù)Acceptor組成的集合S滿足以下條件中的一個(gè)：
    a. S中不存在任何Acceptor通過(guò)了編號(hào)小于n的提案
    b. v是S中所有Acceptor已經(jīng)通過(guò)的編號(hào)小于n的具有最大編號(hào)的提案的value值。

通過(guò)維護(hù)P2c的不變性我們就可以滿足P2b的條件了。

為了維護(hù)P2c的不變性，一個(gè)Proposer在提出編號(hào)為n的提案時(shí)，如果存在一個(gè)將要或者已經(jīng)被多數(shù)Acceptor通過(guò)的編號(hào)小于n的最大編號(hào)提案，Proposer需要知道它的信息。獲取那些已經(jīng)被通過(guò)的提案很簡(jiǎn)單，但是預(yù)測(cè)未來(lái)會(huì)被通過(guò)的卻很困難。為了避免去預(yù)測(cè)未來(lái)，Proposer通過(guò)提出承諾不會(huì)有那樣的通過(guò)情況來(lái)控制它。換句話說(shuō)，Proposer會(huì)請(qǐng)求那些Acceptor不要再通過(guò)任何編號(hào)小于n的提案了。這就導(dǎo)致了如下的提案生成算法：
Proposer選擇一個(gè)新的提案編號(hào)n，然后向某個(gè)Acceptor集合中的成員發(fā)送請(qǐng)示，要求它作出如下回應(yīng)：

    （a）保證不再通過(guò)任何編號(hào)小于n的提案。
    （b）當(dāng)前它已經(jīng)通過(guò)的編號(hào)小于n的最大編號(hào)提案，如何存在的話。
 我們把這樣的請(qǐng)求稱為編號(hào)為n的prepare請(qǐng)求。

如果Proposer收到來(lái)自集合中多數(shù)成員的響應(yīng)結(jié)果，那么它可以提出編號(hào)為n，value值為v的提案，這里v是所有響應(yīng)中最大編號(hào)提案的value值，如果響應(yīng)中不包含任何提案，那么這個(gè)值就由Proposer自由決定。

Proposer通過(guò)向某個(gè)Acceptor集合發(fā)送需要被通過(guò)的提案請(qǐng)求來(lái)產(chǎn)生一個(gè)提案（這里的Acceptor集合不一定是響應(yīng)前一個(gè)請(qǐng)求的集合）。這們把這個(gè)叫做accept請(qǐng)求。

目前我們描述了Proposer端的算法。那么Acceptor端是怎樣的呢？它可能會(huì)收到來(lái)自Proposer端的兩種請(qǐng)求：prepare請(qǐng)求和accept請(qǐng)求。Acceptor可以忽略任意請(qǐng)求而不用擔(dān)心破壞算法的安全性。因此我們只需要說(shuō)明它在什么情況下可以對(duì)一個(gè)請(qǐng)求作出響應(yīng)。它可以在任何時(shí)候響應(yīng)prepare請(qǐng)求也可以在不違反現(xiàn)有承諾的情況下響應(yīng)accept請(qǐng)求。換句話說(shuō)：

P1a. 一個(gè)Acceptor可以通過(guò)一個(gè)編號(hào)為n的提案，只要它還未響應(yīng)任何編號(hào)大于n的prepare請(qǐng)求。

可以看出P1a包含了P1。

現(xiàn)在我們就獲得了一個(gè)滿足安全性需求的提案選定算法——假設(shè)在提案編號(hào)唯一的前提下。只要再做點(diǎn)小優(yōu)化，就能得到最終的算法了。
假設(shè)一個(gè)Acceptor收到了一個(gè)編號(hào)為n的prepare請(qǐng)求，但是它已經(jīng)對(duì)編號(hào)大于n的prepare請(qǐng)求作出了響應(yīng)，因此它肯定不會(huì)再通過(guò)任何新的編號(hào)為n的提案。那么它就沒有必要對(duì)這個(gè)請(qǐng)求作出響應(yīng)，因?yàn)樗隙ú粫?huì)通過(guò)編號(hào)為n的提案，于是我們會(huì)讓Acceptor忽略這樣的prepare請(qǐng)求，我們也會(huì)讓它忽略那些它已經(jīng)通過(guò)的提案的prepare請(qǐng)求。
通過(guò)這個(gè)優(yōu)化，Acceptor只需要記住它已經(jīng)通過(guò)的提案的最大編號(hào)以及它已經(jīng)響應(yīng)過(guò)prepare請(qǐng)求的提案的最大編號(hào)。因?yàn)楸仨氁诔鲥e(cuò)的情況下也保證P2c的不變性，所以Acceptor要在故障和重啟的情況下也能記住這些信息。Proposer可以隨時(shí)丟棄提案以及它的所有信息——只要它可以保證不會(huì)提出具有相同編號(hào)的提案即可。

把Proposer和Acceptor的行為結(jié)合起來(lái)，我們就能得到算法的如下兩階段執(zhí)行過(guò)程：
Phase 1:
Proposer選擇一個(gè)提案編號(hào)n，然后向Acceptor的多數(shù)集發(fā)送編號(hào)為n的prepare請(qǐng)求。
如果一個(gè)Acceptor收到一個(gè)編號(hào)為n的prepare請(qǐng)示，且n大于它所有已響應(yīng)請(qǐng)求的編號(hào)，那么它就會(huì)保證不會(huì)再通過(guò)任意編號(hào)小于n的提案，同時(shí)將它已經(jīng)通過(guò)的最大編號(hào)提案（如果存在的話）一并作為響應(yīng)。
Phase 2:
如果Proposer收到多數(shù)Acceptor對(duì)它prepare請(qǐng)求（編號(hào)為n）的響應(yīng)，那么它就會(huì)發(fā)送一個(gè)編號(hào)為n，value值為v的提案的accept請(qǐng)求給每個(gè)Acceptor，這里v是收到的響應(yīng)中最大編號(hào)提案的值，如果響應(yīng)中不包含任何提案，那么它就可以是任意值。
如果Acceptor收到一個(gè)編號(hào)為n的提案的accept請(qǐng)求，只要它還未對(duì)編號(hào)大于n的prepare作出響應(yīng)，它就可以通過(guò)這個(gè)提案。

一個(gè)Proposer可以提出多個(gè)提案，只要它能遵循以上算法約定。它可以在任意時(shí)刻丟棄某個(gè)提案（即使針對(duì)該提案的請(qǐng)求或響應(yīng)在提案丟棄后很久才到達(dá)，正確性依然可以保證）。如果Proposer已經(jīng)在嘗試提交更大編號(hào)的提案，那么丟棄也未嘗不是一件好事。因此，如果一個(gè)Acceptor因?yàn)橐呀?jīng)收到更高編號(hào)的prepare請(qǐng)求而忽略某個(gè)prepare或者accept請(qǐng)求，它應(yīng)該通知對(duì)應(yīng)的Proposer，然后該P(yáng)roposer可以丟棄這個(gè)提案。這是一個(gè)不影響正確性的性能優(yōu)化。

為了獲取被選定的值，一個(gè)Learner必須要能知道一個(gè)提案已經(jīng)被多數(shù)Acceptor通過(guò)了。最直觀的算法是，讓每個(gè)Acceptor在通過(guò)一個(gè)提案時(shí)就通知所有Learner，把通過(guò)的提案告知它們。這可以讓Learner盡快找到被選定的值，但這需要每個(gè)Acceptor和Learner之間互相通信——通信次數(shù)等于二者數(shù)量的乘積。

在假設(shè)非拜占庭錯(cuò)誤的前提下，一個(gè)Learner可以很容易地通過(guò)另一個(gè)Learner了解一個(gè)值已經(jīng)被選定了。我們可以讓所有Acceptor將它們的通過(guò)信息發(fā)送給一個(gè)特定的Learner，當(dāng)一個(gè)value被選定時(shí)，由它來(lái)通知其他Learner。這種方法需要額外一個(gè)步驟才能通知到所有Learner，而且它也不是可靠的，因?yàn)槟莻€(gè)特定的Learner可能會(huì)發(fā)生一些故障。但是這種情況下的通信次數(shù)，只需要二者數(shù)量之和。

更一般地，Acceptor可以將它們的通過(guò)信息發(fā)送給一個(gè)特寫的Learner集合，它們中的任何一個(gè)都可以在某個(gè)value被選定后通知所有Learner。這個(gè)集合中的Learner越多，可靠性就越好，通信復(fù)雜度也相應(yīng)更高。

因?yàn)橄⒖赡軙?huì)丟失，一個(gè)value被選定后，可能沒有Learner會(huì)發(fā)現(xiàn)。Learner可以向Acceptor詢問(wèn)它們通過(guò)了哪些提案，但是任一Acceptor出錯(cuò)，都有可能導(dǎo)致無(wú)法分辨是否有多數(shù)Acceptor通過(guò)了某個(gè)提案。在這種情況下，只有當(dāng)一個(gè)新的提案被選定時(shí)，Learner才能發(fā)現(xiàn)被選定的value。如果一個(gè)Learner想知道是否已經(jīng)選定一個(gè)value，它可以讓Proposer利用上面的算法提出一個(gè)提案。

很容易可以構(gòu)造出這樣一種情況，兩個(gè)Proposer持續(xù)地提出序號(hào)遞增的提案，但是沒有提案會(huì)被選定。Proposer p為編號(hào)為n1的提案完成Phase 1, 然后另一個(gè)Proposer q為編號(hào)為n2(n2>n1)的提案完成Phase 1。Proposer p對(duì)于編號(hào)n1的Phase 2的accept請(qǐng)求會(huì)被忽略，因?yàn)锳cceptor承諾不再通過(guò)任何編號(hào)小于n2的提案。這樣Proposer p就會(huì)用一個(gè)新的編號(hào)n3(n3>n2)重新開始并完成Phase 1，這又導(dǎo)致了Proposer q對(duì)于Phase 2的accept請(qǐng)求被忽略，如此往復(fù)。

為了保證進(jìn)度，必須選擇一個(gè)特定的Proposer作為唯一的提案提出者。如果這個(gè)Proposer可以和多數(shù)Acceptor進(jìn)行通信，并且可以使用比已用編號(hào)更大的編號(hào)來(lái)進(jìn)行提案的話，那么它提出的提案就可以成功被通過(guò)。如果知道有某些編號(hào)更高的請(qǐng)求，它可以通過(guò)舍棄當(dāng)前的提案并重新開始，這個(gè)Proposer最終一定會(huì)選到一個(gè)足夠大的提案編號(hào)。

如果系統(tǒng)中有足夠的組件（Proposer, Acceptor以及網(wǎng)絡(luò)通信）工作良好，通過(guò)選舉一個(gè)特定的Proposer，活性就能夠達(dá)到。著名的FLP理論[1]指出，一個(gè)可靠的Proposer選舉算法要么利用隨時(shí)性要么利用實(shí)時(shí)性來(lái)實(shí)現(xiàn)——比如使用超時(shí)機(jī)制。然而無(wú)論選舉是否成功，安全性都可以保證。

Paxos算法[5]假設(shè)了一組進(jìn)程網(wǎng)絡(luò)。在它的一致性算法中，每個(gè)進(jìn)程都扮演著Proposer, Acceptor以及Learner的角色。該算法選擇了一個(gè)Leader來(lái)扮演那個(gè)特定的Proposer和Learner。Paxos一致性算法就是上面描述的那個(gè)，請(qǐng)求和響應(yīng)都以普通消息的方式發(fā)送（響應(yīng)消息通過(guò)對(duì)應(yīng)的提案編號(hào)來(lái)標(biāo)識(shí)以避免混淆）。使用可靠的存儲(chǔ)設(shè)備存儲(chǔ)Acceptor需要記住的信息來(lái)防止出錯(cuò)。Acceptor在真正發(fā)送響應(yīng)之前，會(huì)將它記錄到可靠的存儲(chǔ)設(shè)備中。

剩下的就是描述如果保證不會(huì)用到重復(fù)編號(hào)的機(jī)制了。不同的Proposer從不相交的編號(hào)集合中選擇自己的編號(hào)，這樣任何兩個(gè)Proposer就不會(huì)用到相同的編號(hào)了。每個(gè)Proposer都記錄（在可靠存儲(chǔ)設(shè)備中）它使用過(guò)的最大編號(hào)，然后用比這更大編號(hào)的提案開始Phase 1。

有一種實(shí)現(xiàn)分布式系統(tǒng)的簡(jiǎn)單方式，就是使用一組客戶端集合向中央服務(wù)器發(fā)送命令。服務(wù)器可以看成一個(gè)以某種順序執(zhí)行客戶端命令的確定性狀態(tài)機(jī)。這個(gè)狀態(tài)機(jī)有個(gè)當(dāng)前狀態(tài)，通過(guò)接收一個(gè)命令當(dāng)作輸入來(lái)產(chǎn)生一個(gè)輸出和新狀態(tài)。比如，分布式銀行系統(tǒng)的客戶端可能是一些出納員，狀態(tài)機(jī)的狀態(tài)則由所有用戶的賬戶余額組成。一個(gè)取款操作，通過(guò)執(zhí)行一個(gè)減少賬戶余額的狀態(tài)機(jī)命令（當(dāng)且僅當(dāng)余額大于取款數(shù)目時(shí)）實(shí)現(xiàn)，然后將新舊余額作為輸出。

使用單點(diǎn)中央服務(wù)器的系統(tǒng)在該服務(wù)器故障的情況下，整個(gè)系統(tǒng)都將運(yùn)行失敗。因此我們用一組服務(wù)器來(lái)代替它，每個(gè)服務(wù)器都獨(dú)立實(shí)現(xiàn)了該狀態(tài)機(jī)。因?yàn)檫@個(gè)狀態(tài)機(jī)是確定性的，如果所有服務(wù)器都以同樣的順序執(zhí)行命令，那么它們將產(chǎn)生相同的狀態(tài)機(jī)狀態(tài)和輸出。一個(gè)提出命令的客戶端，可以使用任意服務(wù)器為它產(chǎn)生的輸出。

為了保證所有服務(wù)器都能執(zhí)行相同的狀態(tài)機(jī)命令序列，我們需要實(shí)現(xiàn)一系列獨(dú)立的Paxos一致性算法實(shí)例，第i個(gè)實(shí)例選定的值作為序列中的第i個(gè)狀態(tài)機(jī)命令。在算法的每個(gè)實(shí)例中，每個(gè)服務(wù)器擔(dān)任所有角色（Proposer，Acceptor和Learner）?，F(xiàn)在，我們假設(shè)服務(wù)器的集合是固定的，這樣所有的一致性算法實(shí)例都具有相同的參與者集合。

在正常執(zhí)行中，一個(gè)服務(wù)器被選舉成為L(zhǎng)eader，它會(huì)在所有一致性算法實(shí)例當(dāng)中扮演特定的Proposer（唯一的提案提出者）。客戶端給Leader發(fā)送命令，它來(lái)決定每條命令出現(xiàn)在序列當(dāng)中的位置。如果Leader決定某個(gè)客戶端命令應(yīng)該是第135個(gè)，它會(huì)嘗試讓該命令成為第135個(gè)一致性算法實(shí)例選定的value值。這通常都會(huì)成功，但是在一些故障或者有另外的服務(wù)器也認(rèn)為自己是Leader并且對(duì)第135個(gè)命令持有異議時(shí)，它可能會(huì)失敗。但是一致性算法可以保證，最多只有一條命令會(huì)被選定為第135條。

這個(gè)方法的關(guān)鍵在于，在Paxos一致性算法中，被提出的value值只在Phase 2才會(huì)被選定?；貞浺幌?，在Proposer完成Phase 1時(shí)，要么提案的value值被確定了，要么Proposer可以自由提出任意值。

我們現(xiàn)在描述了Paxos狀態(tài)機(jī)實(shí)現(xiàn)是怎樣在正常情況下運(yùn)行的，接下來(lái)我們看看會(huì)有哪些出錯(cuò)的情況，看下之前的Leader故障以及新的Leader被選舉出來(lái)后會(huì)發(fā)生什么（系統(tǒng)啟動(dòng)是一種特殊情況，此時(shí)還沒有命令被提出）。

新的Leader被選舉出來(lái)后，首先要成為所有一致性算法實(shí)例的Learner，需要知道目前已經(jīng)選定的大部分命令。假設(shè)它知道命令1-134，138以及139——也就是一致性算法實(shí)例1-134，138以及139選定的值（后面我們會(huì)看到這樣的命令缺口是如何產(chǎn)生的）。接下來(lái)它會(huì)執(zhí)行135-137以及139以后的算法實(shí)例的Phase 1（下面會(huì)描述如何來(lái)做）。假設(shè)執(zhí)行結(jié)果表明，實(shí)例135和140的提案值已被確定，但是其他執(zhí)行實(shí)例的提案值是沒有限制的。那么Leader可以執(zhí)行實(shí)例135和140的Phase 2，進(jìn)而選定第135和140條命令。

Leader以及其他已經(jīng)獲取Leader所有已知命令的服務(wù)器，現(xiàn)在可以執(zhí)行命令1-135。然而它還不能執(zhí)行命令138-140，因?yàn)槊?36和137還未被選定。Leader可以將接下來(lái)兩條客戶端請(qǐng)求的命令當(dāng)作命令136和137。同時(shí)我們也可以提出一個(gè)特殊的“noop”指令來(lái)立即填補(bǔ)這個(gè)空缺但保持狀態(tài)不變（通過(guò)執(zhí)行一致性算法實(shí)例136和137的Phase 2來(lái)完成）。一旦該no-op指令被選定，命令138-140就可以被執(zhí)行了。

命令1-140目前已經(jīng)被選定了。Leader也已經(jīng)完成了所有大于140的一致性算法實(shí)例的Phase 1，而且它可以在Phase 2中自由地為這些實(shí)例指定任意值。它為下一個(gè)從客戶端接收的命令分配序號(hào)141， 并在Phase 2中將它作為第141個(gè)一致性算法實(shí)例的value值。它將接收到的下一個(gè)客戶端命令作為命令142, 并以此類推。

Leader可以在它提出的命令141被選定前提出命令142。它發(fā)送的關(guān)于命令141的提案信息可能全部丟失，因此在所有其他服務(wù)器獲知Leader選定的命令141之前，命令142就可能已被選定。當(dāng)Leader無(wú)法收到實(shí)例141的Phase 2的期望回應(yīng)時(shí)，它會(huì)重傳這些信息。如果一切順利的話，它的提案命令將被選定。但是仍然可能會(huì)失敗，造成在選定的命令序列中出現(xiàn)缺口。一般來(lái)說(shuō)，假設(shè)Leader可以提前確定a個(gè)命令，這意味著命令i被選定之后，它就可以提出i+1到i+a的命令了。這樣就可能形成長(zhǎng)達(dá)a-1的命令缺口。

一個(gè)新選定的Leader需要為無(wú)數(shù)個(gè)一致性算法實(shí)例執(zhí)行Phase 1——在上面的場(chǎng)景中，就是135-137以及所有大于139的執(zhí)行實(shí)例。通過(guò)向其他服務(wù)器發(fā)送一條合適的消息，就可以讓所有執(zhí)行實(shí)例使用同一個(gè)提案編號(hào)（計(jì)數(shù)器）。在Phase 1中，只要一個(gè)Acceptor已經(jīng)收到來(lái)自某Proposer的Phase 2消息，那么它就可以為不止一個(gè)實(shí)例作出通過(guò)回應(yīng)（在上面的場(chǎng)景中，就是針對(duì)135和140的情況）。因此一個(gè)服務(wù)器（作為Acceptor時(shí)）可以用一條適當(dāng)?shù)亩滔?duì)所有實(shí)例作出回應(yīng)。執(zhí)行這樣無(wú)限多的實(shí)例的Phase 1也不會(huì)有問(wèn)題。
這里應(yīng)該是指穩(wěn)定的Paxos模型，Phase 1可以被省略，只要編號(hào)計(jì)數(shù)器是唯一的。

由于Leader的故障和新Leader的選舉是很少見的情況，那么執(zhí)行一條狀態(tài)機(jī)命令的主要開銷，即在命令值上達(dá)成一致性的開銷，就是執(zhí)行一致性算法中Phase 2的開銷?？梢宰C明，在允許失效的情況下，Paxos一致性算法的Phase 2在所有一致性算法中具有最小可能的時(shí)間復(fù)雜度[2]。因此Paxos算法基本上是最優(yōu)的。

在系統(tǒng)正常運(yùn)行的情況下，我們假設(shè)總是只有一個(gè)Leader，只有在當(dāng)前Leader故障及選舉出新Leader之間的短時(shí)間內(nèi)才會(huì)違背這個(gè)假設(shè)。在特殊情況下，Leader選舉可能失敗。如果沒有服務(wù)器扮演Leader，那么就沒有新命令被提出。如果同時(shí)有多個(gè)服務(wù)器認(rèn)為自己是Leader，它們?cè)谝粋€(gè)一致性算法執(zhí)行實(shí)例中可能提出不同value值，這可能導(dǎo)致沒有任何值能被選定。但是安全性是可以保證的——不可能有兩個(gè)不同的值被選定為第i條狀態(tài)機(jī)命令。單個(gè)Leader的選舉只是為了保證流程能往下進(jìn)行。

如果服務(wù)器的集合是變化的，那么必須有某種方法可以決定哪些服務(wù)器來(lái)實(shí)現(xiàn)哪一些一致性算法實(shí)例。最簡(jiǎn)單的方式就是通過(guò)狀態(tài)機(jī)本身來(lái)完成。當(dāng)前的服務(wù)器集合可以是狀態(tài)的一部分，同時(shí)也可以通過(guò)狀態(tài)機(jī)命令來(lái)改變。通過(guò)用執(zhí)行完第i條狀態(tài)機(jī)命令后的狀態(tài)來(lái)描述執(zhí)行一致性算法i+a的服務(wù)器集合，我們就能讓Leader提前獲取a個(gè)狀態(tài)機(jī)命令。這就允許任意復(fù)雜的重配置算法有一個(gè)簡(jiǎn)單實(shí)現(xiàn)。

參與文獻(xiàn)

[1]    Michael J. Fischer, Nancy Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process.
Journal of the ACM, 32(2):374–382, April 1985. [2]    Idit Keidar and
Sergio Rajsbaum. On the cost of fault-tolerant consensus when there
are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory
for Computer Science, Massachusetts Institute Technology, Cambridge,
MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3]    Leslie Lamport. The implementation of reliable distributed
multiprocess systems. Computer Networks, 2:95–114, 1978. [4]    Leslie
Lamport. Time, clocks, and the ordering of events in a distributed
system. Communications of the ACM, 21(7):558–565, July 1978. [5]    (1,
2, 3, 4) Leslie Lamport. The part-time parliament. ACM Transactions on
Computer Systems, 16(2):133–169, May 1998.