總結(jié)

本文從三個(gè)方面介紹了一致性，首先是描述分布架構(gòu)中的核心理論-CAP揍移，以及其簡(jiǎn)單的證明次和。第二部分介紹了 CAP 里面協(xié)議，重點(diǎn)介紹了 Raft 協(xié)議那伐。第三部分踏施，重點(diǎn)介紹了常用的 zookeeper 原理石蔗。

為了保證數(shù)據(jù) commit 之后不可丟，系統(tǒng)都會(huì)采用（WAL write ahead log）（在每次修改數(shù)據(jù)之前先寫(xiě)操作內(nèi)容日志畅形，然后再去修改數(shù)據(jù)养距。即使修改數(shù)據(jù)時(shí)異常，也可以通過(guò)操作內(nèi)容日志恢復(fù)數(shù)據(jù)）

分布式存儲(chǔ)系統(tǒng)中日熬，是假設(shè)機(jī)器是不穩(wěn)定棍厌，隨時(shí)都有可能 down 掉的情況下來(lái)設(shè)計(jì)的。也就是說(shuō)就算機(jī)器 down 掉了竖席，用戶寫(xiě)入的數(shù)據(jù)也不能丟耘纱，避免單點(diǎn)故障。為此每一份寫(xiě)入的數(shù)據(jù)毕荐，需要在多個(gè)副本中同時(shí)存放束析。例如 zk 節(jié)點(diǎn)數(shù)據(jù)復(fù)制，etcd 的數(shù)據(jù)復(fù)制憎亚。而復(fù)制數(shù)據(jù)給節(jié)點(diǎn)又會(huì)帶來(lái)一致性的問(wèn)題，例如主節(jié)點(diǎn)和從節(jié)點(diǎn)數(shù)據(jù)不一致改如何去同步數(shù)據(jù)第献。也會(huì)帶來(lái)可用性的問(wèn)題载佳，如 leader 節(jié)點(diǎn) down 掉，如何快速選主，恢復(fù)數(shù)據(jù)等彬祖。好在已有成熟的理論如 Paxos 協(xié)議秕磷，ZAB 協(xié)議 Raft 協(xié)議等做為支撐贩汉。

一、一致性

1.1 CAP 理論

C 一致性：分布式環(huán)境中寓落，一致性是指多個(gè)副本之間括丁，在同一時(shí)刻能否有同樣的值

A 可用性：系統(tǒng)提供的服務(wù)必須一直處于可用的狀態(tài)。即使集群中一部分節(jié)點(diǎn)故障伶选。

P 分區(qū)容錯(cuò)性：系統(tǒng)在遇到節(jié)點(diǎn)故障史飞，或者網(wǎng)絡(luò)分區(qū)時(shí)，任然能對(duì)外提供一致性和可用性的服務(wù)仰税。以實(shí)際效果而言构资，分區(qū)相當(dāng)于通信的時(shí)限要求。系統(tǒng)如果不能在一定實(shí)現(xiàn)內(nèi)達(dá)成數(shù)據(jù)一致性陨簇，也就意味著發(fā)生了分區(qū)的情況吐绵。必須就當(dāng)前操作在 C 和 A 之前作出選擇

1.2 CAP不能同時(shí)滿足的證明

假設(shè)系統(tǒng)中有 5 個(gè)節(jié)點(diǎn)，n1~n5河绽。n1己单，n2，n3 在A物理機(jī)房葵姥。n4荷鼠，n5 在 B 物理機(jī)房。現(xiàn)在發(fā)生了網(wǎng)絡(luò)分區(qū)榔幸，A 機(jī)房和 B 機(jī)房網(wǎng)絡(luò)不通允乐。

保證一致性：此時(shí)客戶端在 A 機(jī)房寫(xiě)入數(shù)據(jù)，不能同步到B機(jī)房削咆。寫(xiě)入失敗牍疏。此時(shí)失去了可用性。

保證可用性：數(shù)據(jù)在 A 機(jī)房的 n1~n3 節(jié)點(diǎn)都寫(xiě)入成功后返回成功拨齐。數(shù)據(jù)在 B 機(jī)房的 n4~n5 節(jié)點(diǎn)也寫(xiě)入數(shù)據(jù)鳞陨，返回成功。同一份數(shù)據(jù)在 A 機(jī)房和 B 機(jī)房出現(xiàn)了數(shù)據(jù)不一致的情況。聰明如你厦滤，可以想到 zookeeper援岩，當(dāng)一個(gè)節(jié)點(diǎn) down 掉，系統(tǒng)會(huì)將其剔出節(jié)點(diǎn)掏导，然其它一半以上的節(jié)點(diǎn)寫(xiě)入成功即可享怀。是不是 zookeeper 同時(shí)滿足了 CAP 呢。其實(shí)這里有一個(gè)誤區(qū)趟咆，系統(tǒng)將其剔出節(jié)點(diǎn)添瓷。有一個(gè)隱含的條件是，系統(tǒng)引入了一個(gè)調(diào)度者值纱，一個(gè)踢出壞節(jié)點(diǎn)的調(diào)度者鳞贷。當(dāng)調(diào)度者和 zookeeper 節(jié)點(diǎn)出現(xiàn)網(wǎng)絡(luò)分區(qū)，整個(gè)系統(tǒng)還是不可用的虐唠。

1.3 常見(jiàn)場(chǎng)景

CA without P： 在分布式環(huán)境中搀愧，P 是不可避免的，天災(zāi)（某軟公司的Azure被雷劈劈中）人禍（某里公司 A 和 B 機(jī)房之間的光纜被挖斷）都能導(dǎo)致P凿滤。

CP without A：相當(dāng)于每個(gè)寫(xiě)請(qǐng)求都須在Server之前強(qiáng)一致妈橄。P (分區(qū))會(huì)導(dǎo)致同步時(shí)間無(wú)限延長(zhǎng)。這個(gè)是可以保證的翁脆。例如數(shù)據(jù)庫(kù)的分布式事務(wù)眷蚓，兩階段提交，三階段提交等反番。

