1 Zookeeper 簡(jiǎn)介

ZooKeeper 由雅虎研究院開(kāi)發(fā)挑豌，后來(lái)捐贈(zèng)給了 Apache策橘。ZooKeeper 是一個(gè)開(kāi)源的分布式應(yīng)用程序協(xié)調(diào)服務(wù)器傍睹，其為分布式系統(tǒng)提供一致性服務(wù)沛硅。其一致性是通過(guò)基于 Paxos 算法的ZAB 協(xié)議完成的。其主要功能包括：配置維護(hù)禁炒、域名服務(wù)、分布式同步霍比、集群管理等幕袱。
zookeeper 的官網(wǎng)：http://zookeeper.apache.org

2 一致性

zk 是如何保證分布式系統(tǒng)的一致性的呢？是因?yàn)?zk 具有以下幾方面的特點(diǎn)：

• 順序一致性：zk 接收到的 N 多個(gè)事務(wù)請(qǐng)求（寫(xiě)操作請(qǐng)求）悠瞬，其會(huì)被嚴(yán)格按照接收順序應(yīng)用到zk 中凹蜂。
• 原子性：所有事務(wù)請(qǐng)求的結(jié)果在 zk 集群中每一臺(tái)主機(jī)上的應(yīng)用情況都是一致的。要么全部應(yīng)用成功阁危，要么全部失敗玛痊。
• 單一視圖：無(wú)論 Client 連接的是 zk 集群中的哪個(gè)主機(jī)，其看到的數(shù)據(jù)模型都是一致的狂打。
• 可靠性：一旦 zk 成功應(yīng)用了某事務(wù)擂煞，那么該事務(wù)所引發(fā)的 zk 狀態(tài)變更會(huì)被一直保留下來(lái)，直到另一個(gè)事務(wù)將其修改趴乡。
• 最終一致性：一旦一個(gè)事務(wù)被成功應(yīng)用纤壁，zk 可以保證在一個(gè)很短暫時(shí)間后威创，Client 最終能夠從 zk 上讀取到最新的數(shù)據(jù)狀態(tài)御铃。注意穿撮，不能保證實(shí)時(shí)讀取到。

3 Paxos 算法

對(duì)于zk 理論的學(xué)習(xí)惦辛，最重要也是最難的知識(shí)點(diǎn)就是 Paxos 算法劳秋。所以我們首先學(xué)習(xí) Paxos算法。

3.1 算法簡(jiǎn)介

Paxos 算法是萊斯利·蘭伯特(Leslie Lamport)1990 年提出的一種基于消息傳遞的胖齐、具有高容錯(cuò)性的一致性算法玻淑。Google Chubby 的作者 Mike Burrows 說(shuō)過(guò)，世上只有一種一致性算法呀伙， 那就是 Paxos补履，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一種公認(rèn)的晦澀難懂的算法剿另，并且工程實(shí)現(xiàn)上也具有很大難度箫锤。較有名的 Paxos 工程實(shí)現(xiàn)有Google Chubby、ZAB雨女、微信的 PhxPaxos 等谚攒。
Paxos 算法是用于解決什么問(wèn)題的呢？Paxos 算法要解決的問(wèn)題是戚篙，在分布式系統(tǒng)中如何就某個(gè)決議達(dá)成一致五鲫。

3.2 Paxos 與拜占庭將軍問(wèn)題

拜占庭將軍問(wèn)題是由 Paxos 算法作者萊斯利·蘭伯特提出的點(diǎn)對(duì)點(diǎn)通信中的基本問(wèn)題溺职。該問(wèn)題要說(shuō)明的含義是岔擂，在不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的位喂。所以，Paxos 算法的前提是不存在拜占庭將軍問(wèn)題乱灵，即信道是安全的塑崖、可靠的，集群節(jié)點(diǎn)間傳遞的消息是不會(huì)被篡改的痛倚。

一般情況下规婆，分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)間采用兩種通訊模型：共享內(nèi)存（Shared Memory）、消息傳遞（Messages Passing）蝉稳。而 Paxos 是基于消息傳遞通訊模型的抒蚜。

3.3 算法描述

（1）三種角色

在 Paxos 算法中有三種角色，分別具有三種不同的行為耘戚。但很多時(shí)候嗡髓，一個(gè)進(jìn)程可能同時(shí)充當(dāng)著多種角色。

• Proposer：提案者收津。
• Acceptor：表決者饿这。
• Learner：學(xué)習(xí)者，同步者撞秋。

（2）Paxos 算法的一致性

Paxos 算法的一致性主要體現(xiàn)在以下幾點(diǎn)：

• 每個(gè)提案者在提出提案時(shí)都會(huì)首先獲取到一個(gè)遞增的长捧、全局唯一的提案編號(hào) N，然后將該編號(hào)賦予其要提出的提案吻贿。
  關(guān)于N 的生成串结，有兩種方式：全局性生成器；提案者自身維護(hù) N舅列。
• 每個(gè)表決者在 accept 某提案后奉芦，會(huì)將該提案的編號(hào) N 記錄在本地，這樣每個(gè)表決者中保存著已經(jīng)被 accept 的提案中會(huì)存在一個(gè)編號(hào)最大的提案剧蹂，其編號(hào)假設(shè)為 maxN声功。每個(gè)表決者僅會(huì) accept 編號(hào)大于自己本地 maxN 的提案。
• 在眾多提案中最終只能有一個(gè)提案被選定宠叼。
• 一旦一個(gè)提案被選定先巴，則其它學(xué)習(xí)者會(huì)主動(dòng)同步(Learn)該提案到本地。
• 沒(méi)有提案被提出則不會(huì)有提案被選定冒冬。

