• 什么是Zab協(xié)議
• Zab 協(xié)議的作用
• Zab 協(xié)議原理
• Zab 協(xié)議核心
• Zab 協(xié)議內(nèi)容
• 原子廣播
• 崩潰恢復(fù)
• 如何保證數(shù)據(jù)一致性
• Zab 協(xié)議如何數(shù)據(jù)同步
• 如何處理需要丟棄的 Proposal
• Zab 協(xié)議實現(xiàn)原理
• 選主過程

什么是Zab協(xié)議珊搀？

Zab協(xié)議 的全稱是 Zookeeper Atomic Broadcast （Zookeeper原子廣播）仔沿。
Zookeeper 是通過 Zab 協(xié)議來保證分布式事務(wù)的最終一致性监嗜。

1. Zab協(xié)議是為分布式協(xié)調(diào)服務(wù)Zookeeper專門設(shè)計的一種 支持崩潰恢復(fù) 的 原子廣播協(xié)議 ，是Zookeeper保證數(shù)據(jù)一致性的核心算法允扇。Zab借鑒了Paxos算法侵贵，但又不像Paxos那樣堪遂，是一種通用的分布式一致性算法。它是特別為Zookeeper設(shè)計的支持崩潰恢復(fù)的原子廣播協(xié)議**本缠。

2. 在Zookeeper中主要依賴Zab協(xié)議來實現(xiàn)數(shù)據(jù)一致性，基于該協(xié)議入问，zk實現(xiàn)了一種主備模型（即Leader和Follower模型）的系統(tǒng)架構(gòu)來保證集群中各個副本之間數(shù)據(jù)的一致性丹锹。
   這里的主備系統(tǒng)架構(gòu)模型稀颁，就是指只有一臺客戶端（Leader）負責(zé)處理外部的寫事務(wù)請求，然后Leader客戶端將數(shù)據(jù)同步到其他Follower節(jié)點楣黍。

Zookeeper 客戶端會隨機的鏈接到 zookeeper 集群中的一個節(jié)點匾灶，如果是讀請求，就直接從當前節(jié)點中讀取數(shù)據(jù)租漂；如果是寫請求阶女，那么節(jié)點就會向 Leader 提交事務(wù)，Leader 接收到事務(wù)提交哩治，會廣播該事務(wù)秃踩，只要超過半數(shù)節(jié)點寫入成功，該事務(wù)就會被提交业筏。

Zab 協(xié)議的特性：
1）Zab 協(xié)議需要確保那些已經(jīng)在 Leader 服務(wù)器上提交（Commit）的事務(wù)最終被所有的服務(wù)器提交憔杨。
2）Zab 協(xié)議需要確保丟棄那些只在 Leader 上被提出而沒有被提交的事務(wù)**。

image

Zab 協(xié)議實現(xiàn)的作用

1）使用一個單一的主進程（Leader）來接收并處理客戶端的事務(wù)請求（也就是寫請求）蒜胖，并采用了Zab的原子廣播協(xié)議芍秆，將服務(wù)器數(shù)據(jù)的狀態(tài)變更以 事務(wù)proposal （事務(wù)提議）的形式廣播到所有的副本（Follower）進程上去。

2）保證一個全局的變更序列被順序引用翠勉。
Zookeeper是一個樹形結(jié)構(gòu)妖啥，很多操作都要先檢查才能確定是否可以執(zhí)行，比如P1的事務(wù)t1可能是創(chuàng)建節(jié)點"/a"对碌，t2可能是創(chuàng)建節(jié)點"/a/bb"荆虱，只有先創(chuàng)建了父節(jié)點"/a"，才能創(chuàng)建子節(jié)點"/a/b"朽们。

為了保證這一點怀读，Zab要保證同一個Leader發(fā)起的事務(wù)要按順序被apply，同時還要保證只有先前Leader的事務(wù)被apply之后骑脱，新選舉出來的Leader才能再次發(fā)起事務(wù)菜枷。

3）當主進程出現(xiàn)異常的時候，整個zk集群依舊能正常工作叁丧。

Zab協(xié)議原理

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