AP without C： 當(dāng)網(wǎng)絡(luò)分區(qū)發(fā)生沙热，A 和 B 集群失去聯(lián)系。為了保證高可用罢缸，系統(tǒng)在寫(xiě)入時(shí)篙贸，系統(tǒng)寫(xiě)入部分節(jié)點(diǎn)就會(huì)返回成功，這會(huì)導(dǎo)致在一定時(shí)間之內(nèi)枫疆，客戶端從不同的機(jī)器上面讀取到的是數(shù)據(jù)是不一樣的爵川。例如 redis 主從異步復(fù)制架構(gòu)，當(dāng) master down 掉息楔，系統(tǒng)會(huì)切換到 slave寝贡，由于是異步復(fù)制，salve 不是最新的數(shù)據(jù)值依，會(huì)導(dǎo)致一致性的問(wèn)題圃泡。

二、一致性協(xié)議

2.1 兩階段提交協(xié)議（2PC）

二階段提交( Two-phaseCommit )是指愿险，在計(jì)算機(jī)網(wǎng)絡(luò)以及數(shù)據(jù)庫(kù)領(lǐng)域內(nèi)颇蜡，為了使基于分布式系統(tǒng)架構(gòu)下的所有節(jié)點(diǎn)在進(jìn)行事務(wù)提交時(shí)保持一致性而設(shè)計(jì)的一種算法( Algorithm )。通常，二階段提交也被稱為是一種協(xié)議( Protocol )风秤。在分布式系統(tǒng)中鳖目，每個(gè)節(jié)點(diǎn)雖然可以知曉自己的操作時(shí)成功或者失敗，卻無(wú)法知道其他節(jié)點(diǎn)的操作的成功或失敗唁情。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí)疑苔，為了保持事務(wù)的 ACID 特性，需要引入一個(gè)作為協(xié)調(diào)者的組件來(lái)統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫(xiě)入磁盤(pán)等等)甸鸟。因此，二階段提交的算法思路可以概括為：參與者將操作成敗通知協(xié)調(diào)者兵迅，再由協(xié)調(diào)者根據(jù)所有參與者的反饋情報(bào)決定各參與者是否要提交操作還是中止操作抢韭。

2.1.1 兩種角色

協(xié)調(diào)者

參與者

2.1.2 處理階段

詢問(wèn)投票階段：事務(wù)協(xié)調(diào)者給每個(gè)參與者發(fā)送 Prepare 消息，參與者受到消息后恍箭，刻恭，要么在本地寫(xiě)入 redo 和 undo 日志成功后，返回同意的消息扯夭，否者一個(gè)終止事務(wù)的消息鳍贾。

執(zhí)行初始化（執(zhí)行提交）：協(xié)調(diào)者在收到所有參與者的消息后，如果有一個(gè)返回終止事務(wù)交洗，那么協(xié)調(diào)者給每個(gè)參與者發(fā)送回滾的指令骑科。否者發(fā)送 commit 消息

2.1.3 異常情況處理

協(xié)調(diào)者故障：備用協(xié)調(diào)者接管纸镊，并查詢參與者執(zhí)行到什么地址

參與者故障：協(xié)調(diào)者會(huì)等待他重啟然后執(zhí)行

協(xié)調(diào)者和參與者同時(shí)故障：協(xié)調(diào)者故障亏吝，然后參與者也故障。例如：有機(jī)器 1腮介，2置森，3斗埂，4。其中 4 是協(xié)調(diào)者凫海，1呛凶，2，3是參與者 4 給1行贪，2 發(fā)完提交事務(wù)后故障了漾稀，正好3這個(gè)時(shí)候也故障了，注意這是 3 是沒(méi)有提交事務(wù)數(shù)據(jù)的瓮顽。在備用協(xié)調(diào)者啟動(dòng)了县好，去詢問(wèn)參與者，由于3死掉了暖混，一直不知道它處于什么狀態(tài)（接受了提交事務(wù)缕贡，還是反饋了能執(zhí)行還是不能執(zhí)行 3 個(gè)狀態(tài)）。面對(duì)這種情況，2PC晾咪，是不能解決的收擦，要解決需要下文介紹的 3PC。

2.1.4 缺點(diǎn)

同步阻塞問(wèn)題：由于所有參與的節(jié)點(diǎn)都是事務(wù)阻塞型的谍倦，例如update tablesetstatus=1wherecurrent_day=20181103塞赂，那么參與者table表的current_day=20181103的記錄都會(huì)被鎖住，其他的要修改current_day=20181103行的事務(wù)昼蛀，都會(huì)被阻塞

單點(diǎn)故障阻塞其他事務(wù)：協(xié)調(diào)者再執(zhí)行提交的階段 down 掉宴猾，所有的參與者出于鎖定事務(wù)資源的狀態(tài)中。無(wú)法完成相關(guān)的事務(wù)操作叼旋。

參與者和協(xié)調(diào)者同時(shí) down 掉：協(xié)調(diào)者在發(fā)送完 commit 消息后 down 掉仇哆，而唯一接受到此消息的參與者也 down 掉了。新協(xié)調(diào)者接管夫植，也是一個(gè)懵逼的狀態(tài)讹剔，不知道此條事務(wù)的狀態(tài)。無(wú)論提交或者回滾都是不合適的详民。這個(gè)是兩階段提交無(wú)法改變的

2.2 三階段提交協(xié)議（3PC）

2PC 當(dāng)時(shí)只考慮如果單機(jī)故障的情況延欠，是可以勉強(qiáng)應(yīng)付的。當(dāng)遇到協(xié)調(diào)者和參與者同時(shí)故障的話沈跨，2PC 的理論是不完善的由捎。此時(shí) 3PC 登場(chǎng)。

3PC 就是對(duì) 2PC 漏洞的補(bǔ)充協(xié)議谒出。主要改動(dòng)兩點(diǎn)：

在 2PC 的第一階段和第二階段插入一個(gè)準(zhǔn)備階段隅俘，做到就算參與者和協(xié)調(diào)者同時(shí)故障也不阻塞，并且保證一致性笤喳。

在協(xié)調(diào)者和參與者之間引入超時(shí)機(jī)制

2.2.1 處理的三個(gè)階段

