之前在實習(xí)的時候用到了Elasticsearch仗扬，看了看它內(nèi)部的實現(xiàn)原理症概，發(fā)現(xiàn)ES自己實現(xiàn)了一套分布式一致性解決方法，覺得還挺有意思的厉颤。學(xué)習(xí)過程中很多資料都提到了Zookeeper穴豫，想起來大三的時候就在hadoop里看到的Zookeeper組件但是一直不知道它是干嘛的，最近不是特別忙就研究一下Zookeeper逼友。

簡介

ZooKeeper是一個高可用的一致性協(xié)調(diào)框架精肃，用來為分布式應(yīng)用提供一致性服務(wù)的軟件，提供的功能包括：配置維護帜乞、域名服務(wù)司抱、分布式同步、組服務(wù)等黎烈。這些功能實現(xiàn)起來非常復(fù)雜习柠，但Zookeeper可以提供給開發(fā)者性能高效匀谣，功能穩(wěn)定的服務(wù)。

Zookeeper原理

ZooKeeper為了高可用的一致性協(xié)調(diào)资溃，實現(xiàn)了一種通用的一致性算法ZAB（ZooKeeper Atomic Broadcast）
ZAB是在Fast Paxos算法基礎(chǔ)上進行了擴展改造而來的武翎，另一種一致性算法Raft也和ZAB非常類似，所以為了弄懂Zookeeper實現(xiàn)原理溶锭，我們比較這三種分布式一致性算法（Paxos宝恶，raft和ZAB）的異同：

Paxos

首先，我們來介紹一下Paxos算法趴捅，Lamport大神在1990年提出的這個基于消息傳遞且具有高度容錯特性的一致性算法垫毙，他提出了三種Paxos算法：Basic Paxos，Multi Paxos和Fast Paxos拱绑。Basic Paxos只能對一個值形成決議综芥，決議的形成至少需要兩次網(wǎng)絡(luò)來回，所以一般只用來進行理論研究猎拨；Multi Paxos和Fast Paxos則對它進行一系列的改動膀藐，使更適合直接應(yīng)用在實際項目中。

Basic Paxos
Paxos算法運行在允許宕機故障的異步系統(tǒng)中红省，不要求可靠的消息傳遞消请，可容忍消息丟失、延遲类腮、亂序以及重復(fù)臊泰。它利用大多數(shù) (Majority) 機制保證了2F+1的容錯能力蚜枢，即2F+1個節(jié)點的系統(tǒng)最多允許F個節(jié)點同時出現(xiàn)故障缸逃。
Paxos將系統(tǒng)中的角色分為提議者 (Proposer)，決策者 (Acceptor)厂抽，和最終決策學(xué)習(xí)者 (Learner)：

• Proposer: 提出提案 (Proposal)需频。Proposal信息包括提案編號 (Proposal ID) 和提議的值 (Value)。
• Acceptor：參與決策筷凤，回應(yīng)Proposers的提案昭殉。收到Proposal后可以接受提案，若Proposal獲得多數(shù)Acceptors的接受藐守，則稱該Proposal被批準挪丢。
• Learner：不參與決策，從Proposers/Acceptors學(xué)習(xí)最新達成一致的提案（Value）

Paxos算法通過一個決議分為兩個階段：

• Prepare階段：Proposer向Acceptors發(fā)出Prepare請求卢厂，Acceptors針對收到的Prepare請求進行Promise承諾

• Accept階段：Proposer收到多數(shù)Acceptors承諾的Promise后乾蓬，向Acceptors發(fā)出Propose請求，Acceptors針對收到的Propose請求進行Accept處理慎恒。

  Proposer	Acceptor
  1. 選擇一個proposal number n
  2. 廣播Prepare(n)和Value給所有的Accepter
  	3. 回復(fù)Prepare(n)任内，如果n > minProposal撵渡，則minProposal = n，同時將acceptedProposal和acceptedValue返回
  4. Proposer接收到過半數(shù)回復(fù)后死嗦，如果發(fā)現(xiàn)有acceptedValue返回趋距，將所有回復(fù)中acceptedProposal最大的acceptedValue作為本次提案的value，否則可以任意決定本次提案的value越除；如果沒超半數(shù)棚品，則重新發(fā)起Prepare請求
  5. 廣播Accept(n, value)給所有Accepter
  	6. Acceptor比較n和minProposal，如果n>=minProposal廊敌，則acceptedProposal=minProposal=n，acceptedValue=value门怪，本地持久化后骡澈，返回；否則掷空，返回minProposal
  7. Proposer接收到超半數(shù)的成功回復(fù)后肋殴，將結(jié)果通知給所有Learner；如果沒到半數(shù)坦弟，則重新發(fā)起Prepare請求

Multi Paxos

