Paxos Made Simple（粗略翻譯，略渣）

Paxos演算法，如果用平實的英語來說明，那是非常簡單的。

目錄

1 介紹

2 一致性演算法(The Consensus Algorithm)

• 2.1 問題
• 2.2 選擇一個值
• 2.3 學習一個選定的值
• 2.4 進度
• 2.5 實現

3 實現一個狀態機(State Machine)

參考

1. 介紹

用來實現一個容錯的分散式系統的Paxos 演算法已經被認為相當難於理解。一個可能的原因是原來的說明[5]對於許多讀者而言，太『希臘』(Greek)式了。事實上，Paxos演算法是一個簡單而又明了的分散式演算法，它的核心在於一個一致性的演算法- 也就是在[5]中提到的』教會(synod)』演算法。下面的第二章節會對這個這個一致性演算法的內容說明，並且一些我們希望其能滿足的屬性(properties)也會同時進行解釋。最後一章節將完整的說明Paxos演算法的實現。這個實現基於依賴於一致性的狀態機方法完成的程序，並且這個方法應該是大家廣泛了解的，因為這個方法的主題來源於網上一個廣泛被引用的分散式理論的論文。

2. 一致性演算法(The Consensus Algorithm)

2.1. 問題

假設有一組可以不斷提議值的進程。一個一致性演算法能夠保證這一系列的值中，只有一個將被選定。如果沒有值被提議，那麼就沒有值會被選擇。如果一個值已經被選定，那麼所有的進程已經可以學習(learn)到這個值。一致性需要以下的一些保險的需求：

1. 只有被提議的值會被選定

2. 只有一個值會被選定

3. 一個進程不會學習一個值（接受一個值被選定）直到這個值真的被選定

我們不會詳細的描述相關的需求。但所有的目標都是保證一些被提議的值將被最終選定，並且如果一個值被選定，那麼一個進程最終可以學習到這個值。

我們將一致性演算法中的三個角色定義成三種代理人(agent)：提議者(proposers)，接受者(aceptors)和學習者(learners)。在一個具體的實現中，單個進城可能扮演多個代理人，不過代理者和進程的對應關係不在我們的考慮範圍之內。

假設所有的代理人都可以通過發送消息的方式進行相互通信。我們使用自定義的非同步(asynchronous)，非拜占庭(non-Byzantine)模式，這意味著：

• 代理人執行速度是補丁的，可能因為停止而失敗，也可能發生重啟。既然所有的代理人可能在一個值被選定後發生異常並且重啟，一個成功解決方案必須依賴於每個代理人需要記錄和保存一些信息，確保它們即使在發生異常和重啟後也不會丟失。
• 所有的消息長度是不確定的，也可能發生重複，也可能丟失，但它們不會發生錯誤（也就是沒有拜占庭問題）

2.2. 選定一個值

最簡單的選定一個值的方法是只有單個的接受者代理人。一個提議者提交一個建議到這個接受者，而這個接受者選定其收到的第一個提議作為選定的值。儘管這樣的實現十分簡單，但是這樣的解決方案並不能滿足要求，因為單個的接受者一旦發生錯誤，那麼任何進一步的工作就無法繼續進行(單點失效)。

所以，讓我們嘗試另外一種選定值的方式。我們使用多個接受者，而且不是使用單個接受者。一個提議者發送一個提議值給一組接受者。一個接受者可能接受這個提議的值。這個值將會被選定如果足夠多接受者接受這個提議的值。問題是，足夠多是多少呢？為了確保一個值被選定，我們可以設定包含大多數(majority)的接受者的一組接受者。因為任何兩個佔大多數的接受者組必然至少包含著一個共同的接受者，只要這個共同的接受者最多選定一個值。(這個是一個明顯的關於」大多數」(majority)的推論，有許多論文已經對此進行了描述，比如[3])

不考慮發生錯誤和信息丟失的問題，我們希望一個值將被選定即使只有一個值被一個提議者提出。這引出了這樣一個需求：

P1. 一個接受者必須接受其收到的第一個提議

