轉(zhuǎn)載于https://zhuanlan.zhihu.com/p/31780743

一蒿辙、Paxos算法背景

Paxos算法是Lamport宗師提出的一種基于消息傳遞的分布式一致性算法沼琉，使其獲得2013年圖靈獎(jiǎng)蜈亩。

Paxos由Lamport于1998年在《The Part-Time Parliament》論文中首次公開(kāi)闹啦，最初的描述使用希臘的一個(gè)小島Paxos作為比喻颤难，描述了Paxos小島中通過(guò)決議的流程成肘，并以此命名這個(gè)算法豺裆，但是這個(gè)描述理解起來(lái)比較有挑戰(zhàn)性。后來(lái)在2001年考榨，Lamport覺(jué)得同行不能理解他的幽默感跨细，于是重新發(fā)表了樸實(shí)的算法描述版本《Paxos Made Simple》。

自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)題。

然而溃槐，Paxos的最大特點(diǎn)就是難匣砖，不僅難以理解科吭，更難以實(shí)現(xiàn)昏滴。

二、Paxos算法流程

Paxos算法解決的問(wèn)題正是分布式一致性問(wèn)題对人，即一個(gè)分布式系統(tǒng)中的各個(gè)進(jìn)程如何就某個(gè)值（決議）達(dá)成一致谣殊。

Paxos算法運(yùn)行在允許宕機(jī)故障的異步系統(tǒng)中，不要求可靠的消息傳遞牺弄，可容忍消息丟失姻几、延遲、亂序以及重復(fù)势告。它利用大多數(shù) (Majority) 機(jī)制保證了2F+1的容錯(cuò)能力蛇捌，即2F+1個(gè)節(jié)點(diǎn)的系統(tǒng)最多允許F個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)故障。

一個(gè)或多個(gè)提議進(jìn)程 (Proposer) 可以發(fā)起提案 (Proposal)咱台，Paxos算法使所有提案中的某一個(gè)提案络拌，在所有進(jìn)程中達(dá)成一致。系統(tǒng)中的多數(shù)派同時(shí)認(rèn)可該提案回溺，即達(dá)成了一致春贸。最多只針對(duì)一個(gè)確定的提案達(dá)成一致。

2.1 Paxos算法角色

Paxos將系統(tǒng)中的角色分為提議者 (Proposer)遗遵，決策者 (Acceptor)萍恕，和最終決策學(xué)習(xí)者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案編號(hào) (Proposal ID) 和提議的值 (Value)车要。
• Acceptor：參與決策允粤，回應(yīng)Proposers的提案。收到Proposal后可以接受提案翼岁，若Proposal獲得多數(shù)Acceptors的接受类垫，則稱該P(yáng)roposal被批準(zhǔn)。
• Learner：不參與決策登澜，從Proposers/Acceptors學(xué)習(xí)最新達(dá)成一致的提案（Value）阔挠。

在多副本狀態(tài)機(jī)中，每個(gè)副本同時(shí)具有Proposer脑蠕、Acceptor购撼、Learner三種角色跪削。

Paxos算法通過(guò)一個(gè)決議分為兩個(gè)階段（Learn階段之前決議已經(jīng)形成）：

1. 第一階段：Prepare階段。Proposer向Acceptors發(fā)出Prepare請(qǐng)求迂求，Acceptors針對(duì)收到的Prepare請(qǐng)求進(jìn)行Promise承諾碾盐。
2. 第二階段：Accept階段。Proposer收到多數(shù)Acceptors承諾的Promise后揩局，向Acceptors發(fā)出Propose請(qǐng)求毫玖，Acceptors針對(duì)收到的Propose請(qǐng)求進(jìn)行Accept處理。
3. 第三階段：Learn階段凌盯。Proposer在收到多數(shù)Acceptors的Accept之后付枫，標(biāo)志著本次Accept成功，決議形成驰怎，將形成的決議發(fā)送給所有Learners阐滩。

