ZooKeeper 是一個針對大型分布式系統的可靠協調系統，提供的功能包括：配置維護、名字服務、分布式同步、組服務等，。

ZooKeeper設計目的

1. 最終一致性：client不論連接到哪個Server，展示給它都是同一個視圖，這是zookeeper最重要的性能。
2. 可靠性：具有簡單、健壯、良好的性能，如果消息m被到一臺服務器接受，那么它將被所有的服務器接受。
3. 實時性：Zookeeper保證客戶端將在一個時間間隔范圍內獲得服務器的更新信息，或者服務器失效的信息。但由于網絡延時等原因，Zookeeper不能保證兩個客戶端能同時得到剛更新的數據，如果需要最新數據，應該在讀數據之前調用sync()接口。
4. 等待無關(wait-free)：慢的或者失效的client不得干預快速的client的請求，使得每個client都能有效的等待。
5. 原子性：更新只能成功或者失敗，沒有中間狀態。
6. 順序性：包括全局有序和偏序兩種：全局有序是指如果在一臺服務器上消息a在消息b前發布，則在所有Server上消息a都將在消息b前被發布;偏序是指如果一個消息b在消息a后被同一個發送者發布，a必將排在b前面。

ZooKeeper數據模型

Zookeeper會維護一個具有層次關系的數據結構，它非常類似于一個標準的文件系統，如圖所示：

Zookeeper這種數據結構有如下這些特點：

1)每個子目錄項如NameService都被稱作為znode，這個znode是被它所在的路徑唯一標識，如Server1這個znode的標識為/NameService/Server1。

2)znode可以有子節點目錄，并且每個znode可以存儲數據，注意EPHEMERAL(臨時的)類型的目錄節點不能有子節點目錄。

3)znode是有版本的(version)，每個znode中存儲的數據可以有多個版本，也就是一個訪問路徑中可以存儲多份數據，version號自動增加。

4)znode的類型：

• Persistent 節點，一旦被創建，便不會意外丟失，即使服務器全部重啟也依然存在。每個 Persist 節點即可包含數據，也可包含子節點。
• Ephemeral 節點，在創建它的客戶端與服務器間的 Session 結束時自動被刪除。服務器重啟會導致 Session 結束，因此 Ephemeral 類型的 znode 此時也會自動刪除。
• Non-sequence 節點，多個客戶端同時創建同一 Non-sequence 節點時，只有一個可創建成功，其它勻失敗。并且創建出的節點名稱與創建時指定的節點名完全一樣。
• Sequence 節點，創建出的節點名在指定的名稱之后帶有10位10進制數的序號。多個客戶端創建同一名稱的節點時，都能創建成功，只是序號不同。

5)znode可以被監控，包括這個目錄節點中存儲的數據的修改，子節點目錄的變化等，一旦變化可以通知設置監控的客戶端，這個是Zookeeper的核心特性，Zookeeper的很多功能都是基于這個特性實現的。

6)ZXID：每次對Zookeeper的狀態的改變都會產生一個zxid(ZooKeeper Transaction Id)，zxid是全局有序的，如果zxid1小于zxid2，則zxid1在zxid2之前發生。

ZooKeeper Session

Client和Zookeeper集群建立連接，整個session狀態變化如圖所示：

如果Client因為Timeout和Zookeeper Server失去連接，client處在CONNECTING狀態，會自動嘗試再去連接Server，如果在session有效期內再次成功連接到某個Server，則回到CONNECTED狀態。

注意：如果因為網絡狀態不好，client和Server失去聯系，client會停留在當前狀態，會嘗試主動再次連接Zookeeper Server。client不能宣稱自己的session expired，session expired是由Zookeeper Server來決定的，client可以選擇自己主動關閉session。

ZooKeeper Watch

Zookeeper watch是一種監聽通知機制。Zookeeper所有的讀操作getData(), getChildren()和 exists()都可以設置監視(watch)，監視事件可以理解為一次性的觸發器

官方定義如下：

a watch event is one-time trigger, sent to the client that set the watch, whichoccurs when the data for which the watch was set changes。

Watch的三個關鍵點：

(一次性觸發)One-time trigger

當設置監視的數據發生改變時，該監視事件會被發送到客戶端，例如，如果客戶端調用了getData(“/znode1”, true) 并且稍后 /znode1 節點上的數據發生了改變或者被刪除了，客戶端將會獲取到 /znode1 發生變化的監視事件，而如果 /znode1 再一次發生了變化，除非客戶端再次對/znode1 設置監視，否則客戶端不會收到事件通知。

(發送至客戶端)Sent to the client

