分布式理論之一：Paxos算法的通俗理解

維基的簡介：Paxos算法是萊斯利·蘭伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人現(xiàn)在在微軟研究院）于1990年提出的一種基于消息傳遞且具有高度容錯特性的一致性算法。

Paxos算法目前在Google的Chubby、MegaStore、Spanner等系統(tǒng)中得到了應用，Hadoop中的ZooKeeper也使用了Paxos算法，在上面的各個系統(tǒng)中，使用的算法與Lamport提出的原始Paxos并不完全一樣，這個以后再慢慢分析。本博文的目的是，如何讓一個小白在半個小時之內(nèi)理解Paxos算法的思想。小白可能對數(shù)學不感興趣，對分布式的復雜理論不熟悉，只是一個入門級程序員。之所以想寫這篇博文，是因為自己看了網(wǎng)上很多介紹Paxos算法的文章，以及博客，包括Lamport的論文，感覺還是難以理解，大多過于復雜，本人一直認為，復雜高深的理論背后一定基于一些通用的規(guī)律，而這些通用的規(guī)律在生活中其實我們早就遇到過，甚至用過。所以，我們先忽略Paxos算法本身，從生活中的小事開始談起。

 假如有一群驢友要決定中秋節(jié)去旅游，這群驢友分布在全國各地，假定一共25個人，分別在不同的省，要決定到底去拉薩、昆明、三亞等等哪個地點（會合時間中秋節(jié)已經(jīng)定了，此時需要決定旅游地）。最直接的方式當然就是建一個QQ群，大家都在里面投票，按照少數(shù)服從多數(shù)的原則。這種方式類似于“共享內(nèi)存”實現(xiàn)的一致性，實現(xiàn)起來簡單，但Paxos算法不是這種場景，因為Paxos算法認為這種方式有一個很大的問題，就是QQ服務器掛掉怎么辦？Paxos的原則是容錯性一定要很強。所以，Paxos的場景類似于這25個人相互之間只能發(fā)短信，需要解決的核心問題是，哪怕任意的一部分人（Paxos的目的其實是少于半數(shù)的人）“失聯(lián)”了，其它人也能夠在會合地點上達成一致。好了，怎么設計呢？

這25個人找了另外的5個人（當然這5個人可以從25個人中選，這里為了描述方便，就單拿出另外5個人），比如北京、上海、廣州、深圳、成都的5個人，25個人都給他們發(fā)短信，告訴自己傾向的旅游地。這5個人相互之間可以并不通信，只接受25個人發(fā)過來的短信。這25個人我們稱為驢友，那5個人稱為隊長。

先來看驢友的邏輯。驢友可以給任意5個隊長都發(fā)短信，發(fā)短信的過程分為兩個步驟：

第一步（申請階段）：詢問5個隊長，試圖與隊長溝通旅游地。因為每個隊長一直會收到不同驢友的短信，不能跟多個驢友一起溝通，在任何時刻只能跟一個驢友溝通，按照什么原則才能做到公平公正公開呢？這些短信都帶有發(fā)送時間，隊長采用的原則是同意與短信發(fā)送時間最新的驢友溝通，如果出現(xiàn)了更新的短信，則與短信更新的驢友溝通。總之，作為一個有話語權的人，只有時刻保持傾聽最新的呼聲，才能做出最明智的選擇。在驢友發(fā)出短信后，等著隊長回復。某些隊長可能會回復說，你這條短信太老了，我不與你溝通；有些隊長則可能返回說，你的短信是我收到的最新的，我同意跟你溝通。對于后面這些隊長，還得返回自己決定的旅游地。關于隊長是怎么決定旅游地的，后面再說。

對于驢友來說，第一步必須至少有半數(shù)以上隊長都同意溝通了，才能進入下一步。否則，你連溝通的資格都沒有，一直在那兒狂發(fā)吧。你發(fā)的短信更新，你獲得溝通權的可能性才更大。。。。。。

因為至少有半數(shù)以上隊長（也就是3個隊長以上）同意，你才能與隊長們進行實質性的溝通，也就是進入第二步；而隊長在任何時候只能跟1個驢友溝通，所以，在任何時候，不可能出現(xiàn)兩個驢友都達到了這個狀態(tài)。。。當然，你可以通過狂發(fā)短信把溝通權搶了。。。。

