Paxos演算法詳解

Paxos、Raft分散式一致性演算法應用場景一文講述了分散式一致性問題與分散式一致性演算法的典型應用場景。作為分散式一致性代名詞的Paxos演算法號稱是最難理解的演算法。本文試圖用通俗易懂的語言講述Paxos演算法。

一、Paxos演算法背景

Paxos演算法是Lamport宗師提出的一種基於消息傳遞的分散式一致性演算法，使其獲得2013年圖靈獎。

Paxos由Lamport於1998年在《The Part-Time Parliament》論文中首次公開，最初的描述使用希臘的一個小島Paxos作為比喻，描述了Paxos小島中通過決議的流程，並以此命名這個演算法，但是這個描述理解起來比較有挑戰性。後來在2001年，Lamport覺得同行不能理解他的幽默感，於是重新發表了樸實的演算法描述版本《Paxos Made Simple》。

自Paxos問世以來就持續壟斷了分散式一致性演算法，Paxos這個名詞幾乎等同於分散式一致性。Google的很多大型分散式系統都採用了Paxos演算法來解決分散式一致性問題，如Chubby、Megastore以及Spanner等。開源的ZooKeeper，以及MySQL 5.7推出的用來取代傳統的主從複製的MySQL Group Replication等紛紛採用Paxos演算法解決分散式一致性問題。

然而，Paxos的最大特點就是難，不僅難以理解，更難以實現。

二、Paxos演算法流程

Paxos演算法解決的問題正是分散式一致性問題，即一個分散式系統中的各個進程如何就某個值（決議）達成一致。

Paxos演算法運行在允許宕機故障的非同步系統中，不要求可靠的消息傳遞，可容忍消息丟失、延遲、亂序以及重複。它利用大多數 (Majority) 機制保證了2F+1的容錯能力，即2F+1個節點的系統最多允許F個節點同時出現故障。

一個或多個提議進程 (Proposer) 可以發起提案 (Proposal)，Paxos演算法使所有提案中的某一個提案，在所有進程中達成一致。系統中的多數派同時認可該提案，即達成了一致。最多只針對一個確定的提案達成一致。

Paxos將系統中的角色分為提議者 (Proposer)，決策者 (Acceptor)，和最終決策學習者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案編號 (Proposal ID) 和提議的值 (Value)。
• Acceptor：參與決策，回應Proposers的提案。收到Proposal後可以接受提案，若Proposal獲得多數Acceptors的接受，則稱該Proposal被批准。
• Learner：不參與決策，從Proposers/Acceptors學習最新達成一致的提案（Value）。

在多副本狀態機中，每個副本同時具有Proposer、Acceptor、Learner三種角色。

Paxos演算法通過一個決議分為兩個階段（Learn階段之前決議已經形成）：

1. 第一階段：Prepare階段。Proposer向Acceptors發出Prepare請求，Acceptors針對收到的Prepare請求進行Promise承諾。
2. 第二階段：Accept階段。Proposer收到多數Acceptors承諾的Promise後，向Acceptors發出Propose請求，Acceptors針對收到的Propose請求進行Accept處理。
3. 第三階段：Learn階段。Proposer在收到多數Acceptors的Accept之後，標誌著本次Accept成功，決議形成，將形成的決議發送給所有Learners。

Paxos演算法流程中的每條消息描述如下：

• Prepare: Proposer生成全局唯一且遞增的Proposal ID (可使用時間戳加Server ID)，向所有Acceptors發送Prepare請求，這裡無需攜帶提案內容，只攜帶Proposal ID即可。
• Promise: Acceptors收到Prepare請求後，做出「兩個承諾，一個應答」。

兩個承諾：

1. 不再接受Proposal ID小於等於（注意：這裡是<= ）當前請求的Prepare請求。

2. 不再接受Proposal ID小於（注意：這裡是< ）當前請求的Propose請求。

一個應答：

不違背以前作出的承諾下，回復已經Accept過的提案中Proposal ID最大的那個提案的Value和Proposal ID，沒有則返回空值。

• Propose: Proposer 收到多數Acceptors的Promise應答後，從應答中選擇Proposal ID最大的提案的Value，作為本次要發起的提案。如果所有應答的提案Value均為空值，則可以自己隨意決定提案Value。然後攜帶當前Proposal ID，向所有Acceptors發送Propose請求。
• Accept: Acceptor收到Propose請求後，在不違背自己之前作出的承諾下，接受並持久化當前Proposal ID和提案Value。
• Learn: Proposer收到多數Acceptors的Accept後，決議形成，將形成的決議發送給所有Learners。

