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

我叫Leslie Lamport，我最屌。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1.?簡介

用于實現高容錯性分布式系統的Paxos算法，一直以來總是被認為是難以理解的，或許是因為對很多人來說，初始版本就像是”希臘語"一樣（最初的論文是以希臘故事展開的形式）[5]。實際上，它也算是最淺顯易見的分布式算法之一了。它的核心就是一個一致性算法——論文[5]中的“synod”算法。在下一個章節可以看到，它基本上是根據一個一致性算法所必需滿足的條件自然而然地推斷出來的。最后一個章節，我們通過將Paxos算法作為構建一個實現了狀態機的分布式系統的一致性實現，來完整地描述它。這種使用狀態機方法的論文[4]應該早已廣為人知，因為它可能已經是分布式系統理論研究領域被引用最廣泛的了。

?

2.?一致性算法

2.1 問題描述

假設有一組可以提出提案的進程集合。一個一致性算法需要保證：

• 在這些被提出的提案中，只有一個會被選定。

• 如果沒有提案被提出，則不會有被選定的提案。

• 當一個提案被選定后，進程應該能獲取被選定提案的信息。

?

對于一致來說，安全性（Safety）需求是這樣的：

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

• 只能有一個值被選中（chosen），同時

• 進程不能認為某個提案被選定，除非它真的是被選定的那個。

?

我們不會嘗試去精確地描述活性（Liveness）需求。但是從總體上看，最終的目標是保證有一個提案被選定，并且當提案被選定后，進程最終也能獲取到被選定提案的信息。

?

• 一個分布式算法，有兩個重要的屬性：Safety和Liveness，簡單來說：
  • Safety是指那些需要保證永遠都不會發生的事情
  • Liveness是指那些最終一定會發生的事情

?

在這個一致性算法中，有三個參與角色，我們分別用Proposer，Acceptor和Learner來表示。在具體實現中，一個進程可能充當不止一種角色，但是在這里我們并不關心它們之間的映射關系。

?

假設不同的參與者之間可以通過發消息來進行通信，我們使用普通的非拜占庭模式的異步模型：

• 每個參與者以任意的速度運行，可能會因停止而執行失敗，也可能會重啟。當一個提案被選定后，所有的參與者都有可能失敗然后重啟，除非這些參與者可以記錄某些信息，否則是不可能存在一個解法的。

• 消息在傳輸中可能花費任意時間，可能會重復，也可能丟失，但不會被損壞（不會被篡改，即不會發生拜占庭問題）。

?

2.2 提案的選定

選定提案最簡單的方式就是只有一個Acceptor存在。Proposer發送提案給Acceptor，Acceptor會選擇它接收到的第一個提案作為被選提案。雖然簡單，這個解決方案卻很難讓人滿意，因為當Acceptor出錯時，整個系統就無法工作了。

?

因此，我們應該選擇其他方式來選定提案，比如可以用多個Acceptor來避免一個Acceptor的單點問題。這樣的話，Proposer向一個Acceptor集合發送提案，某個Acceptor可能會通過（accept）這個提案。當有足夠多的Acceptor通過它時，我們就認為這個提案被選定了。那么怎樣才算是足夠多呢？為了確保只一個提案被選定，我們可以讓這個集合大到包含了Acceptor集合中的多數成員。因為任意兩個多數集（majority）至少包含一個公共成員，如果我們再規定一個Acceptor只能通過一個提案，那么就能保證只有一個提案被選定（這是很多論文都研究過的多數集的一個普通應用[3]）。

?

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

?? ?P1. 一個Acceptor必須通過它收到的第一個提案。

?

但是這個需求會引發另外的問題。如果有多個提案被不同的Proposer同時提出，這會導致雖然每個Acceptor都通過了一個提案，但是沒有一個提案是由多數人通過的。甚至即使只有兩個提案被提出，如果每個都被差不多一半的Acceptor通過了，哪怕只有一個Acceptor出錯都可能導致無法確定該選定哪個提案。

• 比如有5個Acceptor，其中2個通過了提案a，另外3個通過了提案b，此時如果通過提案b的3個當中有一個出錯了，那么a和b的通過數都為2, 這樣就無法確定了。

?

P1再加一個提案被選定需要由半數以上Acceptor通過的這個需求，暗示著一個Acceptor必須要能通過不止一個提案。我們為每個提案分配一個編號來記錄一個Acceptor通過的那些提案，于是一個提案就包含一個提案編號以及它的value值。為了避免造成混淆，需要保證不同的提案具有不同編號。如何實現這個功能依賴于具體的實現細節，在這里我們假設已經實現了這種保證。當一個具有value值的提案被多數Acceptor通過后，我們就認為該value被選定了。同時我們也認為該提案被選定了。

?

