ZooKeeper之ZAB協定

ZooKeeper為高可用的一緻性協調架構，自然的ZooKeeper也有着一緻性算法的實作，ZooKeeper使用的是ZAB協定作為資料一緻性的算法，ZAB（ZooKeeper Atomic Broadcast ）全稱為：原子消息廣播協定；ZAB可以說是在Paxos算法基礎上進行了擴充改造而來的，ZAB協定設計了支援崩潰恢複，ZooKeeper使用單一主程序Leader用于處理用戶端所有事務請求，采用ZAB協定将伺服器數狀态以事務形式廣播到所有Follower上；由于事務間可能存在着依賴關系，ZAB協定保證Leader廣播的變更序列被順序的處理，：一個狀态被處理那麼它所依賴的狀态也已經提前被處理；ZAB協定支援的崩潰恢複可以保證在Leader程序崩潰的時候可以重新選出Leader并且保證資料的完整性；

　　在ZooKeeper中所有的事務請求都由一個主伺服器也就是Leader來處理，其他伺服器為Follower，Leader将用戶端的事務請求轉換為事務Proposal，并且将Proposal分發給叢集中其他所有的Follower，然後Leader等待Follwer回報，當有過半數（>=N/2+1）的Follower回報資訊後，Leader将再次向叢集内Follower廣播Commit資訊，Commit為将之前的Proposal送出；

協定狀态

　　ZAB協定中存在着三種狀态，每個節點都屬于以下三種中的一種：

　　1. Looking：系統剛啟動時或者Leader崩潰後正處于選舉狀态

　　2. Following：Follower節點所處的狀态，Follower與Leader處于資料同步階段；

　　3. Leading：Leader所處狀态，目前叢集中有一個Leader為主程序；

　　ZooKeeper啟動時所有節點初始狀态為Looking，這時叢集會嘗試選舉出一個Leader節點，選舉出的Leader節點切換為Leading狀态；當節點發現叢集中已經選舉出Leader則該節點會切換到Following狀态，然後和Leader節點保持同步；當Follower節點與Leader失去聯系時Follower節點則會切換到Looking狀态，開始新一輪選舉；在ZooKeeper的整個生命周期中每個節點都會在Looking、Following、Leading狀态間不斷轉換；

　　　　　　　　　　　　狀态切換圖

　　選舉出Leader節點後ZAB進入原子廣播階段，這時Leader為和自己同步的每個節點Follower建立一個操作序列，一個時期一個Follower隻能和一個Leader保持同步，Leader節點與Follower節點使用心跳檢測來感覺對方的存在；當Leader節點在逾時時間内收到來自Follower的心跳檢測那Follower節點會一直與該節點保持連接配接；若逾時時間内Leader沒有接收到來自過半Follower節點的心跳檢測或TCP連接配接斷開，那Leader會結束目前周期的上司，切換到Looking狀态，所有Follower節點也會放棄該Leader節點切換到Looking狀态，然後開始新一輪選舉；

階段

　　ZAB協定定義了選舉（election）、發現（discovery）、同步（sync）、廣播(Broadcast)四個階段；ZAB選舉（election）時當Follower存在ZXID（事務ID）時判斷所有Follower節點的事務日志，隻有lastZXID的節點才有資格成為Leader，這種情況下選舉出來的Leader總有最新的事務日志，基于這個原因是以ZooKeeper實作的時候把發現（discovery）與同步（sync）合并為恢複（recovery）階段；

　　1. Election：在Looking狀态中選舉出Leader節點，Leader的lastZXID總是最新的；

　　2. Discovery：Follower節點向準Leader推送FOllOWERINFO，該資訊中包含了上一周期的epoch，接受準Leader的NEWLEADER指令，檢查newEpoch有效性，準Leader要確定Follower的epoch與ZXID小于或等于自身的；

　　3. sync：将Follower與Leader的資料進行同步，由Leader發起同步指令，最總保持叢集資料的一緻性；

　　4. Broadcast：Leader廣播Proposal與Commit，Follower接受Proposal與Commit；

　　5. Recovery：在Election階段選舉出Leader後本階段主要工作就是進行資料的同步，使Leader具有highestZXID，叢集保持資料的一緻性；

　　選舉（Election）

