http://www.cnblogs.com/endsock/p/3480093.html
最近研究paxos算法，看了許多相關(guān)的文章，概念還是很模糊，覺得還是沒有掌握paxos算法的精髓，所以花了3天時間分析了libpaxos3的所有代碼，此代碼可以從https://bitbucket.org/sciascid/libpaxos 下載。對paxos算法有初步了解之后，再看此文的效果會更好；如果你也想分析libpaxos3的話，此文應(yīng)該會對你有不小幫助；關(guān)于paxos的歷史這里不多做介紹，關(guān)于描述paxos算法寫的最好的一篇文章應(yīng)該就是維基百科了，地址戳這里：http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95
在paxos算法中，分為4種角色：
Proposer ：提議者
Acceptor：決策者
Client：產(chǎn)生議題者
Learner：最終決策學(xué)習(xí)者
上面4種角色中，提議者和決策者是很重要的，其他的2個角色在整個算法中應(yīng)該算做打醬油的，Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。這里上面出現(xiàn)了個新名詞：最終決策。現(xiàn)在來系統(tǒng)的介紹一下paxos算法中所有的行為：
- Proposer提出議題
- Acceptor初步接受 或者 Acceptor初步不接受
- 如果上一步Acceptor初步接受則Proposer再次向Acceptor確認(rèn)是否最終接受
- Acceptor 最終接受 或者Acceptor 最終不接受
上面Learner最終學(xué)習(xí)的目標(biāo)是Acceptor們最終接受了什么議題？注意，這里是向所有Acceptor學(xué)習(xí)，如果有多數(shù)派個Acceptor最終接受了某提議，那就得到了最終的結(jié)果，算法的目的就達(dá)到了。畫一幅圖來更加直觀：
為什么需要3個Acceptor？因為Acceptor必須是最少大于等于3個，并且必須是奇數(shù)個，因為要形成多數(shù)派嘛，如果是偶數(shù)個，比如4個，2個接受2個不接受，各執(zhí)己見，沒法搞下去了。
為什么是3個Proposer？ 其實無所謂是多少個了，1~n 都可以的；如果是1個proposer，毫無競爭壓力，很順利的完成2階段提交，Acceptor們最終批準(zhǔn)了事。如果是多個proposer就比較復(fù)雜了，請繼續(xù)看。
上面的圖中是畫了很多節(jié)點的，每個節(jié)點需要一臺機(jī)器么？答案是不需要的，上面的圖是邏輯圖，物理中，可以將Acceptor和Proposer以及Client放到一臺機(jī)器上，只是使用了不同的端口號罷了，Acceptor們啟動不同端口的TCP監(jiān)聽，Proposer來主動連接即可；完全可以將Client、Proposer、Acceptor、Learner合并到一個程序里面；這里舉一個例子：比如開發(fā)一個JOB程序，JOB程序部署在多臺服務(wù)器上(數(shù)量為奇數(shù))，這些JOB有可能同時處理一項任務(wù)，現(xiàn)在使用paxos算法讓這些JOB自己來商量由誰(哪臺機(jī)器)來處理這項任務(wù)，這樣JOB程序里就需要包含Client、Proposer、Acceptor、Learner這4大功能，并且需要配置其他JOB服務(wù)器的IP地址。
再舉一個例子，zookeeper常常用來做分布式事務(wù)鎖。Zookeeper所使用的zad協(xié)議也是類似paxos協(xié)議的。所有分布式自協(xié)商一致性算法都是paxos算法的簡化或者變種。Client是使用zookeeper服務(wù)的機(jī)器，Zookeeper自身包含了Acceptor, Proposer, Learner。Zookeeper領(lǐng)導(dǎo)選舉就是paxos過程，還有Client對Zookeeper寫Znode時，也是要進(jìn)行Paxos過程的，因為不同Client可能連接不同的Zookeeper服務(wù)器來寫Znode，到底哪個Client才能寫成功？需要依靠Zookeeper的paxos保證一致性，寫成功Znode的Client自然就是被最終接受了，Znode包含了寫入Client的IP與端口，其他的Client也可以讀取到這個Znode來進(jìn)行Learner。也就是說在Zookeeper自身包含了Learner(因為Zookeeper為了保證自身的一致性而會進(jìn)行領(lǐng)導(dǎo)選舉，所以需要有Learner的內(nèi)部機(jī)制，多個Zookeeper服務(wù)器之間需要知道現(xiàn)在誰是領(lǐng)導(dǎo)了)，Client端也可以Learner，Learner是廣義的。
現(xiàn)在通過一則故事來學(xué)習(xí)paxos的算法的流程(2階段提交)，有2個Client(老板，老板之間是競爭關(guān)系)和3個Acceptor(政府官員)：
- 現(xiàn)在需要對一項議題來進(jìn)行paxos過程，議題是“A項目我要中標(biāo)！”，這里的“我”指每個帶著他的秘書Proposer的Client老板。
- Proposer當(dāng)然聽老板的話了，趕緊帶著議題和現(xiàn)金去找Acceptor政府官員。
- 作為政府官員，當(dāng)然想誰給的錢多就把項目給誰。
- Proposer-1小姐帶著現(xiàn)金同時找到了Acceptor-1~Acceptor-3官員，1與2號官員分別收取了10比特幣，找到第3號官員時，沒想到遭到了3號官員的鄙視，3號官員告訴她，Proposer-2給了11比特幣。不過沒關(guān)系，Proposer-1已經(jīng)得到了1,2兩個官員的認(rèn)可，形成了多數(shù)派(如果沒有形成多數(shù)派，Proposer-1會去銀行提款在來找官員們給每人20比特幣，這個過程一直重復(fù)每次+10比特幣，直到多數(shù)派的形成)，滿意的找老板復(fù)命去了，但是此時Proposer-2保鏢找到了1,2號官員，分別給了他們11比特幣，1,2號官員的態(tài)度立刻轉(zhuǎn)變，都說Proposer-2的老板懂事，這下子Proposer-2放心了，搞定了3個官員，找老板復(fù)命去了，當(dāng)然這個過程是第一階段提交，只是官員們初步接受賄賂而已。故事中的比特幣是編號，議題是value。
這個過程保證了在某一時刻，某一個proposer的議題會形成一個多數(shù)派進(jìn)行初步支持；
===============華麗的分割線，第一階段結(jié)束================
5. 現(xiàn)在進(jìn)入第二階段提交，現(xiàn)在proposer-1小姐使用分身術(shù)(多線程并發(fā))分了3個自己分別去找3位官員，最先找到了1號官員簽合同，遭到了1號官員的鄙視，1號官員告訴他proposer-2先生給了他11比特幣，因為上一條規(guī)則的性質(zhì)proposer-1小姐知道proposer-2第一階段在她之后又形成了多數(shù)派(至少有2位官員的贓款被更新了);此時她趕緊去提款準(zhǔn)備重新賄賂這3個官員(重新進(jìn)入第一階段)，每人20比特幣。剛給1號官員20比特幣， 1號官員很高興初步接受了議題，還沒來得及見到2,3號官員的時候
這時proposer-2先生也使用分身術(shù)分別找3位官員(注意這里是proposer-2的第二階段)，被第1號官員拒絕了告訴他收到了20比特幣，第2,3號官員順利簽了合同，這時2，3號官員記錄client-2老板用了11比特幣中標(biāo)，因為形成了多數(shù)派，所以最終接受了Client2老板中標(biāo)這個議題，對于proposer-2先生已經(jīng)出色的完成了工作；
這時proposer-1小姐找到了2號官員，官員告訴她合同已經(jīng)簽了，將合同給她看，proposer-1小姐是一個沒有什么職業(yè)操守的聰明人，覺得跟Client1老板混沒什么前途，所以將自己的議題修改為“Client2老板中標(biāo)”，并且給了2號官員20比特幣，這樣形成了一個多數(shù)派。順利的再次進(jìn)入第二階段。由于此時沒有人競爭了，順利的找3位官員簽合同，3位官員看到議題與上次一次的合同是一致的，所以最終接受了，形成了多數(shù)派，proposer-1小姐跳槽到Client2老板的公司去了。
===============華麗的分割線，第二階段結(jié)束===============
Paxos過程結(jié)束了，這樣，一致性得到了保證，算法運行到最后所有的proposer都投“client2中標(biāo)”所有的acceptor都接受這個議題，也就是說在最初的第二階段，議題是先入為主的，誰先占了先機(jī)，后面的proposer在第一階段就會學(xué)習(xí)到這個議題而修改自己本身的議題，因為這樣沒職業(yè)操守，才能讓一致性得到保證，這就是paxos算法的一個過程。原來paxos算法里的角色都是這樣的不靠譜，不過沒關(guān)系，結(jié)果靠譜就可以了。該算法就是為了追求結(jié)果的一致性。