深入淺出理解Paxos算法

Paxos算法是萊斯利·蘭伯特（英語：Leslie Lamport，LaTeX中的「La」）于1990年提出的一種基于消息傳遞且具有高度容錯(cuò)特性的一致性算法。

Paxos算法一開始非常難以理解，但是一旦理解其實(shí)也并不難，之所以難理解其實(shí)是因?yàn)樽髡咧v的故事難理解。

Paxos算法維基百科https://en.wikipedia.org/wiki/Paxos_(computer_science)

網(wǎng)上有2篇帖子是講的非常好的，

分別是：以兩軍問題為背景來演繹Basic Paxos和Paxos算法細(xì)節(jié)詳解(一)--通過現(xiàn)實(shí)世界描述算法

本人是在看了這2個(gè)帖子之后再結(jié)合原論文才看懂的。

Paxos一共4個(gè)角色：Client ? Proposer ? ? ?Acceptor ? ? Learner。

Client：產(chǎn)生議題者
Proposer ：提議者
Acceptor：決策者
Learner：最終決策學(xué)習(xí)者，也就是執(zhí)行者。

Proposer拿著Client的議題去向Acceptor提議，讓Acceptor來決策。
Proposer提出議題，Acceptor初步接受或者Acceptor初步不接受。
Acceptor初步接受則Proposer再次向Acceptor確認(rèn)是否最終接受。
Acceptor最終接受或者Acceptor最終不接受。

Learner最終學(xué)習(xí)的目標(biāo)是向所有Acceptor學(xué)習(xí)，如果有多數(shù)派個(gè)Acceptor最終接受了某提議，那就得到了最終的結(jié)果，算法的目的就達(dá)到了。

最基本的Message flow: Basic Paxos演示圖如下圖所示，其他情況可以參考百科。

圖解：

A1，,A2和A3就是Acceptor。

P1，p2和p3就是Proposer。淺色的P1和P2說明是進(jìn)行提議，深色的P1和P2說明是拿到表決。

圓圈123表明是每次提議序號，遞增即可。黑色的圖表示被黑了，也就是否決。方塊表示投票結(jié)果，綠方塊表示投票通過，紅色菱形表示最終的投票結(jié)果。

整個(gè)事件是按照時(shí)間線從左到右發(fā)展。

事件發(fā)展：

第一個(gè)框代表第一階段--提議

1.p2最先找到A2，P2提議序號是2，A2記錄下，因?yàn)橹皼]有其他的序號所以成功了，然后返回標(biāo)志給p2;

2.p1找到A1，P1提議序號是1，A1記錄下，因?yàn)橹皼]有其他的序號所以成功了，然后返回標(biāo)志給p1;

3.p1找到A3，P1提議序號是1，A3記錄下，因?yàn)橹皼]有其他的序號所以成功了，然后返回標(biāo)志給p1;

問題來了

4.p1找到A2，P1提議序號是1，A2已經(jīng)記錄下提議序號2，2>1，所以不成功;

5.p2找到A1，P2提議序號是2，A1已經(jīng)記錄下提議序號1，1>2，所以成功;，然后返回標(biāo)志給p2;

6.p2找到A3，P2提議序號是2，A3已經(jīng)記錄下提議序號1，1>2，所以成功;，然后返回標(biāo)志給p2;

第二個(gè)框代表第二階段--確認(rèn)提議（投票）

7.p1找到A1，P1確認(rèn)序號是1，A1已經(jīng)記錄下提議序號2，1<2，所以不確認(rèn)，然后p1繼續(xù)提議序號是3，周而復(fù)始...;

8.p2找到A2，P2確認(rèn)序號是2，A2已經(jīng)記錄下提議序號2，2=2，所以確認(rèn)成功;，然后返回投票標(biāo)志給p2;

9.p2找到A3，P2確認(rèn)序號是2，A3已經(jīng)記錄下提議序號2，2=2，所以確認(rèn)成功;，然后返回投票標(biāo)志給p2;

10.p2找到A1，P2確認(rèn)序號是2，A1已經(jīng)記錄下提議序號3，2<3，所以不確認(rèn)，;然后p2繼續(xù)提議序號是4，周而復(fù)始...;
問題來了

11.p1找到A2，P1確認(rèn)序號是1，A1已經(jīng)記錄下確認(rèn)序號2，1<2，所以不確認(rèn)，然后返回確認(rèn)序號2;

12.p1找到A3，P1確認(rèn)序號是1，A3已經(jīng)記錄下確認(rèn)序號2，1<2，所以不確認(rèn)，然后返回確認(rèn)序號2;

13.p1和p2都得到確認(rèn)也就是投票結(jié)果是2。

14.所有的Learner最終學(xué)習(xí)的目標(biāo)是2。

Paxos過程結(jié)束了，這樣，一致性得到了保證，算法運(yùn)行到最后所有的proposer都投“2”所有的acceptor都接受這個(gè)議題，也就是說在最初的第二階段，議題是先入為主的，誰先占了先機(jī)，后面的proposer在第一階段就會學(xué)習(xí)到這個(gè)議題而修改自己本身的議題，才能讓一致性得到保證，這就是paxos算法的一個(gè)過程。該算法就是為了追求結(jié)果的一致性。