Paxos算法的特性以及算法

Google的粗粒度鎖服務(wù)Chubby的設(shè)計(jì)開(kāi)發(fā)者Burrows曾經(jīng)說(shuō)過(guò)：所有一致性協(xié)議本質(zhì)上要么是Paxos要么是其變體。

網(wǎng)上有很多講解Paxos算法的文章，但是質(zhì)量層次不齊。今天筆者帶大家深入聊一下Paxos

Paxos是什么？Paxos算法是基于消息傳遞且具有高度容錯(cuò)特性的一致性算法，是目前公認(rèn)的解決分布式一致性問(wèn)題最有效的算法之一。Paxos算法是Lamport宗師提出的一種基于消息傳遞的分布式一致性算法，使其獲得2013年圖靈獎(jiǎng)。自Paxos問(wèn)世以來(lái)就持續(xù)壟斷了分布式一致性算法，Paxos這個(gè)名詞幾乎等同于分布式一致性。Google的很多大型分布式系統(tǒng)都采用了Paxos算法來(lái)解決分布式一致性問(wèn)題，如Chubby、Megastore以及Spanner等。開(kāi)源的ZooKeeper，以及MySQL 5.7推出的用來(lái)取代傳統(tǒng)的主從復(fù)制的MySQL Group Replication等紛紛采用Paxos算法解決分布式一致性問(wèn)題。但是它也有兩個(gè)明顯的缺點(diǎn)：

難以理解

在工程是實(shí)現(xiàn)上比較復(fù)雜。

問(wèn)題產(chǎn)生的背景在常見(jiàn)的分布式系統(tǒng)中，總會(huì)發(fā)生諸如機(jī)器宕機(jī)或網(wǎng)絡(luò)異常（包括消息的延遲、丟失、重復(fù)、亂序，還有網(wǎng)絡(luò)分區(qū)）等情況。Paxos算法需要解決的問(wèn)題就是如何在一個(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)過(guò)程中，并不是一個(gè)進(jìn)程只能擔(dān)任其中一種角色，它有可能會(huì)同時(shí)充當(dāng)多個(gè)。比如一個(gè)進(jìn)程既是Proposer又是Acceptor還是Learner。還有一個(gè)很重要的概念叫提案（Proposal）。最終要達(dá)成一致的value就在提案里。這個(gè)提案包括什么呢？是僅僅包括一個(gè)信息數(shù)值嗎？到底是如何咱們繼續(xù)向下閱讀，目前咱們先認(rèn)為僅僅是一個(gè)普普通通的value。

初次認(rèn)識(shí)

Paxos算法過(guò)程和我國(guó)的立法過(guò)程是極其相似的（法律案的提出、法律案的審議、法律案的表決、法律的公布四個(gè)階段），所謂的提案就是新頒布法律。Proposer （提案者）可以提出（propose）提案；Accoptor可以接受（accept）提案；如果某個(gè)提案被選定（chosen），那么該提案里的value就被選定了。

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

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

Acceptor：只要Acceptor接受了某個(gè)提案，Acceptor就認(rèn)為該提案里的value被選定了。

Learner：作為一個(gè)學(xué)習(xí)者，Acceptor告訴Learner哪個(gè)value被選定，Learner就認(rèn)為那個(gè)value被選定。

問(wèn)題描述假設(shè)有一組可以提出（propose）value的進(jìn)程集合（提案者團(tuán)隊(duì)），一個(gè)一致性算法需要保證提出的這么多value中，僅僅只有一個(gè)相同的value被選定（chosen）。也就是說(shuō)要么沒(méi)有value被提出，只要提出了value并且被選定，那么大家最終學(xué)習(xí)到的value必須是一致的。對(duì)于一致性算法，安全性（safaty）要求如下：

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

只有一個(gè)value被選定。

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

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

俗話說(shuō)的好，哪里有需求，哪里就會(huì)出現(xiàn)糟糕的問(wèn)題。如果假設(shè)不同角色之間可以通過(guò)發(fā)送消息來(lái)進(jìn)行通信，那么：