事務(wù)詢問(wèn)階段（ can commit 階段)：協(xié)調(diào)者向參與者發(fā)送 commit 請(qǐng)求为居，然后等待參與者反應(yīng)。這個(gè)和 2PC 階段不同的是杀狡，此時(shí)參與者沒(méi)有鎖定資源蒙畴，沒(méi)有寫(xiě) redo，undo呜象，執(zhí)行回滾日志膳凝。回滾代價(jià)低

事務(wù)準(zhǔn)備階段 （pre commit）：如果參與者都返回ok，那么就發(fā)送Prepare消息恭陡，參與者本地執(zhí)行redo和undo日志蹬音。否者就向參與者提交終止（abort）事務(wù)的請(qǐng)求。如果再發(fā)送Prepare消息的時(shí)候休玩，等待超時(shí)著淆，也會(huì)向參與者提交終止事務(wù)的請(qǐng)求劫狠。

執(zhí)行事務(wù)階段（do commit）：如果所有發(fā)送Prepare都返回成功，那么此時(shí)變?yōu)閳?zhí)行事務(wù)階段永部，向參與者發(fā)送commit事務(wù)的消息独泞。否者回滾事務(wù)。在此階段參與者如果在一定時(shí)間內(nèi)沒(méi)有收到docommit消息苔埋，觸發(fā)超時(shí)機(jī)制懦砂，會(huì)自己提交事務(wù)。此番處理的邏輯是组橄，能夠進(jìn)入此階段荞膘，說(shuō)明在事務(wù)詢問(wèn)階段所有節(jié)點(diǎn)都是好的。即使在提交的時(shí)候部分失敗晨炕，有理由相信衫画，此時(shí)大部分節(jié)點(diǎn)都是好的。是可以提交的

2.2.2 缺點(diǎn)

不能解決網(wǎng)絡(luò)分區(qū)的導(dǎo)致的數(shù)據(jù)不一致的問(wèn)題：例如 1~5 五個(gè)參與者節(jié)點(diǎn)瓮栗，1，2瞄勾，3 個(gè)節(jié)點(diǎn)在A機(jī)房费奸，4，5 節(jié)點(diǎn)在 B 機(jī)房进陡。在pre commit階段愿阐，1~5 個(gè)節(jié)點(diǎn)都收到 Prepare 消息，但是節(jié)點(diǎn)1執(zhí)行失敗趾疚。協(xié)調(diào)者向1~5個(gè)節(jié)點(diǎn)發(fā)送回滾事務(wù)的消息缨历。但是此時(shí)A，B機(jī)房的網(wǎng)絡(luò)分區(qū)糙麦。1~3 號(hào)節(jié)點(diǎn)會(huì)回滾辛孵。但是 4~5 節(jié)點(diǎn)由于沒(méi)收到回滾事務(wù)的消息，而提交了事務(wù)赡磅。待網(wǎng)絡(luò)分區(qū)恢復(fù)后魄缚，會(huì)出現(xiàn)數(shù)據(jù)不一致的情況。

不能解決 fail-recover 的問(wèn)題：

由于 3PC 有超時(shí)機(jī)制的存在焚廊，2PC 中未解決的問(wèn)題冶匹，參與者和協(xié)調(diào)者同時(shí) down 掉，也就解決了咆瘟。一旦參與者在超時(shí)時(shí)間內(nèi)沒(méi)有收到協(xié)調(diào)者的消息嚼隘，就會(huì)自己提交。這樣也能避免參與者一直占用共享資源袒餐。但是其在網(wǎng)絡(luò)分區(qū)的情況下飞蛹，不能保證數(shù)據(jù)的一致性谤狡。

2.3 Paxos協(xié)議

像 2PC 和 3PC 都需要引入一個(gè)協(xié)調(diào)者的角色，當(dāng)協(xié)調(diào)者 down 掉之后桩皿，整個(gè)事務(wù)都無(wú)法提交豌汇，參與者的資源都出于鎖定的狀態(tài)，對(duì)于系統(tǒng)的影響是災(zāi)難性的泄隔，而且出現(xiàn)網(wǎng)絡(luò)分區(qū)的情況拒贱，很有可能會(huì)出現(xiàn)數(shù)據(jù)不一致的情況。有沒(méi)有不需要協(xié)調(diào)者角色佛嬉，每個(gè)參與者來(lái)協(xié)調(diào)事務(wù)呢逻澳，在網(wǎng)絡(luò)分區(qū)的情況下，又能最大程度保證一致性的解決方案呢暖呕。此時(shí) Paxos 出現(xiàn)了斜做。

Paxos 算法是 Lamport 于 1990 年提出的一種基于消息傳遞的一致性算法。由于算法難以理解起初并沒(méi)有引起人們的重視湾揽，Lamport在八年后重新發(fā)表瓤逼，即便如此Paxos算法還是沒(méi)有得到重視。2006 年 Google 的三篇論文石破天驚库物，其中的 chubby 鎖服務(wù)使用Paxos 作為 chubbycell 中的一致性霸旗，后來(lái)才得到關(guān)注。

2.3.1 解決了什么問(wèn)題

Paxos 協(xié)議是一個(gè)解決分布式系統(tǒng)中戚揭，多個(gè)節(jié)點(diǎn)之間就某個(gè)值（提案）達(dá)成一致（決議）的通信協(xié)議诱告。它能夠處理在少數(shù)節(jié)點(diǎn)離線的情況下，剩余的多數(shù)節(jié)點(diǎn)仍然能夠達(dá)成一致民晒。即每個(gè)節(jié)點(diǎn)精居，既是參與者，也是決策者

2.3.2 兩種角色（兩者可以是同一臺(tái)機(jī)器）

Proposer：提議提案的服務(wù)器

Acceptor：批準(zhǔn)提案的服務(wù)器

由于 Paxos 和下文提到的 zookeeper 使用的 ZAB 協(xié)議過(guò)于相似潜必，詳細(xì)講解參照下文靴姿，?Zookeeper原理部分。

2.4 Raft協(xié)議

