序

本文主要講述2PC及3PC，以及Paxos以及Raft、ZAB協(xié)議。

兩類一致性(操作原子性與副本一致性)

2PC協(xié)議用于保證屬于多個(gè)數(shù)據(jù)分片上的操作的原子性。這些數(shù)據(jù)分片可能分布在不同的服務(wù)器上，2PC協(xié)議保證多臺(tái)服務(wù)器上的操作要么全部成功，要么全部失敗。

Paxos協(xié)議用于保證同一個(gè)數(shù)據(jù)分片的多個(gè)副本之間的數(shù)據(jù)一致性。當(dāng)這些副本分布到不同的數(shù)據(jù)中心時(shí)，這個(gè)需求尤其強(qiáng)烈。

一、2PC（阻塞、數(shù)據(jù)不一致問題、單點(diǎn)問題）

Two-PhaseCommit，兩階段提交

1、階段一：提交事務(wù)請(qǐng)求（投票階段）

（1）事務(wù)詢問

協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)

（2）執(zhí)行事務(wù)

各參與者節(jié)點(diǎn)執(zhí)行事務(wù)操作，并將Undo和Redo信息計(jì)入事務(wù)日志中

（3）各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)

如果參與者成功執(zhí)行了事務(wù)操作，那么就反饋給協(xié)調(diào)者Yes響應(yīng)，表示事務(wù)可以執(zhí)行；如果參與者沒有成功執(zhí)行事務(wù)，那么就反饋給協(xié)調(diào)者No響應(yīng)，表示事務(wù)不可以執(zhí)行。

2、階段二：執(zhí)行事務(wù)提交（執(zhí)行階段）

（1）執(zhí)行事務(wù)提交

如果所有參與者的反饋都是Yes響應(yīng)，那么

A、發(fā)送提交請(qǐng)求

協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Commit請(qǐng)求

B、事務(wù)提交

參與者接收到Commit請(qǐng)求后，會(huì)正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放在整個(gè)事務(wù)執(zhí)行期間占用的事務(wù)資源

C、反饋事務(wù)提交結(jié)果

參與者在完成事務(wù)提交之后，向協(xié)調(diào)者發(fā)送ACK信息

D、完成事務(wù)

協(xié)調(diào)者接收到所有參與者反饋的ACK消息后，完成事務(wù)

（2）中斷事務(wù)

任何一個(gè)參與者反饋了No響應(yīng)，或者在等待超時(shí)之后，協(xié)調(diào)者尚無法接收到所有參與者的反饋響應(yīng)，那么就會(huì)中斷事務(wù)。

A、發(fā)送回滾請(qǐng)求

協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Rollback請(qǐng)求

B、事務(wù)回滾

參與者接收到rollback請(qǐng)求后，會(huì)利用其在階段一中記錄的Undo信息來執(zhí)行事務(wù)回滾操作，并在完成回滾之后釋放整個(gè)事務(wù)執(zhí)行期間占用的資源

C、反饋事務(wù)回滾結(jié)果

參與者在完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送ACK信息

D、中斷事務(wù)

協(xié)調(diào)者接收到所有參與者反饋的ACK信息后，完成事務(wù)中斷

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：原理簡單、實(shí)現(xiàn)方便

缺點(diǎn)：同步阻塞、單點(diǎn)問題、數(shù)據(jù)不一致、太過保守

（1）同步阻塞

同步阻塞會(huì)極大地限制分布式系統(tǒng)的性能。在二階段提交的執(zhí)行過程中，所有參與該事務(wù)操作的邏輯都處于阻塞狀態(tài)，各個(gè)參與者在等待其他參與者響應(yīng)的過程中，將無法進(jìn)行其他任何操作。

（2）單點(diǎn)問題

一旦協(xié)調(diào)者出現(xiàn)問題，那么整個(gè)二階段提交流程將無法運(yùn)轉(zhuǎn)，更為嚴(yán)重的是，如果是在階段二中出現(xiàn)問題，那么其他參與者將會(huì)一直處于鎖定事務(wù)資源的狀態(tài)中，無法繼續(xù)完成事務(wù)操作。

（3）數(shù)據(jù)不一致

