Apache ZooKeeper設計理念和數據結構的研究

陳 濤，索海燕

（1.畢馬威信息技術服務（南京）有限公司，南京 210003；2.南京醫科大學第一附屬醫院（江蘇省人民醫院）信息處，南京 210096）

0 引言

在傳統的計算機行業中，開發人員通常擅長開發單機程序，卻很難高效地開發出多個獨立程序協同工作功能。這是因為開發這種協同技術是非常困難的，很容易導致開發者投入大量的時間考慮協同工作的業務邏輯，而沒有時間更好地處理并實現應用程序的業務邏輯。

Apache ZooKeeper 是基于分布式計算的核心概念設計的，中心化的管理方式，提供了注冊中心和配置中心，旨在解決分布式框架數據一致性的難題。分布式系統的核心要素就是構建中心化平臺，集群中每個子節點都需要通過中心化平臺保障數據的最終一致性。ZooKeeper 一詞的本意是“動物園管理者”，原因是Apache基金會有多個以動物名稱命名的框架，這些框架都需要中心化服務。ZooKeeper 最初由知名互聯網公司雅虎創建，該項目最早起源于雅虎研究院的一個研究小組。當時雅虎研究人員發現，雅虎內部很多大型系統都需要依賴一個分布式協調系統，但是這些系統存在分布式單點問題。開發人員嘗試開發了一個無單點問題的通用分布式協調框架，利用該框架后業務開發人員可以將精力全部集中在處理業務邏輯上。本文深入研究ZooKeeper內核數據結構的原理。

1 ZooKeeper設計理念

分布式領域有一個著名的“拜占庭將軍問題”［1］，它是由Lamport 等人在1982 年提出的。“拜占庭將軍問題”描述了這樣一個場景：拜占庭帝國有許多支軍隊，不同軍隊的將軍需要共同制定一個統一的軍事計劃，用于做出進攻或者撤退的決定。這些將軍因為地理隔離原因，需要依賴通信員進行通信。但是，通信員之中可能會存在叛徒，這些通信員叛徒可以任意篡改軍事信息，從而欺騙將軍。

“拜占庭將軍問題”在分布式計算領域引發了探討［2］。從理論上來說，在分布式計算領域，試圖在異步系統不可靠通道上達到一致性狀態是不可能的。通常在對一致性的研究過程中，都需要一個前提假設：通信通道是可靠的。但在實際應用中，網絡波動和硬件故障很容易造成消息不完整，或被惡意程序篡改。為了保障消息的最終一致性，學者們提出了多個定律或理論。

分布式領域有一個很著名的CAP 定律［3］：一致性（consistency）、可用性（availability）和分區容忍性（partition-tolerance）。任何一個系統都不能同時滿足這三個要求。對于網絡分區（network-partition），為了避免腦裂（split-brain）問題，即從節點無法與群首節點通信時，與第二個群首節點建立主從關系。ZooKeeper 在腦裂場景下，從節點為只讀狀態，從而保證不會產生多個主從關系集群。ZooKeeper 的設計理念可以保證一致性和可用性。

此外分布式領域還有一個BASE 理論［4］，它是基本可用（basically available）、軟狀態（soft state）和最終一致性（eventually consistent）的簡寫。核心思想是即使無法做到實時一致性（強一致性），也能夠采用一定的同步機制來保證系統最終達到一致性的效果。這也是對CAP 定律一致性和可用性進行權衡的結果［5］。ZooKeeper 巧妙地使用了一種稱為Zookeeper 原子廣播（Zoo?keeper atomic broadcast，ZAB）的協議保障數據的最終一致性，使得其成為分布式系統的奠基石。

ZooKeeper 集群采用了中心化設計理念和最終一致性算法，本質上和分布式數據存儲系統原理相似。其數據結構是模仿文件系統設計的，數據結構是一個帶有根節點的目錄樹。其中每個節點被稱為Znode，每個Znode 都對應著唯一的路徑，并默認能夠存儲大小為1MB 的二進制數據。下面以Apache Dubbo 對接ZooKeeper 生成的服務提供目錄為例展示中心化設計理念，如圖1所示。

圖1 Apache Dubbo生成的服務提供目錄

如圖1所示，Apache Dubbo在啟動時會根據用戶配置在ZooKeeper注冊中心創建四個Znode：/providers、/consumers、/routers 和/configurators。每個節點的路徑由父節點和服務名組成，例如，第一行的/providers 節點對應的路徑是/dubbo/ser?vice1/providers。

采用中心化設計理念的分布式系統，可以利用ZooKeeper實現如下五種需求。

（1）為分布式集群提供中心化配置功能，例如負載均衡配置、異常場景策略配置。此外還支持熱更新，監聽某個路徑的狀態，在不重啟程序的前提下，修改配置參數并立即生效。

（2）為分布式集群提供節點動態發現與異常監控機制，例如RPC 提供者向注冊中心同步自己的服務狀態，注冊中心實時監控提供者的異常情況，并及時通知服務消費者。節點的動態拓展功能指的是新節點能夠獲取集群其他節點信息。某節點故障宕機后，集群中其他節點可以獲取通知并實現故障恢復。