我們允許多個提案被選定，但是我們必須保證所有被選定的提案具有相同的值value。通過對提案編號的約定，它需要滿足以下保證：

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

?

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

?

一個提案能被選定，必須要被至少一個Acceptor通過，所以我們可以通過滿足如下條件來滿足P2:

? ? P2a. 如果一個具有value值v的提案被選定了，那么被Acceptor通過的所有編號比它高的提案的value值也必須是v。

?

我們仍然需要P1來保證有提案會被選定。因為通信是異步的，一個提案可能會在某個Acceptor c還沒收到任何提案時就被選定了。假設有個新的Proposer蘇醒了，然后提出了一個具有不同value值的更高編號的提案，根據P1, 需要c通過這個提案，但這是與P2a相矛盾的。因此為了同時滿足P1和P2a，需要對P2a進行強化：

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

?

一個提案被Acceptor通過之前肯定是由某個Proposer提出，因此P2b就隱含P2a，進而隱含了P2.

?

為了發現如何保證P2b，我們來看看如何證明它成立。我們假設某個具有編號m和value值v的提案被選定了，需要證明任意具有編號n（n > m）的提案都具有value值v。我們可以通過對n使用數學歸納法來簡化證明，這樣我們可以在額外的假設下——即編號在m..(n-1)之間的提案具有value值v，來證明編號為n的提案具有value值v，其中i..j表示從i到j的集合。因為編號為m的提案已經被選定了，這就意味著存在一個多數Acceptor組成的集合C，C中的每個成員都通過了這個提案。結合歸納的假設，m被選定意味著：

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

?

由于任何包含多數Acceptor的集合S都至少包含一個C中的成員，我們可以通過保持如下不變性來確保編號為n的提案具有value值v：

? ? P2c. 對于任意v和n，如果一個編號為n，value值為v的提案被提出，那么肯定存在一個由多數Acceptor組成的集合S滿足以下條件中的一個：

? ? ?? ?a. S中不存在任何Acceptor通過了編號小于n的提案

? ? ?? ?b. v是S中所有Acceptor已經通過的編號小于n的具有最大編號的提案的value值。

?

通過維護P2c的不變性我們就可以滿足P2b的條件了。

?

為了維護P2c的不變性，一個Proposer在提出編號為n的提案時，如果存在一個將要或者已經被多數Acceptor通過的編號小于n的最大編號提案，Proposer需要知道它的信息。獲取那些已經被通過的提案很簡單，但是預測未來會被通過的卻很困難。為了避免去預測未來，Proposer通過提出承諾不會有那樣的通過情況來控制它。換句話說，Proposer會請求那些Acceptor不要再通過任何編號小于n的提案了。這就導致了如下的提案生成算法：

Proposer選擇一個新的提案編號n，然后向某個Acceptor集合中的成員發送請示，要求它作出如下回應：

?? ?? ? （a）保證不再通過任何編號小于n的提案。

?? ?? ? （b）當前它已經通過的編號小于n的最大編號提案，如何存在的話。

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

如果Proposer收到來自集合中多數成員的響應結果，那么它可以提出編號為n，value值為v的提案，這里v是所有響應中最大編號提案的value值，如果響應中不包含任何提案，那么這個值就由Proposer自由決定。

?

Proposer通過向某個Acceptor集合發送需要被通過的提案請求來產生一個提案（這里的Acceptor集合不一定是響應前一個請求的集合）。這們把這個叫做accept請求。

?

目前我們描述了Proposer端的算法。那么Acceptor端是怎樣的呢？它可能會收到來自Proposer端的兩種請求：prepare請求和accept請求。Acceptor可以忽略任意請求而不用擔心破壞算法的安全性。因此我們只需要說明它在什么情況下可以對一個請求作出響應。它可以在任何時候響應prepare請求也可以在不違反現有承諾的情況下響應accept請求。換句話說：

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

?

可以看出P1a包含了P1。

?

現在我們就獲得了一個滿足安全性需求的提案選定算法——假設在提案編號唯一的前提下。只要再做點小優化，就能得到最終的算法了。

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

通過這個優化，Acceptor只需要記住它已經通過的提案的最大編號以及它已經響應過prepare請求的提案的最大編號。因為必須要在出錯的情況下也保證P2c的不變性，所以Acceptor要在故障和重啟的情況下也能記住這些信息。Proposer可以隨時丟棄提案以及它的所有信息——只要它可以保證不會提出具有相同編號的提案即可。

?

把Proposer和Acceptor的行為結合起來，我們就能得到算法的如下兩階段執行過程：

Phase 1:

• Proposer選擇一個提案編號n，然后向Acceptor的多數集發送編號為n的prepare請求。

• 如果一個Acceptor收到一個編號為n的prepare請示，且n大于它所有已響應請求的編號，那么它就會保證不會再通過任意編號小于n的提案，同時將它已經通過的最大編號提案（如果存在的話）一并作為響應。