Paxos 故事：
1伸蚯、有一個(gè)叫做 Paxos 的小島(Island)上面住了一批居民，島上面所有的事情由一些特殊的人決定简烤，他們叫做議員(Senator)剂邮。
2、議員的總數(shù)(SenatorCount)是確定的横侦，不能更改挥萌。
3绰姻、島上每次環(huán)境事務(wù)的變更都需要通過(guò)一個(gè)提議(Proposal)，每個(gè)提議都有一個(gè)編號(hào)(PID)引瀑，這個(gè)編號(hào)是一直增長(zhǎng)的狂芋，不能倒退。
4憨栽、每個(gè)提議都需要超過(guò)半數(shù)((SenatorCount)/2+1)的議員同意才能生效帜矾。
5、每個(gè)議員只會(huì)同意大于當(dāng)前編號(hào)的提議屑柔，包括已生效的和未生效的屡萤。
6、如果議員收到小于等于當(dāng)前編號(hào)的提議掸宛，他會(huì)拒絕灭衷，并告知對(duì)方：你的提議已經(jīng)有 人提過(guò)了。這里的當(dāng)前編號(hào)是每個(gè)議員在自己記事本上面記錄的編號(hào)旁涤，他不斷更新這個(gè)編號(hào)翔曲。整個(gè)議會(huì)不能保證所有議員記事本上的編號(hào)總是相同的。

現(xiàn)在議會(huì)有一個(gè)目標(biāo)：保證所有的議員對(duì)于提議都能達(dá)成一致的看法劈愚。好瞳遍，現(xiàn)在議會(huì)開(kāi)始運(yùn)作，所有議員一開(kāi)始記事本上面記錄的編號(hào)都是 0菌羽。
有一個(gè)議員發(fā)了一個(gè)提議：
將電費(fèi)設(shè)定為 1 元/度掠械。他首先看了一下記事本，嗯注祖，當(dāng)前提議編號(hào)是 0猾蒂，那么我的這個(gè)提議的編號(hào)就是 1，于是他給所有議員發(fā)消息：1 號(hào)提議是晨，設(shè)定電費(fèi) 1 元/度肚菠。其他議員收到消息以后查了一下記事本，哦罩缴，當(dāng)前提議編號(hào)是 0蚊逢，這個(gè)提議可接受，于是他記錄下這個(gè)提議并回復(fù)：我接受你的 1 號(hào)提議箫章，同時(shí)他在記事本上記錄：當(dāng)前提議編號(hào)為 1烙荷。發(fā)起提議的議員收到了超過(guò)半數(shù)的回復(fù)，立即給所有人發(fā)通知：1 號(hào)提議生效檬寂！收到的議員會(huì)修改他的記事本终抽，將 1 好提議由記錄改成正式的法令，當(dāng)有人問(wèn)他電費(fèi)為多少時(shí)，他會(huì)查看法令并告訴對(duì)方：1 元/度昼伴。
現(xiàn)在看沖突的解決：
假設(shè)總共有三個(gè)議員 S1匾旭、S2 與 S3，S1 和 S2 同時(shí)發(fā)起了一個(gè)提議：設(shè)定電費(fèi)亩码，提議編號(hào)均為 1。S1 想設(shè)為 1 元/度野瘦，S2 想設(shè)為 2 元/度描沟。此時(shí) S3 先收到了 S1 的提議，于是他一查記事本鞭光，發(fā)現(xiàn)提議編號(hào) 1 大于當(dāng)前的編號(hào) 0吏廉，所以同意了該提議。緊接著他又收到了 S2 的提議惰许，結(jié)果他再查記事本席覆，發(fā)現(xiàn)這個(gè)提議的編號(hào)等于當(dāng)前記錄的編號(hào) 1，于是他拒絕了這個(gè)提議：對(duì)不起汹买，這個(gè)提議先前提過(guò)了佩伤。于是 S2 的提議被拒絕，S1 正式發(fā)布了提議：1 號(hào)提議生效晦毙。S2 向 S1 或者 S3 打聽(tīng)并更新了 1 號(hào)法令的內(nèi)容生巡，然后他可以選擇繼續(xù)發(fā)起 2 號(hào)提議。

Paxos 對(duì)外是如何工作的： 
情況一：
屁民甲(Client)到某個(gè)議員(ZKServer)那里詢(xún)問(wèn)(Get)某條法令的情況(ZNode 的數(shù)據(jù))见妒，議員毫不猶豫的拿出他的記事本(localStorage)孤荣，查閱法令并告訴他結(jié)果。
情況二：
屁民乙(Client)到某個(gè)議員(ZKServer)那里要求政府歸還欠他的一萬(wàn)元錢(qián)须揣，議員讓他在辦公室等著盐股，自己到議會(huì)將這個(gè)作為一個(gè)提議發(fā)給了所有議員。多數(shù)議員表示欠屁民的錢(qián)一定要還耻卡，于是該訪(fǎng)問(wèn)從國(guó)庫(kù)中拿出一萬(wàn)元還債疯汁，國(guó)庫(kù)總資產(chǎn)由 100 萬(wàn)變成 99 萬(wàn)。屁民乙拿到錢(qián)回去了(Client 函數(shù)返回)卵酪。

（3）2PC 與 3PC

Paxos 對(duì)于提案的提交算法有兩種方案涛目，2PC 與 3PC。

• 2PC：Two Phase Commit凛澎，即 prepare -> accept霹肝。
• 3PC：Three Phase Commit，即 prepare -> accept -> commit塑煎。

它們的區(qū)別主要就在于 accept 階段中是否包含 commit 功能沫换。具體看下面的描述。

