分布式理論(3)：Paxos Made Simple

鳳凰苑兇真 2017-02-13

展開全文

作者：LESLIE LAMPORT 2001 譯者：phylips@bmy 2011-4-30

出處：http://duanple.blog.163.com/blog/static/709717672011440267333/

[

序：在PODC2001會議上，我總是聽到人們在抱怨paxos算法是那么的難以理解。人們總是被那些古希臘的名稱弄得暈頭轉(zhuǎn)向，而使得他們覺得論文難以理解，實際上算法本身是很簡單的。于是在會議期間我就找了幾個人聚在一起，試著直接向他們口頭解釋該算法?；丶抑?，我將這些內(nèi)容整理了下來，后來又基于Fred Schneider 和 Butler Lampson的建議做了修改。就形成了現(xiàn)在的這個版本，雖然已經(jīng)有13頁長了，但是其中仍未包含任何一個比n1>n2更復雜的公式。{!本部分摘自Lamport的my writings，my writings是Lamport本人對自己以往發(fā)表的論文的一些總結(jié)，其中很多文字涉及到這些論文的創(chuàng)作來源?？梢钥闯鲈撜撐牡漠a(chǎn)生經(jīng)歷，與拜占庭將軍問題有著截然相反的歷程，在發(fā)表The Byzantine General Problem的時候，作者是用拜占庭將軍這一場景引入到原來的算法中，而Paxos則是作者最初就是用古希臘的故事情節(jié)來描述，我想當時作者之所以采用一個故事性的背景，也是因為拜占庭將軍這一寫作方法帶來的成功而受到的影響。只是事與愿違，人們覺得那篇The Part-Time Parliament太難理解了，而且通篇沒有數(shù)學化的公式證明。根據(jù)Lamport的說法，當時的三個審稿人認為這篇文章雖然重要性不夠但還有點意思，只是還應該把所有有關(guān)Paxos(Lamport在論文中虛構(gòu)出的一個島嶼的名稱)這一描述的地方全部刪掉，但是Lamport覺得這些人太沒幽默感了，也就沒有按照他們要求的去做。以至于作者雖然在1990年就將它提交給了TOCS，但直到1998年才被發(fā)表。但是發(fā)表之后，很多人還是覺得原來那篇太難理解了，于是才產(chǎn)生了這一篇。不過現(xiàn)在回頭再看，雖然當時Lamport的寫作方式令文章被埋沒了數(shù)年，但是也正因此才產(chǎn)生了如此有趣的一則軼聞，Paxos也成為該算法無可爭議的名稱，雖然另一篇文章<<Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems>>在1988年就獨立地提出了類paxos的一致性算法。}

]

Abstract

The Paxos algorithm,when presented in plain English, is very simple.

說明：

Proposer：意為提案者，它可以提出一個提案

Proposal：提案，由Proposer提出。一個提案由一個編號及value形成的對組成，編號是為了防止混淆保證提案的可區(qū)分性，value即代表了提案本身的內(nèi)容。

Acceptor：是提案的受理者，有權(quán)決定是否它本身是否接受該提案

Choose：提案被選定，在本文中當有半數(shù)以上Acceptor接受該提案時，就認為該提案被選定了，被選定的提案

Learner：需要知道被選定的提案信息的那些人

1. 導引

用于實現(xiàn)容錯的分布式系統(tǒng)的Paxos算法，一直以來總是被認為很難理解，或許是因為對很多人來說，并不習慣以希臘故事展開的論文形式。事實上，它應該是眾多分布式算法中最簡單易見的一個了。它的核心就是一個一致性算法—論文[5]中的“synod”算法。從下一個章節(jié)可以看出，它基本上就是根據(jù)一個一致性算法所必需滿足的條件而順理成章的呈現(xiàn)出來的。最后一個章節(jié)，我們還會通過將Paxos算法作為一個使用狀態(tài)機的分布式系統(tǒng)構(gòu)建模式中的一致性實現(xiàn)部分，來完整的描述它。這種使用狀態(tài)機的方法來構(gòu)建分布式系統(tǒng)最初是由論文[4]引入的，早已為人所熟知，而這篇論文估計也已經(jīng)是分布式系統(tǒng)理論研究領(lǐng)域被引用地最廣泛的了。

2. 一致性算法

2.1問題描述

假設(shè)有一組可以提出提案的進程集合。一個一致性算法需要保證：在這些被提出的提案中，只有一個會被選定；如果，沒有提案被提出，那么就不會有被選定的提案；當一個提案被選定后，進程應該可以獲取被選定的提案信息。

