（本文包括章節(jié)：1、由來(lái)，2、算法簡(jiǎn)單回顧，3、演習(xí)道具，4、演習(xí)，5、算法提出者Leslie的八卦。hoho）

1、由來(lái)：

劉備接受了諸葛亮的提議，決定將paxos算法的思想應(yīng)用到蜀帝國(guó)的決策機(jī)制上。然而，玄德生性謹(jǐn)慎，決定先行試點(diǎn)，實(shí)踐下可行性。孔明提議，由蜀國(guó)五大肌肉男：關(guān)羽、張飛、趙云、馬超、黃忠，做為決策者，而廖化、周倉(cāng)、魏延分別無(wú)序的提出關(guān)于同一件事的水火不容的三個(gè)提案，孔明堅(jiān)信：即使腦殘者使用了paxos算法，也不會(huì)出現(xiàn)沖突的政令不一情況。paxos算法理論以及劉備是怎么被孔明忽悠的部分，同學(xué)們可以參考上篇《paxos分布式一致性算法--講述諸葛亮的反穿越》：http://blog.csdn.net/russell_tao/article/details/7244530

閑話少敘，書接上文。

為了少打點(diǎn)字，劉備與諸葛亮倆玻璃不再以對(duì)話形式出現(xiàn)了。他們?cè)O(shè)置了五個(gè)官署（五虎將辦公地，相當(dāng)于Server），三個(gè)提案點(diǎn)（周倉(cāng)等三人，發(fā)起提案時(shí)的辦公地。相當(dāng)于Client），當(dāng)然都不在一起，信使們從提案點(diǎn)到官署傳遞信息的話，正常情況下需要半個(gè)小時(shí)，也就是30分鐘。這次演習(xí)，哥倆不關(guān)注學(xué)習(xí)情況，所以paxos第三段就不在演習(xí)內(nèi)容里了。諸葛亮為廖化、周他、魏延對(duì)于事件e準(zhǔn)備了三個(gè)自相矛盾的提案，我們分別用p1、p2和p3代替吧。先行說(shuō)明提案：

事件e（也就是本次paxos實(shí)例）：蜀國(guó)今后的發(fā)展路線

提案p1：學(xué)習(xí)紅色錘子鐮刀，走激進(jìn)主義，一切發(fā)展按照計(jì)劃進(jìn)行，小民們憑票消費(fèi)，銀子多了也沒(méi)用，集中力量辦大事，崇尚國(guó)家壟斷主義。

提案p2：學(xué)習(xí)自由聯(lián)盟，走自由主義，寧失去效率也不失去公正，發(fā)展民營(yíng)經(jīng)濟(jì)為先，民主、法制、新聞自由，通過(guò)這種公正來(lái)激發(fā)社會(huì)的整體創(chuàng)造力。

提案p3：堅(jiān)持孔孟之道，走保守主義，兼顧黃老之學(xué)，堅(jiān)信中學(xué)為體、西學(xué)為用，國(guó)體不可大改，走有大漢國(guó)情的老路讓別人說(shuō)去吧。

2、算法簡(jiǎn)單回顧

我們?cè)俸?jiǎn)單回顧下提案者和作為決策者的五虎將行動(dòng)準(zhǔn)則，共有六步，書記官（暫讓五虎將兼職）負(fù)責(zé)記錄下通過(guò)的提案p（通過(guò)了就叫法令了），這樣，我們用1a,1b,2a,2b,3a,3c來(lái)表述全部的六步。（這六步就是三段式提交了，這在上篇《paxos分布式一致性算法--講述諸葛亮的反穿越》里講過(guò)，不再?gòu)?fù)述。）

魏延、廖化、周倉(cāng)：

1a,作為提案者，首先向劉備要到個(gè)編號(hào)，搞清楚自己對(duì)事件e的態(tài)度。記錄下當(dāng)前時(shí)間，接下來(lái)向五虎將的多數(shù)派（3個(gè)或以上）發(fā)送事件+編號(hào)。

