ZooKeeper原理解析

2020 年 3 月 18 日
筆記

正文

ZooKeeper中的各種角色

ZooKeeper與客戶端

　　每個Server在工作過程中有三種狀態：
　　　　LOOKING：當前Server不知道leader是誰，正在搜尋
　　　　LEADING：當前Server即為選舉出來的leader
　　　　FOLLOWING：leader已經選舉出來，當前Server與之同步

回到頂部

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

回到頂部

Paxos 算法概述（ZAB 協議）

　　Paxos 算法是萊斯利•蘭伯特（英語：Leslie Lamport）於 1990 年提出的一種基於消息傳遞且具有高度容錯特性的一致性算法。

　　分佈式系統中的節點通信存在兩種模型：共享內存（Shared memory）和消息傳遞（Messages passing）。基於消息傳遞通信模型的分佈式系統，不可避免的會發生以下錯誤：進程可能會慢、被殺死或者重啟，消息可能會延遲、丟失、重複，在基礎 Paxos 場景中，先不考慮可能出現消息篡改即拜占庭錯誤（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）的情況。Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一致，保證不論發生以上任何異常，都不會破壞決議一致性。

　　Paxos 算法使用一個希臘故事來描述，在 Paxos 中，存在三種角色，分別為

　　　　Proposer（提議者，用來發出提案 proposal）

　　　　Acceptor（接受者，可以接受或拒絕提案）

　　　　Learner（學習者，學習被選定的提案，當提案被超過半數的 Acceptor 接受後為被批准）

　　下面更精確的定義 Paxos 要解決的問題：

　　　　1、決議(value)只有在被 proposer 提出後才能被批准

　　　　2、在一次 Paxos 算法的執行實例中，只批准(chose)一個 value

　　　　3、learner 只能獲得被批准(chosen)的 value

　　ZooKeeper 的選舉算法有兩種：一種是基於 Basic Paxos（Google Chubby 採用）實現的，另外一種是基於 Fast Paxos（ZooKeeper 採用）算法實現的。系統默認的選舉算法為 Fast Paxos。並且 ZooKeeper 在 3.4.0 版本後只保留了 FastLeaderElection 算法。

　　ZooKeeper 的核心是原子廣播，這個機制保證了各個 Server 之間的同步。實現這個機制的協議叫做 ZAB 協議（Zookeeper Atomic BrodCast）。 ZAB 協議有兩種模式，它們分別是崩潰恢復模式（選主）和原子廣播模式（同步）。

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

　 2、當 ZooKeeper 集群選舉出 leader 同步完狀態退出恢復模式之後，便進入了原子廣播模式。所有的寫請求都被轉發給 leader，再由 leader 將更新 proposal 廣播給 follower

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

　　這裡給大家介紹以下 Basic Paxos 流程：

1、選舉線程由當前 Server 發起選舉的線程擔任，其主要功能是對投票結果進行統計，並選出推薦的 Server

2、選舉線程首先向所有 Server 發起一次詢問(包括自己)

3、選舉線程收到回復後，驗證是否是自己發起的詢問(驗證 zxid 是否一致)，然後獲取對方的 serverid(myid)，並存儲到當前詢問對象列表中，最後獲取對方提議的 leader 相關信息 (serverid,zxid)，並將這些信息存儲到當次選舉的投票記錄表中

4、收到所有 Server 回復以後，就計算出 id 最大的那個 Server，並將這個 Server 相關信息設置成下一次要投票的 Server

5、線程將當前 id 最大的 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

回到頂部

ZooKeeper 的選主機制

選擇機制中的概念

服務器ID

比如有三台服務器，編號分別是1,2,3。

編號越大在選擇算法中的權重越大。

數據ID

服務器中存放的最大數據ID.

值越大說明數據越新，在選舉算法中數據越新權重越大。

邏輯時鐘

或者叫投票的次數，同一輪投票過程中的邏輯時鐘值是相同的。每投完一次票這個數據就會增加，然後與接收到的其它服務器返回的投票信息中的數值相比，根據不同的值做出不同的判斷。

選舉狀態

LOOKING，競選狀態。
FOLLOWING，隨從狀態，同步leader狀態，參與投票。
OBSERVING，觀察狀態,同步leader狀態，不參與投票。
LEADING，領導者狀態。

選舉消息內容

在投票完成後，需要將投票信息發送給集群中的所有服務器，它包含如下內容。

服務器ID
數據ID
邏輯時鐘
選舉狀態

選舉流程圖

因為每個服務器都是獨立的，在啟動時均從初始狀態開始參與選舉，下面是簡易流程圖。

ZooKeeper 的全新集群選主

　　以一個簡單的例子來說明整個選舉的過程：假設有五台服務器組成的 zookeeper 集群，它們的 serverid 從 1-5，同時它們都是最新啟動的，也就是沒有歷史數據，在存放數據量這一點上，都是一樣的。假設這些服務器依序啟動，來看看會發生什麼

　　1、服務器 1 啟動，此時只有它一台服務器啟動了，它發出去的報沒有任何響應，所以它的選舉狀態一直是 LOOKING 狀態

　　2、服務器 2 啟動，它與最開始啟動的服務器 1 進行通信，互相交換自己的選舉結果，由於兩者都沒有歷史數據，所以 id 值較大的服務器 2 勝出，但是由於沒有達到超過半數以上的服務器都同意選舉它(這個例子中的半數以上是 3)，所以服務器 1、2 還是繼續保持 LOOKING 狀態

　 3、服務器 3 啟動，根據前面的理論分析，服務器 3 成為服務器 1,2,3 中的老大，而與上面不同的是，此時有三台服務器(超過半數)選舉了它，所以它成為了這次選舉的 leader

　　4、服務器 4 啟動，根據前面的分析，理論上服務器 4 應該是服務器 1,2,3,4 中最大的，但是由於前面已經有半數以上的服務器選舉了服務器 3，所以它只能接收當小弟的命了

　　5、服務器 5 啟動，同 4 一樣，當小弟

ZooKeeper 的非全新集群選主

　　那麼，初始化的時候，是按照上述的說明進行選舉的，但是當 zookeeper 運行了一段時間之後，有機器 down 掉，重新選舉時，選舉過程就相對複雜了。

　　需要加入數據 version、serverid 和邏輯時鐘。

　　數據 version：數據新的 version 就大，數據每次更新都會更新 version

　　server id：就是我們配置的 myid 中的值，每個機器一個

　　邏輯時鐘：這個值從 0 開始遞增，每次選舉對應一個值，也就是說：如果在同一次選舉中，那麼這個值應該是一致的；邏輯時鐘值越大，說明這一次選舉 leader 的進程更新，也就是每次選舉擁有一個 zxid，投票結果只取 zxid 最新的

　　選舉的標準就變成：

　　　　1、邏輯時鐘小的選舉結果被忽略，重新投票

　　　　2、統一邏輯時鐘後，數據 version 大的勝出

　　　　3、數據 version 相同的情況下，server id 大的勝出

根據這個規則選出 leader。