對于一致性來說，安全性(safety)需求就是這樣的：

只有被提出的提案才能被選定。

只能有一個值被選定(chosen)，同時

如果某個進程認為某個提案被選定了，那么這個提案必須是真的被選定的那個。

我們不會精確地描述活性(livness)需求。整體上來說，目標就是要保證最終有一個提案會被選定，當提案被選定后，進程最終也能獲取到被選定的提案。{!一個分布式算法，有兩個最重要的屬性：safety 和livness，簡單來說safety就是指那些需要保證永遠都不會發(fā)生的事情，livness是指那些最終一定會發(fā)生的事情}

在該一致性算法中，有三種參與角色，我們用proposers，acceptors和learners來表示。在具體的實現(xiàn)中，一個進程可能充當不止一種角色，在這里我們并不關(guān)心進程如何映射到各種角色。

假設(shè)不同參與者之間可以通過發(fā)送消息來通信，我們使用普通的非拜占庭模式的異步模型：

每個參與者以任意的速度執(zhí)行，可能會出錯而停止，也可能會重啟。當一個提案被選定后，所有的參與者都有可能失敗或重啟，因此除非那些失敗或重啟的參與者可以記錄某些信息，否則是不可能存在一個解的。

消息在傳輸中可能花費任意的時間，可能會重復，丟失，但是不會被損壞{!即其內(nèi)容不會被篡改，不會發(fā)生拜占庭式的問題}。

2.2提案的選定

選定提案的最簡單方式就是只允許一個accpetor存在。proposer發(fā)送提案給accpetor，acceptor會選擇它接收到的第一個提案作為被選定的提案。盡管簡單，但是這個解決方式卻很難讓人滿意，因為如果accpetor出錯，那么整個系統(tǒng)就無法工作了。

因此，應該選擇其他的方式。比如我們用多個accpetor來避免一個accpetor時的單點問題?，F(xiàn)在，proposer向一個acceptor集合發(fā)送提案，某個acceptor可能會通過(accept)這個提案。當有足夠多的acceptor通過(accept)它的時候，我們就可以認為這個提案被選定了。什么是足夠多呢？為了能確保只有一個提案被選定，我們可以讓這個集合大的可以包含acceptor集合中的多數(shù)成員。因為任何兩個多數(shù)集至少有一個公共成員，如果我們再規(guī)定一個acceptor最多只能通過一個提案，那么就能保證只有一個提案被選定(這是對于很多論文都研究過的majority的一個簡單的應用)。

在沒有失敗和消息丟失的情況下，如果我們希望即使在只有一個提案被提出的情況下，仍然可以選出一個提案來，這就暗示了如下這個需求：

P1：一個acceptor必須通過(accept)它收到的第一個提案。

但是這個需求引出了另外一個問題。如果有多個提案被不同的proposers同時提出，這可能會導致雖然每個acceptor都通過了一個提案，但是沒有一個提案是由多數(shù)人都通過的。即使是只有兩個提案，如果每個都被差不多一半的acceptors通過了，此時即使只有一個acceptor出錯都可能使得無法確定該選定哪個提案{!比如有5個acceptor，其中2個通過了提案a，另外3個通過了提案b，此時如果通過b的3個中有一個出錯了，那么a,b的通過者都變成了2個，這不清楚該如何決定了}。

P1再加上一個提案被選定需要由半數(shù)以上的acceptor通過的需求暗示著一個acceptor必須能夠通過(accept)不止一個提案。我們?yōu)槊總€提案設(shè)定一個編號來記錄一個acceptor通過的那些提案。為了避免混淆，需要保證不同的提案具有不同的編號。如何實現(xiàn)這種保證取決于實現(xiàn)，目前我們假設(shè)已經(jīng)提供了這種保證。當一個具有某value值的提案被半數(shù)以上的acceptor通過后，我們就認為該value被選定了。此時我們也認為該提案被選定了。{!此時的提案已經(jīng)跟value變成了不同的東西，提案是由編號+value組成的}

我們允許多個提案被選定，但是我們必須要保證所有被選定的提案都具有相同的value值。在提案編號上規(guī)約，它需要保證：

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

因為編號是全序的，條件P2就保證了只有一個value值被選定的這一關(guān)鍵安全性屬性。

被選定的提案，首先必須被至少一個acceptor通過，因此我們可以通過滿足如下條件來滿足P2：