2.2 Paxos算法流程

Paxos算法流程中的每條消息描述如下：

• Prepare: Proposer生成全局唯一且遞增的Proposal ID (可使用時(shí)間戳加Server ID)，向所有Acceptors發(fā)送Prepare請(qǐng)求县忌，這里無(wú)需攜帶提案內(nèi)容掂榔，只攜帶Proposal ID即可。
• Promise: Acceptors收到Prepare請(qǐng)求后症杏，做出“兩個(gè)承諾装获，一個(gè)應(yīng)答”。

兩個(gè)承諾：

1. 不再接受Proposal ID小于等于（注意：這里是<= ）當(dāng)前請(qǐng)求的Prepare請(qǐng)求厉颤。

2. 不再接受Proposal ID小于（注意：這里是< ）當(dāng)前請(qǐng)求的Propose請(qǐng)求穴豫。

一個(gè)應(yīng)答：

不違背以前作出的承諾下，回復(fù)已經(jīng)Accept過(guò)的提案中Proposal ID最大的那個(gè)提案的Value和Proposal ID走芋，沒(méi)有則返回空值绩郎。

• Propose: Proposer 收到多數(shù)Acceptors的Promise應(yīng)答后，從應(yīng)答中選擇Proposal ID最大的提案的Value翁逞，作為本次要發(fā)起的提案肋杖。如果所有應(yīng)答的提案Value均為空值，則可以自己隨意決定提案Value挖函。然后攜帶當(dāng)前Proposal ID状植，向所有Acceptors發(fā)送Propose請(qǐng)求。
• Accept: Acceptor收到Propose請(qǐng)求后怨喘，在不違背自己之前作出的承諾下津畸，接受并持久化當(dāng)前Proposal ID和提案Value。
• Learn: Proposer收到多數(shù)Acceptors的Accept后必怜，決議形成肉拓，將形成的決議發(fā)送給所有Learners。

Paxos算法偽代碼描述如下：

2.3 Paxos算法偽代碼

1. 獲取一個(gè)Proposal ID n梳庆，為了保證Proposal ID唯一暖途，可采用時(shí)間戳+Server ID生成卑惜；
2. Proposer向所有Acceptors廣播Prepare(n)請(qǐng)求；
3. Acceptor比較n和minProposal驻售，如果n>minProposal露久，minProposal=n，并且將 acceptedProposal 和 acceptedValue 返回欺栗；
4. Proposer接收到過(guò)半數(shù)回復(fù)后毫痕，如果發(fā)現(xiàn)有acceptedValue返回，將所有回復(fù)中acceptedProposal最大的acceptedValue作為本次提案的value迟几，否則可以任意決定本次提案的value消请；
5. 到這里可以進(jìn)入第二階段，廣播Accept (n,value) 到所有節(jié)點(diǎn)瘤旨；
6. Acceptor比較n和minProposal梯啤，如果n>=minProposal，則acceptedProposal=minProposal=n存哲，acceptedValue=value，本地持久化后七婴，返回祟偷；否則，返回minProposal打厘。
7. 提議者接收到過(guò)半數(shù)請(qǐng)求后修肠，如果發(fā)現(xiàn)有返回值result >n，表示有更新的提議户盯，跳轉(zhuǎn)到1嵌施；否則value達(dá)成一致。

下面舉幾個(gè)例子莽鸭，實(shí)例1如下圖：

2.4 Paxos算法實(shí)例1

圖中P代表Prepare階段吗伤，A代表Accept階段。3.1代表Proposal ID為3.1硫眨，其中3為時(shí)間戳足淆，1為Server ID。X和Y代表提議Value礁阁。

實(shí)例1中P 3.1達(dá)成多數(shù)派巧号，其Value(X)被Accept，然后P 4.5學(xué)習(xí)到Value(X)姥闭，并Accept丹鸿。

2.5 Paxos算法實(shí)例2

