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算法中的角色

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

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

Paxos算法流程

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算法偽代碼描述如下：

Paxos算法偽代碼

獲取一個Proposal ID n，為了保證Proposal ID唯一，可采用時間戳+Server ID生成；
Proposer向所有Acceptors廣播Prepare(n)請求；
Acceptor比較n和minProposal，如果n>minProposal，minProposal=n，并且將 acceptedProposal 和 acceptedValue 返回；
Proposer接收到過半數回復后，如果發現有acceptedValue返回，將所有回復中acceptedProposal最大的acceptedValue作為本次提案的value，否則可以任意決定本次提案的value；
到這里可以進入第二階段，廣播Accept (n,value) 到所有節點；
Acceptor比較n和minProposal，如果n>=minProposal，則acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否則，返回minProposal。
提議者接收到過半數請求后，如果發現有返回值result >n，表示有更新的提議，跳轉到1；否則value達成一致。

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

Paxos算法實例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。

Paxos算法實例2

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

Paxos算法實例3

實例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算法可能形成活鎖而永遠不會結束，如下圖實例所示：

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做了兩點改進：

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

Multi-Paxos流程

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：

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

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

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

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

https://zhuanlan.zhihu.com/p/31780743

---------------------
作者：Omni-Space
來源：CSDN
原文：https://blog.csdn.net/omnispace/article/details/79653932
版權聲明：本文為作者原創文章，轉載請附上博文鏈接！
內容解析By：CSDN,CNBLOG博客文章一鍵轉載插件