P2a. 如果具有value值v的提案被選定(chosen)了，那么所有比它編號更高的被acceptor通過的提案的value值也必須是v

我們?nèi)匀恍枰狿1來保證提案會被選定。但是因為通信是異步的，一個提案可能會在某個acceptor c還未收到任何提案時就被選定了。假設(shè)一個新的proposer蘇醒了，然后產(chǎn)生了一個具有另一個value值的更高編號的提案，根據(jù)P1，就需要c通過這個提案，但是這與P2a矛盾。因此如果要同時滿足P1和P2a，需要對P2a進行強化：

P2b.如果具有value值v的提案被選定，那么所有比它編號更高的被proposer提出的提案的value值也必須是v

一個提案被acceptor通過之前肯定要由某個proposer提出，因此P2b就隱含了P2a，進而隱含了P2。

為了發(fā)現(xiàn)如何保證P2b，我們來看看如何證明它成立。我們假設(shè)某個具有編號m和value值v的提案被選定了，需要證明具有編號n(n>m)的提案都具有value值v。我們可以通過對n使用歸納法來簡化證明，這樣我們就可以在額外的假設(shè)下—即編號在m…(n-1)之間的提案具有value值v，來證明編號為n的提案具有value值v。因為編號為m的提案已經(jīng)被選定了，這意味著肯定存在一個由半數(shù)以上的acceptor組成的集合C，C中的每個acceptor都通過了這個提案。再結(jié)合歸納假設(shè)，m被選定意味著：

C中的每個acceptor都通過了一個編號在m…n-1之間的提案，每個編號在m…n-1之間的被acceptor通過的提案都具有value值v。

因為任何包含半數(shù)以上的acceptor的集合S都至少包含C中的一個成員，我們可以通過維護如下不變性就可以保證編號為n的提案具有value v：

P2c.對于任意的n和v，如果編號為n和value值為v的提案被提出，那么肯定存在一個由半數(shù)以上的acceptor組成的集合S，可以滿足條件a)或者b)中的一個：a)S中不存在任何的acceptor通過過編號小于n的提案

b)v是S中所有acceptor通過的編號小于n的具有最大編號的提案的value值。

通過維護P2c我們就可以保證P2b了。{!可以看到上面是對一系列條件的逐步加強，如果需要證明它們可以保證一致性，則需要反過來，P2c->P2b->P2a->P2 + p1 =>保證了一致性。

我們再看P2c，實際上P2c規(guī)定了每個Proposer 如何產(chǎn)生一個提案，對于產(chǎn)生的每個提案(n,v)需要滿足這個條件“存在一個由超過半數(shù)的Acceptor 組成的集合S：要么S中沒有人批準(accept)過編號小于 n 的任何提案，要么S的任何acceptor批準的所有議案（編號小于n）中，v是編號最大的議案的決議”。當Proposer遵守這個規(guī)則產(chǎn)生提案時，就可以保證滿足P2b。論文中，作者是從如何產(chǎn)生提案進而可以保證P2b來思考，才得到P2c的。下面我們反過來看，證明P2c可以保證P2b。如論文中一樣，采用數(shù)學歸納法證明。

首先假設(shè)提案(m,v)被選定了，設(shè)比該提案編號大的提案為(n,v’),我們需要證明的就是在P2c的前提下，對于所有的(n,v’)，有v’=v。

(1)n=m+1時，如果有這樣編號的提案，首先我們知道(m,v)被選定了，這樣就不可能存在一個S且S中沒有人批準過小于n的提案[S與批準(m,v)的Acceptor集合肯定有交集]，那v’只能是多數(shù)集S中編號小于n的最大編號的那個提案的值了，此時n=m+1，理論上小于n的最大的編號肯定是m，同時由于S和通過(m,v)的acceptor集合都是多數(shù)集，就保證了二者肯定有交集，這樣Proposer在確定v’取值時，肯定選到就是v。

上面實際上就是數(shù)學歸納法的第一步，確切的說是使用的是第二數(shù)學歸納法。上面是第一步，驗證了某個初始值成立。下面，需要假設(shè)編號在[m+1,k-1]區(qū)間內(nèi)成立，并在此基礎(chǔ)上推出n=k上也成立。

(2)根據(jù)假設(shè)編號在[m+1,k-1]區(qū)間內(nèi)的所有提案都具有值v，需要證明的是編號為k的提案也具有值v。根據(jù)P2c，首先同樣的不可能存在一個S且S中沒有人批準過小于n的提案，那么編號為k的value值，只能是一個多數(shù)集S中編號小于n的最大編號的那個提案的值，如果這個最大編號落在[m+1,k-1]區(qū)間內(nèi)的，那么值肯定是v，如果不是落在[m+1,k-1]區(qū)間，那么它的編號肯定就是m了，不可能比m再小了，因為S也肯定會與批準(m,v)的Acceptor集合肯定有交集，那么它的編號值就不會比m小，而編號如果是m那么它的值也是v。由此得證。

}