對于獲得溝通權的那個驢友（稱為A），那些隊長會給他發(fā)送他們自己決定的旅游地（也可能都還沒有決定）。可以看出，各個隊長是自己決定旅游地的，隊長之間無需溝通。

第二步（溝通階段）：這個幸運的驢友收到了隊長們給他發(fā)的旅游地，可能有幾種情況：

第一種情況：跟A溝通的隊長們（不一定是全部5個隊長，但是半數(shù)以上）全部都還沒有決定到底去那兒旅游，此時驢友A心花怒放，給這些隊長發(fā)第二條短信，告訴他們自己希望的旅游地（比如馬爾代夫）；

可能會收到兩種結果：一是半數(shù)以上隊長都同意了，于是表明A建議的馬爾代夫被半數(shù)以上隊長都同意了，整個決定過程完畢了，其它驢友遲早會知道這個消息的，A先去收拾東西準備去馬爾代夫；除此之外，表明失敗。可能隊長出故障了，比如某個隊長在跟女朋友打電話等等，也可能被其它驢友搶占溝通權了（因為隊長喜新厭舊嘛，只有要更新的驢友給自己發(fā)短信，自己就與新人溝通，A的建議隊長不同意）等等。不管怎么說，苦逼的A還得重新從第一步開始，重新給隊長們發(fā)短信申請。

第二種情況：至少有一個隊長已經(jīng)決定旅游地了，A可能會收到來自不同隊長決定的多個旅游地，這些旅游地是不同隊長跟不同驢友在不同時間上做出的決定，那么，A會先看一下，是不是有的旅游地已經(jīng)被半數(shù)以上隊長同意了（比如3個隊長都同意去三亞，1個同意去昆明，另外一個沒搭理A），如果出現(xiàn)了這種情況，那就別扯了，說明整個決定過程已經(jīng)達成一致了，收拾收拾準備去三亞吧，結束了；如果都沒有達到半數(shù)以上（比如1個同意去昆明，1個同意去三亞，2個同意去拉薩，1個沒搭理我），A作為一個高素質驢友，也不按照自己的意愿亂來了（Paxos的關鍵所在，后者認同前者，否則整個決定過程永無止境），雖然自己原來可能想去馬爾代夫等等。就給隊長們發(fā)第二條短信的時候，告訴他們自己希望的旅游地，就是自己收到的那堆旅游地中最新決定的那個。（比如，去昆明那個是北京那個隊長前1分鐘決定的，去三亞的決定是上海那個隊長1個小時之前做出來的，于是頂昆明）。驢友A的想法是，既然有隊長已經(jīng)做決定了，那我就干脆頂最新那個決定。

從上面的邏輯可以看出，一旦某個時刻有半數(shù)以上隊長同意了某個地點比如昆明，緊跟著后面的驢友B繼續(xù)發(fā)短信時，如果獲得溝通權，因為半數(shù)以上隊長都同意與B溝通了，說明B收到了來自半數(shù)以上隊長發(fā)過來的消息，B必然會收到至少一個隊長給他發(fā)的昆明這個結果（否則說明半數(shù)以上隊長都沒有同意昆明這個結果，這顯然與前面的假設矛盾），B于是會頂這個最新地點，不會更改，因為后面的驢友都會頂昆明，因此同意昆明的隊長越來越多，最終必然達成一致。

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

隊長的邏輯比較簡單。

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

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

Paxos的基本思想大致就是上面的過程。可以看出，其實驢友的策略才是Paxos的關鍵。讓我們來跟理論對應一下。

Paxos主要用于保證分布式存儲中副本（或者狀態(tài)）的一致性。副本要保持一致，那么，所有副本的更新序列就要保持一致。因為數(shù)據(jù)的增刪改查操作一般都存在多個客戶端并發(fā)操作，到底哪個客戶端先做，哪個客戶端后做，這就是更新順序。如果不是分布式，那么可以利用加鎖的方法，誰先申請到鎖，誰就先操作。但是在分布式條件下，存在多個副本，如果依賴申請鎖+副本同步更新完畢再釋放鎖，那么需要有分配鎖的這么一個節(jié)點（如果是多個鎖分配節(jié)點，那么又出現(xiàn)分布式鎖管理的需求，把鎖給哪一個客戶端又成為一個難點），這個節(jié)點又成為單點，豈不是可靠性不行了，失去了分布式多副本的意義，同時性能也很差，另外，還會出現(xiàn)死鎖等情況。