在階段二，當(dāng)協(xié)調(diào)者向所有參與者發(fā)送commit請(qǐng)求之后，發(fā)生了局部網(wǎng)絡(luò)異常或協(xié)調(diào)者在尚未發(fā)完commit請(qǐng)求之前自身發(fā)生了崩潰，導(dǎo)致最終只有部分參與者接收到了commit請(qǐng)求，于是這部分參與者執(zhí)行事務(wù)提交，而沒收到commit請(qǐng)求的參與者則無法進(jìn)行事務(wù)提交，于是整個(gè)分布式系統(tǒng)出現(xiàn)了數(shù)據(jù)不一致性現(xiàn)象。

（4）太過保守

如果參與者在與協(xié)調(diào)者通信期間出現(xiàn)故障，協(xié)調(diào)者只能靠超時(shí)機(jī)制來判斷是否需要中斷事務(wù)，這個(gè)策略比較保守，需要更為完善的容錯(cuò)機(jī)制，任意一個(gè)節(jié)點(diǎn)的失敗都會(huì)導(dǎo)致整個(gè)事務(wù)的失敗。

二、3PC（解決2PC的阻塞，但還是可能造成數(shù)據(jù)不一致）

Three-Phase Commit，三階段提交，分為CanCommit、PreCommit、do Commit三個(gè)階段。

為了避免在通知所有參與者提交事務(wù)時(shí)，其中一個(gè)參與者crash不一致時(shí)，就出現(xiàn)了三階段提交的方式。三階段提交在兩階段提交的基礎(chǔ)上增加了一個(gè)preCommit的過程，當(dāng)所有參與者收到preCommit后，并不執(zhí)行動(dòng)作，直到收到commit或超過一定時(shí)間后才完成操作。

1、階段一CanCommit

（1）事務(wù)詢問

協(xié)調(diào)者向各參與者發(fā)送CanCommit的請(qǐng)求，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的響應(yīng)

（2）參與者向協(xié)調(diào)者反饋詢問的響應(yīng)

參與者收到CanCommit請(qǐng)求后，正常情況下，如果自身認(rèn)為可以順利執(zhí)行事務(wù)，那么會(huì)反饋Yes響應(yīng)，并進(jìn)入預(yù)備狀態(tài)，否則反饋No。

2、階段二PreCommit

（1）執(zhí)行事務(wù)預(yù)提交

如果協(xié)調(diào)者接收到各參與者反饋都是Yes，那么執(zhí)行事務(wù)預(yù)提交

A、發(fā)送預(yù)提交請(qǐng)求

協(xié)調(diào)者向各參與者發(fā)送preCommit請(qǐng)求，并進(jìn)入prepared階段

B、事務(wù)預(yù)提交

參與者接收到preCommit請(qǐng)求后，會(huì)執(zhí)行事務(wù)操作，并將Undo和Redo信息記錄到事務(wù)日記中

C、各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的響應(yīng)

如果各參與者都成功執(zhí)行了事務(wù)操作，那么反饋給協(xié)調(diào)者Ack響應(yīng)，同時(shí)等待最終指令，提交commit或者終止abort

（2）中斷事務(wù)

如果任何一個(gè)參與者向協(xié)調(diào)者反饋了No響應(yīng)，或者在等待超時(shí)后，協(xié)調(diào)者無法接收到所有參與者的反饋，那么就會(huì)中斷事務(wù)。

A、發(fā)送中斷請(qǐng)求

協(xié)調(diào)者向所有參與者發(fā)送abort請(qǐng)求

B、中斷事務(wù)

無論是收到來自協(xié)調(diào)者的abort請(qǐng)求，還是等待超時(shí)，參與者都中斷事務(wù)

3、階段三doCommit

（1）執(zhí)行提交

A、發(fā)送提交請(qǐng)求

假設(shè)協(xié)調(diào)者正常工作，接收到了所有參與者的ack響應(yīng)，那么它將從預(yù)提交階段進(jìn)入提交狀態(tài)，并向所有參與者發(fā)送doCommit請(qǐng)求

B、事務(wù)提交

參與者收到doCommit請(qǐng)求后，正式提交事務(wù)，并在完成事務(wù)提交后釋放占用的資源

C、反饋事務(wù)提交結(jié)果

參與者完成事務(wù)提交后，向協(xié)調(diào)者發(fā)送ACK信息

D、完成事務(wù)

協(xié)調(diào)者接收到所有參與者ack信息，完成事務(wù)

（2）中斷事務(wù)

假設(shè)協(xié)調(diào)者正常工作，并且有任一參與者反饋No，或者在等待超時(shí)后無法接收所有參與者的反饋，都會(huì)中斷事務(wù)

