（本文包括章節：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

一日，諸葛亮找到劉備，突然獻上一曲《獨角戲》，而后放聲大哭。劉備正沉醉于新曲，暗嘆孔明大才，竟作得如此不凡仙樂，看到孔明忽而大悲，慌問：“水，何事悲慟？”
 
諸葛亮止住抽泣：“亮自主公三顧茅廬出山以來，蒙主公厚愛，自比如魚得水，敢不盡力？然每日擊鼓升帳，皆亮一人在上唱獨角戲，眾將在下唯唯諾諾，只是照亮的安排做事。如此下去，亮日后定會被司馬懿那廝累死呀。”
劉備眨著充滿問號的大眼睛：“孔明可是說曹賊丞相府小小的主薄司馬懿？他有何德何能。。。”
諸葛亮慌打斷：“亮心有些亂，且不提司馬懿那小子。”
諸葛亮正襟危坐：“主公，我們要法制不要人制呀！萬一哪天亮西去。。。”（劉備止含淚花握住孔明雙手，孔明亦緊緊反握住劉備的大手）
半晌，諸葛亮續道：“豈不人亡政息？且主公百年后，阿斗與亮的關系又怎能比得如今亮與主公般相敬如賓？若亮在外爭戰，阿斗與亮政見不合要亮退兵，決策沒有一致性，必將造成大錯！如此，我大蜀何以恢復漢室江山呀？！”
劉備：“備深感如此。”
諸葛亮：“亮昨夜夜觀天象。。。”
劉備大喜：“孔明可有良法？”
諸葛亮：“。。。亮昨夜夜觀天象，竟然睡著，原來近日太耗心力。做一夢，數千年彈指間，亮醒來才覺淚流滿面。夢中一帥哥自稱陶輝，獻上色目人大牛Leslie一法名paxos，或可解我等燃眉之急。”
劉備狂喜：“好！”繼而搔了搔頭：“先請孔明試言我大蜀帝國決策上有哪些問題？”
諸葛亮：“喏。”



1、蜀國現在決策制度的缺陷
諸葛亮：“主公，當下蜀國所有決策皆來自亮，這有兩個問題，一、若亮身體有恙則政令必有耽誤。二、隨著漢中的收復，我們的地盤越來越大，事務也越來越多，目前亮乃五百年不世出奇才，尚能支撐，可若是將來收復長安，亮一人之力必不堪重負。請問主公有何策解此二難？”

劉備沉吟著：“可讓法正法孝直，黃權黃公衡為你副手，平日助你共同議政決策，能幫你減負呀。孔明你老習慣在初一十五深入民間依紅偎翠，那時他們都可暫時頂替于你，如此也不怕政令耽誤了。”
諸葛亮咳嗽了下：“此二人皆治世之才！然，若子龍請求黃公衡允許蜀棉私營，而同時主公又請求亮加強壟斷這有錢途的行業--禁止蜀棉私營，文武百官令行兩出，或聽亮的搞國家壟斷，或聽黃公衡的搞民營經濟，百姓何以自處？”

劉備沉思半晌，方答道：“我們把決策分為兩部分，一種是新增政策，如我正準備加稅。另一種是下級官員請求政令的解釋，比如馬超出征歸來時問傷兵撫恤金是多少等等。這樣，孔明可處理所有新增決策，法正與黃權只負責解釋已有決策。下面官員在執行時，任意找你三人中清閑者，就某個事件詢問有何政令可指導，需要增加新的法令時，則只能找孔明你，孔明你決定新法令后，再通知法正和黃權這哥倆，這樣法令就同步且一致了。當孔明不在時，由法正頂上這個決策位置；法正不在時，由黃權頂上。如此可好？”
諸葛亮驚喜道：“善！這可是master-slave設計呀！”
劉備也睜大了雙眼閃著問號。諸葛亮咳嗽了下：“亮昨夜未睡好，失言了。”

諸葛亮又說道：“可這樣還有問題，日后若我們收復許昌洛陽建業后，那時新法令會更多，只允許一人處理新法令新決策，必然還會忙不過來！而且，人為的指定亮的第二順拉繼承者是法正，黃權為第三順位，這樣也不妥，在地位不平等時，若以后決策組又增加許多新人，或者同一時間多人一起吃酒吃壞肚子，都會非常麻煩。”

