[TOC]

什么是Zab協(xié)議粒没？

Zab協(xié)議 的全稱是 Zookeeper Atomic Broadcast （Zookeeper原子廣播）。

Zookeeper 是通過(guò) Zab 協(xié)議來(lái)保證分布式事務(wù)的最終一致性载萌。

1. Zab協(xié)議是為分布式協(xié)調(diào)服務(wù)Zookeeper專門設(shè)計(jì)的一種 支持崩潰恢復(fù) 的 原子廣播協(xié)議 胞锰，是Zookeeper保證數(shù)據(jù)一致性的核心算法芬骄。Zab借鑒了Paxos算法，但又不像Paxos那樣突琳，是一種通用的分布式一致性算法。它是特別為Zookeeper設(shè)計(jì)的支持崩潰恢復(fù)的原子廣播協(xié)議符相。

2. 在Zookeeper中主要依賴Zab協(xié)議來(lái)實(shí)現(xiàn)數(shù)據(jù)一致性拆融，基于該協(xié)議，zk實(shí)現(xiàn)了一種主備模型（即Leader和Follower模型）的系統(tǒng)架構(gòu)來(lái)保證集群中各個(gè)副本之間數(shù)據(jù)的一致性啊终。
   這里的主備系統(tǒng)架構(gòu)模型镜豹，就是指只有一臺(tái)客戶端（Leader）負(fù)責(zé)處理外部的寫(xiě)事務(wù)請(qǐng)求，然后Leader客戶端將數(shù)據(jù)同步到其他Follower節(jié)點(diǎn)蓝牲。

Zookeeper 客戶端會(huì)隨機(jī)的鏈接到 zookeeper 集群中的一個(gè)節(jié)點(diǎn)趟脂，如果是讀請(qǐng)求，就直接從當(dāng)前節(jié)點(diǎn)中讀取數(shù)據(jù)例衍；如果是寫(xiě)請(qǐng)求昔期，那么節(jié)點(diǎn)就會(huì)向 Leader 提交事務(wù)，Leader 接收到事務(wù)提交佛玄，會(huì)廣播該事務(wù)硼一，只要超過(guò)半數(shù)節(jié)點(diǎn)寫(xiě)入成功，該事務(wù)就會(huì)被提交梦抢。

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

image.png

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

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

2）保證一個(gè)全局的變更序列被順序引用圈驼。
Zookeeper是一個(gè)樹(shù)形結(jié)構(gòu)人芽，很多操作都要先檢查才能確定是否可以執(zhí)行，比如P1的事務(wù)t1可能是創(chuàng)建節(jié)點(diǎn)"/a"绩脆，t2可能是創(chuàng)建節(jié)點(diǎn)"/a/bb"萤厅，只有先創(chuàng)建了父節(jié)點(diǎn)"/a"，才能創(chuàng)建子節(jié)點(diǎn)"/a/b"靴迫。

為了保證這一點(diǎn)惕味，Zab要保證同一個(gè)Leader發(fā)起的事務(wù)要按順序被apply，同時(shí)還要保證只有先前Leader的事務(wù)被apply之后玉锌，新選舉出來(lái)的Leader才能再次發(fā)起事務(wù)名挥。

3）當(dāng)主進(jìn)程出現(xiàn)異常的時(shí)候，整個(gè)zk集群依舊能正常工作主守。

Zab協(xié)議原理

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

• 發(fā)現(xiàn)：要求zookeeper集群必須選舉出一個(gè) Leader 進(jìn)程救湖，同時(shí) Leader 會(huì)維護(hù)一個(gè) Follower 可用客戶端列表愧杯。將來(lái)客戶端可以和這些 Follower節(jié)點(diǎn)進(jìn)行通信。
• 同步：Leader 要負(fù)責(zé)將本身的數(shù)據(jù)與 Follower 完成同步鞋既，做到多副本存儲(chǔ)力九。這樣也是提現(xiàn)了CAP中的高可用和分區(qū)容錯(cuò)。Follower將隊(duì)列中未處理完的請(qǐng)求消費(fèi)完成后邑闺，寫(xiě)入本地事務(wù)日志中跌前。
• 廣播：Leader 可以接受客戶端新的事務(wù)Proposal請(qǐng)求，將新的Proposal請(qǐng)求廣播給所有的 Follower陡舅。

Zab協(xié)議核心

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

