Zookeeper 的 ZAB 协议
Zookeeper 的 ZAB 協議
目錄
1. ZAB 協議
ZAB 協議并不像 Paxos 算法那樣，是一種通用的分布式一致性算法，它是一種特別為 Zookeeper 設計的崩潰可恢復的原子廣播算法。
在 Zookeeper 中，主要依賴 ZAB 協議來實現分布式數據一致性，基于該協議，Zookeeper 實現一種主備模式的系統架構來保持集群中各副本之間數據的一致性。具體的，Zookeeper 使用一個單一的主進程來接收并處理客戶端的所有事務請求，并采用 ZAB 是原子廣播協議，將服務器數據的狀態變更以事務 Proposal 的形式廣播到所有的副本進程上去。ZAB 協議的這個主備模型架構保證了同一時刻集群中只能夠有一個主進程來廣播服務器的狀態變更，因此能夠很好地處理客戶端大量的并發請求。另一方面，順序執行的一些狀態變更其前后會存在一定的依賴關系，ZAB 協議必須能夠保證一個全局的變更序列被順序應用，也就是說，ZAB 協議需要保證一個狀態變更已經被處理了，那么其所依賴的狀態變更應該已經提前處理掉了。最后，考慮到主進程在任何時候都有可能出現崩潰退出或重啟現象，因此，ZAB 協議還需要做到在當前主進程出現上述異常情況的時候，依然能夠正常工作。
ZAB 協議的核心是定義了對于那些會改變 Zookeeper 服務器數據狀態的事務請求的處理方式，即：
所有事務請求必須由一個全局唯一的服務器來協調處理，這樣的服務器被稱為 Leader 服務器，而余下的其他服務器則成為 Follower 服務器。Leader 服務器負責將一個客戶端事務請求轉換成一個事務 Proposal（提議），并將該 Proposal 分發給集群中所有的 Follower 服務器。之后 Leader 服務器需要等待所有 Follower 服務器的反饋，一旦超過半數的 Follower 服務器進行了正確的反饋后，Leader 就會再次向所有的 Follower 服務器分發 Commit 消息，要求其將前一個 Proposal 進行提交。
2. ZAB 協議介紹
ZAB 協議包括兩種基本模式，分別是崩潰恢復和消息廣播。當整個服務框架在啟動過程中，或是當 Leader 服務器出現網絡中斷、崩潰退出與重啟等異常情況時，ZAB 協議就會進入恢復模式并選舉產生新的 Leader 服務器。當選舉產生新的 Leader 服務器，同時集群中已經有過半的機器與該 Leader 服務器完成了狀態同步之后，ZAB 協議就會退出恢復模式。其中，所謂的狀態同步是指數據同步，用來保證集群中存在過半的機器能夠和 Leader 服務器的數據狀態保持一致。
當集群中已經有過半的 Follower 服務器完成了和 Leader 服務器狀態同步，那么整個服務框架就可以進入消息廣播模式了。當一臺同樣遵循 ZAB 協議的服務器啟動后加入到集群中，如果此時集群中已經有一個 Leader 服務器在負責進行消息廣播，那么新加入的服務器就會自覺進入數據恢復模式：找到 Leader 所在的服務器，并與其進行數據同步，然后一起參加到消息廣播流程中去。 Zookeeper 設計成只允許唯一的一個 Leader 服務器來進行事務請求的處理。Leader 服務器在接收到客戶端的事務請求后，會生成對應的事務請提案并發起一輪廣播協議；而如果集群中的其他機器接收到客戶端的事務請求，那么這些非 Leader 服務器首先將這個事務請求轉發給 Leader 服務器。
當 Leader 服務器出現崩潰退出或機器重啟，亦或是集群中已經不存在過半的服務器與該 Leader 服務器保持正常通信時，那么在重新開始新一輪的原子廣播事務操作之前，所有進程首先會使用崩潰恢復協議來使彼此達到一個一致的狀態，于是整個 ZAB 流程就會從消息廣播模式進入到崩潰恢復模式。
一個機器要成為新的 Leader，必須獲得過半進程的支持，同時由于每個進程都有會崩潰，因此 ZAB 協議運行過程中，前后出現多個 Leader，并且每個進程也有可能會多次成為 Leader。進入崩潰恢復模式后，只要集群中存在過半的服務器能夠彼此進行正常通信，那么就可以產生一個新的 Leader 并在此進入消息廣播模式。舉個例子來說，一個由 3 臺機器組成的 ZAB 服務，通常由 1 個 Leader，2個 Follower 服務器組成。某一個時刻，假如其中一個 Follower 服務器掛了，整個 ZAB 機器是不會中斷服務的，這是因為 Leader 服務器依然能夠獲得過半機器（包括 Leader 自己）的支持。
接下來重點介紹 ZAB 協議的消息廣播和崩潰恢復過程。
消息廣播
ZAB 協議的消息廣播過程使用的是一個原子廣播協議，類似于一個二階段提交過程。針對客戶端的事務請求，Leader 服務器會為其生產對應的事務 Proposal，并將其發送給集群中其余的機器，然后再分別收集各自的選票，最后進行事務提交，如下圖就是 ZAB 協議消息廣播流程的示意圖。
此處的 ZAB 協議中涉及的二階段提交過程與二階段提交協議略有不同。在 ZAB 協議的二階段提交過程中，移除了中斷邏輯，所有的 Follower 服務器要么正常反饋 Leader 提出的事務 Proposal，要么拋棄 Leader 服務器。同時，ZAB 協議將二階段提交中的中斷邏輯移除意味著我們可以在過半的 Follower 服務器已經反饋 Ack 之后就可以開始提交事務 Proposal了，而不需要等待集群中所有的 Follower 服務器都反饋響應。當然，在這種簡化的二階段提交模型下，是無法處理 Leader 服務器崩潰退出而帶來的數據不一致問題的，因此在 ZAB 協議中添加了另一個模式，即采用崩潰恢復模式來解決這個問題。另外，整個消息廣播協議是基于具有 FIFO 特性的 TCP 協議來進行網絡通信的，因此能夠很容易地保證廣播過程中消息接收與發送的順序性。
在整個消息廣播過程中，Leader 服務器會為每個事務請求生成對應的 Proposal 來進行廣播，并且在廣播事務 Proposal 之前，Leader 服務器會首先為這個事務 Proposal 分配一個全局單調遞增的唯一 ID，我們稱之為事務 ID（ZXID）。由于 ZAB 協議需要保證每一個消息嚴格的因果關系，因此必須將每一個事務 Proposal 按照其 ZXID 的先后順序來進行排序與處理。
具體的，在消息廣播過程中，Leader 服務器會為每一個 Follower 服務器都各自分配一個單獨的隊列，然后將需要廣播的事務 Proposal 依次放入這些隊列中去，并根據 FIFO 策略進行消息發送。每一個 Follower 服務器在接收到這個事務 Proposal 之后，都會首先將其以事務日志的形式寫入到本地磁盤中去，并且在成功寫入后反饋給 Leader 服務器一個 Ack 響應。當 Leader 服務器接收到超過半數 Follower 的 Ack 響應后，就會廣播一個 Commit 消息給所有的 Follower 服務器以通知其進行事務提交，同時 Leader 自身也會完成對事務的提交，而每一個 Follower 服務器在接收到 Commit 消息后，也會完成對事務的提交。
崩潰恢復
ZAB 協議的這個基于原子廣播協議的消息廣播過程，在正常情況下運行非常良好，但是一旦 Leader 服務器出現崩潰，或者說由于網絡原因導致 Leader 服務器失去了與過半 Follower 的聯系，那么就會進入崩潰恢復模式。在 ZAB 協議中，為了保證程序正確運行，整個恢復過程結束后需要選舉初一個新的 Leader 服務器。因此 ZAB 協議需要一個高效且可靠的 Leader 選舉算法，從而確保能夠快速選舉出新的 Leader。同時 Leader 選舉算法不僅僅讓 Leader 自己知道自身已經被選舉為 Leader，同時還需要讓集群中所有的其他機器也能夠快速地感知到選舉產生的新的 Leader 服務器。
基本特性
ZAB 協議規定如果一個事務 Proposal 在一臺機器上被處理成功，那么應該在所有的機器上都被處理成功，哪怕機器出現故障崩潰。接下來我們看看在崩潰恢復過程中，可能會出現的兩個數據不一致的隱患及針對這些情況 ZAB 協議所需要保證的特性。
ZAB 協議確保那些已經在 Leader 提交的事務最終會被所有服務器提交。
ZAB 協議確保丟棄那些只在 Leader 提出/復制，但沒有提交的事務。
如果在崩潰恢復過程中出現一個需要被丟棄的提案，那么在崩潰恢復結束后需要跳過該事務 Proposal，如下圖所示
在上圖所示的集群中，假設初始的 Leader 服務器 Server1 在提出一個事務 Proposal3 之后就崩潰退出了，從而導致集群中的其他服務器都沒有收到這個事務 Proposal。于是，當 Server1 恢復過來再次加入集群中的時候，ZAB 協議需要確保丟棄 Proposal3 這個事務。
結合上面提到的這兩個崩潰恢復過程中需要處理的特殊情況，就決定了 ZAB 協議必須設計這一一個 Leader 選舉算法：能夠確保提交已經被 Leader 提交的事務 Proposal，同時丟棄已經被跳過的事務 Proposal。針對這個要求，如果讓 Leader 選舉算法能夠保證新選舉出來的 Leader 服務器擁有集群中所有機器最高編號（即 ZXID 最大）的事務 Proposal，那么就可以保證這個新選舉出來的 Leader 一定具有所有已經提交的提案。更為重要的是，如果讓具有最高編號事務 Proposal 的機器來成為 Leader，就可以省去 Leader 服務器檢查 Proposal 的提交和丟棄工作的這個步操作了。
數據同步
完成 Leader 選舉之后，在正式開始工作（即接收客戶端的事務請求，然后提出新的提案）之前，Leader 服務器會首先確認事務日志中的所有 Proposal 是否都已經被集群中過半的機器提交了，即是否完成數據同步。下面來看看 ZAB 協議的數據同步過程。
所有正常運行的服務器，要么成為 Leader，要么成為 Follower 并和 Leader 保持同步。Leader 服務器需要確保所有的 Follower 服務器能夠接收到每一條事務 Proposal，并且能夠正確地將所有已經提交了的事務 Proposal 應用到內存數據庫中。具體的，Leader 服務器會為每一個 Follower 服務器都準備一個隊列，并將那些沒有被各 Follower 服務器同步的事務以 Proposal 消息的形式逐個發送給 Follower 服務器，并在每一個 Proposal 消息后面緊接著 Commit 消息，以表示該事務已經被提交。等到 Follower 服務器將所有其尚未同步的事務 Proposal 都從 Leader 服務器上同步過來并成功應用到本地數據庫中后，Leader 服務器就會將該 Follower 服務器加入到真正的可用 Follower列表中，并開始之后的其他流程。
上面講到的是正常情況下的數據同步邏輯，下面來看 ZAB 協議是如何處理那些需要被丟棄的事務 Proposal 的。在 ZAB 協議的事務編號 ZXID 設計中，ZXID 是一個 64 位的數字，其中低 32 位可以看做是一個簡單的單調遞增的計數器，針對客戶端的每一個事務請求， Leader 服務器在產生一個新的事務 Proposal 的時候，都會對該計數器進行加 1 操作；而高 32 位則代表了 Leader 周期的 epoch 編號每當選舉產生一個新的 Leader 服務器，就會從這個 Leader 服務器上取出其本地日志中最大事務 Proposal 的 ZXID，并從該 ZXID 中解析出對應的 epoch 值，然后再對其進行加 1 操作，之后就會以此編號作為新的 epoch，并將低 32 位從位置 0 來開始生成新的 ZXID。ZAB 協議中的這一通過 epoch 編號來區別 Leader 周期編號的策略，能夠有效地避免不同 Leader 服務器錯誤地使用相同的 ZXID 編號提出不一樣的事務 Proposal 的異常情況，這對于識別在 Leader 崩潰恢復前后生成的 Proposal 非常有幫助，大大簡化和提升了數據恢復流程。
基于這樣的策略，當一個包含了上一個 Leader 周期中尚未提交過的事務 Proposal 的服務器啟動時，其肯定無法成為 Leader，原因很簡單，因為當前集群中一定包含一個 Quorum 集合，該集合中的機器一定包含了更高 epoch 事務 Proposal，因此這臺機器的事務 Proposal 肯定不是最高，也就無法成為 Leader。當這臺機器加入集群中，以 Follower 角色連接上 Leader 服務器之后，Leader 服務器會根據自己服務器上最后被提交的 Proposal 來和 Follower 服務器的 Proposal 進行比對，比對結果當然是 Leader 會要求 Follower 進行一個回退操作——回退到一個確實已經被集群過半機器提交的最新的事務 Proposal。舉個例子來說，在上圖，當 Server1 連接上 Leader 后，Leader 要求 Server1 去除 P3。
3. ZAB 協議內部原理
運行分析
在 ZAB 協議的設計中，每一個進程都有可能處于以下三種狀態之一。
- LOOKING：Leader 選舉階段
- FOLLOWING：Follower 服務器和 Leader 保證同步狀態
- LEADING：Leader 服務器作為主進程領到狀態。
組成 ZAB 協議的所有進程啟動時，其初始狀態都是 LOOKING 狀態，此時進程組中不存在 Leader。所有處于這種狀態的進程，都會試圖去選舉出一個新的 Leader。隨后，如果進程發現已經選舉出新的 Leader，那么它就會馬上切換到 FOLLOWING 狀態，并開始和 Leader 保持同步。這里，我們將處于 FOLLOWING 狀態的進程稱為 Follower，將處于 LEADING 狀態的進程稱為 Leader。考慮到 Leader 隨時會掛掉，當檢測出 Leader 崩潰或者放棄了領到地位時，其余的 Follower 進程就會轉換到 LOOKING 狀態，并開始新一輪的 Leader 選舉。因此在 ZAB 協議運行過程中，每個進程都會在 LEADING,FOLLOWING 和 LOOKING 狀態之間切換。
Leader 選舉過程發生在前兩個階段。圖 4-5 展示了一次 Leader 選舉過程中，各進程之間的消息發送與接收情況。需要注意的是，只有在完成了階段二，即完成各進程之間的數據同步之后，準 Leader 進程才能真正成為新的主進程周期中的 Leader。具體的，我們將一個可用的 Leader 定義如下：
完成 Leader 選舉以及數據同步之后，ZAB 協議就進入原子廣播階段，在這一階段中，Leader 會以隊列的形式為每一個與自己保持同步的 Follower 創建一個操作隊列。同一時刻，一個 Follower 只能和一個 Leader 保持同步，Leader 進程與所有的 Follower 進程之間都通過心跳機制來感知彼此的情況。如果 Leader 能夠在超時時間內正常收到心跳檢測，那么 Follower 就會一直與該 Leader 保持連接。而如果指定的超時時間內 Leader 無法從過半的 Follower 進程那接收到心跳檢測，或者是 TCP 連接本身斷了，那么 Leader 就會終止對當前周期的領到，并切換到 LOOKING 狀態，所有的 Follower 也會選擇放棄這個 Leader，同時轉換到 LOOKING 狀態。之后，所有的進程就會開始新一輪的 Leader 選舉，并在選舉新的 Leader 之后開始新一輪的主進程周期。
4. ZAB 與 Paxos 算法的聯系與區別
ZAB 協議并不是 Paxos 算法的一個經典實現，在講解 ZAB 和 Paxos 之間的區別之前，首先來看下兩種的聯系。
- 兩者都存在一個類似于 Leader 進程的角色，由其負責協調多個 Follower 進程運行。
- Leader 進程都會等待超過半數的 Follower 做出正確的反饋后，才會將一個提案進程提交。
- 在 ZAB 協議中，每個 Proposal 中都包含了一個 epoch值，用愛來代表當前 Leader 周期，在 Paxos算法中，同樣存在這樣的一個標識，只是名字變成了 Ballot。
在 Paxos 算法中，一個新選舉產生的主進程會進行兩個階段的工作。第一階段被稱為讀階段，在這個階段，這個新的主進程會通過和所有的其他進程進行通信的方式來收集上一個主進程提出的提案，并將它們提交。第二階段稱為寫階段，在這個階段，當前主進程開始提出自己的提案。在 Paxos 算法設計的基礎上，ZAB 協議額外添加了一個同步階段，ZAB 協議也存在一個和 Paxos 算法中的讀階段非常類似的過程，稱為發現（Discovery）階段。在同步階段，新的 Leader 會確保存在過半的 Follower 已經提交了之前 Leader 周期中所有事物 Proposal。這一同步階段的引入，能夠有效地保證 Leader 在新的周期中提出事物 Proposal 之前，所有的進程都已經完成了對之前所有事物 Proposal 的提交。一旦完成同步階段后，那么 ZAB 就會執行和 Paxos 算法類似的寫階段。
總是來講，ZAB 協議和 Paxos 算法的本質區別在于，兩者的設計目標不太一樣。ZAB 協議主要用來構建一個高可用的分布式數據主備系統，例如 Zookeeper，而 Paxos 算法則用來構建一個分布式的一致性狀態機系統。
總結
以上是生活随笔為你收集整理的Zookeeper 的 ZAB 协议的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2PC和3PC协议
- 下一篇： LeetCode——双指针