前言

這是我們最後一個要介紹的共識演算法了，也就是Zookeeper使用的ZAB共識演算法。接下來我們會從Zookeeper開始，往上以系統或是實例角度介紹。

Zookeeper Atomic Broadcast (ZAB)

首先，先介紹什麼是Atomic Broadcast，其實他從本質上等價於Consensus，每一次有更新，就必須廣播到所有的replica servers上。而Atomic Broadcast的要求為

1. Validity: 如果一個正常的server廣播了一個訊息，則所有的servers最終都會收到著訊息
2. Uniform Agreement: 反過來說，如果一個server收到且commit了一個訊息，最終所有的servers一定也commit了這個訊息，想想Raft那時的正確性證明
3. Uniform Integrity: 每一個訊息只會被接收到一次，不會重複接收，且收到的訊息一定是到目前為止最新一次的broadcast
4. Uniform Total Order: 跟Raft的commit順序保證一樣，如果一個server的commit訊息順序是ABC，則所有的servers一定也commit了順序ABC的訊息。

因此Atomic Broadcast的做法當然也是Strong Consistency。

可以看到它的要求其實跟Paxos/Raft等共識演算法沒有什麼不同，跟Raft一樣要求了Total Order，所以我們稱他跟共識演算法等價。當然也因此有一樣的要求，也就是必須有 「過半數」 以上的servers可以運作。

其實如果一個系統每一次的更新值都執行一次Raft共識演算法，利用log方法記錄commit log的順序，每一個server都agree同一個順序的log，然後給Replicate State Machine執行，其實也可以說是一種Atomic Broadcast的行為。

接下來介紹Zookeeper Atomic Broadcast你就會發現其實跟Raft超像。

角色狀態

如同Raft，ZAB也定義了三個角色狀態 (幾乎可以一一對應)

• Looking: 系統剛啟動時，或者Leader失效後process進入選舉狀態

• Following: 非Leader且不是在選舉狀態的process就會是在Follower狀態，同步Leader的資料

• Leading: Leader，系統中只會存在一個Leader

階段

1. Election:
   基本上跟Raft一樣，當leader失效 (Raft使用Hearbeat確認Leader) 或是系統剛啟動時，進入選舉階段。就像Raft的Leader要求一樣，ZAB要求選出來的Leader其LastZXID (類似term, index)一定要是最新的，因此選舉過程中會比較每一個Follower的ZXID
   • 每一個Follower進入選舉階段會向別的Follower提出Vote請求
   • 只投LastZXID比自己大的，否則拒絕
   • 當某個process收到 「過半數」 的票及當選為Leader

恩...跟Raft幾乎一樣。

2. Discovery:
   在Raft中是Leader發送Heartbeat向大家宣告自己是Leader順便Append log，在ZAB中反過來是Follower要向Leader發送FollwerInfo，一樣包含目前的任期稱為epoch。

3. Broadcast:
   這邊保證一致性的方法同Paxos與2PC，Leader發送Proposal與Commit，一樣過半數回復則可以commit，因為只有一個Leader所以不用像Paxos一樣要比Proposal Number。另外因為只有一個Leader，所以Client更新的操作只能藉由Leader，而讀取操作則可以透過Follower。

特別注意的是，這邊的通訊方法更強調了保證順序性，因此使用TCP來保證訊息的順序。而接著採用Raft的(term,index)概念，採用ZXID來綁定每一個Proposal保證順序，跟Raft一樣這個ZXID是全域共識的。

4. Recovery:

還記得Raft的

AppendEntries Consistency Check:
Followers 一定要 擁有同樣的前一個entry的(index, term)才會儲存最新的log entry，否則就不接受該RPC

因此leader不斷往回找適當nextIndex
(a)最後會從index5開始發送
(b)最後會從index4開始發送

這邊一樣利用ZXID來判斷多出來的跟少掉的，同步完成後，此Follower會被記錄到Leader上，告訴Client此Follower的資料是最新的可以從上面讀取。

如果Follower發現Leader的epoch(Raft的term)比較小，表示Leader比較舊，則馬上轉為進入選舉模式。

總結

以上大概就是ZAB的介紹，可以看到它其實融合了Paxos與Raft的做法，保障了logs的順序性跟一致性。

接下來我們來介紹一下Zookeeper的系統架構跟我們可以怎麼應用。