一、Zookeeper是什么

Zookeeper是一個(gè)分布式協(xié)調(diào)服務(wù)，可用于服務(wù)發(fā)現(xiàn)，分布式鎖，分布式領(lǐng)導(dǎo)選舉，配置管理等。

這一切的基礎(chǔ)，都是Zookeeper提供了一個(gè)類似于Linux文件系統(tǒng)的樹形結(jié)構(gòu)(可認(rèn)為是輕量級(jí)的內(nèi)存文件系統(tǒng)，但只適合存少量信息，完全不適合存儲(chǔ)大量文件或者大文件)，同時(shí)提供了對(duì)于每個(gè)節(jié)點(diǎn)的監(jiān)控與通知機(jī)制。

既然是一個(gè)文件系統(tǒng)，就不得不提Zookeeper是如何保證數(shù)據(jù)的一致性的。本文將介紹Zookeeper如何保證數(shù)據(jù)一致性，如何進(jìn)行領(lǐng)導(dǎo)選舉，以及數(shù)據(jù)監(jiān)控/通知機(jī)制的語義保證。

二、Zookeeper架構(gòu)

1. 角色

Zookeeper集群是一個(gè)基于主從復(fù)制的高可用集群，每個(gè)服務(wù)器承擔(dān)如下三種角色中的一種

• Leader 一個(gè)Zookeeper集群同一時(shí)間只會(huì)有一個(gè)實(shí)際工作的Leader，它會(huì)發(fā)起并維護(hù)與各Follwer及Observer間的心跳。所有的寫操作必須要通過Leader完成再由Leader將寫操作廣播給其它服務(wù)器。
• Follower 一個(gè)Zookeeper集群可能同時(shí)存在多個(gè)Follower，它會(huì)響應(yīng)Leader的心跳。Follower可直接處理并返回客戶端的讀請(qǐng)求，同時(shí)會(huì)將寫請(qǐng)求轉(zhuǎn)發(fā)給Leader處理，并且負(fù)責(zé)在Leader處理寫請(qǐng)求時(shí)對(duì)請(qǐng)求進(jìn)行投票。
• Observer 角色與Follower類似，但是無投票權(quán)。

2. 原子廣播(ZAB)

為了保證寫操作的一致性與可用性，Zookeeper專門設(shè)計(jì)了一種名為原子廣播(ZAB)的支持崩潰恢復(fù)的一致性協(xié)議?；谠搮f(xié)議，Zookeeper實(shí)現(xiàn)了一種主從模式的系統(tǒng)架構(gòu)來保持集群中各個(gè)副本之間的數(shù)據(jù)一致性。

根據(jù)ZAB協(xié)議，所有的寫操作都必須通過Leader完成，Leader寫入本地日志后再復(fù)制到所有的Follower節(jié)點(diǎn)。

一旦Leader節(jié)點(diǎn)無法工作，ZAB協(xié)議能夠自動(dòng)從Follower節(jié)點(diǎn)中重新選出一個(gè)合適的替代者，即新的Leader，該過程即為領(lǐng)導(dǎo)選舉。該領(lǐng)導(dǎo)選舉過程，是ZAB協(xié)議中最為重要和復(fù)雜的過程。

3. 寫操作

(1) 寫Leader

通過Leader進(jìn)行寫操作流程如下圖所示

由上圖可見，通過Leader進(jìn)行寫操作，主要分為五步：

1. 客戶端向Leader發(fā)起寫請(qǐng)求
2. Leader將寫請(qǐng)求以Proposal的形式發(fā)給所有Follower并等待ACK
3. Follower收到Leader的Proposal后返回ACK
4. Leader得到過半數(shù)的ACK(Leader對(duì)自己默認(rèn)有一個(gè)ACK)后向所有的Follower和Observer發(fā)送Commmit
5. Leader將處理結(jié)果返回給客戶端

這里要注意