實(shí)例2中P 3.1沒(méi)有被多數(shù)派Accept（只有S3 Accept），但是被P 4.5學(xué)習(xí)到棚品，P 4.5將自己的Value由Y替換為X靠欢，Accept（X）弥姻。

2.6 Paxos算法實(shí)例3

實(shí)例3中P 3.1沒(méi)有被多數(shù)派Accept（只有S1 Accept），同時(shí)也沒(méi)有被P 4.5學(xué)習(xí)到掺涛。由于P 4.5 Propose的所有應(yīng)答庭敦，均未返回Value，則P 4.5可以Accept自己的Value (Y)薪缆。后續(xù)P 3.1的Accept (X) 會(huì)失敗秧廉，已經(jīng)Accept的S1，會(huì)被覆蓋拣帽。

Paxos算法可能形成活鎖而永遠(yuǎn)不會(huì)結(jié)束疼电，如下圖實(shí)例所示：

2.7 Paxos算法形成活鎖

回顧兩個(gè)承諾之一，Acceptor不再應(yīng)答Proposal ID小于等于當(dāng)前請(qǐng)求的Prepare請(qǐng)求减拭。意味著需要應(yīng)答Proposal ID大于當(dāng)前請(qǐng)求的Prepare請(qǐng)求蔽豺。

兩個(gè)Proposers交替Prepare成功，而Accept失敗拧粪，形成活鎖（Livelock）修陡。

三、Multi-Paxos算法

原始的Paxos算法（Basic Paxos）只能對(duì)一個(gè)值形成決議可霎，決議的形成至少需要兩次網(wǎng)絡(luò)來(lái)回魄鸦，在高并發(fā)情況下可能需要更多的網(wǎng)絡(luò)來(lái)回，極端情況下甚至可能形成活鎖癣朗。如果想連續(xù)確定多個(gè)值拾因，Basic Paxos搞不定了。因此Basic Paxos幾乎只是用來(lái)做理論研究旷余，并不直接應(yīng)用在實(shí)際工程中绢记。

實(shí)際應(yīng)用中幾乎都需要連續(xù)確定多個(gè)值，而且希望能有更高的效率正卧。Multi-Paxos正是為解決此問(wèn)題而提出蠢熄。Multi-Paxos基于Basic Paxos做了兩點(diǎn)改進(jìn)：

1. 針對(duì)每一個(gè)要確定的值，運(yùn)行一次Paxos算法實(shí)例（Instance）穗酥，形成決議护赊。每一個(gè)Paxos實(shí)例使用唯一的Instance ID標(biāo)識(shí)。
2. 在所有Proposers中選舉一個(gè)Leader砾跃，由Leader唯一地提交Proposal給Acceptors進(jìn)行表決骏啰。這樣沒(méi)有Proposer競(jìng)爭(zhēng)，解決了活鎖問(wèn)題抽高。在系統(tǒng)中僅有一個(gè)Leader進(jìn)行Value提交的情況下判耕，Prepare階段就可以跳過(guò)，從而將兩階段變?yōu)橐浑A段翘骂，提高效率壁熄。

3.1 Multi-Paxos流程

Multi-Paxos首先需要選舉Leader帚豪，Leader的確定也是一次決議的形成，所以可執(zhí)行一次Basic Paxos實(shí)例來(lái)選舉出一個(gè)Leader草丧。選出Leader之后只能由Leader提交Proposal狸臣，在Leader宕機(jī)之后服務(wù)臨時(shí)不可用，需要重新選舉Leader繼續(xù)服務(wù)昌执。在系統(tǒng)中僅有一個(gè)Leader進(jìn)行Proposal提交的情況下烛亦，Prepare階段可以跳過(guò)。

