ZooKeeper的原理（轉）

一、ZooKeeper的角色

領導者（Leader），負責進行投票的發起和決議，更新系統狀態。

學習者（Learner），包括跟隨者（Follower）和觀察者（Observer），Follower用于接受客戶端請求并想客戶端返回結果，在選主過程中參與投票Observer可以接受客戶端連接，將寫請求轉發給Leader，但Observer不參加投票過程，只同步Leader的狀態，Observer的目的是為了擴展系統，提高讀取速度。

客戶端（Client），請求發起方。

ZooKeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現這個機制的協議叫做Zab協議。Zab協議有兩種模式，它們分別是恢復模式（選主）和廣播模式（同步）。當服務啟動或者在領導者崩潰后，Zab就進入了恢復模式，當領導者被選舉出來，且大多數Server完成了和Leader的狀態同步以后，恢復模式就結束了。狀態同步保證了Leader和Server具有相同的系統狀態。

為了保證事務的順序一致性，ZooKeeper采用了遞增的事務id號（zxid）來標識事務。所有的提議（proposal）都在被提出的時候加上了zxid。實現中zxid是一個64位的數字，它高32位是epoch用來標識Leader關系是否改變，每次一個Leader被選出來，它都會有一個新的epoch，標識當前屬于那個Leader的統治時期。低32位用于遞增計數。

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

1. LOOKING：當前Server不知道Leader是誰，正在搜尋
2. LEADING：當前Server即為選舉出來的Leader
3. FOLLOWING：Leader已經選舉出來，當前Server與之同步

二、ZooKeeper的讀寫機制

1、ZooKeeper是一個由多個Server組成的集群

2、一個Leader，多個Follower

3、每個server保存一份數據副本

4、全局數據一致

5、分布式讀寫

6、更新請求轉發，由Leader實施

三、ZooKeeper的保證（Consistency Guarantees）

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

1、順序一致性（Sequential Consistency）：從一個客戶端來的更新請求會被順序執行。

2、原子性（Atomicity）：更新要么成功要么失敗，沒有部分成功的情況。

3、唯一的系統鏡像（Single System Image）：無論客戶端連接到哪個Server，看到系統鏡像是一致的。

4、可靠性（Reliability）：更新一旦有效，持續有效，直到被覆蓋。

5、時間線（Timeliness）：保證在一定的時間內各個客戶端看到的系統信息是一致的。

四、ZooKeeper節點數據操作流程

注：

1. 在Client向Follwer發出一個寫的請求
2. Follwer把請求發送給Leader
3. Leader接收到以后開始發起投票并通知Follwer進行投票
4. Follwer把投票結果發送給Leader
5. Leader將結果匯總后如果需要寫入，則開始寫入同時把寫入操作通知給Leader，然后Commit
6. Follwer把請求結果返回給Client

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結果到客戶端，這個消息最初由客戶端發起，用來強制得到最新的更新。

五、ZooKeeper Leader選舉　　

半數通過：

• 3臺機器掛1臺：2>3/2
• 4臺機器掛2臺：2!>4/2

1、A提案說，我要選自己，B你同意嗎？C你同意嗎？B說，我同意選A；C說，我同意選A。(注意，這里超過半數了，其實在現實世界選舉已經成功了。但是計算機世界是很嚴格，另外要理解算法，要繼續模擬下去。)

2、接著B提案說，我要選自己，A你同意嗎；A說，我已經超半數同意當選，你的提案無效；C說，A已經超半數同意當選，B提案無效。

3、接著C提案說，我要選自己，A你同意嗎；A說，我已經超半數同意當選，你的提案無效；B說，A已經超半數同意當選，C的提案無效。

4、選舉已經產生了Leader，后面的都是Follower，只能服從Leader的命令。而且這里還有個小細節，就是其實誰先啟動誰當頭。

六、zxid

ZNode節點的狀態信息中包含zxid, 那么什么是zxid呢?

ZooKeeper狀態的每一次改變, 都對應著一個遞增的Transaction id, 該id稱為zxid. 由于zxid的遞增性質, 如果zxid1小于zxid2, 那么zxid1肯定先于zxid2發生。

創建任意節點, 或者更新任意節點的數據, 或者刪除任意節點, 都會導致ZooKeeper狀態發生改變, 從而導致zxid的值增加。

七、ZooKeeper工作原理

1、ZooKeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現這個機制的協議叫做Zab協議。Zab協議有兩種模式，它們分別是恢復模式和廣播模式。當服務啟動或者在領導者崩潰后，Zab就進入了恢復模式，當領導者被選舉出來，且大多數server的完成了和Leader的狀態同步以后，恢復模式就結束了。狀態同步保證了Leader和Server具有相同的系統狀態

2、一旦Leader已經和多數的Follower進行了狀態同步后，他就可以開始廣播消息了，即進入廣播狀態。這時候當一個Server加入ZooKeeper服務中，它會在恢復模式下啟動，發現Leader，并和Leader進行狀態同步。待到同步結束，它也參與消息廣播。ZooKeeper服務一直維持在Broadcast狀態，直到Leader崩潰了或者Leader失去了大部分的Followers支持。