2a,此時(shí)開(kāi)始處理五虎將的回應(yīng)，這就有多種情況了。收到明確拒絕就得放棄！檢查沙漏，如果到達(dá)時(shí)間限制了，還沒(méi)有足夠的多數(shù)派回應(yīng)，那么就試著給五虎將的其他人再發(fā)送提案看看。如果收到了足夠的五虎將里多數(shù)派的回應(yīng)，那么，確定在2a這步里，如果要提案，到底提哪個(gè)提議？是自己現(xiàn)在要提的提案？

3a,提案者如果收到足夠的五虎將多數(shù)派回應(yīng)通過(guò)，則記錄提案為通過(guò)的政策法令，同時(shí)通知所有書記官，也就是兼職的五虎將，把法令記錄到羊皮紙上來(lái)。

五虎將：

1b，作為決策者，也需要沙漏，主要用于2b步驟后批準(zhǔn)政策法令后，給自己設(shè)定個(gè)超時(shí)時(shí)間，若第三步信使沒(méi)有過(guò)來(lái)，則超時(shí)后自動(dòng)把提案變成政策法令記錄到羊皮紙上。1b這個(gè)步驟是收到了信使的消息，來(lái)自于1a步驟里的提案者。收到事件e和編號(hào)N。五虎將這時(shí)將有可能出現(xiàn)三個(gè)動(dòng)作：拒絕、通過(guò)以及第三個(gè)復(fù)雜點(diǎn)的動(dòng)作，雖然通過(guò)但告訴魏延廖化，哥曾經(jīng)批準(zhǔn)過(guò)某提案了。（三種條件的達(dá)成請(qǐng)參考上篇文章《paxos分布式一致性算法--講述諸葛亮的反穿越》）

2b，與1b步驟相同，唯一不一樣的是，如果決定批準(zhǔn)某個(gè)提案，必須先把該提案和編號(hào)記錄到羊皮紙的背面。（羊皮紙的詳細(xì)用途參見(jiàn)演習(xí)前提）

3b，記錄法案到羊皮紙的正面上。（本步驟不在下面演習(xí)中出現(xiàn)）

3、演習(xí)道具

先解釋下我們用到的道具吧。

羊皮紙（相當(dāng)于硬盤）：其正面記錄真正通過(guò)的法令，背面相當(dāng)于永久有效的草紙，背面記錄一個(gè)三元組（S，V，Sh），S表示上次批準(zhǔn)的提案編號(hào)，V表示上次批準(zhǔn)的提案，Sh表示處理過(guò)的最大提案編號(hào)。（羊皮紙丟掉后的效果在演習(xí)結(jié)束后說(shuō)明）

草紙：與羊皮紙背面相同，記錄三元組。唯一不同的是，草紙容易丟失。

沙漏：記錄時(shí)間。我們簡(jiǎn)單的認(rèn)為，任何兩個(gè)地方一次通訊時(shí)間為30分鐘。所以，如果我們從提案者那出發(fā)，信使到五虎將再回來(lái)，我們認(rèn)為一個(gè)小時(shí)足矣（忽略五虎將或者提案者的處理時(shí)間）。

下面的演習(xí)中，只有消息的丟失，實(shí)際上對(duì)于消息的重發(fā)和延遲，也不會(huì)有任何問(wèn)題。只是對(duì)五虎將的缺席，需要做說(shuō)明。如果五虎將的羊皮紙丟失，是不能直接再次加入進(jìn)五人決策團(tuán)的，必須學(xué)習(xí)到最新的狀態(tài)。沒(méi)丟羊皮紙，則可以隨時(shí)加入進(jìn)來(lái)。

書記官記錄法令中的不一致情況這里不加討論。

為了方便在圖表中表示，我們先給五虎將五個(gè)字母編號(hào)：關(guān)羽a，張飛b，趙云c，馬超d，黃忠e。

三種顏色表示不同的提案者：黃色表示廖化，藍(lán)色表示周倉(cāng)，紅色表示魏延。

