在 zookeeper源碼分析系列 中按照服務(wù)端客戶端啟動或交互等主線講解了源碼，但并沒有將Zab協(xié)議的完整實現(xiàn)串起來。本文主要翻譯自ZooKeeper’s atomic broadcast protocol:
Theory and practice這篇論文，可完整的展現(xiàn)Zab協(xié)議的理論和實現(xiàn)。
Zab協(xié)議是zookeeper原子廣播協(xié)議，依賴它選舉出一個Leader，同步節(jié)點，通過Leader按順序廣播修改內(nèi)容，并且從故障中快速恢復(fù)正常狀態(tài)。在介紹上述實現(xiàn)之前，我們先了解下Zab協(xié)議的背景和協(xié)議的理論知識。

Paxos協(xié)議和Zab協(xié)議的異同點

原子廣播協(xié)議的重點在于通過leader進程原子的順序廣播到其他節(jié)點進程，同時保證這個操作一致性的成功或者失敗，最終不會出現(xiàn)節(jié)點之間狀態(tài)不一致的情況。滿足四個特性：

• Validity：如果一個正常的節(jié)點廣播了一個消息，則所有正常的其他節(jié)點都會最終提交。
• Uniform Agreement：如果一個節(jié)點提交了一個消息，則所有正常的其他節(jié)點都會最終提交。
• Uniform Integrity：對任何消息，每個節(jié)點最多提交一次，并且先前必須廣播過。
• Uniform Total Order：如果節(jié)點q和p提交兩個消息m和m',則q和p對消息m和m'的提交順序應(yīng)是一樣的。
  Paxos是解決分布式共識（分布式一致性）的協(xié)議。它的目的不在于原子廣播，當然它可以對原子廣播的協(xié)議提供支持，如Zab協(xié)議。但是它不對上述原子廣播中的特性提供保證，如所有節(jié)點的一致性順序提交。它只是一個達成分布式共識的算法。
  Zab協(xié)議兩個重要的要求是提供處理大量的客戶端請求和從崩潰中快速恢復(fù)的能力。這種并發(fā)按順序的提交是通過zookeeper內(nèi)部的FIFO隊列實現(xiàn)的，同時對崩潰恢復(fù)也是有作用的。經(jīng)典的Paxos算法不能滿足處理大量的客戶端請求的要求，因為Paxos算法不要求使用FIFO通道通信，所以它允許消息的丟失和亂序提交。在主節(jié)點崩潰后，Paxos不能利用事務(wù)的順序序列來恢復(fù)集群，而Zab協(xié)議通過事務(wù)標示（zxid）來表示事務(wù)的順序性， 這樣在選舉時會優(yōu)先考慮zxid最高的節(jié)點作為Leader節(jié)點，這樣可使用Leader節(jié)點的提交記錄來同步其他節(jié)點。而在Paxos中節(jié)點同步時，Leader節(jié)點還需要提交所有先前自己為提交的事務(wù)。
  ZooKeeper還需要滿足一些性能要求：如低延遲，高吞吐，一定的容錯性等。

崩潰恢復(fù)模型

有選舉權(quán)的節(jié)點叫做peer節(jié)點，假設(shè)共有N個peer節(jié)點 (Π= {fp1, p2.. pN})，如果其中大于N/2的peer節(jié)點投票的leader節(jié)點是同一個( Q> N=2,Q ? Π)，則選主完成，這組peer節(jié)點稱為一個quorum。每個peer節(jié)點兩兩建立雙向通道，從而保證：

• Integrity：節(jié)點p從特定通道接收到的消息一定是另一端節(jié)點發(fā)送的。
• Prefix：節(jié)點p從特定通道接收到的消息順序一定是另一段節(jié)點發(fā)送的消息順序。ZooKeeper使用tcp通信的先進先出通道來實現(xiàn)。

Zab協(xié)議的滿足特性

