分散式一致性演算法：Paxos——近乎原汁原味的論文分析

超長文預警。
這是在校做作業時，閱讀的《Paxos Made Simple》原文的筆記作業。較之原文，將最終的演算法結果介紹，放在了文章更加靠前的位置。推薦瀏覽順序：2.1 - 2.2 演算法闡述5 演算法實例

4 演算法效果分析
6 分散式一致性演算法拓展其他部分演算法相關概念及推導過程參考譯文：

【譯】Paxos Made Simple?

dsdoc.net

1. 概述

1.1 問題背景

分散式系統是一組電腦( )，通過網路相互鏈接傳遞消息與通信後並協調它們的行為而形成的系統。組件之間彼此進行交互以實現一個共同的目標。把需要進行大量計算的工程數據分區成小塊，由多臺計算機分別計算，再上傳運算結果後，將結果統一合併得出數據結論的科學。分散式系統的例子來自有所不同的面向服務的架構，大型多人在線遊戲，對等網路應用。

分散式系統中的節點通信存在兩種模型：共享內存( )和消息傳遞( )。基於消息傳遞通信模型的分散式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複。

對於這個問題，萊斯利·蘭伯特(英語： )於1990年提出了一種基於消息傳遞且具有高度容錯特性的一致性演算法，Paxos演算法。

1.2 概念摘要

1.2.1 一致性

在分散式系統中，一致性($Consistency$，早期也叫$Agreement$)是指對於系統中的多個服務節點，給定一系列操作，在協議（往往通過某種共識演算法）保障下，試圖使得它們對處理結果達成某種程度的一致。

一致性的定義：

Termination 可結束: 所有進程最終會在有限步數中結束並選取一個值, 演算法不會無盡執行下去。
Agreement 同共識: 所有進程必須同意同一個值。
Validity 值合法: 最終達成一致的值必須是到其中一個, 如果所有初始值都是 , 那麼最終結果也必須是 。
Integrity 完備性: 如果一個正確的進程決定採納作為最終值，那麼這個必須是由一個正確進程提議的。

1.2.2 分散式中的網路模型

同步網路( )

指滿足以下條件的網路：

所有節點的時鐘漂移有上限
網路的傳輸時間有上限
所有節點的計算速度一樣

這意味著整個網路按照round運行，每個round中任何節點都要執行完本地計算並且可以完成一個任意大小消息的傳輸。

對於傳輸：一個發出的消息如果在一個round內沒有到達，那麼一定是網路中斷造成的,，這個消息會丟失，不會延遲到第二個round到達。

在這種模型下可以解決一些問題，比如拜占庭式故障。

非同步網路( )

指滿足以下條件的網路：

節點的時鐘漂移無上限
消息的傳輸延遲無上限
節點計算的速度不可預料

在非同步網路中，有些故障非常難解決，比如當你發給一個節點一個消息之後幾秒鐘都沒有收到他的應答，有可能這個節點計算非常慢，但是也可能是節點crash或者網路延遲造成的, 你很難判斷到底是發生了什麼樣的故障。

1.2.3 節點宕機

節點宕機($fail-stop$): 節點持續宕機，不會恢復。

1.2.4 節點宕機恢復

節點宕機恢復($fail-recover$): 節點宕機一段時間後恢復。

1.2.5 網路分化

網路分化($network partition$): 網路鏈路出現問題，將N個節點隔離成多個部分。

1.2.6 拜占庭將軍問題

拜占庭將軍問題($byantine failure$): 在分散式計算中，不同的計算機通過通訊交換信息達成共識而按照同一套協作策略行動。但有時候，系統中的成員計算機可能出錯而發送錯誤的信息，用於傳遞信息的通訊網路也可能導致信息損壞，使得網路中不同的成員關於全體協作的策略得出不同結論，從而破壞系統一致性。

2. 一致性演算法

2.1 問題提出

假設有一組可以提出提案的進程集合。尋找一個演算法使得最終有一個提案會被選定，當提案被選定後，進程最終也能獲取到被選定的提案。

這個 一致性演算法 需要保證：

唯一值：在這些被提出的提案中，只有一個會被選定
值正確：如果，沒有提案被提出，那麼就不會有被選定的提案
可行性：當一個提案被選定後，進程應該可以獲取被選定的提案信息。

2.2 問題分析

2.2.1 問題重述

為了便於理解，我們將提出一個等價的問題，即：