Zookeeper客戶端和服務端是通過 socket 進行通信的，由于網絡存在故障，所以監視事件很有可能不會成功地到達客戶端，監視事件是異步發送至監視者的，Zookeeper 本身提供了順序保證(ordering guarantee)：即客戶端只有首先看到了監視事件后，才會感知到它所設置監視的znode發生了變化(a client will never see a change for which it has set a watch until it first sees the watch event)。

網絡延遲或者其他因素可能導致不同的客戶端在不同的時刻感知某一監視事件，但是不同的客戶端所看到的一切具有一致的順序。

(被設置 watch 的數據)The data for which the watch was set

這意味著znode節點本身具有不同的改變方式。你也可以想象 Zookeeper 維護了兩條監視鏈表：數據監視和子節點監視(data watches and child watches) getData() 和exists()設置數據監視，getChildren()設置子節點監視。或者你也可以想象 Zookeeper 設置的不同監視返回不同的數據，getData() 和 exists() 返回znode節點的相關信息，而getChildren() 返回子節點列表。

因此，setData() 會觸發設置在某一節點上所設置的數據監視(假定數據設置成功)，而一次成功的create() 操作則會出發當前節點上所設置的數據監視以及父節點的子節點監視。一次成功的 delete操作將會觸發當前節點的數據監視和子節點監視事件，同時也會觸發該節點父節點的child watch。

Zookeeper 中的監視是輕量級的，因此容易設置、維護和分發。當客戶端與 Zookeeper 服務器失去聯系時，客戶端并不會收到監視事件的通知，只有當客戶端重新連接后，若在必要的情況下，以前注冊的監視會重新被注冊并觸發，對于開發人員來說這通常是透明的。

只有一種情況會導致監視事件的丟失，即：通過exists()設置了某個znode節點的監視，但是如果某個客戶端在此znode節點被創建和刪除的時間間隔內與zookeeper服務器失去了聯系，該客戶端即使稍后重新連接 zookeeper服務器后也得不到事件通知。

Consistency Guarantees

Zookeeper是一個高效的、可擴展的服務，read和write操作都被設計為快速的，read比write操作更快。

• 順序一致性(Sequential Consistency)：從一個客戶端來的更新請求會被順序執行。
• 原子性(Atomicity)：更新要么成功要么失敗，沒有部分成功的情況。
• 唯一的系統鏡像(Single System Image)：無論客戶端連接到哪個Server，看到系統鏡像是一致的。
• 可靠性(Reliability)：更新一旦有效，持續有效，直到被覆蓋。
• 時間線(Timeliness)：保證在一定的時間內各個客戶端看到的系統信息是一致的。

ZooKeeper的工作原理

在zookeeper的集群中，各個節點共有下面3種角色和4種狀態：

• 角色：leader,follower,observer
• 狀態：leading,following,observing,looking

Zookeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現這個機制的協議叫做Zab協議(ZooKeeper Atomic Broadcast protocol)。Zab協議有兩種模式，它們分別是恢復模式(Recovery選主)和廣播模式(Broadcast同步)。

當服務啟動或者在領導者崩潰后，Zab就進入了恢復模式，當領導者被選舉出來，且大多數Server完成了和leader的狀態同步以后，恢復模式就結束了。狀態同步保證了leader和Server具有相同的系統狀態。

為了保證事務的順序一致性，zookeeper采用了遞增的事務id號(zxid)來標識事務。所有的提議(proposal)都在被提出的時候加上了zxid。

實現中zxid是一個64位的數字，它高32位是epoch用來標識leader關系是否改變，每次一個leader被選出來，它都會有一個新的epoch，標識當前屬于那個leader的統治時期。低32位用于遞增計數。

每個Server在工作過程中有4種狀態：

• LOOKING：當前Server不知道leader是誰，正在搜尋。
• LEADING：當前Server即為選舉出來的leader。
• FOLLOWING：leader已經選舉出來，當前Server與之同步。
• OBSERVING：observer的行為在大多數情況下與follower完全一致，但是他們不參加選舉和投票，而僅僅接受(observing)選舉和投票的結果。

Leader Election

當leader崩潰或者leader失去大多數的follower，這時候zk進入恢復模式，恢復模式需要重新選舉出一個新的leader，讓所有的Server都恢復到一個正確的狀態。Zk的選舉算法有兩種：一種是基于basic paxos實現的，另外一種是基于fast paxos算法實現的。系統默認的選舉算法為fast paxos。先介紹basic paxos流程：