為了維護P2c的不變性，一個proposer在產(chǎn)生編號為n的提案時，必須要知道某一個將要或已經(jīng)被半數(shù)以上acceptor通過的編號小于n的最大編號的提案。獲取那些已經(jīng)被通過的提案很簡單，但是預測未來會被通過的那些卻很困難。在這里，為了避免讓proposer去預測未來，我們通過限定不會有那樣的通過情況來控制它。換句話說，proposer會請求acceptors不要再通過任何編號小于n的提案。這就導致了如下的提案生成算法：

1. proposer選擇一個新的提案編號n，然后向某個acceptors集合的成員發(fā)送請求，要求acceptor做出如下回應：

(a).保證不再通過任何編號小于n的提案

(b).當前它已經(jīng)通過的編號小于n的最大編號的提案，如果存在的話

我們把這樣的一個請求稱為編號為n的prepare請求。

2. 如果proposer收到了來自半數(shù)以上的acceptor的響應結(jié)果，那么它就可以產(chǎn)生編號為n，value值為v的提案，這里v是所有響應中編號最大的提案的value值，如果響應中不包含任何的提案那么這個值就可以由proposer任意選擇。

Proposer通過向某個acceptors集合發(fā)送需要被通過的提案請求來產(chǎn)生一個提案(此時的acceptors集合不一定是響應prepare階段請求的那個acceptors集合)。我們稱此請求為accept請求。

目前我們描述了proposer端的算法，acceptor端是怎樣的呢？它可能會收到來自proposer端的兩種請求：prepare請求和accept請求。Acceptor可以忽略任何請求而不用擔心破壞其算法的安全性。因此我們只需要說明它在什么情況下可以對一個請求做出響應。它可以在任何時候響應一個prepare請求，對于一個accept請求，只要在它未違反現(xiàn)有承諾的情況下才能響應一個accept請求(通過對應的提案)。換句話說：

P1a.一個acceptor可以接受一個編號為n的提案，只要它還未響應任何編號大于n的prepare請求。

可以看出P1a蘊含了P1。

我們現(xiàn)在就獲得一個滿足安全性需求的提案選定算法—假設(shè)編號唯一的情況下。再做一些小的優(yōu)化就得到了最終的算法。

假設(shè)一個acceptor收到了一個編號為n的prepare請求，但是它已經(jīng)對編號大于n的prepare請求做出了響應，因此它肯定不會再通過任何新的編號為n的提案，那么它就沒有必要對這個請求做出響應，因為它肯定不會通過編號為n的提案，因此我們會讓acceptor忽略這樣的prepare請求。我們也會讓它忽略那些它已經(jīng)通過的提案的prepare請求。

通過這個優(yōu)化，acceptor只需要記住它已經(jīng)通過的最大編號的提案以及它已經(jīng)做出prepare請求響應的最大編號的提案的編號。因為必須要保證P2c的不變性即使在出錯的情況下，acceptor必須記住這些信息即使是在出錯或者重啟的情況下。Proposer可以總是可以丟棄提案以及它所有的信息—只要它可以保證不會產(chǎn)生具有相同編號的提案即可。

將proposer和acceptor放在一塊，我們可以得到算法的如下兩階段執(zhí)行過程：

Phase1.(a) proposer選擇一個提案編號n，然后向acceptors的某個majority集合的成員發(fā)送編號為n的prepare請求。

(b).如果一個acceptor收到一個編號為n的prepare請求，且n大于它已經(jīng)響應的所有prepare請求的編號。那么它就會保證不會再通過(accept)任何編號小于n的提案，同時將它已經(jīng)通過的最大編號的提案(如果存在的話)作為響應{!?此處隱含了一個結(jié)論，最大編號的提案肯定是小于n的}。

Phase2.(a)如果proposer收到來自半數(shù)以上的acceptor對于它的prepare請求(編號為n)的響應，那么它就會發(fā)送一個針對編號為n，value值為v的提案的accept請求給acceptors，在這里v是收到的響應中編號最大的提案的值，如果響應中不包含提案，那么它就是任意值。

