jinfeng_wang

一、前言

　　在學習了Paxos在Chubby中的應用后，接下來學習Paxos在開源軟件Zookeeper中的應用。

二、Zookeeper

　　Zookeeper是一個開源的分布式協調服務，其設計目標是將那些復雜的且容易出錯的分布式一致性服務封裝起來，構成一個高效可靠的原語集，并以一些列簡單的接口提供給用戶使用。其是一個典型的分布式數據一致性的解決方案，分布式應用程序可以基于它實現諸如數據發布/發布、負載均衡、命名服務、分布式協調/通知、集群管理、Master選舉、分布式鎖和分布式隊列等功能。其可以保證如下分布式一致性特性。

　　① 順序一致性，從同一個客戶端發起的事務請求，最終將會嚴格地按照其發起順序被應用到Zookeeper中去。

　　② 原子性，所有事務請求的處理結果在整個集群中所有機器上的應用情況是一致的，即整個集群要么都成功應用了某個事務，要么都沒有應用。

　　③ 單一視圖，無論客戶端連接的是哪個Zookeeper服務器，其看到的服務端數據模型都是一致的。

　　④ 可靠性，一旦服務端成功地應用了一個事務，并完成對客戶端的響應，那么該事務所引起的服務端狀態變更將會一直被保留，除非有另一個事務對其進行了變更。

　　⑤ 實時性，Zookeeper保證在一定的時間段內，客戶端最終一定能夠從服務端上讀取到最新的數據狀態。

　　2.1 設計目標

　　Zookeeper致力于提供一個高性能、高可用、且具有嚴格的順序訪問控制能力（主要是寫操作的嚴格順序性）的分布式協調服務，其具有如下的設計目標。

　　① 簡單的數據模型，Zookeeper使得分布式程序能夠通過一個共享的樹形結構的名字空間來進行相互協調，即Zookeeper服務器內存中的數據模型由一系列被稱為ZNode的數據節點組成，Zookeeper將全量的數據存儲在內存中，以此來提高服務器吞吐、減少延遲的目的。

　　② 可構建集群，一個Zookeeper集群通常由一組機器構成，組成Zookeeper集群的而每臺機器都會在內存中維護當前服務器狀態，并且每臺機器之間都相互通信。

　　③ 順序訪問，對于來自客戶端的每個更新請求，Zookeeper都會分配一個全局唯一的遞增編號，這個編號反映了所有事務操作的先后順序。

　　④ 高性能，Zookeeper將全量數據存儲在內存中，并直接服務于客戶端的所有非事務請求，因此它尤其適用于以讀操作為主的應用場景。

　　2.2 基本概念

　　① 集群角色，最典型的集群就是Master/Slave模式（主備模式），此情況下把所有能夠處理寫操作的機器稱為Master機器，把所有通過異步復制方式獲取最新數據，并提供讀服務的機器為Slave機器。Zookeeper引入了Leader、Follower、Observer三種角色，Zookeeper集群中的所有機器通過Leaser選舉過程來選定一臺被稱為Leader的機器，Leader服務器為客戶端提供寫服務，Follower和Observer提供讀服務，但是Observer不參與Leader選舉過程，不參與寫操作的過半寫成功策略，Observer可以在不影響寫性能的情況下提升集群的性能。

　　② 會話，指客戶端會話，一個客戶端連接是指客戶端和服務端之間的一個TCP長連接，Zookeeper對外的服務端口默認為2181，客戶端啟動的時候，首先會與服務器建立一個TCP連接，從第一次連接建立開始，客戶端會話的生命周期也開始了，通過這個連接，客戶端能夠心跳檢測與服務器保持有效的會話，也能夠向Zookeeper服務器發送請求并接受響應，同時還能夠通過該連接接受來自服務器的Watch事件通知。

　　③ 數據節點，第一類指構成集群的機器，稱為機器節點，第二類是指數據模型中的數據單元，稱為數據節點-Znode，Zookeeper將所有數據存儲在內存中，數據模型是一棵樹，由斜杠/進行分割的路徑，就是一個ZNode，如/foo/path1，每個ZNode都會保存自己的數據內存，同時還會保存一些列屬性信息。ZNode分為持久節點和臨時節點兩類，持久節點是指一旦這個ZNode被創建了，除非主動進行ZNode的移除操作，否則這個ZNode將一直保存在Zookeeper上，而臨時節點的生命周期和客戶端會話綁定，一旦客戶端會話失效，那么這個客戶端創建的所有臨時節點都會被移除。另外，Zookeeper還允許用戶為每個節點添加一個特殊的屬性：SEQUENTIAL。一旦節點被標記上這個屬性，那么在這個節點被創建的時候，Zookeeper會自動在其節點后面追加一個整形數字，其是由父節點維護的自增數字。

