最近在學(xué)習(xí)ZooKeeper，一直想寫篇相關(guān)博文記錄下學(xué)習(xí)內(nèi)容浪耘，礙于自己是個(gè)拖延癥重度患者總是停留在準(zhǔn)備階段乱灵，直到今天心血來(lái)潮突然想干點(diǎn)什么，于是便一不做二不休七冲，通過(guò)對(duì)《從Paxos到Zookeeper 分布式一致性原理與實(shí)踐》一書中ZAB相關(guān)內(nèi)容的總結(jié)痛倚，以及對(duì)一些優(yōu)秀博文的整理碼出來(lái)這篇簡(jiǎn)文。本文首先對(duì)ZooKeeper進(jìn)行一個(gè)簡(jiǎn)單的介紹澜躺，然后重點(diǎn)介紹ZooKeeper采用的ZAB（ZooKeeper Atomic Broadcast）一致性協(xié)議算法蝉稳，加深自己對(duì)ZAB協(xié)議的理解的同時(shí)也希望與簡(jiǎn)友們一起分享討論。
ZooKeeper介紹
ZooKeeper是一個(gè)具有高效且可靠的分布式協(xié)調(diào)服務(wù)苗踪， 由Yahoo創(chuàng)建的基于Google的Chubby開源實(shí)現(xiàn)颠区，并于2010年11月正式成為Apache軟件基金會(huì)的頂級(jí)項(xiàng)目。
ZooKeeper是一個(gè)典型的分布式數(shù)據(jù)一致性解決方案通铲，分布式應(yīng)用程序可基于它實(shí)現(xiàn)諸如數(shù)據(jù)發(fā)布/訂閱毕莱、負(fù)載均衡、命名服務(wù)颅夺、分布式協(xié)調(diào)/通知朋截、集群管理、Master選舉吧黄、分布式鎖和分布式隊(duì)列等功能部服。
ZooKeeper語(yǔ)義保證
保證如下分布式一致性特性
順序一致性
從同一個(gè)客戶端發(fā)起的事務(wù)請(qǐng)求，最終將會(huì)嚴(yán)格地按照其發(fā)生順序被應(yīng)用到ZooKeeper中拗慨。
原子一致性
所有事務(wù)請(qǐng)求的處理結(jié)果在整個(gè)集群中所有機(jī)器上的應(yīng)用情況是一致的廓八，即要么整個(gè)集群所有機(jī)器都成功應(yīng)用了某一個(gè)事務(wù)奉芦，要么都沒(méi)有應(yīng)用，一定不會(huì)出現(xiàn)集群中部分機(jī)器應(yīng)用了該事務(wù)声功，而另外一部分沒(méi)有應(yīng)用的情況先巴。
單一視圖
無(wú)論客戶端連接的是哪個(gè)ZK服務(wù)器伸蚯，其看到的服務(wù)端數(shù)據(jù)模型都是一致的剂邮。
可靠性
一旦服務(wù)端成功地應(yīng)用了一個(gè)事務(wù)并完成對(duì)客戶端的響應(yīng)抗斤，那么該事務(wù)所引起的服務(wù)端狀態(tài)變更將會(huì)被一直保留下來(lái)，除非另外一個(gè)事務(wù)又對(duì)其進(jìn)行了變更龙宏。
實(shí)時(shí)性
通常人們看到實(shí)時(shí)性的第一反應(yīng)是膛虫，一旦一個(gè)事務(wù)被成功應(yīng)用毡庆，那么客戶端能夠立即從服務(wù)端上讀取到這個(gè)事務(wù)變更后的最新數(shù)據(jù)狀態(tài)坎藐。但這個(gè)需要注意的是次慢，ZooKeeper僅僅保證在一定時(shí)間段內(nèi)迫像，客戶端最終一定能夠從服務(wù)端上讀取到最新的數(shù)據(jù)狀態(tài)闻妓。
ZooKeeper服務(wù)器角色
Leader 一個(gè)ZooKeeper集群同一時(shí)間只會(huì)有一個(gè)實(shí)際工作的Leader由缆，它會(huì)發(fā)起并維護(hù)與各Follwer及Observer間的心跳。所有的寫操作必須要通過(guò)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類似野瘦，但是無(wú)投票權(quán)鞭光。
ZAB協(xié)議
協(xié)議簡(jiǎn)介
ZooKeeper Atomic Broadcast (ZAB, ZooKeeper原子消息廣播協(xié)議)是ZooKeeper實(shí)現(xiàn)分布式數(shù)據(jù)一致性的核心算法，ZAB借鑒Paxos算法史辙，但又不像Paxos算法那樣髓霞，是一種通用的分布式一致性算法方库，它是一種特別為ZooKeeper專門設(shè)計(jì)的支持崩潰恢復(fù)的原子廣播協(xié)議纵潦。
協(xié)議核心
ZAB協(xié)議的核心是定義了對(duì)于那些會(huì)改變ZooKeeper服務(wù)器數(shù)據(jù)狀態(tài)的事務(wù)請(qǐng)求處理方式，即：
所有事務(wù)請(qǐng)求必須由一個(gè)全局唯一的服務(wù)器來(lái)協(xié)調(diào)處理遂庄，這樣的服務(wù)器被稱為L(zhǎng)eader服務(wù)器涛目，而余下的其他服務(wù)器稱為Follower服務(wù)器霹肝。Leader服務(wù)器負(fù)責(zé)將一個(gè)客戶端事務(wù)請(qǐng)求轉(zhuǎn)換成一個(gè)事務(wù)Proposal(提議)沫换，并將該P(yáng)roposal分發(fā)給集群中所有的Follower服務(wù)器讯赏。之后Leader服務(wù)器需要等待所有的Follower服務(wù)器的反饋漱挎，一旦超過(guò)半數(shù)的Follower服務(wù)器進(jìn)行了正確的反饋后识樱，那么Leader就會(huì)再次向所有的Follower服務(wù)器分發(fā)Commit消息，要求其將前一個(gè)Proposal進(jìn)提交垢村。
協(xié)議階段劃分
ZAB協(xié)議整體可劃分為兩個(gè)基本的模式：消息廣播和崩潰恢復(fù)
按協(xié)議原理可細(xì)分為四個(gè)階段：選舉（Leader Election）嚎卫、發(fā)現(xiàn)（Discovery）拓诸、同步（Synchronization）和廣播(Broadcast)
按協(xié)議實(shí)現(xiàn)分為三個(gè)時(shí)期：選舉（Fast Leader Election）奠支、恢復(fù)(Recovery Phase)和廣播(Broadcast Phase)
消息廣播
ZAB協(xié)議的消息廣播過(guò)程使用的是一個(gè)原子廣播協(xié)議倍谜，類似于一個(gè)二階段提交過(guò)程。針對(duì)客戶端的事務(wù)請(qǐng)求答毫，Leader服務(wù)器會(huì)為其生成對(duì)應(yīng)的事務(wù)Proposal洗搂，并將其發(fā)送給集群中其余所有的機(jī)器耘拇，然后在分別收集各自的選票驼鞭，最后進(jìn)行事務(wù)提交，此處與二階段提交過(guò)程略有不同译隘，ZAB協(xié)議的二階段提交過(guò)程中固耘，移除了中斷邏輯厅目，所有的Follower服務(wù)器要么正常反饋Leader提出的事務(wù)Proposal损敷，要么就拋棄Leader服務(wù)器拗馒。同時(shí)诱桂，ZAB協(xié)議將二階段提交中的中斷邏輯移除意味著我們可以在過(guò)半的Follower服務(wù)器已經(jīng)反饋Ack之后就開始提交事務(wù)Proposal了挥等，而不需求等待集群中所有的Follower服務(wù)器都反饋?lái)憫?yīng)肝劲。
然而涡相，在這種簡(jiǎn)化的二階段提交模型下催蝗，無(wú)法處理Leader服務(wù)器崩潰退出而帶來(lái)的數(shù)據(jù)不一致問(wèn)題丙号，因此ZAB協(xié)議添加了崩潰恢復(fù)模式來(lái)解決這個(gè)問(wèn)題，另外喳魏，整個(gè)消息廣播協(xié)議是基于有FIFO特性的TCP協(xié)議來(lái)進(jìn)行網(wǎng)絡(luò)通信的，因此很容易地保證消息廣播過(guò)程中消息接收和發(fā)送的順序性枝恋。
在整個(gè)消息廣播過(guò)程中焚碌，Leader服務(wù)器會(huì)為每個(gè)事務(wù)請(qǐng)求生成對(duì)應(yīng)的Proposal來(lái)進(jìn)行廣播十电，并且在廣播事務(wù)Proposal之前，Leader服務(wù)器會(huì)首先為這個(gè)事務(wù)Proposal分配一個(gè)全局單調(diào)遞增的唯一ID台盯，我們稱之為事務(wù)ID(即ZXID)爷恳。由于ZAB協(xié)議需要保證每一個(gè)消息嚴(yán)格的因果關(guān)系，因此必須將每一個(gè)事務(wù)Proposal按照其ZXID的先后順序進(jìn)行排序和處理杯矩。
具體的史隆，在消息廣播過(guò)程中泌射，Leader服務(wù)器會(huì)為每個(gè)Follower服務(wù)器都各自分配一個(gè)單獨(dú)的隊(duì)列熔酷，然后將需要廣播的事務(wù)Proposal依次放入這些隊(duì)列中取，并且根據(jù)FIFO策略進(jìn)行消息發(fā)送号显。每一個(gè)Follower服務(wù)器在接收到這個(gè)事務(wù)Proposal之后，都會(huì)首先將其以事務(wù)日志的形式寫入本地磁盤中揽碘，并且成功寫入后反饋給Leader服務(wù)器一個(gè)Ack相應(yīng)园匹。當(dāng)Leader服務(wù)器接收到過(guò)半數(shù)Follower的Ack響應(yīng)后煞烫，就會(huì)廣播一個(gè)Commit消息給所有的Follower服務(wù)器以通知其進(jìn)行事務(wù)提交滞详，同時(shí)Leader自身也會(huì)完成對(duì)事務(wù)的提交料饥，而每個(gè)Follower服務(wù)器在接收到Commit消息后岸啡，也會(huì)完成對(duì)事務(wù)的提交巡蘸。
崩潰恢復(fù)
上面講解的ZAB協(xié)議的這個(gè)基于原子廣播協(xié)議的消息廣播過(guò)程悦荒，在正常運(yùn)行情況下運(yùn)行非常良好搬味，但是一旦Leader服務(wù)器出現(xiàn)崩潰或者由于網(wǎng)絡(luò)原因?qū)е翷eader服務(wù)器失去了與過(guò)半Follower的聯(lián)系碰纬，那么就會(huì)進(jìn)入崩潰恢復(fù)模式寿桨。在ZAB協(xié)議中牛隅，為了保證程序的正確運(yùn)行，整個(gè)恢復(fù)過(guò)程結(jié)束后需要選舉出一個(gè)新的Leader服務(wù)器陵刹。因此也糊，ZAB協(xié)議需要一個(gè)高效且可靠的Leader選舉算法羡宙，從而確保能夠快速選舉出新的Leader钞馁。同時(shí)僧凰，Leader選舉算法不僅僅需要讓Leader自己知道其自身已經(jīng)被選舉為L(zhǎng)eader熟丸，同時(shí)還需要讓集群中的所有其他服務(wù)器也快速地感知到選舉產(chǎn)生的新的Leader服務(wù)器训措。崩潰恢復(fù)主要包括Leader選舉和數(shù)據(jù)恢復(fù)兩部分，下面將詳細(xì)講解Leader選舉和數(shù)據(jù)恢復(fù)流程光羞。
Leader選舉算法
現(xiàn)有的選舉算法有一下四種：基于UDP的LeaderElection绩鸣、基于UDP的FastLeaderElection、基于UDP和認(rèn)證的FastLeaderElection和基于TCP的FastLeaderElection纱兑，在3.4.10版本中棄用其他三種算法
FastLeaderElection原理
名詞解釋
myid —— zk服務(wù)器唯一ID
zxid ——? 最新事務(wù)ID
高32位是Leader的epoch全闷，從1開始，每次選出新的Leader萍启，epoch加一；
低32位為該epoch內(nèi)的序號(hào)，每次epoch變化局服，都將低32位的序號(hào)重置唆迁；
保證了zkid的全局遞增性。
選票數(shù)據(jù)結(jié)構(gòu)
logicClock 表示這是該服務(wù)器發(fā)起的第多少輪投票看政，從1開始計(jì)數(shù)
state 當(dāng)前服務(wù)器的狀態(tài)
self_id 當(dāng)前服務(wù)器的唯一ID
self_zxid 當(dāng)前服務(wù)器上所保存的數(shù)據(jù)的最大事務(wù)ID嚷兔，從0開始計(jì)數(shù)
vote_id 被推舉的服務(wù)器的唯一ID
vote_zxid 被推舉的服務(wù)器上所保存的數(shù)據(jù)的最大事務(wù)ID乳怎，從0開始計(jì)數(shù)
服務(wù)器狀態(tài)
LOOKING?不確定Leader狀態(tài)恕出。該狀態(tài)下的服務(wù)器認(rèn)為當(dāng)前集群中沒(méi)有Leader，會(huì)發(fā)起Leader選舉。
FOLLOWING?跟隨者狀態(tài)二庵。表明當(dāng)前服務(wù)器角色是Follower睡陪，并且它知道Leader是誰(shuí)。
LEADING?領(lǐng)導(dǎo)者狀態(tài)。表明當(dāng)前服務(wù)器角色是Leader。
OBSERVING?觀察者狀態(tài)，不參與選舉茅郎，也不參與集群寫操作時(shí)的投票掌敬。
Leader選舉流程
能夠確保提交已經(jīng)被Leader提交的事務(wù)Proposal拄养，同時(shí)丟棄已經(jīng)被跳過(guò)的事務(wù)Proposal。針對(duì)這個(gè)要求，如果讓Leader選舉算法能夠保證新選舉出來(lái)的Leader服務(wù)器擁有集群中所有機(jī)器最高編號(hào)(即ZXID最大)的事務(wù)Proposal左腔，那么就可以保證這個(gè)新選舉出來(lái)的Leader一定具有所有已經(jīng)提交的提案鞭莽。更為重要的是，如果讓具有最高編號(hào)事務(wù)Proposal的機(jī)器成為L(zhǎng)eader咬像，就可以省去Leader服務(wù)器檢查Proposal的提交和丟棄工作的這一步操作了。
自增選舉輪次
ZooKeeper規(guī)定所有有效的投票都必須在同一輪次中。每個(gè)服務(wù)器在開始新一輪投票時(shí)南吮，會(huì)先對(duì)自己維護(hù)的logicClock進(jìn)行自增操作必孤。
初始化選票
每個(gè)服務(wù)器在廣播自己的選票前闸与，會(huì)將自己的投票箱清空忽洛。該投票箱記錄了所收到的選票。例：服務(wù)器2投票給服務(wù)器3，服務(wù)器3投票給服務(wù)器1寄狼，則服務(wù)器1的投票箱為(2, 3), (3, 1), (1, 1)。票箱中只會(huì)記錄每一投票者的最后一票，如投票者更新自己的選票奸披，則其它服務(wù)器收到該新選票后會(huì)在自己票箱中更新該服務(wù)器的選票轻局。
發(fā)送初始化選票
每個(gè)服務(wù)器最開始都是通過(guò)廣播把票投給自己置鼻。
接收外部投票
服務(wù)器會(huì)嘗試從其它服務(wù)器獲取投票钙勃，并記入自己的投票箱內(nèi)。如果無(wú)法獲取任何外部投票芥映，則會(huì)確認(rèn)自己是否與集群中其它服務(wù)器保持著有效連接。如果是崔泵，則再次發(fā)送自己的投票；如果否猪瞬，則馬上與之建立連接憎瘸。
更新選票
根據(jù)選票logicClock -> vote_zxid -> vote_id依次判斷
1 判斷選舉輪次
收到外部投票后，首先會(huì)根據(jù)投票信息中所包含的logicClock來(lái)進(jìn)行不同處理：
外部投票的logicClock > 自己的logicClock:? 說(shuō)明該服務(wù)器的選舉輪次落后于其它服務(wù)器的選舉輪次陈瘦，立即清空自己的投票箱并將自己的logicClock更新為收到的logicClock幌甘，然后再對(duì)比自己之前的投票與收到的投票以確定是否需要變更自己的投票，最終再次將自己的投票廣播出去;
外部投票的logicClock < 自己的logicClock: 當(dāng)前服務(wù)器直接忽略該投票痊项，繼續(xù)處理下一個(gè)投票;
外部投票的logickClock = 自己的: 當(dāng)時(shí)進(jìn)行選票PK含潘。
2 選票PK
選票PK是基于(self_id, self_zxid)與(vote_id, vote_zxid)的對(duì)比：
若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并廣播出去肮砾，另外將收到的票及自己更新后的票放入自己的票箱
統(tǒng)計(jì)選票
如果已經(jīng)確定有過(guò)半服務(wù)器認(rèn)可了自己的投票（可能是更新后的投票）诀黍，則終止投票。否則繼續(xù)接收其它服務(wù)器的投票仗处。
更新服務(wù)器狀態(tài)
投票終止后眯勾，服務(wù)器開始更新自身狀態(tài)。若過(guò)半的票投給了自己婆誓，則將自己的服務(wù)器狀態(tài)更新為L(zhǎng)EADING吃环，否則將自己的狀態(tài)更新為FOLLOWING。
圖示Leader選舉流程
注：圖中箭頭上的(1,1,0) 三個(gè)數(shù)一次代表該選票的服務(wù)器的LogicClock洋幻、被推薦的服務(wù)器的myid (即vote_myid) 以及被推薦的服務(wù)器的最大事務(wù)ID(即vote_zxid)郁轻；
(1, 1) 2個(gè)數(shù)分別代表投票服務(wù)器myid(即self_myid)和被推薦的服務(wù)器的myid (即vote_myid)
選舉流程如下:
自增選票輪次&初始化選票&發(fā)送初始化選票
首先，三臺(tái)服務(wù)器自增選舉輪次將LogicClock=1；然后初始化選票好唯，清空票箱竭沫；最后發(fā)起初始化投票給自己將各自的票通過(guò)廣播的形式投個(gè)自己并保存在自己的票箱里。
接受外部投票&更新選票
以Server 1 為例骑篙，分別經(jīng)歷 Server 1 PK Server 2 和 Server 1 PK Server 3 過(guò)程
Server 1 PK Server 2
Server 1 接收到Server 2的選票(1,2,0) 表示蜕提，投票輪次LogicClock為1，投給Server 2替蛉，并且Server 2的最大事務(wù)ID贯溅，ZXID 為0；
這時(shí)Server 1將自身的選票輪次和Server 2 的選票輪次比較躲查，發(fā)現(xiàn)LogicClock=1相等它浅，接著Server 2比較比較最大事務(wù)ID，發(fā)現(xiàn)也zxid=0也相等镣煮，最后比較各自的myid姐霍，發(fā)現(xiàn)Server 2的myid=2 大于自己的myid=1；
根據(jù)選票PK規(guī)則典唇，Server 1將自己的選票由 (1, 1) 更正為 (1, 2)镊折，表示選舉Server 2為L(zhǎng)eader，然后將自己的新選票 (1, 2)廣播給 Server 2 和 Server 3介衔，同時(shí)更新票箱子中自己的選票并保存Server 2的選票恨胚，至此Server 1票箱中的選票為(1, 2) 和 (2, 2)；
Server 2收到Server 1的選票同樣經(jīng)過(guò)輪次比較和選票PK后確認(rèn)自己的選票保持不變炎咖，并更新票箱中Server 1的選票由(1, 1)更新為(1, 2)赃泡，注意此次Server 2自己的選票并沒(méi)有改變所有不用對(duì)外廣播自己的選票。
Server 1 PK Server 3
更加Server 1 PK Server 2的流程類推乘盼，Server 1自己的選票由(1, 2)更新為(1, 3), 同樣更新自己的票箱并廣播給Server 2 和 Server 3升熊；
Server 2再次接收到Server 1的選票(1, 3)時(shí)經(jīng)過(guò)比較后根據(jù)規(guī)則也要將自己的選票從(1, 2)更新為(1, 3), 并更新票箱里自己的選票和Server 1的選票，同時(shí)向Server 1和 Server 3廣播绸栅；
同理 Server 2 和 Server 3也會(huì)經(jīng)歷上述投票過(guò)程级野，依次類推，Server 1 粹胯、Server 2 和Server 3 在倆倆之間在經(jīng)歷多次選舉輪次比較和選票PK后最終確定各自的選票蓖柔。
更新服務(wù)器狀態(tài)
選票確定后服務(wù)器根據(jù)自己票箱中的選票確定各自的角色和狀態(tài)，票箱中超過(guò)半數(shù)的選票投給自己的則為L(zhǎng)eader矛双，更新自己的狀態(tài)為L(zhǎng)EADING渊抽，否則為Follower角色，狀態(tài)為FOLLOWING议忽，
成為L(zhǎng)eader的服務(wù)器要主動(dòng)向Follower發(fā)送心跳包懒闷，F(xiàn)ollower做出ACK回應(yīng)，以維持他們之間的長(zhǎng)連接。
數(shù)據(jù)同步(待完善)
Commit過(guò)的數(shù)據(jù)不丟失
丟棄未Commit過(guò)的數(shù)據(jù)
參考資料
1.《從Paxos到Zookeeper 分布式一致性原理與實(shí)踐》 [倪超著]
2.《實(shí)例詳解ZooKeeper ZAB協(xié)議愤估、分布式鎖與領(lǐng)導(dǎo)選舉》
3.《ZooKeeper’s atomic broadcast protocol:Theory and practice》[Andr ?e Medeiros]