(b).如果acceptor收到一個針對編號n的提案的accept請求，只要它還未對編號大于n的prepare請求作出響應，它就可以通過這個提案。

一個proposer可能或產(chǎn)生多個提案，只要它是遵循如上的算法即可。它可以在任意時刻丟棄某個提案。(即使針對該提案的請求和響應在提案被丟棄很久后才到達，正確性依然可以保證)。如果某個proposer已經(jīng)在試圖生成編號更大的提案，那么丟棄未嘗不是一個好的選擇。因此如果一個acceptor因為已經(jīng)收到更大編號的prepare請求而忽略某個prepare或者accept請求時，那么它也應當通知它的proposer，然后該proposer應該丟棄該提案。當然，這只是一個不影響正確性的性能優(yōu)化。

2.3獲取被選定的提案值

為了獲取被選定的值，一個learner必須確定一個提案已經(jīng)被半數(shù)以上的acceptor通過。最明顯的算法是，讓每個acceptor，只要它通過了一個提案，就通知所有的learners，將它通過的提案告知它們。這可以讓learners盡快的找出被選定的值，但是它需要每個acceptor都要與每個learner通信—所需通信的次數(shù)等于二者個數(shù)的乘積。

在假定非拜占庭錯誤的情況下，一個learner可以很容易地通過另一個learner了解到一個值已經(jīng)被選定。我們可以讓所有的acceptor將它們的通過信息發(fā)送給一個特定的learner，當一個value被選定時，再由它通知其他的learners。這種方法，需要多一個步驟才能通知到所有的learners。而且也是不可靠的，因為那個特定的learner可能會失敗。但是這種情況下的通信次數(shù)，只是acceptors和learners的個數(shù)的和。

更一般的，acceptors可以將它們的通過信息發(fā)送給一個特定的learners集合，它們中的每個都可以在一個value被選定后通知所有的learners。這個集合中的learners個數(shù)越多，可靠性就越好，但是通信復雜度就越高。

由于消息的丟失，一個value被選定后，可能沒有l(wèi)earners會發(fā)現(xiàn)。Learner可以詢問acceptors它們通過了哪些提案，但是一個acceptor出錯，都有可能導致無法判斷出是否已經(jīng)有半數(shù)以上的acceptors通過的提案。在這種情況下，只有當一個新的提案被選定時，learners才能發(fā)現(xiàn)被選定的value。因此如果一個learner想知道是否已經(jīng)選定一個value，它可以讓proposer利用上面的算法產(chǎn)生一個提案。{!上面這段的意思是，acceptor發(fā)送給learners的關(guān)于提案通過的相關(guān)信息可能會丟失，這樣learns就無法知道是否有value被選定，此時呢它可以主動去詢問acceptors，但是此時如果被通過的提案剛好是由n/2+1個acceptor通過了，萬一其中一個acceptor出現(xiàn)問題，那么它無法確定被選定的提案，為了確定被選定的value，必須重新發(fā)起一次新的提案。}

{!但是這引出一種需要考慮的異常情況，當一個值被半數(shù)+1的acceptor選定后，但是其中一個acceptor出錯而死掉了，那么對于這種情況，paxos算法能否正確處理呢？因為這種情況下，某個learner可能會在這個acceptor還活著的時候獲知這個選定的value，但是其他learner獲取信息時該acceptor可能已經(jīng)死掉了。對于這種情況雖然learner可能一時無法判斷哪個value被選定了，但是它可以保證此時被選定的value，將一直是被選定的那個value，因為如果acceptor出錯死掉了，但這并不影響保證多數(shù)集之間肯定存在一個交，因為該出錯的acceptor對于兩個多數(shù)集來說，它們都是死掉的那個，根據(jù)算法執(zhí)行過程，我們可以看到多數(shù)集都是通過接受響應來體現(xiàn)的，也就是說它們肯定都是還活著的acceptor，這樣不同執(zhí)行過程中的phase2的多數(shù)集之間肯定存在一個還活著的公共acceptor。如果一個死掉的acceptor巧合是兩個(n/2+1)多數(shù)集唯一的公共元素，那么它應該是無法滿足收到多數(shù)集的acceptor的響應的。}

2.4進展性

