面試官：ZooKeeper 是強(qiáng)一致的嗎？

每天 11 點(diǎn)更新文章，餓了點(diǎn)外賣(mài)，點(diǎn)擊 ??《無(wú)門(mén)檻外賣(mài)優(yōu)惠券，每天免費(fèi)領(lǐng)！》

Zookeeper通過(guò)ZAB保證分布式事務(wù)的最終一致性。

ZAB全稱(chēng)Zookeeper Atomic Broadcast（ZAB，Zookeeper原子消息廣播協(xié)議）

1. ZAB是一種專(zhuān)門(mén)為Zookeeper設(shè)計(jì)的一種支持?崩潰恢復(fù)?的?原子廣播協(xié)議?，是Zookeeper保證數(shù)據(jù)一致性的核心算法。ZAB借鑒了Paxos算法，但它不是通用的一致性算法，是特別為Zookeeper設(shè)計(jì)的。
2. 基于ZAB協(xié)議，Zookeeper實(shí)現(xiàn)了?種主備模式的系統(tǒng)架構(gòu)來(lái)保持集群中各副本之間的數(shù)據(jù)的?致性，表現(xiàn)形式就是使??個(gè)單?的主進(jìn)程（Leader服務(wù)器）來(lái)接收并處理客戶(hù)端的所有事務(wù)請(qǐng)求（寫(xiě)請(qǐng)求），并采?ZAB的原??播協(xié)議，將服務(wù)器數(shù)據(jù)的狀態(tài)變更為事務(wù) Proposal的形式?播到所有的Follower進(jìn)程中。

問(wèn)題提出

• 主從架構(gòu)下，leader 崩潰，數(shù)據(jù)一致性怎么保證？
• 選舉 leader 的時(shí)候，整個(gè)集群無(wú)法處理寫(xiě)請(qǐng)求的，如何快速進(jìn)行 leader 選舉？

ZAB過(guò)程

ZAB協(xié)議的核?是?定義了對(duì)于那些會(huì)改變Zookeeper服務(wù)器數(shù)據(jù)狀態(tài)的事務(wù)請(qǐng)求的處理?式

所有事務(wù)必須由一個(gè)?全局唯一的服務(wù)器來(lái)協(xié)調(diào)處理?，這樣的服務(wù)器被稱(chēng)為L(zhǎng)eader服務(wù)器，余下的服務(wù)器則稱(chēng)為Follower服務(wù)器

1. Leader服務(wù)器負(fù)責(zé)將一個(gè)客戶(hù)端事務(wù)請(qǐng)求轉(zhuǎn)化為一個(gè)事務(wù)Proposal（提案），并將該P(yáng)roposal分發(fā)給集群中所有的Follower服務(wù)器
2. Leader服務(wù)器等待所有Follower服務(wù)器的反饋，一旦超過(guò)半數(shù)的Follower服務(wù)器進(jìn)行了正確的反饋后，Leader就會(huì)向所有的Follower服務(wù)器發(fā)送Commit消息，要求將前一個(gè)Proposal進(jìn)行提交。

ZAB協(xié)議內(nèi)容簡(jiǎn)介

ZAB協(xié)議包括兩種基本的模式：?崩潰恢復(fù)?和?消息廣播

消息廣播

當(dāng)集群中有過(guò)半的Follower服務(wù)器完成了和Leader服務(wù)器的狀態(tài)同步，那么整個(gè)服務(wù)框架就可以進(jìn)入?消息廣播模式?。

當(dāng)一臺(tái)遵守ZAB協(xié)議的服務(wù)器啟動(dòng)后加入到集群中，如果此時(shí)集群中已經(jīng)存在一個(gè)Leader服務(wù)器在負(fù)責(zé)進(jìn)行消息廣播，那么加入的服務(wù)器會(huì)自覺(jué)的進(jìn)入?數(shù)據(jù)恢復(fù)模式：找到Leader 所在的服務(wù)器，并與其進(jìn)?數(shù)據(jù)同步，數(shù)據(jù)同步完成后參與到消息?播流程中。

ZAB協(xié)議的消息廣播使用原子廣播協(xié)議，?類(lèi)似一個(gè)二階段提交的過(guò)程?，但又有所不同。