• 發(fā)現(xiàn)：要求zookeeper集群必須選舉出一個 Leader 進程蚊锹，同時 Leader 會維護一個 Follower 可用客戶端列表。將來客戶端可以和這些 Follower節(jié)點進行通信稚瘾。

• 同步：Leader 要負責(zé)將本身的數(shù)據(jù)與 Follower 完成同步牡昆，做到多副本存儲。這樣也是提現(xiàn)了CAP中的高可用和分區(qū)容錯摊欠。Follower將隊列中未處理完的請求消費完成后丢烘，寫入本地事務(wù)日志中柱宦。

• 廣播：Leader 可以接受客戶端新的事務(wù)Proposal請求，將新的Proposal請求廣播給所有的 Follower播瞳。

Zab協(xié)議核心

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

1）所有的事務(wù)請求必須由一個全局唯一的服務(wù)器來協(xié)調(diào)處理捷沸，這樣的服務(wù)器被叫做 Leader服務(wù)器。其他剩余的服務(wù)器則是 Follower服務(wù)器狐史。

2）Leader服務(wù)器 負責(zé)將一個客戶端事務(wù)請求痒给，轉(zhuǎn)換成一個 事務(wù)Proposal，并將該 Proposal 分發(fā)給集群中所有的 Follower 服務(wù)器骏全，也就是向所有 Follower 節(jié)點發(fā)送數(shù)據(jù)廣播請求（或數(shù)據(jù)復(fù)制）

3）分發(fā)之后Leader服務(wù)器需要等待所有Follower服務(wù)器的反饋（Ack請求）苍柏，在Zab協(xié)議中，只要超過半數(shù)的Follower服務(wù)器進行了正確的反饋后（也就是收到半數(shù)以上的Follower的Ack請求）姜贡，那么 Leader 就會再次向所有的 Follower服務(wù)器發(fā)送 Commit 消息试吁，要求其將上一個 事務(wù)proposal 進行提交。

image

Zab協(xié)議內(nèi)容

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

協(xié)議過程

當整個集群啟動過程中楼咳，或者當 Leader 服務(wù)器出現(xiàn)網(wǎng)絡(luò)中弄斷熄捍、崩潰退出或重啟等異常時，Zab協(xié)議就會 進入崩潰恢復(fù)模式母怜，選舉產(chǎn)生新的Leader余耽。

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

這時轨域，如果有一臺遵守Zab協(xié)議的服務(wù)器加入集群袱耽，因為此時集群中已經(jīng)存在一個Leader服務(wù)器在廣播消息，那么該新加入的服務(wù)器自動進入恢復(fù)模式：找到Leader服務(wù)器干发，并且完成數(shù)據(jù)同步朱巨。同步完成后，作為新的Follower一起參與到消息廣播流程中枉长。

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

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

保證消息有序

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

消息廣播

1）在zookeeper集群中，數(shù)據(jù)副本的傳遞策略就是采用消息廣播模式粗仓。zookeeper中農(nóng)數(shù)據(jù)副本的同步方式與二段提交相似嫁怀，但是卻又不同。二段提交要求協(xié)調(diào)者必須等到所有的參與者全部反饋ACK確認消息后借浊，再發(fā)送commit消息塘淑。要求所有的參與者要么全部成功，要么全部失敗蚂斤。二段提交會產(chǎn)生嚴重的阻塞問題存捺。

2）Zab協(xié)議中 Leader 等待 Follower 的ACK反饋消息是指“只要半數(shù)以上的Follower成功反饋即可，不需要收到全部Follower反饋”

image

消息廣播具體步驟

1）客戶端發(fā)起一個寫操作請求曙蒸。

2）Leader 服務(wù)器將客戶端的請求轉(zhuǎn)化為事務(wù) Proposal 提案捌治，同時為每個 Proposal 分配一個全局的ID，即zxid纽窟。

3）Leader 服務(wù)器為每個 Follower 服務(wù)器分配一個單獨的隊列肖油，然后將需要廣播的 Proposal 依次放到隊列中取，并且根據(jù) FIFO 策略進行消息發(fā)送臂港。

4）Follower 接收到 Proposal 后构韵，會首先將其以事務(wù)日志的方式寫入本地磁盤中，寫入成功后向 Leader 反饋一個 Ack 響應(yīng)消息趋艘。