（3）為分布式集群提供主從集的集群管理，支持Raft 協議群首節點投票選舉功能，是絕大多數分布式系統主從集的核心功能。

（4）提供分布式鎖，支持公平鎖和非公平鎖，提供分布式隊列。提供分布式計數器、分布式多線程同步器。支撐客戶端實現群首選舉設計模式。

（5）提供發布/訂閱設計模式的實現方案。

2 ZooKeeper數據結構

ZooKeeper 命名空間內部擁有一個樹狀的內存模型，其中各節點被稱為Znode。每個Znode包含一個路徑和與之相關的元數據［6］，以及該Znode 下關聯的子節點列表。ZooKeeper 內核設計原理都是圍繞著Znode 展開的，Znode 在Zoo?Keeper中所起的作用如圖2所示。

圖2 Znode實例

如圖2 所示，提供者向ZooKeeper 節點A 創建了Znode臨時節點，用來保存其地址和接口等信息。服務消費者從Znode臨時節點獲取對應的地址等信息，從Znode永久節點獲取負載均衡路由策略等信息，最后直連提供者發起請求。同時服務消費者監控Znode 臨時節點，及時獲取提供者在線狀態信息。ZooKeeper 節點A 通過ZAB 協議同步Znode 臨時節點數據到ZooKeeper節點B。

每個Znode都對應著一個唯一路徑，并存儲默認1 MB 的二進制數據，格式為字節數組（byte array）。ZooKeeper 不直接提供序列化和反序列化的功能，通常使用客戶端序列化工具進行解析操作。Znode 可以通過配置增大存儲數據容量，但通常不建議這么做，如果存儲的數據容量比較大，客戶端拉取時會面臨著網絡帶寬的壓力，ZooKeeper 主從集同步數據也會有帶寬壓力。如果真有這方面的需求，可以考慮把數據保存在支持事務的數據庫里，例如MySQL 把數據的主鍵更新在Znode上，實現大容量數據的實時同步。此外，因為臨時節點在創建者會話失效時會被刪除，所以ZooKeeper 不允許臨時節點擁有子節點，臨時時序節點同理。如果需要創建子節點，可以考慮父節點采用持久節點或者持久時序節點來實現。ZooKeeper 將全量Znode數據保存在內存中，用此來增加服務器的吞吐量。這種機制導致了ZooKeeper 特別適合以讀操作為主，不涉及事務的請求處理。

原語操作列表API 在擴展操作列表時需要新增API，頻繁更新API 將會降低服務的靈活性。為了保障服務的靈活性，ZooKeeper 提供給客戶端可調用的API，用于文件系統的操作，既實現了對Znode 的操作，又保障了API 的長期穩定運行。

每個Znode 都有一個版本號，當對Znode 執行修改或刪除操作時，都會導致版本號增加。所以對Znode 的并發修改可以保證有順序地執行，因為每次調用API 傳入的參數包含版本號，只有當參數版本號與ZooKeeper 服務器上的版本號一致時，修改或刪除操作才會執行成功。當多個線程同時對一個Znode進行操作時，版本號就能保證操作的原子性和可見性。ZooKeeper API支持用戶設置成禁用版本號檢查。版本號的設計和JDK 的AtomicStampedReference 采用long類型時間戳控制版本號，保障比較并交換（CAS）原子操作的原理相似。圖3 為Znode 使用版本號來控制并發操作的示意圖。

如圖3 所示，客戶端1 發起修改請求，把版本號1 當作參數，如果版本號等于1，就設置/path 路徑Znode 的值為A。服務端接收到請求后，設置Znode 的值為A，并把版本號加1，此時服務端版本號為2。客戶端2 獲取版本號為2的Znode值，然后向ZooKeeper服務端發起請求，把版本號等于2當作參數。服務端通過版本號校驗，把Znode 值設置成了B，并把版本號加1，此時服務端版本號為3。客戶端1 發起修改請求，把版本號2 當作參數，但是此時ZooKeeper服務端的Znode 版本號為3，所以版本校驗不通過。ZooKeeper 服務端直接返回操作失敗異常。通過圖3的示例可以看出版本號機制可以有效地控制并發修改問題，保證操作的原子性。

圖3 Znode版本號機制

Znode 上保存的版本號本質上是Stat 類型的對象屬性，該對象保存了節點的屬性信息。Stat對象主要包含了上次更新的時間戳（ZooKeeper transaction ID，zxid）以及擁有的子節點數量。實際業務中，ZooKeeper 管理版本號時，并不是使用單純加1的操作，還要利用事務的機制，將事務中的版本號zxid 更新Znode 的版本號。Zxid 是ZooKeeper 服務端處理事務最重要的組成元素，zxid 是64 位long 類型整數，前32 位表示時代標識Epoch，后32位表示操作序號counter。

3 監視點與通知

