[[424686]]

上次跟學(xué)弟學(xué)妹們聊完了Spring相關(guān)的一些知識(shí)點(diǎn)，學(xué)弟學(xué)妹們還是挺開心的，但是上次有學(xué)弟在跟我留言，在出去面試的時(shí)候被面試官問了個(gè)一臉蒙逼急的問題：

zookeeper你用過嗎?作為注冊(cè)中心它是怎么如何保證CP的呢?

為了對(duì)的起學(xué)弟學(xué)妹們的信賴這次跟大家具體聊聊zookeeper中的一致性選舉算法Paxos算法

什么是CAP?

CAP理論指的是在一個(gè)分布式系統(tǒng)中，不可能同時(shí)滿足Consistency(一致性)、Availablity(可用性)、Partition tolerance(分區(qū)容錯(cuò)性)這三個(gè)基本需求，最多只能滿足其中的兩項(xiàng)。

• 一致性(Consistency)：數(shù)據(jù)在不同的副本之間數(shù)據(jù)是保持一致的，并且當(dāng)執(zhí)行數(shù)據(jù)更新之后，各個(gè)副本之間能然是處于一致的狀態(tài)。
• 可用性(Availablity)：系統(tǒng)提供的服務(wù)必須是處于一直可用的狀態(tài)，針對(duì)每一次對(duì)系統(tǒng)的請(qǐng)求操作在設(shè)定的時(shí)間內(nèi)，都能得到正常的result返回。
• 分區(qū)容錯(cuò)性(Partition tolerance)：分布式系統(tǒng)在遇到任何網(wǎng)絡(luò)分區(qū)故障的時(shí)候，仍然需要能夠保證對(duì)外提供滿足一致性和可用性的服務(wù)，除非整個(gè)網(wǎng)絡(luò)環(huán)境全部癱瘓了。

什么是三二原則?

• 對(duì)于分布式系統(tǒng)，在CAP原則中，P是一定要保證的，如果沒有分區(qū)容錯(cuò)性那這個(gè)系統(tǒng)就太脆落了，但是并不能同時(shí)保證一致性或者可用性，在現(xiàn)在我們的分布式系統(tǒng)中，滿足一致性，則必然會(huì)失去可用性，滿足可用性，則必然失去一執(zhí)性。所以CAP原則對(duì)一個(gè)分布式系統(tǒng)來說要么滿足AP，要么滿足CP，這就是三二原則。

Zookeeper與Eureka的區(qū)別?

• Zookeeper遵循是的CP原則，即保證了一致性，失去了可用性，體現(xiàn)在當(dāng)Leader宕機(jī)后，zk 集群會(huì)馬上進(jìn)行新的 Leader 的選舉，但是選舉的這個(gè)過程是處于癱瘓狀態(tài)的。所以其不滿足可用性。
• Eureka遵循的是AP原則，即保證了高可用，失去了一執(zhí)行。每臺(tái)服務(wù)器之間都有心跳檢測(cè)機(jī)制，而且每臺(tái)服務(wù)器都能進(jìn)行讀寫，通過心跳機(jī)制完成數(shù)據(jù)共享同步，所以當(dāng)一臺(tái)機(jī)器宕機(jī)之后，其他的機(jī)器可以正常工作，但是可能此時(shí)宕機(jī)的機(jī)器還沒有進(jìn)行數(shù)據(jù)共享同步，所以其不滿足一致性。

言歸正轉(zhuǎn)，基礎(chǔ)就跟大家聊到這里了，開始直接開始正文吧!!!

Paxos算法

• Paxos 算法是萊斯利·蘭伯特(Leslie Lamport)1990 年提出的一種基于消息傳遞的、具有高容錯(cuò)性的一致性算法。Google Chubby 的作者 Mike Burrows 說過，世上只有一種一致性算法， 那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。
• Paxos 算法是一種公認(rèn)的晦澀難懂的算法，并且工程實(shí)現(xiàn)上也具有很大難度。
• 所以 Paxos算法主要用來解決我們的分布式系統(tǒng)中如何根據(jù)表決達(dá)成一致。

算法前置理解

首先需要理解的是算法中的三種角色

• Proposer(提議者)
• Acceptor(決策者)
• Learners(群眾)

一個(gè)提案的決策者(Acceptor)會(huì)存在多個(gè)，但在一個(gè)集群中提議者(Proposer)也是可能存在多個(gè)的，不同的提議者(Proposer)會(huì)提出不同的提案。

paxos算法特點(diǎn)：