5）Leader 接收到超過半數(shù)以上 Follower 的 Ack 響應(yīng)消息后疲恢，即認為消息發(fā)送成功，可以發(fā)送 commit 消息瓷胧。

6）Leader 向所有 Follower 廣播 commit 消息显拳，同時自身也會完成事務(wù)提交。Follower 接收到 commit 消息后搓萧，會將上一條事務(wù)提交杂数。

zookeeper 采用 Zab 協(xié)議的核心，就是只要有一臺服務(wù)器提交了 Proposal瘸洛，就要確保所有的服務(wù)器最終都能正確提交 Proposal揍移。這也是 CAP/BASE 實現(xiàn)最終一致性的一個體現(xiàn)。

Leader 服務(wù)器與每一個 Follower 服務(wù)器之間都維護了一個單獨的 FIFO 消息隊列進行收發(fā)消息反肋，使用隊列消息可以做到異步解耦那伐。 Leader 和 Follower 之間只需要往隊列中發(fā)消息即可。如果使用同步的方式會引起阻塞，性能要下降很多罕邀。

崩潰恢復(fù)

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

在 Zab 協(xié)議中诉探，為了保證程序的正確運行日熬，整個恢復(fù)過程結(jié)束后需要選舉出一個新的 Leader 服務(wù)器。因此 Zab 協(xié)議需要一個高效且可靠的 Leader 選舉算法肾胯，從而確保能夠快速選舉出新的 Leader 竖席。

Leader 選舉算法不僅僅需要讓 Leader 自己知道自己已經(jīng)被選舉為 Leader ，同時還需要讓集群中的所有其他機器也能夠快速感知到選舉產(chǎn)生的新 Leader 服務(wù)器敬肚。

崩潰恢復(fù)主要包括兩部分：Leader選舉 和 數(shù)據(jù)恢復(fù)

Zab 協(xié)議如何保證數(shù)據(jù)一致性

假設(shè)兩種異常情況：
1怕敬、一個事務(wù)在 Leader 上提交了，并且過半的 Folower 都響應(yīng) Ack 了帘皿，但是 Leader 在 Commit 消息發(fā)出之前掛了东跪。
2、假設(shè)一個事務(wù)在 Leader 提出之后鹰溜，Leader 掛了虽填。

要確保如果發(fā)生上述兩種情況，數(shù)據(jù)還能保持一致性曹动，那么 Zab 協(xié)議選舉算法必須滿足以下要求：

Zab 協(xié)議崩潰恢復(fù)要求滿足以下兩個要求：
1）確保已經(jīng)被 Leader 提交的 Proposal 必須最終被所有的 Follower 服務(wù)器提交斋日。
2）確保丟棄已經(jīng)被 Leader 提出的但是沒有被提交的 Proposal。

根據(jù)上述要求
Zab協(xié)議需要保證選舉出來的Leader需要滿足以下條件：
1）新選舉出來的 Leader 不能包含未提交的 Proposal 墓陈。
即新選舉的 Leader 必須都是已經(jīng)提交了 Proposal 的 Follower 服務(wù)器節(jié)點恶守。
2）新選舉的 Leader 節(jié)點中含有最大的 zxid 。
這樣做的好處是可以避免 Leader 服務(wù)器檢查 Proposal 的提交和丟棄工作贡必。

Zab 如何數(shù)據(jù)同步

1）完成 Leader 選舉后（新的 Leader 具有最高的zxid）兔港，在正式開始工作之前（接收事務(wù)請求，然后提出新的 Proposal）仔拟，Leader 服務(wù)器會首先確認事務(wù)日志中的所有的 Proposal 是否已經(jīng)被集群中過半的服務(wù)器 Commit衫樊。

2）Leader 服務(wù)器需要確保所有的 Follower 服務(wù)器能夠接收到每一條事務(wù)的 Proposal ，并且能將所有已經(jīng)提交的事務(wù) Proposal 應(yīng)用到內(nèi)存數(shù)據(jù)中利花。等到 Follower 將所有尚未同步的事務(wù) Proposal 都從 Leader 服務(wù)器上同步過啦并且應(yīng)用到內(nèi)存數(shù)據(jù)中以后科侈，Leader 才會把該 Follower 加入到真正可用的 Follower 列表中。

