在分布式算法領(lǐng)域，有個(gè)非常重要的算法叫Paxos, 它的重要性有多高呢，Google的Chubby [1]中提到

all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

關(guān)于Paxos算法的詳述在維基百科中有更多介紹，中文版介紹的是choose value的規(guī)則[2]，英文版介紹的是Paxos 3 phase commit的流程[3]，中文版不是從英文版翻譯而是獨(dú)立寫的，所以非常具有互補(bǔ)性。Paxos算法是由Leslie Lamport提出的，他在Paxos Made Simple[4]中寫道

The Paxos algorithm, when presented in plain English, is very simple.

當(dāng)你研究了很長一段時(shí)間Paxos算法還是有點(diǎn)迷糊的時(shí)候，看到上面這句話可能會(huì)有點(diǎn)沮喪。但是公認(rèn)的它的算法還是比較繁瑣的，尤其是要用程序員嚴(yán)謹(jǐn)?shù)乃季S將所有細(xì)節(jié)理清的時(shí)候，你的腦袋里更是會(huì)充滿了問號(hào)。Leslie Lamport也是用了長達(dá)9年的時(shí)間來完善這個(gè)算法的理論。

實(shí)際上對(duì)于一般的開發(fā)人員，我們并不需要了解Paxos所有細(xì)節(jié)及如何實(shí)現(xiàn)，只需要知道Paxos是一個(gè)分布式選舉算法就夠了。本文主要介紹一下Paxos常用的應(yīng)用場(chǎng)合，或許有一天當(dāng)你的系統(tǒng)增大到一定規(guī)模，你知道有這樣一個(gè)技術(shù)，可以幫助你正確及優(yōu)雅的解決技術(shù)架構(gòu)上一些難題。

1. database replication, log replication等， 如bdb的數(shù)據(jù)復(fù)制就是使用paxos兼容的算法。Paxos最大的用途就是保持多個(gè)節(jié)點(diǎn)數(shù)據(jù)的一致性。

2. naming service, 如大型系統(tǒng)內(nèi)部通常存在多個(gè)接口服務(wù)相互調(diào)用。 
1) 通常的實(shí)現(xiàn)是將服務(wù)的ip/hostname寫死在配置中，當(dāng)service發(fā)生故障時(shí)候，通過手工更改配置文件或者修改DNS指向的方法來解決。缺點(diǎn)是可維護(hù)性差，內(nèi)部的單元越多，故障率越大。 
2) LVS雙機(jī)冗余的方式，缺點(diǎn)是所有單元需要雙倍的資源投入。 
通過Paxos算法來管理所有的naming服務(wù)，則可保證high available分配可用的service給client。象ZooKeeper還提供watch功能，即watch的對(duì)象發(fā)生了改變會(huì)自動(dòng)發(fā)notification, 這樣所有的client就可以使用一致的，高可用的接口。

3.config配置管理 
1) 通常手工修改配置文件的方法，這樣容易出錯(cuò)，也需要人工干預(yù)才能生效，所以節(jié)點(diǎn)的狀態(tài)無法同時(shí)達(dá)到一致。 
2) 大規(guī)模的應(yīng)用都會(huì)實(shí)現(xiàn)自己的配置服務(wù)，比如用http web服務(wù)來實(shí)現(xiàn)配置中心化。它的缺點(diǎn)是更新后所有client無法立即得知，各節(jié)點(diǎn)加載的順序無法保證，造成系統(tǒng)中的配置不是同一狀態(tài)。

4.membership用戶角色/access control list, 比如在權(quán)限設(shè)置中，用戶一旦設(shè)置某項(xiàng)權(quán)限比如由管理員變成普通身份，這時(shí)應(yīng)在所有的服務(wù)器上所有遠(yuǎn)程CDN立即生效，否則就會(huì)導(dǎo)致不能接受的后果。

5. 號(hào)碼分配。通常簡單的解決方法是用數(shù)據(jù)庫自增ID, 這導(dǎo)致數(shù)據(jù)庫切分困難，或程序生成GUID, 這通常導(dǎo)致ID過長。更優(yōu)雅的做法是利用paxos算法在多臺(tái)replicas之間選擇一個(gè)作為master, 通過master來分配號(hào)碼。當(dāng)master發(fā)生故障時(shí)，再用paxos選擇另外一個(gè)master。

這里列舉了一些常見的Paxos應(yīng)用場(chǎng)合，對(duì)于類似上述的場(chǎng)合，如果用其它解決方案，一方面不能提供自動(dòng)的高可用性方案，同時(shí)也遠(yuǎn)遠(yuǎn)沒有Paxos實(shí)現(xiàn)簡單及優(yōu)雅。

Yahoo!開源的ZooKeeper [5]是一個(gè)開源的類Paxos實(shí)現(xiàn)。它的編程接口看起來很像一個(gè)可提供強(qiáng)一致性保證的分布式小文件系統(tǒng)。對(duì)上面所有的場(chǎng)合都可以適用。但可惜的是，ZooKeeper并不是遵循Paxos協(xié)議，而是基于自身設(shè)計(jì)并優(yōu)化的一個(gè)2 phase commit的協(xié)議，因此它的理論[6]并未經(jīng)過完全證明。但由于ZooKeeper在Yahoo!內(nèi)部已經(jīng)成功應(yīng)用在HBase, Yahoo! Message Broker, Fetch Service of Yahoo! crawler等系統(tǒng)上，因此完全可以放心采用。

另外選擇Paxos made live [7]中一段實(shí)現(xiàn)體會(huì)作為結(jié)尾。

*  There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol. 
* 由于chubby填補(bǔ)了Paxos論文中未提及的一些細(xì)節(jié)，所以最終的實(shí)現(xiàn)系統(tǒng)不是一個(gè)理論上完全經(jīng)過驗(yàn)證的系統(tǒng)

* The fault-tolerance computing community has not developed the tools to make it easy to implement their algorithms. 
* 分布式容錯(cuò)算法領(lǐng)域缺乏幫助算法實(shí)現(xiàn)的的配套工具, 比如編譯領(lǐng)域盡管復(fù)雜，但是yacc, ANTLR等工具已經(jīng)將這個(gè)領(lǐng)域的難度降到最低。

* The fault-tolerance computing community has not paid enough attention to testing, a key ingredient for building fault-tolerant systems. 
* 分布式容錯(cuò)算法領(lǐng)域缺乏測(cè)試手段

這里要補(bǔ)充一個(gè)背景，就是要證明分布式容錯(cuò)算法的正確性通常比實(shí)現(xiàn)算法還困難，Google沒法證明Chubby是可靠的，Yahoo!也不敢保證它的ZooKeeper理論正確性。大部分系統(tǒng)都是靠在實(shí)踐中運(yùn)行很長一段時(shí)間才能謹(jǐn)慎的表示，目前系統(tǒng)已經(jīng)基本沒有發(fā)現(xiàn)大的問題了。

Resources 
[1] The Chubby lock service for loosely-coupled distributed systems (PDF) 
[2] http://zh./wiki/Paxos算法 
[3] http://en./wiki/Paxos_algorithm 
[4] Paxos Made Simple (PDF) 
[5] ZooKeeper 
[6] The life and times of a zookeeper 
[7] Paxos Made Live - An Engineering Perspective (PDF)