但是這樣的需求引發了一個問題。多個值可能在同一時間被不同的提議者提出，這將可能形成一種情況，多個接受者每個都接受了一個值，但是沒有一個共同的值被大多數的接受者所共同接受。即使只有兩個提議值，如果每一個都被一半的接受者所接受，單個節點的失效會使得確定那個值被選定變得不可能。

P1和一個選定的值需要被大多數接受者所接受的需求使得允許一個接受者接受多個提議。為了方便每個提議者追蹤所有接受的不同提議，我們給每個提議分配一個數字編號(自然數)，在這種情況下，每個提議都包含著一個提議編號(ID)和一個值。為了避免迷惑和衝突，我們需要每一個提議的數字編號必須不同。如何達成這樣的目標依賴於具體的實現，目前我們可以直接假設我們有辦法滿足這樣的要求。一個值被選定意味著包含這樣的值的一個提議被大多數的接受者所接受。在這種情況下，我們認為這個提議(包括其包含的值)被選定。

我們可以允許多個提議被選定，但是我們必須保證所有的這些被選定的提議包含相同的值。在提議編號需求滿足的情況下，這足夠去保證：

P2. 如果一個提議包含值v被選定了，那麼任何編號更加高，被選定的提議必須包含值v。

因為提議的編號是排序的(升序)，條件P2保證了至關重要的穩定性確保值v是被選定的。(或者說一旦選定了就確定選定了，不會發生改變)

如果想要被選定，那麼一個值必須至少被一個接受者所接受。所以我們可以通過滿足如下的需求來滿足P2：

P2a. 如果一個提議包含值v被選定了，那麼任何編號更加高的提議如果被任意接受者接受，那麼這個編號更加高的提議的值也是v。

我們依然保持P1用來保證至少有一些提議被選定。因為相互通訊是非同步的，一個提議可能在一些其他特定接受者們c收到任何提議的之前被選定。假定一個新的提議者」醒過來」(waks up)並且發送了一個新的有著更加高編號的提議但是包含一個不同的值。在這種情況下，P1要求c去接受這個提議，但這個P2a發生了衝突。為了同時保證P1和P2a，需要對P2a進行」加強」(strengthening)：

P2b. 如果一個包含值v的提議被選定了，那麼任何編號更加高的提議被任意提交者所提出時，必須保證其所包含的值也是v。

因為一個提議在其被一個接受者所接受之前，必然是由一個提議者所提出的，所以滿足P2b必然會滿足P2a，進而滿足P2。

為了探索如何滿足P2b，我們先考慮下如何做才能保證P2b能夠被滿足(也就是說在提交一個新提議時候應該如何做，或者接受一個提議時應該怎麼做)。我們應該在假設一些提議包含編號m和值v已經被選定的情況下，證明任意編號n>m的提議所包含的值也是v。一種比較簡單的證明方法便是在n上面使用歸納法。我們可以在並且附加任何被提出的編號m..(n-1)的提議的值也是v的條件下，證明編號為n的提議的值也是v，其中i..j意味著從編號從i到j的提議([i,j])。對於選定的提議m，必然存在一個包含了」大多數」(majority)接受者的集合C，並且集合C中所有的接受者都接受了提議m。結合上面所提到的額外歸納條件，關於提議m被選定的假說意味著：

每一個集合C中的接受者已經接受了m..(n-1)提議中的某一個並且每一個被接受的m..(n-1)中的提議都包含值v。

因為任何包含大多數接受者的集合S至少和C共有一個成員，所以我們可以推論出一個編號為n的提議包含值v只要如下的不變式(invariant)被維持：

P2c. 對於任意v和n，如果一個包含值v和編號n的提議被提出，那麼存在一個包含大多數接受者的集合S，其中要麼(a)S中不存在接受了編號<n的提議的接受者(沒有接受過任何的提議)，要麼(b)值v是其中編號<n的所有提議中，編號最大且被S中的某個接受者所接受的提議所包含的值。(通過遞歸可以得到，如果之前已經有提議被選定，那麼這個這個最大值的提議所包含的值必然是已經選定的值)

我們因此可以通過保持不變式P2c來滿足P2b。

