ZAB協(xié)議巧妙的設(shè)計(jì)

一、Zookeeper 簡介

那聊 **ZAB **協(xié)議，先得看下 Zookeeper 是個(gè)什么玩意。

Zookeeper 是一個(gè)分布式數(shù)據(jù)一致性的解決方案，分布式應(yīng)用可以基于它實(shí)現(xiàn)諸如數(shù)據(jù)發(fā)布/訂閱，負(fù)載均衡，命名服務(wù)，分布式協(xié)調(diào)/通知，集群管理，Master 選舉，分布式鎖和分布式隊(duì)列等功能。 Zookeeper 致力于提供一個(gè)高性能、高可用、且具有嚴(yán)格的順序訪問控制能力的分布式協(xié)調(diào)系統(tǒng) 。

好像確實(shí)挺牛逼的，能干這么多事呢，看來搞它是必須的呀！

考慮到 Zookeeper 主要操作數(shù)據(jù)的狀態(tài)，為了保證狀態(tài)的一致性，Zookeeper提出了兩個(gè)安全屬性:

1. 全序（Total order）：如果 消息 a 在 消息 b 之前發(fā)送，則所有 Server 應(yīng)該看到相同的結(jié)果；
2. 因果順序（Causal order）：如果 消息 a 在 消息 b 之前發(fā)生（a 導(dǎo)致了b），并被一起發(fā)送，則 a 始終在 b 之前被執(zhí)行；

為了保證上述兩個(gè)安全屬性，Zookeeper 使用了 TCP 協(xié)議 和 Leader ：

1. 通過使用 TCP 協(xié)議保證了消息的全序特性（先發(fā)先到）；
2. 通過 Leader 解決了因果順序問題：先到 Leader 的先執(zhí)行，但是這樣的話 Leader 有可能出現(xiàn)出現(xiàn)網(wǎng)絡(luò)中斷、崩潰退出與重啟等異常情況，這就有必要引入 Leader 選舉算法；

而 ZAB（Zookeeper Atomic Broadcast 即 Zookeeper 原子消息廣播協(xié)議）正是作為其數(shù)據(jù)一致性的核心算法，下面介紹一下 ZAB 協(xié)議。

二、什么是 ZAB 協(xié)議

ZAB ，Zookeeper Atomic Broadcast，zk 原子消息廣播協(xié)議，是專為 ZooKeeper 設(shè)計(jì)的一 種支持崩潰恢復(fù)的原子廣播協(xié)議。在 Zookeeper 中，基于該協(xié)議，ZooKeeper 實(shí)現(xiàn)了一種主從模式的系統(tǒng)架構(gòu)來保持集群中各個(gè)副本之間的數(shù)據(jù)一致性。

Zookeeper 使用一個(gè)單一主進(jìn)程來接收并處理客戶端的所有事務(wù)請求，即寫請求。當(dāng)服 務(wù)器數(shù)據(jù)的狀態(tài)發(fā)生變更后，集群采用 ZAB 原子廣播協(xié)議，以事務(wù)提案 Proposal 的形式廣 播到所有的副本進(jìn)程上。ZAB 協(xié)議能夠保證一個(gè)全局的變更序列，即可以為每一個(gè)事務(wù)分配 一個(gè)全局的遞增編號 xid。

當(dāng) Zookeeper 客戶端連接到 Zookeeper 集群的一個(gè)節(jié)點(diǎn)后，若客戶端提交的是讀請求， 那么當(dāng)前節(jié)點(diǎn)就直接根據(jù)自己保存的數(shù)據(jù)對其進(jìn)行響應(yīng)；如果是寫請求且當(dāng)前節(jié)點(diǎn)不是 Leader，那么節(jié)點(diǎn)就會將該寫請求轉(zhuǎn)發(fā)給 Leader，Leader 會以提案的方式廣播該寫操作，只 要有超過半數(shù)節(jié)點(diǎn)同意該寫操作，則該寫操作請求就會被提交。然后 Leader 會再次廣播給 所有訂閱者，即 Learner，通知它們同步數(shù)據(jù)。

