Hadoop學習筆記（三）——zookeeper的一緻性協定：ZAB

ZAB：ZooKeeper的Atomic Broadcast協定，能夠保證發給各副本的消息順序相同。

Zookeeper使用了一種稱為Zab（ZookeeperAtomic Broadcast）的協定作為其一緻性複制的核心，其特點為高吞吐量、低延遲、健壯、簡單，但不過分要求其擴充性。

Zookeeper的實作是有Client、Server構成，Server端提供了一個一緻性複制、存儲服務，Client端會提供一些具體的語義，比如分布式鎖、選舉算法、分布式互斥等。從存儲内容來說，Server端更多的是存儲一些資料的狀态，而非資料内容本身，是以Zookeeper可以作為一個小檔案系統使用。資料狀态的存儲量相對不大，完全可以全部加載到記憶體中，進而極大地消除了通信延遲。

Server可以Crash後重新開機，考慮到容錯性，Server必須“記住”之前的資料狀态，是以資料需要持久化，但吞吐量很高時，磁盤的IO便成為系統瓶頸，其解決辦法是使用緩存，把随機寫變為連續寫。

考慮到Zookeeper主要操作資料的狀态，為了保證狀态的一緻性，Zookeeper提出了兩個安全屬性（Safety Property）：

• 全序（Total order）：如果消息a在消息b之前發送，則所有Server應該看到相同的結果
• 因果順序（Causal order）：如果消息a在消息b之前發生（a導緻了b），并被一起發送，則a始終在b之前被執行。

為了保證上述兩個安全屬性，Zookeeper使用了TCP協定和Leader。通過使用TCP協定保證了消息的全序特性（先發先到），通過Leader解決了因果順序問題：先到Leader的先執行。因為有了Leader，Zookeeper的架構就變為：Master-Slave模式，但在該模式中Master（Leader）會Crash，是以，Zookeeper引入了Leader選舉算法，以保證系統的健壯性。歸納起來Zookeeper整個工作分兩個階段：

• Atomic Broadcast
• Leader選舉

1.Atomic Broadcast

同一時刻存在一個Leader節點，其他節點稱為“Follower”，如果是更新請求，如果用戶端連接配接到Leader節點，則由Leader節點執行其請求；如果連接配接到Follower節點，則需轉發請求到Leader節點執行。但對讀請求，Client可以直接從Follower上讀取資料，如果需要讀到最新資料，則需要從Leader節點進行，Zookeeper設計的讀寫比例是2：1。

Leader通過一個簡化版的二段送出模式向其他Follower發送請求，但與二段送出有兩個明顯的不同之處：

• 因為隻有一個Leader，Leader送出到Follower的請求一定會被接受（沒有其他Leader幹擾）

• 不需要所有的Follower都響應成功，隻要一個多數派即可

通俗地說，如果有2f+1個節點，允許f個節點失敗。因為任何兩個多數派必有一個交集，當Leader切換時，通過這些交集節點可以獲得目前系統的最新狀态。如果沒有一個多數派存在（存活節點數小于f+1）則，算法過程結束。但有一個特例：

如果有A、B、C三個節點，A是Leader，如果B Crash，則A、C能正常工作，因為A是Leader，A、C還構成多數派；如果A Crash則無法繼續工作，因為Leader選舉的多數派無法構成。

2. Leader Election

Leader選舉主要是依賴Paxos算法，Leader選舉遇到的最大問題是，”新老互動“的問題，新Leader是否要繼續老Leader的狀态。這裡要按老Leader Crash的時機點分幾種情況：

1. 老Leader在COMMIT前Crash（已經送出到本地）

2. 老Leader在COMMIT後Crash，但有部分Follower接收到了Commit請求

第一種情況，這些資料隻有老Leader自己知道，當老Leader重新開機後，需要與新Leader同步并把這些資料從本地删除，以維持狀态一緻。

第二種情況，新Leader應該能通過一個多數派獲得老Leader送出的最新資料，老Leader重新開機後，可能還會認為自己是Leader，可能會繼續發送未完成的請求，進而因為兩個Leader同時存在導緻算法過程失敗，解決辦法是把Leader資訊加入每條消息的id中，Zookeeper中稱為zxid，zxid為一64位數字，高32位為leader資訊又稱為epoch，每次leader轉換時遞增；低32位為消息編号，Leader轉換時應該從0重新開始編号。通過zxid，Follower能很容易發現請求是否來自老Leader，進而拒絕老Leader的請求。

因為在老Leader中存在着資料删除（情況1），是以Zookeeper的資料存儲要支援補償操作，這也就需要像資料庫一樣記錄log。

3. Zab與Paxos

Zab的作者認為Zab與paxos并不相同，Zab就是Paxos的一種簡化形式，Paxos保證不了全序順序。

這裡首要一點是Paxos的一緻性不能達到ZooKeeper的要求。舉個例子：假設一開始Paxos系統中的leader是P1，他發起了兩個事務<t1, v1>（表示序号為t1的事務要寫的值是v1）和<t2, v2>，過程中挂了。新來個leader是P2，他發起了事務<t1, v1'>。而後又來個新leader是P3，他彙總了一下，得出最終的執行序列<t1, v1'>和<t2, v2>，即P2的t1在前，P1的t2在後。

分析為什麼不滿足ZooKeeper需求：

ZooKeeper是一個樹形結構，很多操作都要先檢查才能确定能不能執行，比如P1的事務t1可能是建立節點“/a”，t2可能是建立節點“/a/aa”，隻有先建立了父節點“/a”，才能建立子節點“/a/aa”。而P2所發起的事務t1可能變成了建立“/b”。這樣P3彙總後的序列是先建立“/b”再建立“/a/aa”，由于“/a”還沒建，建立“a/aa”就搞不定了。

解決方案：

為了保證這一點，ZAB要保證同一個leader的發起的事務要按順序被apply，同時還要保證隻有先前的leader的所有事務都被apply之後，新選的leader才能在發起事務。

ZAB的核心思想：形象的說就是保證任意時刻隻有一個節點是leader，所有更新事務由leader發起去更新所有複本（稱為follower），更新時用的就是兩階段送出協定，隻要多數節點prepare成功，就通知他們commit。各follower要按當初leader讓他們prepare的順序來apply事務。因為ZAB處理的事務永遠不會復原，ZAB的2PC做了點優化，多個事務隻要通知zxid最大的那個commit，之前的各follower會統統commit。

這裡有幾個關鍵點：

1、leader所follower之間通過心跳來檢測異常；

2、檢測到異常之後的節點若試圖成為新的leader，首先要獲得大多數節點的支援，然後從狀态最新的節點同步事務，完成後才可正式成為leader發起事務；

3、區分新老leader的關鍵是一個會一直增長的epoch；

4.結束

本文隻是想從協定、算法的角度分析Zookeeper，而非分析其源碼實作，因為Zookeeper版本的變化，文中描述的場景或許已找不到對應的實作。

 後續不斷完善更新……