下面這幅圖，表示不同的時(shí)間點(diǎn)，五虎將和三個(gè)提案者當(dāng)時(shí)的狀態(tài)。

->表示第一步預(yù)提案。包括1a和1b兩步。

-->表示第二步提交提案，包括2a和2b。

五虎將記錄的(s,v,sh)表示的三元組上面講過(guò)了。法令項(xiàng)下面對(duì)應(yīng)的是提案者魏、廖、周三人的狀態(tài)。（wait）表示剛發(fā)出提案，1小時(shí)內(nèi)等待返回呢。

e is drop表示發(fā)送給e黃忠的提案消息丟失了。

好了，可以往下看了。

4、演習(xí)

先放圖，解釋在下面。

詳細(xì)說(shuō)明上圖：

8：30分上班了，紅色周倉(cāng)同學(xué)首先向關(guān)羽、趙云、黃忠三人發(fā)出了提案p1，編號(hào)為100，周倉(cāng)開(kāi)始等返回，預(yù)計(jì)9：30分時(shí)能收到三位的返回。我們假定，發(fā)給黃忠的信使出門就被孔明的跑車撞了。孔明闖禍后老實(shí)了，以下，不再出現(xiàn)信使失誤事件了。

8：40分，崇尚民主的廖化同學(xué)向關(guān)羽、張飛、黃忠三人發(fā)出了編號(hào)為101的提案p2，預(yù)計(jì)9：40分收到返回的信使。

8：50分，喜歡孔孟的魏延同學(xué)向趙云、馬超、黃忠三人發(fā)出了編號(hào)為110（魏延就是搞到大編號(hào)了啊）的提案p3，預(yù)計(jì)9：50收到返回的信使。

9：00整，周倉(cāng)的提案p1到了關(guān)羽、趙云手里（黃忠沒(méi)收到），兩人無(wú)條件接受，記錄(100,p1,100)，承諾編號(hào)低于100的提案我可不會(huì)再處理了，然后兩個(gè)信使開(kāi)始返回。

9：10分，廖化編號(hào)為101的提案p2到了關(guān)羽、張飛、黃忠之手，張飛、黃忠哥倆從沒(méi)收過(guò)事件e的提案，毫無(wú)疑問(wèn)記為(101,p2,101)，讓信使回復(fù)接受。關(guān)羽則不然，紅臉兄在10分鐘前收到了周倉(cāng)的編號(hào)為100的p1提案。所以，按規(guī)則辦，關(guān)羽改自己的記錄為（100,p1,101），讓信使給廖化回復(fù)：你的編號(hào)101比較大，我同意你繼續(xù)，不過(guò)我之前同意過(guò)一個(gè)編號(hào)為100的提案p1，請(qǐng)注意哦。

9：20分，魏延的p3提案到了趙云、馬超、黃忠三人之手，馬超第一次收到提案，記為(110,p3,110)，回復(fù)批準(zhǔn)。趙云和黃忠則不同，趙云收到過(guò)周倉(cāng)的p1提案，這時(shí)要比提案編號(hào)了，魏延的110大于周倉(cāng)的100，于是趙云記為(100,p1,110)，告訴信使：我通過(guò)了，我承諾編號(hào)小于110的我不會(huì)處理，同時(shí)，我曾經(jīng)批準(zhǔn)過(guò)編號(hào)為100的提案p1。同理，黃忠記為(101,p2,110)，也告訴信使：我曾經(jīng)批準(zhǔn)過(guò)編號(hào)為101的提案p2。

9：30分，周倉(cāng)同學(xué)檢測(cè)返回的信使了，關(guān)羽和趙云都返回批準(zhǔn)，但是黃忠沒(méi)有返回。因?yàn)楸仨歂/2+1，也就是大多數(shù)人批準(zhǔn)才行，所以，周倉(cāng)向張飛發(fā)出提案p1。