3.4 3PC 算法過(guò)程描述

Paxos 算法的 3PC 執(zhí)行過(guò)程劃分為三個(gè)階段：準(zhǔn)備階段 prepare、接受階段 accept讯赏，與提交階段 commit垮兑。

01.png

（1）prepare 階段

1. 提案者(Proposer)準(zhǔn)備提交一個(gè)編號(hào)為 N 的提議，于是其首先向所有表決者(Acceptor)發(fā)送 prepare(N)請(qǐng)求漱挎，用于試探集群是否支持該編號(hào)的提議系枪。
2. 每個(gè)表決者(Acceptor)中都保存著自己曾經(jīng) accept 過(guò)的提議中的最大編號(hào) maxN。當(dāng)一個(gè)表決者接收到其它主機(jī)發(fā)送來(lái)的 prepare(N)請(qǐng)求時(shí)磕谅，其會(huì)比較N 與 maxN 的值私爷。有以下幾種情況：
   a) 若 N 小于 maxN，則說(shuō)明該提議已過(guò)時(shí)膊夹，當(dāng)前表決者采取不回應(yīng)或回應(yīng) Error 的方式來(lái)拒絕該 prepare 請(qǐng)求衬浑；
   b) 若N 大于maxN，則說(shuō)明該提議是可以接受的放刨，當(dāng)前表決者會(huì)首先將該 N 記錄下來(lái)工秩， 并將其曾經(jīng)已經(jīng) accept 的編號(hào)最大的提案 Proposal(myid,maxN,value)反饋給提案者， 以向提案者展示自己支持的提案意愿进统。其中第一個(gè)參數(shù) myid 表示該提案的提案者標(biāo)識(shí) id助币，第二個(gè)參數(shù)表示其曾接受的提案的最大編號(hào) maxN，第三個(gè)參數(shù)表示該提案的真正內(nèi)容value螟碎。當(dāng)然奠支，若當(dāng)前表決者還未曾 accept 過(guò)任何提議，則會(huì)將Proposal(null,null,null)反饋給提案者抚芦。
   c) 在prepare 階段 N 不可能等于 maxN倍谜。這是由 N 的生成機(jī)制決定的。要獲得 N 的值叉抡， 其必定會(huì)在原來(lái)數(shù)值的基礎(chǔ)上采用同步鎖方式增一尔崔。

（2）accept 階段

1. 當(dāng)提案者(Proposer)發(fā)出 prepare(N)后，若收到了超過(guò)半數(shù)的表決者(Accepter)的反饋褥民， 那么該提案者就會(huì)將其真正的提案 Proposal(myid,N,value)發(fā)送給所有的表決者季春。
2. 當(dāng)表決者(Acceptor)接收到提案者發(fā)送的 Proposal(myid,N,value)提案后，會(huì)再次拿出自己曾經(jīng) accept 過(guò)的提議中的最大編號(hào) maxN消返，或曾經(jīng)記錄下的 prepare 的最大編號(hào)载弄，讓 N 與它們進(jìn)行比較，若 N 大于等于這兩個(gè)編號(hào)撵颊，則當(dāng)前表決者 accept 該提案宇攻，并反饋給提案者。若 N 小于這兩個(gè)編號(hào)倡勇，則表決者采取不回應(yīng)或回應(yīng) Error 的方式來(lái)拒絕該提議逞刷。
3. 若提案者沒(méi)有接收到超過(guò)半數(shù)的表決者的 accept 反饋，則有兩種可能的結(jié)果產(chǎn)生。一是放棄該提案夸浅，不再提出仑最；二是重新進(jìn)入 prepare 階段，遞增提案號(hào)帆喇，重新提出 prepare 請(qǐng)求警医。

（3）commit 階段

若提案者接收到的反饋數(shù)量超過(guò)了半數(shù)，則其會(huì)向外廣播兩類(lèi)信息：

1. 向曾 accept 其提案的表決者發(fā)送“可執(zhí)行數(shù)據(jù)同步信號(hào)”坯钦，即讓它們執(zhí)行其曾接收到的提案预皇；
2. 向未曾向其發(fā)送 accept 反饋的表決者發(fā)送“提案 + 可執(zhí)行數(shù)據(jù)同步信號(hào)”，即讓它們接受到該提案后馬上執(zhí)行葫笼。

3.5 2PC 算法過(guò)程描述

2PC 與 3PC 的區(qū)別是深啤，在提案者接收到超過(guò)半數(shù)的表決者對(duì)于 parepare 階段的反饋后拗馒，其會(huì)向所有表決者發(fā)送真正的提案 proposal路星。當(dāng)表決者接受到 proposal 后就直接將其同步到了本地，不用再等待 commit 消息了诱桂。

那么洋丐，為什么不直接使用 2PC，而要使用 3PC 呢挥等？是因?yàn)?2PC 中存在著較多的弊端（這里就不再展開(kāi)來(lái)說(shuō)了）友绝。所以很多 Paxos 工業(yè)實(shí)現(xiàn)使用的都是 3PC 提交。但 2PC 提交的效率要高于 3PC 提交肝劲，所以在保證不出問(wèn)題的情況下迁客，是可以使用 2PC 提交的。

3.6 Paxos 算法的活鎖問(wèn)題

前面所述的Paxos 算法在實(shí)際工程應(yīng)用過(guò)程中辞槐，根據(jù)不同的實(shí)際需求存在諸多不便之處掷漱， 所以也就出現(xiàn)了很多對(duì)于基本 Paxos 算法的優(yōu)化算法，以對(duì) Paxos 算法進(jìn)行改進(jìn)榄檬，例如卜范，Multi Paxos、Fast Paxos鹿榜、EPaxos海雪。