有一組程序進程，進程內各自維護一個變數( )，目標是，提出一種演算法，使得：

最終只產生一個確定的值( )
當這個值( )被確定後，所有進程最終會將( )設置為值( )。

2.2.2 解決演算法

對於這個問題，萊斯利·蘭伯特 提出了Paxos演算法。演算法描述如下：

角色

在該一致性演算法中，有三種參與角色，我們用 Proposers ， Acceptors 和 Learners 來表示。一個進程可能充當不止一種角色。

演算法執行步驟

Phase 1

Proposers 的prepare請求：

Proposer 選擇一個提案[^1]編號 [^2]，然後向Acceptors的某個 [^3]集合的成員發送編號為的prepare請求。

Acceptors 的響應：

當一個Acceptor收到一個編號為的prepare請求，如果大於它已經響應的所有prepare請求的編號，那麼

它就會保證不會再通過任何編號小於的提案
同時將它已經通過的最大編號的提案(如果存在的話，即一個對)作為響應。[^4]

響應動作做的最重要的兩件事是

提出一個不會通過任何編號小於的提案。
給發來prepare請求的Proposers 一個反饋，使演算法進入Phase 2

Phase 2

Proposers 的accept請求：

如果Proposer收到來自半數以上的Acceptor對於它的prepare請求(編號為 )的響應，那麼它就會發送一個編號為，值為的提案的accept請求給Acceptors。

對於$value$值為的確定，遵循：

是收到的響應中編號最大的提案的值。
如果響應中不包含提案[^5]，那麼它就是由Proposer指定的任意值。

Acceptors 的通過：

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

Phase 3

每個Acceptor，只要它通過了一個提案，就通知所有的Learners，將它通過的提案告知它們。最終由Learners決定哪個值為最終一致的值。

至此，完整的**Paxos演算法**已經介紹完畢

2.3 演算法分析

下面講述演算法是如何推導出來的，以及演算法的證明。

2.3.1 相關概念