三、ZAB 協(xié)議原理

ZAB 協(xié)議要求每個(gè) Leader 都要經(jīng)歷三個(gè)階段： 發(fā)現(xiàn)，同步，廣播 。

1. 發(fā)現(xiàn) ：要求 Zookeeper 集群必須選舉出一個(gè) Leader 進(jìn)程，同時(shí) Leader 會維護(hù)一個(gè) Follower 可用客戶端列表。將來客戶端可以和這些 Follower 節(jié)點(diǎn)進(jìn)行通信。
2. 同步 ：Leader 要負(fù)責(zé)將本身的數(shù)據(jù)與 Follower 完成同步，做到多副本存儲。這樣也是體現(xiàn)了CAP中的高可用和分區(qū)容錯(cuò)。Follower 將隊(duì)列中未處理完的請求消費(fèi)完成后，寫入本地事務(wù)日志中
3. 廣播 ：Leader 可以接受客戶端新的事務(wù) Proposal 請求，將新的 Proposal 請求廣播給所有的 Follower。

四、ZAB 協(xié)議核心

ZAB 協(xié)議的核心：定義了事務(wù)請求的處理方式

1. 所有的事務(wù)請求必須由一個(gè)全局唯一的服務(wù)器來協(xié)調(diào)處理，這樣的服務(wù)器被叫做 Leader 服務(wù)器 。其他剩余的服務(wù)器則是 Follower 服務(wù)器 。
2. Leader 服務(wù)器 負(fù)責(zé)將一個(gè)客戶端事務(wù)請求，轉(zhuǎn)換成一個(gè) 事務(wù) Proposal ，并將該 Proposal 分發(fā)給集群中所有的 Follower 服務(wù)器，也就是向所有 Follower 節(jié)點(diǎn)發(fā)送數(shù)據(jù)廣播請求（或數(shù)據(jù)復(fù)制）
3. 分發(fā)之后Leader服務(wù)器需要等待所有 Follower 服務(wù)器的反饋（Ack請求），在ZAB 協(xié)議中，只要超過半數(shù)的 Follower 服務(wù)器進(jìn)行了正確的反饋后（也就是收到半數(shù)以上的Follower的Ack請求），那么 Leader 就會再次向所有的 Follower 服務(wù)器發(fā)送 Commit 消息，要求其將上一個(gè) 事務(wù) Proposal 進(jìn)行提交。

五、ZAB 協(xié)議內(nèi)容

ZAB 協(xié)議包括兩種基本的模式：崩潰恢復(fù) 和 消息廣播

1.協(xié)議過程

當(dāng)整個(gè)集群啟動過程中，或者當(dāng) Leader 服務(wù)器出現(xiàn)網(wǎng)絡(luò)中弄斷、崩潰退出或重啟等異常時(shí)，ZAB 協(xié)議就會 進(jìn)入崩潰恢復(fù)模式 ，選舉產(chǎn)生新的 Leader。

當(dāng)選舉產(chǎn)生了新的 Leader，同時(shí)集群中有過半的機(jī)器與該 Leader 服務(wù)器完成了狀態(tài)同步（即數(shù)據(jù)同步）之后，ZAB 協(xié)議就會退出崩潰恢復(fù)模式， 進(jìn)入消息廣播模式 。

這時(shí)，如果有一臺遵守 ZAB 協(xié)議的服務(wù)器加入集群，那么因?yàn)榇藭r(shí)集群中已經(jīng)存在一個(gè) Leader 服務(wù)器在廣播消息，那么該新加入的服務(wù)器自動進(jìn)入恢復(fù)模式：找到 Leader 服務(wù)器，并且完成數(shù)據(jù)同步。同步完成后，作為新的 Follower 一起參與到消息廣播流程中。

