ZAB協議選主過程詳解

01-29

說明

ZAB 協議是為分散式協調服務ZooKeeper專門設計的一種支持崩潰恢復的一致性協議。基於該協議，ZooKeeper 實現了一種主從模式的系統架構來保持集群中各個副本之間的數據一致性。

ZAB協議運行過程中，所有的客戶端更新都發往Leader，Leader寫入本地日誌後再複製到所有的Follower節點。

一旦Leader節點故障無法工作，ZAB協議能夠自動從Follower節點中重新選擇出一個合適的替代者，這個過程被稱為選主，選主也是ZAB協議中最為重要和複雜的過程。本文主要描述ZAB協議的選主過程以及在Zookeeper中的實現。

選主時機

節點啟動時

每個節點啟動的時候狀態都是LOOKING，處於觀望狀態，接下來就是要進行選主了。

Leader節點異常

Leader節點運行後會周期性地向Follower發送心跳信息（稱之為ping），如果一個Follower未收到Leader節點的心跳信息，Follower節點的狀態會從FOLLOWING轉變為LOOKING，如下：

在Follower節點的主要處理流程中：

void followLeader() throws InterruptedException {ntry {n ......n while (this.isRunning()) {n readPacket(qp);n processPacket(qp);n }n // 如果上面的while循環內出現異常n // 注意：長時間沒有收到Leader的消息也是異常n} catch (Exception e) {n // 出現異常就退出了while循環n // 也就結束了Follower的處理流程n}n

接下來進入節點運行的主循環：

public void run() {n while (running) {n switch (getPeerState()) {n case FOLLOWING:n try {n setFollower(makeFollower(logFactory));n follower.followLeader();n } catch (Exception e) {n ......n } finally {n follower.shutdown();n setFollower(null);n // 狀態更新為LOOKINGn updateServerState();n }n break;n ......nn }n}n

此後，該Follower就會再次進入選主階段。

多數Follower節點異常

Leader節點也會檢測Follower節點的狀態，如果多數Follower節點不再響應Leader節點（可能是Leader節點與Follower節點之間產生了網路分區），那麼Leader節點可能此時也不再是合法的Leader了，也必須要進行一次新的選主。

Leader節點啟動時會接收Follower的主動連接請求，對於每一個Follower的新連接，Leader會創建一個LearnerHandler對象來處理與該Follower的消息通信。

LearnerHandler創建一個獨立線程，在主循環內不停地接受Follower的消息並根據消息類型決定如何處理。除此以外，每收到Follower的消息時，便更新下一次消息的過期時間，在LeaderHandler::run()

public void run() {n ......n while (true) {n qp = new QuorumPacket();n ia.readRecord(qp, "packet");n ......n // 收到Follower的消息後n // 設置下一個消息的過期時間n tickOfNextAckDeadline = leader.self.tick.get() + leader.self.syncLimit;n ......n }n ......n}n

在Leader節點的主循環流程中，會判斷多數派節點的消息狀態，如下：

void lead() throws IOException, InterruptedException {n ......n while (true) {n ......n // 判斷每個每個Follower節點的狀態n // 是否與Leader保持同步n for (LearnerHandler f : getLearners()) {n if (f.synced()) { n syncedAckSet.addAck(f.getSid());n }n }n ......n }n if (!tickSkip && !syncedAckSet.hasAllQuorums()) {n // 如果失去了大多數Follower節點的認可，就跳出Leader主循環，進入選主流程n break;n }n ......n}nn// LearnerHandler::synced()邏輯n// 即判斷當前是否已經過了期望得到的Follower的下一個消息的期限：tickOfNextAckDeadlinenpublic boolean synced() {n return isAlive() && leader.self.tick.get() <= tickOfNextAckDeadline;n}n

選主流程

一些概念

在描述詳細的選主過程之前，有必要交代一些概念，以便對接下來的大段文字不會有丈二和尚的感覺。

election epoch

這是分散式系統中極其重要的概念，由於分散式系統的特點，無法使用精準的時鐘來維護事件的先後順序，因此，Lampert提出的Logical Clock就成為了界定事件順序的最主要方式。

分散式系統中以消息標記事件，所謂的Logical Clock就是為每個消息加上一個邏輯的時間戳。在ZAB協議中，每個消息都被賦予了一個zxid，zxid全局唯一。zxid有兩部分組成：高32位是epoch，低32位是epoch內的自增id，由0開始。每次選出新的Leader，epoch會遞增，同時zxid的低32位清0。這其實像極了咱們古代封建王朝的君主更替，每一次的江山易主，君王更替。

zxid

每個消息的編號，在分散式系統中，事件以消息來表示，事件發生的順序以消息的編號來標記。在ZAB協議中，這就是zxid。ZAB協議中，消息的編號只能由Leader節點來分配，這樣的好處是我們就可以通過zxid來準確判斷事件發生的先後，記住，是任意事件，這也是分散式系統中，由全局唯一的主節點來處理更新事件帶來的極大好處。

分散式系統運行的過程中，Leader節點必然會發生改變，一致性協議必須能夠正確處理這種情況，保證在Leader發生變化的時候，新的Leader期間，產生的zxid必須要大於老的Leader時生成的zxid。這就得通過上面說的epoch機制了，具體實現會在下面的選主過程中詳細描述。

LOOKING/FOLLOWING/LEADING

這三者描述了系統中節點的狀態：

LOOKING: 節點正處於選主狀態，不對外提供服務，直至選主結束；
FOLLOWING: 作為系統的從節點，接受主節點的更新並寫入本地日誌；
LEADING: 作為系統主節點，接受客戶端更新，寫入本地日誌並複製到從節點

選主過程

選主過程參與方有：

發起選主的節點
集群其他節點，這些節點會為發起選主的節點進行投票

節點B判斷確定A可以成為主，那麼節點B就投票給節點A，判斷的依據是：

election epoch(A) > election epoch (B)
zxid(A) > zxid(B)
sid(A) > sid(B)

選主流程：

候選節點A初始化自身的zxid和epoch：updateProposal()；
向其他所有節點發送選主通知：sendNotifications()；
等待其他節點的回復：recvqueue.poll()；
如果來自B節點的回復不為空，且B是一個有效節點，判斷B此時的運行狀態是LOOKING（也在發起選主）還是LEADING/FOLLOWING（正常請求處理過程）

情況1：投票節點是LOOKING狀態

以下以圖示法說明此時選主過程：

STEP 1：處於LOOKING狀態的A發起一次選主請求，並將請求廣播至B、C節點，而此時B、C也恰好處於LOOKING狀態：

STEP 2：B、C節點處理A的選主消息，其中，B接受A的提議，C拒絕A的提議：

說明：

伴隨著A的選主消息的一個額外收穫是B和C此時都獲得了A節點選主的結果（A投票給，記錄為<A, A>），記錄該信息，作為後續判斷大家是否達成一致的標準。

STEP 3：B將處理結果通知A、C

說明：

因為B更新了自己的投票，從投票給自己變成投票給A，因此根據協議的定義，需要將該消息擴散出去。而C由於拒絕了A的提議，因此，無需擴散消息；
B將消息擴散給A和C的同時，A和C也就了解了B的投票信息，可以更新本地的投票信息表，例如上面經過B的擴散後，A知道了B節點的投票信息，C知道了A和B節點的投票信息。

STEP 4：C同時也發起選主

STEP 5：A、B分別處理C的選主請求

說明：

這裡A和B判斷得出C是最合適的Leader，因此A和B都更新自己的候選Leader為C，同時由於C的消息，A和B都更新自身維護的投票信息，增加C的投票信息。

STEP 6：A、B將更新後的信息擴散到其他節點

說明：

因為在第五步中A和B分別將自己的候選Leader變成了C，因此需要將該信息通知到其他節點，其他節點在收到新的投票信息後會更新本地的投票信息列表，如上圖。

STEP 7: 選主結束

此時此刻，所有的節點都已經達成了一致：每個節點都同意節點C作為新的Leader。

情形2：投票節點是FOLLOWING/LEADING狀態

以下原因可能導致出現這種情況：

節點A（Follower）與Leader出現網路問題而觸發一次選主，但是其他Follower與Leader正常;
新節點加入集群也會有同樣的情況發生。

如果一個正常服務狀態(LEADING/FOLLOWING)的節點收到一個節點的選主請求，處理流程是怎麼樣的呢？

在QuorumPeer對象中存在一個WorkerReceiver線程，該線程的主要作用是接受其他節點發送過來的選主消息變更的通知。這個線程中收到其他節點發來的選主消息通知時會判斷當前節點的狀態：

public void run() {n ......n if(self.getPeerState() == QuorumPeer.ServerState.LOOKING) {n recvqueue.offer(n);n ......n // 如果節點處於非LOOKING狀態n } else {n // 節點的投票信息n Vote current = self.getCurrentVote();n if(ackstate == QuorumPeer.ServerState.LOOKING) {n QuorumVerifier qv = self.getQuorumVerifier();n // 給發起投票的節點返回當前節點的投票信息n ToSend notmsg = new ToSend(ToSend.mType.notification, ...）n sendqueue.offer(notmsg);n }n }n}n

此時處理過程是怎樣的：

如果Logical Clock相同，將數據保存在recvset，如果Sender宣稱自己是Leader，那麼判斷是不是半數以上的伺服器都選舉它，如果是設置角色並退出選舉。
否則，這是一條與當前LogicalClock不符合的消息，說明在另一個選舉過程中已經有了選舉結果(另一個選舉過程指的是什麼)，於是將該選舉結果加入到OutOfElection集合中，根據OutOfElection來判斷是否可以結束選舉，如果可以也是保存LogicalClock，更新角色，退出選舉。出現這種情況可能是由於原集群中有一個新的伺服器上線/重新啟動，但是原來的已有集群的機器已經選主成功，因此，別無他法，只有加入原來的集群成為Follower。但這裡的Logical Clock不符合，可能大也可能小，怎麼理解？

說明：

logical clock相同可能是因為出現這種情況：A、B同時發起選主，此時他們的election epoch可能相同，如果B率先完成了選主過程（B可能變成了Leader，也有可能B選擇了其他節點為Leader），但是A還在選主過程中，此時如果B收到了A的選主消息，那麼B就將自己的選主結果和自己的狀態（LEADING/FOLLOWING）連同自己的election epoch回復給A，對於A來說，它收到了一個來自選主完成的節點B的election epoch相同的回復，便有了上面的第一種情況；

上圖的10表示選主的Logical Clock

logical clock不相同可能是因為新增了一個節點或者某個節點出現了網路隔離導致其觸發一次新的選主，然後系統中其他節點狀態依然正常，此時發起選主的節點由於要遞增其logical clock，必然會導致其logical clock要大於其他正常節點的logical clock（當然也可能小於，考慮一個新上線節點觸發選主，其logical clock從1開始計算）。因此就出現了上面的第二種情況，如下圖：

如果對方節點處於FOLLOWING/LEADING狀態，除檢查是否過半外，同時還要檢查leader是否給自己發送過投票信息，從投票信息中確認該leader是不是LEADING狀態。這個解釋如下：

因為目前leader和follower都是各自檢測是否進入leader選舉過程。leader檢測到未過半的server的ping回復，則leader會進入LOOKING狀態，但是follower有自己的檢測，感知這一事件，還需要一定時間，在此期間，如果其他server加入到該集群，可能會收到其他follower的過半的對之前leader的投票，但是此時該leader已經不處於LEADING狀態了，所以需要這麼一個檢查來排除這種情況。

Leader/Follower信息同步

選出了Leader還不算完，根據ZAB協議定義，在真正對外提供服務之前還需要一個信息同步的過程。具體來說，Leader和Follower之間需要同步以下信息：

下一次zxid：這是因為選出新的Leader後，epoch勢必發生改變，因此，需要經過多方協商後選擇出當前最大的epoch，然後再拼湊出下一輪提供服務的zxid
日誌內容：ZAB使用日誌同步來維護多個節點的一致性狀態，同步過程是由Leader發往Follower，因此可能會存在大家步調不一致的情況，表現出的現象就是節點日誌內容不同，可能某些節點領先，而某些節點落後。

Epoch協商

選主過程結束後，接下來就是多數派節點協商出一個最大的epoch（但如果是採用FastLeaderElection演算法的話，選出來的Leader其實就擁有了最大的epoch）。

這個過程涉及到Leader和Follower節點的通信，具體流程：

Leader節點啟動時調用getEpochToPropose()，並將自己的zxid解析出來的epoch作為參數；
Follower節點啟動時也會連接Leader，並從自己的最後一條zxid解析出epoch發送給Leader，leader中處理該Follower消息的線程同樣調用getEpochToPropose()，只是此時傳入的參數是該Follower的epoch；
getEpochToPropose()中會判斷參數中傳入的epoch和當前最大的epoch，選擇兩者中最大的，並且判斷該選擇是否已經獲得了多數派的認可，如果沒有得到，則阻塞調用getEpochToPropose()的線程；如果獲得認可，那就喚醒那些等待epoch協商結果的線程，於是，Follower就得到了多數派認可的全新的epoch，大家就從這個epoch開始生成新的zxid；
Leader的發起epoch更新過程在函數Leader::lead()中，Follower的發起epoch更新過程在函數Follower::followLeader()中，Leader處理Follower的epoch更新請求在函數LearnerHandler::run()中。

日誌同步

選主結束後，接下來需要在Leader和Follower之間同步日誌，根據ZAB協議定義，這個同步過程可能是Leader流向Follower。

對比的原理是將Follower的最新的日誌zxid和Leader的已經提交的日誌zxid對比，會有以下幾種可能：

如果Leader的最新提交的日誌zxid比Follower的最新日誌的zxid大，那就將多的日誌發送給Follower，讓他補齊；
如果Leader的最新提交的日誌zxid比Follower的最新日誌的zxid小，那就發送命令給Follower，將其多餘的日誌截斷；
如果兩者恰好一樣，那什麼都不用做。

即使是一個日誌同步過程也要經歷以下幾個同步過程：

Leader發送同步日誌給Follower，該過程傳輸的主要是日誌數據流或者Leader給Follower的各種命令；
Leader發送NEWLEADER命令給Follower，該命令的作用應該是告訴Follower日誌同步已經完成，Follower對該NEWLEADER作出ACK，而Leader會等待該ACK消息；
Leader最後發送UPTODATE命令至Follower，這個命令的作用應該是告訴Follower，我已經收到了你的ACK，而Follower這邊收到該消息的時候說明一切與Leader同步的初始化工作都已經完成，可以進入正常的處理流程了，而Leader這邊發完該命令後也可以進入正常的請求處理流程了。

總結

使用日誌實現分散式系統一致性的方案中，日誌代表了系統中發生的事件，而日誌存在兩種狀態：

發起（Proposal）：日誌已經被記錄在Leader/Follower的日誌文件中，相當於節點已經記錄了該事件；
提交（Commit）：一旦事件被多數節點記錄，Leader節點便提交該日誌，即處理事件。事件被處理完成後，Leader才會給予客戶端答覆，後續，Leader節點同樣會將該Commit命令通知Follower節點。

一旦日誌被提交，那麼在客戶端看來事件已經被系統處理，那該事件產生的狀態就不能憑空消失，因此，在選主協議中最重要的兩點保證是：

已經被處理的消息不能丟
被丟棄的消息不能再次出現

已經被處理的消息不能丟

這一情況會出現在以下場景：當 leader 收到合法數量 follower 的 ACKs 後，就向各個 follower 廣播 COMMIT 命令，同時也會在本地執行 COMMIT 並向連接的客戶端返回「成功」。但是如果在各個 follower 在收到 COMMIT 命令前 leader 就掛了，導致剩下的伺服器並沒有執行都這條消息。

如圖，消息 1 的 COMMIT命令C1在 Server1（Leader）和 Server2（Follower）上執行了，但是在Server3收到消息C1之前Server1便掛了，客戶端很可能已經收到消息1已經成功執行的回復，協議需要保證重新選主後，C1消息不會丟失。

為了實現該目的，Zab選主時使用以下的策略：

選擇擁有 proposal 最大值（即 zxid 最大）的節點作為新的 Leader。

由於所有提案被COMMIT 之前必須有大多數量的 Follower ACK，即大多數伺服器已經將該 proposal寫入日誌文件。因此，新選出的Leader如果滿足是大多數節點中proposal最多的，它就必然存有所有被COMMIT消息的proposal。

接下來，新Leader與Follower 建立先進先出的隊列，先將自身有而Follower缺失的proposal發送給它，再將這些 proposal的COMMIT命令發送給 Follower，這便保證了所有的Follower都保存了所有的 proposal、所有的Follower 都處理了所有的消息。

通過以上策略，能保證已經被處理的消息不會丟

被丟棄的消息不能再次出現

這一情況會出現在以下場景：當Leader 接收到消息請求生成 proposal後就掛了，其他Follower 並沒有收到此proposal，因此新選出的Leader中必然不含這條消息。此時，假如之前掛了的Leader 重新啟動並註冊成了Follower，它要與新的Leader保持一致，就必須要刪除自己上舊的proposal。

Zab 通過巧妙的設計 zxid 來實現這一目的。一個 zxid 是64位，高 32 是紀元（epoch）編號，每經過一次 Leader選舉產生一個新的Leader，其epoch 號 +1。低 32 位是消息計數器，每接收到一條消息這個值 +1，新Leader 選舉後這個值重置為 0。

這樣設計的目的是即使舊的Leader 掛了後重啟，它也不會被選舉為Leader，因為此時它的zxid 肯定小於當前的新Leader。另外，當舊的Leader 作為Follower提供服務，新的Leader也會讓它將所有多餘未被COMMIT的proposal清除。

參考

Zookeeper源碼分析-Zookeeper Leader選舉演算法深入淺出Zookeeper之六 Leader/Follower初始化