　　election階段必須確定選出的Leader具有highestZXID，否則在Recovery階段沒法保證資料的一緻性，Recovery階段Leader要求Follower向自己同步資料沒有Follower要求Leader保持資料同步，所有選舉出來的Leader要具有最新的ZXID；

　　在選舉的過程中會對每個Follower節點的ZXID進行對比隻有highestZXID的Follower才可能當選Leader；

選舉流程：

　　1. 每個Follower都向其他節點發送選自身為Leader的Vote投票請求，等待回複；

　　2. Follower接受到的Vote如果比自身的大（ZXID更新）時則投票，并更新自身的Vote，否則拒絕投票；

　　3. 每個Follower中維護着一個投票記錄表，當某個節點收到過半的投票時，結束投票并把該Follower選為Leader，投票結束；

　　ZAB協定中使用ZXID作為事務編号，ZXID為64位數字，低32位為一個遞增的計數器，每一個用戶端的一個事務請求時Leader産生新的事務後該計數器都會加1，高32位為Leader周期epoch編号，當新選舉出一個Leader節點時Leader會取出本地日志中最大事務Proposal的ZXID解析出對應的epoch把該值加1作為新的epoch，将低32位從0開始生成新的ZXID；ZAB使用epoch來區分不同的Leader周期；

　　恢複（Recovery）

　　在election階段選舉出來的Leader已經具有最新的ZXID，所有本階段的主要工作是根據Leader的事務日志對Follower節點資料進行更新；

　　Leader：Leader生成新的ZXID與epoch，接收Follower發送過來的FOllOWERINFO（含有目前節點的LastZXID）然後往Follower發送NEWLEADER；Leader根據Follower發送過來的LastZXID根據資料更新政策向Follower發送更新指令；

　　同步政策：

　　1. SNAP：如果Follower資料太老，Leader将發送快照SNAP指令給Follower同步資料；

　　2. DIFF：Leader發送從Follolwer.lastZXID到Leader.lastZXID議案的DIFF指令給Follower同步資料；

　　3. TRUNC：當Follower.lastZXID比Leader.lastZXID大時，Leader發送從Leader.lastZXID到Follower.lastZXID的TRUNC指令讓Follower丢棄該段資料；

　　Follower：往Leader發送FOLLOERINFO指令，Leader拒絕就轉到Election階段；接收Leader的NEWLEADER指令，如果該指令中epoch比目前Follower的epoch小那麼Follower轉到Election階段；Follower還有主要工作是接收SNAP/DIFF/TRUNC指令同步資料與ZXID，同步成功後回複ACKNETLEADER，然後進入下一階段；Follower将所有事務都同步完成後Leader會把該節點添加到可用Follower清單中；

　　SNAP與DIFF用于保證叢集中Follower節點已經Committed的資料的一緻性，TRUNC用于抛棄已經被處理但是沒有Committed的資料；

　　廣播(Broadcast)

　　用戶端送出事務請求時Leader節點為每一個請求生成一個事務Proposal，将其發送給叢集中所有的Follower節點，收到過半Follower的回報後開始對事務進行送出，ZAB協定使用了原子廣播協定；在ZAB協定中隻需要得到過半的Follower節點回報Ack就可以對事務進行送出，這也導緻了Leader幾點崩潰後可能會出現資料不一緻的情況，ZAB使用了崩潰恢複來處理數字不一緻問題；消息廣播使用了TCP協定進行通訊所有保證了接受和發送事務的順序性。廣播消息時Leader節點為每個事務Proposal配置設定一個全局遞增的ZXID（事務ID），每個事務Proposal都按照ZXID順序來處理；

　　Leader節點為每一個Follower節點配置設定一個隊列按事務ZXID順序放入到隊列中，且根據隊列的規則FIFO來進行事務的發送。Follower節點收到事務Proposal後會将該事務以事務日志方式寫入到本地磁盤中，成功後回報Ack消息給Leader節點，Leader在接收到過半Follower節點的Ack回報後就會進行事務的送出，以此同時向所有的Follower節點廣播Commit消息，Follower節點收到Commit後開始對事務進行送出；

參考資料：

http://web.stanford.edu/class/cs347/reading/zab.pdf

http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf

文章首發位址：Solinx

http://www.solinx.co/archives/435