ZAB協(xié)議基本原理

概述

ZAB （Zookeeper Atomic Broadcast）協(xié)議是為分布式協(xié)調(diào)服務(wù) ZooKeeper 專門設(shè)計(jì)的一種支持崩潰恢復(fù)的原子廣播協(xié)議。在 ZooKeeper 中，主要依賴 ZAB 協(xié)議來實(shí)現(xiàn)分布式數(shù)據(jù)一致性，基于該協(xié)議，ZooKeeper 實(shí)現(xiàn)了一種主備模式的系統(tǒng)架構(gòu)來保持集群中各個(gè)副本之間的數(shù)據(jù)一致性。

ZAB 是 Zookeeper 原子廣播協(xié)議的簡(jiǎn)稱，下面我們來討論協(xié)議的內(nèi)容，注意：理論與實(shí)現(xiàn)是有區(qū)別的，如果你對(duì)協(xié)議的理論不感興趣，可以直接跳過看實(shí)現(xiàn)。

問題的提出

Zookeeper 客戶端會(huì)隨機(jī)連接到 Zookeeper 集群的一個(gè)節(jié)點(diǎn)，如果是讀請(qǐng)求，就直接從當(dāng)前節(jié)點(diǎn)中讀取數(shù)據(jù)；如果是寫請(qǐng)求，那么節(jié)點(diǎn)就會(huì)向 leader 提交事務(wù)，leader 會(huì)廣播事務(wù)，只要有超過半數(shù)節(jié)點(diǎn)寫入成功，該寫請(qǐng)求就會(huì)被提交（類 2PC 協(xié)議）。

那么問題來了：

  • 主從架構(gòu)下，leader 崩潰，數(shù)據(jù)一致性怎么保證？
  • 選舉 leader 的時(shí)候，整個(gè)集群無法處理寫請(qǐng)求的，如何快速進(jìn)行 leader 選舉？
    帶著這兩個(gè)問題，我們來看看 ZAB 協(xié)議是如何解決的。

通俗版

Zab 協(xié)議分為兩大塊：

  • 廣播（boardcast）：Zab 協(xié)議中，所有的寫請(qǐng)求都由 leader 來處理。正常工作狀態(tài)下，leader 接收請(qǐng)求并通過廣播協(xié)議來處理。
  • 恢復(fù)（recovery）：當(dāng)服務(wù)初次啟動(dòng)，或者 leader 節(jié)點(diǎn)掛了，系統(tǒng)就會(huì)進(jìn)入恢復(fù)模式，直到選出了有合法數(shù)量 follower 的新 leader，然后新 leader 負(fù)責(zé)將整個(gè)系統(tǒng)同步到最新狀態(tài)。

廣播（boardcast）

廣播的過程實(shí)際上是一個(gè)簡(jiǎn)化的二階段提交過程：

  • Leader 接收到消息請(qǐng)求后，將消息賦予一個(gè)全局唯一的 64 位自增 id，叫做：zxid，通過 zxid 的大小比較即可實(shí)現(xiàn)因果有序這一特性。
  • Leader 為每個(gè)Follower準(zhǔn)備一個(gè)FIFO隊(duì)列（通過 TCP 協(xié)議來實(shí)現(xiàn)，以此實(shí)現(xiàn)了全局有序這一特性）將帶有 zxid 的消息作為一個(gè)提案（proposal）分發(fā)給所有 follower。
  • 當(dāng) follower 接收到 proposal，先將 proposal 寫到硬盤，寫硬盤成功后再向 leader 回一個(gè) ACK。
  • 當(dāng) leader 接收到合法數(shù)量（半數(shù)以上）的 ACKs 后，leader 就向這些follower 發(fā)送 COMMIT 命令，同事會(huì)在本地執(zhí)行該消息。
  • 當(dāng) follower 收到消息的 COMMIT 命令時(shí)，就會(huì)執(zhí)行該消息

相比于完整的二階段提交，Zab 協(xié)議最大的區(qū)別就是不能終止事務(wù)，follower 要么回 ACK 給 leader，要么拋棄 leader，在某一時(shí)刻，leader 的狀態(tài)與 follower 的狀態(tài)很可能不一致，因此它不能處理 leader 掛掉的情況，所以 Zab 協(xié)議引入了恢復(fù)模式來處理這一問題。
從另一角度看，正因?yàn)?Zab 的廣播過程不需要終止事務(wù)，也就是說不需要所有 follower 都返回 ACK 才能進(jìn)行 COMMIT，而是只需要合法數(shù)量（2f+1 臺(tái)服務(wù)器中的 f+1 臺(tái)） 的follower，也提升了整體的性能。

恢復(fù)（recovery）