很容易構(gòu)造出一種情況，在該情況下，兩個proposers持續(xù)地生成編號遞增的一系列提案，但是沒有提案會被選定。Proposer p為一個編號為n1的提案完成了phase1，然后另一個Proposer q為編號為n2(n2>n1)的提案完成了phase1。Proposer p的針對編號n1的提案的phase2的所有accept請求被忽略，因為acceptors已經(jīng)承諾不再通過任何編號小于n2的提案。這樣proposer p就會用一個新的編號n3(n3>n2)重新開始并完成phase1，這又會導致在phase2里proposer q的所有accept請求被忽略，如此循環(huán)往復。

為了保證進度，必須選擇一個特定的proposer來作為一個唯一的提案提出者。如果這個proposer可以同半數(shù)以上的acceptors通信，同時可以使用一個比現(xiàn)有的編號都大的編號的提案的話，那么它就可以成功的產(chǎn)生一個可以被通過的提案。再通過當它知道某些更高編號的請求時，舍棄當前的提案并重做，這個proposer最終一定會產(chǎn)生一個足夠大的提案編號。

如果系統(tǒng)中有足夠的組件(proposer，acceptors及通信網(wǎng)絡(luò))工作良好，通過選擇一個特定的proposer，活性就可以達到。著名的FLP結(jié)論指出，一個可靠的proposer選舉算法要么利用隨機性要么利用實時性來實現(xiàn)—比如使用超時機制。然而，無論選舉是否成功，安全性都可以保證。{!即即使同時有2個或以上的proposers存在，算法仍然可以保證正確性}

2.5實現(xiàn)

Paxos算法假設(shè)了一組進程網(wǎng)絡(luò)。在它的一致性算法中，每個進程扮演著proposer，acceptor及l(fā)earner的角色，該算法選定一個leader來扮演那個特定的proposer和learner。Paxos一致性算法就是上面描述的那個，請求和響應都是以普通消息的方式發(fā)送(響應消息通過對應的提案的編號來標識以防止混淆)。使用可靠性的存儲設(shè)備來存儲acceptor需要記住的信息來防止出錯。Acceptor在真正送出響應之前，會將它記錄在可靠性存儲設(shè)備中。

剩下的就是需要描述保證提案編號唯一性的機制了。不同的proposers會從不相交的編號集合中選擇自己的編號，這樣任何兩個proposers就不會有相同編號的提案了。每個proposer需要將它目前生成的最大編號的提案記錄在可靠性存儲設(shè)備中，然后用一個比已經(jīng)使用的所有編號都大的提案開始phase1。

3. 實現(xiàn)狀態(tài)機模型

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

使用中央服務(wù)器的系統(tǒng)在該服務(wù)器失敗的情況下，整個系統(tǒng)就失敗了。因此，我們使用一組服務(wù)器來代替它，每個服務(wù)器都獨立了實現(xiàn)了該狀態(tài)機。因為狀態(tài)機是確定性的，如果它們都按照相同的命令序列執(zhí)行，那么就會產(chǎn)生相同的狀態(tài)機狀態(tài)和輸出。一個產(chǎn)生命令的客戶端，就可以使用任意服務(wù)器為它產(chǎn)生的輸出。

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

在正常執(zhí)行中，一個服務(wù)器會被選為leader，它會在所有的一致性算法實例中被選作特定的proposer(唯一的提案提出者)?？蛻舳讼蛟搇eader發(fā)送命令，它來決定每個命令被安排在序列中的何處。如果leader決定某個客戶端命令應該是第135個命令，它會嘗試讓該命令成為第135個一致性算法實例選定的value值。通常，這都會成功，但是由于出錯或者另一個服務(wù)器也認為自己是leader，而它對第135個命令應該誰有異議。但是一致性算法可以保證，最多只有一個命令會被選定為第135個命令。

這種策略的關(guān)鍵在于，在Paxos一致性算法中，被提出的value只有在phase2才會被選定。回憶下，在proposer的phase1完成時，要么提案的value已確定，要么proposer可以自由地提出一個值。

現(xiàn)在我們已經(jīng)知道在正常運行時，Paxos狀態(tài)機實現(xiàn)是如何工作的。下面我們看下出錯的情況，看下之前的leader失敗以及新leader被選定后會發(fā)生什么。(系統(tǒng)啟動是一種特殊情況，此時還沒有命令被提出)。