1. 二階段提交中，需要所有參與者反饋ACK后再發(fā)送Commit請(qǐng)求。要求所有參與者要么成功，要么失敗。這樣會(huì)產(chǎn)生嚴(yán)重的阻塞問(wèn)題
2. ZAB協(xié)議中，Leader等待半數(shù)以上的Follower成功反饋ACK即可，不需要收到全部的Follower反饋ACK。

消息廣播過(guò)程：

1. 客戶(hù)端發(fā)起寫(xiě)請(qǐng)求
2. Leader將客戶(hù)端請(qǐng)求信息轉(zhuǎn)化為事務(wù)Proposal，同時(shí)為每個(gè)Proposal分配一個(gè)事務(wù)ID（Zxid）
3. Leader為每個(gè)Follower單獨(dú)分配一個(gè)FIFO的隊(duì)列，將需要廣播的Proposal依次放入到隊(duì)列中
4. Follower接收到Proposal后，首先將其以事務(wù)日志的方式寫(xiě)入到本地磁盤(pán)中，寫(xiě)入成功后給Leader反饋一個(gè)ACK響應(yīng)
5. Leader接收到半數(shù)以上Follower的ACK響應(yīng)后，即認(rèn)為消息發(fā)送成功，可以發(fā)送Commit消息
6. Leader向所有Follower廣播Commit消息，同時(shí)自身也會(huì)完成事務(wù)提交。Follower接收到Commit消息后也會(huì)完成事務(wù)的提交

崩潰恢復(fù)

在整個(gè)服務(wù)框架啟動(dòng)過(guò)程中，如果Leader服務(wù)器出現(xiàn)網(wǎng)絡(luò)中斷、崩潰退出或重啟等異常情況，ZAB協(xié)議就會(huì)進(jìn)入崩潰恢復(fù)模式。同時(shí)選舉出新的Leader服務(wù)器。

當(dāng)選舉產(chǎn)生了新的Leader服務(wù)器，同時(shí)集群中已經(jīng)有過(guò)半的機(jī)器與該Leader服務(wù)器完成了狀態(tài)同步（數(shù)據(jù)同步）之后，ZAB協(xié)議會(huì)退出恢復(fù)模式。

1. 在ZAB協(xié)議中，為了保證程序的正確運(yùn)?，整個(gè)恢復(fù)過(guò)程結(jié)束后需要選舉出?個(gè)新的Leader 服務(wù)器。
2. Leader選舉算法不僅僅需要讓Leader?身知道已經(jīng)被選舉為L(zhǎng)eader，同時(shí)還需要讓集群中的所有其他機(jī)器也能夠快速地感知到選舉產(chǎn)?出來(lái)的新Leader服務(wù)器。

ZAB保證數(shù)據(jù)一致性

ZAB協(xié)議規(guī)定了?如果?個(gè)事務(wù)Proposal在?臺(tái)機(jī)器上被處理成功，那么應(yīng)該在所有的機(jī)器上都被處理成功，哪怕機(jī)器出現(xiàn)故障崩潰。?針對(duì)這些情況ZAB協(xié)議需要保證以下條件：

• 已經(jīng)在Leader服務(wù)器上提交的事務(wù)最終被所有服務(wù)器都提交。

  假設(shè)?個(gè)事務(wù)在 Leader 服務(wù)器上被提交了，并且已經(jīng)得到過(guò)半 Folower 服務(wù)器的Ack反饋，但是在它 將Commit消息發(fā)送給所有Follower機(jī)器之前，Leader服務(wù)器掛了

• 丟棄只在Leader服務(wù)器上被提出（未提交）的事務(wù)。

  假設(shè)初始的 Leader 服務(wù)器 Server1 在提出了?個(gè)事務(wù)Proposal3 之后就崩潰退出 了，從?導(dǎo)致集群中的其他服務(wù)器都沒(méi)有收到這個(gè)事務(wù)Proposal3。于是，當(dāng) Server1 恢復(fù)過(guò)來(lái)再次加 ?到集群中的時(shí)候，ZAB 協(xié)議需要確保丟棄Proposal3這個(gè)事務(wù)。

綜上所述，ZAB的選舉出來(lái)的Leader必須滿(mǎn)足以下條件：