每個(gè)角色以各自任意的速度進(jìn)行通信執(zhí)行，在這個(gè)過(guò)程中可能會(huì)因?yàn)楦鞣N原因出錯(cuò)而導(dǎo)致執(zhí)行停止或重啟。當(dāng)一個(gè)value被選定之后，因?yàn)楣收显虿呕謴?fù)正常的角色因?yàn)槭チ四承┲匾男畔ⅲ瑢?dǎo)致它們無(wú)法確定被選定的值。

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

以上都是可能會(huì)遇到的問(wèn)題，要怎么解決？？？

推導(dǎo)過(guò)程最簡(jiǎn)單的方案——只有一個(gè)Acceptor

假設(shè)只有一個(gè)Acceptor（可以有多個(gè)Proposer），只要Acceptor接受它收到的第一個(gè)提案，則該提案被選定，該提案里的value就是被選定的value。這樣就保證只有一個(gè)value會(huì)被選定。但是，如果這個(gè)唯一的Acceptor宕機(jī)了，那么整個(gè)系統(tǒng)就無(wú)法工作了！因此，一個(gè)Acceptor是不可行的，必須要有多個(gè)Acceptor！

多個(gè)Acceptor

當(dāng)有多個(gè)Acceptor的時(shí)候，如何保證在多個(gè)Proposer和多個(gè)Acceptor的情況下選定一個(gè)value呢？大家可以自己先進(jìn)行思考。首先，我們的最終目標(biāo)是無(wú)論有多少Proposer提出提案，有且僅有一個(gè)value被選定。那么，我們可以先定義一個(gè)約束：

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

但是，這樣又會(huì)出現(xiàn)其它的問(wèn)題：如果每個(gè)Proposer所提出的提案value是不同的，并且將提案發(fā)送給不同的Acceptor。根據(jù)P1約束，每個(gè)Acceptor都接受它收到的第一個(gè)提案，就會(huì)出現(xiàn)不同value被選定的情況，出現(xiàn)了不一致。

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

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

一個(gè)提案被半數(shù)以上接受，說(shuō)明『一個(gè)Acceptor必須能夠接受不止一個(gè)提案！』，不然可能導(dǎo)致最終沒(méi)有value被選定。比如上圖的情況。v1、v2、v3都沒(méi)有被選定，因?yàn)樗鼈兌贾槐灰粋€(gè)Acceptor的接受，并沒(méi)有被超過(guò)半數(shù)以上的Acceptor接受。最開(kāi)始將【提案 = value】已經(jīng)無(wú)法滿足現(xiàn)在的需求，因?yàn)楫?dāng)一個(gè)Proposer發(fā)送多個(gè)提案到一個(gè)Acceptor的時(shí)候，需要使用一個(gè)編號(hào)來(lái)區(qū)分被提出的順序?，F(xiàn)在【提案=提案編號(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。但是，考慮如下的情況：以立法過(guò)程為背景，假設(shè)總的有5個(gè)人大代表（Acceptor）。人民法院（Proposer2）提出［M1，V1］的提案，人大代表2-5號(hào)（半數(shù)以上）均接受了該提案，于是對(duì)于人大代表2-5號(hào)和人民法院來(lái)講，它們都認(rèn)為V1提案是被選定的。此時(shí)，人大代表1在辦完其它事務(wù)之后也參與到其中（之前人大代表1沒(méi)有收到過(guò)任何提案），此時(shí)最高人民檢察院（另一個(gè)提案者Proposer1）向人大代表1發(fā)送了［M2，V2］的提案（V2≠V1且M2》M1），對(duì)于人大代表1來(lái)講，這是它收到的第一個(gè)提案。根據(jù)P1（一個(gè)Acceptor必須接受它收到的第一個(gè)提案。），人大代表1必須接受該提案！同時(shí)人大代表1認(rèn)為V2被選定。這就出現(xiàn)了兩個(gè)問(wèn)題：

人大代表1認(rèn)為V2被選定，人大代表2-5和人民法院認(rèn)為V1被選定。出現(xiàn)了不一致。

V1被選定了，但是編號(hào)更高的被人大代表1接受的提案［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提出來(lái)的，所有我們可以對(duì)Proposer提出的提案進(jìn)行約束。得到P2b：

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

那么，如何確保在某個(gè)value為v的提案被選定后，Proposer提出的編號(hào)更高的提案的value都是v呢？只要滿足P2c即可：

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

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

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

Proposer生成提案

為了滿足P2b，這里有個(gè)比較重要的思想：Proposer生成提案之前，應(yīng)該先去『學(xué)習(xí)』已經(jīng)被選定或者可能被選定的value，然后以該value作為自己提出的提案的value。如果沒(méi)有value被選定，Proposer才可以自己決定value的值。這樣才能達(dá)成一致。這個(gè)學(xué)習(xí)的階段是通過(guò)一個(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)接受過(guò)提案，那么就向Proposer響應(yīng)已經(jīng)接受過(guò)的編號(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)中都沒(méi)有提案，那 么此時(shí)V就可以由Proposer自己選擇（一般為當(dāng)前提案）。

生成提案后，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)過(guò)任何編號(hào)大于N的Prepare請(qǐng)求，那么他就可以接受這個(gè)編號(hào)為N的提案。