2.協(xié)議狀態(tài)切換

當(dāng) Leader 出現(xiàn)崩潰退出或者機(jī)器重啟，亦或是集群中不存在超過半數(shù)的服務(wù)器與 Leader 保存正常通信，ZAB 就會再一次進(jìn)入崩潰恢復(fù)，發(fā)起新一輪Leader 選舉并實(shí)現(xiàn)數(shù)據(jù)同步。同步完成后又會進(jìn)入消息廣播模式，接收事務(wù)請求。

3.保證消息有序

在整個(gè)消息廣播中，Leader 會將每一個(gè)事務(wù)請求轉(zhuǎn)換成對應(yīng)的 Proposal 來進(jìn)行廣播，并且在廣播 事務(wù) Proposal 之前，Leader 服務(wù)器會首先為這個(gè)事務(wù) Proposal 分配一個(gè)全局單遞增的唯一ID，稱之為事務(wù)ID（即 zxid），由于 Zab 協(xié)議需要保證每一個(gè)消息的嚴(yán)格的順序關(guān)系，因此必須將每一個(gè) Proposal 按照其 zxid 的先后順序進(jìn)行排序和處理。

六、崩潰恢復(fù)

一旦 Leader 服務(wù)器出現(xiàn)崩潰或者由于網(wǎng)絡(luò)原因?qū)е?Leader 服務(wù)器失去了與過半 Follower 的聯(lián)系，那么就會進(jìn)入崩潰恢復(fù)模式。

前面我們說過，崩潰恢復(fù)具有兩個(gè)階段： Leader 選舉 與 初始化同步 。當(dāng)完成 Leader 選 舉后，此時(shí)的 Leader 還是一個(gè)準(zhǔn) Leader，其要經(jīng)過初始化同步后才能變?yōu)檎嬲?Leader。

初始化同步

具體過程如下：

1. 為了保證 Leader 向 Learner 發(fā)送提案的有序，Leader 會為每一個(gè) Learner 服務(wù)器準(zhǔn)備一 個(gè)隊(duì)列；
2. Leader 將那些沒有被各個(gè) Learner 同步的事務(wù)封裝為 Proposal；
3. Leader 將這些 Proposal 逐條發(fā)給各個(gè) Learner，并在每一個(gè) Proposal 后都緊跟一個(gè) COMMIT 消息，表示該事務(wù)已經(jīng)被提交，Learner 可以直接接收并執(zhí)行 ；
4. Learner 接收來自于 Leader 的 Proposal，并將其更新到本地；
5. 當(dāng) Learner 更新成功后，會向準(zhǔn) Leader 發(fā)送 ACK 信息；
6. Leader 服務(wù)器在收到來自 Learner 的 ACK 后就會將該 Learner 加入到真正可用的 Follower 列表或 Observer 列表。沒有反饋 ACK，或反饋了但 Leader 沒有收到的 Learner，Leader 不會將其加入到相應(yīng)列表。

七、恢復(fù)模式的兩個(gè)原則

當(dāng)集群正在啟動過程中，或 Leader 與超過半數(shù)的主機(jī)斷連后，集群就進(jìn)入了恢復(fù)模式。對于要恢復(fù)的數(shù)據(jù)狀態(tài)需要遵循兩個(gè)原則。

1. 已被處理過的消息不能丟

當(dāng) Leader 收到超過半數(shù) Follower 的 ACKs 后，就向各個(gè) Follower 廣播 COMMIT 消息， 批準(zhǔn)各個(gè) Server 執(zhí)行該寫操作事務(wù)。當(dāng)各個(gè) Server 在接收到 Leader 的 COMMIT 消息后就會在本地執(zhí)行該寫操作，然后會向客戶端響應(yīng)寫操作成功。