A、發(fā)送中斷請(qǐng)求

協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)送abort請(qǐng)求

B、事務(wù)回滾

參與者接收到abort請(qǐng)求后，利用undo日志執(zhí)行事務(wù)回滾，并在完成事務(wù)回滾后釋放占用的資源

C、反饋事務(wù)回滾結(jié)果

參與者在完成事務(wù)回滾之后，向協(xié)調(diào)者發(fā)送ack信息

D、中斷事務(wù)

協(xié)調(diào)者接收到所有參與者反饋的ack信息后，中斷事務(wù)。

階段三可能出現(xiàn)的問題：

協(xié)調(diào)者出現(xiàn)問題、協(xié)調(diào)者與參與者之間網(wǎng)絡(luò)出現(xiàn)故障。不論出現(xiàn)哪種情況，最終都會(huì)導(dǎo)致參與者無法及時(shí)接收到來自協(xié)調(diào)者的doCommit或是abort請(qǐng)求，針對(duì)這種情況，參與者都會(huì)在等待超時(shí)后，繼續(xù)進(jìn)行事務(wù)提交（timeout后中斷事務(wù)）。

優(yōu)點(diǎn)：降低參與者阻塞范圍，并能夠在出現(xiàn)單點(diǎn)故障后繼續(xù)達(dá)成一致

缺點(diǎn)：引入preCommit階段，在這個(gè)階段如果出現(xiàn)網(wǎng)絡(luò)分區(qū)，協(xié)調(diào)者無法與參與者正常通信，參與者依然會(huì)進(jìn)行事務(wù)提交，造成數(shù)據(jù)不一致。

三、Paxos（解決單點(diǎn)問題）

基于消息傳遞且具有高度容錯(cuò)性的一致性算法。Paxos算法要解決的問題就是如何在可能發(fā)生幾起宕機(jī)或網(wǎng)絡(luò)異常的分布式系統(tǒng)中，快速且正確地在集群內(nèi)部對(duì)某個(gè)數(shù)據(jù)的值達(dá)成一致，并且保證不論發(fā)生以上任何異常，都不會(huì)破壞整個(gè)系統(tǒng)的一致性。

拜占庭問題：消息不完整或者被篡改。Paxos在維持領(lǐng)導(dǎo)者選舉或者變量修改一致性上，采取一種類似議會(huì)投票的過半同意機(jī)制，比如設(shè)定一個(gè)領(lǐng)導(dǎo)者，需要將此看做一個(gè)議案，征求過半同意，每個(gè)節(jié)點(diǎn)通過一個(gè)議案會(huì)有編號(hào)記錄，再次收到此領(lǐng)導(dǎo)者的不同人選，發(fā)現(xiàn)已經(jīng)有編號(hào)記錄便駁回，最后以多數(shù)通過的結(jié)果為準(zhǔn)。

我們舉個(gè)簡單的例子，來闡述一下Paxos的基本思想：假設(shè)我們有5臺(tái)計(jì)算機(jī)A、B、C、D、E，每臺(tái)計(jì)算機(jī)保存著公司CEO的信息，現(xiàn)在CEO任期到了，需要進(jìn)行新一界選舉了。

A計(jì)算機(jī)發(fā)起一個(gè)選舉議案，提議CEO為“張三”，如果沒有其他候選人議案，也沒有網(wǎng)絡(luò)問題，只要其中半數(shù)以上計(jì)算機(jī)收到并通過議案，那么最終“張三”當(dāng)選CEO。由于是分布式環(huán)境，并發(fā)請(qǐng)求、機(jī)器故障、網(wǎng)絡(luò)故障等問題是常態(tài)，如果A和E同時(shí)提交選舉議案，A提名“張三”，E提名“李四”，那么肯定會(huì)涉及多計(jì)算機(jī)的一致性問題了：假設(shè)A、B、C先收到A的議案，D、E先收到E的議案，那么A繼續(xù)提交給D時(shí)，D告訴它已經(jīng)先收到E的議案了，因此駁回了A的請(qǐng)求。同樣E繼續(xù)提交給A、B、C時(shí)也碰到相同的問題。

我們可以通過“在每臺(tái)計(jì)算機(jī)同時(shí)接受議案提交時(shí)設(shè)置一個(gè)編號(hào)，編號(hào)先的通過，編號(hào)后的駁回”的方式來實(shí)現(xiàn)。議案提交上去后，發(fā)現(xiàn)A、B、C投票“張三”為CEO，D、E投票“李四”為CEO，少數(shù)服從多數(shù)，因此最后結(jié)果為“張三”當(dāng)選CEO。