由于之前講的 Zab 協(xié)議的廣播部分不能處理 leader 掛掉的情況，Zab 協(xié)議引入了恢復(fù)模式來處理這一問題。為了使 leader 掛了后系統(tǒng)能正常工作，需要解決以下兩個(gè)問題：

  • 已經(jīng)被處理的消息不能丟
  • 被丟棄的消息不能再次出現(xiàn)

已經(jīng)被處理的消息不能丟

這一情況會(huì)出現(xiàn)在以下場(chǎng)景：當(dāng) leader 收到合法數(shù)量 follower 的 ACKs 后，就向各個(gè) follower 廣播 COMMIT 命令，同時(shí)也會(huì)在本地執(zhí)行 COMMIT 并向連接的客戶端返回「成功」。但是如果在各個(gè) follower 在收到 COMMIT 命令前 leader 就掛了，導(dǎo)致剩下的服務(wù)器并沒有執(zhí)行都這條消息。

如圖下圖，消息 1 的 COMMIT 命令 Server1（leader）和 Server2（follower） 上執(zhí)行了，但是 Server3 還沒有收到消息 1 的 COMMIT 命令，此時(shí) leader Server1 已經(jīng)掛了，客戶端很可能已經(jīng)收到消息 1 已經(jīng)成功執(zhí)行的回復(fù)，經(jīng)過恢復(fù)模式后需要保證所有機(jī)器都執(zhí)行了消息 1。

為了實(shí)現(xiàn)已經(jīng)被處理的消息不能丟這個(gè)目的，Zab 的恢復(fù)模式使用了以下的策略：

  • 選舉擁有 proposal 最大值（即 zxid 最大） 的節(jié)點(diǎn)作為新的 leader：由于所有提案被 COMMIT 之前必須有合法數(shù)量的 follower ACK，即必須有合法數(shù)量的服務(wù)器的事務(wù)日志上有該提案的 proposal，因此，只要有合法數(shù)量的節(jié)點(diǎn)正常工作，就必然有一個(gè)節(jié)點(diǎn)保存了所有被 COMMIT 消息的 proposal 狀態(tài)。
  • 新的 leader 將自己事務(wù)日志中 proposal 但未 COMMIT 的消息處理。
  • 新的 leader 與 follower 建立先進(jìn)先出的隊(duì)列， 先將自身有而 follower 沒有的 proposal 發(fā)送給 follower，再將這些 proposal 的 COMMIT 命令發(fā)送給 follower，以保證所有的 follower 都保存了所有的 proposal、所有的 follower 都處理了所有的消息。
    通過以上策略，能保證已經(jīng)被處理的消息不會(huì)丟

被丟棄的消息不能再次出現(xiàn)

這一情況會(huì)出現(xiàn)在以下場(chǎng)景：當(dāng) leader 接收到消息請(qǐng)求生成 proposal 后就掛了，其他 follower 并沒有收到此 proposal，因此經(jīng)過恢復(fù)模式重新選了 leader 后，這條消息是被跳過的。 此時(shí)，之前掛了的 leader 重新啟動(dòng)并注冊(cè)成了 follower，他保留了被跳過消息的 proposal 狀態(tài)，與整個(gè)系統(tǒng)的狀態(tài)是不一致的，需要將其刪除。

如下圖 ，在 Server1 掛了后系統(tǒng)進(jìn)入新的正常工作狀態(tài)后，消息 3被跳過，此時(shí) Server1 中的 P3 需要被清除。


Zab 通過巧妙的設(shè)計(jì) zxid 來實(shí)現(xiàn)這一目的。一個(gè) zxid 是64位，高 32 是紀(jì)元（epoch）編號(hào)，每經(jīng)過一次 leader 選舉產(chǎn)生一個(gè)新的 leader，新 leader 會(huì)將 epoch 號(hào) +1。低 32 位是消息計(jì)數(shù)器，每接收到一條消息這個(gè)值 +1，新 leader 選舉后這個(gè)值重置為 0。這樣設(shè)計(jì)的好處是舊的 leader 掛了后重啟，它不會(huì)被選舉為 leader，因?yàn)榇藭r(shí)它的 zxid 肯定小于當(dāng)前的新 leader。當(dāng)舊的 leader 作為 follower 接入新的 leader 后，新的 leader 會(huì)讓它將所有的擁有舊的 epoch 號(hào)的未被 COMMIT 的 proposal 清除。

理論：ZAB 的四個(gè)階段

術(shù)語解釋

  • quorum：集群中超過半數(shù)的節(jié)點(diǎn)集合

ZAB 中的節(jié)點(diǎn)有三種狀態(tài)

  • following：當(dāng)前節(jié)點(diǎn)是跟隨者，服從 leader 節(jié)點(diǎn)的命令
  • leading：當(dāng)前節(jié)點(diǎn)是 leader，負(fù)責(zé)協(xié)調(diào)事務(wù)
  • election/looking：節(jié)點(diǎn)處于選舉狀態(tài)

