Wikipedia上的各種Paxos算法的描述非常詳細，大家可以去圍觀一下。
Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議的一致性。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個「一致性算法」以保證每個節點看到的指令一致。一個通用的一致性算法可以應用在許多場景中，是分布式計算中的重要問題。從20世紀80年代起對於一致性算法的研究就沒有停止過。
Notes：Paxos算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的」La」，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞的一致性算法。由於算法難以理解起初並沒有引起人們的重視，使Lamport在八年後1998年重新發表到ACM Transactions on Computer Systems上。即便如此paxos算法還是沒有得到重視，2001年Lamport 覺得同行無法接受他的幽默感，於是用容易接受的方法重新表述了一遍。可見Lamport對Paxos算法情有獨鍾。近幾年Paxos算法的普遍使用也證明它在分布式一致性算法中的重要地位。2006年Google的三篇論文初現「雲」的端倪，其中的Chubby Lock服務使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。（Lamport 本人在他的blog 中描寫了他用9年時間發表這個算法的前前後後）
註：Amazon的AWS中，所有的雲服務都基於一個ALF（Async Lock Framework）的框架實現的，這個ALF用的就是Paxos算法。我在Amazon的時候，看內部的分享視頻時，設計者在內部的Principle Talk裡說他參考了ZooKeeper的方法，但他用了另一種比ZooKeeper更易讀的方式實現了這個算法。
簡單說來，Paxos的目的是讓整個集群的結點對某個值的變更達成一致。Paxos算法基本上來說是個民主選舉的算法——大多數的決定會成個整個集群的統一決定。任何一個點都可以提出要修改某個數據的提案，是否通過這個提案取決於這個集群中是否有超過半數的結點同意（所以Paxos算法需要集群中的結點是單數）。
這個算法有兩個階段（假設這個有三個結點：A，B，C）：
第一階段：Prepare階段
A把申請修改的請求Prepare Request發給所有的結點A，B，C。注意，Paxos算法會有一個Sequence Number（你可以認為是一個提案號，這個數不斷遞增，而且是唯一的，也就是說A和B不可能有相同的提案號），這個決議號會和修改請求一同發出，任何結點在「Prepare階段」時都會拒絕其實小於當前提案號的請求。所以，結點A在向所有結點申請修改請求的時候，需要帶一個提案號，越新的提案，這個提案號就越是是最大的。
如果接收結點收到的提案號n大於其它結點發過來的提案號，這個結點會回應Yes（本結點上最新的被批准提案號），並保證不接收其它<n的提案。這樣一來，結點上在Prepare階段裡總是會對最新的提案做承諾。
優化：在上述 prepare 過程中，如果任何一個結點發現存在一個更高編號的提案，則需要通知 提案人，提醒其中斷這次提案。
第二階段：Accept階段
如果提案者A收到了超過半數的結點返回的Yes，然後他就會向所有的結果發布Accept Request（同樣，需要帶上提案號n），如果沒有超過半數的話，那就返回失敗。
當結點們收到了Accept Request後，如果對於接收的結果來說，n是最大的了，那麼，它就會修改這個值，如果發現自己有一個更大的提案號，那麼，結點就會拒絕修改。
我們可以看以，這似乎就是一個「兩段提交」的優化。其實，2PC/3PC都是分布式一致性算法的殘次版本，Google Chubby的作者Mike Burrows說過這個世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。
我們還可以看到：對於同一個值的在不同結點的修改提案就算是在接收方被亂序收到也是沒有問題的。
關於一些實例，你可以看一下Wikipedia中文中的「Paxos樣例」一節，我在這裡就不再多說了。對於Paxos算法中的一些異常示例，大家可以自己推導一下。你會發現基本上來說只要保證有半數以上的結點存活，就沒有什麼問題。
多說一下，自從Lamport在1998年發表Paxos算法後，對Paxos的各種改進工作就從未停止，其中動作最大的莫過於2005年發表的Fast Paxos。無論何種改進，其重點依然是在消息延遲與性能、吞吐量之間作出各種權衡。為了容易地從概念上區分二者，稱前者Classic Paxos，改進後的後者為Fast Paxos。
下圖來自：Google App Engine的co-founder Ryan Barrett在2009年的google i/o上的演講:
前面，我們說過，要想讓數據有高可用性，就需要冗餘數據寫多份。寫多份的問題會帶來一致性的問題，而一致性的問題又會帶來性能問題。從上圖我們可以看到，我們基本上來說不可以讓所有的項都綠起來，這就是著名的CAP理論：一致性，可用性，分區容忍性，你可以要其中的兩個。
最後我還想提一下Amazon Dynamo的NWR模型。這個NWR模型把CAP的選擇權交給了用戶，讓用戶自己的選擇你的CAP中的哪兩個。
所謂NWR模型。N代表N個備份，W代表要寫入至少W份才認為成功，R表示至少讀取R個備份。配置的時候要求W+R > N。 因為W+R > N， 所以 R > N-W 這個是什麼意思呢？就是讀取的份數一定要比總備份數減去確保寫成功的倍數的差值要大。
也就是說，每次讀取，都至少讀取到一個最新的版本。從而不會讀到一份舊數據。當我們需要高可寫的環境的時候，我們可以配置W = 1 如果N=3 那麼R = 3。 這個時候只要寫任何節點成功就認為成功，但是讀的時候必須從所有的節點都讀出數據。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個時候任何一個節點讀成功就認為成功，但是寫的時候必須寫所有三個節點成功才認為成功。
NWR模型的一些設置會造成髒數據的問題，因為這很明顯不是像Paxos一樣是一個強一致的東西，所以，可能每次的讀寫操作都不在同一個結點上，於是會出現一些結點上的數據並不是最新版本，但卻進行了最新的操作。
所以，Amazon Dynamo引了數據版本的設計。也就是說，如果你讀出來數據的版本是v1，當你計算完成後要回填數據後，卻發現數據的版本號已經被人更新成了v2，那麼伺服器就會拒絕你。版本這個事就像「樂觀鎖」一樣。
但是，對於分布式和NWR模型來說，版本也會有惡夢的時候——就是版本衝的問題，比如：我們設置了N=3 W=1，如果A結點上接受了一個值，版本由v1 -> v2，但還沒有來得及同步到結點B上（異步的，應該W=1，寫一份就算成功），B結點上還是v1版本，此時，B結點接到寫請求，按道理來說，他需要拒絕掉，但是他一方面並不知道別的結點已經被更新到v2，另一方面他也無法拒絕，因為W=1，所以寫一分就成功了。於是，出現了嚴重的版本衝突。
Amazon的Dynamo把版本衝突這個問題巧妙地迴避掉了——版本衝這個事交給用戶自己來處理。
於是，Dynamo引入了Vector Clock（矢量鍾？!）這個設計。這個設計讓每個結點各自記錄自己的版本信息，也就是說，對於同一個數據，需要記錄兩個事：1）誰更新的我，2）我的版本號是什麼。
下面，我們來看一個操作序列：
6.這個時候可以判斷出，D2已經是舊版本（已經包含在D3/D4中），可以捨棄。
7.但是D3和D4是明顯的版本衝突。於是，交給調用方自己去做版本衝突處理。就像原始碼版本管理一樣。
很明顯，上述的Dynamo的配置用的是CAP裡的A和P。
原文連結：分布式系統的事務處理（責編：仲浩）