劉備拍案而起：“孔明你主張大家都是同樣地位，沒有主次之分？這樣無論哪個人出問題了，都不會對蜀國有什么影響？而且多人之間信息共享后，不會因人廢事，也不會有人亡政息之事了？”
諸葛亮：“Bingo！ 全對！這是真正的分布式！”
劉備大聲叫好：“分布式？好名字，和八陣圖一樣響亮呀！”
諸葛亮：“但這完全平等的分布式決策機制，仍然必須政令統一，不能有不一致的法令，例如黃權認為他昨天中午通過的法令是嚼口香糖者一律杖責十板，免得有人隨地亂吐影響市容（好象他們還立法大便后必須沖馬桶）。而法正卻在昨天上午就接受番邦李光耀的提議，允許嚼外國進口環保口香糖，百姓到底聽誰的呢？”
劉備：“我知道孔明你很討厭威權國家，別老抱怨，新加坡又沒礙你事。上面這就是一致性問題了。孔明別賣關子了，快說你的paxos解決方法吧。”



2、paxos需要解決的分布式問題
諸葛亮激動道：“paxos可是真正的民主呀，兩千年后我們漢人仍然做不到，這不是漢人的劣根性（烏坎村都能辦好的），實是歷史遺毒呀。閑話少敘，我們先來看看除了能保持一致性，paxos能解決哪些問題吧。

一、決策委員會里缺了哪個人都可以，蜀國照常做出決策。

二、大家的辦公地又不在一起，平時通過信使小吏們傳遞消息，若信使在路上傳消息時被馬車撞死，仍然不會有政令不一致。

三、若信使被馬車撞傷了，醫治后遲了幾個月才送到某人（例如法正），還不會出現政令不一致。

四、若信使被馬車撞失憶了，以為剛送過消息的黃權還沒送過，又跑去告訴黃權一次，同樣不會有不一致出現。”
劉備：“孔明，我知道你馬車機關多，開名車也不用總提嘛！若是信使被曹操的間諜收買了也沒事嗎？”
諸葛亮尷尬道：“這個不行，我們還是要相信人性本善嘛。呃，蜀國大部分都是好人。嗯，好吧，我們國安局不是吃干飯的，信使可以丟失、重復傳遞、延遲，但是我們保證不會被收買的。”
劉備：“好吧，能解決這四個問題也很不錯，基本異常都考慮到了。快說說這個paxos解決之道吧。”



3、paxos的約束條件
諸葛亮：“剛剛不是說了民主嗎？民主是個寶呀，它能解決一切問題。決策者之間不分高下，所以既然想要他們保持一致，我們就要用投票，少數服從多數！”
劉備：“怎么個投法？”
諸葛亮：“如果主公手下五虎上將是五個決策者。。。”劉備：“那五個肌肉男？”
諸葛亮：“正是，這證明即使五個頭腦簡單的武夫也能做好。”（五虎將齊打噴嚏。）
諸葛亮：“誰提議新政令（提案者），誰就發起投票。我們保證，投票者必須是決策者中的大多數。”
劉備：“怎么定大多數呢？”
諸葛亮：“任意兩次投票中，必須有重合的決策者，這就是大多數了。比如五虎將做決策者，每次政令通過中，必須有三個人或更多投票的人才能決定，這樣兩次投票中至少有一人都參加了，他就可以拍板！對提案者來說，如果大多數投票者都投贊成這個提議，法令就通過。”
劉備沉重地說道：“孔明，萬一總是湊不成大多數，豈不是耽誤我們的現代化進程？民主，對中國國情來說，太復雜了。”

諸葛亮又激動了：“主公，不復雜的，長遠來看好處很明顯，不要短視！如果能做到以個三個基本點，所有政令絕對不會出現不一致，而且不會出現無法進行下去的事。一、所有政令必須被提出后才能批準；二、一次提出政令的過程中，只能批準一條政令；三、書記官（負責永久記錄政令的官員）只能學習已經批準的政令。只要做到這三點，肯定不會政令不一致！”
劉備：“可是孔明，你在說什么呀？我只想知道決策者該怎么做。”
諸葛亮自信滿滿：“別急主公，從數學上可以證明，只要滿足上面三條，一定不會出現政令不一。當然，這三條太寬泛了，不能對決策者做出指導。我還有更加嚴格的約束。一、每個決策者必須接受他收到的第一個提議政令。”
劉備：“憑什么呀？”諸葛亮：“我們要假定提議者已經搞清楚了一切，肯定是好提案啦。這不是我們的重點，別打斷我。”
諸葛亮：“二、一旦關于一件事，我們通過一條法令后，之后關于這件事通過的任何法令，都還得是這個法令。”
劉備呆了下：“這不廢話嗎？”
諸葛亮自信滿滿：“雖然是廢話，但你想，保證了這第2條，是不是所有的政令都必須一致呀？”
劉備：“可是對決策者沒指導意義呀。”
諸葛亮自信滿滿：“是的，所以，我們加強約束，三、如果一條法令批準后，之后每一個決策者如果關于這件事又通過法令，那這個法令還得是同一條。”
劉備傻了：“你說得是沒錯，可這有什么用呢？”
諸葛亮自信滿滿：“所以繼續加強約束：四、如果一條法令被批準通過了，之后提議者關于這件事，又提新法令，必須還得是同一個法令。”
劉備怒了：“孔明我想揍你了，你說這些有個屁用啊！”
諸葛亮自信滿滿：“別急主公，現在我要祭出最強約束條件作為我的奧義了：五、每個提案都得有個獨一無二的編號，如果編號N的提案通過了，那么大多數決策者們，要么從沒接受者編號小于N的任何提議，要么最近一次批準通過的法令就是這個提案。”
劉備開始追打諸葛亮：“孔明你個壞人，你玩我呀！這屁話你對我說！”
諸葛亮邊逃邊喊：“wiki里就是這么解釋的，哎，主公你不懂數學別打我嘛。Leslie的論文也是這么寫的。。。”