如果是C計(jì)算機(jī)發(fā)生了網(wǎng)絡(luò)問題或者故障，雙方投票相同，那么選舉無法完成。

如果C計(jì)算機(jī)發(fā)生了網(wǎng)絡(luò)問題或者故障，A、B、D投票“張三”，E投票“李四”，那么結(jié)果為“張三”當(dāng)選，而C對(duì)于這些情況一無所知，但是當(dāng)C計(jì)算機(jī)恢復(fù)正常時(shí)，他會(huì)發(fā)起一個(gè)“詢問誰是CEO”的議案獲取最新信息。簡言之，Paxos對(duì)每個(gè)節(jié)點(diǎn)的并發(fā)修改采取編號(hào)記錄的方式保持一致性，對(duì)多個(gè)節(jié)點(diǎn)的并發(fā)修改采取少數(shù)服從多數(shù)的方式保持一致性。Paxos有點(diǎn)類似分布式二階段提交方式，但是又不同，二階段提交不能是多數(shù)節(jié)點(diǎn)同意，必須是全部同意。為了遵守過半節(jié)點(diǎn)同意的約束，Paxos算法往往要求節(jié)點(diǎn)總數(shù)為奇數(shù)。

Paxos 算法解決的問題是在一個(gè)可能發(fā)生上述異常的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。一個(gè)典型的場景是，在一個(gè)分布式數(shù)據(jù)庫系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)「一致性算法」以保證每個(gè)節(jié)點(diǎn)看到的指令一致。一個(gè)通用的一致性算法可以應(yīng)用在許多場景中，是分布式計(jì)算中的重要問題。從20世紀(jì)80年代起對(duì)于一致性算法的研究就沒有停止過。

簡單說來，Paxos的目的是讓整個(gè)集群的結(jié)點(diǎn)對(duì)某個(gè)值的變更達(dá)成一致。Paxos算法基本上來說是個(gè)民主選舉的算法——大多數(shù)的決定會(huì)成個(gè)整個(gè)集群的統(tǒng)一決定。任何一個(gè)點(diǎn)都可以提出要修改某個(gè)數(shù)據(jù)的提案，是否通過這個(gè)提案取決于這個(gè)集群中是否有超過半數(shù)的結(jié)點(diǎn)同意（所以Paxos算法需要集群中的結(jié)點(diǎn)是單數(shù)）。

這個(gè)算法有兩個(gè)階段（假設(shè)這個(gè)有三個(gè)結(jié)點(diǎn)：A，B，C）：

第一階段：Prepare階段

A把申請(qǐng)修改的請(qǐng)求Prepare Request發(fā)給所有的結(jié)點(diǎn)A，B，C。注意，Paxos算法會(huì)有一個(gè)Sequence Number（你可以認(rèn)為是一個(gè)提案號(hào)，這個(gè)數(shù)不斷遞增，而且是唯一的，也就是說A和B不可能有相同的提案號(hào)），這個(gè)提案號(hào)會(huì)和修改請(qǐng)求一同發(fā)出，任何結(jié)點(diǎn)在“Prepare階段”時(shí)都會(huì)拒絕其值小于當(dāng)前提案號(hào)的請(qǐng)求。所以，結(jié)點(diǎn)A在向所有結(jié)點(diǎn)申請(qǐng)修改請(qǐng)求的時(shí)候，需要帶一個(gè)提案號(hào)，越新的提案，這個(gè)提案號(hào)就越是是最大的。

如果接收結(jié)點(diǎn)收到的提案號(hào)n大于其它結(jié)點(diǎn)發(fā)過來的提案號(hào)，這個(gè)結(jié)點(diǎn)會(huì)回應(yīng)Yes（本結(jié)點(diǎn)上最新的被批準(zhǔn)提案號(hào)），并保證不接收其它<n的提案。這樣一來，結(jié)點(diǎn)上在Prepare階段里總是會(huì)對(duì)最新的提案做承諾。

優(yōu)化：在上述 prepare 過程中，如果任何一個(gè)結(jié)點(diǎn)發(fā)現(xiàn)存在一個(gè)更高編號(hào)的提案，則需要通知 提案人，提醒其中斷這次提案。

第二階段：Accept階段