能夠確保提交已經(jīng)被 Leader 提交的事務(wù) Proposal，同時(shí)丟棄已經(jīng)被跳過(guò)的事務(wù) Proposal。即：

1. 新選舉出來(lái)的 Leader 不能包含未提交的 Proposal。
2. 新選舉的 Leader 節(jié)點(diǎn)中含有最大的 zxid?。

ZAB如何數(shù)據(jù)同步

所有正常運(yùn)行的服務(wù)器要么成為L(zhǎng)eader，要么成為Follower并和Leader保持同步。

1. 完成Leader選舉（新的 Leader 具有最高的zxid）之后，在正式開(kāi)始?作（接收客戶(hù)端請(qǐng)求）之前，Leader服務(wù)器會(huì)?先確認(rèn)事務(wù)?志中的所有Proposal是否都已經(jīng)被集群中過(guò)半的機(jī)器提交了，即?是否完成數(shù)據(jù)同步?。

2. Leader服務(wù)器需要確保所有的Follower服務(wù)器能夠接收到每?條事務(wù)Proposal，并且能夠正確地將所有已經(jīng)提交了的事務(wù)Proposal應(yīng)?到內(nèi)存數(shù)據(jù)中。等到 Follower服務(wù)器將所有其尚未同步的事務(wù) Proposal 都從 Leader 服務(wù)器上同步過(guò)來(lái)并成功應(yīng)?到本地?cái)?shù)據(jù)庫(kù)中后，Leader服務(wù)器就會(huì)將該Follower服務(wù)器加?到真正的可?Follower列表中，并開(kāi)始之后的其他流程。

ZAB運(yùn)行時(shí)狀態(tài)#

ZAB協(xié)議設(shè)計(jì)中，每個(gè)進(jìn)程都有可能處于如下三種狀態(tài)之一：

• LOOKING：Leader選舉狀態(tài)，正在尋找Leader
• FOLLOWING：當(dāng)前節(jié)點(diǎn)是Follower。與Leader服務(wù)器保持同步狀態(tài)
• LEADING：當(dāng)前節(jié)點(diǎn)是Leader，作為主進(jìn)程領(lǐng)導(dǎo)狀態(tài)。

ZAB狀態(tài)的切換

啟動(dòng)時(shí)的狀態(tài)轉(zhuǎn)換

1. 所有進(jìn)程的初始狀態(tài)都是LOOKING狀態(tài)，此時(shí)不存在Leader。

2. 接下來(lái)，進(jìn)程會(huì)試圖選舉出來(lái)一個(gè)新的Leader，Leader切換為L(zhǎng)EADING狀態(tài)，其它進(jìn)程發(fā)現(xiàn)已經(jīng)選舉出新的Leader，那么它就會(huì)切換到FOLLOWING狀態(tài)，并開(kāi)始與Leader保持同步。

3. 處于FOLLOWING狀態(tài)的進(jìn)程稱(chēng)為Follower，LEADING狀態(tài)的進(jìn)程稱(chēng)為L(zhǎng)eader。

4. 當(dāng)Leader崩潰或者放棄領(lǐng)導(dǎo)地位時(shí)，其余的Follower進(jìn)程就會(huì)切換到LOOKING狀態(tài)開(kāi)始新一輪的Leader選舉。

運(yùn)行過(guò)程中的狀態(tài)轉(zhuǎn)換

一個(gè)Follower只能和一個(gè)Leader保持同步，Leader進(jìn)程和所有的Follower進(jìn)程之間通過(guò)心跳監(jiān)測(cè)機(jī)制來(lái)感知彼此的情況。

1. 若Leader能夠在超時(shí)時(shí)間內(nèi)正常的收到心跳檢測(cè)，那么Follower就會(huì)一直與該Leader保持連接。
2. 如果在指定時(shí)間內(nèi)Leader無(wú)法從過(guò)半的Follower進(jìn)程那里接收到心跳檢測(cè)，或者TCP連接斷開(kāi)，那么Leader會(huì)放棄當(dāng)前周期的領(lǐng)導(dǎo)，并轉(zhuǎn)換為L(zhǎng)OOKING狀態(tài)；其他的Follower也會(huì)選擇放棄這個(gè)Leader，同時(shí)轉(zhuǎn)換為L(zhǎng)OOKING狀態(tài)，之后會(huì)進(jìn)行新一輪的Leader選舉

