（本文包括章節：1、由來，2、算法簡單回顧，3、演習道具，4、演習，5、算法提出者Leslie的八卦。hoho）
1、由來：
劉備接受了諸葛亮的提議，決定將paxos算法的思想應用到蜀帝國的決策機制上。然而，玄德生性謹慎，決定先行試點，實踐下可行性。孔明提議，由蜀國五大肌肉男：關羽、張飛、趙云、馬超、黃忠，做為決策者，而廖化、周倉、魏延分別無序的提出關于同一件事的水火不容的三個提案，孔明堅信：即使腦殘者使用了paxos算法，也不會出現沖突的政令不一情況。paxos算法理論以及劉備是怎么被孔明忽悠的部分，同學們可以參考上篇《paxos分布式一致性算法--講述諸葛亮的反穿越》：http://blog.csdn.net/russell_tao/article/details/7244530
閑話少敘，書接上文。
為了少打點字，劉備與諸葛亮倆玻璃不再以對話形式出現了。他們設置了五個官署（五虎將辦公地，相當于Server），三個提案點（周倉等三人，發起提案時的辦公地。相當于Client），當然都不在一起，信使們從提案點到官署傳遞信息的話，正常情況下需要半個小時，也就是30分鐘。這次演習，哥倆不關注學習情況，所以paxos第三段就不在演習內容里了。諸葛亮為廖化、周他、魏延對于事件e準備了三個自相矛盾的提案，我們分別用p1、p2和p3代替吧。先行說明提案：
事件e（也就是本次paxos實例）：蜀國今后的發展路線
提案p1：學習紅色錘子鐮刀，走激進主義，一切發展按照計劃進行，小民們憑票消費，銀子多了也沒用，集中力量辦大事，崇尚國家壟斷主義。
提案p2：學習自由聯盟，走自由主義，寧失去效率也不失去公正，發展民營經濟為先，民主、法制、新聞自由，通過這種公正來激發社會的整體創造力。
提案p3：堅持孔孟之道，走保守主義，兼顧黃老之學，堅信中學為體、西學為用，國體不可大改，走有大漢國情的老路讓別人說去吧。
2、算法簡單回顧
我們再簡單回顧下提案者和作為決策者的五虎將行動準則，共有六步，書記官（暫讓五虎將兼職）負責記錄下通過的提案p（通過了就叫法令了），這樣，我們用1a,1b,2a,2b,3a,3c來表述全部的六步。（這六步就是三段式提交了，這在上篇《paxos分布式一致性算法--講述諸葛亮的反穿越》里講過，不再復述。）
魏延、廖化、周倉：
1a,作為提案者，首先向劉備要到個編號，搞清楚自己對事件e的態度。記錄下當前時間，接下來向五虎將的多數派（3個或以上）發送事件+編號。
2a,此時開始處理五虎將的回應，這就有多種情況了。收到明確拒絕就得放棄！檢查沙漏，如果到達時間限制了，還沒有足夠的多數派回應，那么就試著給五虎將的其他人再發送提案看看。如果收到了足夠的五虎將里多數派的回應，那么，確定在2a這步里，如果要提案，到底提哪個提議？是自己現在要提的提案？
3a,提案者如果收到足夠的五虎將多數派回應通過，則記錄提案為通過的政策法令，同時通知所有書記官，也就是兼職的五虎將，把法令記錄到羊皮紙上來。
五虎將：
1b，作為決策者，也需要沙漏，主要用于2b步驟后批準政策法令后，給自己設定個超時時間，若第三步信使沒有過來，則超時后自動把提案變成政策法令記錄到羊皮紙上。1b這個步驟是收到了信使的消息，來自于1a步驟里的提案者。收到事件e和編號N。五虎將這時將有可能出現三個動作：拒絕、通過以及第三個復雜點的動作，雖然通過但告訴魏延廖化，哥曾經批準過某提案了。（三種條件的達成請參考上篇文章《paxos分布式一致性算法--講述諸葛亮的反穿越》）
2b，與1b步驟相同，唯一不一樣的是，如果決定批準某個提案，必須先把該提案和編號記錄到羊皮紙的背面。（羊皮紙的詳細用途參見演習前提）
3b，記錄法案到羊皮紙的正面上。（本步驟不在下面演習中出現）
3、演習道具
先解釋下我們用到的道具吧。
羊皮紙（相當于硬盤）：其正面記錄真正通過的法令，背面相當于永久有效的草紙，背面記錄一個三元組（S，V，Sh），S表示上次批準的提案編號，V表示上次批準的提案，Sh表示處理過的最大提案編號。（羊皮紙丟掉后的效果在演習結束后說明）
草紙：與羊皮紙背面相同，記錄三元組。唯一不同的是，草紙容易丟失。
沙漏：記錄時間。我們簡單的認為，任何兩個地方一次通訊時間為30分鐘。所以，如果我們從提案者那出發，信使到五虎將再回來，我們認為一個小時足矣（忽略五虎將或者提案者的處理時間）。
下面的演習中，只有消息的丟失，實際上對于消息的重發和延遲，也不會有任何問題。只是對五虎將的缺席，需要做說明。如果五虎將的羊皮紙丟失，是不能直接再次加入進五人決策團的，必須學習到最新的狀態。沒丟羊皮紙，則可以隨時加入進來。
書記官記錄法令中的不一致情況這里不加討論。
為了方便在圖表中表示，我們先給五虎將五個字母編號：關羽a，張飛b，趙云c，馬超d，黃忠e。
三種顏色表示不同的提案者：黃色表示廖化，藍色表示周倉，紅色表示魏延。
下面這幅圖，表示不同的時間點，五虎將和三個提案者當時的狀態。
->表示第一步預提案。包括1a和1b兩步。
-->表示第二步提交提案，包括2a和2b。
五虎將記錄的(s,v,sh)表示的三元組上面講過了。法令項下面對應的是提案者魏、廖、周三人的狀態。（wait）表示剛發出提案，1小時內等待返回呢。
e is drop表示發送給e黃忠的提案消息丟失了。
好了，可以往下看了。
4、演習
先放圖，解釋在下面。
詳細說明上圖：
8：30分上班了，紅色周倉同學首先向關羽、趙云、黃忠三人發出了提案p1，編號為100，周倉開始等返回，預計9：30分時能收到三位的返回。我們假定，發給黃忠的信使出門就被孔明的跑車撞了。孔明闖禍后老實了，以下，不再出現信使失誤事件了。
8：40分，崇尚民主的廖化同學向關羽、張飛、黃忠三人發出了編號為101的提案p2，預計9：40分收到返回的信使。
8：50分，喜歡孔孟的魏延同學向趙云、馬超、黃忠三人發出了編號為110（魏延就是搞到大編號了啊）的提案p3，預計9：50收到返回的信使。
9：00整，周倉的提案p1到了關羽、趙云手里（黃忠沒收到），兩人無條件接受，記錄(100,p1,100)，承諾編號低于100的提案我可不會再處理了，然后兩個信使開始返回。
9：10分，廖化編號為101的提案p2到了關羽、張飛、黃忠之手，張飛、黃忠哥倆從沒收過事件e的提案，毫無疑問記為(101,p2,101)，讓信使回復接受。關羽則不然，紅臉兄在10分鐘前收到了周倉的編號為100的p1提案。所以，按規則辦，關羽改自己的記錄為（100,p1,101），讓信使給廖化回復：你的編號101比較大，我同意你繼續，不過我之前同意過一個編號為100的提案p1，請注意哦。
9：20分，魏延的p3提案到了趙云、馬超、黃忠三人之手，馬超第一次收到提案，記為(110,p3,110)，回復批準。趙云和黃忠則不同，趙云收到過周倉的p1提案，這時要比提案編號了，魏延的110大于周倉的100，于是趙云記為(100,p1,110)，告訴信使：我通過了，我承諾編號小于110的我不會處理，同時，我曾經批準過編號為100的提案p1。同理，黃忠記為(101,p2,110)，也告訴信使：我曾經批準過編號為101的提案p2。
9：30分，周倉同學檢測返回的信使了，關羽和趙云都返回批準，但是黃忠沒有返回。因為必須N/2+1，也就是大多數人批準才行，所以，周倉向張飛發出提案p1。
9：40分，廖化收到了來自關羽、張飛、黃忠的回復，三人皆表示同意，但關羽表示：關某曾收到過編號100的p1提案。所以按照規則，廖化此時不能堅持自己原來的提案p2，而要改成關羽返回的提案p1，然后發起提交皆段，同樣是讓信使帶給關羽、張飛、黃忠三人，我們用->>(a,b,e)表示。
9：50分，魏延收到了趙云、馬超、黃忠三人在9:20分的答復，三人都同意了，但回答各不相同。馬超沒有多話，趙云說我曾收到過編號為100的p1提案，黃忠說我曾經收到過編號為101的p2提案。于是，魏延根據規則，不再提自己原來的p3提案，改為101編號對應的提案p2。接著，魏延開始向這三人發出提交請求，編號為110的提案p2。
10：00整，張飛收到了9:30分周倉補發的編號為100的提案p1，這之前，張飛在9:10分時曾經批準過來自廖化的提案p2，編號是101。所以，張飛在9:10時就已經承諾了，以后決不再處理編號小于101的提案。于是，張飛大吼一聲：我拒絕。當然信使將會在10:30才能把消息帶給周倉。
10：10分，關羽、張飛、黃忠收到了來自廖化于9：40分發出的(101,p1)提案，關羽和張飛都發現自己可以批準，記錄到羊皮紙的背面，同時告訴信使：告訴廖化P1提案我批準了，我承諾編號小于101的提案不予理會。黃忠則不然，老將黃忠在9:20分時收到過魏延編號為110的提案，那時他批準了，意味著，所有小于110的提案他都會拒絕掉。這次廖化的提案才101，當然被拒絕掉了。三人的回復將于10:40會到達廖化處。
10：20分，魏延編號為110的P2提案到達趙云、馬超、黃忠，三人沒有疑問，畢竟110編號最大，都表示批準，并記錄(110,p2,110)到各自的羊皮紙背面，回復信使通過。
10：30分，周倉收到了他在9：30分發給張飛的回復，張飛在10:00拒絕了，所以周倉這個提案就此作廢。
10：40分，廖化收到了10：10來自關羽、張飛、黃忠的回復，關張二人批準，然而老黃忠明確表示拒絕，于是這次編號101的提案作廢。
10：50分，魏延收到了趙云、馬超、黃忠的回復，三人都表示批準，于是編號為110的提案p2最終作為法令記錄下來（之后的3b學習過程略過），從此以后，蜀國的路線被確立為走民主路線，許多年后，蜀國統一了銀河系。完。
以上任何步驟，大家可以任意制造難度，例如讓同一個信使重復投遞消息，或者延遲一天后消息到達某虎將處。或者讓某個虎將正常如廁，而后正常歸來。大家會發現，一致性是可以達到的，無論怎樣，對于同一個事件e，互相沖突的三個法案：p1,p1,p3，一定只有一個可以達成。
對于任一虎將兄的掛掉，我們要分情況。如果是去大便，那么他的羊皮紙是不能丟的。大便完了，可以正常回到自己的官署辦公。但是如果把羊皮紙丟了，那就不能立刻加入，必須向所有其他人學習，把失落的過程都學到，才能正常加入。這點至關重要，就是說，只要硬盤不壞，隨時SERVER重啟都能加入。硬盤一壞，對不起，學習完了才能繼續辦公。
5、后記---Leslie的八卦：
paxos算法是解決分布式服務數據一致性的終極算法，google的基礎服務chubby（GFS的基礎服務）的開發者說， “there is only one consensus（一致性） protocol, and that’s Paxos”。Microsoft有fast paxos論文，yahoo的zookeeper也用了paxos算法。可見，paxos是解決完全的分布式服務（無單點）間數據一致性的最好方法。但是paxos比較復雜，特別是網上的中文資料里少有能說得清楚的（主要是太多paxos變種算法了，摻合到一起攪得人頭大），例如中文wiki上的paxos解釋，光看這個是不可能搞懂paxos的。
paxos算法由Leslie Lamport在1990年提出，毫無疑問，paxos想解決的就是分布式環境下（server會掛掉，通訊協議不可靠，消息可能延遲、丟失、重發）如何保持數據一致性的問題。Leslie Lamport同學在1982年提出的“拜占庭將軍”問題上嘗到了甜頭，這也是個分布式環境下的一致性問題，Leslie通過類比的方式，偽造了“拜占庭將軍”歷史，通過這種簡單的類比成功的簡化了復雜的分布式環境，效果非常好。于是在1990年Leslie同樣用類比的方式提出了paxos算法，該問題跟“拜占庭將軍”問題的區別是，“拜占庭將軍”允許有叛徒，也就是允許偽造消息（默許被黑客攻擊），而paxos則不允許消息被偽造。
Leslie很有幽默感的把論文寫成一個考古發現，至始至終都在虛構他的“考古發現”。他說在考古中發現了失落的文明：希臘的paxos小島。這里的議員通過郵遞員傳遞消息，議會中一個議員提出法案，多數議員批準后法案獲得通過。當然無論議員還是郵遞員，都是兼職的，他們不可靠，隨時可能走人，呵，典型的分布式環境，server可以掛，消息可以丟。Leslie根據考古文獻反推出了paxos議會如何搞定法案一致性的問題。
發表論文時，Leslie一直用這種語氣在寫論文，于是《ACM Transactions on Computer Systems》編輯們認為太荒誕了，不能從頭到尾虛構故事吧？畢竟是嚴謹的科學雜志，于是打回。Leslie同學身為牛人，堅持自己的看法，同時認為編輯們沒有幽默感，拒絕修改。時間流逝，一晃九年過去，九年后有團隊根據該論文開發出一個paxos實現，終于，編輯們低頭了，允許發布Leslie的論文，但還是加了段編者著，在其中表示Leslie其實是個熱愛計算機技術的考古學家！也算稍事解嘲。
寫這兩篇文章，我也試了下借喻的手段，用我們熟悉的三國人物，看看能否講清楚paxos。其實paxos的算法本身算不得很復雜，但如果想講清楚在各種異常情形下paxos算法的表現，給大家帶來的明確的直觀感受：paxos確實能解決一致性問題，這就不容易了。所以篇幅所限，只寫了丟失一個消息的情況。不過大家如果從頭看到這，應該可以簡單的任意推導出其他異常吧？
最后，上面說的只是算法機制，如果需要了解現有的各種產品實現，最方便的還是看zookeeper源碼，畢竟是開源的，例如去：http://zookeeper.apache.org/doc/r3.3.2/zookeeperOver.html，可以看下概述。淘寶開發團隊有許多關于zookeeper實現的文章，到網上搜下就能看到。
對google的chubby實現，因為不是開源的，只有篇論文可以看：http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/zh-CN/us/archive/chubby-osdi06.pdf