如果Acceptor收到一個(gè)編號(hào)為N的Prepare請(qǐng)求，在此之前它已經(jīng)響應(yīng)過(guò)編號(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只需記?。?. 已接受的編號(hào)最大的提案 2. 已響應(yīng)的請(qǐng)求的最大編號(hào)。

Paxos算法描述

經(jīng)過(guò)上面的推導(dǎo)，我們總結(jié)下Paxos算法的流程。Paxos算法分為兩個(gè)階段。具體如下：1.階段一：

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

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

2.階段二：

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

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

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

方案一

Acceptor接受到一個(gè)提案，就將該提案發(fā)送給所有Learners.

優(yōu)點(diǎn)：Learner能夠快速獲取被選定的value

缺點(diǎn)：通信次數(shù)為M*N（M為提案數(shù)，N為L(zhǎng)earner數(shù)）

方案二

Acceptor接受一個(gè)提案，就將提案發(fā)送給主Learner，主Learner再通知其它Learner

優(yōu)點(diǎn)：通信次數(shù)減少（M+N-1）（M為提案數(shù)，N為L(zhǎng)earner數(shù)，M個(gè)提案發(fā)送給主Learner，然后主Learner通知N-1個(gè)Learner）

缺點(diǎn)：?jiǎn)吸c(diǎn)故障問(wèn)題（主Learner可能出現(xiàn)故障）

方案三

Acceptor接受一個(gè)提案，就將提案發(fā)送給Learner團(tuán)，Learner團(tuán)再通知其它Learner

優(yōu)點(diǎn)：解決了方案二單點(diǎn)故障問(wèn)題，可靠性好

缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，網(wǎng)絡(luò)通信復(fù)雜度高

如何保證Paxos算法的活性通過(guò)選取主Proposer，就可以保證Paxos算法的活性。通過(guò)選取主Proposer，并規(guī)定只有主Proposer才能提出議案。這樣一來(lái)只要主Proposer和過(guò)半的Acceptor能夠正常進(jìn)行網(wǎng)絡(luò)通信，那么但凡主Proposer提出一個(gè)編號(hào)更高的提案，該提案終將會(huì)被批準(zhǔn)，這樣通過(guò)選擇一個(gè)主Proposer，整套Paxos算法就能夠保持活性。至此，我們得到一個(gè)既能保證安全性，又能保證活性的分布式一致性算法——Paxos算法。

總結(jié)到此，我們針對(duì)Paxos算法是什么、它的特性以及算法的具體推導(dǎo)過(guò)程做了詳細(xì)的闡述。Paxos算法是現(xiàn)在很多一致性算法的變體，非常值得我們學(xué)習(xí)~

原文標(biāo)題：聊聊分布式一致性算法協(xié)議 Paxos

文章出處：【微信公眾號(hào)：馬哥Linux運(yùn)維】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。