[[402864]]

本文轉(zhuǎn)載自微信公眾號(hào)「木鳥(niǎo)雜記」，作者木鳥(niǎo)雜記。轉(zhuǎn)載本文請(qǐng)聯(lián)系木鳥(niǎo)雜記公眾號(hào)。

本篇要介紹 Patrick Hunt 等人在 2010 年發(fā)表的、至今仍然廣泛使用的、定位于分布式系統(tǒng)協(xié)調(diào)組件的論文 —— ZooKeeper: Wait-free coordination for Internet-scale systems。我們?cè)诙嗑€程、多進(jìn)程編程時(shí)，免不了進(jìn)行同步和互斥，常見(jiàn)手段有共享內(nèi)存、消息隊(duì)列、鎖、信號(hào)量等等。而在分布式系統(tǒng)中，不同組件間必然也需要類似的協(xié)調(diào)手段，于是 Zookeeper 應(yīng)運(yùn)而生。配合客戶端庫(kù)，Zookeeper 可以提供動(dòng)態(tài)參數(shù)配置(configuration metadata)、分布式鎖、共享寄存器(shared register)、服務(wù)發(fā)現(xiàn)、集群關(guān)系(group membership)、多節(jié)點(diǎn)選主(leader election)等一系列分布式系統(tǒng)的協(xié)調(diào)服務(wù)。

總體來(lái)看，Zookeeper 有以下特點(diǎn)：

1. Zookeeper 是一個(gè)分布式協(xié)調(diào)內(nèi)核，本身功能比較內(nèi)聚，以保持 API 的簡(jiǎn)潔與高效。
2. Zookeeper 提供一組高性能的、保證 FIFO的、基于事件驅(qū)動(dòng)的非阻塞 API。
3. Zookeeper 使用類似文件系統(tǒng)的目錄樹(shù)方式對(duì)數(shù)據(jù)進(jìn)行組織，表達(dá)能力強(qiáng)大，方便客戶端構(gòu)建更復(fù)雜的協(xié)調(diào)源語(yǔ)。
4. Zookeeper 是一個(gè)自洽的容錯(cuò)系統(tǒng)，使用 Zab 原子廣播(atomic broadcast)協(xié)議保證高可用和一致性。

本文依從論文順序，簡(jiǎn)要介紹下 Zookeeper 的服務(wù)接口設(shè)計(jì)與模塊粗略實(shí)現(xiàn)。更多細(xì)節(jié)請(qǐng)參考論文和開(kāi)源項(xiàng)目主頁(yè)。

服務(wù)設(shè)計(jì)

我們?cè)谠O(shè)計(jì)服務(wù)接口的時(shí)候，首先要抽象出服務(wù)組織和交互所涉及到的基本概念，進(jìn)而才能厘清圍繞這些基本概念的動(dòng)作集合。對(duì)于 Zookeeper 來(lái)說(shuō)，這些基本概念稱為術(shù)語(yǔ)(Terminology)，動(dòng)作集合稱為服務(wù)接口(API)。

術(shù)語(yǔ)集

1. 客戶端：client，使用 Zookeeper 服務(wù)的用戶。
2. 服務(wù)器：server，提供 Zookeeper 服務(wù)的進(jìn)程。
3. 數(shù)據(jù)樹(shù)：data tree，Zookeeper 中所有的數(shù)據(jù)以樹(shù)形結(jié)構(gòu)進(jìn)行組織。
4. z-節(jié)點(diǎn)：znode、Zookeeper Node，數(shù)據(jù)樹(shù)中的節(jié)點(diǎn)，是基本數(shù)據(jù)單元。
5. 會(huì)話：session，客戶端與服務(wù)器會(huì)新建一個(gè)會(huì)話來(lái)標(biāo)識(shí)一個(gè)連接，之后客戶端每次請(qǐng)求都會(huì)通過(guò)該會(huì)話句柄來(lái)進(jìn)行。Watch 事件的生命周期也是和會(huì)話綁定的。

后面行文中，對(duì)應(yīng)術(shù)語(yǔ)的中英文可能會(huì)交雜使用。

數(shù)據(jù)組織

Zookeeper 對(duì)所存數(shù)據(jù)進(jìn)行類似文件系統(tǒng)的樹(shù)形層次化組織，可以提供給使用者更強(qiáng)大的靈活性。比如可以很自然的表示命名閾(namespace)，比如使用同一父節(jié)點(diǎn)的所有孩子表示成員關(guān)系(membership)。一個(gè)路徑(Path)可以定位到一個(gè)唯一的數(shù)據(jù)節(jié)點(diǎn)，進(jìn)而能夠唯一標(biāo)識(shí)一個(gè)基本數(shù)據(jù)單元。

