ZooKeeper 分布式資料結構(四)

前面說了ZooKeeper一些基礎性的東西，包括用戶端程式設計架構。這裡我們來探索如何更好的運用ZooKeeper。

開始之前，我想先借用Linus Torvalds(Linux創始人)的一句話。

Bad programmers worry about the code. Good programmers worry about data structures and their relationships

差的程式員關注代碼，好的程式員關注資料結構和資料之間的關系。

與文無關

不管如何，我們能感受到資料結構的重要性，而平時我們開發所涉及到的各種東西，本質還是：

程式=算法+資料結構。資料結構也是程式設計的基礎，我們這裡說如何通過ZooKeeper建構分布式系統，和它涉及的資料結構。

涉及到的資料結構：

• Barrir (障礙)
• Quene (隊列)
• Lock (鎖)
• Leader Selection
• Group MemberShip
• Service Discovery

這是一篇介紹技術的文章，但是裡面一張圖也沒有，捂臉...

Barrier

Barrier中文譯為栅欄，障礙。意思是暫時阻塞部分東西，直到某個條件滿足。比如：“百米賽跑的起跑線，把起跑線當做障礙，大家還不能跑，隻有人到齊了才能跑”。意思就是滿足某個條件之後才能繼續接下來的操作。

可以參考多線程的：CountDownLatch和CyclicBarrir。

使用ZooKeeper算法實作：(使用僞代碼)

1. 首先，建立一個障礙節點 /zk_barrier
2. 如果障礙節點存在的話，也就是系統中是存在某個障礙，需要滿足某個條件的。
3. 用戶端在/zk_barrier節點調用exists()方法，注冊watch事件。
   1. 如果exists()方法傳回為false，也就是條件滿足，用戶端可以進行接下來的操作了。
   2. 如果exists()方法傳回為true,用戶端就等待watch的事件。
4. 當障礙節點需要的條件滿足的時候，負責/zk_barrier節點的用戶端會删除這個節點。
5. 删除節點觸發watch事件，用戶端再次調用exists()方法再障礙節點上。
6. 如果exists()傳回為true的話，用戶端繼續原本的操作，等待條件滿足。

上面的這個結構相對比較簡單，還有種結構用來 鎖住分布式計算的開始和結束，也叫做Double Barrier. 雙重障礙的實作，當節點的數量滿足條件的時候，開始任務，當節點的數量為0的時候，結束任務。

算法實作：

第一部分：

1. 首先建立一個/barrier節點，其餘用戶端在障礙節點上注冊事件，并且在/barrier節點下面建立臨時節點，也就是以/barrier節點為父節點。 新建立的節點一般是用戶端自己的主機名。
2. 用戶端同時注冊一個事件，檢查/barrier/ready節點是否存在。
3. 系統中已經預定義了 N 數字，這個數目為任務開始的最小滿足節點數。節點的數目必須要等于或多與N的時候，才開始任務。

4. 當有新的節點加入的時候，新的節點都擷取一下目前/barrier節點下子節點的數目。注意getChildren沒有設定監聽事件。

   M = getChildren(/barrier, watch=false)

5. 如果M小于N，繼續等待ready節點的出現。
6. 如果M等于N，然後這個用戶端在/barrier節點下建立/barrier/ready節點。

7. 由于之前有節點注冊了監聽事件，每個用戶端都會開始任務。

   第二部分：

8. 用戶端完成它需要完成的任務之後，删除它在/barrier節點下建立的子節點。

9. 删除完之後，用戶端再調用

   M = getChildren(/barrier, watch=true)。

   如果M大于0，用戶端仍然等待通知。

   如果M等于0，用戶端退出。

上面可能有個風險是網絡流量過于龐大，一旦ready節點注冊，它像所有的節點發送通知。有個辦法是每個用戶端注冊ready的下一個最小的序列臨時節點。這樣每次隻有一個節點收到通知。不會一下子所有的節點都被喚醒。

Queue

分布式隊列也是分布式系統中一種非常常見的資料結構，一種比較特殊的隊列叫做。生産者-消費者 隊列。有一個集合，生産者生産的東西存放在這個集合裡面，消費者從集合中拿出東西來消費。它遵守FIFO(先進先出原則)。

直接看僞代碼：

1. 建立一個/QUEUE節點，用作實作隊列的集合。
2. 作為生産者的用戶端，調用create()方法建立名為"queue-"的節點，這個節點是臨時節點，同時是序列節點，并且是/QUEUE的子節點。一般節點名稱像

   queue-N

   。
3. 作為消費者的用戶端，在/QUEUE節點上調用getChildren()方法,同時設定監聽事件。

   M = getChildren(/_QUEUE_, true)

   對子節點排序，拿出數字最小的節點進行消費。然後删除最小的那個節點。

   有可能在删除節點的時候，因為有其它的節點在對這個節點進行通路，導緻删除失敗，這時候我恩需要再次重試删除

