17 張圖帶你搞懂 ZooKeeper 一致性原理！
作者 | Sunddenly
來源 | http://dwz.date/e5a6
01
ZooKeeper 的實現
1.1 ZooKeeper 處理單點故障
我們知道可以通過 ZooKeeper 對分佈式系統進行 Master 選舉，來解決分佈式系統的**單點故障，**如圖所示。
圖 1.1 ZooKeeper 解決單點故障
那麼我們繼續分析一下，ZooKeeper 通過 Master 選舉來幫助分佈式系統解決單點故障，保證該系統中每時每刻只有一個 Master 爲分佈式系統提供服務。也就是說分佈式的單點問題交給了 ZooKeeper 來處理，不知道大家此時有沒有發現一個問題——"故障轉移到了 ZooKeeper 身上"。大家看一下圖就會發現，如果我們的 ZooKeeper 只用一臺機器來提供服務，若這臺機器掛了，那麼該分佈式系統就直接變成雙 Master 模式了，那麼我們在分佈式系統中引入 ZooKeeper 也就失去了意義。那麼這也就意味着，ZooKeeper 在其實現的過程中要做一些可用性和恢復性的保證。這樣才能讓我們放心的以 ZooKeeper 爲起點來構建我們的分佈式系統，來達到節省成本和減少 bug 的目的。
1.2 ZooKeeper 運行模式
ZooKeeper 服務有兩種不同的運行模式。一種是 " 獨立模式 "(standalone mode)，即只有一個 ZooKeeper 服務器。這種模式較爲簡單，比較適合於測試環境，甚至可以在單元測試中採用，但是不能保證高可用性和恢復性。在生產環境中的 ZooKeeper 通常以 " 複製模式 "(replicated mode) 運行於一個計算機集羣上，這個計算機集羣被稱爲一個 " 集合體 "(ensemble)。
圖 1.2 ZooKeeper 集羣
ZooKeeper 通過複製來實現高可用性，只要集合體中半數以上的機器處於可用狀態，它就能夠提供服務。例如，在一個有 5 個節點的集合體中，每個 Follower 節點的數據都是 Leader 節點數據的副本，也就是說我們的每個節點的數據視圖都是一樣的，這樣就可以有五個節點提供 ZooKeeper 服務。並且集合體中任意 2 臺機器出現故障，都可以保證服務繼續，因爲剩下的 3 臺機器超過了半數。
注意，6 個節點的集合體也只能夠容忍 2 臺機器出現故障，因爲如果 3 臺機器出現故障，剩下的 3 臺機器沒有超過集合體的半數。出於這個原因，一個集合體通常包含奇數臺機器。
從概念上來說，ZooKeeper 它所做的就是確保對 Znode 樹的每一個修改都會被複制到集合體中超過半數的機器上。如果少於半數的機器出現故障，則最少有一臺機器會保存最新的狀態，那麼這臺機器就是我們的 Leader。其餘的副本最終也會更新到這個狀態。如果 Leader 掛了，由於其他機器保存了 Leader 的副本，那就可以從中選出一臺機器作爲新的 Leader 繼續提供服務。
1.3 ZooKeeper 的讀寫機制
ZooKeeper 的核心思想是，提供一個非鎖機制的 Wait Free 的用於分佈式系統同步的核心服務。提供簡單的文件創建、讀寫操作接口，其系統核心本身對文件讀寫並不提供加鎖互斥的服務，但是提供基於版本比對的更新操作，客戶端可以基於此自己實現加鎖邏輯。如下圖 1.3 所示。
圖 1.3 Using versions to prevent inconsistencies due to concurrent updates
(2) ZK 集羣服務
Zookeeper 是一個由多個 Server 組成的集羣，該集羣有一個 Leader，多個 Follower。客戶端可以連接任意 ZooKeeper 服務節點來讀寫數據，如下圖 1.4 所示。
圖 1.4 ZooKeeper 集羣服務
ZK 集羣中每個 Server，都保存一份數據副本。Zookeeper 使用簡單的同步策略，通過以下兩條基本保證來實現數據的一致性：
① 全局串行化所有的寫操作
② 保證同一客戶端的指令被 FIFO 執行（以及消息通知的 FIFO）
所有的讀請求由 Zk Server 本地響應，所有的更新請求將轉發給 Leader，由 Leader 實施。
(3) ZK 組件
ZK 組件，如圖 1.5 所示。ZK 組件除了請求處理器（Request Processor）以外，組成 ZK 服務的每一個 Server 會複製這些組件的副本。
圖 ZooKeeper 組件圖
ReplicatedDatabase 是一個內存數據庫，它包含了整個 Data Tree。爲了恢復，更新會被記錄到磁盤，並且寫在被應用到內存數據庫之前，先被序列化到磁盤。
每一個 ZK Server，可服務於多個 Client。Client 可以連接到一臺 Server，來提交請求。讀請求，由每臺 Server 數據庫的本地副本來進行服務。改變服務器的狀態的寫請求，需要通過一致性協議來處理。
作爲一致性協議的一部分，來自 Client 的所有寫請求，都要被轉發到一個單獨的 Server，稱作 Leader。ZK 集羣中其他 Server 稱作 Follower，負責接收 Leader 發來的提議消息，並且對消息轉發達成一致。消息層處理 leader 失效，同步 Followers 和 Leader。
ZooKeeper 使用自定義的原子性消息協議。由於消息傳送層是原子性的，ZooKeeper 能夠保證本地副本不產生分歧。當 leader 收到一個寫請求，它會計算出當寫操作完成後系統將會是什麼狀態，接着將之轉變爲一個捕獲狀態的事務。
(4) ZK 性能
ZooKeeper 被應用程序廣泛使用，並有數以千計的客戶端同時的訪問它，所以我們需要高吞吐量。我們爲 ZooKeeper 設計的工作負載的讀寫比例是 2：1 以上。然而我們發現，ZooKeeper 的高寫入吞吐量，也允許它被用於一些寫佔主導的工作負載。ZooKeeper 通過每臺 Server 上的本地 ZK 的狀態副本，來提供高讀取吞吐量。因此，容錯性和讀吞吐量是以添加到該服務的服務器數量爲尺度。寫吞吐量並不以添加到該服務的機器數量爲尺度。
例如，在它的誕生地 Yahoo 公司，對於寫佔主導的工作負載來說，ZooKeeper 的基準吞吐量已經超過每秒 10000 個操作；對於常規的以讀爲主導的工作負載來說，吞吐量更是高出了好幾倍。
經過上面的分析，我們知道要保證 ZooKeeper 服務的高可用性就需要採用分佈式模式，來冗餘數據寫多份，寫多份帶來一致性問題，一致性問題又會帶來性能問題，那麼就此陷入了無解的死循環。那麼在這，就涉及到了我們分佈式領域的著名的 CAP 理論，在這就簡單的給大家介紹一下，關於 CAP 的詳細內容大家可以網上查閱。
2.1 CAP 理論
(1) 理論概述
分佈式領域中存在 CAP 理論：
① C：Consistency，一致性，數據一致更新，所有數據變動都是同步的。
② A：Availability，可用性，系統具有好的響應性能。
③ P：Partition tolerance，分區容錯性。以實際效果而言，分區相當於對通信的時限要求。系統如果不能在時限內達成數據一致性，就意味着發生了分區的情況，必須就當前操作在 C 和 A 之間做出選擇，也就是說無論任何消息丟失，系統都可用。
該理論已被證明：任何分佈式系統只可同時滿足兩點，無法三者兼顧。因此，將精力浪費在思考如何設計能滿足三者的完美系統上是愚鈍的，應該根據應用場景進行適當取捨。
(2) 一致性分類
一致性是指從系統外部讀取系統內部的數據時，在一定約束條件下相同，即數據變動在系統內部各節點應該是同步的。根據一致性的強弱程度不同，可以將一致性級別分爲如下幾種：
① 強一致性（strong consistency）。任何時刻，任何用戶都能讀取到最近一次成功更新的數據。
② 單調一致性（monotonic consistency）。任何時刻，任何用戶一旦讀到某個數據在某次更新後的值，那麼就不會再讀到比這個值更舊的值。也就是說，可獲取的數據順序必是單調遞增的。
③ 會話一致性（session consistency）。任何用戶在某次會話中，一旦讀到某個數據在某次更新後的值，那麼在本次會話中就不會再讀到比這個值更舊的值。會話一致性是在單調一致性的基礎上進一步放鬆約束，只保證單個用戶單個會話內的單調性，在不同用戶或同一用戶不同會話間則沒有保障。
④ 最終一致性（eventual consistency）。用戶只能讀到某次更新後的值，但系統保證數據將最終達到完全一致的狀態，只是所需時間不能保障。
⑤ 弱一致性（weak consistency）。用戶無法在確定時間內讀到最新更新的值。
2.2 ZooKeeper 與 CAP 理論
我們知道 ZooKeeper 也是一種分佈式系統，它在一致性上有人認爲它提供的是一種強一致性的服務（通過 sync 操作），也有人認爲是單調一致性（更新時的大多說概念），還有人爲是最終一致性（順序一致性），反正各有各的道理這裏就不在爭辯了。然後它在分區容錯性和可用性上做了一定折中，這和 CAP 理論是吻合的。ZooKeeper 從以下幾點保證了數據的一致性
① 順序一致性
來自任意特定客戶端的更新都會按其發送順序被提交。也就是說，如果一個客戶端將 Znode z 的值更新爲 a，在之後的操作中，它又將 z 的值更新爲 b，則沒有客戶端能夠在看到 z 的值是 b 之後再看到值 a（如果沒有其他對 z 的更新）。
② 原子性
每個更新要麼成功，要麼失敗。這意味着如果一個更新失敗，則不會有客戶端會看到這個更新的結果。
④ 持久性
一個更新一旦成功，其結果就會持久存在並且不會被撤銷。這表明更新不會受到服務器故障的影響。
03
ZooKeeper 原理
3.1 原理概述
Zookeeper 的核心是原子廣播機制，這個機制保證了各個 server 之間的同步。實現這個機制的協議叫做 Zab 協議。Zab 協議有兩種模式，它們分別是恢復模式和廣播模式。
(1) 恢復模式
當服務啓動或者在領導者崩潰後，Zab 就進入了恢復模式，當領導者被選舉出來，且大多數 server 完成了和 leader 的狀態同步以後，恢復模式就結束了。狀態同步保證了 leader 和 server 具有相同的系統狀態。
(2) 廣播模式
一旦 Leader 已經和多數的 Follower 進行了狀態同步後，他就可以開始廣播消息了，即進入廣播狀態。這時候當一個 Server 加入 ZooKeeper 服務中，它會在恢復模式下啓動，發現 Leader，並和 Leader 進行狀態同步。待到同步結束，它也參與消息廣播。ZooKeeper 服務一直維持在 Broadcast 狀態，直到 Leader 崩潰了或者 Leader 失去了大部分的 Followers 支持。
Broadcast 模式極其類似於分佈式事務中的 2pc（two-phrase commit 兩階段提交）：即 Leader 提起一個決議，由 Followers 進行投票，Leader 對投票結果進行計算決定是否通過該決議，如果通過執行該決議（事務），否則什麼也不做。
圖 3.1 兩階段提交
在廣播模式 ZooKeeper Server 會接受 Client 請求，所有的寫請求都被轉發給領導者，再由領導者將更新廣播給跟隨者。當半數以上的跟隨者已經將修改持久化之後，領導者纔會提交這個更新，然後客戶端纔會收到一個更新成功的響應。這個用來達成共識的協議被設計成具有原子性，因此每個修改要麼成功要麼失敗。
圖 3.2 ZooKeeper 數據流動圖
3.2 Zab 協議詳解
3.2.1 廣播模式
廣播模式類似一個簡單的兩階段提交：Leader 發起一個請求，收集選票，並且最終提交，圖 3.3 演示了我們協議的消息流程。我們可以簡化該兩階段提交協議，因爲我們並沒有 "aborts" 的情況。followers 要麼確認 Leader 的 Propose，要麼丟棄該 Leader 的 Propose。沒有 "aborts" 意味着，只要有指定數量的機器確認了該 Propose，而不是等待所有機器的迴應。
圖 3.3 The flow of message with protocol
廣播協議在所有的通訊過程中使用 TCP 的 FIFO 信道，通過使用該信道，使保持有序性變得非常的容易。通過 FIFO 信道，消息被有序的 deliver。只要收到的消息一被處理，其順序就會被保存下來。
Leader 會廣播已經被 deliver 的 Proposal 消息。在發出一個 Proposal 消息前，Leader 會分配給 Proposal 一個單調遞增的唯一 id，稱之爲 zxid。因爲 Zab 保證了因果有序，所以遞交的消息也會按照 zxid 進行排序。廣播是把 Proposal 封裝到消息當中，並添加到指向 Follower 的輸出隊列中，通過 FIFO 信道發送到 Follower。當 Follower 收到一個 Proposal 時，會將其寫入到磁盤，可以的話進行批量寫入。一旦被寫入到磁盤媒介當中，Follower 就會發送一個 ACK 給 Leader。當 Leader 收到了指定數量的 ACK 時，Leader 將廣播 commit 消息並在本地 deliver 該消息。當收到 Leader 發來 commit 消息時，Follower 也會遞交該消息。
需要注意的是， 該簡化的兩階段提交自身並不能解決 Leader 故障，所以我們 添加恢復模式來解決 Leader 故障。
3.2.2 恢復模式
(1) 恢復階段概述
正常工作時 Zab 協議會一直處於廣播模式，直到 Leader 故障或失去了指定數量的 Followers。爲了保證進度，恢復過程中必須選舉出一個新 Leader，並且最終讓所有的 Server 擁有一個正確的狀態。對於 Leader 選舉，需要一個能夠成功高几率的保證存活的算法。Leader 選舉協議，不僅能夠讓一個 Leader 得知它是 leader，並且有指定數量的 Follower 同意該決定。如果 Leader 選舉階段發生錯誤，那麼 Servers 將不會取得進展。最終會發生超時，重新進行 Leader 選舉。在我們的實現中，Leader 選舉有兩種不同的實現方式。如果有指定數量的 Server 正常運行，快速選舉的完成只需要幾百毫秒。
(2) 恢復階段的保證
該恢復過程的複雜部分是在一個給定的時間內，提議衝突的絕對數量。最大數量衝突提議是一個可配置的選項，但是默認是 1000。爲了使該協議能夠即使在 Leader 故障的情況下也能正常運作。我們需要做出兩條具體的保證：
① 我們絕不能遺忘已經被 deliver 的消息，若一條消息在一臺機器上被 deliver，那麼該消息必須將在每臺機器上 deliver。
② 我們必須丟棄已經被 skip 的消息。
(3) 保證示例
第一條：
若一條消息在一臺機器上被 deliver，那麼該消息必須將在每臺機器上 deliver，即使那臺機器故障了。例如，出現了這樣一種情況：Leader 發送了 commit 消息，但在該 commit 消息到達其他任何機器之前，Leader 發生了故障。也就是說，只有 Leader 自己收到了 commit 消息。如圖 3.4 中的 C2。
圖 3.4 The flow of message with protocol
圖 3.4 是 "第一條保證"（deliver 消息不能忘記）的一個示例。在該圖中 Server1 是一個 **Leader，**我們用 L1 表示，Server2 和 Server3 爲 Follower。首先 Leader 發起了兩個 Proposal，P1 和 P2，並將 P1、P2 發送給了 Server1 和 Server2。然後 Leader 對 P1 發起了 Commit 即 C1，之後又發起了一個 Proposal 即 P3，再後來又對 P2 發起了 commit 即 C2，就在此時我們的 Leader 掛了。那麼這時候，P3 和 C2 這兩個消息只有 Leader 自己收到了。
因爲 Leader 已經 deliver 了該 C2 消息，client 能夠在消息中看到該事務的結果。所以該事務必須能夠在其他所有的 Server 中 deliver，最終使得 client 看到了一個一致性的服務視圖。
第二條：
**一個被 skip 的消息，必須仍然需要被 skip。例如，發生了這樣一種情況：**Leader 發送了 propose 消息，但在該 propose 消息到達其他任何機器之前，Leader 發生了故障。也就是說，只有 Leader 自己收到了 propose 消息。如圖 3.4 中的 P3 所示。
在圖 3.4 中沒有任何一個 server 能夠看到 3 號提議，所以在圖 3.5 中當 server 1 恢復時他需要在系統恢復時丟棄三號提議 P3。
圖 3.5
在圖 3.5 是 "第二條保證"（skip 消息必須被丟棄）的一個示例。Server1 掛掉以後，Server3 被選舉爲 Leader，我們用 L2 表示。L2 中還有未被 deliver 的消息 P1、P2，所以，L2 在發出新提議 P10000001、P10000002 之前，L2 先將 P1、P2 兩個消息 deliver。因此，L2 先發出了兩個 commit 消息 C1、C2，之後 L2 才發出了新的提議 P10000001 和 P10000002。
如果 Server1 恢復之後再次成爲了 Leader，此時再次將 P3 在 P10000001 和 P10000002 之後 deliver，那麼將違背順序性的保障。
(4) 保證的實現
如果 Leader 選舉協議保證了新 Leader 在 Quorum Server 中具有最高的提議編號，即 Zxid 最高。那麼新選舉出來的 leader 將具有所有已 deliver 的消息。新選舉出來的 Leader，在提出一個新消息之前，首先要保證事務日誌中的所有消息都由 Quorum Follower 已 Propose 並 deliver。需要注意的是，我們可以讓新 Leader 成爲一個用最高 zxid 來處理事務的 server，來作爲一個優化。這樣，作爲新被選舉出來的 Leader，就不必去從一組 Followers 中找出包含最高 zxid 的 Followers 和獲取丟失的事務。
① 第一條
所有的正確啓動的 Servers，將會成爲 Leader 或者跟隨一個 Leader。Leader 能夠確保它的 Followers 看到所有的提議，並 deliver 所有已經 deliver 的消息。通過將新連接上的 Follower 所沒有見過的所有 PROPOSAL 進行排隊，並之後對該 Proposals 的 COMMIT 消息進行排隊，直到最後一個 COMMIT 消息。在所有這樣的消息已經排好隊之後，Leader 將會把 Follower 加入到廣播列表，以便今後的提議和確認。這一條是爲了保證一致性，因爲如果一條消息 P 已經在舊 Leader-Server1 中 deliver 了，即使它剛剛將消息 P deliver 之後就掛了，但是當舊 Leader-Server1 重啓恢復之後，我們的 Client 就可以從該 Server 中看到該消息 P deliver 的事務，所以爲了保證每一個 client 都能看到一個一致性的視圖，我們需要將該消息在每個 Server 上 deliver。
② 第二條
skip 已經 Propose，但不能 deliver 的消息，處理起來也比較簡單。在我們的實現中，Zxid 是由 64 位數字組成的，低 32 位用作簡單計數器。高 32 位是一個 epoch。每當新 Leader 接管它時，將獲取日誌中 Zxid 最大的 epoch，新 Leader Zxid 的 epoch 位設置爲 epoch+1，counter 位設置 0。用 epoch 來標記領導關係的改變, 並要求 Quorum Servers 通過 epoch 來識別該 leader，避免了多個 Leader 用同一個 Zxid 發佈不同的提議。
這個方案的一個優點就是，我們可以 skip 一個失敗的領導者的實例，從而加速並簡化了恢復過程。如果一臺宕機的 Server 重啓，並帶有未發佈的 Proposal，那麼先前的未發佈的所有提議將永不會被 deliver。並且它不能夠成爲一個新 leader，因爲任何一種可能的 Quorum Servers ，都會有一個 Server 其 Proposal 來自與一個新 epoch 因此它具有一個較高的 zxid。當 Server 以 Follower 的身份連接，領導者檢查自身最後提交的提議，該提議的 epoch 爲 Follower 的最新提議的 epoch（也就是圖 3.5 中新 Leader-Server2 中 deliver 的 C2 提議），並告訴 Follower 截斷事務日誌直到該 epoch 在新 Leader 中 deliver 的最後的 Proposal 即 C2。在圖 3.5 中，當舊 Leader-Server1 連接到了新 leader-Server2，leader 將告訴他從事務日誌中清除 3 號提議 P3，具體點就是清除 P2 之後的所有提議，因爲 P2 之後的所有提議只有舊 Leader-Server1 知道，其他 Server 不知道。
(5) Paxos 與 Zab
① Paxos 一致性
Paxos 的一致性不能達到 ZooKeeper 的要求，我們可以下面一個例子。我們假設 ZK 集羣由三臺機器組成，Server1、Server2、Server3。Server1 爲 Leader，他生成了三條 Proposal，P1、P2、P3。但是在發送完 P1 之後，Server1 就掛了。如下圖 3.6 所示。
圖 3.6 Server1 爲 Leader
Server1 掛掉之後，Server3 被選舉成爲 Leader，因爲在 Server3 裏只有一條 Proposal—P1。所以，Server3 在 P1 的基礎之上又發出了一條新 Proposal—P2＇，P2＇的 Zxid 爲 02。如下圖 3.7 所示。
圖 3.7 Server2 成爲 Leader
Server2 發送完 P2＇之後，它也掛了。此時 Server1 已經重啓恢復，並再次成爲了 Leader。那麼，Server1 將發送還沒有被 deliver 的 Proposal—P2 和 P3。由於 Follower-Server2 中 **P2＇**的 Zxid 爲 02 和 Leader-Server1 中 P2 的 Zxid 相等，所以 P2 會被拒絕。而 P3，將會被 Server2 接受。如圖 3.8 所示。
圖 3.8 Server1 再次成爲 Leader
我們分析一下 Follower-Server2 中的 Proposal，由於 P2'將 P2 的內容覆蓋了。所以導致，Server2 中的 Proposal-P3 無法生效，因爲他的父節點並不存在。
② Zab 一致性
首先來分析一下，上面的示例中爲什麼不滿足 ZooKeeper 需求。ZooKeeper 是一個樹形結構，很多操作都要先檢查才能確定能不能執行，比如，在圖 3.8 中 Server2 有三條 Proposal。P1 的事務是創建節點 "/zk"，**P2'**是創建節點 "/c"，而 P3 是創建節點 "/a/b", 由於 "/a" 還沒建，創建 "a/b" 就搞不定了。那麼，我們就能從此看出 Paxos 的一致性達不到 ZooKeeper 一致性的要求。
爲了達到 ZooKeeper 所需要的一致性，ZooKeeper 採用了 Zab 協議。Zab 做了如下幾條保證，來達到 ZooKeeper 要求的一致性。
(a) Zab 要保證同一個 leader 的發起的事務要按順序被 apply，同時還要保證只有先前的 leader 的所有事務都被 apply 之後，新選的 leader 才能在發起事務。
(b) 一些已經 Skip 的消息，需要仍然被 Skip。
我想對於第一條保證大家都能理解，它主要是爲了保證每個 Server 的數據視圖的一致性。我重點解釋一下第二條，它是如何實現。爲了能夠實現，Skip 已經被 skip 的消息。我們在 Zxid 中引入了 epoch，如下圖所示。每當 Leader 發生變換時，epoch 位就加 1，counter 位置 0。
圖 3.9 Zxid
我們繼續使用上面的例子，看一下他是如何實現 Zab 的第二條保證的。我們假設 ZK 集羣由三臺機器組成，Server1、Server2、Server3。Server1 爲 Leader，他生成了三條 Proposal，P1、P2、P3。但是在發送完 P1 之後，Server1 就掛了。如下圖 3.10 所示。
圖 3.10 Server1 爲 Leader
Server1 掛掉之後，Server3 被選舉成爲 Leader，因爲在 Server3 裏只有一條 Proposal—P1。所以，Server3 在 P1 的基礎之上又發出了一條新 Proposal—P2＇，由於 Leader 發生了變換，epoch 要加 1，所以 epoch 由原來的 0 變成了 1，而 counter 要置 0。那麼，P2＇的 Zxid 爲 10。如下圖 3.11 所示。
圖 3.11 Server3 爲 Leader
Server2 發送完 P2＇之後，它也掛了。此時 Server1 已經重啓恢復，並再次成爲了 Leader。那麼，Server1 將發送還沒有被 deliver 的 Proposal—P2 和 P3。由於 Server2 中 **P2＇**的 Zxid 爲 **10，**而 Leader-Server1 中 P2 和 P3 的 Zxid 分別爲 02 和 03，**P2＇**的 epoch 位高於 P2 和 P3。所以此時 Leader-Server1 的 P2 和 P3 都會被拒絕, 那麼我們 Zab 的第二條保證也就實現了。如圖 3.12 所示。
圖 3.12 Server1 再次成爲 Leader
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zazlh8e3rywnSTLNGVOgAw