例如，Paxos 算法存在“活鎖問(wèn)題”舱殿，F(xiàn)ast Paxos 算法對(duì) Paxos 算法進(jìn)行了改進(jìn)：只允許一個(gè)進(jìn)程提交提案奥裸，即該進(jìn)程具有對(duì) N 的唯一操作權(quán)。該方式解決了“活鎖”問(wèn)題沪袭。

4 ZAB 協(xié)議

4.1 ZAB 協(xié)議簡(jiǎn)介

ZAB 刺彩，Zookeeper Atomic Broadcast，zk 原子消息廣播協(xié)議，是專(zhuān)為 ZooKeeper 設(shè)計(jì)的一種支持崩潰恢復(fù)的原子廣播協(xié)議创倔，在 Zookeeper 中嗡害，主要依賴(lài) ZAB 協(xié)議來(lái)實(shí)現(xiàn)分布式數(shù)據(jù)一致性。

Zookeeper 使用一個(gè)單一主進(jìn)程來(lái)接收并處理客戶(hù)端的所有事務(wù)請(qǐng)求畦攘，即寫(xiě)請(qǐng)求霸妹。當(dāng)服務(wù)器數(shù)據(jù)的狀態(tài)發(fā)生變更后，集群采用 ZAB 原子廣播協(xié)議知押，以事務(wù)提案 Proposal 的形式廣播到所有的副本進(jìn)程上叹螟。ZAB 協(xié)議能夠保證一個(gè)全局的變更序列，即可以為每一個(gè)事務(wù)分配一個(gè)全局的遞增編號(hào) xid台盯。

當(dāng) Zookeeper 客戶(hù)端連接到 Zookeeper 集群的一個(gè)節(jié)點(diǎn)后罢绽，若客戶(hù)端提交的是讀請(qǐng)求， 那么當(dāng)前節(jié)點(diǎn)就直接根據(jù)自己保存的數(shù)據(jù)對(duì)其進(jìn)行響應(yīng)静盅；如果是寫(xiě)請(qǐng)求且當(dāng)前節(jié)點(diǎn)不是Leader良价，那么節(jié)點(diǎn)就會(huì)將該寫(xiě)請(qǐng)求轉(zhuǎn)發(fā)給 Leader，Leader 會(huì)以提案的方式廣播該寫(xiě)操作蒿叠，只要有超過(guò)半數(shù)節(jié)點(diǎn)同意該寫(xiě)操作明垢，則該寫(xiě)操作請(qǐng)求就會(huì)被提交。然后 Leader 會(huì)再次廣播給所有訂閱者市咽，即 Learner痊银，通知它們同步數(shù)據(jù)。

02.png

4.2 ZAB 與 Paxos 的關(guān)系

ZAB 協(xié)議是 Paxos 算法的一種工業(yè)實(shí)現(xiàn)算法施绎。但兩者的設(shè)計(jì)目標(biāo)不太一樣溯革。ZAB 協(xié)議主要用于構(gòu)建一個(gè)高可用的分布式數(shù)據(jù)主從系統(tǒng)，即 Follower 是 Leader 的從機(jī)谷醉，Leader 掛了致稀， 馬上就可以選舉出一個(gè)新的 Leader，但平時(shí)它們都對(duì)外提供服務(wù)孤紧。而 Fast Paxos 算法則是用于構(gòu)建一個(gè)分布式一致性狀態(tài)機(jī)系統(tǒng)豺裆，確保系統(tǒng)中各個(gè)節(jié)點(diǎn)的狀態(tài)都是一致的。

另外号显，ZAB 還使用 Google 的 Chubby 算法作為分布式鎖的實(shí)現(xiàn)臭猜，而 Google 的 Chubby 也是 Paxos 算法的應(yīng)用。

zk 集群對(duì)于事務(wù)請(qǐng)求的處理是 Fast Paxos 算法的體現(xiàn)押蚤，即只允許 Leader 提出提案蔑歌。其屬于 3PC 提交。

但 Leader 選舉是 Paxos 算法的體現(xiàn)揽碘，因?yàn)?Leader 宕機(jī)后次屠，所有 Follower 均可提交提案园匹， 它們?cè)谧畛醵际恰拔疫x我”。其屬于 2PC 提交劫灶。

4.3 三類(lèi)角色

為了避免 Zookeeper 的單點(diǎn)問(wèn)題裸违，zk 也是以集群的形式出現(xiàn)的。zk 集群中的角色主要有以下三類(lèi)：

• Leader：zk 集群中事務(wù)請(qǐng)求的唯一處理者本昏；其也可以處理讀請(qǐng)求供汛。
• Follower：處理讀請(qǐng)求；將事務(wù)請(qǐng)求轉(zhuǎn)發(fā)給 Leader涌穆；對(duì) Leader 發(fā)起的提案進(jìn)行表決怔昨；同步 Leader 的事務(wù)處理結(jié)果；在 Leader 的選舉過(guò)程中具有選舉權(quán)與被選舉權(quán)
• Observer：不具有表決權(quán)宿稀，且在 Leader 選舉過(guò)程中沒(méi)有選舉權(quán)與被選舉權(quán)的 Follower趁舀。

Learner：學(xué)習(xí)者，同步者祝沸。
Learner = Follower + Observer
QuorumPeer = Participant = Leader + Follower

4.4 三個(gè)數(shù)據(jù)

在 ZAB 中有三個(gè)很重要的數(shù)據(jù)：

