自Paxos提出，迄今已有20多年了，圍繞著該算法曾經(jīng)發(fā)生過一些非常有趣的事情，這些也已成為人們津津樂道的一段軼事，故事的主角自然是Paxos的提出者Lamport，當(dāng)然Lamport的特立獨(dú)行也是很早就出了名的。首先來講述下這些有趣的八卦，之后會再理一下Paxos的整個發(fā)展過程，以及在這個過程中產(chǎn)生的一系列比較重要的論文，總共會涉及到十幾篇論文，如果有時間還是最好都研讀一下。由于時間關(guān)系，我也只是選擇了其中最為重要的三篇，進(jìn)行了閱讀，并將它們翻譯了出來，稍后會整理出來。 

關(guān)于這段歷史， Lamport本人在他的“My Writings”里對于論文<<The Part-Time Parliament>>的整個從創(chuàng)作到發(fā)表的過程，也做過非常詳細(xì)的描述。我們還是先從這里開始吧。

“上世紀(jì)80年代末，SRC(Systems Research Center，DEC于1984年創(chuàng)立，Lamport也曾在此工作過)構(gòu)建了一個被稱為ECHO的容錯文件系統(tǒng)。該系統(tǒng)的構(gòu)建者們聲稱，系統(tǒng)可以保證在發(fā)生任意數(shù)目的非拜占庭式錯誤情況下的一致性，并且只要有半數(shù)以上的進(jìn)程可以正常工作，它就可以保證系統(tǒng)向前運(yùn)轉(zhuǎn)。對于大多數(shù)像這樣的系統(tǒng)來說，在沒有錯誤發(fā)生的時候都是很簡單的，但是要處理好實現(xiàn)者所有能夠想到的各種錯誤的話，是需要一個非常復(fù)雜的算法的。我感覺他們在做的事情基本上是不可能的，并打算去證明它。結(jié)果事與愿違，在這個過程中我發(fā)現(xiàn)了Paxos算法，也就是本文描述的那個。該算法的核心實際上是一個三階段的一致性協(xié)議。Dale Skeen應(yīng)該是第一個意識到為避免任意可能的單點失敗引起的阻塞需要引入三階段協(xié)議的人。但是，據(jù)我所知，Paxos是第一個具有清晰正確性條件說明及完整正確性證明的真正意義上的三階段提交算法。

無論那時，還是現(xiàn)在，我一直認(rèn)為Paxos是一個非常重要的算法。在寫此文之前，我通過采用拜占庭將軍的描述方法使得一致性問題成功地被人們所接受(即論文The Byzantine General Problem)，受此啟發(fā)，我決定通過一個古希臘島嶼上的議會來描述該算法。Leo Guibas提議將這個島命名為Paxos。我又用工作在該領(lǐng)域的計算機(jī)科學(xué)家的名字對里面的希臘議員進(jìn)行命名，并在 Guibas的幫助下翻譯成了偽造的希臘方言。(論文題目是由Peter Ladkin提議的)。通過描述一個失落的文明，既增加趣味性又可以讓我免于陳述其中乏味的細(xì)節(jié)，只要直接聲明一下關(guān)于該議會協(xié)議的某些細(xì)節(jié)已經(jīng)遺失就可以了。為了讓這種形象化的描述更逼真，我還戴上了Stetson氈帽屁股系上了小酒瓶裝扮成印第安納瓊斯style的考古學(xué)家，進(jìn)行了幾次演講。

只是我這種嘗試不幸地失敗了。那些參加我演講的人們只記住了印第安納瓊斯style，而不是該算法。閱讀該論文的人們看起來也飽受里面的希臘故事的干擾以至于根本沒有理解該算法。在我發(fā)論文給他們閱讀的那些人中，其中 Nancy Lynch(分布式理論研究大牛，<<Distributed Algorithms>> 一書作者), Vassos Hadzilacos, 和Phil Bernstein聲稱已經(jīng)讀完。大概兩個月后，我給他們發(fā)了封郵件，郵件內(nèi)容為“是否能夠?qū)崿F(xiàn)一個可以容忍任意數(shù)目(可能是所有)的進(jìn)程出錯且能保持一致性的分布式數(shù)據(jù)庫，同時當(dāng)半數(shù)以上進(jìn)程恢復(fù)正常時該系統(tǒng)也能夠恢復(fù)正?！薄５撬麄儾]有人意識到該問題與Paxos算法間的關(guān)聯(lián)。