• Leader并不需要得到Observer的ACK，即Observer無投票權(quán)
• Leader不需要得到所有Follower的ACK，只要收到過半的ACK即可，同時(shí)Leader本身對(duì)自己有一個(gè)ACK。上圖中有4個(gè)Follower，只需其中兩個(gè)返回ACK即可，因?yàn)?2+1) / (4+1) > 1/2
• Observer雖然無投票權(quán)，但仍須同步Leader的數(shù)據(jù)從而在處理讀請(qǐng)求時(shí)可以返回盡可能新的數(shù)據(jù)

(2) 寫Follower/Observer

通過Follower/Observer進(jìn)行寫操作流程如下圖所示：

從上圖可見

• Follower/Observer均可接受寫請(qǐng)求，但不能直接處理，而需要將寫請(qǐng)求轉(zhuǎn)發(fā)給Leader處理
• 除了多了一步請(qǐng)求轉(zhuǎn)發(fā)，其它流程與直接寫Leader無任何區(qū)別

4. 讀操作

Leader/Follower/Observer都可直接處理讀請(qǐng)求，從本地內(nèi)存中讀取數(shù)據(jù)并返回給客戶端即可。

由于處理讀請(qǐng)求不需要服務(wù)器之間的交互，F(xiàn)ollower/Observer越多，整體可處理的讀請(qǐng)求量越大，也即讀性能越好。

三、FastLeaderElection原理

1. 術(shù)語介紹

(1) myid

每個(gè)Zookeeper服務(wù)器，都需要在數(shù)據(jù)文件夾下創(chuàng)建一個(gè)名為myid的文件，該文件包含整個(gè)Zookeeper集群唯一的ID(整數(shù))。例如某Zookeeper集群包含三臺(tái)服務(wù)器，hostname分別為zoo1、zoo2和zoo3，其myid分別為1、2和3，則在配置文件中其ID與hostname必須一一對(duì)應(yīng)，如下所示。在該配置文件中，server.后面的數(shù)據(jù)即為myid

server.1=zoo1:2888:3888 
server.2=zoo2:2888:3888 
server.3=zoo3:2888:3888 

(2) zxid

類似于RDBMS中的事務(wù)ID，用于標(biāo)識(shí)一次更新操作的Proposal ID。為了保證順序性，該zkid必須單調(diào)遞增。因此Zookeeper使用一個(gè)64位的數(shù)來表示，高32位是Leader的epoch，從1開始，每次選出新的Leader，epoch加一。低32位為該epoch內(nèi)的序號(hào)，每次epoch變化，都將低32位的序號(hào)重置。這樣保證了zkid的全局遞增性。

2. 支持的領(lǐng)導(dǎo)選舉算法

可通過electionAlg配置項(xiàng)設(shè)置Zookeeper用于領(lǐng)導(dǎo)選舉的算法。

到3.4.10版本為止，可選項(xiàng)有

• 基于UDP的LeaderElection
• 基于UDP的FastLeaderElection
• 基于UDP和認(rèn)證的FastLeaderElection
• 基于TCP的FastLeaderElection

在3.4.10版本中，默認(rèn)值為3，也即基于TCP的FastLeaderElection。另外三種算法已經(jīng)被棄用，并且有計(jì)劃在之后的版本中將它們徹底刪除而不再支持。

3. FastLeaderElection

FastLeaderElection選舉算法是標(biāo)準(zhǔn)的Fast Paxos算法實(shí)現(xiàn)，可解決LeaderElection選舉算法收斂速度慢的問題。

4. 服務(wù)器狀態(tài)

• LOOKING 不確定Leader狀態(tài)。該狀態(tài)下的服務(wù)器認(rèn)為當(dāng)前集群中沒有Leader，會(huì)發(fā)起Leader選舉
• FOLLOWING 跟隨者狀態(tài)。表明當(dāng)前服務(wù)器角色是Follower，并且它知道Leader是誰
• LEADING 領(lǐng)導(dǎo)者狀態(tài)。表明當(dāng)前服務(wù)器角色是Leader，它會(huì)維護(hù)與Follower間的心跳
• OBSERVING 觀察者狀態(tài)。表明當(dāng)前服務(wù)器角色是Observer，與Folower唯一的不同在于不參與選舉，也不參與集群寫操作時(shí)的投票

