【這篇論文我翻一下來，首先感覺還是不好懂，很多地方結(jié)論的得出不夠清楚，需要讀者自己思考其中的原因。要理解Paxos算法，個人建議先搜索下介紹算法的中文文章，大致了解下Paxos算法要做什么，然后就再讀下論文，應(yīng)該會有所感悟。】

Paxos Made Simple

Leslie Lamport

01 Nov 2001

說明

【說明這部分是我自己加的，下面這幾個詞大量出現(xiàn)與論文的主體部分，提前了解它們的含義有助于后面對于算法原理和流程的理解。】

• 議案(proposal):由提議人提出，由審批人進行初審和復(fù)審，包括議案編號和議案內(nèi)容。
• 內(nèi)容(value):議案的內(nèi)容。
• 編號(id):議案的編號，全局唯一。
• 提議人(proposer):提出議案，接收審批人的初審和復(fù)審意見。
• 審批人(acceptoer):接收議案，根據(jù)規(guī)則決定初審和復(fù)審結(jié)果，返回給提議人。
• 執(zhí)行人(learner):一旦議案成為決議，就要通知所有執(zhí)行人。
• 初審(accept):議案的第一輪審核，通過后可以進行復(fù)審。
• 復(fù)審(chossen):議案的第二輪審核，通過后將成為決議。

摘要

Paxos算法，當(dāng)用簡明英語表述時，灰常簡單。【大神的第一篇論文用在虛構(gòu)的希臘島嶼Paxos上的人們通過議會表決法律來解釋Paxos算法，群眾紛紛表示太難理解了。大神表示你們這群渣渣不懂我的幽默，既然如此，我就用簡明英語再表述一遍，哼！】

1 介紹

Paxos算法的目標(biāo)是實現(xiàn)一個具有容錯能力的分布式系統(tǒng)。人們覺得這一算法哪一理解，也許對許多讀者來說，算法最初使用希臘語表述的。[5]事實上，這一算法是分布式算法中最簡單直觀的算法之一。【Google Chubby的作者Mike Burrows:there is only one consensus protocol, and that’s Paxos– all other approaches are just broken versions of Paxos.】這一算法的核心是論文[5]中提到的一致性算法“synod”。下一章我們將看到這一算法如何嚴(yán)格遵守我們制定的規(guī)則。最后一章會通過將一致性算法應(yīng)用于構(gòu)建分布式系統(tǒng)的確定狀態(tài)機（這是分布式理論的文章最常常引用的論文的內(nèi)容[4]）來對Paxos算法進行完整的解釋。

2 一致性算法

2.1 問題的提出

假設(shè)我們有一組服務(wù)器，他們都可以提出議案。一致性算法要保證被提出的多個議案中最終只有一個議案可以通過審核成為決議。如果沒有議案提出，就不會產(chǎn)生決議。如果一個議案成為決議，那么所有process都應(yīng)當(dāng)知道這個決議。那么，要保證一致性就要滿足：

• 所有被提出的議案中只有一個議案可以成為決議
• 只有一個議案成為決議，且
• 服務(wù)器永遠不知道一個議案成為了決議，除非這個議案真的成為了決議

這一過程的運行時間并不重要，但要保證最終將會有某個議案成為決議，并且，一旦議案成為決議，所有服務(wù)器都能夠知道這一決議。

我們用三類代理人代表一致性算法中的三個角色：提議人、審批人和執(zhí)行人。在具體實現(xiàn)中，單個服務(wù)器可以扮演多種代理人，我們不需要關(guān)心他們之間的對應(yīng)關(guān)系。【同一臺服務(wù)器，可以即是提議人，又是審批人或執(zhí)行人。】

假設(shè)代理間通過消息通信。這里我們使用傳統(tǒng)的異步、非拜占庭模型【不考慮拜占庭問題，代理間通信可能丟失或重復(fù)，但不會被篡改】：

• 服務(wù)器運行效率不確定，可能停機或重啟。因為當(dāng)決議產(chǎn)生后所有服務(wù)器都有可能停機重啟，所以服務(wù)器必須能夠做到即使停機重啟也可以記住某些信息，否則停機重啟的問題將無法解決。
• 消息傳遞時間任意，消息可以重復(fù)發(fā)送，允許丟失，但不允許修改。