Paxos 是論證了一致性協(xié)議的可行性刮便，但是論證的過(guò)程據(jù)說(shuō)晦澀難懂空猜，缺少必要的實(shí)現(xiàn)細(xì)節(jié)，而且工程實(shí)現(xiàn)難度比較高廣為人知實(shí)現(xiàn)只有 zk 的實(shí)現(xiàn) zab 協(xié)議恨旱。然后斯坦福大學(xué) RamCloud 項(xiàng)目中提出了易實(shí)現(xiàn)辈毯，易理解的分布式一致性復(fù)制協(xié)議 Raft。Java搜贤，C++谆沃，Go 等都有其對(duì)應(yīng)的實(shí)現(xiàn)。

2.4.1 基本名詞

節(jié)點(diǎn)狀態(tài)

Leader（主節(jié)點(diǎn)）：接受 client 更新請(qǐng)求仪芒，寫(xiě)入本地后唁影，然后同步到其他副本中

Follower（從節(jié)點(diǎn)）：從 Leader 中接受更新請(qǐng)求耕陷，然后寫(xiě)入本地日志文件。對(duì)客戶端提供讀請(qǐng)求

Candidate（候選節(jié)點(diǎn)）：如果 follower 在一段時(shí)間內(nèi)未收到 leader 心跳据沈。則判斷 leader 可能故障哟沫，發(fā)起選主提議。節(jié)點(diǎn)狀態(tài)從 Follower 變?yōu)?Candidate 狀態(tài)锌介，直到選主結(jié)束

termId：任期號(hào)嗜诀，時(shí)間被劃分成一個(gè)個(gè)任期，每次選舉后都會(huì)產(chǎn)生一個(gè)新的 termId孔祸，一個(gè)任期內(nèi)只有一個(gè) leader隆敢。termId 相當(dāng)于 paxos 的 proposalId。

RequestVote：請(qǐng)求投票崔慧，candidate 在選舉過(guò)程中發(fā)起拂蝎，收到 quorum (多數(shù)派）響應(yīng)后，成為 leader惶室。

AppendEntries：附加日志温自，leader 發(fā)送日志和心跳的機(jī)制

election timeout：選舉超時(shí)，如果 follower 在一段時(shí)間內(nèi)沒(méi)有收到任何消息(追加日志或者心跳)皇钞，就是選舉超時(shí)捣作。

2.4.2 特性

Leader 不會(huì)修改自身日志，只會(huì)做追加操作鹅士，日志只能由Leader轉(zhuǎn)向Follower。例如即將要down掉的Leader節(jié)點(diǎn)已經(jīng)提交日志1惩坑，未提交日志 2掉盅，3。down 掉之后以舒，節(jié)點(diǎn) 2 啟動(dòng)最新日志只有 1趾痘，然后提交了日志 4。好巧不巧節(jié)點(diǎn) 1 又啟動(dòng)了蔓钟。此時(shí)節(jié)點(diǎn) 2 的編號(hào) 4 日志會(huì)追加到節(jié)點(diǎn) 1 的編號(hào) 1 日志的后面永票。節(jié)點(diǎn) 1 編號(hào) 2，3 的日志會(huì)丟掉滥沫。

不依賴各個(gè)節(jié)點(diǎn)物理時(shí)序保證一致性侣集，通過(guò)邏輯遞增的 term-id 和 log-id 保證。

2.4.3 選主契機(jī)

在超時(shí)時(shí)間內(nèi)沒(méi)有收到 Leader 的心跳

啟動(dòng)時(shí)

2.4.4 選主過(guò)程

如圖?raft-2所示兰绣，Raft將時(shí)間分為多個(gè) term（任期）世分，term 以連續(xù)的整數(shù)來(lái)標(biāo)識(shí)，每個(gè) term 表示一個(gè)選舉的開(kāi)始缀辩。例如 Follower 節(jié)點(diǎn) 1臭埋，在 term1 和 term2 連接處的時(shí)間踪央，聯(lián)系不到 Leader，將 currentTerm 編號(hào)加1瓢阴，變成2畅蹂，進(jìn)入了到term2任期，在 term2 的藍(lán)色部分選舉完成荣恐，綠色部分正常工作液斜。

當(dāng)然一個(gè)任期不一定能選出 Leader，那么會(huì)將 currentTerm 繼續(xù)加1募胃，然后繼續(xù)進(jìn)行選舉旗唁，例如圖中的 t3。選舉的原則是痹束，每一輪選舉每個(gè)選民一張選票检疫，投票的請(qǐng)求先到且選民發(fā)現(xiàn)候選人節(jié)點(diǎn)的日志 id 大于等于自己的，就會(huì)投票祷嘶，否者不會(huì)投票屎媳。獲得半數(shù)以上的票的節(jié)點(diǎn)成為主節(jié)點(diǎn)，注意這并不是說(shuō)選出來(lái)的事務(wù) id 一定是最大的论巍，例如下圖?raft-1a~f六個(gè)節(jié)點(diǎn)（正方形框里面的數(shù)字是選舉的輪數(shù) term）烛谊。

在第四輪選舉中，a 先發(fā)出投票嘉汰，六臺(tái)機(jī)器中丹禀，a~e 都會(huì)投 a，即使 f 不投 a鞋怀，a 也會(huì)贏得選舉双泪。如果沒(méi)有事務(wù)id（如剛啟動(dòng)時(shí)），就遵循投票請(qǐng)求先來(lái)先頭密似。然后 Leader 將最新的日志復(fù)制到各個(gè)節(jié)點(diǎn)焙矛，再對(duì)外提供服務(wù)。

當(dāng)然除了這些選舉限制残腌，還會(huì)有其他的情況村斟。如 commit 限制等保證，Leader 選舉成功一定包含所有的 commit 和 log抛猫。

2.4.5 日志復(fù)制過(guò)程

raft 日志寫(xiě)入過(guò)程蟆盹，主節(jié)點(diǎn)收到一個(gè)?x=1的請(qǐng)求后，會(huì)寫(xiě)入本地日志邑滨，然后將?x=1的日志廣播出去日缨，follower 如果收到請(qǐng)求，會(huì)將日志寫(xiě)入本地 log 掖看，然后返回成功匣距。當(dāng) leader 收到半數(shù)以上的節(jié)點(diǎn)回應(yīng)時(shí)面哥，會(huì)將此日志的狀態(tài)變?yōu)?commit，然后廣播消息讓 follwer 提交日志毅待。節(jié)點(diǎn)在 commit 日志后尚卫，會(huì)更新?tīng)顟B(tài)機(jī)中的 logindex 。