我在1990將該論文提交給了TOCS。三個審稿者都認(rèn)為該論文盡管并不重要但還有些意思，只是應(yīng)該把其中所有Paxos相關(guān)的內(nèi)容刪掉。在該領(lǐng)域工作的人們?nèi)绱巳狈τ哪?，實在令人生氣，此后我也沒有對該論文做任何修改。很多年后，在SRC工作的兩個人需要為他們正在構(gòu)建的分布式系統(tǒng)尋找一些合適算法，而Paxos恰恰提供了他們想要的。我就將論文發(fā)給他們，他們也沒覺得該論文有什么問題。下面是Chandu Thekkath所講述的Paxos在SRC的歷史：

“在Ed Lee和我從事Petal相關(guān)的工作時，我們需要一種提交協(xié)議來確保分布式系統(tǒng)中的全局操作即使是在發(fā)生故障的情況下也能保證正確性。我們了解到一些3PC的概念，并閱讀了Bernstein, Hadzilacos和 Goodman的經(jīng)典書籍<<Concurrency Control and Recovery in Database Systems>>，對其進(jìn)行了研究。我們發(fā)現(xiàn)這個協(xié)議有些難以理解，于是放棄了對它進(jìn)行實現(xiàn)的嘗試。大概也是在這個時間，Mike Schroeder與我們談起Leslie Lamport 曾經(jīng)發(fā)明了一個一致性方面的協(xié)議并建議我們直接問下Leslie本人。后來Leslie給了Ed一份<<The Part-Time Parliament>>文章的拷貝，我們兩都讀地很happy。我尤其喜歡其中的幽默，直到今天也無法理解為什么人們都不太喜歡這篇文章。Paxos具備我們的系統(tǒng)所需要的所有屬性，同時我們也覺得能夠?qū)⑺鼘崿F(xiàn)出來。此外Leslie還為我們提供了很多咨詢幫助，這樣就產(chǎn)生了我所知的Paxos算法的第一個實現(xiàn)(包含了動態(tài)重配置)。一年后，我們又用Paxos實現(xiàn)了Frangipani file system所需的分布式鎖服務(wù)器”

因此，我覺得重新發(fā)表該論文的時機(jī)到了。

與此同時，在整個悲催的經(jīng)歷中(指論文一開始被拒，沒有人重視)，Butler W.Lampson(1992年圖靈獎得主)是一個例外，他立刻意識到這個算法的重要性，并在他的演講和一篇論文(即<<How to Build a Highly Availability System using Consensus>>)中對該算法進(jìn)行了描述，這引起了Nancy Lynch的關(guān)注。此后De Prisco, Lynch和Lampson發(fā)表了他們那個版本的描述和證明(即<<Revisiting the PAXOS algorithm>>)。他們那篇論文的發(fā)表更使我確信是時候發(fā)表我的這篇論文了。于是我提議當(dāng)時TOCS的編輯Ken Birman發(fā)表該論文。他建議我再修改下，比如添加一個關(guān)于該算法的TLA描述。但是重讀該論文后，我更確信其中的描述和證明已經(jīng)足夠清晰，根本不需要再做改動。誠然，該論文可能需要參考下最近這些年發(fā)表的研究成果進(jìn)行修訂。但是一方面作為一種joke式的延續(xù)，另一方面為保存原有工作，我建議不是再寫一個修訂版本，而是以一個被最近發(fā)現(xiàn)的手稿的形式公布，再由Keith Marzullozz做注。Keith Marzullo很樂意這樣干，Birman也同意了，最終該論文得以重見天日。

這樣該論文就有了一些有趣的排版注腳{!即論文<<The Part-Time Parliament>>里Keith Marzullo的那些注，具體內(nèi)容見原文}。為了讓Marzullo的注解更顯眼，我認(rèn)為它們應(yīng)該印在一個灰色背景上。那時ACM剛獲取了一些非常棒的排版軟件，同時TOCS也準(zhǔn)備不再接收camera-ready copy。不幸的是，他們的新軟件做不出陰影效果。于是，我不得不為那段文字提供一個camera-ready copy。但是，他們的那個牛逼軟件只能以漂浮圖的形式接收我提供的這個拷貝，因此Marzullo的注釋的畫面效果看起來可能并不理想。還有更不幸的是，他們那個超級昂貴的軟件竟然不支持?jǐn)?shù)學(xué)公式。(好吧，畢竟他們是一家計算機(jī)期刊，so可能不需要對公式排版吧…)。因此我又不得不為A2節(jié)里的不變性定義提供一個camera-ready copy，在發(fā)表的版本里他們將它作為了圖3。這就是那張圖里的字體看起來與其他部分的字體并不匹配的原因。