ZAB的四個(gè)階段

選舉階段（Leader Election）

節(jié)點(diǎn)在一開(kāi)始都處于選舉階段，只要有一個(gè)節(jié)點(diǎn)超過(guò)半數(shù)階段的票數(shù)，它就可以當(dāng)選準(zhǔn)Leader，只有到達(dá)第三個(gè)階段（同步階段），這個(gè)準(zhǔn)Leader才會(huì)成為真正的Leader。

這一階段的目的就是為了選出一個(gè)準(zhǔn)Leader，然后進(jìn)入下一階段。

發(fā)現(xiàn)階段

在這個(gè)階段中，F(xiàn)ollowers和上一輪選舉出的準(zhǔn)Leader進(jìn)行通信，同步Followers最近接受的事務(wù)Proposal。這個(gè)階段主要目的是發(fā)現(xiàn)當(dāng)前大多數(shù)節(jié)點(diǎn)接受的最新提議，并且準(zhǔn)Leader生成新的epoch，讓Followers接受，更新它們的acceptedEpoch。

一個(gè)Follower只會(huì)連接一個(gè)Leader，如果有一個(gè)節(jié)點(diǎn)F認(rèn)為另一個(gè)Follower P是Leader，F(xiàn)在嘗試連接P時(shí)會(huì)被拒絕，F(xiàn)被拒絕后，就會(huì)進(jìn)入選舉階段。

同步階段

同步階段主要是利用 Leader 前一階段獲得的最新 Proposal 歷史，同步集群中所有的副本。

只有當(dāng) quorum（超過(guò)半數(shù)的節(jié)點(diǎn)） 都同步完成，準(zhǔn) Leader 才會(huì)成為真正的 Leader。Follower 只會(huì)接收 zxid 比自己 lastZxid 大的 Proposal。

廣播階段

到了這個(gè)階段，Zookeeper 集群才能正式對(duì)外提供事務(wù)服務(wù)，并且 Leader 可以進(jìn)行消息廣播。同時(shí)，如果有新的節(jié)點(diǎn)加入，還需要對(duì)新節(jié)點(diǎn)進(jìn)行同步。需要注意的是，Zab 提交事務(wù)并不像 2PC 一樣需要全部 Follower 都 Ack，只需要得到 quorum（超過(guò)半數(shù)的節(jié)點(diǎn)）的Ack 就可以。

ZAB協(xié)議實(shí)現(xiàn)

Java 版本的ZAB協(xié)議的實(shí)現(xiàn)跟上面的定義略有不同，選舉階段使用的是?Fast Leader Election（FLE），它包含了步驟2的發(fā)現(xiàn)職責(zé)。因?yàn)镕LE會(huì)選舉擁有最新提議的歷史節(jié)點(diǎn)作為 Leader，這樣就省去了發(fā)現(xiàn)最新提議的步驟。

實(shí)際的實(shí)現(xiàn)將?發(fā)現(xiàn)和同步階段合并為 Recovery Phase（恢復(fù)階段）?，所以，Zab 的實(shí)現(xiàn)實(shí)際上有三個(gè)階段。

快速選舉（Fast Leader Election

前面提到的 FLE 會(huì)選舉擁有最新Proposal history （lastZxid最大）的節(jié)點(diǎn)作為 Leader，這樣就省去了發(fā)現(xiàn)最新提議的步驟。?這是基于擁有最新提議的節(jié)點(diǎn)也擁有最新的提交記錄

成為L(zhǎng)eader的條件：

1. 選epoch最大的
2. epoch相等，選zxid最大的
3. epoch和zxid都相等，選server_id最大的（zoo.cfg 中配置的 myid）

節(jié)點(diǎn)在選舉開(kāi)始時(shí)，都默認(rèn)投票給自己，當(dāng)接收其他節(jié)點(diǎn)的選票時(shí)，會(huì)根據(jù)上面的?Leader條件?判斷并且更改自己的選票，然后重新發(fā)送選票給其他節(jié)點(diǎn)。當(dāng)有一個(gè)節(jié)點(diǎn)的得票超過(guò)半數(shù)，該節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 Leading ，其他節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 Following。

