http://www.mamicode.com/info-detail-198650.html
維基的簡(jiǎn)介：Paxos算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人現(xiàn)在在微軟研究院）于1990年提出的一種基于消息傳遞且具有高度容錯(cuò)特性的一致性算法。
Paxos算法目前在Google的Chubby、MegaStore、Spanner等系統(tǒng)中得到了應(yīng)用，Hadoop中的ZooKeeper也使用了Paxos算法，在上面的各個(gè)系統(tǒng)中，使用的算法與Lamport提出的原始Paxos并不完全一樣，這個(gè)以后再慢慢分析。本博文的目的是，如何讓一個(gè)小白在半個(gè)小時(shí)之內(nèi)理解Paxos算法的思想。小白可能對(duì)數(shù)學(xué)不感興趣，對(duì)分布式的復(fù)雜理論不熟悉，只是一個(gè)入門級(jí)程序員。之所以想寫這篇博文，是因?yàn)樽约嚎戳司W(wǎng)上很多介紹Paxos算法的文章，以及博客，包括Lamport的論文，感覺(jué)還是難以理解，大多過(guò)于復(fù)雜，本人一直認(rèn)為，復(fù)雜高深的理論背后一定基于一些通用的規(guī)律，而這些通用的規(guī)律在生活中其實(shí)我們?cè)缇陀龅竭^(guò)，甚至用過(guò)。所以，我們先忽略Paxos算法本身，從生活中的小事開(kāi)始談起。
假如有一群驢友要決定中秋節(jié)去旅游，這群驢友分布在全國(guó)各地，假定一共25個(gè)人，分別在不同的省，要決定到底去拉薩、昆明、三亞等等哪個(gè)地點(diǎn)（會(huì)合時(shí)間中秋節(jié)已經(jīng)定了，此時(shí)需要決定旅游地）。最直接的方式當(dāng)然就是建一個(gè)QQ群，大家都在里面投票，按照少數(shù)服從多數(shù)的原則。這種方式類似于“共享內(nèi)存”實(shí)現(xiàn)的一致性，實(shí)現(xiàn)起來(lái)簡(jiǎn)單，但Paxos算法不是這種場(chǎng)景，因?yàn)镻axos算法認(rèn)為這種方式有一個(gè)很大的問(wèn)題，就是QQ服務(wù)器掛掉怎么辦？Paxos的原則是容錯(cuò)性一定要很強(qiáng)。所以，Paxos的場(chǎng)景類似于這25個(gè)人相互之間只能發(fā)短信，為了這件事情能夠達(dá)成一致，這25個(gè)人找了另外的5個(gè)人（當(dāng)然這5個(gè)人可以從25個(gè)人中選，這里為了描述方便，就單拿出另外5個(gè)人），比如北京、上海、廣州、深圳、成都的5個(gè)人，25個(gè)人都給他們發(fā)短信，告訴自己傾向的旅游地。這5個(gè)人相互之間可以并不通信，只接受25個(gè)人發(fā)過(guò)來(lái)的短信。這25個(gè)人我們稱為驢友，那5個(gè)人稱為隊(duì)長(zhǎng)。
先來(lái)看驢友的邏輯。驢友可以給任意5個(gè)隊(duì)長(zhǎng)都發(fā)短信，發(fā)短信的過(guò)程分為兩個(gè)步驟：
第一步（申請(qǐng)階段）：詢問(wèn)5個(gè)隊(duì)長(zhǎng)，試圖與隊(duì)長(zhǎng)溝通旅游地。因?yàn)槊總€(gè)隊(duì)長(zhǎng)一直會(huì)收到不同驢友的短信，不能跟多個(gè)驢友一起溝通，在任何時(shí)刻只能跟一個(gè)驢友溝通，按照什么原則才能做到公平公正公開(kāi)呢？這些短信都帶有發(fā)送時(shí)間，隊(duì)長(zhǎng)采用的原則是同意與短信發(fā)送時(shí)間最新的驢友溝通，如果出現(xiàn)了更新的短信，則與短信更新的驢友溝通。總之，作為一個(gè)有話語(yǔ)權(quán)的人，只有時(shí)刻保持傾聽(tīng)最新的呼聲，才能做出最明智的選擇。在驢友發(fā)出短信后，等著隊(duì)長(zhǎng)回復(fù)。某些隊(duì)長(zhǎng)可能會(huì)回復(fù)說(shuō)，你這條短信太老了，我不與你溝通；有些隊(duì)長(zhǎng)則可能返回說(shuō)，你的短信是我收到的最新的，我同意跟你溝通。對(duì)于后面這些隊(duì)長(zhǎng)，還得返回自己決定的旅游地。關(guān)于隊(duì)長(zhǎng)是怎么決定旅游地的，后面再說(shuō)。
對(duì)于驢友來(lái)說(shuō)，第一步必須至少有半數(shù)以上隊(duì)長(zhǎng)都同意溝通了，才能進(jìn)入下一步。否則，你連溝通的資格都沒(méi)有，一直在那兒狂發(fā)吧。你發(fā)的短信更新，你獲得溝通權(quán)的可能性才更大。。。。。。
因?yàn)橹辽儆邪霐?shù)以上隊(duì)長(zhǎng)（也就是3個(gè)隊(duì)長(zhǎng)以上）同意，你才能與隊(duì)長(zhǎng)們進(jìn)行實(shí)質(zhì)性的溝通，也就是進(jìn)入第二步；而隊(duì)長(zhǎng)在任何時(shí)候只能跟1個(gè)驢友溝通，所以，在任何時(shí)候，不可能出現(xiàn)兩個(gè)驢友都達(dá)到了這個(gè)狀態(tài)。。。當(dāng)然，你可以通過(guò)狂發(fā)短信把溝通權(quán)搶了。。。。
對(duì)于獲得溝通權(quán)的那個(gè)驢友（稱為A），那些隊(duì)長(zhǎng)會(huì)給他發(fā)送他們自己決定的旅游地（也可能都還沒(méi)有決定）。可以看出，各個(gè)隊(duì)長(zhǎng)是自己決定旅游地的，隊(duì)長(zhǎng)之間無(wú)需溝通。
第二步（溝通階段）：這個(gè)幸運(yùn)的驢友收到了隊(duì)長(zhǎng)們給他發(fā)的旅游地，可能有幾種情況：
第一種情況：跟A溝通的隊(duì)長(zhǎng)們（不一定是全部5個(gè)隊(duì)長(zhǎng)，但是半數(shù)以上）全部都還沒(méi)有決定到底去那兒旅游，此時(shí)驢友A心花怒放，給這些隊(duì)長(zhǎng)發(fā)第二條短信，告訴他們自己希望的旅游地（比如馬爾代夫）；
可能會(huì)收到兩種結(jié)果：一是半數(shù)以上隊(duì)長(zhǎng)都同意了，于是表明A建議的馬爾代夫被半數(shù)以上隊(duì)長(zhǎng)都同意了，整個(gè)決定過(guò)程完畢了，其它驢友遲早會(huì)知道這個(gè)消息的，A先去收拾東西準(zhǔn)備去馬爾代夫；除此之外，表明失敗。可能隊(duì)長(zhǎng)出故障了，比如某個(gè)隊(duì)長(zhǎng)在跟女朋友打電話等等，也可能被其它驢友搶占溝通權(quán)了（因?yàn)殛?duì)長(zhǎng)喜新厭舊嘛，只有要更新的驢友給自己發(fā)短信，自己就與新人溝通，A的建議隊(duì)長(zhǎng)不同意）等等。不管怎么說(shuō)，苦逼的A還得重新從第一步開(kāi)始，重新給隊(duì)長(zhǎng)們發(fā)短信申請(qǐng)。
第二種情況：至少有一個(gè)隊(duì)長(zhǎng)已經(jīng)決定旅游地了，A可能會(huì)收到來(lái)自不同隊(duì)長(zhǎng)決定的多個(gè)旅游地，這些旅游地是不同隊(duì)長(zhǎng)跟不同驢友在不同時(shí)間上做出的決定，那么，A會(huì)先看一下，是不是有的旅游地已經(jīng)被半數(shù)以上隊(duì)長(zhǎng)同意了（比如3個(gè)隊(duì)長(zhǎng)都同意去三亞，1個(gè)同意去昆明，另外一個(gè)沒(méi)搭理A），如果出現(xiàn)了這種情況，那就別扯了，說(shuō)明整個(gè)決定過(guò)程已經(jīng)達(dá)成一致了，收拾收拾準(zhǔn)備去三亞吧，結(jié)束了；如果都沒(méi)有達(dá)到半數(shù)以上（比如1個(gè)同意去昆明，1個(gè)同意去三亞，2個(gè)同意去拉薩，1個(gè)沒(méi)搭理我），A作為一個(gè)高素質(zhì)驢友，也不按照自己的意愿亂來(lái)了（Paxos的關(guān)鍵所在，后者認(rèn)同前者，否則整個(gè)決定過(guò)程永無(wú)止境），雖然自己原來(lái)可能想去馬爾代夫等等。就給隊(duì)長(zhǎng)們發(fā)第二條短信的時(shí)候，告訴他們自己希望的旅游地，就是自己收到的那堆旅游地中最新決定的那個(gè)。（比如，去昆明那個(gè)是北京那個(gè)隊(duì)長(zhǎng)前1分鐘決定的，去三亞的決定是上海那個(gè)隊(duì)長(zhǎng)1個(gè)小時(shí)之前做出來(lái)的，于是頂昆明）。驢友A的想法是，既然有隊(duì)長(zhǎng)已經(jīng)做決定了，那我就干脆頂最新那個(gè)決定。
從上面的邏輯可以看出，一旦某個(gè)時(shí)刻有半數(shù)以上隊(duì)長(zhǎng)同意了某個(gè)地點(diǎn)比如昆明，緊跟著后面的驢友B繼續(xù)發(fā)短信時(shí)，如果獲得溝通權(quán)，因?yàn)榘霐?shù)以上隊(duì)長(zhǎng)都同意與B溝通了，B必然會(huì)收到至少一個(gè)隊(duì)長(zhǎng)給他發(fā)的昆明這個(gè)結(jié)果，B于是會(huì)頂這個(gè)最新地點(diǎn)，不會(huì)更改，因?yàn)楹竺娴捏H友都會(huì)頂昆明，因此同意昆明的隊(duì)長(zhǎng)越來(lái)越多，最終必然達(dá)成一致。
看完了驢友的邏輯，那么隊(duì)長(zhǎng)的邏輯是什么呢？
隊(duì)長(zhǎng)的邏輯比較簡(jiǎn)單。
在申請(qǐng)階段，隊(duì)長(zhǎng)只會(huì)選擇與最新發(fā)申請(qǐng)短信的驢友溝通，隊(duì)長(zhǎng)知道自己接收到最新短信的時(shí)間，對(duì)于更老的短信，隊(duì)長(zhǎng)不會(huì)搭理；隊(duì)長(zhǎng)同意溝通了的話，會(huì)把自己決定的旅游地（或者還沒(méi)決定這一信息）發(fā)給驢友。
在溝通階段，驢友C會(huì)把自己希望的旅游地發(fā)過(guò)來(lái)（同時(shí)會(huì)附加上自己申請(qǐng)短信的時(shí)間，比如3分鐘前），所以隊(duì)長(zhǎng)要檢查一下，如果這個(gè)時(shí)間（3分鐘前）確實(shí)是當(dāng)前自己最新接收到申請(qǐng)短信的時(shí)間（說(shuō)明這段時(shí)間沒(méi)有驢友要跟自己溝通），那么，隊(duì)長(zhǎng)就同意驢友C的這個(gè)旅游地了（比如昆明，哪怕自己1個(gè)小時(shí)前已經(jīng)做過(guò)去三亞的決定，誰(shuí)讓C更新呢，于是更新為昆明）；如果不是最新的，說(shuō)明這3分鐘內(nèi)又有其它驢友D跟自己申請(qǐng)了，因?yàn)樽约菏莻€(gè)喜新厭舊的家伙，同意與D溝通了，所以驢友C的決定自己不會(huì)同意，等著D一會(huì)兒要發(fā)過(guò)來(lái)的決定吧。
Paxos的基本思想大致就是上面的過(guò)程。讓我們來(lái)對(duì)應(yīng)一下。
Paxos主要用于保證分布式存儲(chǔ)中副本（或者狀態(tài)）的一致性。副本要保持一致，那么，所有副本的更新序列就要保持一致。因?yàn)閿?shù)據(jù)的增刪改查操作一般都存在多個(gè)客戶端并發(fā)操作，到底哪個(gè)客戶端先做，哪個(gè)客戶端后做，這就是更新順序。如果不是分布式，那么可以利用加鎖的方法，誰(shuí)先申請(qǐng)到鎖，誰(shuí)就先操作。但是在分布式條件下，存在多個(gè)副本，如果依賴申請(qǐng)鎖+副本同步更新完畢再釋放鎖，那么需要有分配鎖的這么一個(gè)節(jié)點(diǎn)（如果是多個(gè)鎖分配節(jié)點(diǎn)，那么又出現(xiàn)分布式鎖管理的需求，把鎖給哪一個(gè)客戶端又成為一個(gè)難點(diǎn)），這個(gè)節(jié)點(diǎn)又成為單點(diǎn)，豈不是可靠性不行了，失去了分布式多副本的意義，同時(shí)性能也很差，另外，還會(huì)出現(xiàn)死鎖等情況。
所以，說(shuō)來(lái)說(shuō)去，只有解決分布式條件下的一致性問(wèn)題，似乎才能解決本質(zhì)問(wèn)題。
如上面的例子，Paxos解決這一問(wèn)題利用的是選舉，少數(shù)服從多數(shù)的思想，只要2N+1個(gè)節(jié)點(diǎn)中，有N個(gè)以上同意了某個(gè)決定，則認(rèn)為系統(tǒng)達(dá)到了一致，并且按照Paxos原則，最終理論上也達(dá)到了一致，不會(huì)再改變。這樣的話，客戶端不必與所有服務(wù)器通信，選擇與大部分通信即可；也無(wú)需服務(wù)器都全部處于工作狀態(tài)，有一些服務(wù)器掛掉，只有保證半數(shù)以上存活著，整個(gè)過(guò)程也能持續(xù)下去，容錯(cuò)性相當(dāng)好。
Paxos中的Acceptor就相當(dāng)于上面的隊(duì)長(zhǎng)，Proposer就相當(dāng)于上面的驢友，epoch編號(hào)就相當(dāng)于例子中申請(qǐng)短信的發(fā)送時(shí)間。關(guān)于Paxos的正式描述已經(jīng)很多了，這里就不復(fù)述了，關(guān)于Paxos正確性的證明，因?yàn)楸容^復(fù)雜，以后有時(shí)間再分析。另外，Paxos最消耗時(shí)間的地方就在于需要半數(shù)以上同意溝通了才能進(jìn)入第二步，試想一下，一開(kāi)始，所有驢友就給隊(duì)長(zhǎng)狂發(fā)短信，每個(gè)隊(duì)長(zhǎng)收到的最新短信的是不同驢友，這樣，就難以達(dá)到半數(shù)以上都同意與某個(gè)驢友溝通的狀態(tài)，為了減小這個(gè)時(shí)間，Paxos還有Fast Paxos的改進(jìn)等等，有空再分析。
倒是有一些問(wèn)題可以思考一下：在Paxos之前，或者說(shuō)除了Chubby，ZooKeeper這些系統(tǒng)，其它分布式系統(tǒng)同樣面臨這樣的一致性問(wèn)題，比如HDFS、分布式數(shù)據(jù)庫(kù)、Amazon的Dynamo等等，解決思路又不同，有空再進(jìn)行對(duì)比分析。
最后談?wù)勔恢滦赃@個(gè)名詞。
關(guān)于Paxos說(shuō)的一致性，個(gè)人理解是指冗余副本（或狀態(tài)等，但都是因?yàn)榇嬖谌哂啵┑囊恢滦浴＿@與關(guān)系型數(shù)據(jù)庫(kù)中ACID的一致性說(shuō)的不是一個(gè)東西。在關(guān)系數(shù)據(jù)庫(kù)里，可以連副本都沒(méi)有，何談副本的一致性？按照經(jīng)典定義，ACID中的C指的是在一個(gè)事務(wù)中，事務(wù)執(zhí)行的結(jié)果必須是使數(shù)據(jù)庫(kù)從一個(gè)一致性狀態(tài)變到另一個(gè)一致性狀態(tài)。那么，什么又是一致性狀態(tài)呢，這跟業(yè)務(wù)約束有關(guān)系，比如經(jīng)典的轉(zhuǎn)賬事務(wù)，事務(wù)處理完畢后，不能出現(xiàn)一個(gè)賬戶錢被扣了，另一個(gè)賬戶的錢沒(méi)有增加的情況，如果兩者加起來(lái)的錢還是等于轉(zhuǎn)賬前的錢，那么就是一致性狀態(tài)。
從很多博文來(lái)看，對(duì)這兩種一致性往往混淆起來(lái)。另外，CAP原則里面所說(shuō)的一致性，個(gè)人認(rèn)為是指副本一致性，與Paxos里面的一致性接近。都是處理“因?yàn)槿哂鄶?shù)據(jù)的存在而需要保證多個(gè)副本保持一致”的問(wèn)題，NoSQL放棄的強(qiáng)一致性也是指副本一致性，最終一致性也是指副本達(dá)到完全相同存在一定延時(shí)。
當(dāng)然，如果數(shù)據(jù)庫(kù)本身是分布式的，且存在冗余副本，則除了解決事務(wù)在業(yè)務(wù)邏輯上的一致性問(wèn)題外，同時(shí)需要解決副本一致性問(wèn)題，此時(shí)可以利用Paxos協(xié)議。但解決了副本一致性問(wèn)題，還不能完全解決業(yè)務(wù)邏輯一致性；如果是分布式數(shù)據(jù)庫(kù)，但并不存在副本的情況，事務(wù)的一致性需要根據(jù)業(yè)務(wù)約束進(jìn)行設(shè)計(jì)。
另外，談到Paxos時(shí)，還會(huì)涉及到拜占庭將軍問(wèn)題，它指的是在存在消息丟失的不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的。Paxos本身就是利用消息傳遞方式解決一致性問(wèn)題的，所以它的假定是信道必須可靠，這里的可靠，主要指消息不會(huì)被篡改。消息丟失是允許的。
關(guān)于一致性，關(guān)于事務(wù)的ACID，CAP，NoSQL等等問(wèn)題，以后再詳細(xì)分析。