1）所有的事務(wù)請(qǐng)求必須由一個(gè)全局唯一的服務(wù)器來(lái)協(xié)調(diào)處理舒萎，這樣的服務(wù)器被叫做 Leader服務(wù)器。其他剩余的服務(wù)器則是 Follower服務(wù)器蹭沛。

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

3）分發(fā)之后Leader服務(wù)器需要等待所有Follower服務(wù)器的反饋（Ack請(qǐng)求）咆贬，在Zab協(xié)議中，只要超過(guò)半數(shù)的Follower服務(wù)器進(jìn)行了正確的反饋后（也就是收到半數(shù)以上的Follower的Ack請(qǐng)求）帚呼，那么 Leader 就會(huì)再次向所有的 Follower服務(wù)器發(fā)送 Commit 消息掏缎，要求其將上一個(gè) 事務(wù)proposal 進(jìn)行提交。

image.png

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

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

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

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

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

協(xié)議狀態(tài)切換
當(dāng)Leader出現(xiàn)崩潰退出或者機(jī)器重啟库说，亦或是集群中不存在超過(guò)半數(shù)的服務(wù)器與Leader保存正常通信狂鞋，Zab就會(huì)再一次進(jìn)入崩潰恢復(fù)，發(fā)起新一輪Leader選舉并實(shí)現(xiàn)數(shù)據(jù)同步璃弄。同步完成后又會(huì)進(jìn)入消息廣播模式要销，接收事務(wù)請(qǐng)求构回。

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

消息廣播
1）在zookeeper集群中，數(shù)據(jù)副本的傳遞策略就是采用消息廣播模式掏愁。zookeeper中農(nóng)數(shù)據(jù)副本的同步方式與二段提交相似歇由，但是卻又不同。二段提交要求協(xié)調(diào)者必須等到所有的參與者全部反饋ACK確認(rèn)消息后果港，再發(fā)送commit消息沦泌。要求所有的參與者要么全部成功，要么全部失敗辛掠。二段提交會(huì)產(chǎn)生嚴(yán)重的阻塞問(wèn)題谢谦。

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

image.png

消息廣播具體步驟
1）客戶端發(fā)起一個(gè)寫(xiě)操作請(qǐng)求萝衩。
2）Leader 服務(wù)器將客戶端的請(qǐng)求轉(zhuǎn)化為事務(wù) Proposal 提案回挽，同時(shí)為每個(gè) Proposal 分配一個(gè)全局的ID，即zxid猩谊。
3）Leader 服務(wù)器為每個(gè) Follower 服務(wù)器分配一個(gè)單獨(dú)的隊(duì)列千劈，然后將需要廣播的 Proposal 依次放到隊(duì)列中取，并且根據(jù) FIFO 策略進(jìn)行消息發(fā)送牌捷。
4）Follower 接收到 Proposal 后队塘，會(huì)首先將其以事務(wù)日志的方式寫(xiě)入本地磁盤中，寫(xiě)入成功后向 Leader 反饋一個(gè) Ack 響應(yīng)消息宜鸯。
5）Leader 接收到超過(guò)半數(shù)以上 Follower 的 Ack 響應(yīng)消息后憔古，即認(rèn)為消息發(fā)送成功，可以發(fā)送 commit 消息淋袖。
6）Leader 向所有 Follower 廣播 commit 消息鸿市，同時(shí)自身也會(huì)完成事務(wù)提交。Follower 接收到 commit 消息后，會(huì)將上一條事務(wù)提交焰情。

zookeeper 采用 Zab 協(xié)議的核心陌凳，就是只要有一臺(tái)服務(wù)器提交了 Proposal，就要確保所有的服務(wù)器最終都能正確提交 Proposal内舟。這也是 CAP/BASE 實(shí)現(xiàn)最終一致性的一個(gè)體現(xiàn)合敦。

Leader 服務(wù)器與每一個(gè) Follower 服務(wù)器之間都維護(hù)了一個(gè)單獨(dú)的 FIFO 消息隊(duì)列進(jìn)行收發(fā)消息，使用隊(duì)列消息可以做到異步解耦验游。 Leader 和 Follower 之間只需要往隊(duì)列中發(fā)消息即可充岛。如果使用同步的方式會(huì)引起阻塞，性能要下降很多耕蝉。

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