4. 消費者的用戶端不斷的從子節點清單中取出節點進行消費，一旦清單中的節點都被消費了。消費者重新調用getChildren方法。
5. 直到getChildren()傳回為空的清單的時候，這意味着/QUEUE節點下沒有更多的節點了。

有更多精力的話可以實作優先級隊列。

注意：建議看一下ZooKeeper官方對這兩種資料結構的實作位址為

http://zookeeper.apache.org/doc/r3.4.6/zookeeperTutorial.html

分布式鎖

分布式鎖也就是意味着在任何時間，系統中最多隻能有一個用戶端持有這把鎖。一般在下面場景的時候有用：

• 寫入共享資料庫或檔案
• 處理I/O請求

簡單描述一下共享鎖：假設在lock-node下同時建立了三個子節點,l1,l2,l3。那麼建立l1的子節點擁有鎖。當用戶端想釋放鎖的時候，隻需要删除l1節點，然後建立l2的用戶端就擁有了鎖，依次類推。

僞代碼實作：

第一部分：擷取鎖

1. 在/locknode下建立子節點，這個節點是 臨時有序的,

   create("/_locknode_/lock-",CreateMode=EPHEMERAL_SEQUENTIAL)

2. 調用getChilren(/locknode/lock-,false)方法，不設定監聽器。
3. 檢查擷取到的節點清單，如果自己建立的節點擁有最小的序号，那麼目前用戶端擁有鎖。退出算法。
4. 調用

   exists("/_locknode_/<最小的節點>, True)

   方法
5. 如果exists傳回為false，那麼重新進行第2步。
6. 如果exists為true，那麼等待存在的這個節點的 watch事件。然後進行第4步。

第二部分：釋放鎖

1. 持有鎖的用戶端删除節點，觸發下一個節點擷取鎖。
2. 比目前節點序号大的程度最小節點将會擷取到鎖。

Leader選取

Leader選取算法有兩個要求：

• 大多數時間内，隻有一個Leader
• 在任何時間内，要麼沒有Leader要麼隻有一個Leader

暫時我們先把Leader選取算法了解為鎖算法，誰擁有了鎖，誰就是Leader。關于Leader選取算法還需要深入分析。

Group Membership 成員關系

組員關系也是分布式系統的核心元件，目的是為了維護服務的可靠性和一緻性。它可以讓組内的任何一個實體知道目前組的狀況，誰加入了進來，誰離開了。

實作起來較為簡單，僞代碼如下：

1. 建立/Membership持久節點，代表成員關系樹
2. 加入組的節點在/Membership節點下建立臨時節點。
3. 所有的組内成員都有注冊/Membership的監聽事件，是以可以知悉/Membership節點下的變化
4. 當有新的節點加入進來，其它的節點會收到通知。當有節點離開，或故障了，ZooKeeper也會自動的删除這個節點，所有的組員也會知道。
5. 當有節點想知道其它節點的狀态。使用getChildren()擷取/Membership節點下的子節點即可。

服務發現

如果有認真看上面的幾種實作，我想大部分人都該了解ZooKeeper的套路了，服務發現，也就是我們要知道提供某個服務的伺服器有哪些。我們去找誰來提供服務。

可以了解為“物以類聚，人以群分”，這樣一群一群的，就變成了上面的成員關系管理。資料庫服務的一組，web服務的一組。檔案伺服器的一組，想要知道這個組内的狀态，擷取這個組的節點就好了。比如web伺服器，可以建立/web_service節點，然後web服務都去這個節點找。

其餘的就不多說了。和成員關系基本一樣

實作

光有理論不去實作怎麼行呢，代碼貼出來一方面不太好講解，程式設計靠的是思想，你把東西想明白了，開發起來才容易，自己都想不明白的事情，又如何指望計算機來幫你處理呢。

關于本次所有涉及的理論部分，實作的地方有兩處：

1. ZooKeeper的github項目實作 https://github.com/apache/zookeeper/tree/master/src/recipes ，它實作了Quene,Lock,Leader Selection
2. Apache Curaror直接給我們封裝好了常用的分布式資料結構，追求快速的話，可以直接使用Apache Curator. maven包為org.apache.curator.curator-recipes，貌似curator也實作了服務發現。感興趣的都可以自己看。

最後

這次主要還是理論偏多，但是大型項目所依賴的也不過是這些基礎的部分。關于ZooKeeper的應用場景，如何使用到這些資料結構的，下面我們再談。

參考

• 《Apache ZooKeeper Essential》
• ZooKeeper官方文檔