5. 選票數(shù)據(jù)結(jié)構(gòu)

每個(gè)服務(wù)器在進(jìn)行領(lǐng)導(dǎo)選舉時(shí)，會(huì)發(fā)送如下關(guān)鍵信息

• logicClock 每個(gè)服務(wù)器會(huì)維護(hù)一個(gè)自增的整數(shù)，名為logicClock，它表示這是該服務(wù)器發(fā)起的第多少輪投票
• state 當(dāng)前服務(wù)器的狀態(tài)
• self_id 當(dāng)前服務(wù)器的myid
• self_zxid 當(dāng)前服務(wù)器上所保存的數(shù)據(jù)的最大zxid
• vote_id 被推舉的服務(wù)器的myid
• vote_zxid 被推舉的服務(wù)器上所保存的數(shù)據(jù)的最大zxid

6. 投票流程

(1) 自增選舉輪次

Zookeeper規(guī)定所有有效的投票都必須在同一輪次中。每個(gè)服務(wù)器在開始新一輪投票時(shí)，會(huì)先對(duì)自己維護(hù)的logicClock進(jìn)行自增操作。

(2) 初始化選票

每個(gè)服務(wù)器在廣播自己的選票前，會(huì)將自己的投票箱清空。該投票箱記錄了所收到的選票。例：服務(wù)器2投票給服務(wù)器3，服務(wù)器3投票給服務(wù)器1，則服務(wù)器1的投票箱為(2, 3), (3, 1), (1, 1)。票箱中只會(huì)記錄每一投票者的最后一票，如投票者更新自己的選票，則其它服務(wù)器收到該新選票后會(huì)在自己票箱中更新該服務(wù)器的選票。

(3) 發(fā)送初始化選票

每個(gè)服務(wù)器最開始都是通過廣播把票投給自己。

(4) 接收外部投票

服務(wù)器會(huì)嘗試從其它服務(wù)器獲取投票，并記入自己的投票箱內(nèi)。如果無法獲取任何外部投票，則會(huì)確認(rèn)自己是否與集群中其它服務(wù)器保持著有效連接。如果是，則再次發(fā)送自己的投票;如果否，則馬上與之建立連接。

(5) 判斷選舉輪次

收到外部投票后，首先會(huì)根據(jù)投票信息中所包含的logicClock來進(jìn)行不同處理

• 外部投票的logicClock大于自己的logicClock。說明該服務(wù)器的選舉輪次落后于其它服務(wù)器的選舉輪次，立即清空自己的投票箱并將自己的logicClock更新為收到的logicClock，然后再對(duì)比自己之前的投票與收到的投票以確定是否需要變更自己的投票，最終再次將自己的投票廣播出去。
• 外部投票的logicClock小于自己的logicClock。當(dāng)前服務(wù)器直接忽略該投票，繼續(xù)處理下一個(gè)投票。
• 外部投票的logickClock與自己的相等。當(dāng)時(shí)進(jìn)行選票PK。

(6) 選票PK

選票PK是基于(self_id, self_zxid)與(vote_id, vote_zxid)的對(duì)比

• 外部投票的logicClock大于自己的logicClock，則將自己的logicClock及自己的選票的logicClock變更為收到的logicClock
• 若logicClock一致，則對(duì)比二者的vote_zxid，若外部投票的vote_zxid比較大，則將自己的票中的vote_zxid與vote_myid更新為收到的票中的vote_zxid與vote_myid并廣播出去，另外將收到的票及自己更新后的票放入自己的票箱。如果票箱內(nèi)已存在(self_myid, self_zxid)相同的選票，則直接覆蓋
• 若二者vote_zxid一致，則比較二者的vote_myid，若外部投票的vote_myid比較大，則將自己的票中的vote_myid更新為收到的票中的vote_myid并廣播出去，另外將收到的票及自己更新后的票放入自己的票箱