該論文獲得了2012年的ACM SIGOPS Hall of Fame Award{!是不是很熟悉，之前介紹過的Lamport的另一篇文章<<Time Clocks and the Ordering of Events in a Distributed System>>就獲得了2007年的該獎項。該獎項始創(chuàng)于2005年，主要頒發(fā)給那些在操作系統(tǒng)領(lǐng)域產(chǎn)生了深遠(yuǎn)影響的論文，這些論文都至少經(jīng)過了十年的檢驗。獲獎結(jié)果將會在每年的OSDI或SOSP(操作系統(tǒng)領(lǐng)域頂級會議，通常是偶數(shù)年開OSDI，奇數(shù)年開SOSP)上宣布。今年的OSDI上除Lamport的這篇獲獎外，Liskov(2008年圖靈獎得主，她導(dǎo)師是1971年圖靈獎得主John McCarthy)1988年寫的<<Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems>>也是獲獎?wù)撐?，這兩篇都是Paxos相關(guān)的。}

”

從上面可以看到，在Lamport的各種挖坑和吐槽下，已有無數(shù)人中槍，連ACM的排版軟件也不能幸免(好吧，其實此處Lamport有為他的LaTeX打廣告之嫌)。關(guān)于該論文的整個曲折的發(fā)表過程就是這樣的。另外值得關(guān)注的是SRC，它的Petal和Frangipani是不是非常類似于Google的某些東西啊，而且在<<The Part-Time Parliament>>發(fā)表前，這些系統(tǒng)就已經(jīng)完成了Paxos的實現(xiàn)。

現(xiàn)在我們重新回到Paxos。它的整個發(fā)展過程實際上大概可以分為三個階段。

第一個階段，為算法創(chuàng)立階段，基本就是88年和89年，代表性事件是88年Liskov發(fā)表 <<Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems>>，89年Lamport寫出了<<The Part-Time Parliament>>，并在90年將它提交給TOCS。這兩篇都是獨(dú)立完成的，而且Liskov那篇還要早些，但是因為上述種種軼事，大家最終還是稱之為Paxos，而且在Paxos的盛名下，Liskov那篇估計更少有人知道了。最早指出二者本質(zhì)上是一樣的人是Butler Lampson。在這個階段，這兩篇論文基本上都還沒有人關(guān)注。當(dāng)然這兩篇論文的殊途同歸，也從一個側(cè)面說明解決異步一致性問題基本上也沒有其他的路子可走。

第二個階段，可以從開始引起理論研究界的重視算起。代表性事件是96年Butler Lampson發(fā)表<<How to Build a Highly Availability System using Consensus>>。正是經(jīng)過Lampson的大力宣傳，該算法才逐漸為理論研究界的人們所重視，也直接導(dǎo)致了The Part-Time Parliament的重新發(fā)表。為啥當(dāng)年Lamport一方面費(fèi)盡心機(jī)地扮考古學(xué)家，另一方面千辛萬苦把論文寫的那么幽默，都沒能讓理論界的人們看上眼，而Lampson振臂一揮，就有無數(shù)響應(yīng)呢？這可能是因為天時、地利、人和吧，從時間上來看，此時人們對于一個分布式一致性算法的需求日益緊迫，而且與Lamport相比，Lampson明顯說話還是要更有分量些，Lampson 92年就拿到了圖靈獎，江湖地位自然高些，而且他更善于把復(fù)雜的問題講清楚，另外還有就是功力的確深厚，就算Lamport這樣的人物對其也是佩服得不行。這篇論文發(fā)表之后，后續(xù)便引出了一系列關(guān)于Paxos的研究。1999年，De Prisco, Lynch和Lampson聯(lián)合在TCS(Theoretical Computer Science)發(fā)表了<<Revisiting the PAXOS algorithm>>對Paxos算法進(jìn)行了全新的描述及證明，分析了其時間開銷及容錯性。2001年，Lampson又寫了一篇<<The ABCD’s of Paxos>>對Paxos的各種不同形式進(jìn)行了描述，包括AP：Abstract Paxos；BP：Byzantine Paxos；CP：Classic Paxos；DP：Disk Paxos，發(fā)表在PODC’01上。也是在這一年，在參加PODC會議時，Lamport發(fā)現(xiàn)人們還是覺得Paxos很難理解，于是回家后對Paxos進(jìn)行了重新描述和表達(dá)后，形成了<<Paxos Made Simple>>這篇文章，而這篇文章基本上就是The Part-Time Parliament的一個簡化版本?？梢钥闯觯搅?001年，Paxos已經(jīng)成為理論界關(guān)注的熱點。此后的2004年，Lamport寫了篇<<Cheap Paxos>>，2005年又寫了篇<<Fast Paxos>>，對經(jīng)典Paxos算法進(jìn)行了改進(jìn)。