firstLogIndex/lastLogIndex 為節(jié)點(diǎn)中開(kāi)始和結(jié)束的索引位置（包含提交尸红，未提交吱涉，寫(xiě)入狀態(tài)機(jī)）commitIndex：已提交的索引。applyIndex：已寫(xiě)入狀態(tài)機(jī)中的索引外里。

日志復(fù)制的本質(zhì)是讓 follwer 和 Leader 的已提交的日志順序和內(nèi)容都完全一樣怎爵，用于保證一致性。

具體的原則就是：

?原則1：兩個(gè)日志在不同的 raft 節(jié)點(diǎn)中盅蝗，如果有兩個(gè)相同的 term 和 logIndex 鳖链，則保證兩個(gè)日志的內(nèi)容完全一樣。

原則2：兩段日志在不同的 raft 節(jié)點(diǎn)中墩莫，如果起始和終止的的 term芙委，logIndex 都相同，那么兩段日志中日志內(nèi)容完全一樣狂秦。

如何保證

第一個(gè)原則只需要在創(chuàng)建 logIndex 的時(shí)候使用新的 logIndex灌侣，保證 logIndex 的唯一性。而且創(chuàng)建之后不去更改裂问。那么在 leader 復(fù)制到 follwer 之后侧啼，logIndex，term 和日志內(nèi)容都沒(méi)變堪簿。

第二個(gè)原則慨菱，在 Leader 復(fù)制給 Follower 時(shí)，要傳遞當(dāng)前最新日志 currenTermId 和currentLogIndex戴甩，以及上一條日志 preCurrentTermId 和 preCurrentLogIndex。如圖?raft-1闪彼，在 d 節(jié)點(diǎn)甜孤，term7，logIndex12畏腕。在給節(jié)點(diǎn)節(jié)點(diǎn) a 同步時(shí)缴川，發(fā)送(term7，logIndex11)描馅，(term7把夸，logIndex12),a 節(jié)點(diǎn)沒(méi)有找到(term7铭污，logIndex11)的日志恋日，會(huì)讓Leader岂膳，d 節(jié)點(diǎn)重新發(fā)送誓竿。d 節(jié)點(diǎn)會(huì)重新發(fā)（term6，logIndex10）(term7谈截，logIndex11)筷屡，還是沒(méi)有(term6，logIndex10)的日志,依然會(huì)拒絕同步簸喂。接著發(fā)(term6毙死，logIndex9)(term6，logIndex10)∮黯現(xiàn)在a節(jié)點(diǎn)有了(term6扼倘，logIndex9)。那么? leader 節(jié)點(diǎn)就會(huì)將(term6诽表，logIndex9) ~ (term7唉锌，logIndex11)日志內(nèi)容給節(jié)點(diǎn) a，節(jié)點(diǎn) a 將會(huì)和節(jié)點(diǎn) d 有一樣的日志竿奏。

三袄简、Zookeeper 原理

3.1 概述

Google 的粗粒度鎖服務(wù) Chubby 的設(shè)計(jì)開(kāi)發(fā)者 Burrows 曾經(jīng)說(shuō)過(guò)：“所有一致性協(xié)議本質(zhì)上要么是 Paxos 要么是其變體”。Paxos 雖然解決了分布式系統(tǒng)中泛啸，多個(gè)節(jié)點(diǎn)就某個(gè)值達(dá)成一致性的通信協(xié)議绿语。但是還是引入了其他的問(wèn)題。由于其每個(gè)節(jié)點(diǎn)候址，都可以提議提案吕粹，也可以批準(zhǔn)提案。當(dāng)有三個(gè)及以上的 proposer 在發(fā)送 prepare 請(qǐng)求后岗仑，很難有一個(gè) proposer 收到半數(shù)以上的回復(fù)而不斷地執(zhí)行第一階段的協(xié)議匹耕，在這種競(jìng)爭(zhēng)下，會(huì)導(dǎo)致選舉速度變慢荠雕。

所以 zookeeper 在 paxos 的基礎(chǔ)上稳其，提出了 ZAB 協(xié)議，本質(zhì)上是炸卑，只有一臺(tái)機(jī)器能提議提案（Proposer）既鞠，而這臺(tái)機(jī)器的名稱稱之為 Leader 角色。其他參與者扮演 Acceptor 角色。為了保證 Leader 的健壯性，引入了 Leader 選舉機(jī)制汤善。

ZAB協(xié)議還解決了這些問(wèn)題

在半數(shù)以下節(jié)點(diǎn)宕機(jī)睹限，依然能對(duì)臺(tái)提供服務(wù)

客戶端所有的寫(xiě)請(qǐng)求坠宴，交由 Leader 來(lái)處理魄鸦。寫(xiě)入成功后拿愧，需要同步給所有的 follower 和 observer

leader 宕機(jī)夫嗓，或者集群重啟桐玻。需要確保已經(jīng)再 Leader 提交的事務(wù)最終都能被服務(wù)器提交篙挽，并且確保集群能快速回復(fù)到故障前的狀態(tài)

3.2 基本概念

基本名詞

數(shù)據(jù)節(jié)點(diǎn)（dataNode）：zk 數(shù)據(jù)模型中的最小數(shù)據(jù)單元，數(shù)據(jù)模型是一棵樹(shù)镊靴，由斜杠（ / ）分割的路徑名唯一標(biāo)識(shí)铣卡，數(shù)據(jù)節(jié)點(diǎn)可以存儲(chǔ)數(shù)據(jù)內(nèi)容及一系列屬性信息，同時(shí)還可以掛載子節(jié)點(diǎn)偏竟，構(gòu)成一個(gè)層次化的命名空間煮落。