新的leader選出來后，首先要成為所有一致性算法執(zhí)行實例的learner，需要知道目前已經(jīng)選定的大部分命令。假設(shè)它知道命令1-134,138及139—也就是一致性算法實例1-134,138及139選定的值(稍后，我們會看下命令間的缺口是如何形成的)。然后，它需要執(zhí)行135-137以及所有其他大于139的算法執(zhí)行實例的phase1(下面會描述如何來做，即如何為這無限多個實例執(zhí)行phase1)。假設(shè)執(zhí)行結(jié)果表明，將要在執(zhí)行實例135和140中被提出的提案值已經(jīng)確定，但是其他執(zhí)行實例的提案值是沒有限制的{!根據(jù)前面所述經(jīng)過phase1，要么提案value值已確定，要么proposer可以自由提出一個值，那么此處即指135和140的提案value已確定，而其他的則可選任意值，所以下面才能為136和137選一個新來的命令或者是那個特殊的noop命令}。那么現(xiàn)在該leader就可以執(zhí)行實例135和140的phase2，進而選定第135和140號命令。

Leader以及其他所有已經(jīng)獲取該leader的已知命令的服務(wù)器，現(xiàn)在可以執(zhí)行命令1-135。然而它還不能執(zhí)行138-140，因為目前為止命令136和137還未選定。Leader可以將下兩個到來的客戶端請求命令作為命令136和137。但是我們也可以提起一個特殊的“noop”命令作為136和137號命令來填補這個空缺，(通過執(zhí)行一致性算法實例136和137的phase2來完成){?!通過前面我們已經(jīng)知道換了新leader后，leader已經(jīng)執(zhí)行了它們的phase1，這樣就可以直接執(zhí)行phase2，同時phase1的執(zhí)行結(jié)果表明136和137的value值可以任意選擇。此處，noop命令不會改變狀態(tài)機狀態(tài)，實際上是個虛命令，使用它的意義在于因為命令139和140都確定好了，直接選擇一個noop就可以避免額外的命令查找或者等待，就可以盡快填補空缺，從而讓139和140盡快執(zhí)行，降低命令執(zhí)行的等待時間}。一旦該noop命令被選定，命令138-140就可以執(zhí)行了。

命令1-140目前已被選定了。Leader也已經(jīng)完成了所有大于140的一致性算法實例的phase1，而且在這些實例中，它可以自由的提出任何值。它將下一個客戶端的請求命令作為第141個命令，并且在階段2中將它作為一致性算法的第141個實例的value值。它會將下一個客戶端的請求命令作為命令142，如此…

Leader可以在它提出的命令141被選定前提出命令142。它發(fā)送的關(guān)于命令141的消息有可能全部丟失，因此在所有其他服務(wù)器在獲知leader選定了誰作為命令141之前，命令142就可能已被選定。當leader無法收到實例141的phase2的期望響應之后，它會重傳這些信息，但是仍然可能會失敗，這樣就在被選定的命令序列中，出現(xiàn)了缺口。假設(shè)一個leader可以提前確定a個命令，這意味著在i被選定之后，它就可以提出命令i+1到i+a的命令了。這樣就可能形成一個長達a-1的命令缺口。

一個新選擇的leader需要為無數(shù)個一致性算法實例執(zhí)行phase1—在上面的情景中，就是135-137以及所有大于139的執(zhí)行實例。只要向其他的服務(wù)器發(fā)送一個合適的消息內(nèi)容，就可以讓所有的執(zhí)行實例使用相同的提案編號。在phase1，只要一個acceptor已經(jīng)收到來自某個proposer的phase2消息，那么它就可以為不止一個的執(zhí)行實例做出承諾，因此一個服務(wù)器(作為acceptor角色時)通過選擇一個適當?shù)亩滔⒕涂梢詫λ袑嵗龀鲰憫?，那么?zhí)行這樣無限多個實例的phase1也就不會有問題。{?!因為執(zhí)行實例使用的都是相同的編號，這樣它承諾不再通過小于n的提案，應該可以應用在所有執(zhí)行實例上，而不影響正確性}。(在上面的場景中，就是針對135和140的情況)。