(7) 統(tǒng)計(jì)選票

如果已經(jīng)確定有過半服務(wù)器認(rèn)可了自己的投票(可能是更新后的投票)，則終止投票。否則繼續(xù)接收其它服務(wù)器的投票。

(8) 更新服務(wù)器狀態(tài)

投票終止后，服務(wù)器開始更新自身狀態(tài)。若過半的票投給了自己，則將自己的服務(wù)器狀態(tài)更新為LEADING，否則將自己的狀態(tài)更新為FOLLOWING

四、幾種領(lǐng)導(dǎo)選舉場景

1. 集群啟動(dòng)領(lǐng)導(dǎo)選舉

(1) 初始投票給自己

集群剛啟動(dòng)時(shí)，所有服務(wù)器的logicClock都為1，zxid都為0。

各服務(wù)器初始化后，都投票給自己，并將自己的一票存入自己的票箱，如下圖所示。

在上圖中，(1, 1, 0)第一位數(shù)代表投出該選票的服務(wù)器的logicClock，第二位數(shù)代表被推薦的服務(wù)器的myid，第三位代表被推薦的服務(wù)器的最大的zxid。由于該步驟中所有選票都投給自己，所以第二位的myid即是自己的myid，第三位的zxid即是自己的zxid。

此時(shí)各自的票箱中只有自己投給自己的一票。

(2) 更新選票

服務(wù)器收到外部投票后，進(jìn)行選票PK，相應(yīng)更新自己的選票并廣播出去，并將合適的選票存入自己的票箱，如下圖所示。

服務(wù)器1收到服務(wù)器2的選票(1, 2, 0)和服務(wù)器3的選票(1, 3, 0)后，由于所有的logicClock都相等，所有的zxid都相等，因此根據(jù)myid判斷應(yīng)該將自己的選票按照服務(wù)器3的選票更新為(1, 3, 0)，并將自己的票箱全部清空，再將服務(wù)器3的選票與自己的選票存入自己的票箱，接著將自己更新后的選票廣播出去。此時(shí)服務(wù)器1票箱內(nèi)的選票為(1, 3)，(3, 3)。

同理，服務(wù)器2收到服務(wù)器3的選票后也將自己的選票更新為(1, 3, 0)并存入票箱然后廣播。此時(shí)服務(wù)器2票箱內(nèi)的選票為(2, 3)，(3, ,3)。

服務(wù)器3根據(jù)上述規(guī)則，無須更新選票，自身的票箱內(nèi)選票仍為(3, 3)。

服務(wù)器1與服務(wù)器2更新后的選票廣播出去后，由于三個(gè)服務(wù)器最新選票都相同，最后三者的票箱內(nèi)都包含三張投給服務(wù)器3的選票。

(3) 根據(jù)選票確定角色

根據(jù)上述選票，三個(gè)服務(wù)器一致認(rèn)為此時(shí)服務(wù)器3應(yīng)該是Leader。因此服務(wù)器1和2都進(jìn)入FOLLOWING狀態(tài)，而服務(wù)器3進(jìn)入LEADING狀態(tài)。之后Leader發(fā)起并維護(hù)與Follower間的心跳。

2. Follower重啟

(1) Follower重啟投票給自己

Follower重啟，或者發(fā)生網(wǎng)絡(luò)分區(qū)后找不到Leader，會(huì)進(jìn)入LOOKING狀態(tài)并發(fā)起新的一輪投票。

(2) 發(fā)現(xiàn)已有Leader后成為Follower

服務(wù)器3收到服務(wù)器1的投票后，將自己的狀態(tài)LEADING以及選票返回給服務(wù)器1。服務(wù)器2收到服務(wù)器1的投票后，將自己的狀態(tài)FOLLOWING及選票返回給服務(wù)器1。此時(shí)服務(wù)器1知道服務(wù)器3是Leader，并且通過服務(wù)器2與服務(wù)器3的選票可以確定服務(wù)器3確實(shí)得到了超過半數(shù)的選票。因此服務(wù)器1進(jìn)入FOLLOWING狀態(tài)。