如果提案者A收到了超過半數(shù)的結(jié)點(diǎn)返回的Yes，然后他就會(huì)向所有的結(jié)點(diǎn)發(fā)布Accept Request（同樣，需要帶上提案號(hào)n），如果沒有超過半數(shù)的話，那就返回失敗。

當(dāng)結(jié)點(diǎn)們收到了Accept Request后，如果對(duì)于接收的結(jié)點(diǎn)來說，n是最大的了，那么，它就會(huì)通過request（修改這個(gè)值），如果發(fā)現(xiàn)自己有一個(gè)更大的提案號(hào)，那么，結(jié)點(diǎn)就會(huì)拒絕request（拒絕修改）。

我們可以看以，這似乎就是一個(gè)“兩段提交”的優(yōu)化。其實(shí)，2PC/3PC都是分布式一致性算法的殘次版本，Google Chubby的作者M(jìn)ike Burrows說過這個(gè)世界上只有一種一致性算法，那就是Paxos，其它的算法都是殘次品。

我們還可以看到：對(duì)于同一個(gè)值的在不同結(jié)點(diǎn)的修改提案就算是在接收方被亂序收到也是沒有問題的。

四、Raft協(xié)議(解決paxos的實(shí)現(xiàn)難度)

Paxos 相比 Raft 比較復(fù)雜和難以理解。角色扮演和流程比 Raft 都要啰嗦。比如 Agreement 這個(gè)流程，在 Paxos 里邊：Client 發(fā)起請(qǐng)求舉薦 Proposer 成為 Leader，Proposer 然后向全局 Acceptors 尋求確認(rèn)，Acceptors 全部同意 Proposer 后，Proposer 的 Leader 地位得已承認(rèn)，Acceptors 還得再向Learners 進(jìn)行全局廣播來同步。而在 Raft 里邊，只有 Follower/Candidate/Leader 三種角色，角色本身代表狀態(tài)，角色之間進(jìn)行狀態(tài)轉(zhuǎn)移是一件非常自由民主的事情。Raft雖然有角色之分但是是全民參與進(jìn)行選舉的模式；但是在Paxos里邊，感覺更像議員參政模式。

三個(gè)角色

follower、candidate、leader。

最開始大家都是follower，當(dāng)follower監(jiān)聽不到leader，就可以自己成為candidate，發(fā)起投票

leader選舉：timeout限制

選舉的timeout

follower成為candidate的超時(shí)時(shí)間，每個(gè)follower都在150ms and 300ms之間隨機(jī)，之后看誰先timeout，誰就先成為candidate，然后它會(huì)先投自己一票，再向其他節(jié)點(diǎn)發(fā)起投票邀請(qǐng)。

如果其他節(jié)點(diǎn)在這輪選舉還沒有投過票，那么就給candidate投票，然后重置自己的選舉timeout。

如果得到大多數(shù)的投票就成為leader，之后定期開始向follower發(fā)送心跳。

如果兩個(gè)follower同時(shí)成為candidate的話，如果最后得到的票數(shù)相同，則等待其他follower的選擇timeout之后成為candidate，繼續(xù)開始新一輪的選舉。

log復(fù)制

leader把變動(dòng)的log借助心跳同步給follower，過半回復(fù)之后才成功提交，之后再下一次心跳之后，follower也commit變動(dòng)，在自己的node上生效。

分裂之后，另一個(gè)分區(qū)的follower接受不到leader的timeout，然后會(huì)有一個(gè)先timeout，成為candidate，最后成為leader。

于是兩個(gè)分區(qū)就有了兩個(gè)leader。

當(dāng)客戶端有變動(dòng)時(shí)，其中的leader由于無法收到過半的提交，則保持未提交狀態(tài)。有的leader的修改，可以得到過半的提交，則可以修改生效。

當(dāng)分裂恢復(fù)之后，leader開始對(duì)比選舉的term，發(fā)現(xiàn)有更高的term存在時(shí)，他們會(huì)撤銷未提交的修改，然后以最新的為準(zhǔn)。

五、Zab協(xié)議

1、ZAB協(xié)議概述

ZAB：Zookeeper Atomic Broadcast，Zookeeper原子消息廣播協(xié)議，是為Zookeeper所專門設(shè)計(jì)的一種支持崩潰恢復(fù)的原子廣播協(xié)議。ZAB協(xié)議并不像Paxos算法那樣是一種通用的分布式一致性算法，而是專為Zookeeper所設(shè)計(jì)的。