1. 選舉線程由當前Server發起選舉的線程擔任，其主要功能是對投票結果進行統計，并選出推薦的Server;
2. 選舉線程首先向所有Server發起一次詢問(包括自己);
3. 選舉線程收到回復后，驗證是否是自己發起的詢問(驗證zxid是否一致)，然后獲取對方的id(myid)，并存儲到當前詢問對象列表中，最后獲取對方提議的leader相關信息(id,zxid)，并將這些信息存儲到當次選舉的投票記錄表中;
4. 收到所有Server回復以后，就計算出zxid最大的那個Server，并將這個Server相關信息設置成下一次要投票的Server;
5. 線程將當前zxid最大的Server設置為當前Server要推薦的Leader，如果此時獲勝的Server獲得n/2 + 1的Server票數，設置當前推薦的leader為獲勝的Server，將根據獲勝的Server相關信息設置自己的狀態，否則，繼續這個過程，直到leader被選舉出來。

通過流程分析我們可以得出：要使Leader獲得多數Server的支持，則Server總數必須是奇數2n+1，且存活的Server的數目不得少于n+1.

每個Server啟動后都會重復以上流程。在恢復模式下，如果是剛從崩潰狀態恢復的或者剛啟動的server還會從磁盤快照中恢復數據和會話信息，zk會記錄事務日志并定期進行快照，方便在恢復時進行狀態恢復。

fast paxos流程是在選舉過程中，某Server首先向所有Server提議自己要成為leader，當其它Server收到提議以后，解決epoch和zxid的沖突，并接受對方的提議，然后向對方發送接受提議完成的消息，重復這個流程，最后一定能選舉出Leader。

Leader工作流程

Leader主要有三個功能：

1. 恢復數據;
2. 維持與follower的心跳，接收follower請求并判斷follower的請求消息類型;
3. follower的消息類型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根據不同的消息類型，進行不同的處理。

說明：

PING消息是指follower的心跳信息;REQUEST消息是follower發送的提議信息，包括寫請求及同步請求;

ACK消息是follower的對提議的回復，超過半數的follower通過，則commit該提議;

REVALIDATE消息是用來延長SESSION有效時間。

Follower工作流程

Follower主要有四個功能：

1. 向Leader發送請求(PING消息、REQUEST消息、ACK消息、REVALIDATE消息);
2. 接收Leader消息并進行處理;
3. 接收Client的請求，如果為寫請求，發送給Leader進行投票;
4. 返回Client結果。

Follower的消息循環處理如下幾種來自Leader的消息：

1. PING消息：心跳消息
2. PROPOSAL消息：Leader發起的提案，要求Follower投票
3. COMMIT消息：服務器端最新一次提案的信息
4. UPTODATE消息：表明同步完成
5. REVALIDATE消息：根據Leader的REVALIDATE結果，關閉待revalidate的session還是允許其接受消息
6. SYNC消息：返回SYNC結果到客戶端，這個消息最初由客戶端發起，用來強制得到最新的更新。

Zab: Broadcasting State Updates

Zookeeper Server接收到一次request，如果是follower，會轉發給leader，Leader執行請求并通過Transaction的形式廣播這次執行。Zookeeper集群如何決定一個Transaction是否被commit執行?通過“兩段提交協議”(a two-phase commit)：

• Leader給所有的follower發送一個PROPOSAL消息。
• 一個follower接收到這次PROPOSAL消息，寫到磁盤，發送給leader一個ACK消息，告知已經收到。
• 當Leader收到法定人數(quorum)的follower的ACK時候，發送commit消息執行。

Zab協議保證：

• 如果leader以T1和T2的順序廣播，那么所有的Server必須先執行T1，再執行T2。
• 如果任意一個Server以T1、T2的順序commit執行，其他所有的Server也必須以T1、T2的順序執行。

“兩段提交協議”最大的問題是如果Leader發送了PROPOSAL消息后crash或暫時失去連接，會導致整個集群處在一種不確定的狀態(follower不知道該放棄這次提交還是執行提交)。Zookeeper這時會選出新的leader，請求處理也會移到新的leader上，不同的leader由不同的epoch標識。切換Leader時，需要解決下面兩個問題：

1. Never forget delivered messages

Leader在COMMIT投遞到任何一臺follower之前crash，只有它自己commit了。新Leader必須保證這個事務也必須commit。

2. Let go of messages that are skipped

Leader產生某個proposal，但是在crash之前，沒有follower看到這個proposal。該server恢復時，必須丟棄這個proposal。

Zookeeper會盡量保證不會同時有2個活動的Leader，因為2個不同的Leader會導致集群處在一種不一致的狀態，所以Zab協議同時保證：

• 在新的leader廣播Transaction之前，先前Leader commit的Transaction都會先執行。
• 在任意時刻，都不會有2個Server同時有法定人數(quorum)的支持者。

這里的quorum是一半以上的Server數目，確切的說是有投票權力的Server(不包括Observer)。