在 Zab 協(xié)議中垒在，為了保證程序的正確運(yùn)行蒜魄，整個(gè)恢復(fù)過(guò)程結(jié)束后需要選舉出一個(gè)新的 Leader 服務(wù)器。因此 Zab 協(xié)議需要一個(gè)高效且可靠的 Leader 選舉算法场躯，從而確保能夠快速選舉出新的 Leader 坐梯。

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

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

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

假設(shè)兩種異常情況：
1钝腺、一個(gè)事務(wù)在 Leader 上提交了，并且過(guò)半的 Folower 都響應(yīng) Ack 了耘成，但是 Leader 在 Commit 消息發(fā)出之前掛了榔昔。
2、假設(shè)一個(gè)事務(wù)在 Leader 提出之后瘪菌，Leader 掛了撒会。

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

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

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

Zookeeper是什么薛训，我們看看官方的定義：

ZooKeeper: A Distributed Coordination Service for Distributed Applications。

即ZK是為分布式系統(tǒng)提供協(xié)調(diào)服務(wù)的一個(gè)系統(tǒng)仑氛。那么什么場(chǎng)景需要協(xié)調(diào)呢乙埃？

ZK本質(zhì)上是一個(gè)基于內(nèi)存的KV系統(tǒng)闸英，但與一般KV系統(tǒng)不同的是ZK是以Path來(lái)作為Key，以DataTree樹(shù)視圖來(lái)組織這些Path介袜。

ZK內(nèi)部用ConcurrentHashMap<String /Path/, DataNode>來(lái)維持所有的Path甫何，每個(gè)DataNode會(huì)掛一個(gè)子節(jié)點(diǎn)的Path列表。**

所以ZK對(duì)某個(gè)Path的插入和查詢性能很高遇伞，并不需要遍歷什么樹(shù)辙喂，是直接對(duì)HashMap的操作。

ZK的可用性和可靠性的核心基礎(chǔ)便是ZAB（Zookpeeper原子廣播協(xié)議）鸠珠，也就是本文和大家分享的點(diǎn)兒巍耗。

我們會(huì)圍繞《ZooKeeper’s atomic broadcast protocol: Theory and practice》這個(gè)論文來(lái)講解ZAB。掌握了ZAB基本也就掌握了Zookeeper的精髓之處跳芳。

概述

ZAB協(xié)議是為Zookeeper專門設(shè)計(jì)的一種支持奔潰恢復(fù)的原子廣播協(xié)議芍锦。他不像Paxos算法是一種通用的分布式一致性算法竹勉，所以不能把ZAB和Paxos進(jìn)行等同飞盆。

在ZK中，主要依賴ZAB來(lái)實(shí)現(xiàn)分布式數(shù)據(jù)的一致性次乓，ZK本質(zhì)上是一種主備模式（Leader-Follower-Observer）的系統(tǒng)架構(gòu)來(lái)保持集群中各副本之間的一致性吓歇，即單點(diǎn)寫(xiě)Leader。同時(shí)也能在Leader crash后進(jìn)行恢復(fù)重新選主票腰。

ZAB協(xié)議的核心是定義了那些會(huì)改變Zookeeper服務(wù)器數(shù)據(jù)狀態(tài)的事務(wù)請(qǐng)求（Transaction）的處理方式城看，即：
所有事務(wù)請(qǐng)求必須由一個(gè)全局唯一的服務(wù)器（Leader）來(lái)協(xié)調(diào)處理，剩余的服務(wù)器稱為Follower（由權(quán)利參與選主）或者Observer（只負(fù)責(zé)從Leader同步數(shù)據(jù)杏慰，用于讀擴(kuò)展和分擔(dān)集群整體連接數(shù)）测柠。

所有事務(wù)請(qǐng)求必須由一個(gè)全局唯一的服務(wù)器（Leader）來(lái)協(xié)調(diào)處理，剩余的服務(wù)器稱為Follower（由權(quán)利參與選主）或者Observer（只負(fù)責(zé)從Leader同步數(shù)據(jù)缘滥，用于讀擴(kuò)展和分擔(dān)集群整體連接數(shù)）轰胁。