Multi-Paxos通過(guò)改變Prepare階段的作用范圍至后面Leader提交的所有實(shí)例懂拾，從而使得Leader的連續(xù)提交只需要執(zhí)行一次Prepare階段煤禽，后續(xù)只需要執(zhí)行Accept階段，將兩階段變?yōu)橐浑A段岖赋，提高了效率檬果。為了區(qū)分連續(xù)提交的多個(gè)實(shí)例，每個(gè)實(shí)例使用一個(gè)Instance ID標(biāo)識(shí)唐断，Instance ID由Leader本地遞增生成即可选脊。

Multi-Paxos允許有多個(gè)自認(rèn)為是Leader的節(jié)點(diǎn)并發(fā)提交Proposal而不影響其安全性，這樣的場(chǎng)景即退化為Basic Paxos栗涂。

Chubby和Boxwood均使用Multi-Paxos知牌。ZooKeeper使用的Zab也是Multi-Paxos的變形。

附Paxos算法推導(dǎo)過(guò)程

Paxos算法的設(shè)計(jì)過(guò)程就是從正確性開(kāi)始的斤程，對(duì)于分布式一致性問(wèn)題，很多進(jìn)程提出（Propose）不同的值菩混，共識(shí)算法保證最終只有其中一個(gè)值被選定忿墅，Safety表述如下：

• 只有被提出（Propose）的值才可能被最終選定（Chosen）。
• 只有一個(gè)值會(huì)被選定（Chosen）沮峡。
• 進(jìn)程只會(huì)獲知到已經(jīng)確認(rèn)被選定（Chosen）的值疚脐。

Paxos以這幾條約束作為出發(fā)點(diǎn)進(jìn)行設(shè)計(jì)，只要算法最終滿足這幾點(diǎn)邢疙，正確性就不需要證明了棍弄。Paxos算法中共分為三種參與者：Proposer、Acceptor以及Learner疟游，通常實(shí)現(xiàn)中每個(gè)進(jìn)程都同時(shí)扮演這三個(gè)角色呼畸。

Proposers向Acceptors提出Proposal，為了保證最多只有一個(gè)值被選定（Chosen）颁虐，Proposal必須被超過(guò)一半的Acceptors所接受（Accept）蛮原，且每個(gè)Acceptor只能接受一個(gè)值。

為了保證正常運(yùn)行（必須有值被接受）另绩，所以Paxos算法中：

P1：Acceptor必須接受（Accept）它所收到的第一個(gè)Proposal儒陨。

先來(lái)先服務(wù)花嘶，合情合理。但這樣產(chǎn)生一個(gè)問(wèn)題蹦漠，如果多個(gè)Proposers同時(shí)提出Proposal椭员，很可能會(huì)導(dǎo)致無(wú)法達(dá)成一致，因?yàn)闆](méi)有Propopal被超過(guò)一半Acceptors的接受笛园，因此隘击，Acceptor必須能夠接受多個(gè)Proposal，不同的Proposal由不同的編號(hào)進(jìn)行區(qū)分喘沿，當(dāng)某個(gè)Proposal被超過(guò)一半的Acceptors接受后闸度，這個(gè)Proposal就被選定了。

既然允許Acceptors接受多個(gè)Proposal就有可能出現(xiàn)多個(gè)不同值都被最終選定的情況蚜印，這違背了Safety要求莺禁，為了保證Safety要求，Paxos進(jìn)一步提出：

P2：如果值為v的Proposal被選定（Chosen）窄赋，則任何被選定（Chosen）的具有更高編號(hào)的Proposal值也一定為v哟冬。

只要算法同時(shí)滿足P1和P2，就保證了Safety忆绰。P2是一個(gè)比較寬泛的約定浩峡，完全沒(méi)有算法細(xì)節(jié)，我們對(duì)其進(jìn)一步延伸：

P2a：如果值為v的Proposal被選定（Chosen）错敢，則對(duì)所有的Acceptors翰灾，它們接受（Accept）的任何具有更高編號(hào)的Proposal值也一定為v。