根據[問題提出](#2.1 問題提出)，對於一致性來說，**安全性**($Safety$)需求就是這樣的：

只有被提出的提案才能被選定。
只能有一個值被選定($chosen$)。
如果某個進程認為某個提案被選定了，那麼這個提案必須是真的被選定的那個。

我們不會精確地描述**活性($Liveness$)**[^6]需求。整體上來說，目標就是：

要保證最終有一個提案會被選定
當提案被選定後，進程最終也能獲取到被選定的提案。

什麼是活性，什麼是安全性呢？
活性和安全性都是對系統正確性的能力的描述。安全性($Safety$)指的是，你所構建的這個系統，應當能保證壞的事情不發生。比如，如果車鑰匙扭到點火的位置，車子必須啟動；.exe程序打開，就一定要能夠運行；鐘錶能夠滴答。等等活性($Liveness$)指的是，你所構建的這個系統，應當能保證好的事情會發生。紅燈最終會變綠。如果車鑰匙扭到點火的位置，車子最終將會啟動。程序最終將會終止。鐘錶會無限滴答。等等根據FLP定律，非同步通信的場景下，沒有一個演算法可以同時做到絕對的活性和安全性。

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

每個參與者以任意的速度執行，可能會出錯而停止，也可能會重啟。當一個提案被選定後，所有的參與者都有可能失敗或重啟，因此除非那些失敗或重啟的參與者可以記錄某些信息，否則是不可能存在一個解的。
消息在傳輸中可能花費任意的時間，可能會重複，丟失，但是不會被損壞。[^8]

這裡遵循容錯理論在分散式系統開發的應用，即：

我們通過構建失效停止計算機來規避實際生產中，可能出現的拜占庭錯誤所帶來的不可預知的錯誤，以提高分散式系統的容錯性。

2.3.2 提案的選定

2.3.2 論述瞭如何選定一個提案，來達到想要得出的這個演算法的唯一值的特性。

2.3.2.1 最簡單的提案方法

只允許一個Accpetor存在。Proposer發送提案給Accpetor，Acceptor會選擇它接收到的第一個提案作為被選定的提案。

缺點：如果Accpetor出錯，那麼整個系統就無法工作了。即存在單點故障。

2.3.2.2 多Accpetor提案方法

現在，Proposer向一個Acceptor集合發送提案，某個Acceptor可能會通過這個提案。當有足夠多的Acceptor 通過它的時候，我們就可以認為這個提案被選定了。

什麼是足夠多呢？
為了能確保只有一個提案被選定，我們可以讓這個集合大的可以包含Acceptor集合中的多數成員。因為任何兩個多數集至少有一個公共成員，如果我們再規定一個Acceptor最多隻能通過一個提案，那麼就能保證只有一個提案被選定(這是對於很多論文都研究過的majority的一個簡單的應用 [^9] )

在沒有失敗和消息丟失的情況下，如果我們希望即使在只有一個提案被提出的情況下，仍然可以選出一個提案來（即要滿足活性之一），就一定會滿足需求：

我們自然可以聯想到，如果有5個Acceptor，其中2個通過了提案 a ，另外3個通過了提案 b ，此時如果通過 b 的3個中有一個出錯了，那麼 a 、 b 的通過者都變成了2個，這不清楚該如何決定了。

這自然不是我們要的。那麼在 a 、 b 的通過者都變成了2個，這不清楚該如何決定時，我們還需要繼續提出提案，讓Acceptors接受，這就說明，一個Acceptor必須能夠通過不止一個提案。所以我們需要為每個提案設定一個唯一的編號來記錄一個Acceptor通過的那些提案。

當一個具有某$value$值的提案被半數以上的Acceptor通過後，我們就認為該$value$被選定了。此時我們也認為該提案[^10]被選定了。

既然我們允許多個提案被選定，那麼我們必須要保證所有被選定的提案都具有相同的$value$值。在提案編號上規約，它需要保證：

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

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

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

$P2^a. 如果具有value值 v 的提案被選定(chosen)了，\ 那麼所有比它編號更高的被Acceptor通過的提案的value值也必須是 v 。$

比如有Acceptor A1，經過一些步驟後，選定了< id = 3, value = 100 >的提案，那麼由上論述，仍然有情況，使A1需要繼續通過id更高（因為提案生成的更晚，雖然提案審核的順序和天生成的順序沒有直接關聯）的提案。
所以對於A1後來通過的，那些id更高的提案，它們的value必須等於100，才滿足安全性之二的要求。所以纔有了$P2^a$的需求。

我們仍然需要$ P1$ 來保證提案會被選定(滿足活性)。

但是因為通信是非同步的，一個提案可能會在某個Acceptor c 還未收到任何提案時就被選定了，我們可以假設提案為 < id = 1, value = a> *) 。這時一個新的Proposer產生了一個具有另一個$value$值的更高編號的提案，我們假設為< id = 4, value = b> *。

根據 $ P1$ ，就需要Acceptor c 通過這個提案（*< id = 4, value = b> *），但是這與 $P2^a$ 矛盾（value 應該為被選中的提案 a）。因此如果要同時滿足 $ P1$ 和$P2^a$，需要對 $P2^a$進行強化：

$P2^b. 如果具有value值v的提案被選定，\ 那麼所有比它編號更高的被Proposer提出的提案的value值也必須是 v 。$

一個提案被Acceptor通過之前肯定要由某個Proposer提出，因此 $P2^b$ 就隱含了 $P2^a$ ，進而隱含了 $P2$ 。
為了發現如何保證 P2b ，我們來看看如何證明它成立。

我們假設某個具有< id = m, value = v >的提案被選定了，需要證明:

具有編號 $n(n > m)$ 的提案都具有$value$值 $v$ 。

我們可以通過對 n 使用歸納法來簡化證明，這樣我們就可以在額外的假設下——
即編號在 m..(n-1) 之間的提案具有value值 v ，來證明編號為n的提案具有value值 v 。因為編號為m的提案已經被選定了，這意味著肯定存在一個由半數以上的Acceptor組成的集合 C， C 中的每個Acceptor都通過了這個提案。再結合歸納假設， m 被選定意味著：C 中的每個Acceptor都通過了一個編號在 m..n-1 之間的提案，每個編號在 m..(n-1) 之間的被Acceptor通過的提案都具有value值 v。因為任何包含半數以上的Acceptor的集合S都至少包含 C 中的一個成員，我們可以通過維護如下不變性就可以保證編號為n的提案具有value v：

$P2^c. 對於任意的 n 和 v ，如果編號為 n 和value值為 v 的提案被提出，\ 那麼肯定存在一個由半數以上的Acceptor組成的集合 S ，可以滿足條件 a) 或者 b) 中的一個： \ a) S 中不存在任何的Acceptor通過過編號小於 n 的提案 \ b) v 是 S 中所有Acceptor通過的編號小於 n 的具有最大編號的提案的value值。 $$$