Paxos演算法偽代碼描述如下：

1. 獲取一個Proposal ID n，為了保證Proposal ID唯一，可採用時間戳+Server ID生成；
2. Proposer向所有Acceptors廣播Prepare(n)請求；
3. Acceptor比較n和minProposal，如果n>minProposal，表示有更新的提議，minProposal=n；否則將 (acceptedProposal,acceptedValue) 返回；
4. Proposer接收到過半數回復後，如果發現有acceptedValue返回，表示有更新的提議，保存acceptedValue到本地，然後跳轉1，生成一個Proposal ID更高的提議；
5. 到這裡表示沒有Proposal ID更高的提議，可以進入第二階段，廣播Accept (n,value) 到所有節點；
6. Acceptor比較n和minProposal，如果n>=minProposal，則acceptedProposal=minProposal=n，acceptedValue=value，本地持久化後，返回；否則，返回minProposal。
7. 提議者接收到過半數請求後，如果發現有返回值result >n，表示有更新的提議，跳轉到1；否則value達成一致。

下面舉幾個例子，實例1如下圖：

圖中P代表Prepare階段，A代表Accept階段。3.1代表Proposal ID為3.1，其中3為時間戳，1為Server ID。X和Y代表提議Value。

實例1中P 3.1達成多數派，其Value(X)被Accept，然後P 4.5學習到Value(X)，並Accept。

實例2中P 3.1沒有被多數派Accept（只有S3 Accept），但是被P 4.5學習到，P 4.5將自己的Value由Y替換為X，Accept（X）。

實例3中P 3.1沒有被多數派Accept（只有S1 Accept），同時也沒有被P 4.5學習到。由於P 4.5 Propose的所有應答，均未返回Value，則P 4.5可以Accept自己的Value (Y)。後續P 3.1的Accept (X) 會失敗，已經Accept的S1，會被覆蓋。

Paxos演算法可能形成活鎖而永遠不會結束，如下圖實例所示：

回顧兩個承諾之一，Acceptor不再應答Proposal ID小於等於當前請求的Prepare請求。意味著需要應答Proposal ID大於當前請求的Prepare請求。

兩個Proposers交替Prepare成功，而Accept失敗，形成活鎖（Livelock）。

三、Multi-Paxos演算法

原始的Paxos演算法（Basic Paxos）只能對一個值形成決議，決議的形成至少需要兩次網路來回，在高並發情況下可能需要更多的網路來回，極端情況下甚至可能形成活鎖。如果想連續確定多個值，Basic Paxos搞不定了。因此Basic Paxos幾乎只是用來做理論研究，並不直接應用在實際工程中。

實際應用中幾乎都需要連續確定多個值，而且希望能有更高的效率。Multi-Paxos正是為解決此問題而提出。Multi-Paxos基於Basic Paxos做了兩點改進：

1. 針對每一個要確定的值，運行一次Paxos演算法實例（Instance），形成決議。每一個Paxos實例使用唯一的Instance ID標識。
2. 在所有Proposers中選舉一個Leader，由Leader唯一地提交Proposal給Acceptors進行表決。這樣沒有Proposer競爭，解決了活鎖問題。在系統中僅有一個Leader進行Value提交的情況下，Prepare階段就可以跳過，從而將兩階段變為一階段，提高效率。

Multi-Paxos首先需要選舉Leader，Leader的確定也是一次決議的形成，所以可執行一次Basic Paxos實例來選舉出一個Leader。選出Leader之後只能由Leader提交Proposal，在Leader宕機之後服務臨時不可用，需要重新選舉Leader繼續服務。在系統中僅有一個Leader進行Proposal提交的情況下，Prepare階段可以跳過。

Multi-Paxos通過改變Prepare階段的作用範圍至後面Leader提交的所有實例，從而使得Leader的連續提交只需要執行一次Prepare階段，後續只需要執行Accept階段，將兩階段變為一階段，提高了效率。為了區分連續提交的多個實例，每個實例使用一個Instance ID標識，Instance ID由Leader本地遞增生成即可。

Multi-Paxos允許有多個自認為是Leader的節點並發提交Proposal而不影響其安全性，這樣的場景即退化為Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的變形。

附Paxos演算法推導過程

Paxos演算法的設計過程就是從正確性開始的，對於分散式一致性問題，很多進程提出（Propose）不同的值，共識演算法保證最終只有其中一個值被選定，Safety表述如下：