4、paxos執行流程
劉備：“真爽，孔明你手感不錯。說點實在的吧，不懂的東西少扯。”
諸葛亮：“主公，你不懂數學嘛。好吧，我來說說paxos算法的流程，就三段式，六個步驟而已。角色包括，提案者，決策者，書記官（學習政令的）。
一、提案者先從主公那里搞到個獨一無二的編號，例如N。找到決策者們的多數派，就說五虎將吧，找到三個肌肉男先。假設，這個提案者來自成都，想提的是，外地蜀國將級官員不得無故進入魏國使者駐蜀驛館。那么，提案者發給三個五虎將，提案中說，我現在有個編號N的提案，關于蜀國高級將領進出魏國使者驛館的事，請回答我。”

二、五虎將們收到了關于使者驛館事件的提案，編號是N。其中任一個決策者，比如趙云，他在收到N提案后，首先檢查，之前關于魏國使者驛館事件，有沒有收到過提案啊？如果沒收到，當然回復提案通過，同時趙云拿出自己的小本本記上，已經回復編號N的提案。如果收到過關于驛館事件的編號M的提案，就檢查編號M，如果M大于N，那么跟信使說，我拒絕這個提案。如果M小于N，回復通過，并且說，關于這事，上次我已經收到了編號M的提案了。

三、提案者如果收到多數決策者的通過回復，就開始正式提議了。這時，先檢查五虎將的回復，如果都簡單的回復通過，那么就正式提議之前想提議的《蜀國將級官員不得無故進入魏國使者駐蜀國驛館》提案。如果決策者們不是簡單的回復通過，而是說：這次我趙云通過了，但是我曾經回復過編號M的提案。這樣，提案者需要從這次決策者們的回復中，找出所有編號M中的最大值。假設就趙云復雜的回復了，其他四人都是簡單的回復通過。那么，提案者這次不能正式提議自己原來想提的，而要提議編號M對應的提案。

四、同第二步驟一樣，五虎將們根據二步驟的準則，選擇通過還是不通過。
五、提案者如果發現多數決策者同意了，意味著法令通過，這時他要記錄法令，同時告訴書記官們。
六、書記官們在羊皮紙上記錄法令。“



