paxos算法在分布式領(lǐng)域具有非常重要的地位。但是Paxos算法有兩個(gè)比較明顯的缺點(diǎn)：1.難以理解 2.工程實(shí)現(xiàn)更難。

[[313088]]

網(wǎng)上有很多講解Paxos算法的文章，但是質(zhì)量參差不齊。看了很多關(guān)于Paxos的資料后發(fā)現(xiàn)，學(xué)習(xí)Paxos最好的資料是論文《Paxos Made Simple》，其次是中、英文版維基百科對(duì)Paxos的介紹。本文試圖帶大家一步步揭開Paxos神秘的面紗。

Paxos是什么

Paxos算法是基于消息傳遞且具有高度容錯(cuò)特性的一致性算法，是目前公認(rèn)的解決分布式一致性問題最有效的算法之一。

Google Chubby的作者M(jìn)ike Burrows說過這個(gè)世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

雖然Mike Burrows說得有點(diǎn)夸張，但是至少說明了Paxos算法的地位。然而，Paxos算法也因?yàn)榛逎y懂而臭名昭著。本文的目的就是帶領(lǐng)大家深入淺出理解Paxos算法，不僅理解它的執(zhí)行流程，還要理解算法的推導(dǎo)過程，作者是怎么一步步想到最終的方案的。只有理解了推導(dǎo)過程，才能深刻掌握該算法的精髓。而且理解推導(dǎo)過程對(duì)于我們的思維也是非常有幫助的，可能會(huì)給我們帶來一些解決問題的思路，對(duì)我們有所啟發(fā)。

問題產(chǎn)生的背景

在常見的分布式系統(tǒng)中，總會(huì)發(fā)生諸如機(jī)器宕機(jī)或網(wǎng)絡(luò)異常(包括消息的延遲、丟失、重復(fù)、亂序，還有網(wǎng)絡(luò)分區(qū))等情況。Paxos算法需要解決的問題就是如何在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生以上任何異常，都不會(huì)破壞整個(gè)系統(tǒng)的一致性。

注：這里某個(gè)數(shù)據(jù)的值并不只是狹義上的某個(gè)數(shù)，它可以是一條日志，也可以是一條命令(command)。。。根據(jù)應(yīng)用場(chǎng)景不同，某個(gè)數(shù)據(jù)的值有不同的含義。

 

 

相關(guān)概念

在Paxos算法中，有三種角色：

Proposer

Acceptor

Learners

在具體的實(shí)現(xiàn)中，一個(gè)進(jìn)程可能同時(shí)充當(dāng)多種角色。比如一個(gè)進(jìn)程可能既是Proposer又是Acceptor又是Learner。

還有一個(gè)很重要的概念叫提案(Proposal)。最終要達(dá)成一致的value就在提案里。

注：

暫且認(rèn)為『提案=value』，即提案只包含value。在我們接下來的推導(dǎo)過程中會(huì)發(fā)現(xiàn)如果提案只包含value，會(huì)有問題，于是我們?cè)賹?duì)提案重新設(shè)計(jì)。

暫且認(rèn)為『Proposer可以直接提出提案』。在我們接下來的推導(dǎo)過程中會(huì)發(fā)現(xiàn)如果Proposer直接提出提案會(huì)有問題，需要增加一個(gè)學(xué)習(xí)提案的過程。

Proposer可以提出(propose)提案;Acceptor可以接受(accept)提案;如果某個(gè)提案被選定(chosen)，那么該提案里的value就被選定了。

回到剛剛說的『對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致』，指的是Proposer、Acceptor、Learner都認(rèn)為同一個(gè)value被選定(chosen)。那么，Proposer、Acceptor、Learner分別在什么情況下才能認(rèn)為某個(gè)value被選定呢?

Proposer：只要Proposer發(fā)的提案被Acceptor接受(剛開始先認(rèn)為只需要一個(gè)Acceptor接受即可，在推導(dǎo)過程中會(huì)發(fā)現(xiàn)需要半數(shù)以上的Acceptor同意才行)，Proposer就認(rèn)為該提案里的value被選定了。

