面試官問：ZooKeeper是強一致的嗎？怎么實現(xiàn)的？

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

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

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

問題提出

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

ZAB過程

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

所有事務(wù)必須由一個?全局唯一的服務(wù)器來協(xié)調(diào)處理?，這樣的服務(wù)器被稱為Leader服務(wù)器，余下的服務(wù)器則稱為Follower服務(wù)器

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

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

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

消息廣播

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

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

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

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

消息廣播過程：

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

崩潰恢復(fù)

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

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

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

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

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

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

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

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

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

綜上所述，ZAB的選舉出來的Leader必須滿足以下條件：

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

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

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

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

1. 完成Leader選舉（新的 Leader 具有最高的zxid）之后，在正式開始?作（接收客戶端請求）之前，Leader服務(wù)器會?先確認(rèn)事務(wù)?志中的所有Proposal是否都已經(jīng)被集群中過半的機器提交了，即?是否完成數(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ù)器上同步過來并成功應(yīng)?到本地數(shù)據(jù)庫中后，Leader服務(wù)器就會將該Follower服務(wù)器加?到真正的可?Follower列表中，并開始之后的其他流程。

ZAB運行時狀態(tài)#

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

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

ZAB狀態(tài)的切換

啟動時的狀態(tài)轉(zhuǎn)換

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

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

3. 處于FOLLOWING狀態(tài)的進程稱為Follower，LEADING狀態(tài)的進程稱為Leader。

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

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

一個Follower只能和一個Leader保持同步，Leader進程和所有的Follower進程之間通過心跳監(jiān)測機制來感知彼此的情況。

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

ZAB的四個階段

選舉階段（Leader Election）

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

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

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

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

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

同步階段

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

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

廣播階段

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

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

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

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

快速選舉（Fast Leader Election

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

成為Leader的條件：

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

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

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

這一階段 Follower 發(fā)送他們的 lastZxid 給 Leader，Leader 根據(jù) lastZxid 決定如何同步數(shù)據(jù)。這里的實現(xiàn)跟前面的 階段 3 有所不同：Follower 收到 TRUNC 指令會終止?L.lastCommitedZxid?之后的 Proposal ，收到 DIFF 指令會接收新的 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. 都存在一個類似Leader進程的角色，由其負(fù)責(zé)協(xié)調(diào)多個Follower進程的運行
2. Leader進程都會等待超過半數(shù)的Follower作出正確的反饋后，才會將一個提議進行提交（過半原則）
3. 在ZAB中，每個Proposal中都包含了一個epoch值，用來代表當(dāng)前Leader周期，在Paxos中同樣存在這樣的一個表示，名字為 Ballot。

區(qū)別

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

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

總結(jié)

問題解答：

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

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

• 選舉 leader 的時候，整個集群無法處理寫請求的，如何快速進行 leader 選舉？

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