世上只有一種一致性演算法，那就是Paxos ，所有其它一致性演算法都是Paxos演算法的不完整版！

前言

最近在研究Paxos演算法，提到分布式演算法，就不得不提 Paxos 演算法，在過去幾十年里，它基本上是分布式共識的代名詞，因為當前最常用的一批共識演算法都是基于它改進的，比如，Fast Paxos 演算法、Cheap Paxos 演算法、Raft 演算法等等，看了許多相關的文章，概念還是比較模糊，這其實側面說明了 Paxos 演算法有一定的難度，可分布式演算法本身就很復雜，這里整理一下相關的概念便于自己的理解，

概述

Paxos 演算法是萊斯利·蘭伯特（Leslie Lamport，現就職于微軟研究院）于1990年提出的，是一種基于訊息傳遞的一致性演算法，萊斯利·蘭伯特于2013年獲得了圖靈獎，他的分布式計算理論奠定了這門學科的基礎，萊斯利·蘭伯特在1978年發表了論文《分布式系統內的時間、時鐘事件順序》(Time, Clocks, and the Ordering of Events in a Distributed System)，這篇論文成為目前計算機科學史上被參考最多的文獻，他的論文為并發系統的規范與驗證課題的研究貢獻了核心原理，Paxos演算法是在萊斯利·蘭伯特的論文The Part-Time Parliament中提出的，在論文中，他以故事的方式講述了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階段之前決議已經形成）：

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演算法流程

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演算法偽代碼

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回傳，將所有回復中acceptedProposal最大的acceptedValue作為本次提案的value，否則可以任意決定本次提案的value；
5. 到這里可以進入第二階段，廣播Accept (n,value) 到所有節點；
6. Acceptor比較n和minProposal，如果n>=minProposal，則acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，回傳；否則，回傳minProposal，
7. 提議者接收到過半數請求后，如果發現有回傳值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），

參考文章:https://zhuanlan.zhihu.com/p/31780743

總結

　　Paxos演算法是保證在分布式系統中寫操作能夠順利進行，保證系統中大多數狀態是一致的，沒有機會看到不一致，因此，Paxos演算法的特點是一致性>可用性，vector clock向量時鐘是另外一種保證復制的演算法，其特點是可用性>一致性，但是，一旦發生沖突，不像Paxos能自行解決，需要人工干預撰寫代碼解決，Paxos演算法和Vector Clock都是由Leslie Lamport提出，