1 Google Chubby
分布式鎖服務是現代分布式系統的重要基礎之一。簡單的說，分布式鎖服務實現了在一個分布式的環境下實現了單機版鎖服務的功能。在分布式環境下，鎖服務鎖定的資源對象通常不是單個線程，或者進程，而是單個或者多個客戶端。Google對分布式鎖服務的定義是：分布式鎖服務的目標是讓客戶端的行為得到同步，並使他們關於環境的一些基礎信息達到統一。由於是分布式系統的組成部分，分布式鎖的首要設計目標包括：可靠性、對於大規模客戶端的可用性、以及簡單，且易於理解的語義。鎖服務的吞吐率和存儲能力則是其他需要重點考慮的問題。值得注意的一點是，與這幾個重要的目標相比，分布式系統的性能並不是一個需要優先考慮的問題。
Chubby是Google開發的分布式鎖系統，目前，在Bigtable(Google的分布式存儲系統)和MapReduce(Google的分布式計算平台)中都應用了Chubby提供的分布式鎖服務，以保證分布式的同步和並發。在參考文獻[1]中提到，Chubby被用於解決以下問題：
a) 幫助工程師實現服務的高可用性。
b) 為需要主從選擇，數據劃分的服務提供選擇機制和通告方式(advertising the results)。
c) 基於鎖的使用接口(lock-based interface)容易理解
d) 分布式一致性算法利用投票的方式來做出決定，並利用鏡像冗余獲得高可用性
Chubby的設計實現基於以下的考慮：
a) 一個服務通過一個Chubby文件發布服務的基礎信息，而這個服務可能被成千上萬的客戶端所依賴。這就要求在服務器盡可能少的條件下，有效支持這些客戶端對該文件的訪
b) 多服務器冗余環境下，從屬服務器需要知道主服務器的更新狀況，這就需要通知機制來避免輪詢，以提高效率
c) 需要有cache機制來緩存查詢結果，以防止多余重復訪問
d) 需要有權限控制來保證數據訪問的安全
1.1 系統構架
Chubby主要由兩個通過PRC通訊的部分組成：服務器，與應用相連的客戶端庫。
每個Chubby組群(Cell)都包含一組保持相同數據的Chubby服務器，被稱為replicas。每個組群利用分布式一致性協議(distributed consensus protocol, 如：Paxos[2])來選擇一個主服務器(master)，並且在一個主服務器租期(master lease)內，組群不會再選擇新的主服務器。組群中的所有服務器都有一個數據庫的備份，但只有主服務器能發起讀和寫的響應，其他服務器只利用分布式一致性協議從主服務器獲得更新。
客戶端通過DNS服務器獲得組群中主服務器的地址。當客戶端確定了主服務器後，就將所有請求發送到主服務器，直到主服務器不再響應，或者該服務器返回它已經不再是主服務器為止。主服務器將客戶端寫請求轉發給其他服務器，只有當組群中大多數服務器更新成功後，該寫請求才被確認。讀請求完全由主服務器響應。當主服務器死機，或者主服務器租期結束時，組群能在1分鐘之內選出新的主服務器(一般來說，這個過程只花費幾秒鐘時間)。當服務器失效後，若數小時不能恢復服務，則系統自動從備機池中啟用備機保證組群機器數目。
圖一、Chubby系統構架
1.2 系統細節
Chubby采用類似於UNIX文件系統的方式管理系統中的相關文件，如一個典型的文件路徑: /ls/foo/wombat/pouch。其中ls是Chubby系統常用的前綴，代表Lock Service;foo是Chubby集群的名字。/wombat/pouch則標識了Chubby的具體服務。Chubby如此的樹狀層次結構安排主要是為了方便文件系統(如Google File System)的訪問。但與UNIX文件系統不同的是，Chubby中文件的訪問權限完全取決於文件本身定義的訪問權限，與它所在上層目錄的訪問權限無關。Chubby中的文件和文件夾，也被稱為節點(node)，有“永久節點”和“暫時性節點”之分。任何類型的節點都能被刪除，“暫時性節點”還可以在無客戶端連接時自動刪除。每個節點都能作為一個讀寫鎖被使用。節點的元數據信息中，包含ACL(Access Control Links)信息，當節點被創建時，若不指定其訪問權限，則節點自動繼承上級目錄的訪問權限。每次RPC訪問時，系統會自動根據ACL信息確定客戶端的訪問合法性。
節點的元數據中，還包含4個嚴格增長的64位整數：
名稱描述
實體編號比上一個與此節點同名的節點的該編號大
內容編號當文件內容發生改變時增長
鎖編號當鎖狀態從釋放變為持有時增長
ACL編號當節點的ACL信息被修改時增長
Chubby中的任何文件都可以作為鎖被客戶端持有(以互斥鎖，或者讀寫鎖的模式)，但無論以何種方式持有鎖都要求客戶端對該節點有寫權限，如果客戶端只對某個節點有讀權限，它無法阻止有權限的客戶端對節點進行寫操作。分布式環境中的鎖是非常復雜的，因為各個實體間的網絡交互情況是不確定的。可能出現的情況是客戶端A獲得了鎖L，當它發送請求R時，網絡發生故障。此時客戶端B又獲得了鎖L，並進行了某些操作，這時，如果R請求到達的話，它並不是一個受到鎖L保護的操作。解決這個問題的關鍵在於，服務器在處理請求時必須嚴格按照事件發生的順序。由於對於每次交互都加序列號的實現方式代價太大，Chubby只對需要鎖的操作記錄序列號：客戶端在取得了鎖之後，會馬上向服務器請求一個序列號和鎖狀態。當客戶發起操作請求時，服務器會驗證客戶端帶的序列號和鎖狀態是否有效，如果已經失效，則操作被拒絕。
即便如此，也不是所有協議都可以加上序列號，所以Chubby還保存了一種不完美，但比較有效的方法：鎖延時(lock-delay)。當客戶端主動釋放鎖時，其他客戶端可以馬上獲得該鎖。但如果是因為客戶端失效或者通信失敗的話。其他客戶端將在一定時間內(即，鎖延時時間內)不能獲得該鎖。
Chubby具有依據事件的異步喚醒機制，支持的事件包括：
a) 文件內容被修改。該事件通常被用來監視服務描述(即，資源定位)文件
b) 子節點的增加、刪除、或者修改操作
c) Chubby主服務器失效。接收到該事件表明，某些交互信息可能已經丟失
d) 鎖被獲得。這個事件可以被用於判斷某服務器是否被選為主服務器
e) 其他客戶端發來的鎖沖突請求
Chubby實現了以下的API：
接口名描述
Open()根據文件名獲得文件句柄，與UNIX類似。客戶端需要傳遞如下信息：
a)這個句柄的使用方式(讀、寫、鎖定，或者修改訪問權限)，只有在使用方式符合客戶端權限的時候，打開句柄才能成功。
b)客戶端接收的事件類型
c)鎖延時(lock-delay)長度
d)是否需要創建新文件或者新目錄，如果需要則需要傳遞初始化信息
Close()關閉文件句柄
Poison()不關閉文件句柄，但任何關於該句柄的操作都會失敗
GetContentsAndStat()獲得文件(節點)數據和元數據
GetStat()獲得文件(節點)元數據
ReadDir()獲得文件夾中子節點名和他們的元數據
SetContents()寫文件內容。客戶端需要提供當前數據編號，如果編號錯誤，則失敗
SetACL()設置文件(節點)ACL信息
Delete()刪除一個無子節點的節點
Acquire()請求鎖
TryAcquire()嘗試請求鎖
Release()釋放鎖
GetSequencer()返回一個與該句柄持有鎖相關的序列號
SetSequencer()將一個序列號與句柄相關聯
客戶端利用Chubby選主的過程即可利用以上的API實現：所有候選客戶端同時打開同一個文件句柄，並競爭它的鎖，獲得鎖的客戶端將自身信息寫入該文件，以便讓其他客戶端知道自己已經成為主客戶端。
另一方面，為了減輕網絡交互的壓力，Chubby的客戶端庫還實現了cache。客戶端庫接收服務器發送的失效通知來使客戶端內存中的數據失效。當Chubby服務器上的數據和元數據被修改的時候，主服務器會發失效通知給可能cache了這些數據的客戶端，這一機制是建立在KeepAlives機制之上，並依賴租約機制。它保證了客戶端看到的服務器是一致的，或者是失效的。注意，此處Chubby服務器僅僅是讓客戶端的cache失效，而沒有不是更新客戶端的cache，這是由於在分布式情況下讓cache失效遠比直接更新cache要有效率。
Chubby中定義的會話(Session)指的是Chubby組群和客戶端之間的一種連接關系，這種關系存在於一定時間段內，並由一種周期性進行的handshake所維護，這種握手被稱為KeepAlives。除非客戶端通知Chubby組群中止會話，客戶端關於Chubby句柄的任何操作都會使會話保持有效。客戶端在第一次連接Chubby主服務器的時候建立會話，當會話被外部中止，或者空閒的時候，會話結束。每個會話都由一個租期(lease)相關聯，Chubby服務器保證在租期時間內，服務器端不會關閉會話。服務器有權限延長與客戶端的會話租期時間，但不能將其縮短。
服務器通過KeepAlives的回復可以延長客戶端租期的時間。此外，KeepAlives回復還被用於傳遞Chubby服務器事件和cache失效信息給客戶端。當服務器有信息傳遞給客戶端時，KeepAlives回復將會早一些返回。而KeepAlives回復中的Piggybacking事件保證了客戶端不能在沒有做cache失效確認的情況下維持會話有效。這樣的機制簡化了客戶端，並且方便穿透只能單向發起請求的防火牆。當一個客戶端租期到期的時候，客戶端無法判斷是否是服務器中止了會話，此時客戶端會清空本地cache，進入Jeopardy狀態，並等待一段時間(the grace period)。如果在這段時間中，Chubby服務器能成功的完成KeepAlives交互，則客戶端重新使其cache有效。否則客戶端認為會話已經失效。這保證了客戶端的調用不會在Chubby組群失效時永久阻塞。當grace period開始的時候，Chubby客戶端庫保證客戶端會收到Jeopardy事件，如果，KeepAlives能成功完成，則客戶端會收到safe事件，否則，則收到expired事件。
當Chubby主服務器發生變更時，新的Chubby主服務器會做以下一些工作：
a) 首先選擇一個新的時期編號(epoch number)，客戶端的每個請求都需要帶這個編號。這樣可以保證當前的Chubby主服務器不會處理以及過時的(發給以前主服務器的)請求。
b) 新的主服務器也可以響應定位主服務器的請求
c) 新的主服務器在內存中創建被用於會話和鎖等信息的結構體，並保存在數據庫中。並且將會話租期調整到前一主服務器允許的最大租期長度
d) 此時，新的主服務器已經可以接受KeepAlives請求，但不能處理會話相關的操作。
e) 新的主服務器發送服務器失效事件給每個連接客戶端，並通知它們清除cache，因為某些事件可能已經被丟失。
f) 新的主服務器等待所有連接客戶端確認服務器失效事件，並讓會話過期
g) 如果客戶端使用過期的句柄連接服務器，則新的主服務器重新在內存中建立該句柄的標識方式，並相應請求。但如果該句柄被關閉，則新的主服務器保證，在其服務期間，該句柄不能再次被使用，這保證了網絡延時不會造成已關閉的句柄重新打開。
h) 新的主服務器在啟動一段時間後會關閉沒有客戶端鏈接的暫時性節點，所以客戶端在收到主機主機失效的事件後，應該刷新暫時性節點。
關於數據存儲和備份方面，Chubby一開始使用Berkeley DB的key-value存儲方式儲存節點數據和元數據，並每隔幾個小時就將數據庫快照備份到異地的GFS文件服務器上。這樣的備份機制完全可以保證數據恢復，或者重建新備機數據的要求。鏡像功能方面，由於Chubby文件的實現方式，簡單的文件拷貝就能實現鏡像功能。
2 Zookeeper
正如前文所說，Zookeeper的設計和實現參考了Chubby的設計原理。如，Zookeeper也使用了類似於文件系統的樹狀名字空間，也用ACL控制訪問權限，也有事件觸發機制等。但Zookeeper實現的功能可以認為是Chubby實現功能的一個子集。以下將總結和分析Zookeeper實現的功能，並與Chubby以及Space組的UDAM系統的功能做一個比較。
2.1 Zookeeper數據模型
Zookeeper使用類似於分布式文件系統的樹狀命名空間。不同的是，在Zookeeper中只使用絕對路徑，沒有相對路徑。對於命名空間中的每一個節點，都有與之相關的數據和子節點。(分析：此處Zookeeper的資源表示方式與Chubby是一致，以路徑名的方式來表示資源的邏輯關系。UDAM也采用樹狀的方式標識資源)。
2.1.1 數據節點(ZNodes)
Zookeeper樹狀結構上的節點被稱為znode。每個znode維護一個stat數據結構，它包括了數據的版本號，訪問控制鏈的版本號，時間戳等。每次znode的數據發生變化時，數據版本號都會增長。當客戶端發起一個節點的刪除或者更新操作時，必須攜帶該數據節點當前的版本號，若版本號不正確，則操作將會失敗。(分析：與Chubby不同的一點是，Zookeeper的節點並沒有天然的鎖屬性，不能對節點進行直接的加鎖和解鎖操作。但鎖的實現通過Zookeeper實現的另一個特性得到彌補，即，順序節點。本文後面會解釋如何使用序列節點實現分布式鎖功能。另一方面，與Chubby一致的一點是，節點有與之關聯的數據和元數據。數據的格式自由，有很好的擴展性。在這方面，UDAM目前實現的是子系統級別的資源實體定位，數據可擴展性方面較弱)
2.1.1 監視機制(Watch)
Zookeeper客戶端在數據節點上設置監視，則當數據節點發生變化時，客戶端會收到提醒。詳細分析見本文下面的內容。
2.1.2 數據訪問(Data Access)
對於Zookeeper數據節點的數據讀寫是Zookeeper自動完成的，並以單個節點為粒度，即，讀操作讀出與數據節點相關聯的所有數據，寫則替換該節點上的所有數據。每個節點上的“訪問控制鏈”(ACL, Access Control List)保存了各客戶端對於該節點的訪問權限。(分析：ACL的訪問權限控制思想與Chubby一致。Zookeeper對與用戶類別的區分，不只局限於所有者、組、以及所有人三個級別。Zookeeper支持對訪問的區分有更加細的粒度。UDAM使用ip名單的方式控制，防止線下的模塊使用線上的資源。但沒有粒度更小的權限控制。對於目前NS應用來說，UDAM的實現已經夠用，但Zookeeper這方面功能更加完善)
2.1.3 暫時性節點(Ephemeral Nodes)
Zookeeper有個暫時性節點機制，即，暫時性節點僅在單個會話(session)中，當會話結束時，節點便銷毀了。這個特性決定了這類節點不能有子節點。(分析：從Zookeeper文檔描述分析，暫時性節點是對應於模塊級資源的合適選擇。當模塊失效時，節點銷毀。)
2.1.4 順序節點(Sequence Nodes)
順序節點用於保證新創建的節點中所帶的編號一定大於某個已有節點的編號。(分析：Chubby中沒有順序節點的概念，Zookeeper使用順序節點來實現分布式鎖的功能)
2.2 Zookeeper 中的時間
Zxid
Zookeeper 事務ID，由zxid來標識Zookeeper狀態的每一個變化，zxid按照產生的時間順序遞增。
節點版本號：數據節點的每一個變化將改變節點的一個版本號。三個節點版本號包括：版本(數據節點變化的次數)、子節點版本(子節點變化的次數)、訪問控制鏈版本(訪問控制鏈變化的次數)
Ticks：在多服務器的Zookeeper服務中，時間的時間用ticks來描述。當客戶端要求一個比最小會話失效時間更小的超時時間時，最小會話失效時間將會被使用。
2.3 stat 結構體
字段名含義
Czxid該znode創建時的zxid
Mzxid該znode最後一次修改時的zxid
Ctime該znode創建時的時間
Mtime該znode最後一次修改的時間
Version該znode的變化次數
Cversion該znode的子節點變化次數
Aversion該znode的acl變化次數
EphemeralOwner如果是個暫時性節點，則記錄擁有該znode的會話id，否則為0
DataLength該znode數據長度
NumChildren該znode子節點個數
2.4 Zookeeper會話
客戶端保存了所有Zookeeper服務器列表，並在發起服務請求時隨機選擇服務器。當客戶端向Zookeeper發起服務請求時，Zookeeper會創建一個Zookeeper會話，並產生一個64位數值的會話ID。如果客戶端連接其他Zookeeper服務器，則會把這個會話ID作為握手的一個參數。為了保證數據傳輸安全，與會話ID相關聯的一個密碼會發送給客戶端。會話ID與密碼的關聯關系，集群中的任何一台Zookeeper服務器都可以驗證。(分析：該機制不僅保證了數據傳輸的安全性，也保證了，當某台Zookeeper服務器停機時，客戶端能夠毫無障礙地連接新的Zookeeper服務器以獲得持續的會話服務)
客戶端與服務器建立連接時的參數包括：
a)超時設置(以ms為單位)，目前要求這個超時時間至少是tickTime的兩倍
b)默認監視器，當客戶端的數據發生變化的時候，該監視器將被通知。監視器的初始狀態是“連接斷開”，所以發起連接請求時，監視器收到的第一的事件是連接建立。
(分析：UDAM利用α報文建立客戶端與資源中心服務器的連接，交互過程如下：
a)客戶端發送α報文給UDAM資源服務器
b)UDAM資源服務器與客戶端建立TCP連接，並將所有資源服務器信息發送給客戶端，注意，此處UDAM會將最新的資源中心列表發送給客戶端。但Zookeeper的資源服務器列表依賴於自身配置。
c)客戶端發送自己擁有的資源和依賴的資源信息
d)資源服務器發送客戶端所依賴的資源信息，連接建立
Zookeeper的會話保持機制通過客戶端發送的請求來維持，如果客戶端一段時間沒有發送請求，則客戶端會發送PING請求來保持會話。這個心跳機制也保證了服務器端了解客戶端的生存狀態。(分析：UDAM沒有使用Session id作為連接標識，它使用客戶端發送的β報文來行使心跳的功能。由於β報文是以UDP的方式發送的，在服務器端超時未收到β報文的時候，資源服務器會發起TCP連接，以保證客戶端的報文不是由於UDP丟包而導致。此處Chubby的實現方式不一樣，Chubby利用KeepAlives來保持會話，但它利用KeepAlives返回包傳遞服務器事件等信息。Zookeeper沒有使用ping返回包攜帶數據信息，但也是靠客戶端發起獲取資源的請求。這兩種方式對於穿透單向防火牆有幫助。UDAM客戶端需要監聽特定端口來捕獲資源服務器發起的連接。)
當連接成功建立以後，有兩種情況可以導致客戶端產生失去連接錯誤。
a) 對於一個已失效(不合法)的會話的操作
b)客戶端與Zookeeper服務器斷開連接，但仍有未完成的異步請求。
2.5 Zookeeper監視機制
Zookeeper中的各種讀請求，如getDate()，getChildren()，和exists()，都可以選擇加“監視點”(watch)。“監視點”指的是一種一次性的觸發器(trigger)，當受監視的數據發生變化時，該觸發器會通知客戶端。
監視機制有三個關鍵點：
a) “監視點”是一次性的，當觸發過一次之後，除非重新設置，新的數據變化不會提醒客戶端。
b)“監視點”將數據改變的通知客戶端。如果數據改變是客戶端A引起的，不能保證“監視點”通知事件會在引發數據修改的函數返回前到達客戶端A。對於“監視點”，Zookeeper有如下保證：客戶端一定是在接收到“監視”事件(watch event)之後才接收到數據的改變信息。
c)getData() 和exists()設置關於節點數據的“監視點”，並返回節點數據信息;getChildren()設置關於子節點的“監視點”，並返回子節點信息。setData()會觸發關於節點數據的“監視點”。成功的create()會觸發所建立節點的數據“監視點”，和父節點的子節點“監視點”。成功的delete()會觸發所刪除節點的數據“監視點”，和父節點的子節點“監視點”。
“監視點”保留在Zookeeper服務器上，則當客戶端連接到新的Zookeeper服務器上時，所有需要被觸發的相關“監視點”都會被觸發。當客戶端斷線後重連，與它的相關的“監視點”都會自動重新注冊，這對客戶端來說是透明的。在以下情況，“監視點”會被錯過：客戶端B設置了關於節點A存在性的“監視點”，但B斷線了，在B斷線過程中節點A被創建又被刪除。此時，B再連線後不知道A節點曾經被創建過。
(分析：UDAM的資源修改提醒機制實現邏輯如下：
a) 模塊A在修改後重啟時利用α報文通知UDAM資源中心
b)資源中心確認並與模塊A進行數據交互
c)資源中心將所有依賴於模塊A的資源標記為不可用，有一個單獨的定時線程掃描所有資源，並與這些不可用資源通信，以達到更新數據的目的。)
Zookeeper的“監視”機制保證以下幾點：
a) “監視”事件的觸發順序和分發順序與事件觸發的順序一致。
b) 客戶端將先接收到“監視”事件，然後才收到新的數據
c) “監視”事件觸發的順序與Zookeeper服務器上數據變化的順序一致
關於Zookeeper“監視”機制的注意點：
a) “監視點”是一次性的
b) 由於“監視點”是一次性的，而且，從接收到“監視”事件到設置新“監視點”是有延時的，所以客戶端可能監控不到數據的所有變化
c) 一個監控對象，只會被相關的通知觸發一次。如，一個客戶端設置了關於某個數據點exists和getData的監控，則當該數據被刪除的時候，只會觸發“文件被刪除”的通知。
d) 當客戶端斷開與服務器的連接時，客戶端不再能收到“監視”事件，直到重新獲得連接。所以關於Session的信息將被發送給所有Zookeeper服務器。由於當連接斷開時收不到“監視”時間，所以在這種情況下，模塊行為需要容錯方面的設計。
2.6 Zookeeper基於ACL的訪問控制機制
Zookeeper利用訪問控制鏈機制(Access Control List)控制客戶端訪問數據節點的權限，類似於UNIX文件的訪問控制。但Zookeeper對於用戶類別的區分，不止局限於所有者(owner)、組(group)、所有人(world)三個級別。Zookeeper中，數據節點沒有“所有者”的概念。訪問者利用id標識自己的身份，並獲得與之相應的不同的訪問權限。
Zookeeper支持可配置的認證機制。它利用一個三元組來定義客戶端的訪問權限：(scheme:expression, perms)
其中，scheme定義了expression的含義，如：host:host1.corp.com標識了一個名為host1.corp.com的主機。Perms標識了操作權限，如：(ip:19.22.0.0/16, READ)表示IP地址以19.22開頭的主機有該數據節點的讀權限。
Zookeeper權限定義：
權限描述備注
CREATE有創建子節點的權限
READ有讀取節點數據和子節點列表的權限
WRITE有修改節點數據的權限無創建和刪除子節點的權限
DELETE有刪除子節點的權限
ADMIN有設置節點權限的權限
Zookeeper內置的ACL模式：
模式描述
world所有人
auth已經被認證的用戶
digest通過username:password字符串的md5編碼認證用戶
host匹配主機名後綴，如，host:corp.com匹配host:host1.corp.com, host:host2.corp.com，但不能匹配host:host1.store.com
ip通過IP識別用戶，表達式格式為 addr/bits
2.7 Zookeeper一致性保證
a) 序列一致性：客戶端發送的更新將按序在Zookeeper進行更新
b)原子一致性：更新只能成功或者失敗，沒有中間狀態
c)單系統鏡像：無論連接哪台Zookeeper服務器，客戶端看到的服務器數據一致
d)可靠性：任何一個更新成功後都會持續生效，直到另一個更新將它覆蓋。可靠性有兩個關鍵點: 第一，當客戶端的更新得到成功的返回值時，可以保證更新已經生效，但在某些異常情況下(超時，連接失敗)，客戶端無法知道更新是否成功;第二，當更新成功後，不會回滾到以前的狀態，即使是在服務器失效重啟之後。
e)實時性：Zookeeper保證客戶端將在一個時間間隔范圍內獲得服務器的更新信息，或者服務器失效的信息。但由於網絡延時等原因，Zookeeper不能保證兩個客戶端能同時得到剛更新的數據，如果需要最新數據，應該在讀數據之前調用sync()接口。
3 利用Zookeeper實現高級分布式應用
利用Zookeeper的會話，監視等機制，可以實現更高級的分布式應用。雖然Zookeeper的事件采用的是異步通知機制，但Zookeeper可以用於實現同步一致的原語操作，其原因是Zookeeper對於更新事件保證了嚴格的全局順序。
3.1 障礙牆(Barriers)
分布式系統利用障礙牆來保證對於一組數據節點的處理被某個條件阻塞。直到條件被滿足的時候，所有數據節點同時開始處理。在Zookeeper中，可以利用一個“障礙牆節點”(算法中使用b表示該節點)來實現這個功能：
1、 客戶端對於該“障礙牆”節點調用exists(b, true)函數，設置watch
2、如果exists()返回false，“障礙牆”節點不存在，客戶端繼續執行
3、如果exists()返回true，客戶端等待“障礙牆”節點的watch事件
4、當watch事件被激發時，跳回1執行
3.2 雙重障礙牆(Double Barriers)
雙重障礙牆用於保證客戶端同步開始和結束某個計算過程。當足夠的客戶端被障礙牆阻擋的時候，計算開始執行。當所有計算都結束的時候，所有客戶端一起脫離障礙牆。利用Zookeeper實現雙重障礙牆的同步機制，在計算啟動之前，客戶端通過在“障礙牆節點”(算法中使用b表示該節點)注冊來加入同步過程。而在計算結束時，客戶端從“障礙牆節點”注銷。
在以下算法代碼中，n是客戶端的Zookeeper名字標識，p標識了一個客戶端，pmax標識了編號最大的一個客戶端，pmin標識了編號最小的一個客戶端。
進入
1、創建名字 n = b + “/” +p
2、設置“監視點”：exists(b + “/ready”, true)
3、創建子節點：create(n, EPHEMERAL)
4、L = getChildren(b, false)
5、如果L中的子節點個數少於x(根據應用配置)，客戶端等待“監視”事件
否則 create(b + “/ready”, REGULAR)
如算法所示，在進入“障礙牆”的過程中，客戶端在“障礙牆”節點下創建代表自己的臨時節點。當最後一個客戶端進入後，它能檢測到“障礙牆”節點已經有x個子節點，此時，該客戶端創建“ready”節點，通知等待“監視”事件的所有客戶端同時開始計算過程。
退出
1、L = getChildren(b, false)
2、如果沒有L中沒有子節點，退出
3、如果p是L中唯一的子節點，delete(n)，並退出
4、如果p是L中編號最小的節點，等待在pmax之上
否則，delete(n)(如果n還存在)，等待在pmin之上
5、跳回1執行
在計算結束，所有客戶端需要刪除各自子節點，並同時離開“障礙牆節點”。注意，在上述退出協議中，最後一個被刪除的子節點是序號最小的子節點，該子節點對應的客戶端將“監視點”設置在當前序號最大子節點上。當該序號最大的子節點被刪除後，繼續選擇當時序號最大的子節點等待。所有其他客戶端都等待在序號最小的子節點上，當該節點被刪除之後，所有其他的客戶端同時離開。
3.3 隊列
利用Zookeeper實現分布式隊列結構，需要創建一個用於維護隊列的數據節點，“隊列節點”。當客戶端需要往隊列裡添加成員的時候，調用create()函數，並設置“序列(sequence)”和“暫時性(ephemeral)”選項，並以“queue-”為節點名前綴，則由於序列屬性的作用，創建的子節點都以“queue-X”為名，且X為一個嚴格增長的數字。處理隊列的客戶端，調用getChildren()，並設置“監視點”。按照序列號從小到大的順序處理子節點。當第一次getChildren()獲得的子節點都處理完了之後，繼續等待“監視點”事件。這樣就實現了分布式環境下的隊列性質。
3.4 優先級隊列
利用Zookeeper實現帶優先級的隊列，只需要簡單地修改普通隊列中節點的命名方式：以“queue-YY”來做隊列元素的前綴，其中YY為節點的優先級，依據Linux的方式，數值越小，優先級越高。並且，處理隊列的客戶端，在處理完一個節點之後，需要調用sync()以保證有優先級高的節點插入時，能夠先獲得處理資源。
3.5 互斥鎖
分布式互斥鎖的定義是在任意時刻，分布式系統中的兩個客戶端不會同時認為自身持有同一個互斥鎖。同樣，首先我們需要定義一個鎖節點，想要獲得鎖的客戶端，按照以下過程操作：
獲得鎖
1、調用create()函數，設置路徑名“_locknode_/lock-”，並且設置“序列(sequence)”和“暫時性(ephemeral)”選項
2、對鎖節點調用getChildren()函數，並不設置“監視點”(注意，此處不能設置“監視點”)
3、如果1中創建的子節點序號是子節點中最小的序號，則該客戶端獲得了互斥鎖，退出
4、對比1中創建的子節點序號小的最大的子節點調用exists()函數，並設置“監視點”
5、如果exists()返回true，等待“監視”事件通知，並跳回2
否則，跳回2
釋放鎖
1、已經獲得鎖的客戶端要釋放鎖的話，只需要刪除之前創建的子節點便可
需要注意的幾點：
1、每次刪除鎖節點的子節點時，只會喚醒一個客戶端。
2、在這個實現方案中不需要輪詢和超時處理
3.6 讀寫鎖
利用Zookeeper實現的讀寫鎖，是在互斥鎖的基礎上實現的。
獲得讀鎖
1、調用create()函數，設置路徑名“_locknode_/read-”，並且設置“序列(sequence)”和“暫時性(ephemeral)”選項
2、對鎖節點調用getChildren()函數，並不設置“監視點”(注意，此處不能設置“監視點”)
3、如果不存在其子節點序號比1中創建的子節點序號小的“write-”子節點，當前的客戶端獲得讀鎖，退出
4、對於序號小於1中創建的子節點序號的“write-”調用exists()，並設置“監視點”
5、如果exists()返回true，等待“監視事件”通知，並跳回2
否則，跳回2
釋放讀鎖
1、刪除客戶端之前創建的子節點
獲得寫鎖
1、調用create()函數，設置路徑名“_locknode_/read-”，並且設置“序列(sequence)”和“暫時性(ephemeral)”選項
2、對鎖節點調用getChildren()函數，並不設置“監視點”(注意，此處不能設置“監視點”)
3、如果1中創建的子節點序號是子節點中最小的序號，則該客戶端獲得了寫鎖，退出
4、對比1中創建的子節點序號小的最大的子節點調用exists()函數，並設置“監視點”
5、如果exists()返回true，等待“監視”事件通知，並跳回2
否則，跳回2
釋放寫鎖
1、刪除客戶端之前創建的子節點
注意，此處實現之中有多個”read-”子節點同時等待在”write-”子節點上，但這樣的設計不會有副作用。這是因為，”read-”子節點在被喚醒的時候，都能獲得處理資源，而不是只有某個或者某些客戶端能繼續執行。
3.7 可恢復(recoverable)的讀寫鎖
通過對讀寫鎖做不大的修改，便可實現簡單的可恢復讀寫鎖(用於防止某些鎖被客戶端長期持有)。方法如下：
無論是在申請讀鎖還是申請寫鎖時，在調用create()之後，立即對於該節點調用getData()並設置“監視點”(注意，如果getData()接收到了create事件，則重新getData()，並設置“監視點”)。getData()用於監視該節點數據中是否出現“unlock”字符串。需要鎖的其他客戶端通過向該節點數據中寫入”unlock”來提醒持有鎖的客戶端釋放鎖。
注意在這個可恢復讀寫鎖的實現機制中，有一個關鍵點，即，持有鎖的“客戶端”必須同意釋放鎖。在很多情況下，持有鎖的客戶端需要保留鎖來進行未完成的操作。
3.8 二階段提交(Two-phased Commit)
二階段提交機制用於保證分布式系統中的客戶端都同意提交或者放棄某事務。
在Zookeeper中，可以在有協調客戶端(coordinator)的基礎上，實現二階段提交機制。首先協調客戶端創建一個事務節點(如：/app/Tx)，為每個參與客戶端建立一個子節點(如：/app/Tx/s_i)，這些子節點的數據為空。當各個參與客戶端接收到協調客戶端發送的事務時，它們別的客戶端對應的節點設置“監視”。並通過寫自己對應的節點的數據來告訴別的客戶端自己是否確認提交事務。需要注意的是，由於很多情況下，只要有一個客戶端不能確認提交，事務就會被丟棄，所以整個處理時間可能很短。
3.9 主服務選擇
利用Zookeeper實現的主服務選擇，有最直觀的一種方式。建立選擇節點”ELECTION/ ”，參與競選主服務功能的各個客戶端在該節點下建立自己對應的節點，並且設置“序列(sequence)”和“暫時性(ephemeral)”選項。序列號最小的節點為主服務。其他非主服務客戶端在主服務節點上設置“監視”，當其失效的時候，由於其“暫時性”，原來序號倒數第二小的節點變為主服務。這個實現有一個問題，就是，多個客戶端同時監視在一個節點的變化，當這個節點發生變化是，所有客戶端都被喚醒。如果客戶端數量龐大的話，會造成Zookeeper服務器的瞬時大壓力。
4 Zookeeper實際應用場景分析
本章初步分析了Zookeeper在NS各產品線中可能的應用場景，主要包括：資源定位、數據庫主從自動調節、和異步作業管理等。
4.1 資源定位
資源定位是目前NS各產品線比較迫切的一個需求。目前，NS各產品線中各個模塊的相互依賴關系完全是由配置文件指定。這種靈活性較差的資源配置方式在遇到以下異常狀況時難於處理：
1、模塊停止服務。當某模塊A停止服務的時候，依賴於該模塊的模塊B仍然會向該模塊請求服務。在最壞的情況下，模塊B能與模塊A建立TCP連接，但由於模塊A實際已經不能處理請求。模塊B會在讀超時後返回。這樣很有可能造成前端UI模塊處理超時，造成穩定性下降。
2、機器更換和遷移。機器更換和遷移對於需要多服務器支持的服務來說是非常平凡的事情。但每次機器更換和遷移都給op帶來大量運維工作。因為，依賴於這些機器上模塊的服務需要修改配置並重啟。
3、服務器死機。服務器死機的情況與模塊停止服務情況類似，由於一台服務器上往往有多種服務提供，服務器死機對服務穩定性的影響更加大。
分析上述情況可以看出，服務穩定性的關鍵在於及時發現已經失效(或者變化)的模塊，並以此更新程序的行為。利用Zookeeper實現資源定位，可以采用以下的結構方式：
/Zookeeper集群名/機房/服務名/資源節點
服務初始化
1、創建初始節點為常規節點，(/Zookeeper集群名/機房/服務名/)
資源注冊
1、當服務啟動的時候，在對應服務名下創建子節點，並且設置“序列(sequence)”和“暫時性(ephemeral)”選項。
2、將資源的位置和相關信息寫入該節點數據
客戶端使用
1、客戶端啟動時，對於”/Zookeeper集群名/機房/服務名/”調用getChildren()，並設置watch
2、將返回結果中各個子節點的信息保存，用於資源的連接
3、客戶端收到watch事件時，重新調用getChildren()，並設置watch
4、用返回結果中的信息更新保存的資源數據
客戶端收到watch事件，可能是以下兩種原因引起：節點增加，即有冗余服務上線;節點減少，某服務失效。在這些情況下，客戶端都可以通過getChildren()調用，獲得最新的可用數據。
4.2 數據庫主從自動調節
數據庫單主問題也是NS部門常常遇到的一個單點情況。為了保證數據的一致性，各種寫操作都是由主庫完成，並同步到其他從庫中去。這樣的單點設計給運行穩定性造成了極大的隱患，如果主庫失效的話，會造成相當一段時間內(OP切主庫操作)用戶的寫庫操作無法響應。解決該問題包括三個方面：
a) 如何迅速發現主庫已經失效
b) 如何快速選擇出新的主庫，並修改各從庫的同步目標
c) 如何讓應用程序得到新的主庫地址
利用Zookeeper來實現數據庫主從的自動管理，可以按照以下方式實現：
主庫選擇和通知
1、 建立MYSQL_ELECTION/ 節點， MARSTER_MYSQL/ 節點，和SLAVE_MYSQL
2、 為每個mysql服務關聯一個Zookeeper proxy，向該節點注冊自己對應的mysql服務
3、 選擇序列號最小的mysql服務為主庫，主庫對應的proxy在MARSTER_MYSQL/下建立序列、暫時性節點，並寫入主庫地址信息
4、 從庫proxy修改對應的同步對象為主庫，並在SLAVE_MYSQL下注冊自己對應節點
5、 當主庫失效時，MARSTER_MYSQL/下節點消失，直到選擇出新的主庫，創建新的主庫信息節點。該主庫刪除自己在SLAVE_MYSQL節點下的注冊
6、 從庫proxy修改對應同步對象為主庫，並在SLAVE_MYSQL下注冊(如果已經注冊，則不需要重新注冊)
應用程序行為
1、 對MARSTER_MYSQL/節點調用getChild()，並設置監視點，依據所獲得的主庫地址，發送更新請求
2、 對SLAVE_MYSQL/節點調用getChild()，並設置監視點，依據所獲得的從庫地址，發送查詢請求
3、 當主庫失效時，watch事件被觸發，此時應用程序暫時停止寫庫操作，調用getChild()，並設置監視，知道MARSTER_MYSQL下出現新的節點為止
4、 當從庫失效時，僅僅更新本地從庫表，並重新設置監視點
4.3 異步作業管理
異步作業管理是Zookeeper系統能夠發揮作用的另一個分布式應用場景。目前，NS部門中PM常提出較為耗時的統計需求，和挖掘需求(如Passport的連連看系統)。此時，異步作業的管理就成為一個問題。目前，NS流行的做法是在程序跑結束的時候，通過郵件將結果發送給發起者。但這樣的做法需要人工進行數據歸類等二次處理。比較理想的一種解決方案是，PM的統計需求能夠直接通過MIS提交並執行，此時可以再Zookeeper的對應節點建立關於該事件的臨時節點，當處理完成後，刪除這個臨時節點。則監視該節點的MIS系統可以很快的收到通知，並自動取回結果，或者進一步處理。一句話，利用Zookeeper來進行異步作業管理，將會使任務處理過程清晰和方便。
5 小結
本文主要從原理和功能方面分析了Zookeeper系統以及它與Google Chubby的一些差異，並穿插討論了Zookeeper與UDAM系統在實現資源定位相關功能上的不同。基本結論如下：Zookeeper實現了與Chubby相近的功能，可以做較復雜的分布式協同工作。可以被用於諸如：資源定位，數據庫主從自動調節，異步作業管理等工作。與UDAM相比，UDAM的優勢在於，更貼近我們現實的資源定位需求，實現更符合Baidu習慣。而Zookeeper的實現更加通用，擴展性更好，並有比較完善的權限管理選擇。
參考資料
[1] The Chubby lock service for loosely-coupled distributed systems
[2] http://en.wikipedia.org/wiki/Paxos_algorithm
[3] http://hadoop.apache.org/zookeeper/
[4] UDAM設計文檔