3. Leader重啟

(1) Follower發(fā)起新投票

Leader(服務(wù)器3)宕機(jī)后，F(xiàn)ollower(服務(wù)器1和2)發(fā)現(xiàn)Leader不工作了，因此進(jìn)入LOOKING狀態(tài)并發(fā)起新的一輪投票，并且都將票投給自己。

(2) 廣播更新選票

服務(wù)器1和2根據(jù)外部投票確定是否要更新自身的選票。這里有兩種情況

• 服務(wù)器1和2的zxid相同。例如在服務(wù)器3宕機(jī)前服務(wù)器1與2完全與之同步。此時(shí)選票的更新主要取決于myid的大小
• 服務(wù)器1和2的zxid不同。在舊Leader宕機(jī)之前，其所主導(dǎo)的寫操作，只需過半服務(wù)器確認(rèn)即可，而不需所有服務(wù)器確認(rèn)。換句話說，服務(wù)器1和2可能一個(gè)與舊Leader同步(即zxid與之相同)另一個(gè)不同步(即zxid比之小)。此時(shí)選票的更新主要取決于誰的zxid較大

在上圖中，服務(wù)器1的zxid為11，而服務(wù)器2的zxid為10，因此服務(wù)器2將自身選票更新為(3, 1, 11)，如下圖所示。

(3) 選出新Leader

經(jīng)過上一步選票更新后，服務(wù)器1與服務(wù)器2均將選票投給服務(wù)器1，因此服務(wù)器2成為Follower，而服務(wù)器1成為新的Leader并維護(hù)與服務(wù)器2的心跳。

(4) 舊Leader恢復(fù)后發(fā)起選舉

舊的Leader恢復(fù)后，進(jìn)入LOOKING狀態(tài)并發(fā)起新一輪領(lǐng)導(dǎo)選舉，并將選票投給自己。此時(shí)服務(wù)器1會(huì)將自己的LEADING狀態(tài)及選票(3, 1, 11)返回給服務(wù)器3，而服務(wù)器2將自己的FOLLOWING狀態(tài)及選票(3, 1, 11)返回給服務(wù)器3。如下圖所示。

(5) 舊Leader成為Follower

服務(wù)器3了解到Leader為服務(wù)器1，且根據(jù)選票了解到服務(wù)器1確實(shí)得到過半服務(wù)器的選票，因此自己進(jìn)入FOLLOWING狀態(tài)。

五、一致性保證

ZAB協(xié)議保證了在Leader選舉的過程中，已經(jīng)被Commit的數(shù)據(jù)不會(huì)丟失，未被Commit的數(shù)據(jù)對(duì)客戶端不可見。

1. Commit過的數(shù)據(jù)不丟失

(1) Failover前狀態(tài)

為更好演示Leader Failover過程，本例中共使用5個(gè)Zookeeper服務(wù)器。A作為Leader，共收到P1、P2、P3三條消息，并且Commit了1和2，且總體順序?yàn)镻1、P2、C1、P3、C2。根據(jù)順序性原則，其它Follower收到的消息的順序肯定與之相同。其中B與A完全同步，C收到P1、P2、C1，D收到P1、P2，E收到P1，如下圖所示。

這里要注意

• 由于A沒有C3，意味著收到P3的服務(wù)器的總個(gè)數(shù)不會(huì)超過一半，也即包含A在內(nèi)最多只有兩臺(tái)服務(wù)器收到P3。在這里A和B收到P3，其它服務(wù)器均未收到P3
• 由于A已寫入C1、C2，說明它已經(jīng)Commit了P1、P2，因此整個(gè)集群有超過一半的服務(wù)器，即最少三個(gè)服務(wù)器收到P1、P2。在這里所有服務(wù)器都收到了P1，除E外其它服務(wù)器也都收到了P2