但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就掛了，這將導(dǎo)致一種后 果： 部分 Server 已經(jīng)執(zhí)行了該事務(wù)，而部分 Server 尚未收到 COMMIT 消息 ，所以其并沒有執(zhí)行該事務(wù)。當(dāng)新的 Leader 被選舉出，集群經(jīng)過恢復(fù)模式后需要保證所有 Server 上都執(zhí)行 了那些已經(jīng)被部分 Server 執(zhí)行過的事務(wù)。

2. 被丟棄的消息不能再現(xiàn)

當(dāng)新事務(wù)在 Leader 上已經(jīng)通過，其已經(jīng)將該事務(wù)更新到了本地，但所有 Follower 還都沒有收到 COMMIT 之前，Leader 宕機(jī)了（比前面敘述的宕機(jī)更早），此時(shí)，所有 Follower 根本 就不知道該 Proposal 的存在。當(dāng)新的 Leader 選舉出來，整個(gè)集群進(jìn)入正常服務(wù)狀態(tài)后，之 前掛了的 Leader 主機(jī)重新啟動并注冊成為了 Follower。若那個(gè)別人根本不知道的 Proposal 還保留在那個(gè)主機(jī)，那么其數(shù)據(jù)就會比其它主機(jī)多出了內(nèi)容，導(dǎo)致整個(gè)系統(tǒng)狀態(tài)的不一致。所以，該 Proposa 應(yīng)該被丟棄。類似這樣應(yīng)該被丟棄的事務(wù)，是不能再次出現(xiàn)在集群中的， 應(yīng)該被清除。

八、消息廣播

當(dāng)集群中的 Learner 完成了初始化狀態(tài)同步，那么整個(gè) zk 集群就進(jìn)入到了正常工作模式 了。

如果集群中的 Learner 節(jié)點(diǎn)收到客戶端的事務(wù)請求，那么這些 Learner 會將請求轉(zhuǎn)發(fā)給 Leader 服務(wù)器。然后再執(zhí)行如下的具體過程：

1. Leader 接收到事務(wù)請求后，為事務(wù)賦予一個(gè)全局唯一的 64 位自增 id，即 zxid，通過 zxid 的大小比較即可實(shí)現(xiàn)事務(wù)的有序性管理，然后將事務(wù)封裝為一個(gè) Proposal。
2. Leader 根據(jù) Follower 列表獲取到所有 Follower，然后再將 Proposal 通過這些 Follower 的 隊(duì)列將提案發(fā)送給各個(gè) Follower。
3. 當(dāng) Follower 接收到提案后，會先將提案的 zxid 與本地記錄的事務(wù)日志中的最大的 zxid 進(jìn)行比較。若當(dāng)前提案的 zxid 大于最大 zxid，則將當(dāng)前提案記錄到本地事務(wù)日志中，并 向 Leader 返回一個(gè) ACK。
4. 當(dāng) Leader 接收到過半的 ACKs 后，Leader 就會向所有 Follower 的隊(duì)列發(fā)送 COMMIT 消息，向所有 Observer 的隊(duì)列發(fā)送 Proposal。
5. 當(dāng) Follower 收到 COMMIT 消息后，就會將日志中的事務(wù)正式更新到本地。當(dāng) Observer 收到 Proposal 后，會直接將事務(wù)更新到本地。
6. 無論是 Follower 還是 Observer，在同步完成后都需要向 Leader 發(fā)送成功 ACK。

九、實(shí)現(xiàn)原理

1.三類角色

為了避免 Zookeeper 的單點(diǎn)問題，zk 也是以集群的形式出現(xiàn)的。zk 集群中的角色主要有 以下三類：