• 只有被提出（Propose）的值才可能被最終選定（Chosen）。
• 只有一個值會被選定（Chosen）。
• 進程只會獲知到已經確認被選定（Chosen）的值。

Paxos以這幾條約束作為出發點進行設計，只要演算法最終滿足這幾點，正確性就不需要證明了。Paxos演算法中共分為三種參與者：Proposer、Acceptor以及Learner，通常實現中每個進程都同時扮演這三個角色。

Proposers向Acceptors提出Proposal，為了保證最多只有一個值被選定（Chosen），Proposal必須被超過一半的Acceptors所接受（Accept），且每個Acceptor只能接受一個值。

為了保證正常運行（必須有值被接受），所以Paxos演算法中：

P1：Acceptor必須接受（Accept）它所收到的第一個Proposal。

先來先服務，合情合理。但這樣產生一個問題，如果多個Proposers同時提出Proposal，很可能會導致無法達成一致，因為沒有Propopal被超過一半Acceptors的接受，因此，Acceptor必須能夠接受多個Proposal，不同的Proposal由不同的編號進行區分，當某個Proposal被超過一半的Acceptors接受後，這個Proposal就被選定了。

既然允許Acceptors接受多個Proposal就有可能出現多個不同值都被最終選定的情況，這違背了Safety要求，為了保證Safety要求，Paxos進一步提出：

P2：如果值為v的Proposal被選定（Chosen），則任何被選定（Chosen）的具有更高編號的Proposal值也一定為v。

只要演算法同時滿足P1和P2，就保證了Safety。P2是一個比較寬泛的約定，完全沒有演算法細節，我們對其進一步延伸：

P2a：如果值為v的Proposal被選定（Chosen），則對所有的Acceptors，它們接受（Accept）的任何具有更高編號的Proposal值也一定為v。

如果滿足P2a則一定滿足P2，顯然，因為只有首先被接受才有可能被最終選定。但是P2a依然難以實現，因為acceptor很有可能並不知道之前被選定的Proposal（恰好不在接受它的多數派中），因此進一步延伸：

P2b：如果值為v的Proposal被選定（Chosen），則對所有的Proposer，它們提出的的任何具有更高編號的Proposal值也一定為v。

更進一步的：

P2c：為了提出值為v且編號為n的Proposal，必須存在一個包含超過一半Acceptors的集合S，滿足(1) 沒有任何S中的Acceptors曾經接受（Accept）過編號比n小的Proposal，或者(2) v和S中的Acceptors所接受過(Accept)的編號最大且小於n的Proposal值一致。

滿足P2c即滿足P2b即滿足P2a即滿足P2。至此Paxos提出了Proposer的執行流程，以滿足P2c：

1. Proposer選擇一個新的編號n，向超過一半的Acceptors發送請求消息，Acceptor回復: (a)承諾不會接受編號比n小的proposal，以及(b)它所接受過的編號比n小的最大Proposal（如果有）。該請求稱為Prepare請求。
2. 如果Proposer收到超過一半Acceptors的回復，它就可以提出Proposal，Proposal的值為收到回復中編號最大的Proposal的值，如果沒有這樣的值，則可以自由提出任何值。
3. 向收到回復的Acceptors發送Accept請求，請求對方接受提出的Proposal。

仔細品味Proposer的執行流程，其完全吻合P2c中的要求，但你可能也發現了，當多個Proposer同時運行時，有可能出現沒有任何Proposal可以成功被接受的情況（編號遞增的交替完成第一步），這就是Paxos演算法的Liveness問題，或者叫「活鎖」，論文中建議通過對Proposers引入選主演算法選出Distinguished Proposer來全權負責提出Proposal來解決這個問題，但是即使在出現多個Proposers同時提出Proposal的情況時，Paxos演算法也可以保證Safety。

接下來看看Acceptors的執行過程，和我們對P2做的事情一樣，我們對P1進行延伸：

P1a：Acceptor可以接受（Accept）編號為n的Proposal當且僅當它沒有回復過一個具有更大編號的Prepare消息。

易見，P1a包含了P1，對於Acceptors：

1. 當收到Prepare請求時，如果其編號n大於之前所收到的Prepare消息，則回復。
2. 當收到Accept請求時，僅當它沒有回復過一個具有更大編號的Prepare消息，接受該Proposal並回復。

以上涵蓋了滿足P1a和P2b的一套完整一致性演算法。

註：文中部分圖片來自互聯網。

推薦閱讀：