• 沒有提案被提出則不會(huì)有提案被選定。
• 每個(gè)提議者在提出提案時(shí)都會(huì)首先獲取到一個(gè)具有全局唯一性的、遞增的提案編號(hào) N， 即在整個(gè)集群中是唯一的編號(hào)N，然后將該編號(hào)賦予其要提出的提案。(在zookeeper中就是zxid，由epoch 和xid組成)
• 每個(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è)提案被選定，則其它服務(wù)器會(huì)主動(dòng)同步(Learn)該提案到本地。

Paxos算法整個(gè)選舉的過程可以分為兩個(gè)階段來理解。

階段一

這個(gè)階段主要是準(zhǔn)備階段發(fā)送提議

• 提議者(Proposer)準(zhǔn)備提交一個(gè)編號(hào)為 N 的提議，于是其首先向所有表決者(Acceptor)發(fā)送 prepare(N)請(qǐng)求，用于試探集群是否支持該編號(hào)的提議。
• 每個(gè)決策者(Acceptor)中都保存著自己曾經(jīng) accept 過的提議中的最大編號(hào) maxN。當(dāng)一個(gè)表決者接收到其它主機(jī)發(fā)送來的 prepare(N)請(qǐng)求時(shí)，其會(huì)比較 N 與 maxN 的值。
• 若 N 小于 maxN，則說明該提議已過時(shí)，當(dāng)前表決者采取不回應(yīng)來拒絕該 prepare 請(qǐng)求
• 若N 大于maxN，則說明該提議是可以接受的，當(dāng)前表決者會(huì)首先將該 N 記錄下來， 并將其曾經(jīng)已經(jīng) accept 的編號(hào)最大的提案 Proposal(myid,maxN,value)反饋給提議者， 以向提議者展示自己支持的提案意愿。其中第一個(gè)參數(shù) myid 表示表決者 Acceptor 的標(biāo)識(shí) id，第二個(gè)參數(shù)表示其曾接受的提案的最大編號(hào) maxN，第三個(gè)參數(shù)表示該提案的真正內(nèi)容 value。
• 若當(dāng)前表決者還未曾 accept 過任何提議(第一次初始化的時(shí)候)，則會(huì)將Proposal(myid,null,null)反饋給提議者。
• 在當(dāng)前階段 N 不可能等于maxN。這是由 N 的生成機(jī)制決定的。要獲得 N 的值， 其必定會(huì)在原來數(shù)值的基礎(chǔ)上采用同步鎖方式增一

階段二

當(dāng)前階段要是真正的發(fā)送接收階段又被稱為Accept階段

• 當(dāng)提議者(Proposer)發(fā)出 prepare(N)后，若收到了超過半數(shù)的決策者(Accepter)的反饋， 那么該提議者就會(huì)將其真正的提案 Proposal(N,value)發(fā)送給所有的表決者。
• 當(dāng)決策者(Acceptor)接收到提議者發(fā)送的 Proposal(N,value)提案后，會(huì)再次拿出自己曾經(jīng)accept 過的提議中的最大編號(hào) maxN，及曾經(jīng)記錄下的 prepare 的最大編號(hào)，讓 N 與它們進(jìn)行比較，若N 大等于于這兩個(gè)編號(hào)，則當(dāng)前表決者 accept 該提案，并反饋給提議者。若 N 小于這兩個(gè)編號(hào)，則決策者采取不回應(yīng)來拒絕該提議。
• 若提議者沒有接收到超過半數(shù)的表決者的 accept 反饋，則重新進(jìn)入 prepare 階段，遞增提案號(hào)，重新提出 prepare 請(qǐng)求。若提議者接收到的反饋數(shù)量超過了半數(shù)，則其會(huì)向外廣播兩類信息：
• 向曾 accept 其提案的表決者發(fā)送“可執(zhí)行數(shù)據(jù)同步信號(hào)”，即讓它們執(zhí)行其曾接收到的提案

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

看到這里可能很多學(xué)弟都是一臉懵逼，什么鬼?為了加深理解，讓整個(gè)過程更加的透明，還是舉例說明一下吧!!!

假設(shè)現(xiàn)在我們有三臺(tái)主機(jī)服務(wù)器從中選取leader(也可以選擇其他的更多的服務(wù)器，為了比較方便容易理解這里選少一點(diǎn))。所以這三臺(tái)主機(jī)它們就分別充當(dāng)著提議者(Proposer)、決策者(Acceptor)、Learners(群眾)三種角色。