2.2 選擇決議

只有一個審批人的狀況是最簡單的。提議人向?qū)徟税l(fā)送議案，審批人選擇接收到的第一個議案作為決議。這個方案無法解決單機失效問題，如果審批人停機，整個系統(tǒng)將被阻塞。

因此，我們來嘗試另一種選擇決議的方式：讓多個審核人共同參與決議的產(chǎn)生。提議人向一部分審核人發(fā)送議案，審核人可能會初審?fù)ㄟ^這一議案。當(dāng)足夠多的審核人初審?fù)ㄟ^這一議案時，議案就可以進行復(fù)審了。多少人算足夠多？為了保證只有一個議案成為決議，足夠多的人必須包括審核人的多數(shù)派，即半數(shù)以上的審批人。因為任何兩個多數(shù)派集合中至少有一個成員是公共的，因此只要保證一個審批人同一時間最多只能初審?fù)ㄟ^一條議案【這里指的是審批人承認這一議案通過初審，當(dāng)該議案進行復(fù)審時，也會通過復(fù)審的狀態(tài)】，就可以保證最終只有一個議案可以成為決議。 (在大量論文中都涉及了多數(shù)派的研究，最早出現(xiàn)于[3])

在不存在服務(wù)器停機或消息丟失的前提下，我們希望即使只發(fā)起了一個議案，這個議案仍可以成為決議。因此我們需要滿足以下條件：

P1.對于接收到的第一個議案，審核人必須初審?fù)ㄟ^。

但是這一條件會產(chǎn)生一個問題。不同提議人幾乎同時提出不同的議案，導(dǎo)致每個審批人都初審?fù)ㄟ^了一個議案，但是沒有一個議案同時被半數(shù)以上的審批人初審?fù)ㄟ^。即使只有兩個議案，審批人有2n+1個，且他們分別被n個審批人初審?fù)ㄟ^，那么最后一個審批人的停機就可能導(dǎo)致無法產(chǎn)生決議。

條件P1以及決議的產(chǎn)生必須經(jīng)過多數(shù)派審核這一條件表明審批人應(yīng)當(dāng)可以先后初審?fù)ㄟ^多條議案。我們通過為每一個議案分配一個編號來追蹤不同的議案，這樣一個議案就包括議案編號和議案內(nèi)容兩部分。為了防止混淆，我們要求不同議案的編號也必須不同。關(guān)于這點如何保證依賴于具體實現(xiàn)，我們這里只是假設(shè)他成立?！?em>google的編號生成算法在附錄，有興趣的可以看下】當(dāng)一項議案被審批人中的多數(shù)派初審?fù)ㄟ^后，這項議案的內(nèi)容將進入復(fù)審階段。

我們允許多個議案進入復(fù)審階段，但是我們必須保證這些議案的內(nèi)容是相同的。通過引入議案編號，我們可以保證以下條件：

P2.如果一個編號為n內(nèi)容為v的議案【下文用議案（n,v）替代】進入復(fù)審階段，那么所有進入復(fù)審階段的議案編號大于n的議案，他們的議案內(nèi)容也為v。**
【條件P2以及后續(xù)P2的強化條件都在保證一件事：多個提議人可以提出多個議案，議案編號各不相同，但是這些議案的內(nèi)容最終都會一樣】

由于議案編號是有序的，條件P2嚴(yán)格保證了只有一個議案內(nèi)容可以成為決議。

要進入復(fù)審階段并最終成為決議，議案必須被至少一個審批人初審?fù)ㄟ^。因此要滿足條件P2,我們只要滿足以下條件：

P2a.如果議案（n,v）進入復(fù)審階段，那么所有通過初審的編號大于n的議案的議案內(nèi)容為v。

我們?nèi)孕枰獫M足條件P1以保證會有決議產(chǎn)生。因為通信是異步的，一個議案可能被任何尚未收到過議案的審批人初審?fù)ㄟ^，這違背了條件P2a。要保證P1和P2a同時有效，需要把P2a加強為以下條件：

P2b.如果議案（n,v）進入復(fù)審階段，那么任何提議人提出的編號大于n的議案，議案內(nèi)容為v。

