咖啡伴侶

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



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

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

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

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

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



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

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

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

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

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



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

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



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

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

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

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



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