ZooKeeper的ZAB協定。

        ZooKeeper并沒有完全采用Paxos算法，而是使用了一種稱為ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息廣播協定）的協定作為其資料一緻性的核心算法。

        ZAB協定是為分布式協調服務ZooKeeper專門設計的一種支援崩潰恢複的原子廣播協定。在ZooKeeper的官方文檔中指出，ZAB協定并不像Paxos算法那樣，是一種通用的分布式一緻性算法，他是一種特别為ZooKeeper的設計的崩潰可恢複的原子消息廣播算法。

        在ZooKeeper中，主要依賴ZAB協定來實作分布式資料一緻性，基于該協定，ZooKeeper實作了一種主備模式的系統架構來保持叢集中各副本之間資料的一緻性。具體的，ZooKeeper使用一個單一的主程序來接收并處理用戶端的所有事務請求，并采用ZAB的原子廣播協定，将伺服器資料的狀态變更以事務Proposal的形式廣播到所有的副本程序上去。ZAB協定的這個主備模型架構保證了同一時刻叢集中隻能夠有一個主程序來廣播伺服器的狀态變更，是以能夠很好的處理用戶端大量的并發請求。另一方面，考慮到在分布式環境中，順序執行的一些狀态變更其前後會存在一定的依賴關系，有些狀态變更必須依賴于比他早生成的那些狀态變更，例如變更C需要依賴變更A和變更B。這樣的依賴關系也對ZAB協定提出了一個要求：ZAB協定必須能夠保證一個全局的變更序列被順序應用，也就是說，ZAB協定需要保證如果一個狀态變更已經被處理了，那麼所有其依賴的狀态變更都i用改已經被提前處理掉了。最後，考慮到主程序在任何時候都有可能出現崩潰退出或重新開機現象。是以，ZAB協定還需要做到在目前主程序出現上述異常情況的時候，依舊能夠正常工作。

        ZAB協定的核心是定義了對于那些會改變ZooKeeper伺服器資料狀态的事務請求的處理方式，即：

所有事務請求必須由一個全局唯一的伺服器來協調處理，這樣的伺服器被稱為Leader伺服器，而餘下的其他伺服器則成為Follower伺服器。Leader伺服器負責将一個用戶端事務請求轉換成一個事務Proposal（提議），并将該Proposal分發給叢集中所有的Follower伺服器。之後Leader伺服器需要等待所有Follower伺服器的回報，一旦超過半數的Follower伺服器進行了正确的回報後，那麼Leader就會再次向所有的Follower伺服器分發Commit消息，要求其将前一個Proposal進行送出。

協定介紹

        ZAB協定包括兩種基本的模式，分别是崩潰恢複和消息廣播。當整個服務架構在啟動過程中，或是當Leader伺服器出現網絡中斷、崩潰退出與重新開機等異常情況時，ZAB協定就會進入恢複模式并選舉産生新的Leader伺服器。當選舉産生了新的Leader伺服器，同時叢集中已經有過半的機器與該Leader伺服器完成了狀态同步之後，ZAB協定就會退出恢複模式。其中，所謂的狀态同步是指資料同步，用來保證叢集中存在過半的機器能夠和Leader伺服器的資料狀态保持一緻。

        當叢集中已經有過半的Follower伺服器完成了和Leader伺服器的狀态同步，那麼整個服務架構就可以進入消息廣播模式了。當一台同樣遵守ZAB協定的伺服器啟動後加入到叢集中時，如果此時叢集中已經存在一個Leader伺服器在負責進行消息廣播，那麼新加入的伺服器就會自覺的進入資料恢複模式；找到Leader所在的伺服器，并與其進行資料同步，然後一起參與到消息廣播流程中去。正如上文介紹中所說的，ZooKeeper設計成隻允許唯一的一個Leader伺服器來進行事務請求的處理。Leader伺服器在接收到用戶端的事務請求後，會生成對應的事務提案并發起一輪廣播協定；而如果叢集中的其他機器接收到用戶端的事務請求，那麼這些非Leader伺服器會首先将這個事務請求轉發給Leader伺服器。

        當Leader伺服器出現崩潰退出或機器重新開機，亦或是叢集中已經不存在過半的伺服器與該Leader伺服器保持正常通信時，那麼在重新開始新一輪的原子廣播事務操作之前，所有程序首先會使用崩潰恢複協定來使彼此達到一個一緻的狀态，于是整個ZAB流程就會從消息廣播模式進入到崩潰恢複模式。

        一個機器要成為新的Leader，必須獲得過半程序的支援，同時由于每個程序都有可能會崩潰，是以，在ZAB協定運作過程中，前後會出現多個Leader，并且每個程序也有可能會崩潰，是以，在ZAB協定運作過程中，前後會出現多個Leader，并且每個程序也有可能會多次成為Leader。進入崩潰恢複模式後，隻要叢集中存在過半的伺服器能夠彼此進行正常通信，那麼就可以産生一個新的Leader并再次進入消息廣播模式。舉個例子來說，一個由3台機器組成的ZAB服務，通常由1個Leader、2個Follower伺服器組成。某一個時刻，假如其中一個Follower伺服器挂了，整個ZAB叢集中不會中斷服務的，這是因為Leader伺服器依然能夠獲得過半機器（包括Leader自己）的支援。