3、廣播模式需要保證proposal被按順序處理，因此zk采用了遞增的事務id號（zxid）來保證。所有的提議（proposal）都在被提出的時候加上了zxid。實現中zxid是一個64為的數字，它高32位是epoch用來標識Leader關系是否改變，每次一個Leader被選出來，它都會有一個新的epoch。低32位是個遞增計數。

4、當Leader崩潰或者Leader失去大多數的Follower，這時候zk進入恢復模式，恢復模式需要重新選舉出一個新的Leader，讓所有的Server都恢復到一個正確的狀態。　

5、每個Server啟動以后都詢問其它的Server它要投票給誰。

6、對于其他Server的詢問，Server每次根據自己的狀態都回復自己推薦的Leader的id和上一次處理事務的zxid（系統啟動時每個Server都會推薦自己）

7、收到所有Server回復以后，就計算出zxid最大的哪個Server，并將這個Server相關信息設置成下一次要投票的Server。

8、計算這過程中獲得票數最多的的Sever為獲勝者，如果獲勝者的票數超過半數，則改Server被選為Leader。否則，繼續這個過程，直到Leader被選舉出來　　

9、Leader就會開始等待Server連接

10、Follower連接Leader，將最大的zxid發送給Leader

11、Leader根據Follower的zxid確定同步點

12、完成同步后通知Follower已經成為UPTODATE狀態

13、Follower收到UPTODATE消息后，又可以重新接受Client的請求進行服務了

八、數據一致性與paxos算法　　

據說Paxos算法的難理解與算法的知名度一樣令人敬仰，所以我們先看如何保持數據的一致性，這里有個原則就是：

1. 在一個分布式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那么他們最后能得到一個一致的狀態。
2. Paxos算法解決的什么問題呢，解決的就是保證每個節點執行相同的操作序列。好吧，這還不簡單，master維護一個全局寫隊列，所有寫操作都必須 放入這個隊列編號，那么無論我們寫多少個節點，只要寫操作是按編號來的，就能保證一致性。沒錯，就是這樣，可是如果Master掛了呢。
3. Paxos算法通過投票來對寫操作進行全局編號，同一時刻，只有一個寫操作被批準，同時并發的寫操作要去爭取選票，只有獲得過半數選票的寫操作才會被 批準（所以永遠只會有一個寫操作得到批準），其他的寫操作競爭失敗只好再發起一輪投票，就這樣，在日復一日年復一年的投票中，所有寫操作都被嚴格編號排 序。編號嚴格遞增，當一個節點接受了一個編號為100的寫操作，之后又接受到編號為99的寫操作（因為網絡延遲等很多不可預見原因），它馬上能意識到自己 數據不一致了，自動停止對外服務并重啟同步過程。任何一個節點掛掉都不會影響整個集群的數據一致性（總2n+1臺，除非掛掉大于n臺）。

總結：
ZooKeeper作為Hadoop項目中的一個子項目，是Hadoop集群管理的一個必不可少的模塊，它主要用來控制集群中的數據，如它管理Hadoop集群中的NameNode，還有Hbase中Master Election、Server之間狀態同步等。

關于Paxos算法可以查看文章ZooKeeper全解析——Paxos作為靈魂

推薦書籍：《從Paxos到ZooKeeper分布式一致性原理與實踐》

九、Observer　　

1、ZooKeeper需保證高可用和強一致性；

2、為了支持更多的客戶端，需要增加更多Server；

3、Server增多，投票階段延遲增大，影響性能；

4、權衡伸縮性和高吞吐率，引入Observer

5、Observer不參與投票；

6、Observers接受客戶端的連接，并將寫請求轉發給Leader節點；

7、加入更多Observer節點，提高伸縮性，同時不影響吞吐率

十、?為什么ZooKeeper集群的數目，一般為奇數個？

1、Leader選舉算法采用了Paxos協議；

2、Paxos核心思想：當多數Server寫成功，則任務數據寫成功如果有3個Server，則兩個寫成功即可；如果有4或5個Server，則三個寫成功即可。

3、Server數目一般為奇數（3、5、7）如果有3個Server，則最多允許1個Server掛掉；如果有4個Server，則同樣最多允許1個Server掛掉由此，我們看出3臺服務器和4臺服務器的的容災能力是一樣的，所以為了節省服務器資源，一般我們采用奇數個數，作為服務器部署個數。

十一、ZooKeeper的數據模型　

1、層次化的目錄結構，命名符合常規文件系統規范

2、每個節點在ZooKeeper中叫做znode,并且其有一個唯一的路徑標識

3、節點ZNode可以包含數據和子節點，但是EPHEMERAL類型的節點不能有子節點

4、ZNode中的數據可以有多個版本，比如某一個路徑下存有多個數據版本，那么查詢這個路徑下的數據就需要帶上版本

5、客戶端應用可以在節點上設置監視器

6、節點不支持部分讀寫，而是一次性完整讀寫

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

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