Zookeeper主要依賴ZAB協(xié)議來實(shí)現(xiàn)分布式數(shù)據(jù)的一致性?；谠搮f(xié)議，Zookeeper實(shí)現(xiàn)了一種主備模式的系統(tǒng)架構(gòu)來保持集群中各副本之間的數(shù)據(jù)一致性。

Zookeeper使用一個(gè)單一的主進(jìn)程來接收并處理客戶端的所有事務(wù)請(qǐng)求，并通過ZAB協(xié)議，將服務(wù)器數(shù)據(jù)的狀態(tài)變更以事務(wù)Proposal的形式廣播到所有副本進(jìn)程上去。ZAB協(xié)議的這個(gè)主備架構(gòu)模型保證了同一時(shí)刻集群中只能有一個(gè)主進(jìn)程來廣播服務(wù)器的狀態(tài)變更，因此能夠很好地處理客戶端的并發(fā)請(qǐng)求。

ZAB協(xié)議通過一個(gè)全局遞增的事務(wù)id，來保證狀態(tài)變更的順序性。也就是說，ZAB保證了一個(gè)狀態(tài)變更的請(qǐng)求如果已經(jīng)被處理，那么所有該變更所依賴的狀態(tài)變更都已經(jīng)被處理過了。

考慮到主進(jìn)程在任何時(shí)刻都可能出現(xiàn)宕機(jī)的情況，ZAB協(xié)議還保證了即使主進(jìn)程出現(xiàn)異常，只要集群中有半數(shù)以上節(jié)點(diǎn)存活，就仍然可以正常提供服務(wù)。

2、ZAB協(xié)議的核心

ZAB協(xié)議的核心是，定義了如何處理那些會(huì)改變Zookeeper服務(wù)器數(shù)據(jù)狀態(tài)的事務(wù)請(qǐng)求。即：

所有的事務(wù)請(qǐng)求(會(huì)改變服務(wù)器數(shù)據(jù)狀態(tài)的請(qǐng)求，如修改節(jié)點(diǎn)數(shù)據(jù)、刪除節(jié)點(diǎn)等)必須由一個(gè)全局唯一的服務(wù)器來協(xié)調(diào)處理，該服務(wù)器被稱為Leader，而剩余的其他服務(wù)器被稱為Follower。Leader負(fù)責(zé)將一個(gè)客戶端的事務(wù)請(qǐng)求轉(zhuǎn)換成一個(gè)事務(wù)Proposal(提議)，并將該P(yáng)roposal分發(fā)給集群中的所有Follower。然后Leader等待所有Follower的反饋結(jié)果，一旦有超過半數(shù)的Follower做出了正確的反饋后，Leader就會(huì)向所有的Follower再次發(fā)送Commit消息，要求將前一個(gè)Proposal提交。

3、ZAB協(xié)議詳解

1、ZAB協(xié)議的兩種模式：

崩潰恢復(fù)

當(dāng)Zookeeper集群初始化時(shí)，或Leader故障宕機(jī)時(shí)，ZAB協(xié)議就會(huì)進(jìn)入崩潰恢復(fù)模式，并選舉出新的Leader。當(dāng)新的Leader選舉出來后，并且集群中已經(jīng)有過半的節(jié)點(diǎn)與Leader完成了數(shù)據(jù)同步，ZAB協(xié)議就會(huì)退出崩潰恢復(fù)模式，轉(zhuǎn)而進(jìn)入消息廣播模式。一個(gè)節(jié)點(diǎn)要想成為Leader，必須獲得集群中過半節(jié)點(diǎn)的支持。

消息廣播

ZAB的正常工作模式，如前文所說，Zookeeper設(shè)計(jì)成只允許唯一的一個(gè)Leader節(jié)點(diǎn)負(fù)責(zé)處理客戶端的事務(wù)請(qǐng)求，當(dāng)Leader接收到事務(wù)請(qǐng)求后，會(huì)生成相應(yīng)的事務(wù)Proposal并發(fā)起一輪消息廣播。如果集群中的非Leader節(jié)點(diǎn)(Follower或Observer)接收到了事務(wù)請(qǐng)求，會(huì)將請(qǐng)求轉(zhuǎn)發(fā)給Leader處理。

當(dāng)Leader宕機(jī)，或者是集群中已經(jīng)不存在超過半數(shù)的節(jié)點(diǎn)與Leader保持正常通信，那么集群就會(huì)進(jìn)入崩潰恢復(fù)模式。