消息廣播

        ZAB協定的消息廣播過程使用的是一個原子廣播協定，類似于一個二階段送出過程。針對用戶端的事務請求，Leader伺服器會為其生成對應的事務Proposal，并将其發送給叢集中其餘所有的機器，然後再分别收集各自的選票，最後進行事務送出，下圖所示就是ZAB協定消息廣播流程的示意圖。

        此處ZAB協定中涉及的二階段送出過程則與其略有不同。在ZAB協定的二階段送出過程中，移除了中斷邏輯，所有的Follower伺服器要麼正常回報Leader提出的事務Proposal，要麼就抛棄Leader伺服器。同時，ZAB協定将二階段送出中的中斷邏輯移除意味着我們可以在過半的Follower伺服器已經回報Ack之後就開始送出事務Proposal了，而不需要等待叢集中所有的Follower伺服器都回報響應。當然，在這種簡化了的二階段送出模型下，是無法處理Leader伺服器崩潰退出而帶來的資料不一緻問題的，是以在ZAB協定中添加了另一個模式，即采用崩潰恢複模式來解決這個問題。另外，整個消息傳播協定是基于具有FIFO特性的TCP協定來進行網絡通信的，是以能夠很容易的保證消息廣播過程中消息接收與發送的順序性。

        在整個消息廣播中，Leader伺服器會為每個事務請求生成對應的Proposal來進行廣播，并且在廣播事務Proposal之前，Leader伺服器會首先為這個事務Proposal配置設定一個全局單調遞增的唯一ID，我們稱之為事務ID（即ZXID）。由于ZAB協定需要保證每一個消息嚴格的因果關系，是以必須将每一個事務Proposal按照其ZXID的先後順序來進行排序與處理。

        具體的，在消息廣播過程中，Leader伺服器會為每一個Follower伺服器都各自配置設定一個單獨的隊列，然後将需要廣播的事務Proposal依次放入這些隊列中去，并且根據FIFO政策進行消息發送。每一個Follower伺服器在接收到這個事務Proposal之後，都會首先将其以事務日志的形式寫入到本地磁盤中去，并且在成功寫入後回報給Leader伺服器一個Ack響應。當Leader伺服器接收到超過半數Follower的Ack響應後，就會廣播一個Commit消息給所有的Follower伺服器以通知其進行事務送出，同時Leader自身也會完成對事務的送出，而每一個Follower伺服器在接收到Commit消息後，也會完成對事務的送出。

崩潰恢複

        上面我們主要講解了ZAB協定中的消息廣播過程。ZAB協定的這個基于原子廣播協定的消息傳播過程，在正常情況下運作非常良好，但是一旦Leader伺服器出現崩潰，或者說由于網絡原因導緻Leader伺服器失去了與過半Follower聯系，那麼就會進入崩潰恢複模式。在ZAB協定中，為了保證程式的正确運作，整個恢複過程結束後需要選舉出一個新的Leader伺服器。是以，ZAB協定需要一個高效且可靠的Leader選舉算法，進而確定能夠快速地選舉出新的Leader。同時，Leader選舉算法不僅僅需要讓Leader自己知道其自身已經被選舉為Leader，同時還需要讓叢集中的所有其他機器也能夠快速的感覺到選舉産生的新的Leader伺服器。

基本特性

        根據上面的内容，我們了解到，ZAB協定規定了如果一個事務Proposal在一台機器上被處理成功，那麼應該在所有的機器上都被處理成功，哪怕機器出現故障崩潰。接下來我們看看在崩潰恢複過程中，可能會出現的兩個資料不一緻性的隐患及針對這些情況ZAB協定所需要保證的特性。

        ZAB 協定需要確定那些已經在Leader伺服器上送出的事務最終被所有伺服器都送出

假設一個事務在Leader伺服器上被送出了，并且已經得到過半Follower伺服器的Ack回報，但是在他将Commit消息發送給所有Follower機器之前，Leader伺服器挂了，如下圖所示。