客戶端可以對Znode 設置監視點（watcher），當Znode 狀態發生變化時，ZooKeeper 對客戶端發出對應的事件通知，又稱基于通知（notifica?tion）的事件消息機制［7］。簡而言之，就是對Znode 綁定了一個狀態監視機制。監視點是單次觸發的操作，一個監視點只能觸發一個通知。

對一個Znode 的操作，ZooKeeper 先向客戶端傳送事件通知，然后對該節點進行變更操作。這里的Znode操作是一個事務，客戶端不需要擔心收到通知后，再獲取的數據有問題。Zoo?Keeper 管理的API 均可在Znode 上設置監聽點，監聽其讀寫操作，如Exists（）、GetData（）、GetChildren（）。

ZooKeeper 移除監視點的方法有兩個，一是觸發這個監視點事件通知；二是客戶端會話關閉或超時，監視點通知無法發送，導致監視點移除。監視點觸發的事件通知不包含變更的Znode 數據。客戶端在獲取事件通知以后，仍然需要主動調用GetData API 獲取變更的數據。當然這個操作并不是原子性的，獲得通知和拉取數據的過程中Znode數據可能會被再次修改。監視點事件通知的詳細過程如圖4所示。

在圖4 中，客戶端1 創建Znode 數據為A，并設置監聽點。客戶端2 更新Znode 數據為B，并觸發監聽點NodeDataChanged。此時，Zoo?Keeper 先通知客戶端1 數據變更，再通過ZAB協議通知集群數據為B，并修改群首持久化數據。客戶端1 接收到只是變更通知，仍需發起GetData 請求獲取Znode 數據，客戶端1 獲取數據的過程中，客戶端2 又更新Znode 數據為A。結果客戶端1 獲取Znode 數據仍然為A。客戶端1 再次對Znode 設置監聽點。雖然客戶端1 使用監聽點，沒有獲取數據B，出現了ABA 的問題，但是監聽點機制能夠保證數據的最終一致性。這里獲取Znode 數據和設置監聽點是同一個API請求（GetData API）。

圖4 監視點事件通知

服務端監聽點的信息全部保存在內存中，每個監聽點大約占用0.3 KB 內存，監聽點不會存到硬盤上。因為當服務端發現客戶端連接斷開時，判斷出無法給客戶端發送監視點通知，就會把內存中失效的監視點刪除。之所以客戶端重連后監視點仍舊生效，是因為客戶端本地保存了監視點數據，重連后同步服務端啟用對應的監視點。

客戶端重連成功后，會將全部未觸發的監視點列表發送給服務端。服務端接收并檢查該列表，如果部分Znode在客戶端上一個會話注冊監視點之后就已經更新了，那么服務端將直接把對應的監視點通知事件發送給客戶端，其余監視點重新在服務端上注冊。服務端通過對比Znode 修改zxid 包含的時間戳，就能判斷未觸發監視點列表Znode是否已經更新。

除此之外，還有一種可能導致ABA 的問題場景，假設Path 路徑的Znode 不存在，客戶端A調用Exists API 監聽該路徑是否存在，如果此時客戶端A 突然斷線，在客戶端A 斷線期間，客戶端B 創建了Path 路徑的Znode，很快Path 路徑的Znode 又被刪除了。Path 刪除后，客戶端A 重新連上了，但是此時客戶端A 無法感知Znode是否存在過。客戶端A 沒有收到對應監視點通知，仍然會將全部未觸發的監視點列表發送給服務端。這種ABA 問題無法避免，所以業務上應盡量規避這種場景。

4 ACL權限控制

ZooKeeper 提供的安全機制，是通過訪問控制表（access control list，ACL）來實現訪問權限控制的。權限控制表ACL 綁定在每個Znode 上，且子節點不會繼承父節點的權限，父、子節點的權限相對獨立。如果客戶端沒有父節點的權限，在子節點沒有設置權限的情況下，客戶端可以直接訪問子節點，所以需要分別設置父、子節點權限。ACL 權限控制方式也被應用在Linux和Unix文件系統中。

ACL 定義了Read、Write、Create、Delete、Admin共五種Znode操作的權限。Read權限用于獲取當前節點數據權限，獲取子節點列表權限。Write 權限用于更新當前節點權限。Create 權限用于創建子節點權限。Delete權限用于刪除子節點權限。Admin 權限用于設置節點ACL 列表的權限。

訪問權限的檢查是基于每一個Znode 的，ACL 權限控制包含兩個方面，一是ZooKeeper 服務端內置的ACL 鑒權模式；二是客戶端請求服務器提交的鑒權信息。客戶端請求攜帶的鑒權信息數據結構是根據ZooKeeper 服務端采用的鑒權模式來匹配的，格式是scheme:auth-info，即“鑒權模式:鑒權信息”的格式。通常客戶端進程可以在任何時候調用addAuthInfo 來提交鑒權，只有IP 鑒權模式不需要該操作。常用的鑒權模式包括world 鑒權模式、digest 鑒權模式、IP 鑒權模式、自定義鑒權模式、SAS鑒權模式、super鑒權模式共六種。