Leader負(fù)責(zé)將一個(gè)客戶端事務(wù)請(qǐng)求轉(zhuǎn)換成一個(gè)事務(wù)Proposal（提議），并將該P(yáng)roposal分發(fā)給集群中所有的Follower節(jié)點(diǎn)（Leader會(huì)維持一個(gè)Follower列表）朝扼。之后Leader需要等待Follower的反饋赃阀，一旦超過(guò)半數(shù)的Follower進(jìn)行了正確的反饋，Leader則會(huì)對(duì)所有Follower發(fā)起Commit消息擎颖，要求所有Follower將該P(yáng)roposal進(jìn)行提交（即寫(xiě)入Transaction Log）榛斯。

一、Crash-recovery system model （奔潰恢復(fù)模型）

Zookeeper是一個(gè)crash-recovery系統(tǒng)模型搂捧。即有能力從奔潰狀態(tài)中自我恢復(fù)驮俗，比如某個(gè)節(jié)點(diǎn)掛掉或者Leader掛掉，只要過(guò)半的節(jié)點(diǎn)存活并且能通信就能保證Zookeeper的高可用和高可靠能力允跑。

假設(shè)系統(tǒng)是由N個(gè)進(jìn)程組成 Π = {p1, p2, . . . , pN }王凑，每個(gè)進(jìn)程稱為Peer提佣，Peer之間能相互通信，并且各自有自己的存儲(chǔ)設(shè)備來(lái)存儲(chǔ)事務(wù)日志和DataTree快照（Snapshot）荤崇。

Q (quorum of Π)表示進(jìn)程集合中的過(guò)半節(jié)點(diǎn)集合拌屏，滿足 Q ? Π 和 |Q| > N/2。任何的兩個(gè)Q必然會(huì)有Peer交集术荤。

進(jìn)程（Process）有兩種狀態(tài)：up和down倚喂。ZK節(jié)點(diǎn)什么時(shí)候提供寫(xiě)能力呢？一個(gè)Follower節(jié)點(diǎn)掛了重啟后不是立馬就能對(duì)外響應(yīng)請(qǐng)求的瓣戚，因?yàn)镕ollower落后Leader的Proposal需要進(jìn)行同步端圈。只有同步完成后才能對(duì)外提供服務(wù)。那么Peer crash后到恢復(fù)階段稱為down狀態(tài)子库，從恢復(fù)階段到下次crash稱為up狀態(tài)舱权。

二、Expected properties （ZAB所具備基本屬性）

奔潰恢復(fù)模型中仑嗅，必須保證同一時(shí)間只有一個(gè)Leader存在宴倍，每個(gè)時(shí)間（epoch）的Leader節(jié)點(diǎn)可以是不一樣的，比如 , ρe ∈ Π仓技。epoch用int來(lái)表示鸵贬。

每個(gè)Proposal用<v, z>表示，其中v是提交的新?tīng)顟B(tài)值脖捻，z則是zxid阔逼。zxid唯一標(biāo)示一個(gè)事務(wù)請(qǐng)求（Transaction），一個(gè)事務(wù)請(qǐng)求有兩種狀態(tài)地沮，proposed和commited嗜浮，proposed表示一個(gè)事務(wù)已經(jīng)被Leader提出，但尚未被Quorum所ACK摩疑， commited表示這個(gè)Transaction已經(jīng)被Quorum所ACK危融，Leader對(duì)所有的follower發(fā)出了commit的請(qǐng)求，所有節(jié)點(diǎn)進(jìn)行了本地commit操作未荒。

為了滿足Zookeeper的副本一致性专挪，ZAB需要滿足的一致性基本條件：

• Integrity（正確性）：如果有節(jié)點(diǎn)收到commit proposal的請(qǐng)求，那么肯定是有節(jié)點(diǎn)進(jìn)行了廣播片排。即proposal不能是拜占庭錯(cuò)誤寨腔。
• Total order：全局順序性，即某個(gè)Peer提交了兩個(gè)Proposal率寡，<v, z>和<v', z'>迫卢。 如果<v, z>比<v', z'>先被提交，那么從任何其他Peer上看冶共，也必然是<v, z>比<v', z'>先被提交乾蛤。
• Agreement：如果Pi提交了<v, z>每界， Pj提交了<v', z'>，那么要不pi已經(jīng)提交了了<v', z'>, 要不pj已經(jīng)提交了<v, z>

另外家卖，對(duì)于Leader來(lái)說(shuō)眨层，需要滿足的順序性屬性為：