　　④ 版本，對于每個ZNode，Zookeeper都會為其維護一個叫作Stat的數據結構，Stat記錄了這個ZNode的三個數據版本，分別是version（當前ZNode的版本）、cversion（當前ZNode子節點的版本）、aversion（當前ZNode的ACL版本）。

　　⑤ Watcher，Zookeeper允許用戶在指定節點上注冊一些Watcher，并且在一些特定事件觸發的時候，Zookeeper服務端會將事件通知到感興趣的客戶端。

　　⑥ ACL，Zookeeper采用ACL（Access Control Lists）策略來進行權限控制，其定義了如下五種權限：

　　　　· CREATE：創建子節點的權限。

　　　　· READ：獲取節點數據和子節點列表的權限。

　　　　· WRITE：更新節點數據的權限。

　　　　· DELETE：刪除子節點的權限。

　　　　· ADMIN：設置節點ACL的權限。

　　2.3 ZAB協議

　　Zookeeper使用了Zookeeper Atomic Broadcast（ZAB，Zookeeper原子消息廣播協議）的協議作為其數據一致性的核心算法。ZAB協議是為Zookeeper專門設計的一種支持崩潰恢復的原子廣播協議。

　　Zookeeper依賴ZAB協議來實現分布式數據的一致性，基于該協議，Zookeeper實現了一種主備模式的系統架構來保持集群中各副本之間的數據的一致性，即其使用一個單一的諸進程來接收并處理客戶端的所有事務請求，并采用ZAB的原子廣播協議，將服務器數據的狀態變更以事務Proposal的形式廣播到所有的副本進程中，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，并且每臺機器也有可能會多次成為Leader，進入崩潰恢復模式后，只要集群中存在過半的服務器能夠彼此進行正常通信，那么就可以產生一個新的Leader并再次進入消息廣播模式。如一個由三臺機器組成的ZAB服務，通常由一個Leader、2個Follower服務器組成，某一個時刻，加入其中一個Follower掛了，整個ZAB集群是不會中斷服務的。

　　① 消息廣播，ZAB協議的消息廣播過程使用原子廣播協議，類似于一個二階段提交過程，針對客戶端的事務請求，Leader服務器會為其生成對應的事務Proposal，并將其發送給集群中其余所有的機器，然后再分別收集各自的選票，最后進行事務提交。

　　在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服務器出現崩潰，或者由于網絡原因導致Leader服務器失去了與過半Follower的聯系，那么就會進入崩潰恢復模式，在ZAB協議中，為了保證程序的正確運行，整個恢復過程結束后需要選舉出一個新的Leader服務器，因此，ZAB協議需要一個高效且可靠的Leader選舉算法，從而保證能夠快速地選舉出新的Leader，同時，Leader選舉算法不僅僅需要讓Leader自身知道已經被選舉為Leader，同時還需要讓集群中的所有其他機器也能夠快速地感知到選舉產生的新的Leader服務器。

　　③ 基本特性，ZAB協議規定了如果一個事務Proposal在一臺機器上被處理成功，那么應該在所有的機器上都被處理成功，哪怕機器出現故障崩潰。ZAB協議需要確保那些已經在Leader服務器上提交的事務最終被所有服務器都提交，假設一個事務在Leader服務器上被提交了，并且已經得到了過半Follower服務器的Ack反饋，但是在它Commit消息發送給所有Follower機器之前，Leader服務掛了。如下圖所示

　　在集群正常運行過程中的某一個時刻，Server1是Leader服務器，其先后廣播了P1、P2、C1、P3、C2（C2是Commit Of Proposal2的縮寫），其中，當Leader服務器發出C2后就立即崩潰退出了，針對這種情況，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是否都已經被集群中的過半機器提交了，即是否完成了數據同步。Leader服務器需要確所有的Follower服務器都能夠接收到每一條事務Proposal，并且能夠正確地將所有已經提交了的事務Proposal應用到內存數據庫中。Leader服務器會為每個Follower服務器維護一個隊列，并將那些沒有被各Follower服務器同步的事務以Proposal消息的形式逐個發送給Follower服務器，并在每一個Proposal消息后面緊接著再發送一個Commit消息，以表示該事務已經被提交，等到Follower服務器將所有其尚未同步的事務Proposal都從Leader服務器上同步過來并成功應用到本地數據庫后，Leader服務器就會將該Follower服務器加入到真正的可用Follower列表并開始之后的其他流程。

