iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
0

前言

這是我們最後一個要介紹的共識演算法了,也就是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幾乎一樣。

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

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

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

  1. 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的系統架構跟我們可以怎麼應用。


上一篇
Day 16 - 分散式系統溝通的方法 - RPC
下一篇
Day 18 - Google Distributed Lock Service - Chubby(上)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言