Phase 2:

• 如果Proposer收到多數Acceptor對它prepare請求（編號為n）的響應，那么它就會發送一個編號為n，value值為v的提案的accept請求給每個Acceptor，這里v是收到的響應中最大編號提案的值，如果響應中不包含任何提案，那么它就可以是任意值。

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

?

一個Proposer可以提出多個提案，只要它能遵循以上算法約定。它可以在任意時刻丟棄某個提案（即使針對該提案的請求或響應在提案丟棄后很久才到達，正確性依然可以保證）。如果Proposer已經在嘗試提交更大編號的提案，那么丟棄也未嘗不是一件好事。因此，如果一個Acceptor因為已經收到更高編號的prepare請求而忽略某個prepare或者accept請求，它應該通知對應的Proposer，然后該Proposer可以丟棄這個提案。這是一個不影響正確性的性能優化。

?

2.3 獲取被選定的提案值

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

?

在假設非拜占庭錯誤的前提下，一個Learner可以很容易地通過另一個Learner了解一個值已經被選定了。我們可以讓所有Acceptor將它們的通過信息發送給一個特定的Learner，當一個value被選定時，由它來通知其他Learner。這種方法需要額外一個步驟才能通知到所有Learner，而且它也不是可靠的，因為那個特定的Learner可能會發生一些故障。但是這種情況下的通信次數，只需要二者數量之和。

?

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

?

因為消息可能會丟失，一個value被選定后，可能沒有Learner會發現。Learner可以向Acceptor詢問它們通過了哪些提案，但是任一Acceptor出錯，都有可能導致無法分辨是否有多數Acceptor通過了某個提案。在這種情況下，只有當一個新的提案被選定時，Learner才能發現被選定的value。如果一個Learner想知道是否已經選定一個value，它可以讓Proposer利用上面的算法提出一個提案。

?

2.4 進展性

很容易可以構造出這樣一種情況，兩個Proposer持續地提出序號遞增的提案，但是沒有提案會被選定。Proposer p為編號為n1的提案完成Phase 1, 然后另一個Proposer q為編號為n2(n2>n1)的提案完成Phase 1。Proposer p對于編號n1的Phase 2的accept請求會被忽略，因為Acceptor承諾不再通過任何編號小于n2的提案。這樣Proposer p就會用一個新的編號n3(n3>n2)重新開始并完成Phase 1，這又導致了Proposer q對于Phase 2的accept請求被忽略，如此往復。

?

為了保證進度，必須選擇一個特定的Proposer作為唯一的提案提出者。如果這個Proposer可以和多數Acceptor進行通信，并且可以使用比已用編號更大的編號來進行提案的話，那么它提出的提案就可以成功被通過。如果知道有某些編號更高的請求，它可以通過舍棄當前的提案并重新開始，這個Proposer最終一定會選到一個足夠大的提案編號。

?

如果系統中有足夠的組件（Proposer, Acceptor以及網絡通信）工作良好，通過選舉一個特定的Proposer，活性就能夠達到。著名的FLP理論[1]指出，一個可靠的Proposer選舉算法要么利用隨時性要么利用實時性來實現——比如使用超時機制。然而無論選舉是否成功，安全性都可以保證。

?

2.5 實現

Paxos算法[5]假設了一組進程網絡。在它的一致性算法中，每個進程都扮演著Proposer, Acceptor以及Learner的角色。該算法選擇了一個Leader來扮演那個特定的Proposer和Learner。Paxos一致性算法就是上面描述的那個，請求和響應都以普通消息的方式發送（響應消息通過對應的提案編號來標識以避免混淆）。使用可靠的存儲設備存儲Acceptor需要記住的信息來防止出錯。Acceptor在真正發送響應之前，會將它記錄到可靠的存儲設備中。

?

剩下的就是描述如果保證不會用到重復編號的機制了。不同的Proposer從不相交的編號集合中選擇自己的編號，這樣任何兩個Proposer就不會用到相同的編號了。每個Proposer都記錄（在可靠存儲設備中）它使用過的最大編號，然后用比這更大編號的提案開始Phase 1。

?

3.?狀態機實現

有一種實現分布式系統的簡單方式，就是使用一組客戶端集合向中央服務器發送命令。服務器可以看成一個以某種順序執行客戶端命令的確定性狀態機。這個狀態機有個當前狀態，通過接收一個命令當作輸入來產生一個輸出和新狀態。比如，分布式銀行系統的客戶端可能是一些出納員，狀態機的狀態則由所有用戶的賬戶余額組成。一個取款操作，通過執行一個減少賬戶余額的狀態機命令（當且僅當余額大于取款數目時）實現，然后將新舊余額作為輸出。

?

