網路上有很多關於優秀的關於Paxos 演算法的文章，我下麵進行整理搜集一下： 分散式理論之一：Paxos演算法的通俗理解 維基的簡介：Paxos演算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞且具有高度容錯特性的 ...
網路上有很多關於優秀的關於Paxos 演算法的文章，我下麵進行整理搜集一下：
分散式理論之一：Paxos演算法的通俗理解
維基的簡介：Paxos演算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人現在在微軟研究院）於1990年提出的一種基於消息傳遞且具有高度容錯特性的一致性演算法。
Paxos演算法目前在Google的Chubby、MegaStore、Spanner等系統中得到了應用，Hadoop中的ZooKeeper也使用了Paxos演算法，在上面的各個系統中，使用的演算法與Lamport提出的原始Paxos並不完全一樣，這個以後再慢慢分析。本博文的目的是，如何讓一個小白在半個小時之內理解Paxos演算法的思想。小白可能對數學不感興趣，對分散式的複雜理論不熟悉，只是一個入門級程式員。之所以想寫這篇博文，是因為自己看了網上很多介紹Paxos演算法的文章，以及博客，包括Lamport的論文，感覺還是難以理解，大多過於複雜，本人一直認為，複雜高深的理論背後一定基於一些通用的規律，而這些通用的規律在生活中其實我們早就遇到過，甚至用過。所以，我們先忽略Paxos演算法本身，從生活中的小事開始談起。
假如有一群驢友要決定中秋節去旅游，這群驢友分佈在全國各地，假定一共25個人，分別在不同的省，要決定到底去拉薩、昆明、三亞等等哪個地點（會合時間中秋節已經定了，此時需要決定旅游地）。最直接的方式當然就是建一個QQ群，大家都在裡面投票，按照少數服從多數的原則。這種方式類似於“共用記憶體”實現的一致性，實現起來簡單，但Paxos演算法不是這種場景，因為Paxos演算法認為這種方式有一個很大的問題，就是QQ伺服器掛掉怎麼辦？Paxos的原則是容錯性一定要很強。所以，Paxos的場景類似於這25個人相互之間只能發簡訊，需要解決的核心問題是，哪怕任意的一部分人（Paxos的目的其實是少於半數的人）“失聯”了，其它人也能夠在會合地點上達成一致。好了，怎麼設計呢？
這25個人找了另外的5個人（當然這5個人可以從25個人中選，這裡為了描述方便，就單拿出另外5個人），比如北京、上海、廣州、深圳、成都的5個人，25個人都給他們發簡訊，告訴自己傾向的旅游地。這5個人相互之間可以並不通信，只接受25個人發過來的簡訊。這25個人我們稱為驢友，那5個人稱為隊長。
先來看驢友的邏輯。驢友可以給任意5個隊長都發簡訊，發簡訊的過程分為兩個步驟：
第一步（申請階段）：詢問5個隊長，試圖與隊長溝通旅游地。因為每個隊長一直會收到不同驢友的簡訊，不能跟多個驢友一起溝通，在任何時刻只能跟一個驢友溝通，按照什麼原則才能做到公平公正公開呢？這些簡訊都帶有發送時間，隊長採用的原則是同意與簡訊發送時間最新的驢友溝通，如果出現了更新的簡訊，則與簡訊更新的驢友溝通。總之，作為一個有話語權的人，只有時刻保持傾聽最新的呼聲，才能做出最明智的選擇。在驢友發出簡訊後，等著隊長回覆。某些隊長可能會回覆說，你這條簡訊太老了，我不與你溝通；有些隊長則可能返回說，你的簡訊是我收到的最新的，我同意跟你溝通。對於後面這些隊長，還得返回自己決定的旅游地。關於隊長是怎麼決定旅游地的，後面再說。
對於驢友來說，第一步必須至少有半數以上隊長都同意溝通了，才能進入下一步。否則，你連溝通的資格都沒有，一直在那兒狂發吧。你發的簡訊更新，你獲得溝通權的可能性才更大。。。。。。
因為至少有半數以上隊長（也就是3個隊長以上）同意，你才能與隊長們進行實質性的溝通，也就是進入第二步；而隊長在任何時候只能跟1個驢友溝通，所以，在任何時候，不可能出現兩個驢友都達到了這個狀態。。。當然，你可以通過狂發簡訊把溝通權搶了。。。。
對於獲得溝通權的那個驢友（稱為A），那些隊長會給他發送他們自己決定的旅游地（也可能都還沒有決定）。可以看出，各個隊長是自己決定旅游地的，隊長之間無需溝通。
第二步（溝通階段）：這個幸運的驢友收到了隊長們給他發的旅游地，可能有幾種情況：
第一種情況：跟A溝通的隊長們（不一定是全部5個隊長，但是半數以上）全部都還沒有決定到底去那兒旅游，此時驢友A心花怒放，給這些隊長髮第二條簡訊，告訴他們自己希望的旅游地（比如馬爾地夫）；
可能會收到兩種結果：一是半數以上隊長都同意了，於是表明A建議的馬爾地夫被半數以上隊長都同意了，整個決定過程完畢了，其它驢友遲早會知道這個消息的，A先去收拾東西準備去馬爾地夫；除此之外，表明失敗。可能隊長出故障了，比如某個隊長在跟女朋友打電話等等，也可能被其它驢友搶占溝通權了（因為隊長喜新厭舊嘛，只有要更新的驢友給自己發簡訊，自己就與新人溝通，A的建議隊長不同意）等等。不管怎麼說，苦逼的A還得重新從第一步開始，重新給隊長們發簡訊申請。
第二種情況：至少有一個隊長已經決定旅游地了，A可能會收到來自不同隊長決定的多個旅游地，這些旅游地是不同隊長跟不同驢友在不同時間上做出的決定，那麼，A會先看一下，是不是有的旅游地已經被半數以上隊長同意了（比如3個隊長都同意去三亞，1個同意去昆明，另外一個沒搭理A），如果出現了這種情況，那就別扯了，說明整個決定過程已經達成一致了，收拾收拾準備去三亞吧，結束了；如果都沒有達到半數以上（比如1個同意去昆明，1個同意去三亞，2個同意去拉薩，1個沒搭理我），A作為一個高素質驢友，也不按照自己的意願亂來了（Paxos的關鍵所在，後者認同前者，否則整個決定過程永無止境），雖然自己原來可能想去馬爾地夫等等。就給隊長們發第二條簡訊的時候，告訴他們自己希望的旅游地，就是自己收到的那堆旅游地中最新決定的那個。（比如，去昆明那個是北京那個隊長前1分鐘決定的，去三亞的決定是上海那個隊長1個小時之前做出來的，於是頂昆明）。驢友A的想法是，既然有隊長已經做決定了，那我就乾脆頂最新那個決定。
從上面的邏輯可以看出，一旦某個時刻有半數以上隊長同意了某個地點比如昆明，緊跟著後面的驢友B繼續發簡訊時，如果獲得溝通權，因為半數以上隊長都同意與B溝通了，說明B收到了來自半數以上隊長髮過來的消息，B必然會收到至少一個隊長給他發的昆明這個結果（否則說明半數以上隊長都沒有同意昆明這個結果，這顯然與前面的假設矛盾），B於是會頂這個最新地點，不會更改，因為後面的驢友都會頂昆明，因此同意昆明的隊長越來越多，最終必然達成一致。
看完了驢友的邏輯，那麼隊長的邏輯是什麼呢？
隊長的邏輯比較簡單。
在申請階段，隊長只會選擇與最新發申請簡訊的驢友溝通，隊長知道自己接收到最新簡訊的時間，對於更老的簡訊，隊長不會搭理；隊長同意溝通了的話，會把自己決定的旅游地（或者還沒決定這一信息）發給驢友。
在溝通階段，驢友C會把自己希望的旅游地發過來（同時會附加上自己申請簡訊的時間，比如3分鐘前），所以隊長要檢查一下，如果這個時間（3分鐘前）確實是當前自己最新接收到申請簡訊的時間（說明這段時間沒有驢友要跟自己溝通），那麼，隊長就同意驢友C的這個旅游地了（比如昆明，哪怕自己1個小時前已經做過去三亞的決定，誰讓C更新呢，於是更新為昆明）；如果不是最新的，說明這3分鐘內又有其它驢友D跟自己申請了，因為自己是個喜新厭舊的家伙，同意與D溝通了，所以驢友C的決定自己不會同意，等著D一會兒要發過來的決定吧。
Paxos的基本思想大致就是上面的過程。可以看出，其實驢友的策略才是Paxos的關鍵。讓我們來跟理論對應一下。
Paxos主要用於保證分散式存儲中副本（或者狀態）的一致性。副本要保持一致，那麼，所有副本的更新序列就要保持一致。因為數據的增刪改查操作一般都存在多個客戶端併發操作，到底哪個客戶端先做，哪個客戶端後做，這就是更新順序。如果不是分散式，那麼可以利用加鎖的方法，誰先申請到鎖，誰就先操作。但是在分散式條件下，存在多個副本，如果依賴申請鎖+副本同步更新完畢再釋放鎖，那麼需要有分配鎖的這麼一個節點（如果是多個鎖分配節點，那麼又出現分散式鎖管理的需求，把鎖給哪一個客戶端又成為一個難點），這個節點又成為單點，豈不是可靠性不行了，失去了分散式多副本的意義，同時性能也很差，另外，還會出現死鎖等情況。
所以，說來說去，只有解決分散式條件下的一致性問題，似乎才能解決本質問題。
如上面的例子，Paxos解決這一問題利用的是選舉，少數服從多數的思想，只要2N+1個節點中，有N個以上同意了某個決定，則認為系統達到了一致，並且按照Paxos原則，最終理論上也達到了一致，不會再改變。這樣的話，客戶端不必與所有伺服器通信，選擇與大部分通信即可；也無需伺服器都全部處於工作狀態，有一些伺服器掛掉，只有保證半數以上存活著，整個過程也能持續下去，容錯性相當好。因此，以前看有的博客說在部署ZooKeeper這種服務的時候，需要奇數台機器，這種說法當然有一定來源背景，比如如果是5台，那麼任意客戶端與任意其中3台達成一致就相當於投票結束，不過6台有何不可？只是此時需要與4台以上達成一致。
Paxos中的Acceptor就相當於上面的隊長，Proposer就相當於上面的驢友，epoch編號就相當於例子中申請簡訊的發送時間。關於Paxos的正式描述已經很多了，這裡就不覆述了，關於Paxos正確性的證明，因為比較複雜，以後有時間再分析。另外，Paxos最消耗時間的地方就在於需要半數以上同意溝通了才能進入第二步，試想一下，一開始，所有驢友就給隊長狂發簡訊，每個隊長收到的最新簡訊的是不同驢友，這樣，就難以達到半數以上都同意與某個驢友溝通的狀態，為了減小這個時間，Paxos還有Fast Paxos的改進等等，有空再分析。
倒是有一些問題可以思考一下：在Paxos之前，或者說除了Chubby，ZooKeeper這些系統，其它分散式系統同樣面臨這樣的一致性問題，比如HDFS、分散式資料庫、Amazon的Dynamo等等，解決思路又不同，有空再進行對比分析。
最後談談一致性這個名詞。
關於Paxos說的一致性，個人理解是指冗餘副本（或狀態等，但都是因為存在冗餘）的一致性。這與關係型資料庫中ACID的一致性說的不是一個東西。在關係資料庫里，可以連副本都沒有，何談副本的一致性？按照經典定義，ACID中的C指的是在一個事務中，事務執行的結果必須是使資料庫從一個一致性狀態變到另一個一致性狀態。那麼，什麼又是一致性狀態呢，這跟業務約束有關係，比如經典的轉賬事務，事務處理完畢後，不能出現一個賬戶錢被扣了，另一個賬戶的錢沒有增加的情況，如果兩者加起來的錢還是等於轉賬前的錢，那麼就是一致性狀態。
從很多博文來看，對這兩種一致性往往混淆起來。另外，CAP原則裡面所說的一致性，個人認為是指副本一致性，與Paxos裡面的一致性接近。都是處理“因為冗餘數據的存在而需要保證多個副本保持一致”的問題，NoSQL放棄的強一致性也是指副本一致性，最終一致性也是指副本達到完全相同存在一定延時。
當然，如果資料庫本身是分散式的，且存在冗餘副本，則除瞭解決事務在業務邏輯上的一致性問題外，同時需要解決副本一致性問題，此時可以利用Paxos協議。但解決了副本一致性問題，還不能完全解決業務邏輯一致性；如果是分散式資料庫，但並不存在副本的情況，事務的一致性需要根據業務約束進行設計。
另外，談到Paxos時，還會涉及到拜占庭將軍問題，它指的是在存在消息丟失的不可靠通道上試圖通過消息傳遞的方式達到一致性是不可能的。Paxos本身就是利用消息傳遞方式解決一致性問題的，所以它的假定是通道必須可靠，這裡的可靠，主要指消息不會被篡改。消息丟失是允許的。
關於一致性、事務的ACID，CAP，NoSQL等等問題，以後再詳細分析。本文的描述也許可能存在一些舉例不太恰當的地方，如果錯誤，歡迎批評指正。
Paxos演算法細節詳解(一)--通過現實世界描述演算法
最近研究paxos演算法，看了許多相關的文章，概念還是很模糊，覺得還是沒有掌握paxos演算法的精髓，所以花了3天時間分析了libpaxos3的所有代碼，此代碼可以從https://bitbucket.org/sciascid/libpaxos 下載。對paxos演算法有初步瞭解之後，再看此文的效果會更好；如果你也想分析libpaxos3的話，此文應該會對你有不小幫助；關於paxos的歷史這裡不多做介紹，關於描述paxos演算法寫的最好的一篇文章應該就是維基百科了，地址戳這裡：http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95
在paxos演算法中，分為4種角色：
Proposer ：提議者
Acceptor：決策者
Client：產生議題者
Learner：最終決策學習者
上面4種角色中，提議者和決策者是很重要的，其他的2個角色在整個演算法中應該算做打醬油的，Proposer就像Client的使者，由Proposer使者拿著Client的議題去向Acceptor提議，讓Acceptor來決策。這裡上面出現了個新名詞：最終決策。現在來系統的介紹一下paxos演算法中所有的行為：
- Proposer提出議題
- Acceptor初步接受 或者 Acceptor初步不接受
- 如果上一步Acceptor初步接受則Proposer再次向Acceptor確認是否最終接受
- Acceptor 最終接受 或者Acceptor 最終不接受
上面Learner最終學習的目標是Acceptor們最終接受了什麼議題？註意，這裡是向所有Acceptor學習，如果有多數派個Acceptor最終接受了某提議，那就得到了最終的結果，演算法的目的就達到了。畫一幅圖來更加直觀：
為什麼需要3個Acceptor？因為Acceptor必須是最少大於等於3個，並且必須是奇數個，因為要形成多數派嘛，如果是偶數個，比如4個，2個接受2個不接受，各執己見，沒法搞下去了。
為什麼是3個Proposer？ 其實無所謂是多少個了，1~n 都可以的；如果是1個proposer，毫無競爭壓力，很順利的完成2階段提交，Acceptor們最終批准了事。如果是多個proposer就比較複雜了，請繼續看。
上面的圖中是畫了很多節點的，每個節點需要一臺機器麽？答案是不需要的，上面的圖是邏輯圖，物理中，可以將Acceptor和Proposer以及Client放到一臺機器上，只是使用了不同的埠號罷了，Acceptor們啟動不同埠的TCP監聽，Proposer來主動連接即可；完全可以將Client、Proposer、Acceptor、Learner合併到一個程式裡面；這裡舉一個例子：比如開發一個JOB程式，JOB程式部署在多台伺服器上(數量為奇數)，這些JOB有可能同時處理一項任務，現在使用paxos演算法讓這些JOB自己來商量由誰(哪台機器)來處理這項任務，這樣JOB程式里就需要包含Client、Proposer、Acceptor、Learner這4大功能，並且需要配置其他JOB伺服器的IP地址。
再舉一個例子，zookeeper常常用來做分散式事務鎖。Zookeeper所使用的zad協議也是類似paxos協議的。所有分散式自協商一致性演算法都是paxos演算法的簡化或者變種。Client是使用zookeeper服務的機器，Zookeeper自身包含了Acceptor, Proposer, Learner。Zookeeper領導選舉就是paxos過程，還有Client對Zookeeper寫Znode時，也是要進行Paxos過程的，因為不同Client可能連接不同的Zookeeper伺服器來寫Znode，到底哪個Client才能寫成功？需要依靠Zookeeper的paxos保證一致性，寫成功Znode的Client自然就是被最終接受了，Znode包含了寫入Client的IP與埠，其他的Client也可以讀取到這個Znode來進行Learner。也就是說在Zookeeper自身包含了Learner(因為Zookeeper為了保證自身的一致性而會進行領導選舉，所以需要有Learner的內部機制，多個Zookeeper伺服器之間需要知道現在誰是領導了)，Client端也可以Learner，Learner是廣義的。
現在通過一則故事來學習paxos的演算法的流程(2階段提交)，有2個Client(老闆，老闆之間是競爭關係)和3個Acceptor(政府官員)：
- 現在需要對一項議題來進行paxos過程，議題是“A項目我要中標！”，這裡的“我”指每個帶著他的秘書Proposer的Client老闆。
- Proposer當然聽老闆的話了，趕緊帶著議題和現金去找Acceptor政府官員。
- 作為政府官員，當然想誰給的錢多就把項目給誰。
- Proposer-1小姐帶著現金同時找到了Acceptor-1~Acceptor-3官員，1與2號官員分別收取了10比特幣，找到第3號官員時，沒想到遭到了3號官員的鄙視，3號官員告訴她，Proposer-2給了11比特幣。不過沒關係，Proposer-1已經得到了1,2兩個官員的認可，形成了多數派(如果沒有形成多數派，Proposer-1會去銀行提款在來找官員們給每人20比特幣，這個過程一直重覆每次+10比特幣，直到多數派的形成)，滿意的找老闆覆命去了，但是此時Proposer-2保鏢找到了1,2號官員，分別給了他們11比特幣，1,2號官員的態度立刻轉變，都說Proposer-2的老闆懂事，這下子Proposer-2放心了，搞定了3個官員，找老闆覆命去了，當然這個過程是第一階段提交，只是官員們初步接受賄賂而已。故事中的比特幣是編號，議題是value。
這個過程保證了在某一時刻，某一個proposer的議題會形成一個多數派進行初步支持；
===============華麗的分割線，第一階段結束================
5. 現在進入第二階段提交，現在proposer-1小姐使用分身術(多線程併發)分了3個自己分別去找3位官員，最先找到了1號官員簽合同，遭到了1號官員的鄙視，1號官員告訴他proposer-2先生給了他11比特幣，因為上一條規則的性質proposer-1小姐知道proposer-2第一階段在她之後又形成了多數派(至少有2位官員的贓款被更新了);此時她趕緊去提款準備重新賄賂這3個官員(重新進入第一階段)，每人20比特幣。剛給1號官員20比特幣， 1號官員很高興初步接受了議題，還沒來得及見到2,3號官員的時候
這時proposer-2先生也使用分身術分別找3位官員(註意這裡是proposer-2的第二階段)，被第1號官員拒絕了告訴他收到了20比特幣，第2,3號官員順利簽了合同，這時2，3號官員記錄client-2老闆用了11比特幣中標，因為形成了多數派，所以最終接受了Client2老闆中標這個議題，對於proposer-2先生已經出色的完成了工作；
這時proposer-1小姐找到了2號官員，官員告訴她合同已經簽了，將合同給她看，proposer-1小姐是一個沒有什麼職業操守的聰明人，覺得跟Client1老闆混沒什麼前途，所以將自己的議題修改為“Client2老闆中標”，並且給了2號官員20比特幣，這樣形成了一個多數派。順利的再次進入第二階段。由於此時沒有人競爭了，順利的找3位官員簽合同，3位官員看到議題與上次一次的合同是一致的，所以最終接受了，形成了多數派，proposer-1小姐跳槽到Client2老闆的公司去了。
===============華麗的分割線，第二階段結束===============
Paxos過程結束了，這樣，一致性得到了保證，演算法運行到最後所有的proposer都投“client2中標”所有的acceptor都接受這個議題，也就是說在最初的第二階段，議題是先入為主的，誰先占了先機，後面的proposer在第一階段就會學習到這個議題而修改自己本身的議題，因為這樣沒職業操守，才能讓一致性得到保證，這就是paxos演算法的一個過程。原來paxos演算法里的角色都是這樣的不靠譜，不過沒關係，結果靠譜就可以了。該演算法就是為了追求結果的一致性。
資源來源自網路，保持更新。