9：40分，廖化收到了來(lái)自關(guān)羽、張飛、黃忠的回復(fù)，三人皆表示同意，但關(guān)羽表示：關(guān)某曾收到過(guò)編號(hào)100的p1提案。所以按照規(guī)則，廖化此時(shí)不能堅(jiān)持自己原來(lái)的提案p2，而要改成關(guān)羽返回的提案p1，然后發(fā)起提交皆段，同樣是讓信使帶給關(guān)羽、張飛、黃忠三人，我們用->>(a,b,e)表示。

9：50分，魏延收到了趙云、馬超、黃忠三人在9:20分的答復(fù)，三人都同意了，但回答各不相同。馬超沒(méi)有多話，趙云說(shuō)我曾收到過(guò)編號(hào)為100的p1提案，黃忠說(shuō)我曾經(jīng)收到過(guò)編號(hào)為101的p2提案。于是，魏延根據(jù)規(guī)則，不再提自己原來(lái)的p3提案，改為101編號(hào)對(duì)應(yīng)的提案p2。接著，魏延開(kāi)始向這三人發(fā)出提交請(qǐng)求，編號(hào)為110的提案p2。

10：00整，張飛收到了9:30分周倉(cāng)補(bǔ)發(fā)的編號(hào)為100的提案p1，這之前，張飛在9:10分時(shí)曾經(jīng)批準(zhǔn)過(guò)來(lái)自廖化的提案p2，編號(hào)是101。所以，張飛在9:10時(shí)就已經(jīng)承諾了，以后決不再處理編號(hào)小于101的提案。于是，張飛大吼一聲：我拒絕。當(dāng)然信使將會(huì)在10:30才能把消息帶給周倉(cāng)。

10：10分，關(guān)羽、張飛、黃忠收到了來(lái)自廖化于9：40分發(fā)出的(101,p1)提案，關(guān)羽和張飛都發(fā)現(xiàn)自己可以批準(zhǔn)，記錄到羊皮紙的背面，同時(shí)告訴信使：告訴廖化P1提案我批準(zhǔn)了，我承諾編號(hào)小于101的提案不予理會(huì)。黃忠則不然，老將黃忠在9:20分時(shí)收到過(guò)魏延編號(hào)為110的提案，那時(shí)他批準(zhǔn)了，意味著，所有小于110的提案他都會(huì)拒絕掉。這次廖化的提案才101，當(dāng)然被拒絕掉了。三人的回復(fù)將于10:40會(huì)到達(dá)廖化處。

10：20分，魏延編號(hào)為110的P2提案到達(dá)趙云、馬超、黃忠，三人沒(méi)有疑問(wèn)，畢竟110編號(hào)最大，都表示批準(zhǔn)，并記錄(110,p2,110)到各自的羊皮紙背面，回復(fù)信使通過(guò)。

10：30分，周倉(cāng)收到了他在9：30分發(fā)給張飛的回復(fù)，張飛在10:00拒絕了，所以周倉(cāng)這個(gè)提案就此作廢。

10：40分，廖化收到了10：10來(lái)自關(guān)羽、張飛、黃忠的回復(fù)，關(guān)張二人批準(zhǔn)，然而老黃忠明確表示拒絕，于是這次編號(hào)101的提案作廢。

10：50分，魏延收到了趙云、馬超、黃忠的回復(fù)，三人都表示批準(zhǔn)，于是編號(hào)為110的提案p2最終作為法令記錄下來(lái)（之后的3b學(xué)習(xí)過(guò)程略過(guò)），從此以后，蜀國(guó)的路線被確立為走民主路線，許多年后，蜀國(guó)統(tǒng)一了銀河系。完。

以上任何步驟，大家可以任意制造難度，例如讓同一個(gè)信使重復(fù)投遞消息，或者延遲一天后消息到達(dá)某虎將處。或者讓某個(gè)虎將正常如廁，而后正常歸來(lái)。大家會(huì)發(fā)現(xiàn)，一致性是可以達(dá)到的，無(wú)論怎樣，對(duì)于同一個(gè)事件e，互相沖突的三個(gè)法案：p1,p1,p3，一定只有一個(gè)可以達(dá)成。