恢復(fù)階段（Recovery Phase）

這一階段 Follower 發(fā)送他們的 lastZxid 給 Leader，Leader 根據(jù) lastZxid 決定如何同步數(shù)據(jù)。這里的實(shí)現(xiàn)跟前面的 階段 3 有所不同：Follower 收到 TRUNC 指令會(huì)終止?L.lastCommitedZxid?之后的 Proposal ，收到 DIFF 指令會(huì)接收新的 Proposal。

history.lastCommittedZxid：最近被提交的提議的 zxid history.oldThreshold：被認(rèn)為已經(jīng)太舊的已提交提議的 zxid

廣播階段（Broadcast Phase）

參考 4.1 [ZAB協(xié)議內(nèi)容#消息廣播]

ZAB與Paxos的聯(lián)系和區(qū)別

聯(lián)系

1. 都存在一個(gè)類(lèi)似Leader進(jìn)程的角色，由其負(fù)責(zé)協(xié)調(diào)多個(gè)Follower進(jìn)程的運(yùn)行
2. Leader進(jìn)程都會(huì)等待超過(guò)半數(shù)的Follower作出正確的反饋后，才會(huì)將一個(gè)提議進(jìn)行提交（過(guò)半原則）
3. 在ZAB中，每個(gè)Proposal中都包含了一個(gè)epoch值，用來(lái)代表當(dāng)前Leader周期，在Paxos中同樣存在這樣的一個(gè)表示，名字為 Ballot。

區(qū)別

1. Paxos算法中，新選舉產(chǎn)生的主進(jìn)程會(huì)進(jìn)行兩個(gè)階段的工作；第一階段稱(chēng)為讀階段：新的主進(jìn)程和其他進(jìn)程通信來(lái)收集主進(jìn)程提出的提議，并將它們提交。第二階段稱(chēng)為寫(xiě)階段：當(dāng)前主進(jìn)程開(kāi)始提出自己的提議。
2. ZAB協(xié)議在Paxos基礎(chǔ)上添加了同步階段，此時(shí)，新的Leader會(huì)確保存在過(guò)半的Follower已經(jīng)提交了之前Leader周期中的所有事物Proposal。這一同步階段的引入，能夠有效保證，Leader在新的周期中提出事務(wù)Proposal之前，所有的進(jìn)程都已經(jīng)完成了對(duì)之前所有事務(wù)Proposal的提交。

總的來(lái)說(shuō)，ZAB協(xié)議和Paxos算法的本質(zhì)區(qū)別在于兩者的設(shè)計(jì)目的不一樣：ZAB協(xié)議主要用于構(gòu)建一個(gè)高可用的分布式數(shù)據(jù)主備系統(tǒng)，而Paxos算法則用于構(gòu)建一個(gè)分布式的一致性狀態(tài)機(jī)系統(tǒng)。

總結(jié)

問(wèn)題解答：

• 主從架構(gòu)下，leader 崩潰，數(shù)據(jù)一致性怎么保證？

  leader 崩潰之后，集群會(huì)選出新的 leader，然后就會(huì)進(jìn)入恢復(fù)階段，新的 leader 具有所有已經(jīng)提交的提議，因此它會(huì)保證讓 followers 同步已提交的提議，丟棄未提交的提議（以 leader 的記錄為準(zhǔn)），這就保證了整個(gè)集群的數(shù)據(jù)一致性。

• 選舉 leader 的時(shí)候，整個(gè)集群無(wú)法處理寫(xiě)請(qǐng)求的，如何快速進(jìn)行 leader 選舉？

  這是通過(guò) Fast Leader Election 實(shí)現(xiàn)的，leader 的選舉只需要超過(guò)半數(shù)的節(jié)點(diǎn)投票即可，這樣不需要等待所有節(jié)點(diǎn)的選票，能夠盡早選出 leader。

下方二維碼關(guān)注我

技術(shù)草根，堅(jiān)持分享?編程，算法，架構(gòu)

看完文章，餓了點(diǎn)外賣(mài)，點(diǎn)擊 ??《無(wú)門(mén)檻外賣(mài)優(yōu)惠券，每天免費(fèi)領(lǐng)！》