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