5、paxos算法里的各角色該做的事
劉備搔搔頭：“孔明，你再說說提案者，決策者要做的事吧，書記官的很簡單，就不用說了。”
諸葛亮：“主公，書記官的工作不簡單啊，信使會傳丟消息的，書記官也會生病的。我們既要在法令通過時主動通知書記官，又要允許書記官在對法令不清楚時過來主動詢問。不過，既然主公想多了解提案者和決策者的工作，我就來詳細說說。
一、提案者。首先他得從主公那搞來一個獨一無二的編號。”
劉備：“我很忙的孔明，我是一把手哎。”
諸葛亮有些無奈：“就光給編號也不干呀！那讓他們自己維護自己的編號吧，遇到編號相同時，按級別排序，例如按關羽、張飛、趙云、馬超、黃忠排序。然后要找到五虎將的多數派，例如關張趙這三人，發自己要決定的事以及編號過去。這是第一步。在第三步時，又到了提案者要做工作了。如果關羽又不響應自己了，那么再發給黃忠問問看。直到有大多數人響應自己。對于響應的處理，有以下情況：
A、這些響應中，如果有人明確拒絕，比如趙云說，關于驛館事件，我已經批了編號大于N的提案，那么這次提案最好就放棄吧，或者加大自己的編號，重復第一步再提！
B、張飛說我可以通過，但是之前我批準過驛館事件編號小于N的提案，內容是允許進入達到政治避難目的。那么，這次提案內容必須變更為張飛之前提交的方案。
C、所有人都無條件通過。繼續正式提交自己的方案。
到第五步，如果多數派批準了，那么方案正式成為法令。提案者要告訴書記官記錄哦。”
劉備：“你這么說我就明白了嘛。多簡單？先前搞七搞八的說了一大通。”
諸葛亮：“唉，先前的證明嘛。當然，微軟還搞了個兩段式提交，號稱fast paxos，那個雅虎的zookeeper也是的，其實也就對第五步做了優化。主公，不要打我，你不用管我剛才說了什么。我們繼續說決策者的工作。
第二步，決策者開始工作了。例如還是說趙云，他在收到N提案后，首先檢查，之前關于魏國使者驛館事件，有沒有收到過提案啊？如果沒收到，簡單的回復提案通過，同時趙云拿出自己的小本本記上，已經回復編號N的提案。趙云同時承諾，以后收到編號小于N的關于驛館事件的提案，保證不批！如果收到過編號M的提案，檢查這上次編號M，如果M大于N，那么跟信使說，我拒絕這個提案。如果M小于N，回復通過，并且說，關于這事，上次我已經收到了編號M的提案了。
第四步決策者批準時也和上面一樣。不過fast paxos等兩段式的paxos改進算法，在這里決策者們已經可以記錄法案了。”
劉備：“好孔明！我有些明白了，不過光說不練假把式，演習下吧。把五個肌肉男叫來，你我來提案，外加搗亂，你可以用你的跑車撞信使了，看看是否出現不一致。”
諸葛亮：“No problem。不過現在我口干舌燥，咱們下回再說吧。”（想從具體的演習，從時間和各種容錯上看paxos的效用，敬請期待下篇《paxos算法如何容錯的--講述五虎將的實踐》

Panic和Recover

Go沒有像Java那樣的異常機制，它不能拋出異常，而是使用了panic和recover機制。一定要記住，你應當把它作為最后的手段來使用，也就是說，你的代碼中應當沒有，或者很少有panic的東西。這是個強大的工具，請明智地使用它。那么，我們應該如何使用它呢？

Panic

是一個內建函數，可以中斷原有的控制流程，進入一個令人恐慌的流程中。當函數F調用panic，函數F的執行被中斷，但是F中的延遲函數會正常執行，然后F返回到調用它的地方。在調用的地方，F的行為就像調用了panic。這一過程繼續向上，直到發生panic的goroutine中所有調用的函數返回，此時程序退出。恐慌可以直接調用panic產生。也可以由運行時錯誤產生，例如訪問越界的數組。

Recover

是一個內建的函數，可以讓進入令人恐慌的流程中的goroutine恢復過來。recover僅在延遲函數中有效。在正常的執行過程中，調用recover會返回nil，并且沒有其它任何效果。如果當前的goroutine陷入恐慌，調用recover可以捕獲到panic的輸入值，并且恢復正常的執行。

下面這個函數演示了如何在過程中使用panic

var user = os.Getenv("USER")  func init() {     if user == "" {         panic("no value for $USER")     } } 

下面這個函數檢查作為其參數的函數在執行時是否會產生panic：

func throwsPanic(f func()) (b bool) {     defer func() {         if x := recover(); x != nil {             b = true         }     }()     f() //執行函數f，如果f中出現了panic，那么就可以恢復回來     return } 

最容易理解就是給個例子，文章里有例子：

package main  import(     "fmt"     //"os" )  var user = "" func inita() {     defer func(){         fmt.Print("defer##\n")     }()     if user == "" {         fmt.Print("@@@before panic\n")         panic("no value for user\n")         fmt.Print("!!after panic\n")     } }  func throwsPanic (f func()) (b bool){     defer func(){         if x:= recover(); x != nil{             fmt.Print(x)             b = true         }     }()     f()     fmt.Print("after the func run")     return }  func main(){     throwsPanic(inita) } 

執行結果：

D:\go>go run b.go
@@@before panic
defer##
no value for user

如上面所說的：

panic在user=""時，打斷了函數的執行，fmt.Print("!!after panic\n")沒有執行。 但函數中的延遲函數會正常執行，打印了 defer##。然后返回到調用該函數的地方，繼續上面的過程。

直到執行完所有函數的defer，退出程序。Recover可以捕獲到panic的值，上面的打印no value for user。并且恢復正常的執行。