(2) 選出新Leader

舊Leader也即A宕機(jī)后，其它服務(wù)器根據(jù)上述FastLeaderElection算法選出B作為新的Leader。C、D和E成為Follower且以B為Leader后，會(huì)主動(dòng)將自己最大的zxid發(fā)送給B，B會(huì)將Follower的zxid與自身zxid間的所有被Commit過的消息同步給Follower，如下圖所示。

在上圖中

• P1和P2都被A Commit，因此B會(huì)通過同步保證P1、P2、C1與C2都存在于C、D和E中
• P3由于未被A Commit，同時(shí)幸存的所有服務(wù)器中P3未存在于大多數(shù)據(jù)服務(wù)器中，因此它不會(huì)被同步到其它Follower

(3) 通知Follower可對(duì)外服務(wù)

同步完數(shù)據(jù)后，B會(huì)向D、C和E發(fā)送NEWLEADER命令并等待大多數(shù)服務(wù)器的ACK(下圖中D和E已返回ACK，加上B自身，已經(jīng)占集群的大多數(shù))，然后向所有服務(wù)器廣播UPTODATE命令。收到該命令后的服務(wù)器即可對(duì)外提供服務(wù)。

2. 未Commit過的消息對(duì)客戶端不可見

在上例中，P3未被A Commit過，同時(shí)因?yàn)闆]有過半的服務(wù)器收到P3，因此B也未Commit P3(如果有過半服務(wù)器收到P3，即使A未Commit P3，B會(huì)主動(dòng)Commit P3，即C3)，所以它不會(huì)將P3廣播出去。

具體做法是，B在成為Leader后，先判斷自身未Commit的消息(本例中即P3)是否存在于大多數(shù)服務(wù)器中從而決定是否要將其Commit。然后B可得出自身所包含的被Commit過的消息中的最小zxid(記為min_zxid)與最大zxid(記為max_zxid)。C、D和E向B發(fā)送自身Commit過的最大消息zxid(記為max_zxid)以及未被Commit過的所有消息(記為zxid_set)。B根據(jù)這些信息作出如下操作

• 如果Follower的max_zxid與Leader的max_zxid相等，說明該Follower與Leader完全同步，無須同步任何數(shù)據(jù)
• 如果Follower的max_zxid在Leader的(min_zxid，max_zxid)范圍內(nèi)，Leader會(huì)通過TRUNC命令通知Follower將其zxid_set中大于Follower的max_zxid(如果有)的所有消息全部刪除

上述操作保證了未被Commit過的消息不會(huì)被Commit從而對(duì)外不可見。

上述例子中Follower上并不存在未被Commit的消息。但可考慮這種情況，如果將上述例子中的服務(wù)器數(shù)量從五增加到七，服務(wù)器F包含P1、P2、C1、P3，服務(wù)器G包含P1、P2。此時(shí)服務(wù)器F、A和B都包含P3，但是因?yàn)槠睌?shù)未過半，因此B作為Leader不會(huì)Commit P3，而會(huì)通過TRUNC命令通知F刪除P3。如下圖所示。

六、總結(jié)

• 由于使用主從復(fù)制模式，所有的寫操作都要由Leader主導(dǎo)完成，而讀操作可通過任意節(jié)點(diǎn)完成，因此Zookeeper讀性能遠(yuǎn)好于寫性能，更適合讀多寫少的場景
• 雖然使用主從復(fù)制模式，同一時(shí)間只有一個(gè)Leader，但是Failover機(jī)制保證了集群不存在單點(diǎn)失敗(SPOF)的問題
• ZAB協(xié)議保證了Failover過程中的數(shù)據(jù)一致性
• 服務(wù)器收到數(shù)據(jù)后先寫本地文件再進(jìn)行處理，保證了數(shù)據(jù)的持久性

【本文為51CTO專欄作者“郭俊”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

戳這里，看該作者更多好文