對(duì)于任一虎將兄的掛掉，我們要分情況。如果是去大便，那么他的羊皮紙是不能丟的。大便完了，可以正常回到自己的官署辦公。但是如果把羊皮紙丟了，那就不能立刻加入，必須向所有其他人學(xué)習(xí)，把失落的過(guò)程都學(xué)到，才能正常加入。這點(diǎn)至關(guān)重要，就是說(shuō)，只要硬盤不壞，隨時(shí)SERVER重啟都能加入。硬盤一壞，對(duì)不起，學(xué)習(xí)完了才能繼續(xù)辦公。

5、后記---Leslie的八卦：

paxos算法是解決分布式服務(wù)數(shù)據(jù)一致性的終極算法，google的基礎(chǔ)服務(wù)chubby（GFS的基礎(chǔ)服務(wù)）的開(kāi)發(fā)者說(shuō)， “there is only one consensus（一致性） protocol, and that’s Paxos”。Microsoft有fast paxos論文，yahoo的zookeeper也用了paxos算法。可見(jiàn)，paxos是解決完全的分布式服務(wù)（無(wú)單點(diǎn)）間數(shù)據(jù)一致性的最好方法。但是paxos比較復(fù)雜，特別是網(wǎng)上的中文資料里少有能說(shuō)得清楚的（主要是太多paxos變種算法了，摻合到一起攪得人頭大），例如中文wiki上的paxos解釋，光看這個(gè)是不可能搞懂paxos的。

paxos算法由Leslie Lamport在1990年提出，毫無(wú)疑問(wèn)，paxos想解決的就是分布式環(huán)境下（server會(huì)掛掉，通訊協(xié)議不可靠，消息可能延遲、丟失、重發(fā)）如何保持?jǐn)?shù)據(jù)一致性的問(wèn)題。Leslie Lamport同學(xué)在1982年提出的“拜占庭將軍”問(wèn)題上嘗到了甜頭，這也是個(gè)分布式環(huán)境下的一致性問(wèn)題，Leslie通過(guò)類比的方式，偽造了“拜占庭將軍”歷史，通過(guò)這種簡(jiǎn)單的類比成功的簡(jiǎn)化了復(fù)雜的分布式環(huán)境，效果非常好。于是在1990年Leslie同樣用類比的方式提出了paxos算法，該問(wèn)題跟“拜占庭將軍”問(wèn)題的區(qū)別是，“拜占庭將軍”允許有叛徒，也就是允許偽造消息（默許被黑客攻擊），而paxos則不允許消息被偽造。

Leslie很有幽默感的把論文寫成一個(gè)考古發(fā)現(xiàn)，至始至終都在虛構(gòu)他的“考古發(fā)現(xiàn)”。他說(shuō)在考古中發(fā)現(xiàn)了失落的文明：希臘的paxos小島。這里的議員通過(guò)郵遞員傳遞消息，議會(huì)中一個(gè)議員提出法案，多數(shù)議員批準(zhǔn)后法案獲得通過(guò)。當(dāng)然無(wú)論議員還是郵遞員，都是兼職的，他們不可靠，隨時(shí)可能走人，呵，典型的分布式環(huán)境，server可以掛，消息可以丟。Leslie根據(jù)考古文獻(xiàn)反推出了paxos議會(huì)如何搞定法案一致性的問(wèn)題。

發(fā)表論文時(shí)，Leslie一直用這種語(yǔ)氣在寫論文，于是《ACM Transactions on Computer Systems》編輯們認(rèn)為太荒誕了，不能從頭到尾虛構(gòu)故事吧？畢竟是嚴(yán)謹(jǐn)?shù)目茖W(xué)雜志，于是打回。Leslie同學(xué)身為牛人，堅(jiān)持自己的看法，同時(shí)認(rèn)為編輯們沒(méi)有幽默感，拒絕修改。時(shí)間流逝，一晃九年過(guò)去，九年后有團(tuán)隊(duì)根據(jù)該論文開(kāi)發(fā)出一個(gè)paxos實(shí)現(xiàn)，終于，編輯們低頭了，允許發(fā)布Leslie的論文，但還是加了段編者著，在其中表示Leslie其實(shí)是個(gè)熱愛(ài)計(jì)算機(jī)技術(shù)的考古學(xué)家！也算稍事解嘲。