所以假設(shè)現(xiàn)在開始模擬選舉，三臺(tái)服務(wù)分別開始獲取N(具有全局唯一性的、遞增的提案編號(hào) N)的值，此時(shí) serverOne(主機(jī)1) 就對(duì)應(yīng)這個(gè) ProposerOne(提議者1)、serverTwo(主機(jī)2)對(duì)應(yīng)ProposerTwo(提議者2)、serverThree(主機(jī)3)對(duì)應(yīng)ProposerThree(提議者3)。

為了整個(gè)流程比較簡(jiǎn)單清晰，過程中更好理解。他們的初始N值就特定的設(shè)置為 ServerOne(2)、ServerTwo(1)、ServerThree(3)，所以他們都要發(fā)送給提議(Proposal)給決策者(Acceptor)，讓它們進(jìn)行表決確定

• 名詞解析
• 提議(Proposal)：提議者向決策者發(fā)送的中間數(shù)據(jù)的包裝簡(jiǎn)稱提議。

同時(shí)每個(gè) 提議者(Proposer)向其中的兩個(gè)決策者(Acceptor)發(fā)送提案消息。所以假設(shè)：

ProposerOne(提議者1)向 AcceptorOne(決策者1)和AcceptorTwo(決策者2)、

ProposerTwo(提議者2)向AcceptorTwo(決策者2)和AcceptorThree(決策者3)、

ProposerThree(提議者3)向AcceptorTwo(決策者2)和AcceptorThree(決策者3)、

發(fā)送提案消息。為了流程結(jié)構(gòu)簡(jiǎn)單就向其中的2臺(tái)發(fā)送提案，但是也是已經(jīng)超過半票了，當(dāng)然也可以多選幾個(gè)主機(jī)，多發(fā)送提案，只是流程就復(fù)雜了一點(diǎn)不好理解了。注意點(diǎn)就是一定要超過半票。

那么整個(gè)圖可以如下所示：

所以根據(jù)上面的圖開始走第一階段

按照上面我們假設(shè)的流程開始執(zhí)行流程

ProposerOne(提議者1)向 AcceptorOne(決策者1)和AcceptorTwo(決策者2)

• AcceptorOne(決策者1)和AcceptorTwo(決策者2)第一次收到ProposerOne(提議者1)的提議(Proposal)，由于是第一次收到提議(Proposal)，本地沒有存儲(chǔ)最大的N值，所以都會(huì)接受ProposerOne(提議者1)的提議。
• 所以AcceptorOne(決策者1)和AcceptorTwo(決策者2)都會(huì)提議返回給ProposerOne(提議者1)告知我贊同你的提議。
• 同時(shí)AcceptorOne(決策者1)和AcceptorTwo(決策者2)因?yàn)槭盏降漠?dāng)前的最大提議編號(hào)N為2，并且保存在本地，所以想接受到其他的N值小于2時(shí)則不會(huì)回復(fù)提議。
• 而ProposerOne(提議者1)已經(jīng)收到超過半數(shù)返回，所以提議通過
• 此時(shí) ：
• AcceptorOne(決策者1)本地 N值為2
• AcceptorTwo(決策者2) 本地 N值為2
• AcceptorThree(決策者3)本地 N值為null

ProposerTwo(提議者2)向AcceptorTwo(決策者2)和AcceptorThree(決策者3)

• AcceptorTwo(決策者2)和AcceptorThree(決策者3)收到ProposerTwo(提議者2)的提議(Proposal)時(shí)。因?yàn)锳cceptorTwo(決策者2)之前已經(jīng)接受過ProposerOne(提議者1)的提議，所以本地的N值已經(jīng)存儲(chǔ)了2
• 當(dāng)ProposerTwo(提議者2)的N值為1的時(shí)候，小于本地存的最大N值，所以不給予通過，也就不回復(fù)ProposerTwo(提議者2)
• 而AcceptorThree(決策者3)因?yàn)檫@是第一次收到提議，沒有最大N值，所以同意提議(Proposal)，返回當(dāng)前提，更新本地N值。
• 最后ProposerTwo(提議者2)只收到AcceptorThree(決策者3)的同意反饋，沒有超過半數(shù)選擇，所以不給通過。
• 此時(shí) ：
• AcceptorOne(決策者1)本地 N值為2
• AcceptorTwo(決策者2) 本地 N值為2
• AcceptorThree(決策者3)本地 N值為1

ProposerThree(提議者3)向AcceptorTwo(決策者2)和AcceptorThree(決策者3)