通過維護 $P2^c$ 我們就可以保證$ P2^b$ 了。

實際上 P2c 規定了每個Proposer 如何產生一個提案，對於產生的每個提案 (n, v) 需要滿足這個條件「存在一個由超過半數的Acceptor 組成的集合 S ：要麼 S 中沒有人批准(accept)過編號小於 n 的任何提案，要麼 S 的任何Acceptor批准的所有議案（編號小於 n ）中， v 是編號最大的議案的決議」。當Proposer遵守這個規則產生提案時，就可以保證滿足 P2b 。論文中，作者是從如何產生提案進而可以保證 P2b 來思考，纔得到 P2c 的。下面我們反過來看，證明 P2c 可以保證 P2b 。如論文中一樣，採用數學歸納法證明。
首先假設提案 (m, v) 被選定了，設比該提案編號大的提案為 (n, v』) ,我們需要證明的就是在 P2c 的前提下，對於所有的 (n, v』) ，有 v』 = v 。

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

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

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

為了維護$ P2^c$ 的不變性，一個Proposer在產生編號為 n 的提案時，必須要知道某一個將要或已經被半數以上Acceptor通過的編號小於 n 的最大編號的提案。

為了避免對「將要」成為被半數以上Acceptor通過的提案做預測，我們通過對提案生成演算法的限定，來控制避免預測。即令，Proposer會請求Acceptors不要再通過任何編號小於 n 的提案。這就推導出了Proposer對如下的提案生成演算法：

Proposers 的prepare請求：

Proposer選擇一個新的提案編號 $n$ ，然後向某個Acceptors集合的成員發送請求，要求Acceptor做出如下回應：

保證不再通過任何編號小於 n 的提案
當前它已經通過的編號小於 n 的最大編號的提案，如果存在的話。

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

Proposers 的accept請求：

如果Proposer收到了來自半數以上的Acceptor的響應結果，那麼它就可以產生編號為 n ，value值為 v 的提案，這裡 v 是所有響應中編號最大的提案的value值，如果響應中不包含任何的提案那麼這個值就可以由Proposer任意選擇。

Proposer通過向某個Acceptors集合發送需要被通過的提案請求來產生一個提案（此時的Acceptors集合不一定是響應前一請求的那個Acceptors集合）。我們稱此請求為 accept 請求。

目前我們描述了Proposer端的演算法，Acceptor端是怎樣的呢？

它可能會收到來自Proposer端的兩種請求：prepare請求和accept請求。

Acceptor可以忽略任何請求而不用擔心破壞其演算法的安全性。

因此我們只需要說明它在什麼情況下可以對一個請求做出響應。它可以在任何時候響應一個prepare請求，對於一個accept請求，只要在它未違反現有承諾的情況下才能響應一個accept請求(通過對應的提案)。換句話說：

$P1^a. 一個Acceptor可以接受一個編號為 n 的提案，\只要它還未響應任何編號大於 n 的prepare請求。$

可以看出 $P1^a$ 蘊含了$ P1 $。

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

假設一個Acceptor收到了一個編號為 n 的prepare請求，但是它已經對編號大於 n 的prepare請求做出了響應，因此它肯定不會再通過任何新的編號為n的提案，那麼它就沒有必要對這個請求做出響應，因為它肯定不會通過編號為 n 的提案，因此我們會讓Acceptor忽略這樣的prepare請求。我們也會讓它忽略那些它已經通過的提案的prepare請求。
通過這個優化，Acceptor只需要記住它已經通過的最大編號的提案以及它已經做出prepare請求響應的最大編號的提案的編號。因為必須要保證 P1c 的不變性即使在出錯的情況下，Acceptor必須記住這些信息即使是在出錯或者重啟的情況下。Proposer可以總是可以丟棄提案以及它所有的信息—只要它可以保證不會產生具有相同編號的提案即可。

將Proposer和Acceptor放在一塊，我們可以得到演算法的兩階段執行過程，即解決演算法。

3. 獲取被選定的提案值

為了獲取被選定的值，一個Learner必須確定一個提案已經被半數以上的Acceptor通過。