寫這兩篇文章，我也試了下借喻的手段，用我們熟悉的三國(guó)人物，看看能否講清楚paxos。其實(shí)paxos的算法本身算不得很復(fù)雜，但如果想講清楚在各種異常情形下paxos算法的表現(xiàn)，給大家?guī)?lái)的明確的直觀感受：paxos確實(shí)能解決一致性問(wèn)題，這就不容易了。所以篇幅所限，只寫了丟失一個(gè)消息的情況。不過(guò)大家如果從頭看到這，應(yīng)該可以簡(jiǎn)單的任意推導(dǎo)出其他異常吧？

最后，上面說(shuō)的只是算法機(jī)制，如果需要了解現(xiàn)有的各種產(chǎn)品實(shí)現(xiàn)，最方便的還是看zookeeper源碼，畢竟是開(kāi)源的，例如去：http://zookeeper.apache.org/doc/r3.3.2/zookeeperOver.html，可以看下概述。淘寶開(kāi)發(fā)團(tuán)隊(duì)有許多關(guān)于zookeeper實(shí)現(xiàn)的文章，到網(wǎng)上搜下就能看到。

對(duì)google的chubby實(shí)現(xiàn)，因?yàn)椴皇情_(kāi)源的，只有篇論文可以看：http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/zh-CN/us/archive/chubby-osdi06.pdf

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



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

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

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

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

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



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

一、決策委員會(huì)里缺了哪個(gè)人都可以，蜀國(guó)照常做出決策。

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

三、若信使被馬車撞傷了，醫(yī)治后遲了幾個(gè)月才送到某人（例如法正），還不會(huì)出現(xiàn)政令不一致。

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



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

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



4、paxos執(zhí)行流程
劉備：“真爽，孔明你手感不錯(cuò)。說(shuō)點(diǎn)實(shí)在的吧，不懂的東西少扯。”
諸葛亮：“主公，你不懂?dāng)?shù)學(xué)嘛。好吧，我來(lái)說(shuō)說(shuō)paxos算法的流程，就三段式，六個(gè)步驟而已。角色包括，提案者，決策者，書記官（學(xué)習(xí)政令的）。
一、提案者先從主公那里搞到個(gè)獨(dú)一無(wú)二的編號(hào)，例如N。找到?jīng)Q策者們的多數(shù)派，就說(shuō)五虎將吧，找到三個(gè)肌肉男先。假設(shè)，這個(gè)提案者來(lái)自成都，想提的是，外地蜀國(guó)將級(jí)官員不得無(wú)故進(jìn)入魏國(guó)使者駐蜀驛館。那么，提案者發(fā)給三個(gè)五虎將，提案中說(shuō)，我現(xiàn)在有個(gè)編號(hào)N的提案，關(guān)于蜀國(guó)高級(jí)將領(lǐng)進(jìn)出魏國(guó)使者驛館的事，請(qǐng)回答我。”

二、五虎將們收到了關(guān)于使者驛館事件的提案，編號(hào)是N。其中任一個(gè)決策者，比如趙云，他在收到N提案后，首先檢查，之前關(guān)于魏國(guó)使者驛館事件，有沒(méi)有收到過(guò)提案啊？如果沒(méi)收到，當(dāng)然回復(fù)提案通過(guò)，同時(shí)趙云拿出自己的小本本記上，已經(jīng)回復(fù)編號(hào)N的提案。如果收到過(guò)關(guān)于驛館事件的編號(hào)M的提案，就檢查編號(hào)M，如果M大于N，那么跟信使說(shuō)，我拒絕這個(gè)提案。如果M小于N，回復(fù)通過(guò)，并且說(shuō)，關(guān)于這事，上次我已經(jīng)收到了編號(hào)M的提案了。