1. 每個子目錄項如NameService都被稱作為ZNode，這個ZNode是被它所在的路徑唯一標識，如Server1這個ZNode的標識為/NameService/Server1。
2. ZNode可以有子節點目錄，并且每個ZNode可以存儲數據，注意EPHEMERAL（臨時的）類型的目錄節點不能有子節點目錄。
3. ZNode是有版本的（version），每個znode中存儲的數據可以有多個版本，也就是一個訪問路徑中可以存儲多份數據，version號自動增加。
4. ZNode可以是臨時節點（EPHEMERAL），可以是持久節點（PERSISTENT）。如果創建的是臨時節點，一旦創建這個EPHEMERALznode的客戶端與服務器失去聯系，這個ZNode也將自動刪除，ZooKeeper的客戶端和服務器通信采用長連接方式，每個客戶端和服務器通過心跳來保持連接，這個連接狀態稱為Session，如果ZNode是臨時節點，這個Session失效，ZNode也就刪除了。
5. ZNode的目錄名可以自動編號，如App1已經存在，再創建的話，將會自動命名為App2。
6. ZNode可以被監控，包括這個目錄節點中存儲的數據的修改，子節點目錄的變化等，一旦變化可以通知設置監控的客戶端，這個是ZooKeeper的核心特性，ZooKeeper的很多功能都是基于這個特性實現的。
7. zxid：每次對ZooKeeper的狀態的改變都會產生一個zxid（ZooKeeper Transaction Id），zxid是全局有序的，如果zxid1小于zxid2，則zxid1在zxid2之前發生。

十二、ZooKeeper的節點

1、ZNode有兩種類型，短暫的（ephemeral）和持久的（persistent）

2、ZNode的類型在創建時確定并且之后不能再修改

3、短暫zNode的客戶端會話結束時，ZooKeeper會將該短暫ZNode刪除，短暫ZNode不可以有子節點

4、持久ZNode不依賴于客戶端會話，只有當客戶端明確要刪除該持久ZNode時才會被刪除

5、ZNode有四種形式的目錄節點

6、PERSISTENT（持久的）

7、EPHEMERAL（暫時的）

8、PERSISTENT_SEQUENTIAL（持久化順序編號目錄節點）

9、EPHEMERAL_SEQUENTIAL（暫時化順序編號目錄節點）

十三、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的三個關鍵點：

1、（一次性觸發）One-time trigger

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

2、（發送至客戶端）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）。網絡延遲或者其他因素可能導致不同的客戶端在不同的時刻感知某一監視事件，但是不同的客戶端所看到的一切具有一致的順序。

3、（被設置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服務器后也得不到事件通知。

十五、Zab: Broadcasting State Updates

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

1. Leader給所有的follower發送一個PROPOSAL消息。
2. 一個follower接收到這次PROPOSAL消息，寫到磁盤，發送給leader一個ACK消息，告知已經收到。
3. 當Leader收到法定人數（quorum）的Follower的ACK時候，發送Commit消息執行。

Zab協議保證：

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

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

Never forget delivered messages

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

Let go of messages that are skipped

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

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

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

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

十六、ZooKeeper寫流程：

客戶端首先和一個Server或者Observe（可以認為是一個Server的代理）通信，發起寫請求，然后Server將寫請求轉發給Leader，Leader再將寫請求轉發給其他Server，Server在接收到寫請求后寫入數據并相應Leader，Leader在接收到大多數寫成功回應后，認為數據寫成功，相應Client。

ZooKeeper的寫數據流程主要分為以下幾步：

1. 比如Client向ZooKeeper的Server1上寫數據，發送一個寫請求。
2. 如果Server1不是Leader，那么Server1 會把接受到的請求進一步轉發給Leader，因為每個ZooKeeper的Server里面有一個是Leader。這個Leader會將寫請求廣播給各個Server，比如Server1和Server2， 各個Server寫成功后就會通知Leader。
3. 當Leader收到大多數Server數據寫成功了，那么就說明數據寫成功了。如果這里三個節點的話，只要有兩個節點數據寫成功了，那么就認為數據寫成功了。寫成功之后，Leader會告訴Server1數據寫成功了。
4. Server1會進一步通知Client數據寫成功了，這時就認為整個寫操作成功。

?

參考：

http://www.cnblogs.com/raphael5200/p/5285583.html（以上內容大部分轉自此篇文章）

http://www.cnblogs.com/lpshou/archive/2013/06/14/3136738.html

http://www.cnblogs.com/edison2012/p/5654011.html（以上內容小部分轉自此篇文章）

http://blog.csdn.net/u010330043/article/details/51209939（以上內容小部分轉自此篇文章）

http://blog.csdn.net/xuxiuning/article/details/51218941

http://cailin.iteye.com/blog/2014486/

http://blog.chinaunix.net/uid-13875633-id-4551483.html

http://www.cnblogs.com/xubiao/p/5551426.html

http://blog.csdn.net/xlgen157387/article/details/53572760

http://zhengchao730.iteye.com/blog/1839755

http://blog.chinaunix.net/uid-26748613-id-4536290.html

http://liufengyi2006123-sina-com.iteye.com/blog/1886255