zookeeper 層次化的命名空間組織

樹(shù)中支持兩種類型的 znode：

1. 普通節(jié)點(diǎn)：Regular，生命周期無(wú)限，客戶端需要調(diào)用接口顯式的對(duì)這類節(jié)點(diǎn)進(jìn)行增刪。
2. 暫態(tài)節(jié)點(diǎn)：Ephemeral，生命周期綁定到會(huì)話上，會(huì)話銷毀，節(jié)點(diǎn)刪除。

此外，Zookeeper 允許客戶端在創(chuàng)建 znode 時(shí)，附加一個(gè) sequential 標(biāo)志。Zookeeper 便會(huì)自動(dòng)給節(jié)點(diǎn)名字添加一個(gè)全局自增的計(jì)數(shù)作為后綴。

Zookeeper 使用***推***的方式實(shí)現(xiàn)訂閱機(jī)制，即用戶在訂閱(watch)了某個(gè)節(jié)點(diǎn)后，當(dāng)該節(jié)點(diǎn)發(fā)生變化時(shí)，客戶端會(huì)收到一次通知(邊緣觸發(fā))，一個(gè)訂閱是綁定到會(huì)話上的，因此會(huì)話銷毀后，訂閱的事件也會(huì)消失。

會(huì)話機(jī)制(session)?？梢钥吹剑琙ookeeper 使用會(huì)話機(jī)制管理客戶端一次連接的生命周期。在實(shí)現(xiàn)時(shí)，會(huì)話會(huì)關(guān)聯(lián)一個(gè)超時(shí)間隔(timeout)。如果客戶端死掉或者與 Zookeeper 斷開(kāi)連接，超時(shí)時(shí)限內(nèi)客戶端未進(jìn)行心跳，Zookeeper 會(huì)在服務(wù)器端銷毀該會(huì)話。

數(shù)據(jù)模型(Data model)。Zookeeper 本質(zhì)上提供樹(shù)形組織的 KV 模型。除存儲(chǔ)鍵值對(duì)數(shù)據(jù)外，Zookeeper 更多的是以其空間結(jié)構(gòu)和生命周期管理作為表達(dá)能力，來(lái)提供協(xié)調(diào)語(yǔ)義。當(dāng)然，Zookeeper 也允許客戶端為節(jié)點(diǎn)附加一些元信息(meta-data)和配置信息(configuration)，并且提供版本和時(shí)間戳支持，從而提供更強(qiáng)大的表達(dá)能力。

API 細(xì)節(jié)

下面是以偽碼的形式列出 Zookeeper 對(duì)客戶端提供的 API 細(xì)節(jié)和注釋。所有操作對(duì)象都是路徑( path) 所對(duì)應(yīng)的數(shù)據(jù)節(jié)點(diǎn)(znode)。

// 在路徑 path 處創(chuàng)建一個(gè) znode，存入數(shù)據(jù) data 
// 并設(shè)置 regular, ephemeral, sequential 等 flags 標(biāo)志。 
// 返回值：znode 名字 
create(path, data, flags)  
 
// 如果 path 處的 znode 與預(yù)期 version 相同， 
// 則刪除該 znode。 
// 指定 version 一般是為了并發(fā)安全。 
delete(path, version) 
 
// watch 讓客戶端在此 path 上添加一個(gè)監(jiān)聽(tīng) 
// 返回值：路徑對(duì)應(yīng)的 znode，存在時(shí)返回 true 
// 不存在返回 false 
exists(path, watch) 
 
// 獲取路徑 path 對(duì)應(yīng)的 znode 的數(shù)據(jù)和元信息 
// 當(dāng) znode 存在時(shí)，允許設(shè)置 watch 來(lái)監(jiān)聽(tīng) 
// znode 數(shù)據(jù)變化 
getData(path, watch) 
 
// 當(dāng) version 匹配時(shí)，將數(shù)據(jù) data 寫入 
// path 對(duì)應(yīng)的 znode 
setData(path, data, version) 
 
// 獲取路徑 path 對(duì)應(yīng)的 znode 的所有孩子 
getChildren(path, watch) 
 
// 同步最新數(shù)據(jù)，通常放在 getData 前面 
sync(path) 

上面的 API 有以下特點(diǎn)：

異步支持。所有接口都有同步(synchronous)和異步(asynchronous)版本。異步版本以回調(diào)函數(shù)方式進(jìn)行執(zhí)行，客戶端可以根據(jù)業(yè)務(wù)需求，選擇阻塞等待以獲取重要更新，或者異步調(diào)用以獲得更好性能。

