Zab也是一個(gè)強(qiáng)一致性算法，也是(multi-)Paxos的一種谨娜，全稱是Zookeeper atomic broadcast protocol航攒，是Zookeeper內(nèi)部用到的一致性協(xié)議。相比Paxos趴梢，也易于理解漠畜。其保證了消息的全局有序和因果有序，擁有著一致性坞靶。Zab和Raft也是非常相似的憔狞，只是其中有些概念名詞不一樣。
Role(or Status)
節(jié)點(diǎn)狀態(tài)：
Leading：說明當(dāng)前節(jié)點(diǎn)為Leader
Following：說明當(dāng)前節(jié)點(diǎn)為Follower
Election：說明節(jié)點(diǎn)處于選舉狀態(tài)彰阴。整個(gè)集群都處于選舉狀態(tài)中瘾敢。
Epoch邏輯時(shí)鐘
Epoch相當(dāng)于paxos中的proposerID，Raft中的term尿这，相當(dāng)于一個(gè)國家廉丽，朝代紀(jì)元。
Quorums：
多數(shù)派妻味，集群中超過半數(shù)的節(jié)點(diǎn)集合。
節(jié)點(diǎn)中的持久化信息：
history:?a log of transaction proposals accepted; 歷史提議日志文件
acceptedEpoch:?the epoch number of the last NEWEPOCH message accepted; 集群中的最近最新Epoch
currentEpoch:?the epoch number of the last NEWLEADER message accepted; 集群中的最近最新Leader的Epoch
lastZxid:?zxid of the last proposal in the history log; 歷史提議日志文件的最后一個(gè)提議的zxid
在 ZAB 協(xié)議的事務(wù)編號(hào) Zxid 設(shè)計(jì)中欣福，Zxid?是一個(gè) 64 位的數(shù)字责球，
低 32 位是一個(gè)簡單的單調(diào)遞增的計(jì)數(shù)器，針對客戶端每一個(gè)事務(wù)請求，計(jì)數(shù)器加 1雏逾；
高 32 位則代表 Leader 周期 epoch 的編號(hào)嘉裤，每個(gè)當(dāng)選產(chǎn)生一個(gè)新的 Leader 服務(wù)器，就會(huì)從這個(gè) Leader 服務(wù)器上取出其本地日志中最大事務(wù)的ZXID栖博，并從中讀取 epoch 值屑宠，然后加 1，以此作為新的 epoch仇让，并將低 32 位從 0 開始計(jì)數(shù)典奉。
epoch：可以理解為當(dāng)前集群所處的年代或者周期，每個(gè) leader 就像皇帝丧叽，都有自己的年號(hào)卫玖，所以每次改朝換代，leader 變更之后踊淳，都會(huì)在前一個(gè)年代的基礎(chǔ)上加 1假瞬。這樣就算舊的 leader 崩潰恢復(fù)之后，也沒有人聽他的了迂尝，因?yàn)?follower 只聽從當(dāng)前年代的 leader 的命令脱茉。
ZAB協(xié)議
Zab協(xié)議分為四個(gè)階段
Phase 0: Leader election（選舉階段，Leader不存在）
節(jié)點(diǎn)在一開始都處于選舉階段垄开，只要有一個(gè)節(jié)點(diǎn)得到超半數(shù)Quorums節(jié)點(diǎn)的票數(shù)的支持琴许，它就可以當(dāng)選prospective ?leader。只有到達(dá) Phase 3 prospective leader 才會(huì)成為established ?leader(EL)说榆。
這一階段的目的是就是為了選出一個(gè)prospective leader（PL）虚吟，然后進(jìn)入下一個(gè)階段。
協(xié)議并沒有規(guī)定詳細(xì)的選舉算法签财，后面我們會(huì)提到實(shí)現(xiàn)中使用的?Fast Leader Election串慰。
Phase 1: Discovery（發(fā)現(xiàn)階段，Leader不存在）
在這個(gè)階段唱蒸，PL收集Follower發(fā)來的acceptedEpoch(或者)邦鲫，并確定了PL的Epoch和Zxid最大，則會(huì)生成一個(gè)NEWEPOCH分發(fā)給Follower神汹，F(xiàn)ollower確認(rèn)無誤后返回ACK給PL庆捺。
這個(gè)一階段的主要目的是PL生成NEWEPOCH，同時(shí)更新Followers的acceptedEpoch屁魏，并尋找最新的historylog滔以，賦值給PL的history。
這個(gè)階段的根本：發(fā)現(xiàn)最新的history log氓拼，發(fā)現(xiàn)最新的history log你画，發(fā)現(xiàn)最新的history log抵碟。
一個(gè) follower 只會(huì)連接一個(gè) leader，如果有一個(gè)節(jié)點(diǎn) f 認(rèn)為另一個(gè) follower 是 leader坏匪，f 在嘗試連接 p 時(shí)會(huì)被拒絕拟逮，f 被拒絕之后，就會(huì)進(jìn)入 Phase 0适滓。
1PL?????????Followers
2|<---------X--X--X????????FOLLOWERINFO(F.acceptedEpoch)
3X--------->|->|->|????????NEWEPOCH(e′)
4|<---------X--X--X????????ACKEPOCH(F.currentEpoch,?F.history,?F.lastZxid)敦迄，接著PL尋找所有Follower和PL中最新的history賦值給PL.history
Phase 2: Synchronization（同步階段，Leader不存在）
同步階段主要是利用 leader 前一階段獲得的最新提議歷史凭迹，同步集群中所有的副本罚屋。只有當(dāng) quorum 都同步完成，PL才會(huì)成為EL蕊苗。follower 只會(huì)接收 zxid 比自己的 lastZxid 大的提議沿后。
這個(gè)一階段的主要目的是同步PL的historylog副本。
1PL?????????Followers
2X--------->|->|->|????????NEWLEADER(e′?,?L.history)?
3|<---------X--X--X????????ACKNEWLEADER(e′,L.history)
4X--------->|->|->|????????COMMIT?message,Follow?Deliver??v,?z?,PL->L
Phase 3: Broadcast（廣播階段朽砰，Leader存在）
到了這個(gè)階段尖滚，Zookeeper 集群才能正式對外提供事務(wù)服務(wù)，并且 leader 可以進(jìn)行消息廣播瞧柔。同時(shí)如果有新的節(jié)點(diǎn)加入漆弄，還需要對新節(jié)點(diǎn)進(jìn)行同步。
這個(gè)一階段的主要目的是接受請求造锅，進(jìn)行消息廣播
值得注意的是撼唾，ZAB 提交事務(wù)并不像 2PC 一樣需要全部 follower 都 ACK，只需要得到 quorum （超過半數(shù)的節(jié)點(diǎn)）的 ACK 就可以了哥蔚。
1Client?????Leader??????Followers
2|?????????|??????????|??|??|
3???X-------->|??????????|??|??|??????write?Request
4|?????????X--------->|->|->|?????sent?Propose??e′,??v,?z??
5|?????????|<---------X--X--X?????Append?proposal?to?F.history,Send?ACK(?e′,??v,?z??)?to?L
6|?????????X--------->|->|->|?????COMMIT(e′,??v,?z?),F?Commit?(deliver)?transaction??v,?z?
zookeeper中zab協(xié)議的實(shí)現(xiàn)
協(xié)議的 Java 版本實(shí)現(xiàn)跟上面的定義有些不同倒谷，選舉階段使用的是 Fast Leader Election（FLE），它包含了 Phase 1 的發(fā)現(xiàn)職責(zé)糙箍。因?yàn)?FLE 會(huì)選舉擁有最新提議歷史的節(jié)點(diǎn)作為 leader渤愁，這樣就省去了發(fā)現(xiàn)最新提議的步驟。實(shí)際的實(shí)現(xiàn)將 Phase 1 和 Phase 2 合并為 Recovery Phase（恢復(fù)階段）深夯。所以抖格，ZAB 的實(shí)現(xiàn)只有三個(gè)階段：
Phase 1:Fast Leader Election(快速選舉階段，Leader不存在)
前面提到 FLE 會(huì)選舉擁有最新提議歷史（lastZixd最大）的節(jié)點(diǎn)作為 leader咕晋，這樣就省去了發(fā)現(xiàn)最新提議的步驟雹拄。這是基于擁有最新提議的節(jié)點(diǎn)也有最新提交記錄的前提。
每個(gè)節(jié)點(diǎn)會(huì)同時(shí)向自己和其他節(jié)點(diǎn)發(fā)出投票請求掌呜，互相投票滓玖。
選舉流程：
選epoch最大的
epoch相等，選 zxid 最大的
epoch和zxid都相等质蕉，選擇serverID最大的（就是我們配置zoo.cfg中的myid）
節(jié)點(diǎn)在選舉開始都默認(rèn)投票給自己势篡，當(dāng)接收其他節(jié)點(diǎn)的選票時(shí)损姜，會(huì)根據(jù)上面的條件更改自己的選票并重新發(fā)送選票給其他節(jié)點(diǎn)，當(dāng)有一個(gè)節(jié)點(diǎn)的得票超過半數(shù)殊霞，該節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 leading，其他節(jié)點(diǎn)會(huì)設(shè)置自己的狀態(tài)為 following汰蓉。
Phase 2:Recovery Phase（恢復(fù)階段绷蹲，Leader不存在）
這一階段 follower 發(fā)送它們的 lastZixd 給 leader，leader 根據(jù) lastZixd 決定如何同步數(shù)據(jù)顾孽。這里的實(shí)現(xiàn)跟前面 Phase 2 有所不同：Follower 收到 TRUNC 指令會(huì)中止 L.lastCommittedZxid 之后的提議祝钢，收到 DIFF 指令會(huì)接收新的提議。
1L?????????Followers
2X-----------------??????????L.lastZxid?←??L.lastZxid.epoch?+?1,?0?
3|<---------X--X--X????????FOLLOWERINFO(F.lastZxid)
4X--------->|->|->|????????NEWEPOCH(L.lastZxid)
5X--------->|->|->|????????SNAP,DIFF?or?TRUNC指令
6|<---------X--X--X????????if?TRUNC?notAccept?L.lastZxid?else(DIFF)?accept,commit?proposal?else(SNAP)?...
Phase 3:Broadcast Election(廣播階段若厚，Leader存在)
同上
Leader故障
如果是Leader故障拦英，首先進(jìn)行Phase 1:Fast Leader Election，然后Phase 2:Recovery Phase测秸，恢復(fù)階段保證了如下兩個(gè)問題疤估，這兩個(gè)問題同時(shí)也和Raft中的Leader故障解決的問題是一樣的，總之就是要保證Leader操作日志是最新的：
已經(jīng)被處理的消息不能丟? ? ??
被丟棄的消息不能再次出現(xiàn)
總結(jié)
Zab和Raft都是強(qiáng)一致性協(xié)議霎冯，但是Zab和Raft的實(shí)質(zhì)是一樣的铃拇，都是mutli-paxos衍生出來的強(qiáng)一致性算法。簡單而言沈撞，他們的算法都都是先通過Leader選舉慷荔，選出一個(gè)Leader，然后Leader接受到客戶端的提議時(shí)缠俺，都是先寫入操作日志显晶，然后再與其他Followers同步日志，Leader再commit提議壹士，再與其他Followers同步提議磷雇。如果Leader故障，重新走一遍選舉流程墓卦，選取最新的操作日志倦春，然后同步日志，接著繼續(xù)接受客戶端請求等等落剪。過程都是一樣睁本，只不過兩個(gè)的實(shí)現(xiàn)方式不同，描述方式不同忠怖。實(shí)現(xiàn)Raft的核心是Term呢堰，Zab的核心是Zxid，反正Term和Zxid都是邏輯時(shí)鐘凡泣。