• zxid：64 位長(zhǎng)度的Long 類(lèi)型矮烹，其高 32 位為 epoch，低 32 位為 xid奋隶。
• epoch：每一個(gè)新的Leader 都會(huì)有一個(gè)新的 epoch
• xid：其為一個(gè)流水號(hào)

4.5 三種模式

ZAB 協(xié)議中對(duì)zkServer 的狀態(tài)描述有三種模式擂送。這三種模式并沒(méi)有十分明顯的界線(xiàn)悦荒，它們相互交織在一起唯欣。

• 恢復(fù)模式：其包含兩個(gè)重要階段：Leader 的選舉，與初始化同步
• 廣播模式：其可以分為兩類(lèi)：初始化廣播搬味，與更新廣播
• 同步模式：其可以分為兩類(lèi)：初始化同步境氢，與更新同步

4.6 四種狀態(tài)

zk 集群中的每一臺(tái)主機(jī)，在不同的階段會(huì)處于不同的狀態(tài)碰纬。每一臺(tái)主機(jī)具有四種狀態(tài)萍聊。

• LOOKING：選舉狀態(tài)
• FOLLOWING：Follower 的正常工作狀態(tài)
• OBSERVING：Observer 的正常工作狀態(tài)
• LEADING：Leader 的正常工作狀態(tài)

4.8 Leader 選舉

在集群?jiǎn)?dòng)過(guò)程中，或 Leader 宕機(jī)后悦析，集群就進(jìn)入了恢復(fù)模式寿桨。恢復(fù)模式中最重要的階段就是 Leader 選舉强戴。

（1）Leader 選舉中的基本概念

A亭螟、serverId
這是zk 集群中服務(wù)器的唯一標(biāo)識(shí)，也稱(chēng)為 sid骑歹，其實(shí)質(zhì)就是 zk 中配置的 myid预烙。例如， 有三個(gè) zk 服務(wù)器道媚，那么編號(hào)分別是 1,2,3扁掸。
B翘县、 邏輯時(shí)鐘
邏輯時(shí)鐘，Logicalclock谴分，是一個(gè)整型數(shù)锈麸，該概念在選舉時(shí)稱(chēng)為 logicalclock，而在選舉結(jié)束后稱(chēng)為epoch牺蹄。即 epoch 與 logicalclock 是同一個(gè)值掐隐，在不同情況下的不同名稱(chēng)。

（2）Leader 選舉算法

在集群?jiǎn)?dòng)過(guò)程中的 Leader 選舉過(guò)程（算法）與 Leader 斷連后的 Leader 選舉過(guò)程稍微有一些區(qū)別钞馁，基本相同虑省。

A、集群?jiǎn)?dòng)中的 Leader 選舉

05.png

對(duì)于 Server1 而言，它的投票是(1, 0)呆贿，接收 Server2 的投票為(2, 0)嚷兔。其首先會(huì)比較兩者的 ZXID，均為 0做入，再比較 myid冒晰，此時(shí) Server2 的 myid 最大，于是 Server1 更新自己的投票為(2, 0)竟块，然后重新投票壶运。對(duì)于 Server2 而言，其無(wú)須更新自己的投票浪秘，只是再次向集群中所有主機(jī)發(fā)出上一次投票信息即可蒋情。
(4) 統(tǒng)計(jì)投票。每次投票后耸携，服務(wù)器都會(huì)統(tǒng)計(jì)投票信息棵癣，判斷是否已經(jīng)有過(guò)半機(jī)器接受到相同的投票信息。對(duì)于 Server1夺衍、Server2 而言狈谊，都統(tǒng)計(jì)出集群中已經(jīng)有兩臺(tái)主機(jī)接受了(2, 0)的投票信息，此時(shí)便認(rèn)為已經(jīng)選出了新的 Leader刷后，即 Server2的畴。
(5) 改變服務(wù)器狀態(tài)渊抄。一旦確定了 Leader尝胆，每個(gè)服務(wù)器就會(huì)更新自己的狀態(tài)，如果是Follower护桦，那么就變更為 FOLLOWING含衔，如果是 Leader，就變更為 LEADING二庵。
(6) 添加主機(jī)贪染。在新的 Leader 選舉出來(lái)后 Server3 啟動(dòng)，其想發(fā)出新一輪的選舉催享。但由于當(dāng)前集群中各個(gè)主機(jī)的狀態(tài)并不是 LOOKING杭隙，而是各司其職的正常服務(wù)，所以其只能是以Follower 的身份加入到集群中因妙。

B痰憎、 宕機(jī)后的 Leader 選舉
在 Zookeeper 運(yùn)行期間票髓，Leader 與非 Leader 服務(wù)器各司其職，即便當(dāng)有非 Leader 服務(wù)器宕機(jī)或新加入時(shí)也不會(huì)影響 Leader铣耘。但是若 Leader 服務(wù)器掛了洽沟，那么整個(gè)集群將暫停對(duì)外服務(wù)，進(jìn)入新一輪的 Leader 選舉蜗细，其過(guò)程和啟動(dòng)時(shí)期的 Leader 選舉過(guò)程基本一致裆操。

06.png

4.7 同步模式與廣播模式

（1）初始化同步

前面我們說(shuō)過(guò)盒齿，恢復(fù)模式具有兩個(gè)階段：Leader 選舉與初始化同步。當(dāng)完成 Leader 選舉后困食，此時(shí)的 Leader 還是一個(gè)準(zhǔn) Leader边翁，其要經(jīng)過(guò)初始化同步后才能變?yōu)檎嬲?Leader。

03.png

具體過(guò)程如下：