為了實現(xiàn)一致性保證，Zab協(xié)議必須滿足一些特性。首先先聲明下一些協(xié)議定義。
ZooKeeper中需要保證事務(wù)的順序性，所以同一時刻只能有一個leader節(jié)點。我們定義leader節(jié)點的變化為ρ1ρ2 ... ρe....(ρe ? Π)，其中e代表一個整數(shù)epoch,表示在這個周期內(nèi)ρe是這組集群的leader節(jié)點。此外如果e < e',則 ρe節(jié)點不是祝節(jié)點，ρe'才是。
事務(wù)代表的是leader節(jié)點向其他節(jié)點廣播的新狀態(tài)，用<v,z>表示。其中v代表新狀態(tài)的內(nèi)容,z代表zxid。事務(wù)的提交是兩階段提交，首先leader節(jié)點發(fā)送事務(wù)的 proposal，得到超過一半的peer節(jié)點的ack之后，再發(fā)送commit給所有節(jié)點。下面這些特性Zab協(xié)議必須滿足：

• Integrity：如果節(jié)點提交<v,z>事務(wù)，則節(jié)點一定收到過事務(wù)的proposal。
• Total order：如果一些節(jié)點先提交<v,z>，后提交<v',z'>，則其他任何節(jié)點也是這個提交順序。
• Agreement：就是說一個事務(wù)要么成功，要么失敗。且成功的內(nèi)容所有節(jié)點都是一樣的。
  每個集群節(jié)點的事務(wù)一致性順序性（Primary order）需要滿足：
• Local primary order：如果 leader節(jié)點上<v,z>先于<v',z'>廣播，則<v,z>，先于<v',z'>提交。
• Global primary order：如果epoch i<i'，ρi節(jié)點廣播了<v,z>，ρi'節(jié)點廣播了<v',z'>，如果均提交的話，則<v,z>，先于<v',z'>提交。
• Primary integrity:如果epoch i<i'，ρi節(jié)點廣播了<v,z>并且有些節(jié)點提交了<v',z'>，則<v,z>的提交要先于<v',z'>的廣播。

Local primary order是由節(jié)點本地FIFO隊列實現(xiàn)的，Primary integrity保證了新的epoch的前epoch事務(wù)都已經(jīng)提交了。

Zab協(xié)議的理論實現(xiàn)

在Zab協(xié)議中，一個peer節(jié)點可能有三種狀態(tài)：

• following
• leading
• electing
  同時，一個peer節(jié)點對應(yīng)ZooKeeper中的三種執(zhí)行階段：
  Phase1:discovery
  此時peer節(jié)點處于electing狀態(tài)，正在投票選舉出一個leader節(jié)點出來，同時確定自己的節(jié)點狀態(tài)。有時集群選舉也叫做Phase0階段。
  Phase2:synchronization
  leader節(jié)點和其他節(jié)點數(shù)據(jù)同步。
  Phase3:broadcast
  Phase3階段完成了過半peer節(jié)點的數(shù)據(jù)一致性同步，此階段至多有一個leader節(jié)點用來廣播原子事務(wù)消息，類似于兩階段提交。Phase1和Phase2對于集群整體數(shù)據(jù)一致性至關(guān)重要，特別是在崩潰回復(fù)時。在這三個階段中，如果peer節(jié)點有節(jié)點間通信失敗或者超時發(fā)生，peer節(jié)點可決定是否回到Phase0階段重新選舉。
  ZooKeeper客戶端通常和一個ZooKeeper服務(wù)端節(jié)點建立會話連接，如果是寫請求，ZooKeeper節(jié)點會將請求轉(zhuǎn)發(fā)給leader節(jié)點，讀請求的話則節(jié)點自己處理?？蛻舳丝砂l(fā)送sync請求是建立連接的節(jié)點數(shù)據(jù)副本和leader節(jié)點保持一致。

Zab協(xié)議中zxid對total order 特性至關(guān)重要。一個事務(wù)<v,z>中的z(zxid)由兩部分構(gòu)成，記為<e,c>。其中 e 為發(fā)出當前事務(wù)的leader節(jié)點的epoch, c 是自增整數(shù)計數(shù)器。當一個新的選舉周期epoch產(chǎn)生時，一個新的leader節(jié)點被激活，c 從0開始遞增，而 e 在原來epoch值的基礎(chǔ)上遞增。因此，事務(wù)的順序由它們的zxid保證。對于兩個zxid <e,c>和<e',c'>,如果 <e,c> < <e',c'>，則e < e' or (if e = e' and c < c')