因為一個議案首先要由提議人提出才有可能被審批人初審?fù)ㄟ^，所以條件P2b保證了條件P2a也就保證條件P2.

在找到方法滿足P2b前，我們先研究如何使這一條件成立。假設(shè)議案（m,v）進入復(fù)審階段，如何使議案編號為n且n>m的任意議案的議案內(nèi)容為v 。我們使用對n使用數(shù)學(xué)歸納法證明，這樣我們要證明議案n的內(nèi)容為v，就要需要額外的假設(shè)條件：任意編號在m和n-1區(qū)間內(nèi)的議案的內(nèi)容為v。因為議案（m,v）已經(jīng)進入復(fù)審階段，那么必然有一個多數(shù)派的審批人集合C，集合中的每個審批人都對議案m初審?fù)ㄟ^。把這一結(jié)論與額外條件結(jié)合，議案m進入復(fù)審階段表明：

每個集合C中的審批人都初審?fù)ㄟ^一個編號在m和n-1區(qū)間內(nèi)的議案，并且所有編號在m和n1-1區(qū)間內(nèi)的議案內(nèi)容為v。

【要理解這一部分，需要了解算法的具體執(zhí)行過程。對于編號m到n-1的議案，議案的內(nèi)容為v，提議人是怎么樣決定議案內(nèi)容的呢？提議人必然是通過向集合C中的某些成員發(fā)送初審請求并通過初步審核后，從回復(fù)信息中獲知這一信息的。這就是上半句話的解釋】

因為任意審批人多數(shù)派的集合S和集合C至少有一個成員相同，那么只要保證以下條件成立，議案n的內(nèi)容就可以保證為v：

P2c.對任意內(nèi)容v和編號n，議案（n,v）如果被某個提議人發(fā)出，那么必然有一個審批人的多數(shù)派集合S，他們要么

（a） S中的任何審批人都沒有收到過編號小于n的議案，或者

（b） 集合S中所有審批人初審?fù)ㄟ^的編號小于n的議案中編號最大的那個議案的議案內(nèi)容為v。

我們可以證明滿足條件P2c即可滿足條件P2b。

要保證條件P2c，當(dāng)一個提議人想要發(fā)出一個編號為n的議案時，他必須知道已經(jīng)或?qū)⒁ㄟ^多數(shù)派審批人初步審核的編號小于n的議案中編號最大的那個議案的內(nèi)容。要知道已經(jīng)通過初審的議案很簡單，但是預(yù)測未來的初審結(jié)果很難。為了規(guī)避預(yù)測未來這一難題，審批人必須保證不會有允許這樣的初審結(jié)果出現(xiàn)。也就是說，提議人要求審批人一旦初審?fù)ㄟ^編號為n的議案將不得再初審?fù)ㄟ^編號小于n的議案。因此發(fā)出議案的算法如下：

1. 一個提議人生成一個新的議案編號n并發(fā)給一半以上的任意審批人，要求他們回復(fù)：

（a） 保證不再審核通過【包括初審和復(fù)審】編號小于n的議案，且**

（b） 如果已經(jīng)初審?fù)ㄟ^了議案，把編號小于n且編號最大的那個議案的編號和內(nèi)容回復(fù)給我。

這一過程稱為編號為n的議案的初審請求。

2. 如果提議人收到了半數(shù)以上的初審?fù)ㄟ^回復(fù)，那么他將發(fā)起一個議案，議案的編號為n，內(nèi)容為v，【請注意，此時才決定議案內(nèi)容，之前初步審核只是要確認議案編號是否可用】如果審批人的回復(fù)中包括議案，v就是這些議案中編號最大的那個議案的內(nèi)容，如果審批人的回復(fù)中不包括議案，那么提議人可以自己設(shè)置一個議案內(nèi)容。**

提議人向多數(shù)派審批人發(fā)送已經(jīng)通過初審的議案（初審的多數(shù)派和這次審核的多數(shù)派成員可以不同），我們稱第二次審核的過程為復(fù)審。