路徑而非句柄。為了簡(jiǎn)化接口設(shè)計(jì)，并減少服務(wù)端維護(hù)的狀態(tài)， Zookeeper 使用路徑而非 znode 句柄的形式來(lái)提供對(duì) znode 的操作接口。畢竟，句柄類似于 session，是有狀態(tài)的，會(huì)增加分布式系統(tǒng)的實(shí)現(xiàn)復(fù)雜度。使用路徑，可以配合版本信息做成類似冪等的接口，在處理多客戶端并發(fā)時(shí)，更容易實(shí)現(xiàn)。

版本信息。所有的更新操作(set/delete)都需要指明對(duì)應(yīng)數(shù)據(jù)的版本號(hào)，版本號(hào)不匹配則終止更新并返回異常。但可以通過(guò)指定特殊版本號(hào) -1 ，跳過(guò)版本號(hào)檢查。

語(yǔ)義保證

在處理多個(gè)客戶端向 Zookeeper 發(fā)出的并發(fā)請(qǐng)求時(shí)， API 有兩個(gè)基本順序的保證：

線性化寫(Linearizable writes)。所有 Zookeeper 狀態(tài)的更新請(qǐng)求會(huì)被串行化執(zhí)行。

客戶端內(nèi)的先入先出(FIFO client order)。給定客戶端的請(qǐng)求會(huì)按其發(fā)送的順序進(jìn)行執(zhí)行。

但這里的線性化是一種異步線性化：A-linearizability。即單個(gè)客戶端可以同時(shí)有多個(gè)正在執(zhí)行的請(qǐng)求(multiple outstanding operations)，但是這些請(qǐng)求會(huì)按發(fā)出順序進(jìn)行執(zhí)行。對(duì)于讀請(qǐng)求，可以在每個(gè)服務(wù)器本地(不需要通過(guò)主)執(zhí)行。因此，可以通過(guò)增加服務(wù)器(Observer)提升讀請(qǐng)求的吞吐。

此外，Zookeeper 還提供可用性和持久性的保證：

可用性(liveness)：Zookeeper 集群中過(guò)半數(shù)節(jié)點(diǎn)可用，則可對(duì)外正常提供服務(wù)。

持久性(durability)：任何被成功返回給客戶端的修改請(qǐng)求，都會(huì)作用到 Zookeeper 狀態(tài)機(jī)中。即使不斷有節(jié)點(diǎn)故障重啟，只要 Zookeeper 能正常提供服務(wù)，就不會(huì)影響這一特性。

Zookeeper 架構(gòu)

為了提供高可靠性，Zookeeper 使用多臺(tái)服務(wù)器對(duì)數(shù)據(jù)進(jìn)行冗余存取。然后使用 Zab 共識(shí)協(xié)議處理所有的更新請(qǐng)求，然后寫入 WAL，進(jìn)而應(yīng)用到本地內(nèi)存狀態(tài)機(jī)(data tree)。

在 Zab 協(xié)議中，所有節(jié)點(diǎn)分為兩種角色，Leader 和 Followers，前者只有一個(gè)，剩余的都是 Followers。但后來(lái)實(shí)踐中，可能有 Observers。

zookeeper 組件與請(qǐng)求流程

如上圖所示，當(dāng) Server 收到一個(gè)請(qǐng)求時(shí)，首先進(jìn)行預(yù)處理(Request Processor)，如果是寫請(qǐng)求，則通過(guò) Zab 協(xié)議(Atomic Broadcast)達(dá)成一致，然后各自提交到本地?cái)?shù)據(jù)庫(kù)(Replicated Database)。對(duì)于讀請(qǐng)求，直接讀取本地?cái)?shù)據(jù)庫(kù)中狀態(tài)后返回。

請(qǐng)求處理(Request Processor)

所有更新請(qǐng)求都會(huì)被轉(zhuǎn)為冪等(idempotent)的事務(wù)(txn)，具體方法為獲取當(dāng)前狀態(tài)、計(jì)算出目標(biāo)狀態(tài)，封裝為事務(wù)，即可使用類似 CAS 的方式處理并發(fā)請(qǐng)求。因此，只要保證所有事務(wù)按固定順序執(zhí)行，就能避免不同服務(wù)器上的數(shù)據(jù)副本分裂。

原子廣播(Atomic Broadcast)