最明顯的演算法是，讓每個Acceptor，只要它通過了一個提案，就通知所有的Learners，將它通過的提案告知它們。這可以讓Learners儘快的找出被選定的值，但是它需要每個Acceptor都要與每個Learner通信—所需通信的次數等於二者個數的乘積。
另外一個演算法，我們可以讓所有的Acceptor將它們的通過信息發送給一個特定的Learner，當一個$value$被選定時，再由它通知其他的Learners。這種方法，需要多一個步驟才能通知到所有的Learners。而且也是不可靠的，因為那個特定的Learner可能會失敗。但是這種情況下的通信次數，只是Acceptors和Learners的個數的和。

更一般的，Acceptors可以將它們的通過信息發送給一個特定的Learners集合，它們中的每個都可以在一個value被選定後通知所有的Learners。這個集合中的Learners個數越多，可靠性就越好，但是通信複雜度就越高。

由於消息的丟失，一個$value$被選定後，可能沒有Learners會發現。Learner可以詢問Acceptors它們通過了哪些提案，但是一個Acceptor出錯，都有可能導致無法判斷出是否已經有半數以上的Acceptors通過的提案。

在這種情況下，只有當一個新的提案被選定時，Learners才能發現被選定的$value$。因此如果一個Learner想知道是否已經選定一個$value$，它可以讓Proposer利用上面的演算法產生一個提案。

4. 進展性

4.1 FLP impossibility

分散式系統一致性協議裡面有一個FLP impossibility的結論，這個結論是說，在分散式系統中，非同步網路（消息延遲可能任意大或丟失，消息可能亂序），只要有一個進程失效（進程死亡或者足夠長時間不響應），就不可能設計出一個一致性協議。

這個結論說明瞭，即使有一個協議能滿足分散式下的容錯條件，也無法達成分散式下的一致性；只要存在進程失效的情況，就不存在可以達成一致性的協議。

4.1 活鎖

很容易構造出一種情況，在該情況下，兩個Proposers持續地生成編號遞增的一系列提案，但是沒有提案會被選定。

Proposer p1 為一個編號為 n1 的提案完成了Phase1，然後另一個Proposer q 為編號為 n2(n2 > n1) 的提案完成了Phase1。
Proposer p 的針對編號 n1 的提案的Phase2的所有accept請求被忽略，因為Acceptors已經承諾不再通過任何編號小於 n2 的提案。
這樣Proposer p 就會用一個新的編號 n3(n3 > n2) 重新開始並完成Phase1，這又會導致在Phase2裏Proposer q 的所有accept請求被忽略，如此循環往複。

這種情況下演算法產生活鎖。

4.2 Leader演算法

4.2.1 概述

為瞭解決活鎖，我們選擇一個特定的Proposer來作為一個唯一的提案提出者。如果這個Proposer可以同半數以上的Acceptors通信，那麼它就可以獲知目前編號信息，繼而可以

使用一個比現有的編號都大的編號，成功的產生一個可以被通過的提案。
知道某些更高編號的請求時，捨棄當前的提案並重做，產生一個足夠大的提案編號繼而成功的產生一個可以被通過的提案

那麼如果系統中有足夠的組件(Proposer，Acceptors及通信網路)工作良好，通過選擇一個特定的Proposer，活性就可以達到。

對於Leader的選舉，我們可以利用隨機性或者利用實時性（比如使用超時機制）來實現一個可靠的Proposer選舉演算法。

然而，無論選舉是否成功，安全性都可以保證，因為經過上述論證，即使同時有2個或以上的Proposers存在，演算法仍然可以保證正確性。

4.2.2 Multi-Paxos

4.2.2.1 演算法描述

使用了Leader演算法的Paxos演算法，被稱作Multi-Paxos演算法。

在Paxos集羣中利用Paxos協議選舉唯一的leader，在leader有效期內所有的議案都只能由leader發起，這裡強化了協議的假設：即leader有效期內不會有其他server提出的議案。

Multi-Paxos可以簡單的理解為，經過一輪的Basic-Paxos，成功得到多數派accept的proposer即成為leader（這個過程稱為leader Elect），之後可以通過lease機制，保持這個leader的身份，使得其他proposer不再發起提案，這樣就進入了一個leader任期。在leader任期中，由於沒有了並發衝突，這個leader在對後續的日誌進行投票時，不必每次都向多數派詢問logID，也不必執行prepare階段，直接執行accept階段即可。