參考 Paxos算法是萊斯利（LeslieLamport，就是LaTeX中的"La"，此人現在在微軟）于1990年一種基于消息傳遞Paxos算法目前在的Chubby、MegaStore、Spanner等系統中得到了應用，Hadoop中的ZooKeeper也使Paxos算法，在上面的各個系統中，使用的算法與Lamport原始Paxos并不完全一樣，這個以后再慢慢分析。本博文的目的是，如何讓一個在半個小時之內理解Paxos算法的思想。可能對數學所以想寫這篇博文，是因為自己看了網上很多介紹Paxos算法的文章，以及博客，包括Lamport的，感覺還是難以理解，大多過于以，我們先忽略Paxos算法本身，從生活中的小事開始談起。假一群驢友要決定中秋節去旅游，這群驢友分布在各地，定一共25個人，分別在不同的省，要決定到底去、、三亞等等哪個地點（會合時間中秋節已經定了，此時需要決定旅游地）。最直接的方式當然就是建一個QQ群，大家都在里面投票，按照少數來簡單，但Paxos算法不是這種場景，因為Paxos算法認為這種方式有一個很大的問題，就是QQ服務器掛掉怎么辦？Paxos的原則是容錯性一定要很強。所以，Paxos的場景類似于這25個人相互之間25個人找了另5個人（當然這5個人可以從25個人中選，這里為了描述方便，就單拿出另外5個人），比如、、廣州、、的5個人，25個人都給他們發，告訴自己傾向的旅游地。這5個人相互之間可以并不通信，只接受25個人發過來的。這25個人我們稱為驢友，那5個人稱為隊長先來看驢友的邏輯。驢友可以給任意5個隊長都發，發的過第一步（申請階段）：詢問5個隊長，試圖與隊長溝通旅游地。因為長可能會回復說，你這條太老了，我不與你溝通；有些隊長則能返回說，你的是我收到的的，我同意跟你溝通。對于后的，后面再說。發的更新，你獲得溝通權的可能性才更大。。。。。。因為至少有半數以上隊長（也就是3個隊長以上）同意，你才能與隊跟1個驢友溝通，所以，在任何時候，不可能出現兩個驢友都達到了對于獲得溝通權的那個驢友（稱為），那些隊長會給他發送他們自己決定的旅游地（也可能都還沒有決定）己決定旅游地的，隊長之間無需溝通。第二步（溝通階段）地，可能有幾種情況：第一種情況：跟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還有FatPaxos的改進等等，有空再分析。倒是有一些問題可以思考一下Paxos之前，或者說除了Chubby，ZooKeeper這些系統，其它分布式系統同樣這樣的一致性問題HDFS、分布式數據庫、AmazonDynamo等最后談談一致性這個名詞關于Paxos說的一致性，個人理解是指冗余副本（或狀態等，但都是因為存在冗余）的一致性。這與關系型數據庫中ACID的一致性說的致性？按照經典定義，ACIDC指的是在一個事務中，事務執行從很多博文來看，對這兩種一致性往往起來。另外，P原則里面所說的一致性，個人認為是指副本一致性，與Paxos里面的一致性接近。都是處理“因為冗余數據的存在而需要保證多個副本保持一致”的問題，oL放棄的強一致性