為了保持不變式P2c，一個想要提出一個編號為n的提議的提議者，必須學習所有編號<n的提議中，如果存在的，已經被某個大多數(majority)中的所有接受者所接受或者將要被接受編號最大的那個提議。學習提議是件足夠簡單的事情；預測將來的接受是困難的。為了不依賴於預測將來的接受，提議者引申出一個保證(promise)，這個保證要求不會發生那樣的接受。換句話說，提議者要求接受者必須不再接受任何編號小於n的提議。在這種情況下，引申出如下的提議提出的演算法：

1 一個提議者選擇一個新的提議編號n並且向一個接收者集合中的每一個成員發送一個請求，要求它們回復如下信息：

(a) 一個保證(promise)滿足不再接受任何提議編號小於n的提議

(b) 已經被接受的提議中編號最高編號的那個，如果曾今接受過任何提議的話。

我們將這樣的請求定義為編號為n的準備(prepare)請求。

2 如果提議者從一個大多數的接受者集合收到了所請求的回復，那麼它隨後可以提交一個編號為n包含值v的請求。其中值v是這個大多數接受者集合中編號最大提議所包含的值，或者如果回復不包含任何已經被接受的請求(也就是目標的接受者集合任意成員都沒有接受過任意提議)，那麼提議者任意選取的值。

一個提議隨後被提議者發送到一系列的請求者，要求這些請求者接受這個同意。(這要求這一系列的接受者就是之前初始階段的那些。)讓我們稱之為接受(accept)請求。

以上描述了一個提交者演算法。那麼關於接受者呢？接受者可以接受兩類從提交者發來的請求：準備請求和接受請求。一個接受者可以無視任何請求並且不威脅到安全性。所以，我們只需要確定什麼時候可以接受一個請求。接受者可以總是回復一個準備請求。接受者也可以在並且只在與當前已有的保證(promise)不衝突的情況下，回復一個接受請求並且接受提議。換句話說：

P1a. 一個接受者可以接受一個編號n的提議，如果並且只有其沒有回復任何一個編號大於n的提議的準備(prepare)請求。

非常明顯的，P1a被歸納於P1之中。

現在我們有一套完整的演算法來在滿足安全性的情況下選定一個值的演算法，只要假定有一個生成唯一提議編號的辦法。最終的演算法還包含一個小的優化。

假定一個接受者收到一個編號為n的準備請求，但這個接受者已經接受了一個編號>n的準備請求，在這種情況下，接受者已經給出了一個保證(promising)不能在接受這個編號n的準備請求。因此，沒有任何理由接受者需要去回復這個準備請求，因為這個接受者不準備接受有提議者所提出的編號n的提議。所以我們規定接受者直接忽略這個準備請求，同時也忽略一個已經被接受過的準備請求。

引入這個優化後，一個接受者只需要記住其所接受的最大的提議編號和其所接受的最大的編號的準備請求。因為P2c必須在即使有失效和錯誤的情況下依然保證不變性，一個接受者必須記住所需要的信息即使其發生了錯誤並且重啟了。值得注意到的是，一個請求者可以放棄一個請求並且忘記它，只要它不會使用同樣的一個編號再次發送一個請求。

把這些提議者和接受者的行為集中起來，我們可以看到整個過程包含兩個階段(Phase) :

階段1 ：

1. 一個提議者挑選(得到)一個編號n並且發送一個編號為n的準備請求。

2. 一個接受者收到一個編號n的準備請求，並且如果這個編號n大於任何其已經回復過的準備請求的編號，那麼它將回復這個請求附帶一個保證(promise)，確保不接受如何編號小於n的提議，同時附帶上已經接受的最大的提議的信息，如果這樣的提議存在的話。

階段2 ：

1. 如果一個提議者從一個大多數的請求者那裡接收到準備請求(編號n)的回復，那麼它會發送一個接受請求到那些回復編號n的請求的接受者，附帶一個值v。這個值v就是所有回復中包含的已有編號最高的提議的值，或者如果回復中沒有包含任何提議，那麼提議者可以任意選擇一個值。