對于一個peer節(jié)點，有四個重要的屬性影響著它的節(jié)點狀態(tài)，在各個執(zhí)行階段均有所作用。

history:最新log文件中接受的事務(wù)proposals
acceptedEpoch:最近一次接收到的NEWEPOCH消息的epoch值（ 可看作最近一次的選舉epoch值,當選舉結(jié)束進入phase2時，leader節(jié)點acceptedEpoch=currentEpoch+1；進入phase3時，各節(jié)點acceptedEpoch=currentEpoch）
currentEpoch:最近一次接收到的NEWLEADER消息的epoch值（可看作最近一次廣播階段的epoch）
lastZxid:history中最大的zxid值

Phase0：Leader election

這階段peer節(jié)點進行初始化（會初始化上面四個屬性），節(jié)點狀態(tài)為electing。當集群獲得一個quorum節(jié)點集合的一致投票時，leader節(jié)點就被選出了。每個peer節(jié)點會將這個選票保存到內(nèi)存volatile變量中。如果leader選票節(jié)點是自己，增更新狀態(tài)為leading，否則為following。

Phase1：Discovery

這階段其他節(jié)點主動和leader節(jié)點建立連接，leader節(jié)點可以收集follower節(jié)點的最近事務(wù)信息。這個階段的目的是在一個quorum中發(fā)現(xiàn)最新接收的proposal，并且確定新一輪的epoch，從而使之前的leader無法原子廣播事務(wù)。

Phase2：Synchronization

同步階段是使集群節(jié)點的副本數(shù)據(jù)狀態(tài)統(tǒng)一更新為Phase1中l(wèi)eader節(jié)點的數(shù)據(jù)狀態(tài)。leader節(jié)點首先將自己的history發(fā)送給各個節(jié)點，當leader接收到一個quorum的ack之后，leader會發(fā)送commit消息給各個節(jié)點。從而leader節(jié)點真正建立了。

Phase3：Broadcast

如果不發(fā)生崩潰，peers節(jié)點將永遠待在這個狀態(tài)，并開啟對客戶端的服務(wù)提供。由leader節(jié)點負責客戶端的寫入請求的原子廣播。同時，leader節(jié)點也允許新的follower節(jié)點加入這個epoch中。

Zab協(xié)議算法分析

從上面三個算法中，可以得出一些不變性：

• 在phase3階段，一個從節(jié)點接收一個proposal <e,<v,z>>只有當它當前的currentEpoch=e才行。
• 在一個epoch=e的phase3階段，只有從節(jié)點的currentEpoch=e才能根據(jù)zxid的順序接收事務(wù)的proposal和commit。
• 在phase1階段，從節(jié)點不會接收比自己的acceptEpoch小的任何周期的leader的proposal。
• 在phase1階段，ACKEPOCH（F.currentEpoch,F.history,F.lastZxid）消息中F.history的事務(wù)不會改變，重排序或丟失。在phase2階段，NEWLEADER（e',L.history）消息中,L.history的事務(wù)不會改變，重排序或丟失。
• 在phase3階段，從節(jié)點提交的事務(wù)順序就是當前l(fā)eader節(jié)點廣播并提交的事務(wù)順序。
  同樣可得出一些聲明：
• 在每個周期epoch e內(nèi)，在phase3階段只能???一個進程調(diào)用ready(e)。
• Zab協(xié)議滿足我們上面提到的broadcast integrity, agreement, total order, local primary order, global primary order, and primary integrity特性。
• Liveness property:如果位于Quorum中的主從節(jié)點均是正常通信狀態(tài)，則leader節(jié)點發(fā)送的事務(wù)proposal和commit消息，位于Quorum中的從節(jié)點會及時收到并且作出對應(yīng)的狀態(tài)修改。

ZooKeeper中Zab協(xié)議的具體實現(xiàn)