2、消息廣播模式

ZAB協(xié)議的消息廣播模式采用的是原子消息廣播，類似于一個(gè)兩階段提交，Leader接收客戶端的事務(wù)請(qǐng)求，為其生成對(duì)應(yīng)的Proposal，并廣播給集群中所有其他的服務(wù)器，然后分別收集每個(gè)服務(wù)器的選票，最后進(jìn)行事務(wù)提交。ZAB消息廣播模式的示意圖如下：

在整個(gè)消息廣播的過程中，Leader會(huì)為每個(gè)事務(wù)請(qǐng)求生成Proposal并進(jìn)行廣播。此外，在廣播Proposal之前，Leader會(huì)首先為這個(gè)Proposal生成全局單調(diào)遞增的唯一ID，稱為事務(wù)ID，也即ZXID。ZAB協(xié)議會(huì)嚴(yán)格按照ZXID的順序處理每個(gè)Proposal，保證了消息的順序性。

在消息廣播過程中，Leader會(huì)在Leader側(cè)為每個(gè)Follower都各自分配一個(gè)單獨(dú)的隊(duì)列，然后將需要廣播的Proposal依次放入這些隊(duì)列中，按照FIFO的原則進(jìn)行發(fā)送。Follower在接收到Proposal后，會(huì)首先將其以事務(wù)日志的形式寫入磁盤中，寫入成功后給Leader響應(yīng)ACK。當(dāng)Leader收到超過半數(shù)的Follower的ACK后，會(huì)廣播一個(gè)Commit消息通知所有Follower進(jìn)行事務(wù)提交，同時(shí)Leader自身也會(huì)提交事務(wù)。Follower在收到Commit消息后，就會(huì)完成對(duì)事務(wù)的提交。

3、崩潰恢復(fù)模式

如前文所述，在正常情況下ZAB處于消息廣播模式運(yùn)行良好。但是在Leader發(fā)生故障宕機(jī)，或者由于網(wǎng)絡(luò)原因?qū)е翷eader與過半的Follower通信失敗，則會(huì)進(jìn)入崩潰恢復(fù)模式。只要集群中有超過半數(shù)的節(jié)點(diǎn)正常運(yùn)行，ZAB協(xié)議就能重新選舉中一個(gè)新的Leader，并且通知集群中的所有機(jī)器新Leader的產(chǎn)生。

4、ZAB協(xié)議的基本特性

ZAB算法設(shè)計(jì)為新被選舉出來的Leader擁有集群中ZXID最大的事務(wù)Proposal，這樣就可以保證新的Leader一定具有所有已經(jīng)提交的Proposal。更為重要的是，如果讓ZXID最大的節(jié)點(diǎn)成為Leader，就可以省去Leader節(jié)點(diǎn)檢查Proposal的提交和丟棄的工作了。

4、深入ZAB算法

ZAB協(xié)議的三個(gè)階段

如前文所述，ZAB協(xié)議有崩潰恢復(fù)和消息廣播兩種模式，而具體可細(xì)分為三個(gè)階段：

階段一 發(fā)現(xiàn)：主要就是Leader選舉過程，用于在多個(gè)分布式進(jìn)程中選舉出主進(jìn)程。

階段二 同步：當(dāng)發(fā)現(xiàn)階段完成后，表明已經(jīng)選舉出了Leader，下面就會(huì)進(jìn)入同步階段，F(xiàn)ollower開始與Leader進(jìn)行數(shù)據(jù)的同步。

階段三 廣播：當(dāng)同步階段完成后，ZAB協(xié)議就進(jìn)入廣播階段，開始正式接收客戶端發(fā)送的事務(wù)請(qǐng)求，并進(jìn)行消息廣播。

在正常運(yùn)行的情況下，ZAB協(xié)議會(huì)一直處于階段三來反復(fù)地進(jìn)行消息廣播流程。如果出現(xiàn)Leader崩潰或者其他原因?qū)е翷eader缺失，ZAB協(xié)議就會(huì)再次進(jìn)入階段一，重新選舉新的Leader。

進(jìn)程的三種狀態(tài)

在ZAB協(xié)議運(yùn)行過程中，每個(gè)進(jìn)程都會(huì)處于下面三種狀態(tài)之一：

Looking：Leader選舉狀態(tài)

Following：Follower進(jìn)程與Leader進(jìn)程保持同步狀態(tài)