以上就是提議人的算法，審批人呢？他接受兩種審批請求：初審請求和復(fù)審請求。審批人可以拒絕任意請求而不會對系統(tǒng)造成損害，我們應(yīng)當(dāng)說清楚在什么情況下審批人可以回復(fù)一個請求。在不違背初審?fù)ㄟ^時的承諾【保證不再審核通過編號小于n的議案】的前提下，他既可以初審?fù)ㄟ^又可以復(fù)審?fù)ㄟ^一個議案。換句話說：

P1a.一個審批人可以初審或復(fù)審?fù)ㄟ^一個議案（n,v），當(dāng)且僅當(dāng)他從未初審?fù)ㄟ^一個編號大于n的議案。
【當(dāng)審批人從未收到任何議案時，他可以初審?fù)ㄟ^收到的任何議案，這符合條件P1.所以】P1a包含了P1.

我們現(xiàn)在擁有完整的決議產(chǎn)生算法并且滿足我們設(shè)定的條件——議案編號唯一。最終算法仍需要一些優(yōu)化。

假設(shè)審批人收到了一個編號為n的初審請求，但是他已經(jīng)初審?fù)ㄟ^了編號大于n的議案，因此已經(jīng)保證過不對編號為n的議案做出回應(yīng)。因為他不會初審?fù)ㄟ^這一議案，所以他沒有必要對初審請求做出回應(yīng)。因此我們讓審批人忽略這一初審請求，同時，審批人也會忽略再次收到的已經(jīng)初審?fù)ㄟ^的議案的初審請求。

這一優(yōu)化要求審批人必須且只需記住他收到過的編號最高的議案以及他初審?fù)ㄟ^的編號最高的議案。因為P2c條件在某些角色停機的情況下仍要保證有效，審批人即使在停機重啟后仍要記的這些信息。注意提議人可以隨時放棄當(dāng)前的議案或者忘掉之前提出過的議案，但是他必須保證議案的編號唯一且遞增。

把提議人和審批人的算法結(jié)合在一起，我們得到下面兩個階段的算法：

階段1

（a） 提議人生成議案編號n，向半數(shù)以上審批人發(fā)送編號為n的初審請求。

（b） 如果審批人收到的初審請求編號n大于他之前初審?fù)ㄟ^的議案編號，將回復(fù)兩個信息：一個是保證不再對編號小于n的議案做出回應(yīng)【包括初審和復(fù)審】，二是如果之前初審?fù)ㄟ^了議案，將其中編號最大的議案的編號和內(nèi)容回復(fù)給提議人。**

階段2
（a） 如果提議人收到了半數(shù)以上的審批人的初審?fù)ㄟ^回復(fù)，他將會以議案（n,v）發(fā)送復(fù)審請求。對于議案內(nèi)容v，如果審批人的初審回復(fù)中包含議案，那么v就是這些議案中編號最大的那個議案的內(nèi)容，如果初審回復(fù)中不包含議案，提議人可以自行決定議案內(nèi)容v。

（b） 如果審批人收到了編號為n的議案的復(fù)審請求，只要他沒有初審?fù)ㄟ^編號大于n的議案【從而做出過保證】，他會復(fù)審?fù)ㄟ^這一議案。**

提議人可以在遵守算法規(guī)則的前提下提出多個議案。他可以在協(xié)議的任意階段隨時放棄某個議案。（算法不會因此出現(xiàn)問題，即使審核請求或回復(fù)在議案被拋棄后才接收到）如果其他提議人開始發(fā)起編號更高的議案，也許放棄當(dāng)前編號較低的議案是個好主意?！?em>不管編號更高的議案能否通過多數(shù)派的初審，都意味著當(dāng)前編號的議案不會得到半數(shù)以上的通過回復(fù)，發(fā)送請求和等待回復(fù)將是浪費時間】因此，如果審批人因為保證過不再回復(fù)編號較小的議案而忽略某些議案時，他應(yīng)當(dāng)通知提議人：你的議案編號太小了，放棄當(dāng)前議案，選一個更大的編號，重新發(fā)送申請。這是一個性能方面的優(yōu)化，不會影響算法的正常運行。

2.3 產(chǎn)生決議后如何通知執(zhí)行人