Acceptor：只要Acceptor接受了某個(gè)提案，Acceptor就任務(wù)該提案里的value被選定了。

Learner：Acceptor告訴Learner哪個(gè)value被選定，Learner就認(rèn)為那個(gè)value被選定。

 

 

問題描述

假設(shè)有一組可以提出(propose)value(value在提案Proposal里)的進(jìn)程集合。一個(gè)一致性算法需要保證提出的這么多value中，只有一個(gè)value被選定(chosen)。如果沒有value被提出，就不應(yīng)該有value被選定。如果一個(gè)value被選定，那么所有進(jìn)程都應(yīng)該能學(xué)習(xí)(learn)到這個(gè)被選定的value。對(duì)于一致性算法，安全性(safaty)要求如下：

只有被提出的value才能被選定。

只有一個(gè)value被選定，并且

如果某個(gè)進(jìn)程認(rèn)為某個(gè)value被選定了，那么這個(gè)value必須是真的被選定的那個(gè)。

我們不去精確地定義其活性(liveness)要求。我們的目標(biāo)是保證最終有一個(gè)提出的value被選定。當(dāng)一個(gè)value被選定后，進(jìn)程最終也能學(xué)習(xí)到這個(gè)value。

Paxos的目標(biāo)：保證最終有一個(gè)value會(huì)被選定，當(dāng)value被選定后，進(jìn)程最終也能獲取到被選定的value。

假設(shè)不同角色之間可以通過發(fā)送消息來進(jìn)行通信，那么：

每個(gè)角色以任意的速度執(zhí)行，可能因出錯(cuò)而停止，也可能會(huì)重啟。一個(gè)value被選定后，所有的角色可能失敗然后重啟，除非那些失敗后重啟的角色能記錄某些信息，否則等他們重啟后無法確定被選定的值。

消息在傳遞過程中可能出現(xiàn)任意時(shí)長(zhǎng)的延遲，可能會(huì)重復(fù)，也可能丟失。但是消息不會(huì)被損壞，即消息內(nèi)容不會(huì)被篡改(拜占庭將軍問題)。

推導(dǎo)過程

最簡(jiǎn)單的方案——只有一個(gè)Acceptor

假設(shè)只有一個(gè)Acceptor(可以有多個(gè)Proposer)，只要Acceptor接受它收到的第一個(gè)提案，則該提案被選定，該提案里的value就是被選定的value。這樣就保證只有一個(gè)value會(huì)被選定。

但是，如果這個(gè)唯一的Acceptor宕機(jī)了，那么整個(gè)系統(tǒng)就無法工作了!

因此，必須要有多個(gè)Acceptor!

 

 

多個(gè)Acceptor

多個(gè)Acceptor的情況如下圖。那么，如何保證在多個(gè)Proposer和多個(gè)Acceptor的情況下選定一個(gè)value呢?

 

 

下面開始尋找解決方案。

如果我們希望即使只有一個(gè)Proposer提出了一個(gè)value，該value也最終被選定。

那么，就得到下面的約束：

P1：一個(gè)Acceptor必須接受它收到的第一個(gè)提案。

但是，這又會(huì)引出另一個(gè)問題：如果每個(gè)Proposer分別提出不同的value，發(fā)給不同的Acceptor。根據(jù)P1，Acceptor分別接受自己收到的value，就導(dǎo)致不同的value被選定。出現(xiàn)了不一致。如下圖：

 

 

剛剛是因?yàn)椤阂粋€(gè)提案只要被一個(gè)Acceptor接受，則該提案的value就被選定了』才導(dǎo)致了出現(xiàn)上面不一致的問題。因此，我們需要加一個(gè)規(guī)定：

規(guī)定：一個(gè)提案被選定需要被半數(shù)以上的Acceptor接受

這個(gè)規(guī)定又暗示了：『一個(gè)Acceptor必須能夠接受不止一個(gè)提案!』不然可能導(dǎo)致最終沒有value被選定。比如上圖的情況。v1、v2、v3都沒有被選定，因?yàn)樗鼈兌贾槐灰粋€(gè)Acceptor的接受。