• Leader：接收和處理客戶端的讀請求；zk 集群中事務(wù)請求的唯一處理者，并負(fù)責(zé)發(fā)起決議和投票，然后將通過的事務(wù)請求在本地進(jìn)行處理后，將處理結(jié)果同步給集群中的其它主機(jī)。
• Follower：接收和處理客戶端的讀請求; 將事務(wù)請求轉(zhuǎn)給 Leader；同步 Leader 中的數(shù)據(jù)；當(dāng) Leader 掛了，參與 Leader 的選舉（具有選舉權(quán)與被選舉權(quán)）；
• Observer：就是沒有選舉權(quán)與被選舉權(quán)，且沒有投票權(quán)的 Follower（臨時(shí)工）。若 zk 集 群中的讀壓力很大，則需要增加 Observer，最好不要增加 Follower。因?yàn)樵黾?Follower 將會增大投票與統(tǒng)計(jì)選票的壓力，降低寫操作效率，及 Leader 選舉的效率。

這三類角色在不同的情況下又有一些不同的名稱，在zookeeper源碼中的定義，可以了解下，看源碼可能會少點(diǎn)疑惑的。

• Learner = Follower + Observer
• QuorumServer = Follower + Leader

2.三個(gè)數(shù)據(jù)

在 ZAB 中有三個(gè)很重要的數(shù)據(jù)：

• zxid：是一個(gè) 64 位長度的 Long 類型。其中高 32 位表示 epoch，低 32 表示 xid。
• epoch：每個(gè) Leader 都會具有一個(gè)不同的 epoch，用于區(qū)分不同的時(shí)期（可以理解為朝代的年號）
• xid：事務(wù) id，是一個(gè)流水號，（每次朝代更替，即 leader 更換），從0開始遞增。

每當(dāng)選舉產(chǎn)生一個(gè)新的 Leader ，就會從這個(gè) Leader 服務(wù)器上取出本地事務(wù)日志中最大編號 Proposal 的 zxid，并從 zxid 中解析得到對應(yīng)的 epoch 編號，然后再對其加1，之后該編號就作為新的 epoch 值，并將低32位數(shù)字歸零，由0開始重新生成 zxid。

3.三種狀態(tài)

zk 集群中的每一臺主機(jī)，在不同的階段會處于不同的狀態(tài)。每一臺主機(jī)具有四種狀態(tài)。

• LOOKING：選舉狀態(tài)
• FOLLOWING：Follower 的正常工作狀態(tài)，從 Leader 同步數(shù)據(jù)的狀態(tài)
• LEADING：Leader 的正常工作狀態(tài)，Leader 廣播數(shù)據(jù)更新的狀態(tài)

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

• OBSERVING：Observer 的正常工作狀態(tài)，從 Leader 同步數(shù)據(jù)的狀態(tài)

4.Zab 的四個(gè)階段

• myid : 這是 zk 集群中服務(wù)器的唯一標(biāo)識，稱為 myid。例如，有三個(gè) zk 服務(wù)器，那么編號分別 是 1,2,3。
• 邏輯時(shí)鐘 : 邏輯時(shí)鐘，Logicalclock，是一個(gè)整型數(shù)，該概念在選舉時(shí)稱為 logicalclock，而在選舉結(jié) 束后稱為 epoch。即 epoch 與 logicalclock 是同一個(gè)值，在不同情況下的不同名稱。

1).選舉階段（Leader Election）

節(jié)點(diǎn)在一開始都處于選舉節(jié)點(diǎn)，只要有一個(gè)節(jié)點(diǎn)得到超過半數(shù)節(jié)點(diǎn)的票數(shù)，它就可以當(dāng)選準(zhǔn) Leader，只有到達(dá)第三個(gè)階段（也就是同步階段），這個(gè)準(zhǔn) Leader 才會成為真正的 Leader。

Zookeeper 規(guī)定所有有效的投票都必須在同一個(gè) 輪次 中，每個(gè)服務(wù)器在開始新一輪投票時(shí)，都會對自己維護(hù)的 logicalClock 進(jìn)行自增操作 。

每個(gè)服務(wù)器在廣播自己的選票前，會將自己的投票箱（recvset）清空。該投票箱記錄了所收到的選票。

例如：Server_2 投票給 Server_3，Server_3 投票給 Server_1，則Server_1的投票箱為 (2,3)、(3,1)、(1,1)。（每個(gè)服務(wù)器都會默認(rèn)給自己投票）