使用單點中央服務器的系統在該服務器故障的情況下，整個系統都將運行失敗。因此我們用一組服務器來代替它，每個服務器都獨立實現了該狀態機。因為這個狀態機是確定性的，如果所有服務器都以同樣的順序執行命令，那么它們將產生相同的狀態機狀態和輸出。一個提出命令的客戶端，可以使用任意服務器為它產生的輸出。

?

為了保證所有服務器都能執行相同的狀態機命令序列，我們需要實現一系列獨立的Paxos一致性算法實例，第i個實例選定的值作為序列中的第i個狀態機命令。在算法的每個實例中，每個服務器擔任所有角色（Proposer，Acceptor和Learner）。現在，我們假設服務器的集合是固定的，這樣所有的一致性算法實例都具有相同的參與者集合。

?

在正常執行中，一個服務器被選舉成為Leader，它會在所有一致性算法實例當中扮演特定的Proposer（唯一的提案提出者）。客戶端給Leader發送命令，它來決定每條命令出現在序列當中的位置。如果Leader決定某個客戶端命令應該是第135個，它會嘗試讓該命令成為第135個一致性算法實例選定的value值。這通常都會成功，但是在一些故障或者有另外的服務器也認為自己是Leader并且對第135個命令持有異議時，它可能會失敗。但是一致性算法可以保證，最多只有一條命令會被選定為第135條。

?

這個方法的關鍵在于，在Paxos一致性算法中，被提出的value值只在Phase 2才會被選定。回憶一下，在Proposer完成Phase 1時，要么提案的value值被確定了，要么Proposer可以自由提出任意值。

?

我們現在描述了Paxos狀態機實現是怎樣在正常情況下運行的，接下來我們看看會有哪些出錯的情況，看下之前的Leader故障以及新的Leader被選舉出來后會發生什么（系統啟動是一種特殊情況，此時還沒有命令被提出）。

?

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

?

Leader以及其他已經獲取Leader所有已知命令的服務器，現在可以執行命令1-135。然而它還不能執行命令138-140，因為命令136和137還未被選定。Leader可以將接下來兩條客戶端請求的命令當作命令136和137。同時我們也可以提出一個特殊的“noop”指令來立即填補這個空缺但保持狀態不變（通過執行一致性算法實例136和137的Phase 2來完成）。一旦該no-op指令被選定，命令138-140就可以被執行了。

?

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

?

Leader可以在它提出的命令141被選定前提出命令142。它發送的關于命令141的提案信息可能全部丟失，因此在所有其他服務器獲知Leader選定的命令141之前，命令142就可能已被選定。當Leader無法收到實例141的Phase 2的期望回應時，它會重傳這些信息。如果一切順利的話，它的提案命令將被選定。但是仍然可能會失敗，造成在選定的命令序列中出現缺口。一般來說，假設Leader可以提前確定a個命令，這意味著命令i被選定之后，它就可以提出i+1到i+a的命令了。這樣就可能形成長達a-1的命令缺口。

?

一個新選定的Leader需要為無數個一致性算法實例執行Phase 1——在上面的場景中，就是135-137以及所有大于139的執行實例。通過向其他服務器發送一條合適的消息，就可以讓所有執行實例使用同一個提案編號（計數器）。在Phase 1中，只要一個Acceptor已經收到來自某Proposer的Phase 2消息，那么它就可以為不止一個實例作出通過回應（在上面的場景中，就是針對135和140的情況）。因此一個服務器（作為Acceptor時）可以用一條適當的短消息對所有實例作出回應。執行這樣無限多的實例的Phase 1也不會有問題。

• 這里應該是指穩定的Paxos模型，Phase 1可以被省略，只要編號計數器是唯一的。

?

在系統正常運行的情況下，我們假設總是只有一個Leader，只有在當前Leader故障及選舉出新Leader之間的短時間內才會違背這個假設。在特殊情況下，Leader選舉可能失敗。如果沒有服務器扮演Leader，那么就沒有新命令被提出。如果同時有多個服務器認為自己是Leader，它們在一個一致性算法執行實例中可能提出不同value值，這可能導致沒有任何值能被選定。但是安全性是可以保證的——不可能有兩個不同的值被選定為第i條狀態機命令。單個Leader的選舉只是為了保證流程能往下進行。

?

如果服務器的集合是變化的，那么必須有某種方法可以決定哪些服務器來實現哪一些一致性算法實例。最簡單的方式就是通過狀態機本身來完成。當前的服務器集合可以是狀態的一部分，同時也可以通過狀態機命令來改變。通過用執行完第i條狀態機命令后的狀態來描述執行一致性算法i+a的服務器集合，我們就能讓Leader提前獲取a個狀態機命令。這就允許任意復雜的重配置算法有一個簡單實現。

?

?

參考文獻

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

?

轉載于:https://www.cnblogs.com/j-well/p/7056951.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Paxos Made Simple（译）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。