最開始講的『提案=value』已經(jīng)不能滿足需求了，于是重新設(shè)計(jì)提案，給每個(gè)提案加上一個(gè)提案編號(hào)，表示提案被提出的順序。令『提案=提案編號(hào)+value』。

雖然允許多個(gè)提案被選定，但必須保證所有被選定的提案都具有相同的value值。否則又會(huì)出現(xiàn)不一致。

于是有了下面的約束：

P2：如果某個(gè)value為v的提案被選定了，那么每個(gè)編號(hào)更高的被選定提案的value必須也是v。

一個(gè)提案只有被Acceptor接受才可能被選定，因此我們可以把P2約束改寫成對(duì)Acceptor接受的提案的約束P2a。

P2a：如果某個(gè)value為v的提案被選定了，那么每個(gè)編號(hào)更高的被Acceptor接受的提案的value必須也是v。

只要滿足了P2a，就能滿足P2。

但是，考慮如下的情況：假設(shè)總的有5個(gè)Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2~5(半數(shù)以上)均接受了該提案，于是對(duì)于Acceptor2~5和Proposer2來講，它們都認(rèn)為V1被選定。Acceptor1剛剛從宕機(jī)狀態(tài)恢復(fù)過來(之前Acceptor1沒有收到過任何提案)，此時(shí)Proposer1向Acceptor1發(fā)送了[M2,V2]的提案(V2≠V1且M2>M1)，對(duì)于Acceptor1來講，這是它收到的第一個(gè)提案。根據(jù)P1(一個(gè)Acceptor必須接受它收到的第一個(gè)提案。),Acceptor1必須接受該提案!同時(shí)Acceptor1認(rèn)為V2被選定。這就出現(xiàn)了兩個(gè)問題：

Acceptor1認(rèn)為V2被選定，Acceptor2~5和Proposer2認(rèn)為V1被選定。出現(xiàn)了不一致。

V1被選定了，但是編號(hào)更高的被Acceptor1接受的提案[M2,V2]的value為V2，且V2≠V1。這就跟P2a(如果某個(gè)value為v的提案被選定了，那么每個(gè)編號(hào)更高的被Acceptor接受的提案的value必須也是v)矛盾了。

 

 

所以我們要對(duì)P2a約束進(jìn)行強(qiáng)化!

P2a是對(duì)Acceptor接受的提案約束，但其實(shí)提案是Proposer提出來的，所有我們可以對(duì)Proposer提出的提案進(jìn)行約束。得到P2b：

P2b：如果某個(gè)value為v的提案被選定了，那么之后任何Proposer提出的編號(hào)更高的提案的value必須也是v。

由P2b可以推出P2a進(jìn)而推出P2。

那么，如何確保在某個(gè)value為v的提案被選定后，Proposer提出的編號(hào)更高的提案的value都是v呢?

只要滿足P2c即可：

P2c：對(duì)于任意的N和V，如果提案[N, V]被提出，那么存在一個(gè)半數(shù)以上的Acceptor組成的集合S，滿足以下兩個(gè)條件中的任意一個(gè)：

S中每個(gè)Acceptor都沒有接受過編號(hào)小于N的提案。

S中Acceptor接受過的最大編號(hào)的提案的value為V。

Proposer生成提案

為了滿足P2b，這里有個(gè)比較重要的思想：Proposer生成提案之前，應(yīng)該先去『學(xué)習(xí)』已經(jīng)被選定或者可能被選定的value，然后以該value作為自己提出的提案的value。如果沒有value被選定，Proposer才可以自己決定value的值。這樣才能達(dá)成一致。這個(gè)學(xué)習(xí)的階段是通過一個(gè)『Prepare請(qǐng)求』實(shí)現(xiàn)的。

于是我們得到了如下的提案生成算法：

Proposer選擇一個(gè)新的提案編號(hào)N，然后向某個(gè)Acceptor集合(半數(shù)以上)發(fā)送請(qǐng)求，要求該集合中的每個(gè)Acceptor做出如下響應(yīng)(response)。

(a) 向Proposer承諾保證不再接受任何編號(hào)小于N的提案。