要隨時知道一個決議是否產(chǎn)生了，執(zhí)行人必須能隨時獲悉是否有一個議案被半數(shù)以上審批人復(fù)審?fù)ㄟ^。首先想到的算法是，讓審批人每次復(fù)審?fù)ㄟ^一條議案，就給所有執(zhí)行人發(fā)送一條消息。這使得執(zhí)行人可以實時了解當(dāng)前審核情況，但是這要求每個審批人和每個執(zhí)行人通信，通信規(guī)模是兩者數(shù)量的乘積。

非拜占庭問題的假設(shè)使得執(zhí)行人獲得消息變得簡單。我們可以選出一個執(zhí)行人代表，所有審批人都與執(zhí)行人代表進行通信，而當(dāng)決議產(chǎn)生時，執(zhí)行人代表再把決議通知其他執(zhí)行人。這里需要一輪額外的通信以通知所有執(zhí)行人當(dāng)前決議。而且這一做法更不可靠，因為執(zhí)行人代表也可能停機。但是他的通信量僅僅是兩者數(shù)量之和。
更進一步，我們可以讓審批人和多個執(zhí)行人代表通信，每個執(zhí)行人代表都可以在決議產(chǎn)生后通知其他執(zhí)行人。多個執(zhí)行人代表可以使系統(tǒng)更加穩(wěn)定但是通信的復(fù)雜度也會提高。

由于允許通信失敗，執(zhí)行人可能無法得知進入復(fù)審階段議案的內(nèi)容。執(zhí)行人可以向所有審批人詢問當(dāng)前初審?fù)ㄟ^的議案，但是某個審批人停機就可能導(dǎo)致沒有一個議案被半數(shù)以上審批人初審?fù)ㄟ^。在這一情況下，只有當(dāng)新的議案進入復(fù)審階段時，執(zhí)行人才能知曉議案內(nèi)容。如果執(zhí)行人需要知道當(dāng)前是否有進入復(fù)審階段的議案的內(nèi)容，他可以要求提議人根據(jù)上面的算法發(fā)起一個議案。【這個新議案的議案編號足夠大，發(fā)起初審請求后能夠得到半數(shù)以上審批人的回復(fù)，他們的回復(fù)中如果有議案，議案編號最大的那個議案內(nèi)容就是目前進入復(fù)審階段的議案內(nèi)容。提議人可以繼續(xù)發(fā)起復(fù)審請求，也可以放棄當(dāng)前議案。最終產(chǎn)生的決議內(nèi)容是不會發(fā)生變化的。】

2.4 保證算法的進行

很容易就可以想到一個場景，兩個提議人輪流發(fā)起編號遞增的提議并通過初步審核，雖然按照算法規(guī)則，他們的提議內(nèi)容是相同的，但是由于復(fù)審請求時，審批人已經(jīng)初審?fù)ㄟ^了另一個編號更高的議案，導(dǎo)致自己的復(fù)審請求無法通過，因此永遠無法產(chǎn)生決議。提議人p的議案n1通過初審，然后提議人q的議案n2通過初審，n2>n1；提議人p的復(fù)審請求將被忽略，因為審批人已經(jīng)保證過不再回復(fù)編號小于n2的議案。然后提議人p將議案編號提高為n3，n3>n2，并通過初步審核，導(dǎo)致q的復(fù)審請求也被忽略。這樣重復(fù)下去，永遠無法產(chǎn)生決議?！?em>活鎖】

要保證算法進行下去，必須選出一個提議人代表，只有他可以發(fā)出議案。如果提議人代表可以和半數(shù)以上的審核人成功通信，并且他提出的議案編號比所有已經(jīng)提出過的議案的編號都大，他就可以成功讓議案變成決議。如果通過審核人的忽略回復(fù)得知已經(jīng)存在某些編號更高的議案，提議人代表會放棄當(dāng)前議案，增大議案編號然后重新進行步驟一的初步審核，最終，提議人代表能夠選出一個足夠大的編號用于產(chǎn)生決議。