1. 為了保證 Leader 向 Learner 發(fā)送提案的有序硕盹，Leader 會(huì)為每一個(gè) Learner 服務(wù)器準(zhǔn)備一個(gè)隊(duì)列
2. Leader 將那些沒(méi)有被各個(gè) Learner 同步的事務(wù)封裝為Proposal
3. Leader 將這些 Proposal 逐條發(fā)給各個(gè) Learner符匾，并在每一個(gè) Proposal 后都緊跟一個(gè)COMMIT 消息，表示該事務(wù)已經(jīng)被提交莱睁，Learner 可以直接接收并執(zhí)行
4. Learner 接收來(lái)自于 Leader 的 Proposal待讳，并將其更新到本地
5. 當(dāng) Learner 更新成功后，會(huì)向準(zhǔn) Leader 發(fā)送 ACK 信息
6. Leader 服務(wù)器在收到來(lái)自 Learner 的ACK 后就會(huì)將該 Learner 加入到真正可用的Follower 列表或 Observer 列表仰剿。沒(méi)有反饋 ACK，或反饋了但 Leader 沒(méi)有收到的 Learner痴晦，Leader 不會(huì)將其加入到相應(yīng)列表南吮。

（2）消息廣播算法

04.png

當(dāng)集群中的 Learner 完成了初始化狀態(tài)同步，那么整個(gè) zk 集群就進(jìn)入到了正常工作模式了誊酌。
如果集群中的 Learner 節(jié)點(diǎn)收到客戶(hù)端的事務(wù)請(qǐng)求部凑，那么這些 Learner 會(huì)將請(qǐng)求轉(zhuǎn)發(fā)給Leader 服務(wù)器露乏。然后再執(zhí)行如下的具體過(guò)程：

1. Leader 接收到事務(wù)請(qǐng)求后，為事務(wù)賦予一個(gè)全局唯一的 64 位自增 id涂邀，即 zxid瘟仿，通過(guò)zxid 的大小比較即可實(shí)現(xiàn)事務(wù)的有序性管理，然后將事務(wù)封裝為一個(gè) Proposal比勉。
2. Leader 根據(jù) Follower 列表獲取到所有 Follower劳较，然后再將 Proposal 通過(guò)這些 Follower 的隊(duì)列將提案發(fā)送給各個(gè) Follower。
3. 當(dāng) Follower 接收到提案后浩聋，會(huì)先將提案的 zxid 與本地記錄的事務(wù)日志中的最大的zxid 進(jìn)行比較观蜗。若當(dāng)前提案的 zxid 大于最大zxid，則將當(dāng)前提案記錄到本地事務(wù)日志中衣洁，并向 Leader 返回一個(gè) ACK墓捻。
4. 當(dāng) Leader 接收到過(guò)半的 ACKs 后，Leader 就會(huì)向所有 Follower 的隊(duì)列發(fā)送 COMMIT消息坊夫，向所有 Observer 的隊(duì)列發(fā)送 Proposal砖第。
5. 當(dāng) Follower 收到 COMMIT 消息后，就會(huì)將事務(wù)正式更新到本地环凿。當(dāng) Observer 收到
   Proposal 后厂画，會(huì)直接將事務(wù)更新到本地。
6. 無(wú)論是 Follower 還是 Observer拷邢，在同步完成后都需要向 Leader 發(fā)送成功 ACK袱院。

（3）Observer 的數(shù)量問(wèn)題

Observer 數(shù)量并不是越多越好，一般與 Follower 數(shù)量相同瞭稼。因?yàn)?Observer 數(shù)量的增多雖不會(huì)增加事務(wù)操作壓力忽洛，但其需要從 Leader 同步數(shù)據(jù)，Observer 同步數(shù)據(jù)的時(shí)間是小于等于 Follower 同步數(shù)據(jù)的時(shí)間的环肘。當(dāng) Follower 同步數(shù)據(jù)完成欲虚，Leader 的 Observer 列表中的Observer 主機(jī)將結(jié)束同步。那些完成同步的 Observer 將會(huì)進(jìn)入到另一個(gè)對(duì)外提供服務(wù)的列表悔雹。那么复哆，那些沒(méi)有同步了數(shù)據(jù)無(wú)法提供服務(wù)的 Observer 主機(jī)就形成了資源浪費(fèi)。
所以腌零，對(duì)于事務(wù)操作發(fā)生頻繁的系統(tǒng)梯找，不建議使用過(guò)多的 Observer。

Leader 中保存的 Observer 列表其實(shí)有兩個(gè)：
all：包含所有 Observer益涧。
service：已經(jīng)完成了從 Leader 同步數(shù)據(jù)的任務(wù)锈锤。service <= all。其是動(dòng)態(tài)的。

Leader 中保存的 Follower 列表其實(shí)也有兩個(gè)：
all：要求其中必須有過(guò)半的 Follower 向Leader 反饋ACK
service：

4.9 恢復(fù)模式的三個(gè)原則

當(dāng)集群正在啟動(dòng)過(guò)程中久免，或 Leader 崩潰后浅辙，集群就進(jìn)入了恢復(fù)模式。對(duì)于要恢復(fù)的數(shù)據(jù)狀態(tài)需要遵循三個(gè)原則阎姥。

（1）Leader 的主動(dòng)出讓原則

若集群中 Leader 收到的 Follower 心跳數(shù)量沒(méi)有過(guò)半记舆，此時(shí) Leader 會(huì)自認(rèn)為自己與集群的連接已經(jīng)出現(xiàn)了問(wèn)題，其會(huì)主動(dòng)修改自己的狀態(tài)為 LOOKING呼巴，去查找新的 Leader泽腮。
而其它 Server 由于有過(guò)半的主機(jī)認(rèn)為已經(jīng)丟失了 Leader，所以它們會(huì)發(fā)起新的 Leader選舉伊磺，選出一個(gè)新的 Leader盛正。