事務(wù)及 zxid：事務(wù)是指能夠改變 Zookeeper 服務(wù)器狀態(tài)的操作，一般包括數(shù)據(jù)節(jié)點(diǎn)的創(chuàng)建與刪除踊谋、數(shù)據(jù)節(jié)點(diǎn)內(nèi)容更新和客戶端會(huì)話創(chuàng)建與失效等操作蝉仇。對(duì)于每個(gè)事務(wù)請(qǐng)求，zk 都會(huì)為其分配一個(gè)全局唯一的事務(wù) ID殖蚕，即 zxid轿衔，是一個(gè) 64 位的數(shù)字，高 32 位表示該事務(wù)發(fā)生的集群選舉周期（集群每發(fā)生一次 leader 選舉睦疫，值加 1）害驹，低 32 位表示該事務(wù)在當(dāng)前選擇周期內(nèi)的遞增次序（leader 每處理一個(gè)事務(wù)請(qǐng)求，值加 1蛤育，發(fā)生一次 leader 選擇宛官，低 32 位要清 0）。

事務(wù)日志：所有事務(wù)操作都是需要記錄到日志文件中的瓦糕，可通過(guò) dataLogDir 配置文件目錄底洗，文件是以寫(xiě)入的第一條事務(wù) zxid 為后綴，方便后續(xù)的定位查找咕娄。zk 會(huì)采取“磁盤(pán)空間預(yù)分配”的策略亥揖，來(lái)避免磁盤(pán) Seek 頻率，提升 zk 服務(wù)器對(duì)事務(wù)請(qǐng)求的影響能力圣勒。默認(rèn)設(shè)置下徐块，每次事務(wù)日志寫(xiě)入操作都會(huì)實(shí)時(shí)刷入磁盤(pán)，也可以設(shè)置成非實(shí)時(shí)（寫(xiě)到內(nèi)存文件流灾而，定時(shí)批量寫(xiě)入磁盤(pán)），但那樣斷電時(shí)會(huì)帶來(lái)丟失數(shù)據(jù)的風(fēng)險(xiǎn)扳剿。

事務(wù)快照：數(shù)據(jù)快照是 zk 數(shù)據(jù)存儲(chǔ)中另一個(gè)非常核心的運(yùn)行機(jī)制旁趟。數(shù)據(jù)快照用來(lái)記錄 zk 服務(wù)器上某一時(shí)刻的全量?jī)?nèi)存數(shù)據(jù)內(nèi)容，并將其寫(xiě)入到指定的磁盤(pán)文件中，可通過(guò) dataDir 配置文件目錄锡搜〕壤В可配置參數(shù) snapCount，設(shè)置兩次快照之間的事務(wù)操作個(gè)數(shù)耕餐，zk 節(jié)點(diǎn)記錄完事務(wù)日志時(shí)凡傅，會(huì)統(tǒng)計(jì)判斷是否需要做數(shù)據(jù)快照（距離上次快照，事務(wù)操作次數(shù)等于snapCount/2~snapCount 中的某個(gè)值時(shí)肠缔，會(huì)觸發(fā)快照生成操作夏跷，隨機(jī)值是為了避免所有節(jié)點(diǎn)同時(shí)生成快照，導(dǎo)致集群影響緩慢）明未。

核心角色

leader：系統(tǒng)剛啟動(dòng)時(shí)或者 Leader 崩潰后正處于選舉狀態(tài)槽华；

follower：Follower 節(jié)點(diǎn)所處的狀態(tài)，F(xiàn)ollower 與 Leader 處于數(shù)據(jù)同步階段趟妥；

observer：Leader 所處狀態(tài)猫态，當(dāng)前集群中有一個(gè) Leader 為主進(jìn)程。

節(jié)點(diǎn)狀態(tài)

LOOKING：節(jié)點(diǎn)正處于選主狀態(tài)披摄，不對(duì)外提供服務(wù)亲雪，直至選主結(jié)束；

FOLLOWING：作為系統(tǒng)的從節(jié)點(diǎn)疚膊，接受主節(jié)點(diǎn)的更新并寫(xiě)入本地日志义辕；

LEADING：作為系統(tǒng)主節(jié)點(diǎn)，接受客戶端更新酿联，寫(xiě)入本地日志并復(fù)制到從節(jié)點(diǎn)

3.3 常見(jiàn)的誤區(qū)

寫(xiě)入節(jié)點(diǎn)后的數(shù)據(jù)终息，立馬就能被讀到，這是錯(cuò)誤的贞让。* zk 寫(xiě)入是必須通過(guò) leader 串行的寫(xiě)入周崭，而且只要一半以上的節(jié)點(diǎn)寫(xiě)入成功即可。而任何節(jié)點(diǎn)都可提供讀取服務(wù)喳张。例如：zk续镇，有 1~5 個(gè)節(jié)點(diǎn)，寫(xiě)入了一個(gè)最新的數(shù)據(jù)销部，最新數(shù)據(jù)寫(xiě)入到節(jié)點(diǎn) 1~3摸航，會(huì)返回成功。然后讀取請(qǐng)求過(guò)來(lái)要讀取最新的節(jié)點(diǎn)數(shù)據(jù)舅桩，請(qǐng)求可能被分配到節(jié)點(diǎn) 4~5 酱虎。而此時(shí)最新數(shù)據(jù)還沒(méi)有同步到節(jié)點(diǎn)4~5。會(huì)讀取不到最近的數(shù)據(jù)擂涛。如果想要讀取到最新的數(shù)據(jù)读串，可以在讀取前使用 sync 命令*。

zk啟動(dòng)節(jié)點(diǎn)不能偶數(shù)臺(tái)，這也是錯(cuò)誤的恢暖。zk 是需要一半以上節(jié)點(diǎn)才能正常工作的排监。例如創(chuàng)建 4 個(gè)節(jié)點(diǎn)，半數(shù)以上正常節(jié)點(diǎn)數(shù)是 3杰捂。也就是最多只允許一臺(tái)機(jī)器 down 掉舆床。而 3 臺(tái)節(jié)點(diǎn)，半數(shù)以上正常節(jié)點(diǎn)數(shù)是 2嫁佳，也是最多允許一臺(tái)機(jī)器 down 掉挨队。4 個(gè)節(jié)點(diǎn)，多了一臺(tái)機(jī)器的成本脱拼，但是健壯性和 3 個(gè)節(jié)點(diǎn)的集群一樣瞒瘸。基于成本的考慮是不推薦的

