Zookeeper：基于Zookeeper的分布式鎖與上司選舉

本文轉發自技術世界，原文連結　http://www.jasongj.com/zookeeper/distributedlock/

1、Zookeeper特點

1.1 Zookeeper節點類型

如上文《Zookeeper架構及FastLeaderElection機制》所述，Zookeeper 提供了一個類似于 Linux 檔案系統的樹形結構。該樹形結構中每個節點被稱為 znode ，可按如下兩個次元分類

• Persist vs. Ephemeral

1. Persist節點，一旦被建立，便不會意外丢失，即使伺服器全部重新開機也依然存在。每個 Persist 節點即可包含資料，也可包含子節點
2. Ephemeral節點，在建立它的用戶端與伺服器間的 Session 結束時自動被删除。伺服器重新開機會導緻 Session 結束，是以 Ephemeral 類型的 znode 此時也會自動删除

• Sequence vs. Non-sequence

1. Non-sequence節點，多個用戶端同時建立同一 Non-sequence 節點時，隻有一個可建立成功，其它均失敗。并且建立出的節點名稱與建立時指定的節點名完全一樣
2. Sequence節點，建立出的節點名在指定的名稱之後帶有10位10進制數的序号。多個用戶端建立同一名稱的節點時，都能建立成功，隻是序号不同

1.2 Zookeeper語義保證

Zookeeper 簡單高效，同時提供如下語義保證，進而使得我們可以利用這些特性提供複雜的服務。

• 順序性　用戶端發起的更新會按發送順序被應用到 Zookeeper 上
• 原子性 更新操作要麼成功要麼失敗，不會出現中間狀态
• 單一系統鏡像　一個用戶端無論連接配接到哪一個伺服器都能看到完全一樣的系統鏡像（即完全一樣的樹形結構）。注：根據上文《Zookeeper架構及FastLeaderElection機制》介紹的 ZAB 協定，寫操作并不保證更新被所有的 Follower 立即确認，是以通過部分 Follower 讀取資料并不能保證讀到最新的資料，而部分 Follwer 及 Leader 可讀到最新資料。如果一定要保證單一系統鏡像，可在讀操作前使用 sync 方法。
• 可靠性　一個更新操作一旦被接受即不會意外丢失，除非被其它更新操作覆寫
• 最終一緻性　寫操作最終（而非立即）會對用戶端可見

1.3 Zookeeper Watch機制

所有對 Zookeeper 的讀操作，都可附帶一個 Watch 。一旦相應的資料有變化，該 Watch 即被觸發。Watch 有如下特點

• 主動推送　Watch被觸發時，由 Zookeeper 伺服器主動将更新推送給用戶端，而不需要用戶端輪詢。
• 一次性　資料變化時，Watch 隻會被觸發一次。如果用戶端想得到後續更新的通知，必須要在 Watch 被觸發後重新注冊一個 Watch。
• 可見性　如果一個用戶端在讀請求中附帶 Watch，Watch 被觸發的同時再次讀取資料，用戶端在得到 Watch 消息之前肯定不可能看到更新後的資料。換句話說，更新通知先于更新結果。
• 順序性　如果多個更新觸發了多個 Watch ，那 Watch 被觸發的順序與更新順序一緻。

2、 分布式鎖與上司選舉關鍵點

2.1 最多一個擷取鎖 / 成為Leader

對于分布式鎖（這裡特指排它鎖）而言，任意時刻，最多隻有一個程序（對于單程序内的鎖而言是單線程）可以獲得鎖。

對于上司選舉而言，任意時間，最多隻有一個成功當選為Leader。否則即出現腦裂（Split brain）

2.2 鎖重入 / 确認自己是Leader

對于分布式鎖，需要保證獲得鎖的程序在釋放鎖之前可再次獲得鎖，即鎖的可重入性。

對于上司選舉，Leader需要能夠确認自己已經獲得上司權，即确認自己是Leader。

2.3 釋放鎖 / 放棄上司權

鎖的獲得者應該能夠正确釋放已經獲得的鎖，并且當獲得鎖的程序當機時，鎖應該自動釋放，進而使得其它競争方可以獲得該鎖，進而避免出現死鎖的狀态。

上司應該可以主動放棄上司權，并且當上司所在程序當機時，上司權應該自動釋放，進而使得其它參與者可重新競争上司而避免進入無主狀态。

2.4 感覺鎖釋放 / 上司權的放棄

當獲得鎖的一方釋放鎖時，其它對于鎖的競争方需要能夠感覺到鎖的釋放，并再次嘗試擷取鎖。

原來的Leader放棄上司權時，其它參與方應該能夠感覺該事件，并重新發起選舉流程。

3、非公平上司選舉

從上面幾個方面可見，分布式鎖與上司選舉的技術要點非常相似，實際上其實作機制也相近。本章就以上司選舉為例來說明二者的實作原理，分布式鎖的實作原理也幾乎一緻。

3.1 選主過程

假設有三個Zookeeper的用戶端，如下圖所示，同時競争Leader。這三個用戶端同時向Zookeeper叢集注冊Ephemeral且Non-sequence類型的節點，路徑都為/zkroot/leader（工程實踐中，路徑名可自定義）。