（2）已被處理的消息不能丟

正常情況下，當(dāng) Leader 收到超過(guò)半數(shù) Follower 的 ACKs 后屑埋，就向各個(gè) Follower 廣播COMMIT 消息豪筝，批準(zhǔn)各個(gè)Server 執(zhí)行該寫(xiě)操作事務(wù)。當(dāng)各個(gè)Server 在接收到Leader 的COMMIT 消息后就會(huì)在本地執(zhí)行該寫(xiě)操作摘能，然后會(huì)向客戶(hù)端響應(yīng)寫(xiě)操作成功续崖。
但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就掛了，這將導(dǎo)致一種后果：部分 Server 已經(jīng)執(zhí)行了該事務(wù)团搞，而部分 Server 尚未收到 COMMIT 消息严望，所以其并沒(méi)有執(zhí)行該事務(wù)棚点。當(dāng)新的 Leader 被選舉出滔韵，集群經(jīng)過(guò)恢復(fù)模式后需要保證所有 Server 上都執(zhí)行了那些已經(jīng)被部分 Server 執(zhí)行過(guò)的事務(wù)逃沿。

（3）被丟棄的消息不能再現(xiàn)

當(dāng)在 Leader 新事務(wù)已經(jīng)通過(guò)咽斧，其已經(jīng)將該事務(wù)更新到了本地，但所有 Follower 還都沒(méi)有收到 COMMIT 之前俱萍，Leader 宕機(jī)了库菲，此時(shí)琐鲁，所有 Follower 根本就不知道該 Proposal 的存在挽拂。當(dāng)新的 Leader 選舉出來(lái)惭每，整個(gè)集群進(jìn)入正常服務(wù)狀態(tài)后，之前掛了的 Leader 主機(jī)重新啟動(dòng)并注冊(cè)成為了 Follower亏栈。若那個(gè)別人根本不知道的 Proposal 還保留在那個(gè)主機(jī)台腥，那么其數(shù)據(jù)就會(huì)比其它主機(jī)多出了內(nèi)容，導(dǎo)致整個(gè)系統(tǒng)狀態(tài)的不一致绒北。所以黎侈，該 Proposa 應(yīng)該被丟棄。類(lèi)似這樣應(yīng)該被丟棄的事務(wù)镇饮，是不能再次出現(xiàn)在集群中的蜓竹，應(yīng)該被清除箕母。

5 高可用集群的容災(zāi)

5.1 服務(wù)器數(shù)量的奇數(shù)與偶數(shù)

前面我們說(shuō)過(guò)储藐，無(wú)論是寫(xiě)操作投票俱济，還是 Leader 選舉投票，都必須過(guò)半才能通過(guò)钙勃，也就是說(shuō)若出現(xiàn)超過(guò)半數(shù)的主機(jī)宕機(jī)蛛碌，則投票永遠(yuǎn)無(wú)法通過(guò)∠皆矗基于該理論蔚携，由 5 臺(tái)主機(jī)構(gòu)成的集群，最多只允許 2 臺(tái)宕機(jī)克饶。而由 6 臺(tái)構(gòu)成的集群酝蜒，其最多也只允許 2 臺(tái)宕機(jī)。即矾湃，6 臺(tái)與5 臺(tái)的容災(zāi)能力是相同的亡脑。基于此容災(zāi)能力的原因邀跃，建議使用奇數(shù)臺(tái)主機(jī)構(gòu)成集群霉咨，以避免資源浪費(fèi)。
但從系統(tǒng)吞吐量上說(shuō)拍屑，6 臺(tái)主機(jī)的性能一定是高于 5 臺(tái)的途戒。所以使用 6 臺(tái)主機(jī)并不是資源浪費(fèi)。

5.2 容災(zāi)設(shè)計(jì)方案

對(duì)于一個(gè)高可用的系統(tǒng)僵驰，除了要設(shè)置多臺(tái)主機(jī)部署為一個(gè)集群避免單點(diǎn)問(wèn)題外喷斋，還需要考慮將集群部署在多個(gè)機(jī)房、多個(gè)樓宇蒜茴。對(duì)于多個(gè)機(jī)房星爪、樓宇中集群也是不能隨意部署的， 下面就多個(gè)機(jī)房的部署進(jìn)行分析矮男。
在多機(jī)房部署設(shè)計(jì)中移必，要充分考慮“過(guò)半原則”，也就是說(shuō)毡鉴，盡量要確保 zk 集群中有過(guò)半的機(jī)器能夠正常運(yùn)行崔泵。

（1）三機(jī)房部署

在生產(chǎn)環(huán)境下，三機(jī)房部署是最常見(jiàn)的猪瞬、容災(zāi)性最好的部署方案憎瘸。三機(jī)房部署中要求每個(gè)機(jī)房中的主機(jī)數(shù)量必須少于集群總數(shù)的一半。

（2）雙機(jī)房部署

zk 官方?jīng)]有給出較好的雙機(jī)房部署的容災(zāi)方案陈瘦。只能是讓其中一個(gè)機(jī)房占有超過(guò)半數(shù)的主機(jī)幌甘，使其做為主機(jī)房，而另一機(jī)房少于半數(shù)。當(dāng)然锅风，若主機(jī)房出現(xiàn)問(wèn)題酥诽，則整個(gè)集群會(huì)癱瘓。

6 CAP 定理

6.1 簡(jiǎn)介

CAP 定理又稱(chēng) CAP 原則皱埠，指的是在一個(gè)分布式系統(tǒng)中肮帐，Consistency（一致性）、Availability（可用性）边器、Partition tolerance（分區(qū)容錯(cuò)性）训枢，三者不可兼得。