3.4 選舉同步過(guò)程

3.4.1 發(fā)起投票的契機(jī)

節(jié)點(diǎn)啟動(dòng)

節(jié)點(diǎn)運(yùn)行期間無(wú)法與 Leader 保持連接熄浓，

Leader 失去一半以上節(jié)點(diǎn)的連接

3.4.2 如何保證事務(wù)

ZAB 協(xié)議類似于兩階段提交情臭，客戶端有一個(gè)寫(xiě)請(qǐng)求過(guò)來(lái)，例如設(shè)置?/my/test?值為 1赌蔑，Leader 會(huì)生成對(duì)應(yīng)的事務(wù)提議（proposal）（當(dāng)前 zxid為 0x5000010 提議的 zxid 為Ox5000011）俯在，現(xiàn)將?set/my/test1（此處為偽代碼）寫(xiě)入本地事務(wù)日志，然后?set/my/test1日志同步到所有的follower娃惯。follower收到事務(wù) proposal 跷乐，將 proposal 寫(xiě)入到事務(wù)日志。如果收到半數(shù)以上 follower 的回應(yīng)趾浅，那么廣播發(fā)起 commit 請(qǐng)求愕提。follower 收到 commit 請(qǐng)求后。會(huì)將文件中的 zxid ox5000011 應(yīng)用到內(nèi)存中皿哨。

上面說(shuō)的是正常的情況浅侨。有兩種情況。第一種 Leader 寫(xiě)入本地事務(wù)日志后证膨，沒(méi)有發(fā)送同步請(qǐng)求如输，就 down 了。即使選主之后又作為 follower 啟動(dòng)央勒。此時(shí)這種還是會(huì)日志會(huì)丟掉（原因是選出的 leader 無(wú)此日志不见，無(wú)法進(jìn)行同步）。第二種 Leader 發(fā)出同步請(qǐng)求崔步，但是還沒(méi)有 commit 就 down 了稳吮。此時(shí)這個(gè)日志不會(huì)丟掉，會(huì)同步提交到其他節(jié)點(diǎn)中井濒。

3.4.3 服務(wù)器啟動(dòng)過(guò)程中的投票過(guò)程

現(xiàn)在 5 臺(tái) zk 機(jī)器依次編號(hào) 1~5

節(jié)點(diǎn) 1 啟動(dòng)灶似，發(fā)出去的請(qǐng)求沒(méi)有響應(yīng)慎陵，此時(shí)是 Looking 的狀態(tài)

節(jié)點(diǎn) 2 啟動(dòng)，與節(jié)點(diǎn) 1 進(jìn)行通信喻奥，交換選舉結(jié)果。由于兩者沒(méi)有歷史數(shù)據(jù)捏悬，即 zxid 無(wú)法比較撞蚕，此時(shí) id 值較大的節(jié)點(diǎn) 2 勝出，但是由于還沒(méi)有超過(guò)半數(shù)的節(jié)點(diǎn)过牙，所以 1 和 2 都保持 looking 的狀態(tài)

節(jié)點(diǎn) 3 啟動(dòng)甥厦，根據(jù)上面的分析，id 值最大的節(jié)點(diǎn) 3 勝出寇钉，而且超過(guò)半數(shù)的節(jié)點(diǎn)都參與了選舉刀疙。節(jié)點(diǎn) 3 勝出成為了 Leader

節(jié)點(diǎn) 4 啟動(dòng)，和 1~3 個(gè)節(jié)點(diǎn)通信扫倡，得知最新的 leader 為節(jié)點(diǎn) 3谦秧，而此時(shí) zxid 也小于節(jié)點(diǎn) 3，所以承認(rèn)了節(jié)點(diǎn) 3 的 leader 的角色

節(jié)點(diǎn) 5 啟動(dòng)撵溃，和節(jié)點(diǎn) 4 一樣疚鲤，選取承認(rèn)節(jié)點(diǎn) 3 的 leader 的角色

3.4.4 服務(wù)器運(yùn)行過(guò)程中選主過(guò)程

1. 節(jié)點(diǎn) 1 發(fā)起投票，第一輪投票先投自己缘挑，然后進(jìn)入 Looking 等待的狀態(tài)集歇。

2. 其他的節(jié)點(diǎn)（如節(jié)點(diǎn) 2 ）收到對(duì)方的投票信息。節(jié)點(diǎn) 2 在 Looking 狀態(tài)语淘，則將自己的投票結(jié)果廣播出去（此時(shí)走的是上圖中左側(cè)的 Looking 分支）诲宇；如果不在 Looking 狀態(tài)，則直接告訴節(jié)點(diǎn) 1 當(dāng)前的 Leader 是誰(shuí)惶翻，就不要瞎折騰選舉了（此時(shí)走的是上圖右側(cè)的 Leading/following 分支）姑蓝。

3. 此時(shí)節(jié)點(diǎn) 1，收到了節(jié)點(diǎn) 2 的選舉結(jié)果维贺。如果節(jié)點(diǎn) 2 的 zxid 更大它掂，那么清空投票箱，建立新的投票箱溯泣，廣播自己最新的投票結(jié)果虐秋。在同一次選舉中，如果在收到所有節(jié)點(diǎn)的投票結(jié)果后垃沦，如果投票箱中有一半以上的節(jié)點(diǎn)選出了某個(gè)節(jié)點(diǎn)客给，那么證明 leader 已經(jīng)選出來(lái)了，投票也就終止了肢簿。否則一直循環(huán)靶剑。

zookeeper 的選舉蜻拨，優(yōu)先比較大 zxid，zxid 最大的節(jié)點(diǎn)代表?yè)碛凶钚碌臄?shù)據(jù)桩引。如果沒(méi)有 zxid缎讼，如系統(tǒng)剛剛啟動(dòng)的時(shí)候，則比較機(jī)器的編號(hào)坑匠，優(yōu)先選擇編號(hào)大的血崭。

3.5 同步的過(guò)程