　　下面分析ZAB協議如何處理需要丟棄的事務Proposal的，ZXID是一個64位的數字，其中32位可以看做是一個簡單的單調遞增的計數器，針對客戶端的每一個事務請求，Leader服務器在產生一個新的事務Proposal時，都會對該計數器進行加1操作，而高32位則代表了Leader周期epoch的編號，每當選舉產生一個新的Leader時，就會從這個Leader上取出其本地日志中最大事務Proposal的ZXID，并解析出epoch值，然后加1，之后以該編號作為新的epoch，低32位則置為0來開始生成新的ZXID，ZAB協議通過epoch號來區分Leader周期變化的策略，能夠有效地避免不同的Leader服務器錯誤地使用不同的ZXID編號提出不一樣的事務Proposal的異常情況。當一個包含了上一個Leader周期中尚未提交過的事務Proposal的服務器啟動時，其肯定無法成為Leader，因為當前集群中一定包含了一個Quorum（過半）集合，該集合中的機器一定包含了更高epoch的事務的Proposal，因此這臺機器的事務Proposal并非最高，也就無法成為Leader。

　　2.4 ZAB協議原理

　　ZAB主要包括消息廣播和崩潰恢復兩個過程，進一步可以分為三個階段，分別是發現（Discovery）、同步（Synchronization）、廣播（Broadcast）階段。ZAB的每一個分布式進程會循環執行這三個階段，稱為主進程周期。

　　· 發現，選舉產生PL(prospective leader)，PL收集Follower epoch(cepoch)，根據Follower的反饋，PL產生newepoch(每次選舉產生新Leader的同時產生新epoch)。

　　· 同步，PL補齊相比Follower多數派缺失的狀態、之后各Follower再補齊相比PL缺失的狀態，PL和Follower完成狀態同步后PL變為正式Leader(established leader)。

　　· 廣播，Leader處理客戶端的寫操作，并將狀態變更廣播至Follower，Follower多數派通過之后Leader發起將狀態變更落地(deliver/commit)。

　　在正常運行過程中，ZAB協議會一直運行于階段三來反復進行消息廣播流程，如果出現崩潰或其他原因導致Leader缺失，那么此時ZAB協議會再次進入發現階段，選舉新的Leader。

　　2.4.1 運行分析

　　每個進程都有可能處于如下三種狀態之一

　　· LOOKING：Leader選舉階段。

　　· FOLLOWING：Follower服務器和Leader服務器保持同步狀態。

　　· LEADING：Leader服務器作為主進程領導狀態。

　　所有進程初始狀態都是LOOKING狀態，此時不存在Leader，此時，進程會試圖選舉出一個新的Leader，之后，如果進程發現已經選舉出新的Leader了，那么它就會切換到FOLLOWING狀態，并開始和Leader保持同步，處于FOLLOWING狀態的進程稱為Follower，LEADING狀態的進程稱為Leader，當Leader崩潰或放棄領導地位時，其余的Follower進程就會轉換到LOOKING狀態開始新一輪的Leader選舉。

　　一個Follower只能和一個Leader保持同步，Leader進程和所有與所有的Follower進程之間都通過心跳檢測機制來感知彼此的情況。若Leader能夠在超時時間內正常收到心跳檢測，那么Follower就會一直與該Leader保持連接，而如果在指定時間內Leader無法從過半的Follower進程那里接收到心跳檢測，或者TCP連接斷開，那么Leader會放棄當前周期的領導，比你轉換到LOOKING狀態，其他的Follower也會選擇放棄這個Leader，同時轉換到LOOKING狀態，之后會進行新一輪的Leader選舉，并在選舉產生新的Leader之后開始新的一輪主進程周期。

　　2.5 ZAB與Paxos的聯系和區別

　　聯系：

　　① 都存在一個類似于Leader進程的角色，由其負責協調多個Follower進程的運行。

　　② Leader進程都會等待超過半數的Follower做出正確的反饋后，才會將一個提議進行提交。

　　③ 在ZAB協議中，每個Proposal中都包含了一個epoch值，用來代表當前的Leader周期，在Paxos算法中，同樣存在這樣的一個標識，名字為Ballot。

　　區別：

　　Paxos算法中，新選舉產生的主進程會進行兩個階段的工作，第一階段稱為讀階段，新的主進程和其他進程通信來收集主進程提出的提議，并將它們提交。第二階段稱為寫階段，當前主進程開始提出自己的提議。

　　ZAB協議在Paxos基礎上添加了同步階段，此時，新的Leader會確保存在過半的Follower已經提交了之前的Leader周期中的所有事務Proposal。

　　ZAB協議主要用于構建一個高可用的分布式數據主備系統，而Paxos算法則用于構建一個分布式的一致性狀態機系統。

三、總結

　　此部分也還是理論知識偏多，學好理論之后再看代碼應該會更快速一些，也謝謝各位園友的觀看~