首先需要明白ZooKeeper節(jié)點之間的FIFO順序通信Zab協(xié)議的保證，本文大致基于ZooKeeper 3.3.4的版本進行分析。ZooKeeper對Zab協(xié)議的實現(xiàn)大體遵循上面的算法1，2，3，此外會有一些算法優(yōu)化導(dǎo)致具體實現(xiàn)有所不同。
在ZooKeeper中，默認實現(xiàn)的選舉算法是Fast Leader Election（FLE），其中Phase0和Phase1階段是緊緊耦合在一起的。這個算法的優(yōu)化在于：它嘗試在集群選舉中從quorum節(jié)點中選出擁有最新history的節(jié)點作為leader節(jié)點，這樣在phase1階段leader節(jié)點不需要和其他從節(jié)點通信來發(fā)現(xiàn)最新的history了。在FLE的實現(xiàn)中，Phase1階段的部分功能可省略，我們將Phase1和Phase2階段合并為Recovery Phase。對比zab協(xié)議的階段劃分，zookeeper中具體階段實現(xiàn)為：

Recovery Phase

同步的目的是使得所有節(jié)點上的副本數(shù)據(jù)和主節(jié)點保持一致。所以leader節(jié)點上已提交的事務(wù)必須按同樣的順序同步到所有其他節(jié)點，未提交的proposal（包括所有節(jié)點上比leader.history.lastCommitedZxid大的proposal）必須拋棄掉使得所有節(jié)點都不會提交。SNAP和DIFF消息保證提交不丟失，TRUNC消息保證未提交proposal被丟棄掉。

這里如果zookeeper并沒有區(qū)分acceptedEpoch和currentEpoch，從節(jié)點會從history.lastCommitedZxid 中獲得current epoch，如果F嘗試連接的本地prospective leader L不是leading狀態(tài)，則L會拒絕連接，F(xiàn)會執(zhí)行22行。

Fast Leader Election

FLE算法是Recovery Phase的重要保證，它嘗試保證leader節(jié)點擁有所有歷史提交的事務(wù)，基于如果一個peer節(jié)點有最新的proposal（lastZxid）,那么它同樣擁有最新的commit這樣一個假設(shè)。
下面我們將看一下FLE的實現(xiàn)細節(jié)。選舉過程中peer節(jié)點相互交換自己的選票，期間如果接收到更新的選票則更新自己的選票，最終從一個quorum節(jié)點中選出一個leader。選票結(jié)束時，每個peer節(jié)點會根據(jù)選票結(jié)果確定自己是leader還是follower。期間出現(xiàn)異常會導(dǎo)致peer節(jié)點回到electing狀態(tài)并重新選舉，新一輪FLE的開始會導(dǎo)致選舉輪次自增（選舉輪次只是用來標記本節(jié)點收到的選票是在第幾輪，leader節(jié)點的選舉是同處在選舉狀態(tài)的節(jié)點在同一個輪次中誕生的。選舉開始時選舉輪次的值為currentEpoch）。
其中如何確定誰的選票最大呢？假設(shè)有N個peer節(jié)點，peer節(jié)點 pi 的選票為用<zi,i>表示，其中 zi 代表 pi 上最新proposal的zxid（即lastZxid），i 代表節(jié)點的的server id（在集群中是唯一的，就是zookeeper中的myid）。如果<zi,i> > <zi',i'>則滿足zi > zi' or (zi = zi' and i>i')。這樣可保證當選舉結(jié)束時，從節(jié)點自己的選票票值是小于主節(jié)點的。

在FLE選舉過程中，是沒有將變量狀態(tài)持久化到磁盤的。這意味著FLE的選舉輪次是沒有持久化的。選舉過程中使用了持久化的變量lastZxid,其中沒有持久化的重要變量有選票vote，選舉狀態(tài)state，當前選舉輪次round，identification number（id）和接收選票的隊列內(nèi)容。對于zookeeper來說，發(fā)送給其他peer節(jié)點的選舉投票消息是notification消息，包括(vote, id, state, round)這些信息。完整的算法偽代碼為：

算法中有幾個需要注意的點：

• DeduceLeader(id):從quorum中確定leader節(jié)點是誰時，需要根據(jù)leader節(jié)點信息確定出自己的state狀態(tài)。
• Put(Table(id), vote, round):收集來自其他peer節(jié)點的選票set集合，key為server id。
• Notifications Receiver:會有一個專門的線程負責接收其他節(jié)點的Notifications，并依次放到fifo隊列中并傳遞到FLE選舉過程中。并且比較選票之后，發(fā)出自己的最新選票給其他peer節(jié)點。
  