代碼實(shí)現(xiàn)中多了一種：observing 狀態(tài)，這是 Zookeeper 引入 Observer 之后加入的，Observer 不參與選舉，是只讀節(jié)點(diǎn)，跟 ZAB 協(xié)議沒有關(guān)系

節(jié)點(diǎn)的持久狀態(tài)

  • history：當(dāng)前節(jié)點(diǎn)接收到事務(wù)提議的 log
  • acceptedEpoch：follower 已經(jīng)接受的 leader 更改年號(hào)的 NEWEPOCH 提議
  • currentEpoch：當(dāng)前所處的年代
  • lastZxid：history 中最近接收到的提議的 zxid （最大的）

ZAB 協(xié)議的事務(wù)編號(hào) Zxid 設(shè)計(jì)

  • Zxid 是一個(gè) 64 位的數(shù)字，其中低 32 位是一個(gè)簡(jiǎn)單的單調(diào)遞增的計(jì)數(shù)器，針對(duì)客戶端每一個(gè)事務(wù)請(qǐng)求，計(jì)數(shù)器加 1；而高 32 位則代表 Leader 周期 epoch 的編號(hào)，每個(gè)當(dāng)選產(chǎn)生一個(gè)新的 Leader 服務(wù)器，就會(huì)從這個(gè) Leader 服務(wù)器上取出其本地日志中最大事務(wù)的ZXID，并從中讀取 epoch 值，然后加 1，以此作為新的 epoch，并將低 32 位從 0 開始計(jì)數(shù)。

  • epoch：可以理解為當(dāng)前集群所處的年代或者周期，每個(gè) leader 就像皇帝，都有自己的年號(hào)，所以每次改朝換代，leader 變更之后，都會(huì)在前一個(gè)年代的基礎(chǔ)上加 1。這樣就算舊的 leader 崩潰恢復(fù)之后，也沒有人聽他的了，因?yàn)?follower 只聽從當(dāng)前年代的 leader 的命令。*

Phase 0: Leader election（選舉階段）

節(jié)點(diǎn)在一開始都處于選舉階段，只要有一個(gè)節(jié)點(diǎn)得到超半數(shù)節(jié)點(diǎn)的票數(shù)，它就可以當(dāng)選準(zhǔn) leader。只有到達(dá) Phase 3 準(zhǔn) leader 才會(huì)成為真正的 leader。這一階段的目的是就是為了選出一個(gè)準(zhǔn) leader，然后進(jìn)入下一個(gè)階段。

協(xié)議并沒有規(guī)定詳細(xì)的選舉算法，后面我們會(huì)提到實(shí)現(xiàn)中使用的 Fast Leader Election。

Phase 1: Discovery（發(fā)現(xiàn)階段）

在這個(gè)階段，followers 跟準(zhǔn) leader 進(jìn)行通信，同步 followers 最近接收的事務(wù)提議。這個(gè)一階段的主要目的是發(fā)現(xiàn)當(dāng)前大多數(shù)節(jié)點(diǎn)接收的最新提議，并且準(zhǔn) leader 生成新的 epoch，讓 followers 接受，更新它們的 acceptedEpoch。

一個(gè) follower 只會(huì)連接一個(gè) leader，如果有一個(gè)節(jié)點(diǎn) f 認(rèn)為另一個(gè) follower p 是 leader，f 在嘗試連接 p 時(shí)會(huì)被拒絕，f 被拒絕之后，就會(huì)進(jìn)入 Phase 0。

Phase 2: Synchronization（同步階段）

同步階段主要是利用 leader 前一階段獲得的最新提議歷史，同步集群中所有的副本。只有當(dāng) quorum 都同步完成，準(zhǔn) leader 才會(huì)成為真正的 leader。follower 只會(huì)接收 zxid 比自己的 lastZxid 大的提議。

Phase 3: Broadcast（廣播階段）

到了這個(gè)階段，Zookeeper 集群才能正式對(duì)外提供事務(wù)服務(wù)，并且 leader 可以進(jìn)行消息廣播。同時(shí)如果有新的節(jié)點(diǎn)加入，還需要對(duì)新節(jié)點(diǎn)進(jìn)行同步。

值得注意的是，ZAB 提交事務(wù)并不像 2PC 一樣需要全部 follower 都 ACK，只需要得到 quorum （超過半數(shù)的節(jié)點(diǎn)）的 ACK 就可以了。

協(xié)議實(shí)現(xiàn)