2. 如果一個接受者收到一個編號n的接受請求，那麼它將接受這個請求只要它沒有回復任何編號大於n的準備請求。

一個提議者可以提出多個提議，只要其對於每一個提議都遵循了上述的演算法。它也可以在任何時候棄置一個請求。(準確性將被保證，即使這個請求和/或者響應的回復可能在請求被棄置後很久才抵達它們的目的地。)一個可能是明智的棄置某個請求的時機是，如果發現了有提議者嘗試去提出編號更加高的提議。所以，如果一個接受者因為接收到了一個編號更加高的準備請求而忽略一些準備請求和接受請求時候，它也可以通知提議者，隨後提議者根據此，便可以選擇棄置當前請求。這是一個性能上的優化，並且不影響準確性。

2.3. 學習一個選定的值

為了學習一個被選定的值，一個學習者必須找出一個被某個大多數接受者所接受的提議。最明顯的演算法便是，當一個接受者接受一個提議時，向所有的學習者發送一個回復，包含被接受的提議。這允許學習者們能夠儘快的找到一個被選定的值，代價是要求所有的接受者要向所有的學習者發送回復，所發送的回複數目是接受者數量和學習者數量的乘積(O(mn))。

在沒有拜占庭失效(non-Byzantine failure)的假定下，一個學習者是相對容易去從另外一個學習者那裡學習到某個值被選定了。我們可以讓所有的接受者向一個特定的(distinguished)學習者發送接受信息，然後這個學習者將接著通知其餘學習者某個值被選定了。這使得所有的學習者需要額外的時間(round)去發現某個選定製。然而這是不太可靠地，因為那個特定的學習者可能發現錯誤。不過好處是，需要發送回復的數量，僅僅取決於接受者的數量。

更加普遍的而言，接受者們發送他們的接受信息給一組特定的學習者(而不是單個學習者)，隨後在某個值被選定時候，這些學習者們可以向所有的學習者傳遞這個信息。使用一大組的特定學習者提供了更加高的可靠性，但是會增加交流的複雜性。

因為消息可能丟失，一個值可能在沒有任何學習者發現的情況下被選定。學習者可以向接受者們詢問他們接受了哪些請求，但是失效(錯誤丟失等)可能使得得知是否有一個大多數接受了一個特定的提議。在這種情況下，學習者們將在新的值被選定的時候得知一個值被選定。如果一個學習者需要知道某個值是不是被選定，它可以讓一個提議者提出一個提議，並使用上面提到的演算法。

2.4. 進度

非常簡單的可以構造出一個場景，在這樣的場景中，兩個提交者不停地提出一序列的提議，但是這些提議沒有一個會被選中。提交者p使用編號n1的提議完成階段1。另外一個提交者使用編號n2 > n1的提議完成階段1。提交者p在階段2時候所提交的接受請求被接受者所忽略，因為接受者給出了一個不再接受<n2編號的請求的保證。在這種情況下，提議者p接著使用編號n3 > n2重新開始並且完成階段1，這使得提交者q的階段2(的請求)，也將被接受者失敗。諸如此類。

為了保證向前進展，必須選定一個特別的(distinguished)提議者，只有這個特別的提議者可以提出提議。如果這個特別的提議者和某個大多數接受者成功的進行通訊，並且如果其使用一個編號大於目前所有曾使用過的編號的提議，那麼這個編號的提議可以成功的被提出並且被接受。即使有更加高的提議存在，這個特別的提議者依然可以通過不斷的放棄提議和重試，從而最終選擇一個足夠高的提議編號。

如果整個系統(包括提議者，接受者和通訊網路)運行的足夠正常，系統可以選取一個單獨的提議者來完整工作。Fishcher，Lynch和Paterson得出的著名的結論[1]就是，一個可靠的選舉提議者的演算法，必須是隨機的或者實時的，比如，使用超時(timeouts)。然而，這個安全性不考慮選舉的成功和失敗所帶來的影響。

2.5. 實現