原始的Paxos算法只能對一個值進行決議护锤，而且每次決議至少需要兩次網(wǎng)絡(luò)來回，在實際應(yīng)用中可能會產(chǎn)生各種各樣的問題酿傍，所以不適合直接應(yīng)用在實際工程中烙懦。因此，Multi Paxos解決了這一問題赤炒，可以連續(xù)確定多個值并提高效率氯析，基于Basix Paxos主要做了如下改進：

• 針對每一個要確定的值，運行一次Paxos算法實例（Instance）莺褒，形成決議掩缓。每一個Paxos實例使用唯一的Instance ID標識。
• 在所有Proposers中選舉一個Leader遵岩，由Leader唯一地提交Proposal給Acceptors進行表決你辣。這樣沒有Proposer競爭，解決了活鎖問題尘执。在系統(tǒng)中僅有一個Leader進行Value提交的情況下舍哄，Prepare階段就可以跳過，從而將兩階段變?yōu)橐浑A段誊锭，提高效率蠢熄。

所以Multi Paxos的實際過程是：首先進行Leader選舉，利用Basic Paxos來實現(xiàn)炉旷。選出Leader后签孔，只由Leader來提交Proposal叉讥，如果Leader出現(xiàn)宕機，則重新選舉Leader饥追，在系統(tǒng)中僅有一個Leader可以提交Proposal图仓。
Multi Paxos通過改變Prepare階段的作用范圍至后面Leader提交的所有實例，從而使得Leader的連續(xù)提交只需要執(zhí)行一次Prepare階段但绕，后續(xù)只需要執(zhí)行Accept階段救崔，將兩階段變?yōu)橐浑A段，提高了效率捏顺。

Fast Paxos

在之前提到的Paxos協(xié)議中六孵，消息最后到達Learner一般都要經(jīng)歷 Client-->Proposer-->Acceptor-->Learner 總共3個步驟；為了更快的讓消息到達Learner幅骄，可以跳過Proposer這一步劫窒，直接將請求發(fā)送給Accepter，由Leader在中間進行檢查拆座。

• Leader檢測到?jīng)_突之后主巍，根據(jù)規(guī)定的算法從沖突中選擇一個數(shù)據(jù)，重新發(fā)送Accept請求挪凑。
• 當檢測到?jīng)_突的時候孕索，如果Acceptors自己就能解決沖突，那么就完全不需要Leader再次發(fā)送Accept請求了躏碳，這樣就又減少了一次請求搞旭，節(jié)省了時間

ZAB

基于Paxos，Zookeeper實現(xiàn)了ZAB算法菇绵，個人感覺ZAB和Multi Paxos更像一點选脊。
ZAB的算法流程為：

• Leader election：leader選舉過程，electionEpoch自增脸甘，在選舉的時候lastProcessedZxid越大恳啥，越有可能成為leader
• Discovery：
  • （1）leader收集follower的lastProcessedZxid，這個主要用來通過和leader的lastProcessedZxid對比來確認follower需要同步的數(shù)據(jù)范圍
  • （2）選舉出一個新的peerEpoch丹诀，主要用于防止舊的leader來進行提交操作（舊leader向follower發(fā)送命令的時候钝的，follower發(fā)現(xiàn)zxid所在的peerEpoch比現(xiàn)在的小，則直接拒絕铆遭，防止出現(xiàn)不一致性）
• Synchronization：
  follower中的事務(wù)日志和leader保持一致的過程硝桩，就是依據(jù)follower和leader之間的lastProcessedZxid進行，follower多的話則刪除掉多余部分枚荣，follower少的話則補充碗脊，一旦對應(yīng)不上則follower刪除掉對不上的zxid及其之后的部分然后再從leader同步該部分之后的數(shù)據(jù)
• Broadcast
  正常處理客戶端請求的過程。leader針對客戶端的事務(wù)請求橄妆，然后提出一個議案衙伶，發(fā)給所有的follower祈坠，一旦過半的follower回復(fù)OK的話，leader就可以將該議案進行提交了矢劲，向所有follower發(fā)送提交該議案的請求赦拘，leader同時返回OK響應(yīng)給客戶端

Raft

Raft算法是因為該作者覺得Paxos太難以理解了，所以就提出了Raft芬沉，一定程度上也可以看作是Paxos的一種改進躺同。它強化了leader的地位，把整個協(xié)議可以清楚的分割成兩個部分丸逸，并利用日志的連續(xù)性做了一些簡化： （1）Leader在時蹋艺。由Leader向Follower同步日志 （2）Leader掛掉了，選一個新Leader黄刚，Leader選舉算法捎谨。

算法演示：（這個演示很簡單明白，就不用文字講了）
Raft

主要區(qū)別