上圖的消息C2就是一個典型的例子：在叢集正常運作過程中的某一個時刻，Server 1 是Leader伺服器，其先後廣播了消息P1、P2、C1、P3和C2，其中，當Leader伺服器将消息C2（C2是Commit Of Proposal2的縮寫，即送出事務Proposal2）發出後就立即崩潰退出了。針對這種情況，ZAB協定就需要確定事務Proposal2最終能夠在所有的伺服器上都被送出成功，否則将出現不一緻。

        ZAB協定需要確定丢棄那些隻在Leader伺服器上被提出的事務

相反，如果在崩潰恢複過程中出現一個需要被丢棄的提案，那麼子啊崩潰恢複結束後需要跳過該事務Proposal，如下圖所示。

在上圖所示的叢集中，假設出事的Leader伺服器Server1 在提出了一個事務Proposal3之後就崩潰退出了，進而導緻叢集中的其他伺服器都沒有收到這個事務Proposal。于是，當Server1恢複過來再次加入到叢集中的時候，ZAB協定需要確定丢棄Proposal3這個事務。

        結合上面提到的這兩個崩潰恢複過程中需要處理的特殊情況，就決定了ZAB協定必須設計這樣一個Leader選舉算法：能夠確定送出已經被Leader送出的事務Proposal，同時丢棄已經被跳過的事務Proposal。針對這個要求，如果讓Leader選舉算法能夠保證新選舉出來的Leader伺服器擁有叢集中所有機器最高編号（即ZXID最大）的事務Proposal，那麼就可以保證這個新選舉出來的Leader一定具有所有已經送出的提案。更為重要的是，如果讓具有最高編号事務Proposal的機器來成為Leader，就可以省去Leader伺服器檢查Proposal的送出和丢棄工作的這一步操作了。

資料同步

        完成Leader選舉之後，在正式開始工作（即接收用戶端的事務請求，然後提出新的提案）之前，Leader伺服器會首先确認事務日志中的所有Proposal是否都已經被叢集中過半的機器送出了，即是否完成資料同步。下main我們就來看看ZAB協定的資料同步過程。

        所有正常運作的伺服器，要麼成為Leader，要麼成為Follower并和Leader保持同步。Leader伺服器需要確定所有的Follower伺服器能夠接收到每一條事務Proposal，并且能夠正确的将所有已經送出了的事務Proposal應用到記憶體資料庫中去。具體的，Leader伺服器會為每一個Follower伺服器都準備一個隊列，并将那些沒有被Follower伺服器同步的事務以Proposal消息的形式逐個發送給Follower伺服器，并在每一個Proposal消息後面緊接着再發送一個Commit消息，以表示該事務已經被送出。等到Follower伺服器将所有其尚未同步的事務Proposal都從Leader伺服器上同步過來并成功應用到本地資料庫中後，Leader伺服器就會将該Follower伺服器加入到真正的可用Follower清單中，并開始之後的其他流程。

        上面講到的是正常情況下的資料同步邏輯，下面來看ZAB協定是如何處理那些需要被丢棄的事務Proposal的。在ZAB協定的事務編号ZXID設計中，ZXID是一個64位的數字，其中低32位可以看作是一個簡單的單調遞增的計數器，針對用戶端的每一個事務請求，Leader伺服器在産生一個新的事務Proposal的時候，都會對該計數器進行加1操作；而高32位則代表了Leader周期epoch的編号，每當選舉産生一個新的Leader伺服器，就會從這個Leader伺服器上取出其本地日志彙總最大事務Proposal的ZXID，并從該ZXID中解析出對應的epoch值，然後再對其進行加1操作，之後就會以此編号作為新的epoch，并将32位置0來開始生成新的ZXID。ZAB協定中的這一通過epoch編号來區分Leader周期變化的政策，能夠有效地避免不同的Leader伺服器錯誤的使用相同的ZXID編号提出不一樣的事務Proposal的異常情況，這對于識别在Leader崩潰恢複前後生成的Proposal非常有幫助，大大簡化和提升了資料恢複流程。

        基于這樣的政策，當一個包含了上一個Leader周期中尚未送出過的事務Proposal的伺服器啟動時，其肯定無法成為Leader，原因很簡單，因為目前叢集中一定包含一個Quorum集合，該集合中的機器一定包含了更高epoch的事務Proposal，是以這台機器的事務Proposal肯定不是最高，也就是無法成為Leader了。當這台機器加入到叢集中，以Follower角色連接配接上Leader伺服器之後，Leader伺服器會根據自己伺服器上最後被送出的Proposal來和Follower伺服器的Proposal進行比對，比對的結果當然是Leader會要求Follower進行一個回退操作——回退到一個确實已經被叢集中過半機器送出的最新的事務Proposal。