• Local primary order（本地順序性）：如果Leader在原子廣播階段先后commit了<v, z>和<v', z'>， 如果一個(gè)Follower commit了<v', z'>上荡， 那么Follower肯定先commit了<v, z>趴樱。
• Global primary order（全局一致性）：如果ρi是epoch為i的leader，ρj 是epoch為j的leader酪捡，而且i < j, 表示 ρi是之前的leader叁征， ρj是之后的leader。ρi commit了<v, z>逛薇， pj commit了<v', z'>, 如果leader commit了<v, z> 和 <v', z'>捺疼， 那么肯定是<v, z> 先于 <v', z'>被commit.
• Primary integrity (正確性）：ρi 如果廣播了<v, z> ，并且其他Follower commit了<v', z'>永罚，而<v', z'> 是pj先于pi提交的啤呼，即pj的epoch比pi的epoch小，那么pi肯定也commit了<v, z>尤蛮。

三媳友、Atomic broadcast protocol（原子廣播協(xié)議）

在ZAB協(xié)議中斯议，每個(gè)Peer有三種可能的狀態(tài)：following产捞、leading、election哼御。其中處于following的Peer稱為Follower坯临，處于leading的Peer稱為L(zhǎng)eader.

ZAB協(xié)議整體分為四個(gè)階段：0）Leader election 、 1）discovery恋昼、 2）synchronization看靠、 3）broadcast

其中處于階段0-階段2的Zookeeper集群還處于不可用的狀態(tài)，即不能響應(yīng)客戶端的讀寫(xiě)請(qǐng)求操作液肌。只有選出主挟炬，完成上一個(gè)epoch期間的proposal的廣播以及補(bǔ)齊已經(jīng)commit的proposal后，整個(gè)集群才能對(duì)外服務(wù)嗦哆。

也就是只有處于階段3即原子廣播階段才能對(duì)外服務(wù)谤祖。

ZAB的每個(gè)階段是順序推進(jìn)的，如果在階段1-3任何一個(gè)階段出現(xiàn)故障老速，比如失敗或者超時(shí)粥喜，則會(huì)進(jìn)入階段0，重新再來(lái)一輪橘券。

先看幾個(gè)概念：

• zxid：zxid作為Zookeeper最核心的一個(gè)概念额湘，唯一標(biāo)識(shí)一個(gè)transaction卿吐，全局唯一遞增的64位正數(shù)。即proposal表示為<value, zxid>锋华， zxid由 <epoch, count>構(gòu)造嗡官，
• epoch：每個(gè)leader生命周期的一個(gè)標(biāo)識(shí)，簡(jiǎn)單來(lái)說(shuō)就是年號(hào)毯焕，newEpoch等于上一個(gè)epoch + 1谨湘，即newEpoch = lastEpoch + 1，zxid的高32位芥丧；
• count：標(biāo)識(shí)每個(gè)epoch期間的每個(gè)transaction id紧阔，每個(gè)count都從0開(kāi)始加一遞增，zxid的低32位续担。
• zxid的對(duì)比：我們稱zxid <e, c> 大于 zxid'<e', c'>擅耽，當(dāng)滿足 (e > e' ) || (e = e' & c > c').

每個(gè)Peer會(huì)存儲(chǔ)4個(gè)核心變量：

• history：被Peer提交的歷史proposal
• acceptedEpoch：接收最新NEWEPOCH的epoch
• currentEpoch：接收最新NEWLEADER的epoch
• lastZxid：history中最近一個(gè)提交的proposal的zxid

簡(jiǎn)單的來(lái)說(shuō)，acceptedEpoch用于Discovery階段來(lái)判斷要不要接收先的NEWEPOCH物遇。currentEpoch用于存儲(chǔ)上個(gè)epoch的值乖仇。

這幾個(gè)值都會(huì)進(jìn)行存儲(chǔ)，其中acceptedEpoch和currentEpoch會(huì)存儲(chǔ)在磁盤上询兴，history和lastZxid可以從DataTree的snapshot中恢復(fù)乃沙。

階段0: Leader Election

這個(gè)階段的目的是選出一個(gè)Leader，然后進(jìn)入到后續(xù)的階段诗舰。具體的算法警儒，我們?cè)赯ookeeper的實(shí)現(xiàn)小節(jié)中闡述，也就是FLE（Fast Leader Election）算法眶根。

image.png

主流程:

1. Follower節(jié)點(diǎn)F知道準(zhǔn)Leader節(jié)點(diǎn)后蜀铲，發(fā)送一個(gè)FOLLOWERINFO類型消息，將自己的信息上報(bào)給準(zhǔn)Leader属百，該信息包括自己的epoch內(nèi)容F. acceptedEpoch
2. Leader節(jié)點(diǎn)L等待收到過(guò)半的FOLLOWERINFO消息后记劝，從這些F.acceptedEpoch中取出最大的epoch，并且加1族扰，即newEpoch = max {F. acceptedEpoch} + 1厌丑， 然后將新的epoch信息NEWEPOCH發(fā)給Quorum中的節(jié)點(diǎn)，等待Quorum的ACK確認(rèn)
3. Follower節(jié)點(diǎn)收到NEWEPOCH后渔呵，將新的epoch與自己的epoch比較
   a. 如果準(zhǔn)Leader提過(guò)來(lái)的新epoch > acceptedEpoch, 即接收新的epoch怒竿。更新自己的acceptedEpoch為新epoch，然后給Leader回復(fù)一個(gè)
   ACKEPOCH信息厘肮，該信息包括上個(gè)epoch愧口，history和lastZxid。
   b. 如果準(zhǔn)Leader提過(guò)來(lái)的新epoch < acceptedEpoch类茂，則回退到階段0
4. Leader收到Quorum中所有follower的ACKEPOCH后耍属，從所有的follower找出currentEpoch最大的或者lastZxid最大的follower托嚣，然后把該 follower的history作為自己的history。

有點(diǎn)需要注意的是厚骗，Quorum是包括Leader自身的示启。這里的Leader還只是準(zhǔn)Leader。

總結(jié)下來(lái):

Discovery的目的就是確定一個(gè)新leader的epoch值领舰，然后找到上個(gè)epoch周期內(nèi)的擁有最大zxid的follower節(jié)點(diǎn)夫嗓，然后進(jìn)入同步階段，把這個(gè)history進(jìn)行重 新同步冲秽。

之所以可以取最大zxid作為新的leader的history舍咖，是基于一個(gè)假設(shè)，因?yàn)閦xid是全局遞增的锉桑，也就是擁有最大zxid的節(jié)點(diǎn)也用了最新的proposal提交記錄排霉。

階段2:Synchronization
同步階段的目的就是上一個(gè)階段的時(shí)候Leader拿到了最新的history，需要進(jìn)行同步給所有Follower民轴，處理上一個(gè)epoch階段遺留proposal攻柠，該commit的 commit，該清理的清理.

image.png

主流程:

1. 在上階段準(zhǔn)Leader拿到過(guò)半的ACKEPOCH后后裸，也就是有了最新的proprosal history瑰钮。
2. Leader給所有Follower發(fā)一個(gè)NEWLEADER類型消息，把最新的epoch和histroy帶過(guò)去微驶。
3. Follower收到NEWLEADER消息后浪谴，判斷當(dāng)選舉輪次自己的acceptedEpoch是否和新epoch相同

a. Follower的acceptedEpoch和新epoch相同，表示自己已經(jīng)跟上了新的epoch祈搜，那么
i. 更新自己的currentEpoch為新的epoch较店，表示進(jìn)入新的朝代了，
ii. 按照zxid的大小逐一進(jìn)行本地proposed容燕，此時(shí)這些transaction還未commit iii. 更新自己的history為最新的history
iv. 返回一個(gè)ACKNEWLEADER給Leader，表示本Follower已經(jīng)同步完數(shù)據(jù)
b. 如果Follower的acceptedEpoch和新epoch不相同婚度，那么退回到階段0蘸秘，重新進(jìn)行選主

4. Leader收到Quorum中節(jié)點(diǎn)的ACKNEWLEADER后，對(duì)history這些proposal進(jìn)行commit蝗茁，所有Follower節(jié)點(diǎn)即收到commit請(qǐng)求
5. Follower收到Leader的對(duì)history的COMMIT消息后醋虏，對(duì)于outstanding的事務(wù)(即已經(jīng)proposed，但是還未commit的transaction)哮翘，進(jìn)行按
   zxid順序進(jìn)行commit颈嚼。
6. LEADER和FOLLOWER都同步完成后進(jìn)入階段3.

階段3:Broadcast

如果Peers都安然無(wú)恙，那么會(huì)永遠(yuǎn)停留在這個(gè)階段饭寺，也就是原子廣播階段阻课，該階段才是真正對(duì)外服務(wù)的階段叫挟，也就是開(kāi)始接收外界寫(xiě)請(qǐng)求(Transaction) 了。