由于Paxos偏理論隘击，Raft和ZAB又都是基于他實現(xiàn)的，他們在整體思路上有一些地方還是挺像的研铆，但細節(jié)上有些不同埋同，所以我們主要比較這兩種算法，下面是我總結(jié)的幾個區(qū)別：

• 選舉過程
  • 基本實現(xiàn)：
    • ZooKeeper：在每次leader選舉完成之后棵红，都會進行數(shù)據(jù)之間的同步糾正凶赁，所以每一個輪次，大家都日志內(nèi)容都是統(tǒng)一的逆甜；
    • Raft：在leader選舉完成之后沒有這個同步過程虱肄，而是靠之后的AppendEntries RPC請求的一致性檢查來實現(xiàn)糾正過程，則就會出現(xiàn)上述案例中隔了幾個輪次還不統(tǒng)一的現(xiàn)象
  • 加入已完成選舉集群：
    • ZooKeeper：該server啟動后交煞，會向所有的server發(fā)送投票通知咏窿，這時候就會收到處于LOOKING、FOLLOWING狀態(tài)的server的投票（這種狀態(tài)下的投票指向的leader）素征，則該server放棄自己的投票集嵌，判斷上述投票是否過半，過半則可以確認該投票的內(nèi)容就是新的leader御毅。
    • Raft：比較簡單根欧，該server啟動后，會收到leader的AppendEntries RPC,這時就會從RPC中獲取leader信息端蛆，識別到leader凤粗，即使該leader是一個老的leader，之后新leader仍然會發(fā)送AppendEntries RPC,這時就會接收到新的leader了（因為新leader的term比老leader的term大今豆，所以會更新leader）
• 上一輪次的Leader
  • 處理策略
    • Zookeeper：采取激進的策略嫌拣，對于所有過半還是未過半的日志都判定為提交柔袁，都將其應(yīng)用到狀態(tài)機中
    • Raft：對于之前term的過半或未過半復(fù)制的日志采取的是保守的策略，全部判定為未提交亭罪，只有當當前term的日志過半了瘦馍，才會順便將之前term的日志進行提交
• 異常處理
  • Follower掛了
    • ZooKeeper：重啟之后，需要和當前l(fā)eader數(shù)據(jù)之間進行差異的確定应役，同時期間又有新的請求到來情组，所以需要暫時獲取leader數(shù)據(jù)的讀鎖，禁止此期間的數(shù)據(jù)更改箩祥，先將差異的數(shù)據(jù)先放入隊列院崇，差異確定完畢之后，還需要將leader中已提交的議案和未提交的議案也全部放入隊列
    • Raft：重啟之后袍祖，由于leader的AppendEntries RPC調(diào)用底瓣，識別到leader，leader仍然會按照leader的log進行順序復(fù)制蕉陋，也不用關(guān)心在復(fù)制期間新的添加的日志捐凭，在下一次同步中自動會同步
  • Leader掛了
    • ZooKeeper:ZooKeeper每次leader選舉之后都會進行數(shù)據(jù)同步，不會有亂序問題
    • Raft：Raft對于之前term的entry被過半復(fù)制暫不提交凳鬓，只有當本term的數(shù)據(jù)提交了才能將之前term的數(shù)據(jù)一起提交茁肠，也是能保證順序的

Zk基本特性

Zookeeper在設(shè)計了一套分布式一致性算法后，提供了一系列的基本特性缩举，供開發(fā)者使用：

• 構(gòu)建高可用分布式集群
  • Zookeeper的分布式一致性算法保證了集群的高可用性
• 集群配置統(tǒng)一管理
  • Zookeeper的數(shù)據(jù)模型類似文件系統(tǒng)垦梆，可以方便的進行集群配置的管理
• 發(fā)布和訂閱
  • 支持服務(wù)的發(fā)布和狀態(tài)監(jiān)聽機制
• 分布式鎖
  • Zookeeper利用選舉模式和數(shù)據(jù)模型可以實現(xiàn)分布式鎖，保證分布式系統(tǒng)的同步
• 數(shù)據(jù)的強一致性
  • 基于分布式一致性算法進行保證仅孩，當數(shù)據(jù)修改之后會同步到其他備份上

Zk主要應(yīng)用

• Hadoop
  • 分布式鎖托猩，保證只有一個ResourceManager創(chuàng)建成功
  • 監(jiān)聽狀態(tài)
  • 狀態(tài)存儲
• Hbase
  • 利用Zookeeper主從備份，狀態(tài)的保存和監(jiān)控辽慕，實現(xiàn)系統(tǒng)容錯
• Kafka
  • 注冊節(jié)點管理服務(wù)器
  • 注冊多節(jié)點京腥，實現(xiàn)負載均衡
• Dubbo
  • 用于服務(wù)注冊