如上圖所示，由于是Non-sequence節點，這三個用戶端隻會有一個建立成功，其它節點均建立失敗。

此時，建立成功的用戶端（即上圖中的Client 1）即成功競選為 Leader 。其它用戶端（即上圖中的Client 2和Client 3）此時均為 Follower。

3.2 放棄上司權

如果 Leader 打算主動放棄上司權，直接删除/zkroot/leader節點即可。

如果 Leader 程序意外當機，其與 Zookeeper 間的 Session 也結束，該節點由于是Ephemeral類型的節點，是以也會自動被删除。

此時/zkroot/leader節點不複存在，對于其它參與競選的用戶端而言，之前的 Leader 已經放棄了上司權。

3.3 感覺上司權的放棄

由上圖可見，建立節點失敗的節點，除了成為 Follower 以外，還會向/zkroot/leader注冊一個 Watch ，一旦 Leader 放棄上司權，也即該節點被删除，所有的 Follower 會收到通知。

3.4 重新選舉

感覺到舊 Leader 放棄上司權後，所有的 Follower 可以再次發起新一輪的上司選舉，如下圖所示。

從上圖中可見

• 新一輪的上司選舉方法與最初的上司選舉方法完全一樣，都是發起節點建立請求，建立成功即為 Leader，否則為 Follower ，且 Follower 會 Watch 該節點
• 新一輪的選舉結果，無法預測，與它們在第一輪選舉中的順序無關。這也是該方案被稱為非公平模式的原因

3.5 非公平模式總結

• 非公平模式實作簡單，每一輪選舉方法都完全一樣
• 競争參與方不多的情況下，效率高。每個 Follower 通過 Watch 感覺到節點被删除的時間不完全一樣，隻要有一個 Follower 得到通知即發起競選，即可保證當時有新的 Leader 被選出
• 給Zookeeper 叢集造成的負載大，是以擴充性差。如果有上萬個用戶端都參與競選，意味着同時會有上萬個寫請求發送給 Zookeper。如《Zookeeper架構》一文所述，Zookeeper 存在單點寫的問題，寫性能不高。同時一旦 Leader 放棄上司權，Zookeeper 需要同時通知上萬個 Follower，負載較大。

4、公平上司選舉

4.1 選主過程

如下圖所示，公平上司選舉中，各用戶端均建立/zkroot/leader節點，且其類型為Ephemeral與Sequence。

由于是Sequence類型節點，故上圖中三個用戶端均建立成功，隻是序号不一樣。此時，每個用戶端都會判斷自己建立成功的節點的序号是不是目前最小的。如果是，則該用戶端為 Leader，否則即為 Follower。

在上圖中，Client 1建立的節點序号為 1 ，Client 2建立的節點序号為 2，Client 3建立的節點序号為3。由于最小序号為 1 ，且該節點由Client 1建立，故Client 1為 Leader 。

4.2 放棄上司權

Leader 如果主動放棄上司權，直接删除其建立的節點即可。

如果 Leader 所在程序意外當機，其與 Zookeeper 間的 Session 結束，由于其建立的節點為Ephemeral類型，故該節點自動被删除。

4.3 感覺上司權的放棄

與非公平模式不同，每個 Follower 并非都 Watch 由 Leader 建立出來的節點，而是 Watch 序号剛好比自己序号小的節點。

在上圖中，總共有 1、2、3 共三個節點，是以Client 2 Watch /zkroot/leader1，Client 3 Watch /zkroot/leader2。（注：序号應該是10位數字，而非一位數字，這裡為了友善，以一位數字代替）

一旦 Leader 當機，/zkroot/leader1被删除，Client 2可得到通知。此時Client 3由于 Watch 的是/zkroot/leader2，故不會得到通知。

4.4 重新選舉

Client 2得到/zkroot/leader1被删除的通知後，不會立即成為新的 Leader 。而是先判斷自己的序号 2 是不是目前最小的序号。在該場景下，其序号确為最小。是以Client 2成為新的 Leader 。

這裡要注意，如果在Client 1放棄上司權之前，Client 2就當機了，Client 3會收到通知。此時Client 3不會立即成為Leader，而是要先判斷自己的序号 3 是否為目前最小序号。很顯然，由于Client 1建立的/zkroot/leader1還在，是以Client 3不會成為新的 Leader ，并向Client 2序号 2 前面的序号，也即 1 建立 Watch。該過程如下圖所示。

4.5 公平模式總結

• 實作相對複雜
• 擴充性好，每個用戶端都隻 Watch 一個節點且每次節點被删除隻須通知一個用戶端
• 舊 Leader 放棄上司權時，其它用戶端根據競選的先後順序（也即節點序号）成為新 Leader，這也是公平模式的由來
• 延遲相對非公平模式要高，因為它必須等待特定節點得到通知才能選出新的 Leader

5、總結

基于 Zookeeper 的上司選舉或者分布式鎖的實作均基于 Zookeeper 節點的特性及通知機制。充分利用這些特性，還可以開發出适用于其它場景的分布式應用。