一讽膏、一致性
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ī)房寫入數(shù)據(jù)高蜂，不能同步到B機(jī)房聪黎。寫入失敗。此時(shí)失去了可用性备恤。
保證可用性：數(shù)據(jù)在 A 機(jī)房的 n1~n3 節(jié)點(diǎn)都寫入成功后返回成功稿饰。數(shù)據(jù)在 B 機(jī)房的 n4~n5 節(jié)點(diǎn)也寫入數(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)寫入成功即可沉噩。是不是 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 常見場(chǎng)景
CA without P： 在分布式環(huán)境中康聂，P 是不可避免的匾嘱，天災(zāi)（某軟公司的Azure被雷劈劈中）人禍（某里公司 A 和 B 機(jī)房之間的光纜被挖斷）都能導(dǎo)致P
CP without A：相當(dāng)于每個(gè)寫請(qǐng)求都須在Server之前強(qiáng)一致。P (分區(qū))會(huì)導(dǎo)致同步時(shí)間無限延長(zhǎng)早抠。這個(gè)是可以保證的。例如數(shù)據(jù)庫(kù)的分布式事務(wù)撬讽，兩階段提交蕊连，三階段提交等
AP without C： 當(dāng)網(wǎng)絡(luò)分區(qū)發(fā)生悬垃，A 和 B 集群失去聯(lián)系。為了保證高可用甘苍，系統(tǒng)在寫入時(shí)尝蠕，系統(tǒng)寫入部分節(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)致一致性的問題茁计。
二、一致性協(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í)成功或者失敗优质，卻無法知道其他節(jié)點(diǎn)的操作的成功或失敗竣贪。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí)，為了保持事務(wù)的 ACID 特性盆赤，需要引入一個(gè)作為協(xié)調(diào)者的組件來統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫入磁盤等等)贾富。因此，二階段提交的算法思路可以概括為：參與者將操作成敗通知協(xié)調(diào)者牺六，再由協(xié)調(diào)者根據(jù)所有參與者的反饋情報(bào)決定各參與者是否要提交操作還是中止操作颤枪。
2.1.1 兩種角色
- 協(xié)調(diào)者
- 參與者
2.1.2處理階段
- 詢問投票階段：事務(wù)協(xié)調(diào)者給每個(gè)參與者發(fā)送 Prepare 消息，參與者受到消息后淑际，畏纲，要么在本地寫入 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 是沒有提交事務(wù)數(shù)據(jù)的。在備用協(xié)調(diào)者啟動(dòng)了盏档，去詢問參與者凶掰，由于3死掉了，一直不知道它處于什么狀態(tài)（接受了提交事務(wù)蜈亩，還是反饋了能執(zhí)行還是不能執(zhí)行 3 個(gè)狀態(tài)）懦窘。面對(duì)這種情況，2PC稚配，是不能解決的畅涂，要解決需要下文介紹的 3PC。
2.1.4缺點(diǎn)
-
同步阻塞問題：由于所有參與的節(jié)點(diǎn)都是事務(wù)阻塞型的道川，例如
update table set status=1 where current_day=20181103午衰，那么參與者table表的current_day=20181103的記錄都會(huì)被鎖住，其他的要修改current_day=20181103行的事務(wù)冒萄，都會(huì)被阻塞 - 單點(diǎn)故障阻塞其他事務(wù)：協(xié)調(diào)者再執(zhí)行提交的階段 down 掉臊岸，所有的參與者出于鎖定事務(wù)資源的狀態(tài)中。無法完成相關(guān)的事務(wù)操作尊流。
- 參與者和協(xié)調(diào)者同時(shí) down 掉：協(xié)調(diào)者在發(fā)送完 commit 消息后 down 掉帅戒，而唯一接受到此消息的參與者也 down 掉了。新協(xié)調(diào)者接管崖技，也是一個(gè)懵逼的狀態(tài)逻住，不知道此條事務(wù)的狀態(tài)。無論提交或者回滾都是不合適的迎献。這個(gè)是兩階段提交無法改變的
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ù)詢問階段（ can commit 階段)：協(xié)調(diào)者向參與者發(fā)送 commit 請(qǐng)求渔伯，然后等待參與者反應(yīng)。這個(gè)和 2PC 階段不同的是肄程，此時(shí)參與者沒有鎖定資源锣吼，沒有寫 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)沒有收到docommit消息艇肴，觸發(fā)超時(shí)機(jī)制，會(huì)自己提交事務(wù)叁温。此番處理的邏輯是再悼，能夠進(jìn)入此階段，說明在事務(wù)詢問階段所有節(jié)點(diǎn)都是好的膝但。即使在提交的時(shí)候部分失敗冲九，有理由相信，此時(shí)大部分節(jié)點(diǎn)都是好的锰镀。是可以提交的
2.2.2 缺點(diǎn)
- 不能解決網(wǎng)絡(luò)分區(qū)的導(dǎo)致的數(shù)據(jù)不一致的問題：例如 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)者向15個(gè)節(jié)點(diǎn)發(fā)送回滾事務(wù)的消息古拴。但是此時(shí)A箩帚，B機(jī)房的網(wǎng)絡(luò)分區(qū)。13 號(hào)節(jié)點(diǎn)會(huì)回滾黄痪。但是 4~5 節(jié)點(diǎn)由于沒收到回滾事務(wù)的消息紧帕，而提交了事務(wù)。待網(wǎng)絡(luò)分區(qū)恢復(fù)后桅打，會(huì)出現(xiàn)數(shù)據(jù)不一致的情況是嗜。 - 不能解決 fail-recover 的問題：
由于 3PC 有超時(shí)機(jī)制的存在，2PC 中未解決的問題挺尾，參與者和協(xié)調(diào)者同時(shí) down 掉鹅搪，也就解決了。一旦參與者在超時(shí)時(shí)間內(nè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ù)都無法提交锰蓬，參與者的資源都出于鎖定的狀態(tài)幔睬，對(duì)于系統(tǒng)的影響是災(zāi)難性的，而且出現(xiàn)網(wǎng)絡(luò)分區(qū)的情況芹扭，很有可能會(huì)出現(xiàn)數(shù)據(jù)不一致的情況麻顶。有沒有不需要協(xié)調(diào)者角色，每個(gè)參與者來協(xié)調(diào)事務(wù)呢舱卡，在網(wǎng)絡(luò)分區(qū)的情況下辅肾，又能最大程度保證一致性的解決方案呢。此時(shí) Paxos 出現(xiàn)了轮锥。
Paxos 算法是 Lamport 于 1990 年提出的一種基于消息傳遞的一致性算法矫钓。由于算法難以理解起初并沒有引起人們的重視，Lamport在八年后重新發(fā)表舍杜，即便如此Paxos算法還是沒有得到重視新娜。2006 年 Google 的三篇論文石破天驚，其中的 chubby 鎖服務(wù)使用Paxos 作為 chubbycell 中的一致性既绩，后來才得到關(guān)注概龄。
2.3.1 解決了什么問題
- 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é)議過于相似锣光，詳細(xì)講解參照下文，Zookeeper原理部分
2.4 Raft協(xié)議
Paxos 是論證了一致性協(xié)議的可行性铝耻，但是論證的過程據(jù)說晦澀難懂誊爹，缺少必要的實(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)求诈火，寫入本地后兽赁，然后同步到其他副本中
- Follower（從節(jié)點(diǎn)）：從 Leader 中接受更新請(qǐng)求，然后寫入本地日志文件冷守。對(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 在選舉過程中發(fā)起，收到 quorum (多數(shù)派）響應(yīng)后幕随，成為 leader蚁滋。
- AppendEntries：附加日志，leader 發(fā)送日志和心跳的機(jī)制
- election timeout：選舉超時(shí)赘淮，如果 follower 在一段時(shí)間內(nè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í)序保證一致性涧黄，通過邏輯遞增的 term-id 和 log-id 保證篮昧。
2.4.3 選主契機(jī)
- 在超時(shí)時(shí)間內(nèi)沒有收到 Leader 的心跳
- 啟動(dòng)時(shí)
2.4.4 選主過程
如圖raft-2所示，Raft將時(shí)間分為多個(gè) term（任期）笋妥，term 以連續(xù)的整數(shù)來標(biāo)識(shí)懊昨，每個(gè) term 表示一個(gè)選舉的開始。例如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)（注意這并不是說選出來的事務(wù)id一定是最大的，沽讹。例如下圖raft-1af六個(gè)節(jié)點(diǎn)（正方形框里面的數(shù)字是選舉的輪數(shù)term）般卑。在第四輪選舉中，a先發(fā)出投票爽雄，六臺(tái)機(jī)器中蝠检，ae都會(huì)投a，即使f不投a挚瘟，a也會(huì)贏得選舉叹谁。）饲梭。如果沒有事務(wù)id（如剛啟動(dòng)時(shí)），就遵循投票請(qǐng)求先來先頭焰檩。然后Leader將最新的日志復(fù)制到各個(gè)節(jié)點(diǎn)憔涉，再對(duì)外提供服務(wù)。
當(dāng)然除了這些選舉限制析苫，還會(huì)有其他的情況兜叨。如commit限制等保證，Leader選舉成功一定包含所有的commit和log
2.4.5 日志復(fù)制過程
raft日志寫入過程衩侥，主節(jié)點(diǎn)收到一個(gè)x=1的請(qǐng)求后国旷，會(huì)寫入本地日志，然后將x=1的日志廣播出去茫死，follower如果收到請(qǐng)求跪但，會(huì)將日志寫入本地 log ，然后返回成功峦萎。當(dāng) leader 收到半數(shù)以上的節(jié)點(diǎn)回應(yīng)時(shí)特漩，會(huì)將此日志的狀態(tài)變?yōu)閏ommit，然后廣播消息讓 follwer 提交日志骨杂。節(jié)點(diǎn)在 commit 日志后，會(huì)更新狀態(tài)機(jī)中的 logindex 雄卷。
firstLogIndex/lastLogIndex 為節(jié)點(diǎn)中開始和結(jié)束的索引位置（包含提交搓蚪，未提交，寫入狀態(tài)機(jī)）commitIndex：已提交的索引丁鹉。applyIndex：已寫入狀態(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)容都沒變魔熏。
第二個(gè)原則衷咽，在 Leader 復(fù)制給 Follower 時(shí)鸽扁，要傳遞當(dāng)前最新日志 currenTermId 和currentL??ogIndex，以及上一條日志 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)沒有找到(term7裆赵，logIndex11)的日志东囚，會(huì)讓Leader，d 節(jié)點(diǎn)重新發(fā)送战授。d 節(jié)點(diǎn)會(huì)重新發(fā)（term6页藻，logIndex10）(term7，logIndex11)植兰，還是沒有(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ì)開發(fā)者 Burrows 曾經(jīng)說過：“所有一致性協(xié)議本質(zhì)上要么是 Paxos 要么是其變體”堵泽。Paxos 雖然解決了分布式系統(tǒng)中，多個(gè)節(jié)點(diǎn)就某個(gè)值達(dá)成一致性的通信協(xié)議恢总。但是還是引入了其他的問題落恼。由于其每個(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é)議還解決了這些問題
- 在半數(shù)以下節(jié)點(diǎn)宕機(jī)努隙，依然能對(duì)臺(tái)提供服務(wù)
- 客戶端所有的寫請(qǐng)求，交由 Leader 來處理辜昵。寫入成功后荸镊，需要同步給所有的 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ù)模型是一棵樹舀锨，由斜杠（ / ）分割的路徑名唯一標(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ù)操作都是需要記錄到日志文件中的襟衰，可通過 dataLogDir 配置文件目錄，文件是以寫入的第一條事務(wù) zxid 為后綴粪摘，方便后續(xù)的定位查找瀑晒。zk 會(huì)采取“磁盤空間預(yù)分配”的策略绍坝，來避免磁盤 Seek 頻率，提升 zk 服務(wù)器對(duì)事務(wù)請(qǐng)求的影響能力苔悦。默認(rèn)設(shè)置下轩褐，每次事務(wù)日志寫入操作都會(huì)實(shí)時(shí)刷入磁盤，也可以設(shè)置成非實(shí)時(shí)（寫到內(nèi)存文件流玖详，定時(shí)批量寫入磁盤）把介，但那樣斷電時(shí)會(huì)帶來丟失數(shù)據(jù)的風(fēng)險(xiǎn)。
- 事務(wù)快照：數(shù)據(jù)快照是 zk 數(shù)據(jù)存儲(chǔ)中另一個(gè)非常核心的運(yùn)行機(jī)制蟋座。數(shù)據(jù)快照用來記錄 zk 服務(wù)器上某一時(shí)刻的全量?jī)?nèi)存數(shù)據(jù)內(nèi)容拗踢，并將其寫入到指定的磁盤文件中，可通過 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)的更新并寫入本地日志反璃；
- LEADING：作為系統(tǒng)主節(jié)點(diǎn)，接受客戶端更新假夺，寫入本地日志并復(fù)制到從節(jié)點(diǎn)
3.3 常見的誤區(qū)
- 寫入節(jié)點(diǎn)后的數(shù)據(jù)淮蜈，立馬就能被讀到，這是錯(cuò)誤的已卷。** zk 寫入是必須通過 leader 串行的寫入梧田，而且只要一半以上的節(jié)點(diǎn)寫入成功即可。而任何節(jié)點(diǎn)都可提供讀取服務(wù)。例如：zk柿扣，有 1~5 個(gè)節(jié)點(diǎn)肖方，寫入了一個(gè)最新的數(shù)據(jù)，最新數(shù)據(jù)寫入到節(jié)點(diǎn) 1~3未状，會(huì)返回成功俯画。然后讀取請(qǐng)求過來要讀取最新的節(jié)點(diǎn)數(shù)據(jù)，請(qǐng)求可能被分配到節(jié)點(diǎn) 4~5 司草。而此時(shí)最新數(shù)據(jù)還沒有同步到節(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 選舉同步過程
3.4.1 發(fā)起投票的契機(jī)
- 節(jié)點(diǎn)啟動(dòng)
- 節(jié)點(diǎn)運(yùn)行期間無法與 Leader 保持連接嗅剖，
- Leader 失去一半以上節(jié)點(diǎn)的連接
3.4.2 如何保證事務(wù)
ZAB 協(xié)議類似于兩階段提交辩越，客戶端有一個(gè)寫請(qǐng)求過來，例如設(shè)置 /my/test 值為 1信粮，Leader 會(huì)生成對(duì)應(yīng)的事務(wù)提議（proposal）（當(dāng)前 zxid為 0x5000010 提議的 zxid 為Ox5000011）黔攒，現(xiàn)將set /my/test 1（此處為偽代碼）寫入本地事務(wù)日志，然后set /my/test 1日志同步到所有的follower蒋院。follower收到事務(wù) proposal ，將 proposal 寫入到事務(wù)日志莲绰。如果收到半數(shù)以上 follower 的回應(yīng)欺旧，那么廣播發(fā)起 commit 請(qǐng)求。follower 收到 commit 請(qǐng)求后蛤签。會(huì)將文件中的 zxid ox5000011 應(yīng)用到內(nèi)存中辞友。
上面說的是正常的情況。有兩種情況。第一種 Leader 寫入本地事務(wù)日志后称龙，沒有發(fā)送同步請(qǐng)求留拾，就 down 了。即使選主之后又作為 follower 啟動(dòng)鲫尊。此時(shí)這種還是會(huì)日志會(huì)丟掉（原因是選出的 leader 無此日志痴柔，無法進(jìn)行同步）。第二種 Leader 發(fā)出同步請(qǐng)求疫向，但是還沒有 commit 就 down 了咳蔚。此時(shí)這個(gè)日志不會(huì)丟掉，會(huì)同步提交到其他節(jié)點(diǎn)中搔驼。
3.4.3 服務(wù)器啟動(dòng)過程中的投票過程
現(xiàn)在 5 臺(tái) zk 機(jī)器依次編號(hào) 1~5
- 節(jié)點(diǎn) 1 啟動(dòng)谈火，發(fā)出去的請(qǐng)求沒有響應(yīng)，此時(shí)是 Looking 的狀態(tài)
- 節(jié)點(diǎn) 2 啟動(dòng)舌涨，與節(jié)點(diǎn) 1 進(jìn)行通信糯耍，交換選舉結(jié)果。由于兩者沒有歷史數(shù)據(jù)囊嘉，即 zxid 無法比較温技，此時(shí) id 值較大的節(jié)點(diǎn) 2 勝出，但是由于還沒有超過半數(shù)的節(jié)點(diǎn)哗伯，所以 1 和 2 都保持 looking 的狀態(tài)
- 節(jié)點(diǎn) 3 啟動(dòng)荒揣，根據(jù)上面的分析，id 值最大的節(jié)點(diǎn) 3 勝出焊刹，而且超過半數(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)行過程中選主過程
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 是誰，就不要瞎折騰選舉了（此時(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)選出來了，投票也就終止了。否則一直循環(huán)
zookeeper 的選舉，優(yōu)先比較大 zxid瓦阐，zxid 最大的節(jié)點(diǎn)代表?yè)碛凶钚碌臄?shù)據(jù)。如果沒有 zxid篷牌，如系統(tǒng)剛剛啟動(dòng)的時(shí)候睡蟋，則比較機(jī)器的編號(hào)，優(yōu)先選擇編號(hào)大的
3.5 同步的過程
在選出 Leader 之后枷颊，zk 就進(jìn)入狀態(tài)同步的過程戳杀。其實(shí)就是把最新的 zxid 對(duì)應(yīng)的日志數(shù)據(jù)，應(yīng)用到其他的節(jié)點(diǎn)中夭苗。此 zxid 包含 follower 中寫入日志但是未提交的 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)在，上文提到過的淮悼，Leader 發(fā)出了同步請(qǐng)求咐低，但是還沒有 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)在，上文提到過的癌刽，Leader寫入本地事務(wù)日志后役首，還沒發(fā)出同步請(qǐng)求，就down了显拜，然后在同步日志的時(shí)候作為learner出現(xiàn)衡奥。
例如即將要 down 掉的 leader 節(jié)點(diǎn) 1，已經(jīng)處理了 0x20001远荠，0x20002矮固，在處理 0x20003 時(shí)還沒發(fā)出提議就 down 了。后來節(jié)點(diǎn) 2 當(dāng)選為新 leader譬淳，同步數(shù)據(jù)的時(shí)候档址，節(jié)點(diǎn) 1 又神奇復(fù)活。如果新 leader 還沒有處理新事務(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上面沒有緩存隊(duì)列场晶。leader直接使用SNAP命令進(jìn)行全量同步
四混埠、使用 Raft + RocksDB 有贊分布式 KV 存儲(chǔ)服務(wù)
當(dāng)前開源的緩存 kv 系統(tǒng)，大都是 AP 系統(tǒng)诗轻，例如設(shè)置主從同步集群 redis钳宪，master 異步同步到 slave。雖然在 master 停止服務(wù)后扳炬，slave 會(huì)頂上來吏颖。但是在 master 寫入了數(shù)據(jù)，但是還沒來得及同步到 slave 就 down 了恨樟，然后 slave 被選為主節(jié)點(diǎn)繼續(xù)對(duì)外提供服務(wù)的情況下半醉，會(huì)丟失部分?jǐn)?shù)據(jù)。這對(duì)于要求強(qiáng)一致性的系統(tǒng)來說是不可接受的劝术。例如很多場(chǎng)景下 redis 做分布式鎖缩多，有天然的缺陷在里面呆奕，如果 master 停止服務(wù)，這個(gè)鎖不很不可靠的衬吆，雖然出現(xiàn)的幾率很小梁钾，但一旦出現(xiàn)，將是致命的錯(cuò)誤逊抡。
為了實(shí)現(xiàn) CP 的 KV 存儲(chǔ)系統(tǒng)姆泻，且要兼容現(xiàn)有的 redis 業(yè)務(wù)。有贊開發(fā)了 ZanKV（先已開源ZanRedisDB）冒嫡。
底層的存儲(chǔ)結(jié)構(gòu)是 RocksDB（底層采用 LSM 數(shù)據(jù)結(jié)構(gòu)）拇勃。一個(gè)set x=1的會(huì)通過 redis protocol 協(xié)議傳輸，內(nèi)容會(huì)通過 Raft 協(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ù)映射表的方式來建立分區(qū)和節(jié)點(diǎn)的關(guān)系牙勘，映射表會(huì)根據(jù)一定的算法并配合靈活的策略生成，來達(dá)到方便擴(kuò)容所禀。具體原理可參見使用開源技術(shù)構(gòu)建有贊分布式KV存儲(chǔ)服務(wù)
五方面、總結(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ù)之前先寫操作內(nèi)容日志耿焊，然后再去修改數(shù)據(jù)。即使修改數(shù)據(jù)時(shí)異常遍搞，也可以通過操作內(nèi)容日志恢復(fù)數(shù)據(jù)）
分布式存儲(chǔ)系統(tǒng)中罗侯，是假設(shè)機(jī)器是不穩(wěn)定，隨時(shí)都有可能 down 掉的情況下來設(shè)計(jì)的溪猿。也就是說就算機(jī)器 down 掉了钩杰，用戶寫入的數(shù)據(jù)也不能丟纫塌，避免單點(diǎn)故障。為此每一份寫入的數(shù)據(jù)讲弄，需要在多個(gè)副本中同時(shí)存放护戳。例如 zk 節(jié)點(diǎn)數(shù)據(jù)復(fù)制，etcd 的數(shù)據(jù)復(fù)制垂睬。而復(fù)制數(shù)據(jù)給節(jié)點(diǎn)又會(huì)帶來一致性的問題，例如主節(jié)點(diǎn)和從節(jié)點(diǎn)數(shù)據(jù)不一致改如何去同步數(shù)據(jù)抗悍。也會(huì)帶來可用性的問題驹饺，如 leader 節(jié)點(diǎn) down 掉，如何快速選主缴渊，恢復(fù)數(shù)據(jù)等赏壹。好在已有成熟的理論如 Paxos 協(xié)議，ZAB 協(xié)議 Raft 協(xié)議等做為支撐衔沼。
參考文章/書籍
《從 paxos 到 Zookeeper 分布式一致性原理與實(shí)踐》
使用開源技術(shù)構(gòu)建有贊分布式KV存儲(chǔ)服務(wù)
關(guān)于分布式事務(wù)蝌借、兩階段提交協(xié)議、三階提交協(xié)議