在選出 Leader 之后，zk 就進(jìn)入狀態(tài)同步的過(guò)程厘灼。其實(shí)就是把最新的 zxid 對(duì)應(yīng)的日志數(shù)據(jù)夹纫，應(yīng)用到其他的節(jié)點(diǎn)中。此 zxid 包含 follower 中寫(xiě)入日志但是未提交的 zxid 设凹。稱之為服務(wù)器提議緩存隊(duì)列 committedLog 中的 zxid舰讹。

同步會(huì)完成三個(gè) zxid 值的初始化。

peerLastZxid：該 learner 服務(wù)器最后處理的 zxid闪朱。?minCommittedLog：leader服務(wù)器提議緩存隊(duì)列 committedLog 中的最小 zxid月匣。?maxCommittedLog：leader服務(wù)器提議緩存隊(duì)列 committedLog 中的最大 zxid。

系統(tǒng)會(huì)根據(jù) learner 的?peerLastZxid和 leader 的?minCommittedLog监透，?maxCommittedLog做出比較后做出不同的同步策略桶错。

3.5.1 直接差異化同步

場(chǎng)景：?peerLastZxid介于?minCommittedLogZxid和?maxCommittedLogZxid間。

此種場(chǎng)景出現(xiàn)在胀蛮，上文提到過(guò)的院刁，Leader 發(fā)出了同步請(qǐng)求，但是還沒(méi)有 commit 就 down 了粪狼。 leader 會(huì)發(fā)送 Proposal 數(shù)據(jù)包退腥，以及 commit 指令數(shù)據(jù)包。新選出的 leader 繼續(xù)完成上一任 leader 未完成的工作再榄。

例如此刻 Leader 提議的緩存隊(duì)列為 0x20001狡刘，0x20002，0x20003困鸥，0x20004嗅蔬，此處 learn 的 peerLastZxid 為 0x20002，Leader會(huì)將 0x20003 和 0x20004 兩個(gè)提議同步給 learner疾就。

3.5.2 先回滾在差異化同步/僅回滾同步

此種場(chǎng)景出現(xiàn)在澜术，上文提到過(guò)的，Leader 寫(xiě)入本地事務(wù)日志后猬腰，還沒(méi)發(fā)出同步請(qǐng)求鸟废，就 down 了，然后在同步日志的時(shí)候作為 learner 出現(xiàn)姑荷。

例如即將要 down 掉的 leader 節(jié)點(diǎn) 1盒延，已經(jīng)處理了 0x20001缩擂，0x20002，在處理 0x20003 時(shí)還沒(méi)發(fā)出提議就 down 了添寺。后來(lái)節(jié)點(diǎn) 2 當(dāng)選為新 leader胯盯，同步數(shù)據(jù)的時(shí)候，節(jié)點(diǎn) 1 又神奇復(fù)活计露。如果新 leader 還沒(méi)有處理新事務(wù)陨闹，新 leader 的隊(duì)列為，0x20001, 0x20002薄坏，那么僅讓節(jié)點(diǎn) 1 回滾到 0x20002 節(jié)點(diǎn)處，0x20003 日志廢棄寨闹，稱之為僅回滾同步胶坠。如果新 leader 已經(jīng)處理 0x30001 , 0x30002 事務(wù)，那么新 leader 此處隊(duì)列為0x20001繁堡，0x20002沈善，0x30001，0x30002椭蹄，那么讓節(jié)點(diǎn) 1 先回滾闻牡，到 0x20002 處，再差異化同步0x30001绳矩，0x30002罩润。

3.5.3 全量同步

peerLastZxid小于?minCommittedLogZxid或者 leader 上面沒(méi)有緩存隊(duì)列。leader 直接使用 SNAP 命令進(jìn)行全量同步翼馆。

四割以、使用 Raft + RocksDB 分布式 KV 存儲(chǔ)服務(wù)

當(dāng)前開(kāi)源的緩存 kv 系統(tǒng)，大都是 AP 系統(tǒng)应媚，例如設(shè)置主從同步集群 redis严沥，master 異步同步到 slave。雖然在 master 停止服務(wù)后中姜，slave 會(huì)頂上來(lái)消玄。但是在 master 寫(xiě)入了數(shù)據(jù)，但是還沒(méi)來(lái)得及同步到 slave 就 down 了丢胚，然后 slave 被選為主節(jié)點(diǎn)繼續(xù)對(duì)外提供服務(wù)的情況下翩瓜，會(huì)丟失部分?jǐn)?shù)據(jù)。這對(duì)于要求強(qiáng)一致性的系統(tǒng)來(lái)說(shuō)是不可接受的奥溺。例如很多場(chǎng)景下 redis 做分布式鎖，有天然的缺陷在里面骨宠，如果 master 停止服務(wù)立美，這個(gè)鎖不很不可靠的，雖然出現(xiàn)的幾率很小，但一旦出現(xiàn)劲腿，將是致命的錯(cuò)誤。

為了實(shí)現(xiàn) CP 的 KV 存儲(chǔ)系統(tǒng)鸟妙，且要兼容現(xiàn)有的 redis 業(yè)務(wù)焦人。有贊開(kāi)發(fā)了 ZanKV（先已開(kāi)源ZanRedisDB）。

底層的存儲(chǔ)結(jié)構(gòu)是 RocksDB（底層采用 LSM 數(shù)據(jù)結(jié)構(gòu)）重父。一個(gè)?setx=1的會(huì)通過(guò) redis protocol 協(xié)議傳輸花椭，內(nèi)容會(huì)通過(guò) Raft 協(xié)議，同步寫(xiě)入到其他的節(jié)點(diǎn)的 RocksDB房午。有了Raft 理論的加持矿辽，RocksDB優(yōu)秀的存儲(chǔ)性能，即使遇到網(wǎng)絡(luò)分區(qū)郭厌，master 節(jié)點(diǎn) down 掉嗦锐， slave 節(jié)點(diǎn) down 掉，等一系列異常情況沪曙，其都能輕松應(yīng)對(duì)奕污。在擴(kuò)容方面，系統(tǒng)用選擇維護(hù)映射表的方式來(lái)建立分區(qū)和節(jié)點(diǎn)的關(guān)系液走，映射表會(huì)根據(jù)一定的算法并配合靈活的策略生成碳默，來(lái)達(dá)到方便擴(kuò)容。