Leading：Leader主進(jìn)程處于領(lǐng)導(dǎo)狀態(tài)

當(dāng)ZAB協(xié)議的進(jìn)程剛開始啟動(dòng)時(shí)，所有進(jìn)程都處于Looking的初始化狀態(tài)，此時(shí)集群中并不存在Leader。接下來，所有處于Looking狀態(tài)的進(jìn)程都會(huì)試圖去選舉出一個(gè)Leader。如果某個(gè)進(jìn)程發(fā)現(xiàn)已經(jīng)選舉出了Leader，那么它會(huì)馬上切換到Following，開始和Leader保存同步。此時(shí)，我們將處于Following狀態(tài)的進(jìn)程稱為Follower，處于Leading狀態(tài)的進(jìn)程稱為Leader?？紤]到Leader進(jìn)程隨時(shí)可能掛掉，當(dāng)檢測出Leader已經(jīng)崩潰或放棄領(lǐng)導(dǎo)地位時(shí)，其余的Following狀態(tài)的進(jìn)程就會(huì)重新進(jìn)入Looking狀態(tài)，并開始進(jìn)行新一輪的Leader選舉。因此在ZAB協(xié)議中，每個(gè)進(jìn)程的狀態(tài)都在Looking、Following和Leading之間不斷轉(zhuǎn)換。

在進(jìn)程完成Leader選舉和數(shù)據(jù)同步之后，ZAB協(xié)議就進(jìn)入了廣播階段。在這個(gè)階段中，Leader會(huì)為每一個(gè)與自己保持同步的Follower創(chuàng)建一個(gè)操作隊(duì)列。同一時(shí)刻，一個(gè)Follower只能與一個(gè)Leader保持同步。Leader進(jìn)程與所有的Follower進(jìn)程之間通過心跳檢測機(jī)制來感知彼此的狀態(tài)。如果Leader能在超時(shí)時(shí)間內(nèi)收到Follower的心跳，則Follower就會(huì)一直與Leader保持同步。而一旦在超時(shí)時(shí)間內(nèi)Leader無法收到過半的Follower的心跳信息，或者TCP連接本身斷開了，那么Leader就會(huì)停止對(duì)當(dāng)前周期的領(lǐng)導(dǎo)，并轉(zhuǎn)換到Looking狀態(tài)。同時(shí)，所有Follower也會(huì)放棄這個(gè)Leader，進(jìn)入Looking狀態(tài)。之后，所有進(jìn)程就會(huì)開啟新一輪的Leader選舉。

六、ISR的機(jī)制(解決f容錯(cuò)的2f+1成本問題)

Kafka并沒有使用Zab或Paxos協(xié)議的多數(shù)投票機(jī)制來保證主備數(shù)據(jù)的一致性，而是提出了ISR的機(jī)制（In-Sync Replicas）的機(jī)制來保證數(shù)據(jù)一致性。

ISR認(rèn)為對(duì)于2f+1個(gè)副本來說，多數(shù)投票機(jī)制要求最多只能允許f個(gè)副本發(fā)生故障，如果要支持2個(gè)副本的容錯(cuò)，則需要至少維持5個(gè)副本，對(duì)于消息系統(tǒng)的場景來說，效率太低。

ISR的運(yùn)行機(jī)制如下：將所有次級(jí)副本數(shù)據(jù)分到兩個(gè)集合，其中一個(gè)被稱為ISR集合，這個(gè)集合備份數(shù)據(jù)的特點(diǎn)是即時(shí)和主副本數(shù)據(jù)保持一致，而另外一個(gè)集合的備份數(shù)據(jù)允許其消息隊(duì)列落后于主副本的數(shù)據(jù)。在做主備切換時(shí)，只允許從ISR集合中選擇主副本，只有ISR集合內(nèi)所有備份都寫成功才能認(rèn)為這次寫入操作成功。在具體實(shí)現(xiàn)時(shí)，kafka利用zookeeper來保持每個(gè)ISR集合的信息，當(dāng)ISR集合內(nèi)成員變化時(shí)，相關(guān)構(gòu)件也便于通知。通過這種方式，如果設(shè)定ISR集合大小為f+1，那么可以最多允許f個(gè)副本故障，而對(duì)于多數(shù)投票機(jī)制來說，則需要2f+1個(gè)副本才能達(dá)到相同的容錯(cuò)性。

參考鏈接：https://segmentfault.com/a/1190000004474543