分布式一緻性算法Paxos詳解

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算法中所有的行為：

1. Proposer提出議題
2. Acceptor初步接受 或者 Acceptor初步不接受
3. 如果上一步Acceptor初步接受則Proposer再次向Acceptor确認是否最終接受
4. 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(政府官員)：

1. 現在需要對一項議題來進行paxos過程，議題是“A項目我要中标！”，這裡的“我”指每個帶着他的秘書Proposer的Client老闆。
2. Proposer當然聽老闆的話了，趕緊帶着議題和現金去找Acceptor政府官員。
3. 作為政府官員，當然想誰給的錢多就把項目給誰。
4. 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算法裡的角色都是這樣的不靠譜，不過沒關系，結果靠譜就可以了。該算法就是為了追求結果的一緻性。

轉載自：http://www.cnblogs.com/endsock/p/3480093.html

示例

假如有一群驢友要決定中秋節去旅遊，這群驢友分布在全國各地，假定一共25個人，分别在不同的省，要決定到底去拉薩、昆明、三亞等等哪個地點（會合時間中秋節已經定了，此時需要決定旅遊地）。最直接的方式當然就是建一個QQ群，大家都在裡面投票，按照少數服從多數的原則。這種方式類似于“共享記憶體”實作的一緻性，實作起來簡單，但Paxos算法不是這種場景，因為Paxos算法認為這種方式有一個很大的問題，就是QQ伺服器挂掉怎麼辦？Paxos的原則是容錯性一定要很強。是以，Paxos的場景類似于這25個人互相之間隻能發短信，為了這件事情能夠達成一緻，這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于是會頂這個最新地點，不會更改，因為後面的驢友都會頂昆明，是以同意昆明的隊長越來越多，最終必然達成一緻。

看完了驢友的邏輯，那麼隊長的邏輯是什麼呢？

隊長的邏輯比較簡單。

在申請階段，隊長隻會選擇與最新發申請短信的驢友溝通，隊長知道自己接收到最新短信的時間，對于更老的短信，隊長不會搭理；隊長同意溝通了的話，會把自己決定的旅遊地（或者還沒決定這一資訊）發給驢友。

在溝通階段，驢友C會把自己希望的旅遊地發過來（同時會附加上自己申請短信的時間，比如3分鐘前），是以隊長要檢查一下，如果這個時間（3分鐘前）确實是目前自己最新接收到申請短信的時間（說明這段時間沒有驢友要跟自己溝通），那麼，隊長就同意驢友C的這個旅遊地了（比如昆明，哪怕自己1個小時前已經做過去三亞的決定，誰讓C更新呢，于是更新為昆明）；如果不是最新的，說明這3分鐘内又有其它驢友D跟自己申請了，因為自己是個喜新厭舊的家夥，同意與D溝通了，是以驢友C的決定自己不會同意，等着D一會兒要發過來的決定吧。