如果分布式系統(tǒng)中足夠多的部分正常工作（至少一個提議人、半數(shù)以上審批人、工作正常的通信網(wǎng)絡(luò)），通過選舉選出一個提議人代表就可以保證系統(tǒng)正常運行。Fischer,lynch和Patterson[1]的著名研究結(jié)果表明，可靠地選舉算法要么是隨機的，要么是實時的-比如使用超時機制?！?em>另一篇文章中關(guān)于FLP理論與Paxos算法的討論：其實仔細回憶Paxos論文會發(fā)現(xiàn)，Paxos中存在活鎖，理論上的活鎖會導(dǎo)致Paxos算法無法滿足Termination屬性，也就不算一個正確的一致性算法。Lamport在自己的論文中也提到“FLP結(jié)果表明，不存在完全滿足一致性的異步算法..."，因此他建議通過Leader來代替Paxos中的Proposer，而Leader則通過隨機或其他方式來選定（Paxos中假如隨機過程會極大降低FLP發(fā)生的概率）。也就是說Paxos算法其實也不算理論上完全正確的，只是在工程實現(xiàn)中避免了一些理論上存在的問題。但這絲毫不影響Paxos的偉大性！】但是，不管選舉成功還是失敗，系統(tǒng)安全性都可以得到保障。

2.5 實現(xiàn)

Paxos算法[5]建立在一組通過網(wǎng)絡(luò)通信的服務(wù)器上。在此一致性算法中，每個服務(wù)器都可以是提議人、審批人或執(zhí)行人。算法選舉出一個提議人代表防止活鎖出現(xiàn)、選出一個執(zhí)行人代表降低通信復(fù)雜度。Paxos一致性算法中的審核請求和審核回復(fù)都以普通消息的形式發(fā)送（審核回復(fù)帶有相應(yīng)的議案編號防止出現(xiàn)消息發(fā)送失敗、延遲或重復(fù)時導(dǎo)致提議人的混亂）。持久化存儲保證即使停機后仍可以保存數(shù)據(jù)，用來保存審核人必須記住的信息。審核人在發(fā)送審核回復(fù)消息前，會先在持久化存儲中存儲這些消息。

最后要描述的是實現(xiàn)任意兩個議案編號不相同的機制。不同的提議人從互不相交的集合中選擇編號，因此兩個提議人不會生成相同的編號。每個提議人都會存儲他們發(fā)出過的最大的議案編號，當(dāng)他們再次開始步驟一的初步審核申請時，會選擇一個比之前議案編號更大的編號。

3 有限狀態(tài)機的實現(xiàn)

實現(xiàn)分布式系統(tǒng)的一個方案是由一組客戶端向中心服務(wù)器發(fā)送指令。中心服務(wù)器作為確定狀態(tài)自動機按一定順序執(zhí)行接收的指令。狀態(tài)機根據(jù)當(dāng)前狀態(tài)和接收到的指令產(chǎn)生輸出結(jié)果和新的狀態(tài)。例如，分布式銀行系統(tǒng)的客戶端可能是出納員，而狀態(tài)機的狀態(tài)可能是所有賬戶余額的集合。提現(xiàn)操作會向狀態(tài)機發(fā)出指令，當(dāng)且僅當(dāng)賬戶余額不小于提現(xiàn)金額時，減少賬戶余額數(shù)量【新的狀態(tài)】，并返回提現(xiàn)前后的余額【輸出】。

單個中心服務(wù)器無法解決單機失效問題。因此我們使用一組中心服務(wù)器，每個服務(wù)器都是一個獨立的狀態(tài)機。因為狀態(tài)機屬于確定狀態(tài)自動機，所以當(dāng)輸入命令的內(nèi)容和順序相同時，這些狀態(tài)的狀態(tài)變化和輸出也是相同的。因此客戶端的指令發(fā)送給任何服務(wù)器都是有效的。

要保證所有服務(wù)器執(zhí)行相同的狀態(tài)機指令序列，我們執(zhí)行多輪paxos一致性算法，第i輪產(chǎn)生的決議作為指令序列中第i條狀態(tài)機指令。每個服務(wù)器都將作為提議人、審核人和執(zhí)行人參與到算法中。我們假設(shè)服務(wù)器組不發(fā)生變動，每一輪算法執(zhí)行都是用同一組服務(wù)器。