協(xié)議的 Java 版本實(shí)現(xiàn)跟上面的定義有些不同，選舉階段使用的是 Fast Leader Election（FLE），它包含了 Phase 1 的發(fā)現(xiàn)職責(zé)。因?yàn)?FLE 會(huì)選舉擁有最新提議歷史的節(jié)點(diǎn)作為 leader，這樣就省去了發(fā)現(xiàn)最新提議的步驟。實(shí)際的實(shí)現(xiàn)將 Phase 1 和 Phase 2 合并為 Recovery Phase（恢復(fù)階段）。所以，ZAB 的實(shí)現(xiàn)只有三個(gè)階段：

  • Fast Leader Election
  • Recovery Phase
  • Broadcast Phase

Fast Leader Election

前面提到 FLE 會(huì)選舉擁有最新提議歷史（lastZixd最大）的節(jié)點(diǎn)作為 leader，這樣就省去了發(fā)現(xiàn)最新提議的步驟。這是基于擁有最新提議的節(jié)點(diǎn)也有最新提交記錄的前提。

  • 成為 leader 的條件
  1. epoch最大的
  2. epoch相等，選 zxid 最大的
  3. epoch和zxid都相等，選擇server id最大的（就是我們配置zoo.cfg中的myid）

節(jié)點(diǎn)在選舉開始都默認(rèn)投票給自己，當(dāng)接收其他節(jié)點(diǎn)的選票時(shí)，會(huì)根據(jù)上面的條件更改自己的選票并重新發(fā)送選票給其他節(jié)點(diǎn)，當(dāng)有一個(gè)節(jié)點(diǎn)的得票超過半數(shù)，該節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 leading，其他節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 following。

選舉過程

Recovery Phase （恢復(fù)階段）

這一階段 follower 發(fā)送它們的 lastZixd 給 leader，leader 根據(jù) lastZixd 決定如何同步數(shù)據(jù)。這里的實(shí)現(xiàn)跟前面 Phase 2 有所不同：Follower 收到 TRUNC 指令會(huì)中止 L.lastCommittedZxid 之后的提議，收到 DIFF 指令會(huì)接收新的提議。

history.lastCommittedZxid：最近被提交的提議的 zxid
history:oldThreshold：被認(rèn)為已經(jīng)太舊的已提交提議的 zxid

總結(jié)

經(jīng)過上面的分析，我們可以來回答開始提到的兩個(gè)問題

  • 主從架構(gòu)下，leader 崩潰，數(shù)據(jù)一致性怎么保證？leader 崩潰之后，集群會(huì)選出新的 leader，然后就會(huì)進(jìn)入恢復(fù)階段，新的 leader 具有所有已經(jīng)提交的提議，因此它會(huì)保證讓 followers 同步已提交的提議，丟棄未提交的提議（以 leader 的記錄為準(zhǔn)），這就保證了整個(gè)集群的數(shù)據(jù)一致性。
  • 選舉 leader 的時(shí)候，整個(gè)集群無法處理寫請(qǐng)求的，如何快速進(jìn)行 leader 選舉？這是通過 Fast Leader Election 實(shí)現(xiàn)的，leader 的選舉只需要超過半數(shù)的節(jié)點(diǎn)投票即可，這樣不需要等待所有節(jié)點(diǎn)的選票，能夠盡早選出 leader。

這篇文章是根據(jù)我對(duì) ZAB 協(xié)議的理解寫成的，如果覺得有些細(xì)節(jié)沒有講清楚，可以看后面的參考資料，我主要是參考這篇論文的。

Ref:
http://blog.jobbole.com/104985/
http://www.itdecent.cn/p/fb527a64deee

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 簡(jiǎn)介 ZooKeeper是一個(gè)開放源碼的分布式應(yīng)用程序協(xié)調(diào)服務(wù)，它包含一個(gè)簡(jiǎn)單的原語集，分布式應(yīng)用程序可以基于它實(shí)...
    jiangmo閱讀 875評(píng)論 0贊 2
  • 一個(gè)真正的寫數(shù)據(jù)流程是怎么樣的？一個(gè)真正的讀數(shù)據(jù)流程是怎么樣的？一個(gè)真正的同步數(shù)據(jù)流程是怎么樣的？從哪里到哪里？什...
    時(shí)待吾閱讀 4,308評(píng)論 0贊 14
  • zookeeper是我在使用dubbo的時(shí)候認(rèn)識(shí)的一個(gè)中間件，它是一個(gè)分布式服務(wù)框架，當(dāng)時(shí)候，我只知道dubbo通...
    vivi_wong閱讀 776評(píng)論 0贊 0
  • Apache Zookeeper是由Apache Hadoop的子項(xiàng)目發(fā)展而來，于2010年11月正式成為Apac...
    olostin閱讀 6,238評(píng)論 2贊 9
  • ZooKeeper是一個(gè)分布式的，開放源碼的分布式應(yīng)用程序協(xié)調(diào)服務(wù)，它包含一個(gè)簡(jiǎn)單的原語集，分布式應(yīng)用程序可以基于...
    Prize閱讀 310評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容