如果滿足P2a則一定滿足P2稚茅，顯然纸淮，因?yàn)橹挥惺紫缺唤邮懿庞锌赡鼙蛔罱K選定。但是P2a依然難以實(shí)現(xiàn)亚享，因?yàn)閍cceptor很有可能并不知道之前被選定的Proposal（恰好不在接受它的多數(shù)派中）咽块，因此進(jìn)一步延伸：

P2b：如果值為v的Proposal被選定（Chosen），則對(duì)所有的Proposer欺税，它們提出的的任何具有更高編號(hào)的Proposal值也一定為v侈沪。

更進(jìn)一步的：

P2c：為了提出值為v且編號(hào)為n的Proposal，必須存在一個(gè)包含超過(guò)一半Acceptors的集合S晚凿，滿足(1) 沒(méi)有任何S中的Acceptors曾經(jīng)接受（Accept）過(guò)編號(hào)比n小的Proposal亭罪，或者(2) v和S中的Acceptors所接受過(guò)(Accept)的編號(hào)最大且小于n的Proposal值一致。

滿足P2c即滿足P2b即滿足P2a即滿足P2晃虫。至此Paxos提出了Proposer的執(zhí)行流程皆撩，以滿足P2c：

1. Proposer選擇一個(gè)新的編號(hào)n，向超過(guò)一半的Acceptors發(fā)送請(qǐng)求消息，Acceptor回復(fù): (a)承諾不會(huì)接受編號(hào)比n小的proposal扛吞，以及(b)它所接受過(guò)的編號(hào)比n小的最大Proposal（如果有）呻惕。該請(qǐng)求稱為Prepare請(qǐng)求。
2. 如果Proposer收到超過(guò)一半Acceptors的回復(fù)滥比，它就可以提出Proposal亚脆，Proposal的值為收到回復(fù)中編號(hào)最大的Proposal的值，如果沒(méi)有這樣的值盲泛，則可以自由提出任何值濒持。
3. 向收到回復(fù)的Acceptors發(fā)送Accept請(qǐng)求，請(qǐng)求對(duì)方接受提出的Proposal寺滚。

仔細(xì)品味Proposer的執(zhí)行流程柑营，其完全吻合P2c中的要求，但你可能也發(fā)現(xiàn)了村视，當(dāng)多個(gè)Proposer同時(shí)運(yùn)行時(shí)官套，有可能出現(xiàn)沒(méi)有任何Proposal可以成功被接受的情況（編號(hào)遞增的交替完成第一步），這就是Paxos算法的Liveness問(wèn)題蚁孔，或者叫“活鎖”奶赔，論文中建議通過(guò)對(duì)Proposers引入選主算法選出Distinguished Proposer來(lái)全權(quán)負(fù)責(zé)提出Proposal來(lái)解決這個(gè)問(wèn)題，但是即使在出現(xiàn)多個(gè)Proposers同時(shí)提出Proposal的情況時(shí)杠氢，Paxos算法也可以保證Safety站刑。

接下來(lái)看看Acceptors的執(zhí)行過(guò)程，和我們對(duì)P2做的事情一樣鼻百，我們對(duì)P1進(jìn)行延伸：

P1a：Acceptor可以接受（Accept）編號(hào)為n的Proposal當(dāng)且僅當(dāng)它沒(méi)有回復(fù)過(guò)一個(gè)具有更大編號(hào)的Prepare消息绞旅。

易見(jiàn)，P1a包含了P1温艇，對(duì)于Acceptors：

1. 當(dāng)收到Prepare請(qǐng)求時(shí)玻靡，如果其編號(hào)n大于之前所收到的Prepare消息，則回復(fù)中贝。
2. 當(dāng)收到Accept請(qǐng)求時(shí)，僅當(dāng)它沒(méi)有回復(fù)過(guò)一個(gè)具有更大編號(hào)的Prepare消息臼朗，接受該P(yáng)roposal并回復(fù)邻寿。

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