Zab 數(shù)據(jù)同步過程中炒事，如何處理需要丟棄的 Proposal

在 Zab 的事務(wù)編號 zxid 設(shè)計中臀栈，zxid是一個64位的數(shù)字。

其中低32位可以看成一個簡單的單增計數(shù)器挠乳，針對客戶端每一個事務(wù)請求权薯，Leader 在產(chǎn)生新的 Proposal 事務(wù)時姑躲，都會對該計數(shù)器加1。而高32位則代表了 Leader 周期的 epoch 編號崭闲。

epoch 編號可以理解為當前集群所處的年代肋联，或者周期威蕉。每次Leader變更之后都會在 epoch 的基礎(chǔ)上加1刁俭，這樣舊的 Leader 崩潰恢復(fù)之后，其他Follower 也不會聽它的了韧涨，因為 Follower 只服從epoch最高的 Leader 命令牍戚。

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

Zab 協(xié)議通過 epoch 編號來區(qū)分 Leader 變化周期彬祖，能夠有效避免不同的 Leader 錯誤的使用了相同的 zxid 編號提出了不一樣的 Proposal 的異常情況茁瘦。

基于以上策略
當一個包含了上一個 Leader 周期中尚未提交過的事務(wù) Proposal 的服務(wù)器啟動時，當這臺機器加入集群中储笑，以 Follower 角色連上 Leader 服務(wù)器后甜熔，Leader 服務(wù)器會根據(jù)自己服務(wù)器上最后提交的 Proposal 來和 Follower 服務(wù)器的 Proposal 進行比對，比對的結(jié)果肯定是 Leader 要求 Follower 進行一個回退操作突倍，回退到一個確實已經(jīng)被集群中過半機器 Commit 的最新 Proposal腔稀。

實現(xiàn)原理

Zab 節(jié)點有三種狀態(tài)：

• Following：當前節(jié)點是跟隨者，服從 Leader 節(jié)點的命令羽历。
• Leading：當前節(jié)點是 Leader焊虏，負責(zé)協(xié)調(diào)事務(wù)。
• Election/Looking：節(jié)點處于選舉狀態(tài)秕磷，正在尋找 Leader炕淮。

代碼實現(xiàn)中，多了一種狀態(tài)：Observing 狀態(tài)
這是 Zookeeper 引入 Observer 之后加入的跳夭，Observer 不參與選舉涂圆，是只讀節(jié)點，跟 Zab 協(xié)議沒有關(guān)系币叹。

節(jié)點的持久狀態(tài)：

• history：當前節(jié)點接收到事務(wù) Proposal 的Log
• acceptedEpoch：Follower 已經(jīng)接受的 Leader 更改 epoch 的 newEpoch 提議润歉。
• currentEpoch：當前所處的 Leader 年代
• lastZxid：history 中最近接收到的Proposal 的 zxid（最大zxid）

Zab 的四個階段

1、選舉階段（Leader Election）
節(jié)點在一開始都處于選舉節(jié)點颈抚，只要有一個節(jié)點得到超過半數(shù)節(jié)點的票數(shù)踩衩，它就可以當選準 Leader嚼鹉，只有到達第三個階段（也就是同步階段），這個準 Leader 才會成為真正的 Leader驱富。

Zookeeper 規(guī)定所有有效的投票都必須在同一個 輪次 中锚赤，每個服務(wù)器在開始新一輪投票時，都會對自己維護的 logicalClock 進行自增操作褐鸥。

每個服務(wù)器在廣播自己的選票前线脚，會將自己的投票箱（recvset）清空。該投票箱記錄了所受到的選票叫榕。
例如：Server_2 投票給 Server_3浑侥，Server_3 投票給 Server_1，則Server_1的投票箱為(2,3)晰绎、(3,1)寓落、(1,1)。（每個服務(wù)器都會默認給自己投票）

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

這一階段的目的就是為了選出一個準 Leader ，然后進入下一個階段会宪。
協(xié)議并沒有規(guī)定詳細的選舉算法肖卧，后面會提到實現(xiàn)中使用的 Fast Leader Election。

image

