很多人都知道，可用性和一致性是分佈式系統的基本問題，先有著名的CAP理論定義過分佈式環境下二者不可兼得的關係，又有神秘的Paxos協議號稱是史上最簡單的分佈式系統一致性算法並獲得圖靈獎，再有開源產品ZooKeeper實現的ZAB協議號稱超越Paxos，它們之間究竟有什麼聯繫？今天我們邀請阿里資深技術專家見獨，分享他的思考與觀點。
分佈式系統的挑戰
一致性可理解為所有節點都能訪問到最新版本的數據，這在單機場景下非常容易實現，使用共享內存和鎖即可解決，但數據存儲在單機會有兩個限制：
1）單機不可用系統整體將不可用；
2）系統吞吐量受限於單機的計算能力。
消除這兩個限制的方法是用多機來存儲數據的多個副本，負責更新的客戶端會同時更新數據的多個副本，於是問題就來了，多機之間的網絡可能無法連接，當負責更新的客戶端無法同時到連接多個機器時，如何能保證所有客戶端都能讀到最新版本的數據？
如下圖1中所示，Client A負責更新數據，為了保證Server 1和Server 2上的數據是一致的，Client A會將X=1的寫操作同時發給Server 1和Server 2，但是當Client A和Server 2之間發生網絡分區（網絡無法連接）時，此時如果讓write X=1的寫操作在Server 1上成功，那Client B和Client C將從Server 1和Server 2上讀取到不一致的X值；此時如果要保持X值的一致性，那麼write X=1的寫操作在Server 1和Server 2上都必須失敗，這就是著名的CAP理論：在容忍網絡分區的前提下，要麼犧牲數據的一致性，要麼犧牲寫操作的可用性。
圖1：CAP理論示意圖
圖1：CAP理論示意圖
解決這個問題你可能會想到讓Client C同時讀取Server 1和Server 2上的X值和版本信息，然後取Server 1和Server 2最新版本的X值，如下圖2所示。但Client C和Server 1之間也可能發生網絡分區，這本質上是犧牲讀可用性換取寫可用性，並沒有突破CAP理論。
圖2：對圖1中可用性的優化
圖2：對圖1中可用性的優化
CAP理論
CAP理論由加州大學伯克利分校的計算機教授Eric Brewer在2000年提出，其核心思想是任何基於網絡的數據共享系統最多隻能滿足數據一致性(Consistency)、可用性(Availability)和網絡分區容忍(Partition Tolerance)三個特性中的兩個，三個特性的定義如下：
數據一致性：等同於所有節點擁有數據的最新版本可用性：數據具備高可用性分區容忍：容忍網絡出現分區，分區之間網絡不可達在大規模的分佈式環境下，網絡分區是必須容忍的現實，於是只能在可用性和一致性兩者間做出選擇，CAP理論似乎給分佈式系統定義了一個悲觀的結局，一時間大家都按照CAP理論在對熱門的分佈式系統進行判定，譬如認為HBase是一個CP系統、Cassandra是AP系統。
我個人認為這是不嚴謹的，理由是CAP理論是對分佈式系統中一個數據無法同時達到可用性和一致性的斷言，而一個系統中往往存在很多類型的數據，部分數據（譬如銀行賬戶中的餘額）是需要強一致性的，而另外一部分數據（譬如銀行的總客戶數）並不要求強一致性，所以拿CAP理論來劃分整個系統是不嚴謹的， CAP理論帶來的價值是指引我們在設計分佈式系統時需要區分各種數據的特點，並仔細考慮在小概率的網絡分區發生時究竟為該數據選擇可用性還是一致性。
對CAP理論的另外一種誤讀是系統設計時選擇其一而完全不去優化另外一項，可用性和一致性的取值範圍並不是只有0和1，可用性的值域可以定義成0到100%的連續區間，而一致性也可分為強一致性、弱一致性、讀寫一致性、最終一致性等多個不同的強弱等級，細想下去CAP理論定義的其實是在容忍網絡分區的條件下，“強一致性”和“極致可用性”無法同時達到。
（注：這裡用“極致可用性”而不用“100%可用性”是因為即使不考慮一致性，多臺server組成的分佈式系統也達不到100%的可用性，如果單個server的可用性是P，那n臺server的極致可用性是
，公式的意思是隻要任何一臺或多臺server可用就認為系統都是可用的）
雖然無法達到同時達到強一致性和極致可用性，但我們可以根據數據類型在二者中選擇其一後去優化另外一個，Paxos協議就是一種在保證強一致性前提下把可用性優化到極限的算法。
Paxos協議
Paxos協議由Leslie Lamport最早在1990年提出，由於Paxos在雲計算領域的廣泛應用Leslie Lamport因此獲得了2013年度圖靈獎。
Paxos協議提出只要系統中2f+1個節點中的f+1個節點可用，那麼系統整體就可用並且能保證數據的強一致性，它對於可用性的提升是極大的，仍然假設單節點的可用性是P，那麼2f+1個節點中任意組合的f+1以上個節點正常的可用性P(total)=
，又假設P=0.99，f=2，P(total)=0.9999901494，可用性將從單節點的2個9提升到了5個9，這意味著系統每年的宕機時間從87.6小時降到0.086小時，這已經可以滿足地球上99.99999999%的應用需求。
Leslie寫的兩篇論文：《The Part-Time Parliament》和《Paxos Made Simple》比較完整的闡述了Paxos的工作流程和證明過程，Paxos協議把每個數據寫請求比喻成一次提案（proposal），每個提案都有一個獨立的編號，提案會轉發到提交者（Proposer）來提交，提案必須經過2f+1個節點中的f+1個節點接受才會生效，2f+1個節點叫做這次提案的投票委員會(Quorum)，投票委員會中的節點叫做Acceptor，Paxos協議流程還需要滿足兩個約束條件：
a）Acceptor必須接受它收到的第一個提案；
b）如果一個提案的v值被大多數Acceptor接受過，那後續的所有被接受的提案中也必須包含v值（v值可以理解為提案的內容，提案由一個或多個v和提案編號組成）。
Paxos協議流程劃分為兩個階段，第一階段是Proposer學習提案最新狀態的準備階段；第二階段是根據學習到的狀態組成正確提案提交的階段，完整的協議過程如下：
階段 1
階段 2
如果Proposer收到來自半數以上的Acceptor對於它的prepare請求(編號為n )的響應，那麼它就會發送一個針對編號為 n ，value值為 v 的提案的accept請求給Acceptors，在這裡 v 是收到的響應中編號最大的提案的值，如果響應中不包含提案，那麼它就是任意值。如果Acceptor收到一個針對編號n 的提案的accept請求，只要它還未對編號大於 n 的prepare請求作出響應，它就可以通過這個提案。
用時序圖來描述Paxos協議如圖3所示：
圖3：Paxos協議流程的時序圖
圖3：Paxos協議流程的時序圖
上述Paxos協議流程看起來比較複雜，是因為要保證很多邊界條件下的協議完備性，譬如初試值為空、兩個Proposer同時提交提案等情況，但Paxos協議的核心可以簡單描述為：Proposer先從大多數Acceptor那裡學習提案的最新內容，然後根據學習到的編號最大的提案內容組成新的提案提交，如果提案獲得大多數Acceptor的投票通過就意味著提案被通過。由於學習提案和通過提案的Acceptor集合都超過了半數，所以一定能學到最新通過的提案值，兩次提案通過的Acceptor集合中也一定存在一個公共的Acceptor，在滿足約束條件b時這個公共的Acceptor時保證了數據的一致性，於是Paxos協議又被稱為多數派協議。
Paxos協議的真正偉大之處在於它的簡潔性，Paxos協議流程中任何消息都是可以丟失的，一致性保證並不依賴某個特殊消息傳遞的成功，這極大的簡化了分佈式系統的設計，極其匹配分佈式環境下網絡可能分區的特點，相比較在Paxos協議之前的“兩階段提交（2PC）”也能保證數據強一致性，但複雜度相當高且依賴單個協調者的可用性。
那既然Paxos如此強大，那為什麼還會出現ZAB協議？
ZAB協議
Paxos協議雖然是完備的，但要把它應用到實際的分佈式系統中還有些問題要解決：
在多個Proposer的場景下，Paxos不保證先提交的提案先被接受，實際應用中要保證多提案被接受的先後順序怎麼辦？Paxos允許多個Proposer提交提案，那有可能出現活鎖問題，出現場景是這樣的：提案n在第二階段還沒有完成時，新的提案n+1的第一階段prepare請求到達Acceptor，按協議規定Acceptor將響應新提案的prepare請求並保證不會接受小於n+1的任何請求，這可能導致提案n將不會被通過，同樣在n+1提案未完成第二階段時，假如提案n的提交者又提交了n+2提案，這可能導致n+1提案也無法通過。Paxos協議規定提案的值v只要被大多數Acceptor接受過，後續的所有提案不能修改值v，那現實情況下我還要修改v值怎麼辦？
ZooKeeper的核心算法ZAB通過一個簡單的約束解決了前2個問題：所有提案都轉發到唯一的Leader（通過Leader選舉算法從Acceptor中選出來的）來提交，由Leader來保證多個提案之間的先後順序，同時也避免了多Proposer引發的活鎖問題。
ZAB協議的過程用時序圖描述如圖4所示，相比Paxos協議省略了Prepare階段，因為Leader本身就有提案的最新狀態，不需要有提案內容學習的過程,圖中的Follower對應Paxos協議中的Acceptor，Observer對應Paxos中的Learner。
圖4：ZAB協議的工作過程
圖4：ZAB協議的工作過程
ZAB引入Leader後也會帶來一個新問題： Leader宕機了怎麼辦？其解決方案是選舉出一個新的Leader，選舉Leader的過程也是一個Paxos提案決議過程，這裡不展開討論。
那如何做到提案的值v可以修改呢？這不是ZAB協議的範疇，研究ZooKeeper源碼後發現它是這麼做的：ZooKeeper提供了一個znode的概念，znode可以被修改，ZooKeeper對每個znode都記錄了一個自增且連續的版本號，對znode的任何修改操作（create/set/setAcl）都會促發一次Paxos多數派投票過程，投票通過後znode版本號加1，這相當於用znode不同版本的多次Paxos協議來破除單次Paxos協議無法修改提案值的限制。
從保證一致性的算法核心角度看ZAB確實是借鑑了Paxos的多數派思想，但它提供的全局時序保證以及ZooKeeper提供給用戶可修改的znode才讓Paxos在開源界大放異彩，所以ZAB的價值不僅僅是提供了Paxos算法的優化實現，也難怪ZAB的作者一直強調ZAB和Paxos是不一樣的算法。
總結
CAP理論告訴我們在分佈式環境下網絡分區無法避免，需要去權衡選擇數據的一致性和可用性，Paxos協議提出了一種極其簡單的算法在保障數據一致性時最大限度的優化了可用性，ZooKeeper的ZAB協議把Paxos更加簡化，並提供全局時序保證，使得Paxos能夠廣泛應用到工業場景。
加Java架構師進階交流群獲取Java工程化、高性能及分佈式、高性能、深入淺出。高架構。性能調優、Spring，MyBatis，Netty源碼分析和大數據等多個知識點高級進階乾貨的直播免費學習權限 都是大牛帶飛 讓你少走很多的彎路的 群號是：883922439 對了 小白勿進 最好是有開發經驗
注：加群要求
1、具有工作經驗的，面對目前流行的技術不知從何下手，需要突破技術瓶頸的可以加。
2、在公司待久了，過得很安逸，但跳槽時面試碰壁。需要在短時間內進修、跳槽拿高薪的可以加。
3、如果沒有工作經驗，但基礎非常紮實，對java工作機制，常用設計思想，常用java開發框架掌握熟練的，可以加。
4、覺得自己很牛B，一般需求都能搞定。但是所學的知識點沒有系統化，很難在技術領域繼續突破的可以加。
5.阿里Java高級大牛直播講解知識點，分享知識，多年工作經驗的梳理和總結，帶著大家全面、科學地建立自己的技術體系和技術認知！