前一個(gè)數(shù)字表示投票者，后一個(gè)數(shù)字表示被選舉者。票箱中只會記錄每一個(gè)投票者的最后一次投票記錄，如果投票者更新自己的選票，則其他服務(wù)器收到該新選票后會在自己的票箱中更新該服務(wù)器的選票。

這一階段的目的就是為了選出一個(gè)準(zhǔn) Leader ，然后進(jìn)入下一個(gè)階段。

2). 發(fā)現(xiàn)階段（Descovery）

在這個(gè)階段，F(xiàn)ollowers 和上一輪選舉出的準(zhǔn) Leader 進(jìn)行通信，同步 Followers 最近接收的事務(wù) Proposal 。

這個(gè)階段的主要目的是發(fā)現(xiàn)當(dāng)前大多數(shù)節(jié)點(diǎn)接收的最新 Proposal，并且準(zhǔn) Leader 生成新的 epoch ，讓 Followers 接收，更新它們的 acceptedEpoch 。

3). 同步階段（Synchronization)

同步階段主要是利用 Leader 前一階段獲得的最新 Proposal 歷史，同步集群中所有的副本 。

只有當(dāng) quorum（超過半數(shù)的節(jié)點(diǎn)） 都同步完成，準(zhǔn) Leader 才會成為真正的 Leader。Follower 只會接收 zxid 比自己 lastZxid 大的 Proposal。

4). 廣播階段（Broadcast）

到了這個(gè)階段，Zookeeper 集群才能正式對外提供事務(wù)服務(wù)，并且 Leader 可以進(jìn)行消息廣播。同時(shí)，如果有新的節(jié)點(diǎn)加入，還需要對新節(jié)點(diǎn)進(jìn)行同步。需要注意的是，ZAB 提交事務(wù)并不像 2PC 一樣需要全部 Follower 都 Ack，只需要得到 quorum（超過半數(shù)的節(jié)點(diǎn)）的Ack 就可以。

十、ZAB 與 Paxos

上面已經(jīng)針對 ZAB 協(xié)議涉及流程作了詳細(xì)的描述，那么它和 Paxos 是什么關(guān)系呢？

ZAB 的作者認(rèn)為ZAB 與 Paxos 并不相同，之所以沒有采用 Paxos 是因?yàn)镻axos 保證不了全序順序：

Because multiple leaders can propose a value for a given instance two problems arise. First, proposals can conflict. Paxos uses ballots to detect and resolve conflicting proposals. Second, it is not enough to know that a given instance number has been committed, processes must also be able to fi gure out which value has been committed.

Paxos 算法的確是不關(guān)心請求之間的邏輯順序，而只考慮數(shù)據(jù)之間的全序，但很少有人直接使用 Paxos 算法，都會經(jīng)過一定的簡化、優(yōu)化。

Google的粗粒度鎖服務(wù)Chubby的設(shè)計(jì)開發(fā)者Burrows曾經(jīng)說過：“ 所有一致性協(xié)議本質(zhì)上要么是 Paxos 要么是其變體 ”。這句話還是有一定道理的，ZAB本質(zhì)上就是 Paxos 的一種簡化形式。

總結(jié):

本文主要講解了ZAB 上述一系列巧妙的設(shè)計(jì)，比如：為了加快收斂速度避免活鎖引發(fā)的競爭引入了 Leader 角色，在正常情況下最多只有一個(gè)參與者扮演 Leader角色，其他參與者扮演 Acceptor；在這種優(yōu)化算法中，只有 Leader 可以提出議案，從而避免了競爭使得算法能夠快速地收斂而趨于一致；而為了保證 Leader 的健壯性，又引入了 Leader 選舉，再考慮到同步的階段，提出了消息廣播和崩潰初始化同步以及恢復(fù)模式的兩個(gè)原則。