三、提案者如果收到多數(shù)決策者的通過(guò)回復(fù)，就開(kāi)始正式提議了。這時(shí)，先檢查五虎將的回復(fù)，如果都簡(jiǎn)單的回復(fù)通過(guò)，那么就正式提議之前想提議的《蜀國(guó)將級(jí)官員不得無(wú)故進(jìn)入魏國(guó)使者駐蜀國(guó)驛館》提案。如果決策者們不是簡(jiǎn)單的回復(fù)通過(guò)，而是說(shuō)：這次我趙云通過(guò)了，但是我曾經(jīng)回復(fù)過(guò)編號(hào)M的提案。這樣，提案者需要從這次決策者們的回復(fù)中，找出所有編號(hào)M中的最大值。假設(shè)就趙云復(fù)雜的回復(fù)了，其他四人都是簡(jiǎn)單的回復(fù)通過(guò)。那么，提案者這次不能正式提議自己原來(lái)想提的，而要提議編號(hào)M對(duì)應(yīng)的提案。

四、同第二步驟一樣，五虎將們根據(jù)二步驟的準(zhǔn)則，選擇通過(guò)還是不通過(guò)。
五、提案者如果發(fā)現(xiàn)多數(shù)決策者同意了，意味著法令通過(guò)，這時(shí)他要記錄法令，同時(shí)告訴書記官們。
六、書記官們?cè)谘蚱ぜ埳嫌涗浄睢?#8220;



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

Panic和Recover

Go沒(méi)有像Java那樣的異常機(jī)制，它不能拋出異常，而是使用了panic和recover機(jī)制。一定要記住，你應(yīng)當(dāng)把它作為最后的手段來(lái)使用，也就是說(shuō)，你的代碼中應(yīng)當(dāng)沒(méi)有，或者很少有panic的東西。這是個(gè)強(qiáng)大的工具，請(qǐng)明智地使用它。那么，我們應(yīng)該如何使用它呢？

Panic

是一個(gè)內(nèi)建函數(shù)，可以中斷原有的控制流程，進(jìn)入一個(gè)令人恐慌的流程中。當(dāng)函數(shù)F調(diào)用panic，函數(shù)F的執(zhí)行被中斷，但是F中的延遲函數(shù)會(huì)正常執(zhí)行，然后F返回到調(diào)用它的地方。在調(diào)用的地方，F的行為就像調(diào)用了panic。這一過(guò)程繼續(xù)向上，直到發(fā)生panic的goroutine中所有調(diào)用的函數(shù)返回，此時(shí)程序退出。恐慌可以直接調(diào)用panic產(chǎn)生。也可以由運(yùn)行時(shí)錯(cuò)誤產(chǎn)生，例如訪問(wèn)越界的數(shù)組。

Recover

是一個(gè)內(nèi)建的函數(shù)，可以讓進(jìn)入令人恐慌的流程中的goroutine恢復(fù)過(guò)來(lái)。recover僅在延遲函數(shù)中有效。在正常的執(zhí)行過(guò)程中，調(diào)用recover會(huì)返回nil，并且沒(méi)有其它任何效果。如果當(dāng)前的goroutine陷入恐慌，調(diào)用recover可以捕獲到panic的輸入值，并且恢復(fù)正常的執(zhí)行。

下面這個(gè)函數(shù)演示了如何在過(guò)程中使用panic

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

下面這個(gè)函數(shù)檢查作為其參數(shù)的函數(shù)在執(zhí)行時(shí)是否會(huì)產(chǎn)生panic：

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

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

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) } 

執(zhí)行結(jié)果：

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

如上面所說(shuō)的：

panic在user=""時(shí)，打斷了函數(shù)的執(zhí)行，fmt.Print("!!after panic\n")沒(méi)有執(zhí)行。 但函數(shù)中的延遲函數(shù)會(huì)正常執(zhí)行，打印了 defer##。然后返回到調(diào)用該函數(shù)的地方，繼續(xù)上面的過(guò)程。

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