ZAB协议选主过程详解
說明
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 { try {......while (this.isRunning()) {readPacket(qp);processPacket(qp);}// 如果上面的while循環內出現異常// 注意：長時間沒有收到Leader的消息也是異常 } catch (Exception e) {// 出現異常就退出了while循環// 也就結束了Follower的處理流程 }接下來進入節點運行的主循環：
public void run() {while (running) {switch (getPeerState()) {case FOLLOWING:try {setFollower(makeFollower(logFactory));follower.followLeader();} catch (Exception e) {......} finally {follower.shutdown();setFollower(null);// 狀態更新為LOOKINGupdateServerState();}break;......} }此后，該Follower就會再次進入選主階段。
多數Follower節點異常
Leader節點也會檢測Follower節點的狀態，如果多數Follower節點不再響應Leader節點（可能是Leader節點與Follower節點之間產生了網絡分區），那么Leader節點可能此時也不再是合法的Leader了，也必須要進行一次新的選主。
Leader節點啟動時會接收Follower的主動連接請求，對于每一個Follower的新連接，Leader會創建一個LearnerHandler對象來處理與該Follower的消息通信。
LearnerHandler創建一個獨立線程，在主循環內不停地接受Follower的消息并根據消息類型決定如何處理。除此以外，每收到Follower的消息時，便更新下一次消息的過期時間，在LeaderHandler::run()
public void run() {......while (true) {qp = new QuorumPacket();ia.readRecord(qp, "packet");......// 收到Follower的消息后// 設置下一個消息的過期時間tickOfNextAckDeadline = leader.self.tick.get() + leader.self.syncLimit;......}...... }在Leader節點的主循環流程中，會判斷多數派節點的消息狀態，如下：
void lead() throws IOException, InterruptedException {......while (true) {......// 判斷每個每個Follower節點的狀態// 是否與Leader保持同步for (LearnerHandler f : getLearners()) {if (f.synced()) { syncedAckSet.addAck(f.getSid());}}......}if (!tickSkip && !syncedAckSet.hasAllQuorums()) {// 如果失去了大多數Follower節點的認可，就跳出Leader主循環，進入選主流程break;}...... }// LearnerHandler::synced()邏輯 // 即判斷當前是否已經過了期望得到的Follower的下一個消息的期限：tickOfNextAckDeadline public boolean synced() {return isAlive() && leader.self.tick.get() <= tickOfNextAckDeadline; }選主流程
在描述詳細的選主過程之前，有必要交代一些概念，以便對接下來的大段文字不會有丈二和尚的感覺。
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)
選主流程：
情況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；C由于拒絕了A的提議，因此，無需擴散消息。
說明：
- 因為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() {......if(self.getPeerState() == QuorumPeer.ServerState.LOOKING) {recvqueue.offer(n);......// 如果節點處于非LOOKING狀態} else {// 節點的投票信息Vote current = self.getCurrentVote();if(ackstate == QuorumPeer.ServerState.LOOKING) {QuorumVerifier qv = self.getQuorumVerifier();// 給發起投票的節點返回當前節點的投票信息ToSend notmsg = new ToSend(ToSend.mType.notification, ...）sendqueue.offer(notmsg);}} }此時處理過程是怎樣的：
- 如果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和Follower之間同步日志，根據ZAB協議定義，這個同步過程可能是Leader流向Follower。
對比的原理是將Follower的最新的日志zxid和Leader的已經提交的日志zxid對比，會有以下幾種可能：
- 如果Leader的最新提交的日志zxid比Follower的最新日志的zxid大，那就將多的日志發送給Follower，讓他補齊；
- 如果Leader的最新提交的日志zxid比Follower的最新日志的zxid小，那就發送命令給Follower，將其多余的日志截斷；
- 如果兩者恰好一樣，那什么都不用做。
即使是一個日志同步過程也要經歷以下幾個同步過程：
總結
使用日志實現分布式系統一致性的方案中，日志代表了系統中發生的事件，而日志存在兩種狀態：
- 發起（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初始化
總結
以上是生活随笔為你收集整理的ZAB协议选主过程详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ZAB算法详解
- 下一篇： Redis Cluster Gossip