• 一致性（C）：分布式系統(tǒng)中多個(gè)主機(jī)之間是否能夠保持?jǐn)?shù)據(jù)一致的特性忘巧。即恒界，當(dāng)系統(tǒng)數(shù)據(jù)發(fā)生更新操作后，各個(gè)主機(jī)中的數(shù)據(jù)仍然處于一致的狀態(tài)砚嘴。
• 可用性（A）：系統(tǒng)提供的服務(wù)是否一直處于可用的狀態(tài)十酣，即對(duì)于用戶(hù)的每一個(gè)請(qǐng)求，系統(tǒng)是否總是可以在有限的時(shí)間內(nèi)對(duì)用戶(hù)做出響應(yīng)枣宫。
• 分區(qū)容錯(cuò)性（P）：分布式系統(tǒng)在遇到任何網(wǎng)絡(luò)分區(qū)故障時(shí)婆誓，仍能夠保證對(duì)外提供滿(mǎn)足一致性和可用性的服務(wù)。
  分區(qū)是網(wǎng)絡(luò)分區(qū)也颤。

對(duì)于分布式系統(tǒng)洋幻，網(wǎng)絡(luò)環(huán)境相對(duì)是不可控的，出現(xiàn)網(wǎng)絡(luò)分區(qū)是不可避免的翅娶，因此系統(tǒng)必須具備分區(qū)容錯(cuò)性文留。但其并不能同時(shí)保證一致性與可用性。CAP 原則對(duì)于一個(gè)分布式系統(tǒng)來(lái)說(shuō)竭沫，只可能滿(mǎn)足兩項(xiàng)燥翅，即要么 CP，要么 AP蜕提。

6.2 BASE 理論

BASE 是Basically Available（基本可用）森书、Soft state（軟狀態(tài)）和 Eventually consistent（最終一致性）三個(gè)短語(yǔ)的簡(jiǎn)寫(xiě)。

BASE 理論的核心思想是：即使無(wú)法做到實(shí)時(shí)一致性谎势，但每個(gè)系統(tǒng)都可以根據(jù)自身的業(yè)務(wù)特點(diǎn)凛膏，采用適當(dāng)?shù)姆绞絹?lái)使系統(tǒng)達(dá)到最終一致性。

（1）基本可用

基本可用是指分布式系統(tǒng)在出現(xiàn)不可預(yù)知故障的時(shí)候脏榆，允許損失部分可用性猖毫。
損失響應(yīng)時(shí)間：
損失功能：

（2）軟狀態(tài)

軟狀態(tài)，是指允許系統(tǒng)數(shù)據(jù)存在的中間狀態(tài)须喂，并認(rèn)為該中間狀態(tài)的存在不會(huì)影響系統(tǒng)的整體可用性吁断，即允許系統(tǒng)主機(jī)間進(jìn)行數(shù)據(jù)同步的過(guò)程存在一定延時(shí)趁蕊。軟狀態(tài)，其實(shí)就是一種灰度狀態(tài)仔役，過(guò)渡狀態(tài)掷伙。

（3）最終一致性

最終一致性強(qiáng)調(diào)的是系統(tǒng)中所有的數(shù)據(jù)副本，在經(jīng)過(guò)一段時(shí)間的同步后骂因，最終能夠達(dá)到一個(gè)一致的狀態(tài)炎咖。因此赃泡，最終一致性的本質(zhì)是需要系統(tǒng)保證最終數(shù)據(jù)能夠達(dá)到一致寒波，而不需要實(shí)時(shí)保證系統(tǒng)數(shù)據(jù)的一致性。

（4）總結(jié)

從達(dá)到一致性的時(shí)間角度來(lái)劃分升熊，可以分為：

• 實(shí)時(shí)一致性：?jiǎn)螜C(jī)情況下可以實(shí)現(xiàn)實(shí)時(shí)一致性
• 最終一致性：經(jīng)過(guò)一段時(shí)間后可以達(dá)到一致性

單從客戶(hù)端訪(fǎng)問(wèn)到的內(nèi)容角度來(lái)劃分俄烁，可以分為：

• 強(qiáng)一致性（嚴(yán)格一致性）：
• 弱一致性：允許客戶(hù)端訪(fǎng)問(wèn)不到部分或全部更新過(guò)的數(shù)據(jù)。

6.3 ZK 與 CP

zk 遵循的是 CP 原則级野，即保證了一致性页屠，但犧牲了可用性。體現(xiàn)在哪里呢蓖柔？

當(dāng) Leader 宕機(jī)后辰企，zk 集群會(huì)馬上進(jìn)行新的 Leader 的選舉。但選舉時(shí)長(zhǎng)一般在 200 毫秒內(nèi)况鸣，最長(zhǎng)不超過(guò) 60 秒牢贸，整個(gè)選舉期間 zk 集群是不接受客戶(hù)端的讀寫(xiě)操作的，即 zk 集群是處于癱瘓狀態(tài)的镐捧。所以潜索，其不滿(mǎn)足可用性。

6.4 zk 可能會(huì)存在腦裂

這里說(shuō)的zk可能會(huì)引發(fā)腦裂懂酱，是指的在多機(jī)房部署中竹习，若出現(xiàn)了網(wǎng)絡(luò)連接問(wèn)題，形成多個(gè)分區(qū)列牺，則可能會(huì)出現(xiàn)腦裂問(wèn)題整陌，可能會(huì)導(dǎo)致數(shù)據(jù)不一致。
（1）情況一

07.png

（2）情況二

08.png

09.png

10.png

（5）情況五

11.png