• AcceptorTwo(決策者2)和AcceptorThree(決策者3)收到ProposerThree(提議者3)的提議(Proposal)時(shí)。因?yàn)?/li>
• AcceptorTwo(決策者2)和AcceptorThree(決策者3)都已經(jīng)都到過提議(Proposal)，所以AcceptorTwo(決策者2)收到ProposerThree(提議者3)的提議時(shí)，本地N值2小于ProposerThree(提議者3)的N值3，所以通過提議
• AcceptorThree(決策者3)因?yàn)楸镜刂笆盏阶畲蟮闹禐?，所以本次通過也通過提議，更新本次的N值為3
• 最后ProposerThree(提議者3)收到超過半數(shù)的同意反饋，所以通過。
• 此時(shí) ：
• AcceptorOne(決策者1)本地 N值為2
• AcceptorTwo(決策者2) 本地 N值為3
• AcceptorThree(決策者3)本地 N值為3

由于之前ProposerTwo(提議者2)向AcceptorTwo(決策者2)和AcceptorThree(決策者3)發(fā)出提議時(shí)，沒有超過半數(shù)投票。所以會(huì)從新獲取最大N值(具有全局唯一性的、遞增的提案編號(hào) N)，這個(gè)時(shí)候ProposerTwo(提議者2)本地獲取的N值為4所以會(huì)再次發(fā)起一輪投票

• AcceptorTwo(決策者2)和AcceptorThree(決策者3)再次收到ProposerTwo(提議者2)的提議(Proposal)時(shí)。AcceptorTwo(決策者2)和AcceptorThree(決策者3)本地存儲(chǔ)的最大N值都小于現(xiàn)在最新的ProposerTwo(提議者2)的N值4，所以全部通過返回提議，更新本地N值
• 當(dāng)ProposerTwo(提議者2)的N值為1的時(shí)候，小于本地存的最大N值，所以不給予通過，也就不回復(fù)ProposerTwo(提議者2)
• 最后ProposerTwo(提議者2)收到超過半數(shù)的同意反饋，所以通過。
• 此時(shí) ：
• AcceptorOne(決策者1)本地 N值為2
• AcceptorTwo(決策者2) 本地 N值為4
• AcceptorThree(決策者3)本地 N值為4

到此第一階段的工作就已經(jīng)完成了，整個(gè)流程都是文字較多，看起需要多看幾遍。同時(shí)我也給大家畫了一個(gè)流程圖如下：

由于上面已經(jīng)走完第一階段，那么接下來肯定就是第二階段的流程了

同時(shí)整體第二階段可以分為兩塊來理解，第一塊是正式提交提議，第二塊是表決確定階段

第一階段執(zhí)行完得到的結(jié)果：

Proposer

• ProposerOne(提議者1) 本地N值為2
• ProposerTwo(提議者2) 本地N值為4
• ProposerThree(提議者3) 本地N值為3

Acceptor

• AcceptorOne(決策者1) 本地N值為2
• AcceptorTwo(決策者2) 本地N值為4
• AcceptorThree(決策者3) 本地N值為4

第一塊：

• ProposerOne(提議者1)正式發(fā)出提議到AcceptorOne(決策者1)和AcceptorTwo(決策者2),通過第一階段的結(jié)果可以知道只有AcceptorOne(決策者1)表決通過，AcceptorTwo(決策者2)不通過因?yàn)樾∮诒镜豊值
• ProposerTwo(提議者2)正式發(fā)出提議到AcceptorTwo(決策者2)和AcceptorThree(決策者3)，同樣的通過第一階段的結(jié)果，可以知道兩個(gè)決策者都通過，所以超過半數(shù)投票
• ProposerThree(提議者3)正式發(fā)出提議到AcceptorTwo(決策者2)和AcceptorThree(決策者3)，同樣的通過第一階段的結(jié)果，可以知道兩個(gè)決策者都沒有通過

第二塊：

• 從上面的第一塊結(jié)果來看，只有**ProposerTwo(提議者2)**得到半數(shù)同意，所以ProposerTwo(提議者2)立馬就能成為leader。至此選舉狀態(tài)就結(jié)束，即ProposerTwo(提議者2)會(huì)發(fā)布廣播給所有的learner，通知它們過來同步數(shù)據(jù)。當(dāng)數(shù)據(jù)完成同步時(shí)，那個(gè)整個(gè)服務(wù)器的集群就能正常工作了。

總結(jié)

整個(gè)Paxos算法過程還是比較難理解，為了講明白這里面的流程都是按最簡(jiǎn)單的例子來的。這里面也可以有更多的機(jī)器發(fā)起更多的提議。但是整個(gè)流程那就更難理解了。