Paxos演算法假定了一個進程網路。在其一致性演算法中，每一個進程都扮演著提議者，接受者和學習者的角色。這個演算法選定一個領導者(leader)，其扮演了特定的提議者和特定的學習者的的角色。上述所提到的 Paxos一致性演算法恰是的一個演算法，一個請求和回復都是普通的消息信息。(回複信息標記上了對應的提議編號作為區別)。穩定可靠的存儲，在失效發生的時候保存信息，被用來保存那些接受者必須要記住的信息。一個接受者記錄先將所需要記錄的信息放置到穩定可靠的存儲之上，隨後才真正的發送回復。

剩下的部分著重在了描述如何保證任意兩個提議都不會使用相同的編號的機制之上。不同的提議者從互相沒有交集的編號組裡面選擇他們的編號，所以任何兩個不同的提議者必然不會提出相同的提議編號。任何一個提議者記錄(在穩定可靠的存儲中)記錄它曾嘗試發送的最大編號的提議，隨後使用一個比起任何用過的提議編號更大的提議編號進入階段1。

3. 實現一個狀態機(State Machine)

一個簡單的實現分散式系統的方式是一系列的客戶端向一個中心伺服器發送命令。這個伺服器可以被描述成一個有限狀態自動機(deterministic state machine)，這個狀態機按照一定順序執行客戶端命令。這個狀態機包含一個當前狀態；其執行的一步代表著：接受一個命令，輸出結果並且進入一個新的狀態。舉個例子，一個分散式銀行業務的客戶端可以是一個出納員，然後那個狀態機可能包含所有客戶的賬號餘額信息。一次提款將被對應到一個狀態機命令，這個命令將減少一個賬戶的餘額，如果餘額大於所需要提取的款額，隨後列印原有的餘額和新的餘額信息。

一個使用單個中心伺服器的實現發生失效如果那個中心伺服器失效的話。我們因此使用一組伺服器來代替一個中心伺服器的策略，這些伺服器每一個都是獨立的狀態機的實現。因為狀態機是有限的(deterministic)，所有的伺服器接受相同的命令序列將生成相同順序的狀態和輸出信息。一個客戶端因此可以向任何一台伺服器發送命令並且接受所生產的輸出。

為了保證所有的伺服器執行同樣的命令序列，我們實現一系列的單獨的Paxos一致性演算法的實例，第i個實例所選定的值是序列中第i個狀態機命令。每一個伺服器每一個的演算法實例中扮演所有的角色(提議者，接受者和學習者)。從現在開始，我假設一組伺服器已經被固定(已經排好順序)，所以所有的一致性演算法的實例使用同樣一組代理人(agents)。

對於普通操作，可以選擇單個伺服器作為領導者，在所有一致性演算法實例中扮演特定提交者的角色(唯一會嘗試去提交提議的角色)。客戶端發送命令到領導者那裡，後者決定命令出現的順序。如果領導者決定某個客戶端命令的順序是第135個，那麼它將嘗試將第135個一致性演算法的實例選定的值定為這個命令。在大多數情況下，這個過程會成功。但這可能會失敗因為發生錯誤，也可能其他的伺服器也認為自己是領導者並且對於第135個命令究竟是哪個有不同的分歧。但是上面提到的一致性演算法能夠保證只有一個命令會被選擇成第135個命令。

這個方法的效率的關鍵在於，在Paxos一致性演算法中，一個值只有到了階段2才會被最終選定。回憶一下，在完成一致性演算法的階段1以後，要麼那個值已經被確定，要麼提議者已經可以去提議另外一個值。

我們現在將描述Paxos狀態機的實現在普通的操作中是如何工作的。稍後我們將討論其會如何發生錯誤。我們考慮如果之前的一個領導者(leader)發生了錯誤，一個新的領導者被選定。(系統啟動是一個特定的情況，在這種情況下還沒有任何命令被提議。)

