Paxos協(xié)議/算法是分布式系統(tǒng)中比較重要的協(xié)議，它有多重要呢？
<分布式系統(tǒng)的事務(wù)處理>：
Google Chubby的作者M(jìn)ike Burrows說過這個(gè)世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。
<大規(guī)模分布式存儲系統(tǒng)>：
理解了這兩個(gè)分布式協(xié)議之后(Paxos/2PC)，學(xué)習(xí)其他分布式協(xié)議會變得相當(dāng)容易。
學(xué)習(xí)Paxos算法有兩部分：a) 算法的原理/證明；b) 算法的理解/運(yùn)作。
理解這個(gè)算法的運(yùn)作過程其實(shí)基本就可以用于工程實(shí)踐。而且理解這個(gè)過程相對來說也容易得多。
網(wǎng)上我覺得講Paxos講的好的屬于這篇：paxos圖解及Paxos算法詳解，我這里就結(jié)合wiki上的實(shí)例進(jìn)一步闡述。一些paxos基礎(chǔ)通過這里提到的兩篇文章，以及wiki上的內(nèi)容基本可以理解。
算法內(nèi)容
Paxos在原作者的《Paxos Made Simple》中內(nèi)容是比較精簡的：
Phase 1
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.
Phase 2
(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
借用paxos圖解文中的流程圖可概括為：
實(shí)例及詳解
Paxos中有三類角色Proposer、Acceptor及Learner，主要交互過程在Proposer和Acceptor之間。
Proposer與Acceptor之間的交互主要有4類消息通信，如下圖：
這4類消息對應(yīng)于paxos算法的兩個(gè)階段4個(gè)過程：
- phase 1
- a) proposer向網(wǎng)絡(luò)內(nèi)超過半數(shù)的acceptor發(fā)送prepare消息
- b) acceptor正常情況下回復(fù)promise消息
- phase 2
- a) 在有足夠多acceptor回復(fù)promise消息時(shí)，proposer發(fā)送accept消息
- b) 正常情況下acceptor回復(fù)accepted消息
因?yàn)樵谡麄€(gè)過程中可能有其他proposer針對同一件事情發(fā)出以上請求，所以在每個(gè)過程中都會有些特殊情況處理，這也是為了達(dá)成一致性所做的事情。如果在整個(gè)過程中沒有其他proposer來競爭，那么這個(gè)操作的結(jié)果就是確定無異議的。但是如果有其他proposer的話，情況就不一樣了。
以paxos中文wiki上的例子為例。簡單來說該例子以若干個(gè)議員提議稅收，確定最終通過的法案稅收比例。
以下圖中基本只畫出proposer與一個(gè)acceptor的交互。時(shí)間標(biāo)志T2總是在T1后面。propose number簡稱N。
情況之一如下圖：
A3在T1發(fā)出accepted給A1，然后在T2收到A5的prepare，在T3的時(shí)候A1才通知A5最終結(jié)果(稅率10%)。這里會有兩種情況：
- A5發(fā)來的N5小于A1發(fā)出去的N1，那么A3直接拒絕(reject)A5
- A5發(fā)來的N5大于A1發(fā)出去的N1，那么A3回復(fù)promise，但帶上A1的(N1, 10%)
這里可以與paxos流程圖對應(yīng)起來，更好理解。acceptor會記錄(MaxN, AcceptN, AcceptV)。
A5在收到promise后，后續(xù)的流程可以順利進(jìn)行。但是發(fā)出accept時(shí)，因?yàn)槭盏搅?AcceptN, AcceptV)，所以會取最大的AcceptN對應(yīng)的AcceptV，例子中也就是A1的10%作為AcceptV。如果在收到promise時(shí)沒有發(fā)現(xiàn)有其他已記錄的AcceptV，則其值可以由自己決定。
針對以上A1和A5沖突的情況，最終A1和A5都會廣播接受的值為10%。
其實(shí)4個(gè)過程中對于acceptor而言，在回復(fù)promise和accepted時(shí)由于都可能因?yàn)槠渌鹥roposer的介入而導(dǎo)致特殊處理。所以基本上看在這兩個(gè)時(shí)間點(diǎn)收到其他proposer的請求時(shí)就可以了解整個(gè)算法了。例如在回復(fù)promise時(shí)則可能因?yàn)閜roposer發(fā)來的N不夠大而reject：
如果在發(fā)accepted消息時(shí)，對其他更大N的proposer發(fā)出過promise，那么也會reject該proposer發(fā)出的accept，如圖：
這個(gè)對應(yīng)于Phase 2 b)：
it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
總結(jié)
Leslie Lamport沒有用數(shù)學(xué)描述Paxos，但是他用英文闡述得很清晰。將Paxos的兩個(gè)Phase的內(nèi)容理解清楚，整個(gè)算法過程還是不復(fù)雜的。
至于Paxos中一直提到的一個(gè)全局唯一且遞增的proposer number，其如何實(shí)現(xiàn)，引用如下：
如何產(chǎn)生唯一的編號呢？在《Paxos made simple》中提到的是讓所有的Proposer都從不相交的數(shù)據(jù)集合中進(jìn)行選擇，例如系統(tǒng)有5個(gè)Proposer，則可為每一個(gè)Proposer分配一個(gè)標(biāo)識j(0~4)，則每一個(gè)proposer每次提出決議的編號可以為5*i + j(i可以用來表示提出議案的次數(shù))
參考文檔