目錄

Paxos一致性演算法詳解

1.問題描述

2.推導程序

3.演算法流程

4.Multi-Paxos演算法

5.參考文獻

Paxos一致性演算法詳解

1.問題描述

假設有一組可以提出提案的行程集合，那么對于一個一致性演算法來說需要保證以下幾點:

• 在這些被提出的提案中，只有一個會被選定，
• 如果沒有提案被提出，那么就不會有被選定的提案，
• 當一個提案被選定后，行程應該可以獲取被選定的提案資訊，

而且為了滿足安全一致性，有如下要求:

• 要求只有被提出的提案才能被選定，
• 只能有一個提案被選定，
• 如果某個行程認為某個提案被選定了，那么這個提案必須是真的被選定的那個，

在Paxos一致性演算法中，有Proposer、Acceptor和Learner三種參與角色，假設不同參與者之間可以通過收發訊息來進行通信，其中Proposer提出提案，Acceptor決定哪個提案作為被選定的提案，Learner作為提案的接受者，

2.推導程序

本部分描述性文字比較多，如果對此不感興趣，可以直接看第3部分的演算法流程，

首先，我們希望即使只有一個提案被提出，仍然可以有提案被選定，這暗示我們：

P1：一個Acceptor必須批準它收到的第一個提案，

但根據P1，就可能導致多個提案分別被數量一致或相近的Acceptor批準，比如A、B分別被1、2批準，這樣仍然無法確定唯一一個提案，怎么解決呢？

P2：一個提案被選定必須得到半數以上的Acceptor的批準，

這一需求的引入，表明Paxos演算法要求奇數個節點組成集群，它的容錯能力為2F+1，即最多允許F個節點同時出現故障，

至此我們已經保證了，只要有提案被提出，就一定會有一個提案被選定，并且結合P1和P2，暗示一個Acceptor必須能夠批準多個提案，我們在這里引入一個全域有序的編號，ProposalID來唯一標識每一個被Acceptor批準的提案，

當一個提案——我們用value指代它的內容，被半數以上Acceptor批準后，我們就認為該value被選定了，該提案也被選定了，此時提案變成了一個由編號和Value組成的結合體：[ProposalID,Value]，

但此時又出現了一個問題，Acceptor可以批準對個提案，這就導致可能會有多個不同提案被選定，這違背了第1節中只有一個提案被選定的要求，所以：

P3：如果提案[ProposalID0,Value0]被選定了，那么后續所有被選定的提案的Value都必須為Value0，

只要能滿足P3，即使有多個提案被選定，我們也可以保證所有被選定的提案具有相同的value值，

那怎么滿足P3的要求呢？我們可以進一步得到

P3-1：如果提案[ProposalID0,Value0]被選定了，那么后續所有Acceptor批準的提案的Value都必須為Value0，

只要滿足P3-1，P3肯定滿足，但問題來了，如果此時提案[ProposalID0,Value0]被選定了，但是AcceptorN正好沒有批準這個提案因為通信是異步的，即它不知道該提案已經被選定，它就沒法對它后續批準的提案進行設定，這仍然會使得P3不滿足，所以我們可以進一步對Proposer要求：

P3-2：如果提案[ProposalID0,Value0]被選定了，那么之后任何Proposer提出的提案Value值都必須為Value0，

綜上，我們可以得到Propser的執行流程：

1.Proposer向半數以上Acceptors發送一個只含有ProposalID的訊息，該請求稱為準備請求，

2.如果Proposer收到超過一半Accepotor的回復，就使用回復中最大的ProposalID的value，加上準備訊息的ProposalID作為提案，如果回復中value為空，則可以提出任意值，

3.向回復的Acceptors發送Accept請求，請求它們批準提出的Proposal，

Acceptor的執行流程如下：

1.當收到準備請求時，如果ProposalID大于之前收到的準備訊息，則回復其批準過的最大編號的提案，

2.當收到Accept請求時，如果Acceptor沒有回復過一個更大ProposalID的準備訊息，接受該Proposal并回復，

3.演算法流程

我們可以得到Paxos的演算法流程：

1.Proposer選擇一個提案編號Mn（為保證唯一，可以使用時間戳+ServerID），然后向半數以上的Acceptor發送編號為Mn的準備請求，

2.如果一個Acceptor，A收到一個編號為Mn的準備請求，且Mn>A之前回應過的準備訊息的最大編號（maxM_pre），則A將其批準過的最大編號的提案（既包含編號又包含value，假定為[Ma_max,va]）作為回應反饋給Proposer，并且令maxM_pre=Mn（即不再回復編號小于等于Mn的準備訊息），

3.如果Proposer收到來自半數以上的Acceptor對于準備訊息Mn回傳的反饋，那么他就會發送一個提案[Mn,Vn]給Acceptors，其中Vn為收到的反饋中編號最大的提案的值（即可能為va），如果回應中不包含任何提案，則可以是任意值，這一步被稱為Accept請求，

4.如果Acceptor收到這個針對[Mn,Vn]提案的Accept的請求，只要maxM_pre<=Mn，即沒回應過更大編號的準備請求，則通過這個提案，同時，令Ma_max=Mn,va=Vn，

偽代碼如下：

通過偽代碼我們可以發現一個問題，假設有兩個ProposerA和B，A發送一個準備得到了半數以上的反饋，正在進行accept請求時，B也發送了一個準備，此時A檢測到有更新的提案，會重新回到步驟1，重復上面程序，將會形成一個活鎖(Livelock)的情形，

可以考慮選擇一個Proposer作為主Proposer，規定只有它能提出提案，這樣就能保證演算法流程的活性，

4.Multi-Paxos演算法

原始的Paxos演算法（Basic Paxos）只能對一個值形成決議，決議的形成至少需要兩次網路來回，在高并發情況下可能需要更多的網路來回，極端情況下甚至可能形成活鎖，如果想連續確定多個值，原始Paxos演算法就無法解決，

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

1. 針對每一個要確定的值，運行一次Paxos演算法實體（Instance），形成決議，每一個Paxos實體使用唯一的Instance ID標識，
2. 在所有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的變形，

5.參考文獻

[1]https://zhuanlan.zhihu.com/p/31780743

[2]《從Paxos到Zookeeper分布式一致性原理與實踐》