2掸鹅、發(fā)現(xiàn)階段（Descovery）
在這個階段塞帐，F(xiàn)ollowers 和上一輪選舉出的準 Leader 進行通信，同步 Followers 最近接收的事務(wù) Proposal 巍沙。
一個 Follower 只會連接一個 Leader葵姥，如果一個 Follower 節(jié)點認為另一個 Follower 節(jié)點，則會在嘗試連接時被拒絕句携。被拒絕之后榔幸，該節(jié)點就會進入 Leader Election階段。

這個階段的主要目的是發(fā)現(xiàn)當前大多數(shù)節(jié)點接收的最新 Proposal矮嫉，并且準 Leader 生成新的 epoch 削咆，讓 Followers 接收，更新它們的 acceptedEpoch蠢笋。

image

3拨齐、同步階段（Synchronization）
同步階段主要是利用 Leader 前一階段獲得的最新 Proposal 歷史，同步集群中所有的副本昨寞。
只有當 quorum（超過半數(shù)的節(jié)點） 都同步完成瞻惋，準 Leader 才會成為真正的 Leader厦滤。Follower 只會接收 zxid 比自己 lastZxid 大的 Proposal。

image

4歼狼、廣播階段（Broadcast）
到了這個階段掏导，Zookeeper 集群才能正式對外提供事務(wù)服務(wù)，并且 Leader 可以進行消息廣播羽峰。同時趟咆，如果有新的節(jié)點加入，還需要對新節(jié)點進行同步限寞。
需要注意的是忍啸，Zab 提交事務(wù)并不像 2PC 一樣需要全部 Follower 都 Ack仰坦，只需要得到 quorum（超過半數(shù)的節(jié)點）的Ack 就可以履植。

image

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

協(xié)議的 Java 版本實現(xiàn)跟上面的定義略有不同，選舉階段使用的是 Fast Leader Election（FLE）悄晃，它包含了步驟1的發(fā)現(xiàn)指責(zé)玫霎。因為FLE會選舉擁有最新提議的歷史節(jié)點作為 Leader，這樣就省去了發(fā)現(xiàn)最新提議的步驟妈橄。

實際的實現(xiàn)將發(fā)現(xiàn)和同步階段合并為 Recovery Phase（恢復(fù)階段）庶近，所以，Zab 的實現(xiàn)實際上有三個階段眷蚓。

Zab協(xié)議三個階段：

1）選舉（Fast Leader Election）
2）恢復(fù)（Recovery Phase）
3）廣播（Broadcast Phase）

Fast Leader Election（快速選舉）
前面提到的 FLE 會選舉擁有最新Proposal history （lastZxid最大）的節(jié)點作為 Leader鼻种，這樣就省去了發(fā)現(xiàn)最新提議的步驟。這是基于擁有最新提議的節(jié)點也擁有最新的提交記錄

• 成為 Leader 的條件：
  1）選 epoch 最大的
  2）若 epoch 相等沙热，選 zxid 最大的
  3）若 epoch 和 zxid 相等叉钥，選擇 server_id 最大的（zoo.cfg中的myid）

節(jié)點在選舉開始時，都默認投票給自己篙贸，當接收其他節(jié)點的選票時投队，會根據(jù)上面的 Leader條件 判斷并且更改自己的選票，然后重新發(fā)送選票給其他節(jié)點爵川。當有一個節(jié)點的得票超過半數(shù)敷鸦，該節(jié)點會設(shè)置自己的狀態(tài)為 Leading ，其他節(jié)點會設(shè)置自己的狀態(tài)為 Following寝贡。

image

Recovery Phase（恢復(fù)階段）
這一階段 Follower 發(fā)送他們的 lastZxid 給 Leader扒披，Leader 根據(jù) lastZxid 決定如何同步數(shù)據(jù)。這里的實現(xiàn)跟前面的 Phase 2 有所不同：Follower 收到 TRUNC 指令會終止 L.lastCommitedZxid 之后的 Proposal 圃泡，收到 DIFF 指令會接收新的 Proposal碟案。

history.lastCommitedZxid：最近被提交的 Proposal zxid
history.oldThreshold：被認為已經(jīng)太舊的已經(jīng)提交的 Proposal zxid

image

轉(zhuǎn)自：http://www.reibang.com/p/2bceacd60b8a