第三個階段，由Google發(fā)表的兩篇論文開啟，也是從那時起Paxos開始從理論界進(jìn)入工業(yè)實踐，并被越來越多的工程技術(shù)人員所熟知。2006年，Google有兩篇論文發(fā)表在OSDI上，一篇是<<Bigtable:A Distributed Storage System for Structured Data>>，另一篇就是<<The Chubby lock service for loosely-coupled distributed systems>>，而在Chubby這篇中有這樣一段話“Indeed, all working protocols for asynchronous consensus we have so far encountered have Paxos at their core”。另外還有一句流傳甚廣的話，“世上只有一種一致性算法，那就是Paxos—Mike Burrows”，這句話可能是出于這篇文章<<Consensus Protocols: Two-Phase Commit>>，是否為Mike Burrows的原話就不得而知了，但是Chubby中的那句的確與這話十分接近。Chubby發(fā)表之后，開源社區(qū)也推出了與之對應(yīng)的Zookeeper。此后，Paxos逐步為大眾所了解，至少聽說過的人越來越多了。Google除了Chubby那篇，當(dāng)然實際上Chubby并未講述Paxos相關(guān)的內(nèi)容，還有另一篇非常好的文章<<Paxos Made Live>>，這篇文章詳細(xì)解釋了Google實現(xiàn)Paxos中越到的各種問題及解決方案，講述了如何將理論應(yīng)用到實踐，而二者之間通常都是具有很大的鴻溝的,尤其是在分布式系統(tǒng)領(lǐng)域，往往都是理想豐滿現(xiàn)實悲慘。其實這篇已經(jīng)完全超越了Paxos算法本身，重要的不是如何實現(xiàn)Paxos(實際上大多數(shù)人都不需要實現(xiàn)Paxos)，而是應(yīng)理解如何將理論應(yīng)用到實踐，如何彌補(bǔ)理論與實踐的差異，如何進(jìn)行分布式系統(tǒng)的工程實現(xiàn)，如何進(jìn)行分布式系統(tǒng)的測試，而實踐中的很多問題理論界并沒有給出答案。 

另外，如果要自己實現(xiàn)Paxos，還有如下幾篇文章可供參考：<<Paxos Made Code>>作者M(jìn)acro Primi，他實現(xiàn)了一個Paxos開源庫libpaxos，更多信息可以參考此處。<<Paxos for System Builders>>以一個系統(tǒng)實現(xiàn)者的角度討論了實現(xiàn)Paxos的諸多具體問題，比如leader選舉，數(shù)據(jù)及消息類型，流控等。<<Paxos Made Moderately Complex>>，這篇比較新，2011年才發(fā)表的，該文章介紹了很多實現(xiàn)細(xì)節(jié)，并提供了很多偽代碼，一方面可以幫助理解Paxos，另一方面也可以據(jù)此實現(xiàn)一個Paxos。<<Paxos Made Practical>>是少有的一篇對Liskov的那篇論文進(jìn)行重新解讀的文章，主要介紹如何采用Paxos實現(xiàn)replication，如果要讀Liskov的那篇，也可以同時參考這篇。除了Macro Primi的那個開源實現(xiàn)外，目前還可以找到如下一些Paxos實現(xiàn)的代碼：Java版，Python版。

關(guān)于Paxos的介紹，這兩篇文章也非常不錯：<<Consensus Protocols: Paxos>>，<<Consensus>>。