所以，說來說去，只有解決分布式條件下的一致性問題，似乎才能解決本質問題。

如上面的例子，Paxos解決這一問題利用的是選舉，少數(shù)服從多數(shù)的思想，只要2N+1個節(jié)點中，有N個以上同意了某個決定，則認為系統(tǒng)達到了一致，并且按照Paxos原則，最終理論上也達到了一致，不會再改變。這樣的話，客戶端不必與所有服務器通信，選擇與大部分通信即可；也無需服務器都全部處于工作狀態(tài)，有一些服務器掛掉，只有保證半數(shù)以上存活著，整個過程也能持續(xù)下去，容錯性相當好。因此，以前看有的博客說在部署ZooKeeper這種服務的時候，需要奇數(shù)臺機器，這種說法當然有一定來源背景，比如如果是5臺，那么任意客戶端與任意其中3臺達成一致就相當于投票結束，不過6臺有何不可？只是此時需要與4臺以上達成一致。

Paxos中的Acceptor就相當于上面的隊長，Proposer就相當于上面的驢友，epoch編號就相當于例子中申請短信的發(fā)送時間。關于Paxos的正式描述已經(jīng)很多了，這里就不復述了，關于Paxos正確性的證明，因為比較復雜，以后有時間再分析。另外，Paxos最消耗時間的地方就在于需要半數(shù)以上同意溝通了才能進入第二步，試想一下，一開始，所有驢友就給隊長狂發(fā)短信，每個隊長收到的最新短信的是不同驢友，這樣，就難以達到半數(shù)以上都同意與某個驢友溝通的狀態(tài)，為了減小這個時間，Paxos還有Fast Paxos的改進等等，有空再分析。

倒是有一些問題可以思考一下：在Paxos之前，或者說除了Chubby，ZooKeeper這些系統(tǒng)，其它分布式系統(tǒng)同樣面臨這樣的一致性問題，比如HDFS、分布式數(shù)據(jù)庫、Amazon的Dynamo等等，解決思路又不同，有空再進行對比分析。

最后談談一致性這個名詞。

關于Paxos說的一致性，個人理解是指冗余副本（或狀態(tài)等，但都是因為存在冗余）的一致性。這與關系型數(shù)據(jù)庫中ACID的一致性說的不是一個東西。在關系數(shù)據(jù)庫里，可以連副本都沒有，何談副本的一致性？按照經(jīng)典定義，ACID中的C指的是在一個事務中，事務執(zhí)行的結果必須是使數(shù)據(jù)庫從一個一致性狀態(tài)變到另一個一致性狀態(tài)。那么，什么又是一致性狀態(tài)呢，這跟業(yè)務約束有關系，比如經(jīng)典的轉賬事務，事務處理完畢后，不能出現(xiàn)一個賬戶錢被扣了，另一個賬戶的錢沒有增加的情況，如果兩者加起來的錢還是等于轉賬前的錢，那么就是一致性狀態(tài)。

從很多博文來看，對這兩種一致性往往混淆起來。另外，CAP原則里面所說的一致性，個人認為是指副本一致性，與Paxos里面的一致性接近。都是處理“因為冗余數(shù)據(jù)的存在而需要保證多個副本保持一致”的問題，NoSQL放棄的強一致性也是指副本一致性，最終一致性也是指副本達到完全相同存在一定延時。

當然，如果數(shù)據(jù)庫本身是分布式的，且存在冗余副本，則除了解決事務在業(yè)務邏輯上的一致性問題外，同時需要解決副本一致性問題，此時可以利用Paxos協(xié)議。但解決了副本一致性問題，還不能完全解決業(yè)務邏輯一致性；如果是分布式數(shù)據(jù)庫，但并不存在副本的情況，事務的一致性需要根據(jù)業(yè)務約束進行設計。

另外，談到Paxos時，還會涉及到拜占庭將軍問題，它指的是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。Paxos本身就是利用消息傳遞方式解決一致性問題的，所以它的假定是信道必須可靠，這里的可靠，主要指消息不會被篡改。消息丟失是允許的。

關于一致性、事務的ACID，CAP，NoSQL等等問題，以后再詳細分析。本文的描述也許可能存在一些舉例不太恰當?shù)牡胤剑绻e誤，歡迎批評指正。