新的領導者，在所有的一致性演算法實例中扮演一個學習者必，應該知道所有的已經被選定的命令。假設它已經知道命令1-134，138和139，也就是在一致性演算法實例1-134，138和139中被選定的命令。(我們稍微將了解到為什麼這些命令間的空隙是如何產生的。) 新的領導者隨後為實例135-137以及所有執行階段1。(我們在下面描述這是怎麼完成的)。假設這些執行的結果決定了實例135和140的被提議的值，但是剩下所有的實例沒有被確定。領導者隨後為實例135和140執行階段2，隨後選定命令135和140.

領導者以及其他學習了領導者所知道到命令(已經被選定的)的伺服器，現在可以執行命令1-135。然而，命令138-140不能被執行，和大家了解的一樣，因為命令136和137還沒有被選定。領導者隨後可以將客戶端發來的請求定義為命令136和137.但是作為替代，我們立即提交連個特殊的」no-op」命令作為命令136和137來填充空隙，這些特殊的命令將維持狀態不變。(通過執行一致性演算法實例136和137的階段2來實現。)一旦這些no-op命令被選定，命令138-140就可以被執行了。

命令1-140現在已經被選定。領導者同樣為所有大於140的實例完成了階段1，其現在可以為任何實例的階段2提議值。領導者分配命令編號141給下一個客戶端送發送來的請求，提議這個值(這個命令)作為一致性演算法實例141階段2的值。領導者提議下一個接收到的客戶端命令作為命令142，如此往複。

領導者可以在命令141命令被選定之前提議命令142。所有為了提議命令141的而發送的消息可能丟失，並且命令142可能在任何其他伺服器學習到領導者提議了命令141之前就被選定了。當領導者沒有成功的接收到預想中的實例141的回複信息時，它將重新發送這些消息。如果一切正常，它提議的命令會被選定。然而，這樣的過程可能先發生失敗，在選定命令序列中留下一個空隙。一般而言，假設一個領導者可以前置a個命令， 也就是說，它可以一次性提議 i+1至i + a命令，只要1至i命令已經被選定。 在這種情況下，一個大小為a-1的空隙就可能產生。

一個新選定的領導者執行會為無限個實例執行階段1，在上面描述的情境中，領導者為實例135-137以及所有大於139的實例，都執行了階段1。通過發送一個簡單的消息給所有其他的伺服器，可以對每一個實例都使用同樣的提議號。在階段1，一個接受者只有在其已經從某個提議者那裡接受了一個階段2的消息以後才會發送複雜的消息而不是一個簡單的OK。(在上述的場景中，這隻會對135和140實例發生)。因此，一個伺服器(扮演一個接受者的角色)可以針對所有的實例返回單個有意義的短消息。執行這些無限多的實例的階段1因此不會引發問題。

因為領導者失效並且重選相對而言是一個非常少會發生的事情，因此因此執行狀態機名利的執行效率的成本主要來自於對執行命令/值達到一致性，也就是只執行一致性函數階段2的代價(階段1會多個一起提出並執行)。可以看到Paxos一致性演算法的階段2是所有能夠容錯的演算法中，成本最低的一個[2]。因此，Paxos演算法是本質性的優化。

上述對於普通系統執行命令的討論，假設了系統中總是存在單個領導者，並且發生錯誤後重新選擇領導到這間隔是很小的。在異常的環境中，領導者選舉本身就可能發生錯誤。如果沒有一個伺服器扮演一個領導者的角色，那麼就不會有新的命令會被提出。如果多個伺服器認為自己都是領導者，那麼他們會對相同的一致性演算法的實例提議值，這將使得沒有任何值會被選定。然而，保證性可以確保，兩個不同的伺服器不會對第i個狀態機命令被選定為某個值發生不和。選舉單個領導者只是為了保證能夠向前進行。

如果伺服器的集合會發生改變，那麼哪裡必須有一些方法可以用來判斷那些伺服器實現了那些一致性函數的實例。最簡單的方法便是通過狀態機本身。當前伺服器集合的情況可以作為狀態的信息的一部分，可以通過普通的狀態機命令進行改變。我們可以允許一個領導者獲得a個命令前置，通過要求那些執行i+a一致性演算法實例的伺服器集合也作為命令i的狀態的一部分。這描述了一個對於任意複雜的可配置的演算法的簡單實現。

參考

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

推薦閱讀：