深入淺出理解Paxos算法
Paxos算法是萊斯利·蘭伯特（英語：Leslie Lamport，LaTeX中的「La」）于1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法。
Paxos算法一開始非常難以理解，但是一旦理解其實也并不難，之所以難理解其實是因為作者講的故事難理解。
Paxos算法維基百科https://en.wikipedia.org/wiki/Paxos_(computer_science)
網(wǎng)上有2篇帖子是講的非常好的，
分別是：以兩軍問題為背景來演繹Basic Paxos和Paxos算法細節(jié)詳解(一)--通過現(xiàn)實世界描述算法
本人是在看了這2個帖子之后再結(jié)合原論文才看懂的。
Paxos一共4個角色：Client ? Proposer ? ? ?Acceptor ? ? Learner。
Client：產(chǎn)生議題者
Proposer ：提議者
Acceptor：決策者
Learner：最終決策學習者，也就是執(zhí)行者。
Proposer拿著Client的議題去向Acceptor提議，讓Acceptor來決策。
Proposer提出議題，Acceptor初步接受或者Acceptor初步不接受。
Acceptor初步接受則Proposer再次向Acceptor確認是否最終接受。
Acceptor最終接受或者Acceptor最終不接受。
Learner最終學習的目標是向所有Acceptor學習，如果有多數(shù)派個Acceptor最終接受了某提議，那就得到了最終的結(jié)果，算法的目的就達到了。
最基本的Message flow: Basic Paxos演示圖如下圖所示，其他情況可以參考百科。
圖解：
A1，,A2和A3就是Acceptor。
P1，p2和p3就是Proposer。淺色的P1和P2說明是進行提議，深色的P1和P2說明是拿到表決。
圓圈123表明是每次提議序號，遞增即可。黑色的圖表示被黑了，也就是否決。方塊表示投票結(jié)果，綠方塊表示投票通過，紅色菱形表示最終的投票結(jié)果。
整個事件是按照時間線從左到右發(fā)展。
事件發(fā)展：
第一個框代表第一階段--提議
1.p2最先找到A2，P2提議序號是2，A2記錄下，因為之前沒有其他的序號所以成功了，然后返回標志給p2;
2.p1找到A1，P1提議序號是1，A1記錄下，因為之前沒有其他的序號所以成功了，然后返回標志給p1;
3.p1找到A3，P1提議序號是1，A3記錄下，因為之前沒有其他的序號所以成功了，然后返回標志給p1;
問題來了
4.p1找到A2，P1提議序號是1，A2已經(jīng)記錄下提議序號2，2>1，所以不成功;
5.p2找到A1，P2提議序號是2，A1已經(jīng)記錄下提議序號1，1>2，所以成功;，然后返回標志給p2;
6.p2找到A3，P2提議序號是2，A3已經(jīng)記錄下提議序號1，1>2，所以成功;，然后返回標志給p2;
第二個框代表第二階段--確認提議（投票）
7.p1找到A1，P1確認序號是1，A1已經(jīng)記錄下提議序號2，1<2，所以不確認，然后p1繼續(xù)提議序號是3，周而復始...;
8.p2找到A2，P2確認序號是2，A2已經(jīng)記錄下提議序號2，2=2，所以確認成功;，然后返回投票標志給p2;
9.p2找到A3，P2確認序號是2，A3已經(jīng)記錄下提議序號2，2=2，所以確認成功;，然后返回投票標志給p2;
10.p2找到A1，P2確認序號是2，A1已經(jīng)記錄下提議序號3，2<3，所以不確認，;然后p2繼續(xù)提議序號是4，周而復始...;
問題來了
11.p1找到A2，P1確認序號是1，A1已經(jīng)記錄下確認序號2，1<2，所以不確認，然后返回確認序號2;
12.p1找到A3，P1確認序號是1，A3已經(jīng)記錄下確認序號2，1<2，所以不確認，然后返回確認序號2;
13.p1和p2都得到確認也就是投票結(jié)果是2。
14.所有的Learner最終學習的目標是2。
Paxos過程結(jié)束了，這樣，一致性得到了保證，算法運行到最后所有的proposer都投“2”所有的acceptor都接受這個議題，也就是說在最初的第二階段，議題是先入為主的，誰先占了先機，后面的proposer在第一階段就會學習到這個議題而修改自己本身的議題，才能讓一致性得到保證，這就是paxos算法的一個過程。該算法就是為了追求結(jié)果的一致性。
下載文檔
