本文将會圍繞《ZooKeeper’s atomic broadcast protocol: Theory and practice》這篇論文講解 ZooKeeper 和 ZAB 的精髓之處。
📢📢📢大家好，我是周周，前幾周開組會時被點名回答一些 ZooKeeper 相關問題，竟然一問三不知，組長直呼當初被我帥氣外表所騙，稀裡糊塗的招了進來。
于是下來後對這個在我手發揮極其重要作用的這項基建産生了濃厚興趣，是以決定痛改前非，先從 ZAB 出發，開啟一系列的 ZooKeeper 進階之旅。
tips：
本文主要是對 Paper 的消化和了解，稍顯枯燥，建議工作累了劃水時對着 Paper 慢慢看。
文章目錄
- 1 概述
-
- 1.1 什麼是 ZooKeeper
- 1.2 什麼是 ZAB
- 1.3 奔潰恢複模型
- 1.4 ZAB 的基本屬性
- 2 原子廣播協定
-
- 2.1 選舉階段
- 2.2 發現階段
- 2.3 同步階段
- 2.4 廣播階段
- 3 ZAB 協定實作
-
- 3.1 Discover
- 3.2 Fast Leader Election
-
- 選票 PK
- 接收選票
- FLE 算法
- 算法精髓
- 4 總結
1 概述
ZooKeeper 作為一項重要的基礎設施應用于各大廠商中，其可用性和可靠性不言而喻，而 ZAB（ZooKpeeper 原子廣播協定）更是保證 ZK 可用性和可靠性的基礎，也是本文主要的分享點。
1.1 什麼是 ZooKeeper
在了解 ZAB 之前，我們要先了解 ZooKeeper 是究竟什麼？
關于這個問題，ZK 官方給出了自己的定義：A Distributed Coordination Service for Distributed Applications。即 ZK 是一個為分布式系統提供協調能力的系統。
ZK 作用
- 配置服務
- 分布式鎖
- 服務管理
- 服務注冊與發現
資料模型
ZK 本質還是一個基于記憶體的 KV 系統，但與一般 KV 系統不同的是 ZK 以 Path 來作為 Key，以 DataTree 樹視圖來組織這些 Path。
如上圖所示，資料資訊被儲存在⼀個個的資料節點上，這些節點被稱為 ZNode，ZNode 是 ZooKeeper 中最⼩資料機關，在 ZNode 下⾯⼜可以再挂 ZNode，這樣⼀層層下去就形成了⼀個階層化命名空間 ZNode 樹。
ZK 内部用
ConcurrentHashMap<String , DataNode>
來維持所有的 Path，每個 ZNode 會挂一個子節點的 Path 清單。
是以 ZK 對某個 Path 的插入和查詢性能很高，并不需要周遊什麼樹，是直接對 HashMap 的操作。
節點角色
- Leader 所有的寫操作均需要通過該節點完成
- Follower 處理讀請求和轉發寫請求給 Leader，并對 Leader 廣播的寫請求投票
- Observer 類似 Follower，但無投票權
1.2 什麼是 ZAB
ZAB 協定是為 Zookeeper 專門設計的一種支援崩潰恢複的原子廣播協定。而 Paxos 是一種通用的分布式一緻性算法，故不能把 ZAB 和 Paxos 進行等同。
在 ZK 中主要依賴 ZAB 來實作分布式資料的一緻性。從本質上講，ZK 也是一種主備模式（Leader-Follower-Observer）的系統架構，用來保持叢集中各副本之間的一緻性，即在 Leader 進行單點寫，同時也能在 Leader crash 後進行恢複重新選主。
ZAB 協定的核心是定義了那些會改變 ZooKeeper 伺服器資料狀态的事務請求（Transaction）的處理方式。即：
1）所有事務請求必須由一個全局唯一的伺服器（Leader）來協調處理，剩餘的伺服器稱為 Follower（有權利參與選主）或者 Observer（隻負責從 Leader 同步資料，用于讀擴充和分擔叢集整體連接配接數）。
2）Leader 負責将一個用戶端事務請求轉換成一個事務 Proposal（提議），并将該 Proposal 分發給叢集中所有的 Follower 節點（Leader 會維持一個 Follower 清單）。
3）之後 Leader 需要等待 Follower 的回報，一旦超過半數的 Follower 進行了正确的回報，Leader 則會對所有 Follower 發起 Commit 消息，要求所有 Follower 将該 Proposal 進行送出（即寫入 Transaction Log）。
- Refer 執行個體詳解ZooKeeper ZAB協定、分布式鎖與上司選舉
1.3 奔潰恢複模型
Crash-recovery system model
ZooKeeper 是一個奔潰恢複系統模型，即有能力從崩潰狀态中自我恢複。如某個節點挂掉或者 Leader 挂掉，隻要過半的節點存活并且能通信就能保證 ZooKeeper 的高可用和高可靠能力。
假設系統是由 N 個程序組成
Π = {p1, p2, . . . , pN }
，每個程序稱為 Peer（節點），且節點之間能夠互相通信，并有各自的存儲來記錄事務日志和 DataTree 的快照。
Q (quorum of Π)
表示程序集合中的過半節點集合，滿足
Q ⊆ Π
和
|Q| > N/2
。任何的兩個 Q 必然會有 Peer 之間的交集。
程序有兩種狀态：up 和 down。ZK 節點什麼時候提供寫能力呢？
一個 Follower 節點挂了重新開機後不是立馬就能對外響應請求的，因為 Follower 落後 Leader 的 Proposal，隻有待資料同步後才能對外提供服務。
是以 Peer 奔潰後到開始恢複前階段稱為 down 狀态，從開始恢複階段到下次奔潰稱為 up 狀态。
1.4 ZAB 的基本屬性
在崩潰恢複模型中，需要保證同一時刻隻有一個 Leader 存在，每個時期（epoch）的 Leader 可以不同，如
p1.p2.p3....pe..., ρe ∈ Π
。
每個 Proposal 用
<v, z>
表示，其中
v
是送出的新狀态值，
z
則是 zxid。
zxid 用于唯一标示一個事務請求（Transaction），一個事務請求有兩種狀态：
- proposed 表示一個事務已經被 Leader 提出，但尚未被 Quorum 進行 ACK，
- commited 表示這個 Transaction 已經被 Quorum 進行 ACK，後續 Leader 對所有的 Follower 發出 commit 的請求，所有節點進行了本地 commit 操作。
因為，為了實作 ZooKeeper 副本的一緻性，ZAB 需要滿足一下基本條件：
- Integrity（正确性）：如果有節點收到 commit Proposal（送出議案） 的請求，那麼肯定是有節點對該 Proposal 進行了廣播。即 Proposal 不能是拜占庭問題。
- Total order（全局順序性）：，即某個 Peer 按序送出了
<v, z>
<v', z'>
<v, z>
<v', z'>
- Agreement（契約性）：如果 Pi 送出了
<v, z>
<v', z'>
<v', z'>
<v, z>
此外，對于 Leader 節點而言，還需滿足其順序屬性：
- Local primary order（本地順序性）：如果 Leader 在原子廣播階段先後 commit了
<v, z>
<v', z'>
<v', z'>
<v, z>
- Global primary order（全局一緻性）：如果 ρi 是 epoch 為 i 的 Leader，ρj 是 epoch 為 j 的 Leader，且 i < j, 表示 ρi 是之前的 Leader， ρj 是之後的 Leader。ρi 送出了
<v, z>
<v', z'>
<v, z>
<v', z'>
<v, z>
<v', z'>
- Primary integrity (正确性）：ρi 如果廣播了<v, z> ，并且其他Follower commit了<v’, z’>，而<v’, z’> 是pj先于pi送出的，即pj的epoch比pi的epoch小，那麼pi肯定也commit了<v, z>。
2 原子廣播協定
Atomic broadcast protocol
在了解原子廣播協定前，先來了解一些概念：
三種狀态
在 ZAB 協定中，每個伺服器節點 Peer 有三種可能狀态：following、leading 以及 election。（其中處于 following 的節點稱為 Follower，處于 leading 的節點稱為 Leader）
四個階段
同時 ZAB 協定整體分為四個階段：0）Leader election、 1）discovery、 2）synchronization、 3）broadcast。
處于階段 0）到階段 2）的 ZK 叢集還處于不可用的狀态，即不能響應用戶端的讀寫請求操作。隻有選出主并完成上一個 epoch 期間的 Proposal 的廣播後，整個叢集才會對外服務。也就是說隻有處于階段3即原子廣播階段才能對外服務。
ZAB 的每個階段是順序推進的，如果在階段 1）-3） 任何一個階段出現故障，比如失敗或者逾時，則會重新進入階段 0）再來一輪。
zxid
zxid 作為 ZooKeeper 最核心的一個概念，唯一辨別一個 Transaction，即 Proposal 表示為
<value, zxid>
。為了保證順序性，zkid 必須單調遞增，是以全局唯一遞增的 64 位正整數，是以 zxid 又由
<epoch, count>
構造。
epoch 是 zxid 的高 32 位，指的是每個 Leader 生命周期的一個辨別，簡單來說就是年号。每次選出新的 Leader，epoch 就加一。
count 是低 32 位，辨別一個 epoch 期間每個 Transaction ID，每個 epoch 的 count 都會從 0 開始遞增。
核心變量
1）history：被 Peer 送出的曆史 Proposal
2）acceptedEpoch：接收最新 NEWEPOCH 的 epoch
3）currentEpoch：接收最新 NEWLEADER 的 epoch
4）lastZxid：history 中最近一個送出的 Proposal 的 zxid
簡單的來說，acceptedEpoch 用于 Discovery 階段來判斷要不要接收新的 NEWEPOCH。currentEpoch 用于存放上個 epoch 的值。
這幾個值都會進行存儲，其中 acceptedEpoch 和 currentEpoch 會存儲在磁盤上，history 和 lastZxid 可以從 DataTree 的 snapshot 中恢複。
2.1 選舉階段
Leader Election
這個階段的目的是選出一個 Leader，然後進入後續階段。具體的算法将會在後續 ZK 的實作小節中闡述，也就是 FLE（Fast Leader Election）算法。
2.2 發現階段
Discovery
該階段的目的就是确定一個新 Leader 的 epoch 值，然後找到上個 epoch 周期内擁有最大 zxid 的 Follower 節點。之是以可以取最大 zxid 作為新的 Leader 的 history，是基于一個假設，因為 zxid 是全局遞增的，也就是擁有最大 zxid 的節點也擁有了最新的 Proposal 送出記錄。
具體流程如下：
1）Follower 向準 Leader 發送一個 FOLLOWERINFO 類型消息，将自己的資訊上報給準 Leader，該資訊包括自己的 epoch 内容 F.acceptedEpoch。
2）Leader 等待收到過半的 FOLLOWERINFO 消息後，從這些 Follower 節點的 acceptedEpoch 中取出最大的 epoch，并且加1，即
newEpoch = max {F.acceptedEpoch} + 1
，再将新的 epoch 資訊 NEWEPOCH 發給叢集中的節點。
3）Follower 收到 NEWEPOCH 後，将新的 epoch 與自己的 epoch 比較：
- 新 epoch > acceptedEpoch, 即更新自己的 acceptedEpoch為 為新 epoch，然後給 Leader 發送一個 ACKEPOCH 資訊，該資訊包括上個 epoch、history 和 lastZxid。
- 新 epoch < acceptedEpoch，則回退到階段0
4）Leader 收到所有 Follower 的 ACKEPOCH 後，從中找出 currentEpoch 最大的或者 lastZxid 最大的 Follower，把該 Follower 的 history 作為自己的 history。
值得注意的是，Quorum 是包括 Leader 自身的。這裡的 Leader 還隻是準 Leader。
2.3 同步階段
Synchronization
同步階段的目的就是準 Leader 需要将最新的 history 同步給叢集内所有的 Follower。
1）在上階段準 Leader 拿到過半的 ACKEPOCH 後，也就是有了最新的 Proprosal history。
2）Leader 給所有 Follower 發一個 NEWLEADER 類型消息，把最新的 epoch 和 histroy 帶過去。
3）Follower 收到 NEWLEADER 消息後，判斷自己的 acceptedEpoch 和新 epoch 是否相等。
- 如果相等則表示自己已經跟上了新 epoch，那麼更新自己的 currentEpoch 為新 epoch，表示進入新的朝代。同時按照 zxid 的大小逐一進行本地 proposed（此時這些 Transaction 還未 commit），然後更新history，傳回一個 ACKNEWLEADER 消息表示已經同步完資料。
- 如果不相等，那麼退回到選舉階段，重新進行選主。
3）Leader 收到叢集中節點的 ACKNEWLEADER 後，對 history 中的這些 Proposal 進行 commit，即向所有 Follower 發送 commit 請求。
4）Follower 收到 Leader 對 history 的 COMMIT 消息後，對于 outstanding（即已經 proposed，但還未 commit）的事務按 zxid 順序進行 commit。
5）Leader 和 Follower 都完成資料同步後進入廣播階段.
2.4 廣播階段
如果所有節點都安然無恙，那麼叢集就會永遠停留在這個階段，也就是原子廣播階段。該階段才真正對外通過服務，也就是開始接收外界寫請求（Transaction）。
這個階段不可能會存在雙主，但可以加入新的 Follower 或 Observer 節點。
發起 Proposal 流程
1）Leader 在接收到 write 請求後，生成一個
Proposal <value, zxid>, zxid = lastzxid + 1
，然後對叢集 Quorum 中的 Follower 節點發起 propose 請求
2）Follower 接收到 propose 請求後，将 Proposal 放入自己 history 隊列中，并傳回 ACK
3）Leader 收到過半的針對 Proposal 的 ACK 後，認為獲得了大部分的同意，則對 Proposal 進行送出，向所有 Follower 發起 COMMIT 請求
4）Follower 收到
Propose <value, zxid>
的 COMMIT 請求後開始送出，但是為了滿足 zxid 的全局一緻性，如果存在比該 zxid 更小的
zxid‘
還未送出，那麼需要等待
zxid’
的
Propose <value', zxid'>
被送出
新增 Follower 流程
1）新加入的節點會給 Leader 發一個 FOLLOWERINFO 請求
2）Leader 收到 FOLLOWERINFO 請求後會回複 NEWEPOCH 和 NEWLEADER，即告訴 Follower 目前的 epoch 和 history
3）新節點收到 NEWLEADER 後，如果正常邏輯處理後，回一個 ACKNEWLEADER 給 Leader
4）Leader 收到 ACKNEWLEADER 後給該新節點一個 COMMIT 請求，讓新節點送出 history
5）Leader 最後把新加入的 Follower 節點放入自己的 Quorum 清單中。
值得注意的是：
- 整個 propose 過程是并行的，對于 Leader 來說，一個 Proposal 不會等上一個 commit 才會發起新 Proposal 的 propose 請求
- 每個 Peer 進行本地 commit Proposal 的時候是有序的，即 zxid 小的需要先 commit。這也是為了保障全局順序性
3 ZAB 協定實作
在 ZooKeeper 實作原子廣播協定中，對上面描述的幾個階段進行了優化，如圖所示：
ZK 将階段 0）選主和階段 1）發現合二為一，實作為 Fast Leader Election 階段，其算法核心内容是嘗試選出一個擁有最新 history 資料（即最大 lastZxid）的節點作為 Leader。這樣就可以把 Discovery 階段省掉。
同時 ZK 還針對階段 2）同步進行了一些調整，實作為發現階段，接下來我們将較長的描述這兩個階段的具體實作。
3.1 Discover
當 ZK 叢集進入到恢複階段，Leader 節點已由 FLE 階段選舉出來，并且擁有最大的 zxid。
為了将叢集中節點資料恢複到一緻，Follower 将處理來自準 Leader 的三種請求：
- SNAP：從 Leader 拉一份 snapshot（快照），再進行本地送出
- DIFF：送出請求體中的 Proposal
- TRUNC：Follower 節點丢棄
Leader.lastCommitedZxid～lastZxid
接下來的主要流程：
1）Leader 從 lastZxid 中拿出 epoch 進行加 1 作為新的 epoch，并且低 32 位重置為 0，即
LastZxid ← {lastZxid.epoch + 1, 0}
。
2）Follower 連接配接上準 Leader 節點後，向其發送攜帶自己 lastZxid 的 FOLLOWERINFO 資訊。如果 Leader 拒絕了連接配接，可能是因為 Leader 的 epoch 比自己小等原因，那麼 Follower 重新将狀态設定回 election，回退到FLE階段。
3）Leader 接收到 Follower 請求後，發送 NEWLEADER 資訊給 Follower。
4）如果 Follower 的 lastZxid 小于 Leader 中的 lastCommittedZxid，證明 Follower 的送出落後于 Leader，需要同步：
- 如果 Follower 的 lastZxid 比 Leader 設定的同步 DIFF 門檻值還小，需要同步整個 snapshot，即向 Follower 發一個 SNAP 類型消息
- 否則 發送一個 DIFF 類型消息，消息内容是 Leader 已經送出的 history 中的那些 diff 的議案
5）Follower 收到準 Leader 的 NEWLEADER 請求後，需要對比 epoch：
- 如果 NEWLEADER.newLeaderZxid.epoch 比目前小，那麼不能認可該 Leader，自己更新為選主狀态，重新選主
- 如果 epoch 是同一個輪次中，那麼則需要處理 SNAP、DIFF 和 TRUNC 請求
- 完成同步後，傳回一個 ACKNEWLEADER 消息，進入廣播階段
6）Leader 收到叢集大部分 Follower 節點的 ACKNEWLEADER 後，表示過半節點完成了同步，也進入階段3——廣播階段。
至于為什麼出現 TRUNC 請求，原因很簡單，因為出現了一個有意思的例子：https://issues.apache.org/jira/browse/ZOOKEEPER-1154
3.2 Fast Leader Election
FLE 算法的核心是在叢集 Quorum 中找出 lastZxid 最大的那個節點。那麼每個節點之間需要同步選票，就需要幾個核心資訊：
- id：投票節點的 myid（在配置檔案中配置）
- vote：被投票節點的 myid
- state：投票節點的狀态，可以是 leading、following 或 election（隻有重新發起新一輪 FLE 後才會變更為 election）
- round：投票輪次，每一輪 FLE 都會有一個 round，并在之前基礎上加 1
選票 PK
我們将定義
Vote(zi , i)
表示一次投票，即 myid 為 i 的節點目前 zxid 是 zi。同時定義 Vote 間的優劣：
(zi, i) > (zj, j), 滿足zi > zj || (zi = zj && i > j)
，通俗來說，zxid 大的優先，誰大選誰，zxid 相同時再比較 myid，大的優先。
是以我們在配置 ZK 叢集時，需要給每個節點配置一個全局唯一的 myid。
接收選票
在 FLE 階段，叢集中每個節點都會維護一個清單當做 “投票箱” 以存放其他節點的選票資訊，當然，也包括節點自身的選票。ZK 還會啟動一個線程以便發送自身選票和接收其他節點的選票，同時還會根據對方選票記錄和變更自己的狀态和選擇。
1）如果目前節點是選主（election）狀态，則先将對方投票資訊放入清單中
2）如果對方節點狀态也是選主，那麼将先比較一下選舉輪次（round），如果目前節點輪次小于對方節點，則通知對方自己的投票資訊
3）如果目前節點非選主狀态，說明目前節點已經是 Leader 或 Follower，且對方節點還是選主狀态的話，則需要告知對方目前節點的狀态
4）如果雙方都非選主狀态，則代表這一輪選舉結束
整個流程的精髓在于：記錄對方的選票，然後互通有無。
FLE 算法
先看主流程：
1）節點 P 在啟動初始化後，會投票給自己，即投票是
vote <P.zxid, P.myid>
，此時
round = round + 1
，就是 1。
2）然後開始給所有節點發送自己的投票
（<P.zxid, P.myid>, P.myid, election, 1）
。
3）完成對自己的投票後，開始等待接收其它節點的投票資訊。（這裡需要注意一下，收到的投票不是投給 P 的，是由其它節點廣播給所有叢集内的節點自己的選擇）
4）當節點收到了對法節點狀态是 Leading 的通知或者在循環内達成了投票共識（即決策了Leader）後，退出循環，結束選主狀态。
決策流程
首先從目前節點的選票隊列中彈出收到的選票 n，如果目前沒有收到的投票，那麼發出自己的投票資訊，等待 2 倍的 timeout 時間。
當拿到選票後，對選票處理也很簡單，根據選票中投票節點的狀态可以做出兩種行為：
1 如果選票 n 是選主狀态，即
P.state = election
：
1）比較選票的投票輪次
-
如果選票中的輪次大于目前節點，代表自身輪次落後，需要更新目前節點的輪次和選票隊列
（i）更新節點自身的 round 為選票 n 的 round，同時清空選票隊列 ReceivedVotes
（ii）PK 選票
v = Vote(zxid , myid)
，如果對方節點的選票較新，則修改自身選票為 v
（iii）向叢集廣播自己新一輪選票
- 如果選票輪次與目前節點相同，表示在同一個選票輪次中，那麼更新自身的 vote 為選票 n 中的 vote，然後再次進行廣播
- 如果選票輪次比目前節點小，則忽略改選票，繼續處理下一條新
2）如果投票 n 是有效的，那麼就放入到隊列 ReceivedVotes 中
3）如果目前 ReceivedVotes 等于 SizeEnsemble，也就是所有節點都進行了投票，則進行開票流程
4）如果目前節點獲得的投票已經占了過半數，則等一個選舉時間（tickTime）後進行開票
2 如果選票 n 已經是 leading 或 following 狀态，那麼說明某個節點已經進行開票并決策出結果，目前的節點進行更新狀态即可：
1）如果選票 n 和目前節點處于同一個投票輪次，則選票有效，放入隊列中：
- 如果 n 的狀态是 leading，表示對方節點已經是 leading 狀态，那麼直接開票，不用繼續看其餘選票。
- 如果 n 是 following，那麼對比下選票看看是不是自己中選（超過過半節點）了，如果是則開票更新，否則看下票的 id 是不是處于 leading 狀态，是則開票
2）OutOfElection 是已經出結果的集合，因為這個選票 n 不是 following 就是 leading，是以放入 OutOfElection，然後根據 OutOfElection 進行判斷自己結果
- 目前選票 n 投票的是自己，并且自己擷取了 OutOfElection 中的過半，那麼開票，變更狀态
- 如果 OutOfElection 中有過半的投票投給了 n, 并且被投票的節點處于 leading 狀态，也屬于 OutOfElection，進行開票
3 如果以上邏輯均未命中，拿出下個選票，繼續循環。
算法精髓
1）節點會随着收到投票的狀态而變更自己的投票結果，即如果有人投票比自身新，那就變票然後再次發聲。
2）在裁定狀态及退出循環的判斷中，隻接收輪次不比自身小的。不僅會判斷
(vote, id, state, round)
中投票者的狀态，也會判斷這個被投票節點的狀态，另外還要滿足過半節點的政策。
3）每個節點會維持倆個狀态集合 ReceivedVotes 和 OutOfElection， ReceivedVotes存放接收到的合法選票，OutOfElection 存放節點已經是 leading 或 following 狀态的選票。這也不難了解，ReceivedVotes 是還沒開票，需要判斷，OutOfElection 則是已經大選已經接收了，明确的狀态了。
4）總有一個節點會在 election 選主狀态先拿到過半節點，判定自己就是 leading 狀态，然後廣播給其其它節點，其它節點收到廣播後進行自身狀态修改。
4 總結
其實 ZAB 的哲學和 Paxos 一緻，即限制未來就是更好的選擇。
就如德州撲克一樣，随着不斷開牌，勝算小的選手就會不斷放棄自己的 call，最終隻剩一個赢家拿走所有籌碼。
🌲🌲🌲 最後，如果大家覺得對你有幫助的話還希望大家動動手指給個免費的一鍵三連~，你的支援是我前進最大的動力。