Apache ZooKeeper設(shè)計理念和數(shù)據(jù)結(jié)構(gòu)的研究

陳 濤，索海燕

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

0 引言

在傳統(tǒng)的計算機(jī)行業(yè)中，開發(fā)人員通常擅長開發(fā)單機(jī)程序，卻很難高效地開發(fā)出多個獨立程序協(xié)同工作功能。這是因為開發(fā)這種協(xié)同技術(shù)是非常困難的，很容易導(dǎo)致開發(fā)者投入大量的時間考慮協(xié)同工作的業(yè)務(wù)邏輯，而沒有時間更好地處理并實現(xiàn)應(yīng)用程序的業(yè)務(wù)邏輯。

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

1 ZooKeeper設(shè)計理念

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

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

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

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

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

圖1 Apache Dubbo生成的服務(wù)提供目錄

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

采用中心化設(shè)計理念的分布式系統(tǒng)，可以利用ZooKeeper實現(xiàn)如下五種需求。

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

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

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

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

（5）提供發(fā)布/訂閱設(shè)計模式的實現(xiàn)方案。

2 ZooKeeper數(shù)據(jù)結(jié)構(gòu)

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

圖2 Znode實例

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

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

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

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

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

圖3 Znode版本號機(jī)制

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

3 監(jiān)視點與通知

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

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

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

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

圖4 監(jiān)視點事件通知

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

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

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

4 ACL權(quán)限控制

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

ACL 定義了Read、Write、Create、Delete、Admin共五種Znode操作的權(quán)限。Read權(quán)限用于獲取當(dāng)前節(jié)點數(shù)據(jù)權(quán)限，獲取子節(jié)點列表權(quán)限。Write 權(quán)限用于更新當(dāng)前節(jié)點權(quán)限。Create 權(quán)限用于創(chuàng)建子節(jié)點權(quán)限。Delete權(quán)限用于刪除子節(jié)點權(quán)限。Admin 權(quán)限用于設(shè)置節(jié)點ACL 列表的權(quán)限。

訪問權(quán)限的檢查是基于每一個Znode 的，ACL 權(quán)限控制包含兩個方面，一是ZooKeeper 服務(wù)端內(nèi)置的ACL 鑒權(quán)模式；二是客戶端請求服務(wù)器提交的鑒權(quán)信息?？蛻舳苏埱髷y帶的鑒權(quán)信息數(shù)據(jù)結(jié)構(gòu)是根據(jù)ZooKeeper 服務(wù)端采用的鑒權(quán)模式來匹配的，格式是scheme:auth-info，即“鑒權(quán)模式:鑒權(quán)信息”的格式。通?？蛻舳诉M(jìn)程可以在任何時候調(diào)用addAuthInfo 來提交鑒權(quán)，只有IP 鑒權(quán)模式不需要該操作。常用的鑒權(quán)模式包括world 鑒權(quán)模式、digest 鑒權(quán)模式、IP 鑒權(quán)模式、自定義鑒權(quán)模式、SAS鑒權(quán)模式、super鑒權(quán)模式共六種。