通常，某個服務(wù)器會被選出作為提議人代表，在每一輪算法執(zhí)行時，只有代表可以提出議案。客戶端向代表發(fā)送指令，由提議人代表決定指令應(yīng)該何時執(zhí)行。如果代表決定某條指令應(yīng)當(dāng)成為指令隊列中第135條指令，他會把這條指令作為議案內(nèi)容發(fā)送給審核人，最終形成決議。一般情況下總是可以成功的。但也有失敗的可能，如果出現(xiàn)通信失敗、停機或者另一個服務(wù)器誤以為自己也是提議人代表，并且希望另一條指令成為第135條指令。但是Paxos算法保證至多只有一條指令可以成為第135條指令。

產(chǎn)生這一結(jié)果的關(guān)鍵是，在Paxos一致性算法中，決議必須要經(jīng)過復(fù)審才可以產(chǎn)生?；叵胍幌拢?dāng)議案通過初審時，提議人自己也不確定議案內(nèi)容是什么，他必須根據(jù)審批人的回復(fù)來決定要么使用之前的議案內(nèi)容、要么自己決定議案內(nèi)容。

現(xiàn)在我將描述正常情況下Paxos狀態(tài)機如何工作。稍后，再來討論可能出現(xiàn)的風(fēng)險?？紤]上一個代表停機，新的代表剛剛選出的情況。（系統(tǒng)啟動狀態(tài)是一個特殊狀態(tài)，此時還沒有任何議案提出）

新的提議人代表，作為執(zhí)行人，應(yīng)當(dāng)知道已經(jīng)產(chǎn)生的指令隊列中的大部分指令。假設(shè)他知道指令1-134號，138號和139號，即第1輪到134輪，138輪和139輪算法執(zhí)行的結(jié)果。（我們稍后會看到這種指令空缺是如何產(chǎn)生的）然后他開始執(zhí)行空缺的135-137輪算法以及139輪以后的算法的初審階段。假設(shè)只有135輪和140輪的議案初審?fù)ㄟ^的回復(fù)中包含指令信息，其他輪的初審回復(fù)不包含指令信息【這里是指135輪和140輪之前已經(jīng)進行過，在初審?fù)ㄟ^的返回信息中包含了之前已經(jīng)進入復(fù)審階段的議案，而進入復(fù)審階段的議案是包含議案內(nèi)容的，因此不需要等待客戶端發(fā)送指令請求來決定議案內(nèi)容，可以直接發(fā)起復(fù)審請求】。提議人代表之后會執(zhí)行135輪和140輪的復(fù)審階段，最終產(chǎn)生135號指令和140號指令。

提議人代表以及所有從提議人代表處了解到所有指令的服務(wù)器都可以執(zhí)行1-135號指令。但是，138號-140號指令不能執(zhí)行，因為136號和137號指令還沒有產(chǎn)生。提議人可以用接下來收到的兩條客戶端指令請求作為136號和137號指令。但是為了立即彌補指令空缺，我們用‘no-op’指令作為136號和137號指令的議案內(nèi)容，這一指令不會對狀態(tài)機狀態(tài)產(chǎn)生影響。一旦這兩條no-op指令被選出為決議，指令138號-140號就可以執(zhí)行了。

第1號-140號指令都已經(jīng)產(chǎn)生。提議人代表也已經(jīng)完成了所有編號大于140的指令的初審階段，提議人代表可以自由決定復(fù)審階段應(yīng)當(dāng)使用的議案內(nèi)容。他把接下來收到的第一個客戶端指令請求作為141號指令進行復(fù)審。接著把收到的下一條客戶端指令作為142號，以此類推。

提議人代表不需要等待141號指令產(chǎn)生就可以發(fā)起142號指令的復(fù)審請求。有可能提議人發(fā)出的所有141號指令復(fù)審請求都發(fā)送失敗，可能142號指令已經(jīng)產(chǎn)生了，執(zhí)行人還不知道141號指令的內(nèi)容是什么。當(dāng)執(zhí)行人沒有收到關(guān)于141號指令的復(fù)審請求回復(fù)時，他會再次發(fā)送請求。如果一切正常，141號指令就會成功產(chǎn)生。然而，這次仍有可能失敗，導(dǎo)致指令隊列中出現(xiàn)空缺。綜上，如果一個提議人可以一次產(chǎn)生長度為α的指令隊列，那么當(dāng)指令1到指令i產(chǎn)生后，他可以繼續(xù)產(chǎn)生指令i+1到i+α。最壞的情況是產(chǎn)生一個α-1大小的指令空缺?！?em>i+1輪到i+α-1輪的算法執(zhí)行都沒有成功，i+α輪執(zhí)行成功】