{!此處應該可以算是對于多個paxos執(zhí)行實例同時運行的情況的優(yōu)化，內(nèi)容類似于http://en./wiki/Paxos_(computer_science)#Multi-Paxos中提到的Multi-Paxos模式。根據(jù)wiki上的描述，如果leader是相對穩(wěn)定的，那么phase1可能就是不必要的了，那么對于同一個leader未來會參與的那些執(zhí)行實例，是可以直接跳過phase1的。但是，需要在每個value值中加上執(zhí)行實例的編號。

該模式執(zhí)行過程如下(圖中一個豎線應該認為是一個參與者，比如acceptor下有三個豎線，代表由三個acceptor)。從圖中可以看出，只有第一個執(zhí)行執(zhí)行了prepare過程，而在leader進入穩(wěn)定狀態(tài)后，后續(xù)的執(zhí)行實例直接進入了階段2，同時執(zhí)行實例的編號(即圖中的I)被加入到了消息中：

Message flow: Multi-Paxos, start

(first instance with new leader)

 Client   Proposer      Acceptor     Learner

   |         |          |  |  |       |  | --- First Request ---

   X-------->|          |  |  |       |  |  Request

   |         X--------->|->|->|       |  |  Prepare(N)

   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})

   |         X--------->|->|->|       |  |  Accept!(N,I,Vn)

   |         |<---------X--X--X------>|->|  Accepted(N,I,Vn)

   |<---------------------------------X--X  Response

   |         |          |  |  |       |  |

Message flow: Multi-Paxos, steady-state

(subsequent instances with same leader)

Client   Proposer      Acceptor     Learner

   |         |          |  |  |       |  |  --- Following Requests ---

   X-------->|          |  |  |       |  |  Request

   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)

   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)

   |<---------------------------------X--X  Response

   |         |          |  |  |       |  |

}

因為leader的失敗和新leader的選舉都是很少見的情況，因此執(zhí)行一個狀態(tài)機命令—即在命令值上達成一致性的花費就是執(zhí)行該一致性算法的phase2的花費{?那階段1呢}?？梢宰C明，在允許失效的情況下，在所有的一致性算法中， paxos一致性算法的階段2具有最小可能的【時間】復雜度[2]。因此paxos算法基本就是最優(yōu)的。

在該系統(tǒng)的正常執(zhí)行情況下，我們假設(shè)總是只有一個leader，只有在當前l(fā)eader失效及選舉新leader的較短時期內(nèi)才會違背這個假設(shè)。在特殊情況下，leader選舉可能失敗。如果沒有服務(wù)器擔任leader，那么就沒有新命令被提出。如果同時有多個服務(wù)器認為自己是leader，它們在一個一致性算法執(zhí)行實例中可能提出不同的value，這可能會導致無法選出一個value。但是，安全性一直都可以保證—即不可能會同時有兩個命令被選定為第i個狀態(tài)機命令。Leader的選舉只是為了保證progress。

如果服務(wù)器集合是變化的，那么必須有某種方式來決定哪些服務(wù)器來實現(xiàn)哪些一致性算法實例。最簡單的方式就是通過狀態(tài)機本身來完成。當前的服務(wù)器集合可以作為狀態(tài)的一部分，同時可以通過某些狀態(tài)機命令來改變。同時通過用執(zhí)行完第i個狀態(tài)機命令后的狀態(tài)來描述執(zhí)行一致性算法實例i+a的服務(wù)器集合，我們就能讓leader在執(zhí)行完第i個狀態(tài)機命令后可以提前獲取a個狀態(tài)機命令{!即在服務(wù)器集合可變的情況下，也能預取命令，就需要我們能知道確定該命令的一致性算法執(zhí)行實例對應的服務(wù)器集合，這里提供了一個簡單的服務(wù)器集合決定方式，也就是說我們既然將服務(wù)器集合作為狀態(tài)機狀態(tài)的一部分，那么我們就將在執(zhí)行完第i個狀態(tài)機命令后標識的服務(wù)器集合，作為一致性算法執(zhí)行實例i+a的服務(wù)器集合。比如我們把第0個狀態(tài)機命令執(zhí)行后的服務(wù)器集合，作為實現(xiàn)第i個的一致性算法實例的服務(wù)器集合，第1個狀態(tài)機命令執(zhí)行后的服務(wù)器集合，作為實現(xiàn)第i+1個的一致性算法實例的服務(wù)器集合，依次類推}。這就提供了一種支持任意復雜的重配置算法的簡單實現(xiàn)。{!實際上呢這就允許我們通過發(fā)送一個改變服務(wù)器集合的命令來動態(tài)的改變執(zhí)行第n個一致性算法的服務(wù)器集合，也就是實現(xiàn)了動態(tài)重配置的目的。因為該命令會改變直接服務(wù)器集合，那么就能影響到后續(xù)的執(zhí)行實例。}

譯考文獻：

http://en./wiki/Paxos_(computer_science)

http://www./document/613756

http:///distributed/paxos-scenarios/

http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html

http://rdc.taobao.com/blog/cs/?p=162

參考文獻：

[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,