這個(gè)階段不可能會(huì)存在雙主限煞，這個(gè)階段也會(huì)又新的Follower或者Observer加入進(jìn)來(lái)抹恳。

image.png

image.png

主流程:

1. Leader接收到一個(gè)write請(qǐng)求后，生成一個(gè)新的proposal <value, zxid>, zxid = lastZxid + 1. 然后對(duì)Quorum中的follower發(fā)起propose請(qǐng)求

2. 2. Follower收到新的propose后署驻，講propose放到自己的history隊(duì)列中奋献。返回返回ACK給leader，表示我準(zhǔn)備好了旺上。

3. Leader收到過(guò)半的針對(duì)propose的ACK后瓶蚂，認(rèn)為獲得了大部分的同意，則進(jìn)行commit宣吱，對(duì)所有follower發(fā)起COMMIT請(qǐng)求扬跋。

4. Follower收到propose <v, z> 的commit后，開(kāi)始提交凌节。
   a. 但是為了滿足zxid的全局一致性钦听，如果此時(shí)存在比該zxid更小的zxid‘還未提交，那么需要等待zxid’的propose <v', z'>的commit倍奢。
   b. 等待比zxid都要小的zxid‘都commit后朴上，zxid開(kāi)始進(jìn)行本地提交。

5. 在原子廣播階段卒煞，Leader也能接收新的Follower加入痪宰，然后放到自己的Quorum中。這塊就比較簡(jiǎn)單了畔裕。

   a. 新加入的節(jié)點(diǎn)會(huì)給Leader發(fā)一個(gè)FOLLOWERINFO請(qǐng)求
   b. Leader收到FOLLOWERINFO請(qǐng)求后衣撬，會(huì)回NEWEPOCH和NEWLEADER，即告訴他當(dāng)前的epoch和當(dāng)前的history c. 新節(jié)點(diǎn)收到NEWLEADER后扮饶，如果正常邏輯處理后具练，回一個(gè)ACKNEWLEADER給Leader
   d. Leader收到ACKNEWLEADER后，給該新節(jié)點(diǎn)一個(gè)COMMIT請(qǐng)求甜无，讓新節(jié)點(diǎn)提交history
   e. Leader最后把新加入的Follower節(jié)點(diǎn)放入自己的Quorum列表中扛点。

注意點(diǎn):

• 整個(gè)propose其實(shí)是并行的，對(duì)于Leader來(lái)說(shuō)岂丘，一個(gè)proposal不會(huì)等上一個(gè)commit才會(huì)發(fā)起新proposal的propose陵究。
• 每個(gè)Peer進(jìn)行本地commit proposal的時(shí)候是有序的，即zxid小的需要先commit奥帘。這也是為了保障全局順序性铜邮。

四、Implementation (算法實(shí)現(xiàn))

在Zookeeper實(shí)現(xiàn)過(guò)程中，對(duì)上述的幾個(gè)階段進(jìn)行了優(yōu)化松蒜。如下:

image.png

其中的Fast Leader Election階段的算法核心:嘗試選出一個(gè)Peer作為L(zhǎng)eader扔茅，該P(yáng)eer擁有最新的history數(shù)據(jù)即最大的lastZxid。那么就可以把Discovery階 段省掉牍鞠，所以實(shí)現(xiàn)上就簡(jiǎn)化成了三階段:

1)Fast Leader Election 咖摹、2)Recovery 、3)Broadcast

另外Recovery階段即恢復(fù)階段的算法就需要做調(diào)整了难述，如下:

Recovery階段:

image.png

主流程:

1. Leader當(dāng)前已經(jīng)通過(guò)FAST LEADER ELECTION階段選出萤晴，即該Leader已經(jīng)擁有最大的zxid。
2. Leader從lastZxid中拿出epoch進(jìn)行加1作為新的epoch胁后，count低32位重置為0店读，即 LastZxid ← {lastZxid.epoch + 1, 0}
3. Follower節(jié)點(diǎn)連接上準(zhǔn)Leader后，發(fā)送FOLLOWERINFO消息攀芯，并且把自己的lastZxid帶上
   a. 如果Leader拒絕了連接屯断，可能是Leader的epoch比自己的小等原因，那么重新Follower狀態(tài)設(shè)置回election侣诺，回退到階段0殖演，即FLE階段