所有更新請(qǐng)求都會(huì)被轉(zhuǎn)給 Zookeeper 的 Leader，Leader 首先將事務(wù)追加到本地 WAL，然后將變動(dòng)使用 Zab 協(xié)議廣播到各個(gè)節(jié)點(diǎn)，收到過(guò)半成功回復(fù)之后，Leader 將變動(dòng)提交(Commit)到本地內(nèi)存數(shù)據(jù)庫(kù)，并廣播該 Commit 給 Followers。

由于 Zab 使用多數(shù)票原則，因此 2k+1 個(gè)節(jié)點(diǎn)的集群最多可以容忍 k 個(gè)節(jié)點(diǎn)的故障(failures)。

為了提高系統(tǒng)吞吐，Zookeeper 使用流水線(pipelined)方式優(yōu)化多個(gè)請(qǐng)求處理過(guò)程。

復(fù)制狀態(tài)機(jī)(Replicated Database)

每個(gè)服務(wù)器都會(huì)在本機(jī)內(nèi)存中維護(hù)一個(gè) Zookeeper 中所有狀態(tài)的副本(replica)，為了應(yīng)對(duì)宕機(jī)重啟，ZooKeeper 會(huì)定期將狀態(tài)做快照。不同于普通快照，Zookeeper 稱其快照為 fuzzy snapshots，即在做快照時(shí)并不上鎖，通過(guò) DFS 的方式遍歷文件樹(shù) Dump 到本地。之后由于異常宕機(jī)重啟時(shí)，只需加最新快照，然后重新執(zhí)行最新快照之后幾條 WAL 即可。由于 WAL 中記錄的事務(wù)的冪等性特點(diǎn)，即使快照和 WAL 的時(shí)間點(diǎn)不完全對(duì)應(yīng)，也不會(huì)影響副本間的一致性。

客戶端服務(wù)器交互事宜(Client-Server Interactions)

串行寫。無(wú)論是在全局范圍還是具體到一個(gè) Server 本地，所有更新操作都是串行的。在執(zhí)行某個(gè) Path 數(shù)據(jù)更新時(shí)，該 Server 會(huì)觸發(fā)所有與之連接的 Client 所訂閱的 Watch 事件。需要注意，這些事件只保存在 Server 本地，因?yàn)樗麄兪呛蜁?huì)話關(guān)聯(lián)的，如果 Client 與該 Server 斷開(kāi)連接，會(huì)話便會(huì)銷毀，這些事件也隨之消亡。

本地讀。為了獲取極致性能，Zookeeper 的 Server 直接在本地處理讀請(qǐng)求。但這有可能造成客戶端拿到陳舊數(shù)據(jù)(比如其他客戶端在另外的 Server 更新了同一 Path)。于是 Zookeeper 設(shè)計(jì)出了 Sync 操作，會(huì)將調(diào)用 Sync 時(shí)刻的最新提交數(shù)據(jù)同步到與該 Client 連接的 Server 上，然后將最新數(shù)據(jù)返回給 Client。即，Zookeeper 將性能與時(shí)效性的選擇權(quán)交給了用戶，方法是是否調(diào)用 Sync。

一致性視圖。Zookeeper 全局會(huì)維持一個(gè)事務(wù)自增標(biāo)識(shí)：zxid，它本質(zhì)上是個(gè)邏輯時(shí)鐘，可以標(biāo)識(shí) Zookeeper 一個(gè)時(shí)刻的數(shù)據(jù)視圖。Client 在故障重啟后重新連接到一個(gè)新的 Server 時(shí)，如果該 Server 未執(zhí)行到客戶端所存 zxid，則要么 Server 執(zhí)行到該 zxid 后再回復(fù) Client，要么 Client 換一個(gè)更新的 Server 進(jìn)行連接。如此，可以保證 Client 不會(huì)看到回退的視圖。

會(huì)話過(guò)期。會(huì)話在 Zookeeper 中本質(zhì)上標(biāo)識(shí)一個(gè) Client 到 Server 的連接。會(huì)話有超時(shí)時(shí)間，如果 Client 長(zhǎng)時(shí)間(大于超時(shí)間隔)不發(fā)請(qǐng)求或者心跳，Server 便會(huì)刪除該會(huì)話。

小結(jié)

Zookeeper 使用目錄樹(shù)組織數(shù)據(jù)、使用 Zab 協(xié)議同步數(shù)據(jù)、使用非阻塞方式提供接口，構(gòu)建了一個(gè)表達(dá)能力強(qiáng)大的分布式協(xié)調(diào)性內(nèi)核。可以用于分布式系統(tǒng)的控制面以進(jìn)行協(xié)調(diào)、調(diào)度和控制。近年來(lái)基于 Raft 的 Etcd 也是類似地位。