理解Paxos算法需要按上面的兩個(gè)階段來理解。第一階段是做什么，得到了什么結(jié)果，第二階段又是基于第一階段的結(jié)果執(zhí)行怎樣的一個(gè)選舉流程，這個(gè)是大家需要思考的重點(diǎn)。

這里主要是跟大家分享的是Paxos算法這個(gè)選舉過程，也有很多其他的優(yōu)化版本比如 Fast Paxos、EPaxos等等。

Zookeeper

在zookeeper中的選舉算法就是用的 Fast Paxos算法，為什么用Fast paxos?

Fast Paxos算法是Paxos的優(yōu)化版本，解決了Paxos算法的活鎖問題保證每次線程過來獲取到唯一的N值。

ZAB(Zookeeper Atomic BroadCast)原子廣播協(xié)議

ZAB其實(shí)就是上面算法的一種實(shí)現(xiàn)，所以Zookeeper也就是依賴ZAB來實(shí)現(xiàn)分布式數(shù)據(jù)的一致性的。

所以在zookeeper中，只有一臺(tái)服務(wù)器機(jī)器作為leader機(jī)器，所以當(dāng)客戶端鏈接到機(jī)器的某一個(gè)節(jié)點(diǎn)時(shí)

• 當(dāng)這個(gè)客戶端提交的是讀取數(shù)據(jù)請(qǐng)求，那么當(dāng)前連接的機(jī)器節(jié)點(diǎn)，就會(huì)把自己保存的數(shù)據(jù)返回出去。
• 當(dāng)這個(gè)客戶端提交的是寫數(shù)據(jù)請(qǐng)求時(shí)，首先會(huì)看當(dāng)前連接的節(jié)點(diǎn)是不是leader節(jié)點(diǎn)，如果不是leader節(jié)點(diǎn)則會(huì)轉(zhuǎn)發(fā)出去到leader機(jī)器的節(jié)點(diǎn)上，由leader機(jī)器寫入，然后廣播出去通知其他的節(jié)點(diǎn)過來同步數(shù)據(jù)

在ZAB中的三類角色

• Leader：ZK集群的老大，唯一的一個(gè)可以進(jìn)行寫數(shù)據(jù)的機(jī)器。
• Follower：ZK集群的具有一定職位的干活人。只能進(jìn)行數(shù)據(jù)的讀取，當(dāng)老大(leader)機(jī)器掛了之后可以參與選舉投票的機(jī)器。
• Observe：最小的干活小弟，只能進(jìn)行數(shù)據(jù)讀取，就算老大(leader)機(jī)器掛了，跟他一毛關(guān)系沒有，不能參與選舉投票的機(jī)器。

在ZAB中的三個(gè)重點(diǎn)數(shù)據(jù)

• Zxid：是zookeeper中的事務(wù)ID，總長(zhǎng)度為64位的長(zhǎng)度的Long類型數(shù)據(jù)。其中有兩部分構(gòu)成前32位是epoch后32位是xid
• Epoch：每一個(gè)leader都會(huì)有一個(gè)這個(gè)值，表示當(dāng)前l(fā)eader獲取到的最大N值，可以理解為“年代”
• Xid：事務(wù)ID，表示當(dāng)前zookeeper集群當(dāng)前提交的事物ID是多少(watch機(jī)制)，方便選舉的過程后不會(huì)出現(xiàn)事務(wù)重復(fù)執(zhí)行或者遺漏等一些特殊情況。

zookeeper中的一些知識(shí)點(diǎn)就分享到這里了，因?yàn)檫@里面還有很多很多東西，比如Session 、Znode、Watcher機(jī)制 、ACL、三種狀態(tài)模式 還zookeeper怎么實(shí)現(xiàn)分布式事務(wù)鎖等等。沒有辦法一次性跟大家聊完。

這次主要還是想讓學(xué)弟學(xué)妹了解清楚Zookeeper中的一致性的算法是怎么保證。

結(jié)尾

針對(duì)面試來說能完全的跟面試官講明白這個(gè)一致性算法，那你就已經(jīng)走在前面了。整個(gè)過程還是比較復(fù)雜的，需要自己不斷的多看多畫圖理解。

在這個(gè)互聯(lián)內(nèi)卷的時(shí)代，只有懂得比別人多才能走的比別人遠(yuǎn)。

最后希望我的學(xué)弟學(xué)妹們都能有一個(gè)好的校招結(jié)果!!!