新產(chǎn)生的提議人代表要執(zhí)行無限多次初審請求【初審請求為了確定議案的編號，不需要知道議案的內(nèi)容，也就是說在收到初審?fù)ㄟ^的回復(fù)前，提議人也不知道指令內(nèi)容是什么，由于整個系統(tǒng)中只有一個提議人發(fā)送請求，初審請求一般是一次通過的】，在上面的場景中，提議人要執(zhí)行135輪-137輪以及139輪之后算法的初審階段。通過在審核回復(fù)中添加額外的信息【當(dāng)前算法執(zhí)行輪數(shù)】，提議人就可以在不同算法執(zhí)行輪中使用相同的議案編號。在初審階段，僅當(dāng)某個議案進入復(fù)審階段時，審批人在回復(fù)給其他提議人的初審?fù)ㄟ^消息中會附帶該議案的議案編號和議案內(nèi)容。因此，審批人對于每一輪算法執(zhí)行過程中的消息回復(fù)都可以非常精簡。【僅包括算法執(zhí)行輪數(shù)和已經(jīng)進入復(fù)審的議案內(nèi)容】即使執(zhí)行無窮多次初審階段也不會造成任何問題。

由于提議人代表停機并選擇新的提議人是非常罕見的情況，產(chǎn)生狀態(tài)機指令序列的效率，也就是在指令/決議上達成一致的效率僅僅取決于算法執(zhí)行的復(fù)審階段?？梢宰C明，在允許失效的情況下【停機、消息發(fā)送失敗】，Paxos算法比其他任何算法都更加高效。因此，Paxos算法絕對是一致性算法的最佳選擇。

以上討論假設(shè)提議人代表在系統(tǒng)中一直在線，除了當(dāng)前代表停機和選出新代表間的短暫時間。在特殊情況下，新代表的選舉也可能失敗。如果沒有提議人代表在線，就無法產(chǎn)生新的指令。如果多個服務(wù)器都認為自己是代表，那么他們會在算法執(zhí)行的每一輪都提出議案，導(dǎo)致活鎖，同樣使得指令無法產(chǎn)生。然而算法的安全性是可以保證的，兩個服務(wù)器也許會提出不同的議案，但是他們的議案內(nèi)容必然是相同的。選出單個的提議人代表只是為了避免活鎖的出現(xiàn)。

如果服務(wù)器組可以變動，必須有辦法確定哪些服務(wù)器參與了某一輪算法的執(zhí)行。最簡單的方法是通過改變狀態(tài)機狀態(tài)來實現(xiàn)。當(dāng)前服務(wù)器組作為狀態(tài)信息的一部分，當(dāng)服務(wù)器發(fā)生變化時，可以通過狀態(tài)機指令修改狀態(tài)來記錄。在執(zhí)行完第i條指令后，通過標(biāo)明將要參與第i+α輪算法執(zhí)行的服務(wù)器組，就可以保證執(zhí)行人代表可以提前發(fā)布α條指令的初審請求。這樣就實現(xiàn)了一個簡單地arbitrarily sophisticated reconfiguration algorithm。

參考文獻

• [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] Leslie Lamport. The part-time parliament. ACM Transactions on Com- puter Systems, 16(2):133–169, May 1998.

附錄

議案編號生成算法

在Google的Chubby論文中給出了這樣一種方法：

假設(shè)有n個proposer，每個編號為ir(0<=ir<n)，proposol編號的任何值s都應(yīng)該大于他已知的最大值，并且滿足：s %n = ir => s = m*n + ir

proposer已知的最大值來自兩部分：proposer自己對編號自增后的值和接收到acceptor的reject后所得到的值

以3個proposer P1、P2、P3為例，開始m=0,編號分別為0，1，2

P1提交的時候發(fā)現(xiàn)了P2已經(jīng)提交，P2編號為1 > P1的0，因此P1重新計算編號：new P1 = 1*3+0 = 4
P3以編號2提交，發(fā)現(xiàn)小于P1的4，因此P3重新編號：new P3 = 1*3+2 = 5