(b) 如果Acceptor已經(jīng)接受過提案，那么就向Proposer響應(yīng)已經(jīng)接受過的編號(hào)小于N的最大編號(hào)的提案。

我們將該請(qǐng)求稱為編號(hào)為N的Prepare請(qǐng)求。

如果Proposer收到了半數(shù)以上的Acceptor的響應(yīng)，那么它就可以生成編號(hào)為N，Value為V的提案[N,V]。這里的V是所有的響應(yīng)中編號(hào)最大的提案的Value。如果所有的響應(yīng)中都沒有提案，那 么此時(shí)V就可以由Proposer自己選擇。

生成提案后，Proposer將該提案發(fā)送給半數(shù)以上的Acceptor集合，并期望這些Acceptor能接受該提案。我們稱該請(qǐng)求為Accept請(qǐng)求。(注意：此時(shí)接受Accept請(qǐng)求的Acceptor集合不一定是之前響應(yīng)Prepare請(qǐng)求的Acceptor集合)

Acceptor接受提案

Acceptor可以忽略任何請(qǐng)求(包括Prepare請(qǐng)求和Accept請(qǐng)求)而不用擔(dān)心破壞算法的安全性。因此，我們這里要討論的是什么時(shí)候Acceptor可以響應(yīng)一個(gè)請(qǐng)求。

我們對(duì)Acceptor接受提案給出如下約束：

P1a：一個(gè)Acceptor只要尚未響應(yīng)過任何編號(hào)大于N的Prepare請(qǐng)求，那么他就可以接受這個(gè)編號(hào)為N的提案。

如果Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，在此之前它已經(jīng)響應(yīng)過編號(hào)大于N的Prepare請(qǐng)求。根據(jù)P1a，該Acceptor不可能接受編號(hào)為N的提案。因此，該Acceptor可以忽略編號(hào)為N的Prepare請(qǐng)求。當(dāng)然，也可以回復(fù)一個(gè)error，讓Proposer盡早知道自己的提案不會(huì)被接受。

因此，一個(gè)Acceptor只需記住：1. 已接受的編號(hào)最大的提案 2. 已響應(yīng)的請(qǐng)求的最大編號(hào)。

 

 

Paxos算法描述

經(jīng)過上面的推導(dǎo)，我們總結(jié)下Paxos算法的流程。

Paxos算法分為兩個(gè)階段。具體如下：

階段一：

(a) Proposer選擇一個(gè)提案編號(hào)N，然后向半數(shù)以上的Acceptor發(fā)送編號(hào)為N的Prepare請(qǐng)求。

(b) 如果一個(gè)Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，且N大于該Acceptor已經(jīng)響應(yīng)過的所有Prepare請(qǐng)求的編號(hào)，那么它就會(huì)將它已經(jīng)接受過的編號(hào)最大的提案(如果有的話)作為響應(yīng)反饋給Proposer，同時(shí)該Acceptor承諾不再接受任何編號(hào)小于N的提案。

階段二：

(a) 如果Proposer收到半數(shù)以上Acceptor對(duì)其發(fā)出的編號(hào)為N的Prepare請(qǐng)求的響應(yīng)，那么它就會(huì)發(fā)送一個(gè)針對(duì)[N,V]提案的Accept請(qǐng)求給半數(shù)以上的Acceptor。注意：V就是收到的響應(yīng)中編號(hào)最大的提案的value，如果響應(yīng)中不包含任何提案，那么V就由Proposer自己決定。

(b) 如果Acceptor收到一個(gè)針對(duì)編號(hào)為N的提案的Accept請(qǐng)求，只要該Acceptor沒有對(duì)編號(hào)大于N的Prepare請(qǐng)求做出過響應(yīng)，它就接受該提案。

 

 

Learner學(xué)習(xí)被選定的value

Learner學(xué)習(xí)(獲取)被選定的value有如下三種方案：

 

 

如何保證Paxos算法的活性

 

 

通過選取主Proposer，就可以保證Paxos算法的活性。至此，我們得到一個(gè)既能保證安全性，又能保證活性的分布式一致性算法——Paxos算法。