ZooKeeper實現(xiàn)Zab協(xié)議中的問題

這里主要討論兩個問題。
1.節(jié)點在Recovery Phase和FLE之間循環(huán)
ZooKeeper 3.3.3版本沒有區(qū)分acceptedEpoch和currentEpoch，會可能導(dǎo)致節(jié)點在Recovery Phase和FLE之間循環(huán)。當一個peer節(jié)點內(nèi)部選票達成一致，并稱為leader（稱為proposal leader）時，運行到Algorithm4 的第4行,將自己的lastZxid發(fā)送給其他follower節(jié)點（注意Algorithm4 的第2行此時leader將epoch遞增了，lastZxid也會更新epoch）。因為當follower節(jié)點的lastZxid.epoch大于leader節(jié)點的lastZxid.epoch時，將會重新回到electing狀態(tài)（Algorithm4 的第25行）。當proposal leader節(jié)點出現(xiàn)異常并放棄自己的領(lǐng)導(dǎo)權(quán)限并且成為之前epoch選舉出來的新leader的follower時，便會出現(xiàn)Algorithm4 的第25行的情況。此時這個原來的proposal leader節(jié)點便會在Recovery Phase和FLE之間循環(huán)。

產(chǎn)生這個問題的原因就是peer節(jié)點用lastZxid來記錄epoch值，并不能區(qū)分出來最新選舉過程中的epoch和認定的最新leader的epoch，因此定義了acceptedEpoch和currentEpoch。這樣在Algorithm4 的第25行便可通過proposal leader節(jié)點的新的epoch（在acceptedEpoch的基礎(chǔ)上加1）和follower的acceptedEpoch做比較，前者一定大于后者，從而避免循環(huán)。

2.丟掉follower節(jié)點proposal事務(wù)
Algorithm4假設(shè)第11行當follower.lastZxid>L.history.lastCommittedZxid時，leader節(jié)點就發(fā)送TRUNC消息使follower節(jié)點丟掉L.history.lastCommittedZxid之后的proposal，但有時follower節(jié)點可能存在L.history.lastCommittedZxid之前的應(yīng)丟棄的proposal。(參考issue ZOOKEEPER-1154)。下面將考慮導(dǎo)致這個問題的一種場景：

假設(shè)有三個peer節(jié)點p1,p2,p3，此時處于廣播階段，p1是leader節(jié)點且所有peer節(jié)點都處于正常工作狀態(tài)。此時它們均同步一致并提交了zxid <e = 1,c = 3>事務(wù)，p1節(jié)點接收并創(chuàng)建了新的事務(wù)zxid <e = 1,c = 4>，但還沒有將這個proposal發(fā)給p2,p3便掛掉了。p2,p3經(jīng)過重新選舉，p2成為新的leader節(jié)點，并且成功進入廣播狀態(tài)，提交事務(wù)到zxid <e = 2,c = 1>，并且p2.history.oldThreshold = <1,1>。此時p1節(jié)點重新處于正常工作狀態(tài),會成為p2的follower節(jié)點。在p1的Recovery階段，p1會給p2發(fā)送FOLLOWERINFO(p1.lastZxid = <1, 4>)消息，因為 p2.history.oldThreshold (1,1) <1, 4> < p2.history.lastCommittedZxid (<2,1>)，按照Algorithm4此時p2會給p1發(fā)送DIFF請求進行差異同步。但是 <1, 4>只存在于p1節(jié)點上，應(yīng)該被丟棄掉。

對于這種場景，p2可發(fā)送TRUNC消息使p1丟棄掉 <1, 4>，或者p2可發(fā)送SNAP消息使p1全量同步自己的數(shù)據(jù)。ZooKeeper采用的后一種方式來解決這個問題。

感謝您的閱讀，我是Monica23334 || Monica2333 。立下每周寫一篇原創(chuàng)文章flag的小姐姐，關(guān)注我并期待打臉吧～