本文編寫的目的：為了深入理解后期關(guān)于zookeeper的文章，本文這里對分布式一致性算法的由來以及要解決的問題做一個簡述，更加深入的原理性東西后續(xù)將會以專輯的形式撰寫。另該文比較長，建議收藏閱讀
本文編寫的順序:從集中式演化到分布式--->分布式出現(xiàn)的一些問題--->如何解決這些問題(即最重要的一致性問題)---->事務(wù)(保證一致性的方法)---->從早期的ACID到CAP/BASE理論---->2pc/3pc----->Paxos算法
背景
20世紀(jì)60年代大型主機被發(fā)明出來以后，集中式的計算機系統(tǒng)架構(gòu)成為了主流，其單機處理能力方面的優(yōu)勢非常明顯，但從20世紀(jì)80年代之后，傳統(tǒng)的集中式處理模式越來越不能滿足人們的需求，同時集中式系統(tǒng)有明顯的單點故障問題，從2008年開始，阿里開啟了“去IOE”計劃，后來逐漸的往分布式系統(tǒng)的方向發(fā)展。
分布式系統(tǒng)是一個硬件或軟件組件分布在不同的網(wǎng)路計算機上，彼此之間僅僅通過消息傳遞進行通信和協(xié)調(diào)的系統(tǒng)。因此分布式系統(tǒng)具有以下幾個特點：
分布性
多臺計算機在空間上隨意分布，同時分布情況也會隨時變動
對等性
集群中的每個節(jié)點角色都是一樣的，注意副本的概念
并發(fā)性
多個機器可能會同時操作一個數(shù)據(jù)庫或存儲系統(tǒng)，可能會引起數(shù)據(jù)不一致問題
缺乏全局時鐘
分布式系統(tǒng)中的多個主機事件先后順序很難界定
故障總發(fā)生
服務(wù)器宕機，網(wǎng)絡(luò)擁堵和延遲
同時和分布式系統(tǒng)進行對比發(fā)現(xiàn)集中式系統(tǒng)具有以下幾個特點:
- 部署結(jié)構(gòu)簡單
- 成本高
- 單點故障
- 大型主機的性能擴展受限于摩爾定律
注意：這里要區(qū)分集群和分布式的概念，集群是指大量的機器做同一件事情；分布式是指每臺機器都有不同的角色，做不同的事情
分布式異常問題
分布式系統(tǒng)體系結(jié)構(gòu)從出現(xiàn)到現(xiàn)在仍有很多的問題，這里列出一些典型的問題
通信異常
從集中式向分布式演變，必然會引入網(wǎng)絡(luò)因素，由于網(wǎng)絡(luò)的不可靠性，必然會在分布式節(jié)點之間出現(xiàn)網(wǎng)絡(luò) 異常的情況
網(wǎng)絡(luò)分區(qū)
網(wǎng)絡(luò)分區(qū)也就是常說的腦裂，即出現(xiàn)多個局部小集群，每個局部網(wǎng)絡(luò)可以互相通信
三態(tài)
三態(tài)指的是三種狀態(tài)，即成功、失敗、超時；在集中式系統(tǒng)中只有成功和失敗，而超時是由于分布式系統(tǒng)中會出現(xiàn)網(wǎng)絡(luò)異常才會有的狀態(tài)
節(jié)點故障
分布式節(jié)點總會出現(xiàn)宕機或者僵死現(xiàn)象
數(shù)據(jù)丟失
對于有狀態(tài)的節(jié)點，數(shù)據(jù)丟失意味著狀態(tài)丟失，通常只能從其他節(jié)點讀取，恢復(fù)存儲的狀態(tài)；通常針對這種問題，通過引入副本機制就可以解決
衡量分布式系統(tǒng)的性能
- 性能
- 即系統(tǒng)吞吐能力、響應(yīng)延遲、QPS等
- 可用性
- 可擴展性
- 一致性
一致性模型
分布式環(huán)境下，一致性指的是數(shù)據(jù)在多個副本之間是否能夠保持一致的特性，對于一個將數(shù)據(jù)副本分布在不同節(jié)點的系統(tǒng)上來說，如果對一個節(jié)點的數(shù)據(jù)進行了更新操作，卻沒有使得第二個節(jié)點上的數(shù)據(jù)得到響應(yīng)的更新，那么此時在讀取第二個節(jié)點的數(shù)據(jù)時，將會出現(xiàn)臟讀現(xiàn)象(即數(shù)據(jù)不一致).那么一致性又分為以下幾種：
強一致性
即寫操作完成后，讀操作一定能夠讀到最新的數(shù)據(jù)，在分布式場景下，很難實現(xiàn)；Paxos、Quorum機制、ZAB協(xié)議能夠?qū)崿F(xiàn),后面會對這幾種協(xié)議算法進行講解。
弱一致性
不承諾立即可以讀到寫入的值，也不承諾多久后能達到數(shù)據(jù)一致，但會盡可能保證某個時間級別后，數(shù)據(jù)達到一致狀態(tài)
讀寫一致性
用戶讀取自己寫入結(jié)果的一致性，保證用戶能夠第一時間看到自己更新的內(nèi)容;這種實現(xiàn)的解決方案有:
一種方案是對于特定的內(nèi)容，我們?nèi)ブ鲙觳樵?/p>
設(shè)置一個更新時間窗口，在剛更新的一段時間內(nèi)，默認去主庫讀取，過了這個窗口后，挑選最近更新的從庫進行讀取
直接記錄用戶更新的時間戳，在請求的時候把這個時間戳帶上，凡是最后更新時間小于這個時間戳的從庫都不響應(yīng)
單調(diào)讀一致性
本地讀到的數(shù)據(jù)不比上次讀到的舊，多次刷新返回舊數(shù)據(jù)會出現(xiàn)靈異事件，對于這種情況可以通過hash映射到同一臺機器上
因果一致性
如果節(jié)點A在更新完某個數(shù)據(jù)后通知了節(jié)點B，那么節(jié)點B之后對該數(shù)據(jù)的訪問和修改基于A更新的值。此時，和節(jié)點A無因果關(guān)系的節(jié)點C的數(shù)據(jù)訪問則沒有這樣的限制
最終一致性
所有分布式一致性模型中最弱的。不考慮中間的任何狀態(tài)，只保證經(jīng)過一段時間之后，最終系統(tǒng)內(nèi)數(shù)據(jù)正確，最大程度上保證了系統(tǒng)的并發(fā)能力，因此在高并發(fā)場景下，也是使用最廣的一致性模型
事務(wù)
事務(wù)是可以保證一致性的方法，在集中式系統(tǒng)架構(gòu)中可以通過ACID的方式實現(xiàn)，在早期分布式架構(gòu)，是通過CAP/BASE理論來實現(xiàn)的，后來又演化出了2pc/3pc,以及Paxos、Raft等算法來保證一致性。
事務(wù)是由一系列對系統(tǒng)中數(shù)據(jù)進行訪問與更新的操作所組成的一個程序執(zhí)行邏輯單元。(概念性的東西直接略過～)
-
ACID
-
Atomicity原子性
簡單說就是一個操作序列要么全部成功執(zhí)行，要么全部不執(zhí)行
-
Consistency一致性
也就是說數(shù)據(jù)從一個一致性狀態(tài)轉(zhuǎn)變到另一個一致性狀態(tài)，中間不能存在不一致的狀態(tài)
-
Isolation隔離性
在并發(fā)環(huán)境下，一個事務(wù)的執(zhí)行不能被其他事務(wù)所干擾，每個事務(wù)都有各自獨立完整的數(shù)據(jù)空間，也就是說一個事務(wù)內(nèi)部的操作以及數(shù)據(jù)的使用對其他并發(fā)的事務(wù)都是隔離的。
根據(jù)隔離性的強度分為4個級別:
-
未授權(quán)讀取(讀未提交)
這是隔離級別最低的。比如說事務(wù)A和事務(wù)B同時進行，事務(wù)A在整個執(zhí)行的過程中，會將某個數(shù)據(jù)值從1開始做加法操作直到變成10之后提交事務(wù)，而此時事務(wù)B能夠看到事務(wù)A操作這個數(shù)據(jù)的所有變化(即從1到10的變化)，而這一系列中間值的讀取就是未授權(quán)讀取
-
授權(quán)讀取(讀已提交)
只允許讀取已經(jīng)被提交的數(shù)據(jù)而且不可重復(fù)讀。比如說事務(wù)A和事務(wù)B同時進行，同樣進行加法操作(從1到10),那么此時事務(wù)B是無法看到所有的中間值，只能看到最終的10.
-
可重復(fù)讀取
在保證事務(wù)處理的過程中，多次讀取同一個數(shù)據(jù)時候，它的值和事務(wù)開始時刻是一致的，可能會出現(xiàn)幻影數(shù)據(jù)（即同一個事務(wù)操作，在前后兩個時間段內(nèi)執(zhí)行對同一個數(shù)據(jù)項進行讀取，可能會得到不同的結(jié)果），還是拿上面的例子，事務(wù)B在第一次事務(wù)讀取的時候，始終讀到的是1，但是到第二次事務(wù)讀取的時候就會變成了10（因為這個時候事務(wù)A已經(jīng)完成了）
-
串行化
即所有的事務(wù)串行執(zhí)行
-
Durability持久性
即一個事務(wù)一旦提交，對應(yīng)數(shù)據(jù)的狀態(tài)變更就是永久性的
-
-
CAP
-
Consistency一致性
數(shù)據(jù)在多個副本之間是否能夠保持一致的特性。
-
Avaliabilty可用性
指系統(tǒng)提供的服務(wù)必須一直處于可用的狀態(tài)，對于用戶的操作總能給在有限的時間內(nèi)返回結(jié)果，這里要注意下是在有限的時間內(nèi)哦
-
Partition tolerance分區(qū)容錯性
即分布式系統(tǒng)在遇到網(wǎng)絡(luò)分區(qū)的時候，仍然能夠保證對外提供滿足一致性和可用性的服務(wù)，除非整個網(wǎng)絡(luò)發(fā)生了故障
注意：分布式系統(tǒng)無法滿足上面三個特性，但是一定要有分布容錯性，即P，C和A根據(jù)需求進行衡量
-
-
BASE
-
Basically Avaliable 基本可用
即分布式系統(tǒng)中在出現(xiàn)故障的時候，允許損失部分可用性，比如響應(yīng)時間上的損失或者功能上的損失，例如雙11的時候，可以將一些無關(guān)緊要的服務(wù)進行降級
-
Soft state軟狀態(tài)
即允許系統(tǒng)中的數(shù)據(jù)存在中間狀態(tài)，且中間狀態(tài)的存在不會影響系統(tǒng)的整個可用性，即允許系統(tǒng)在不同節(jié)點的數(shù)據(jù)副本之間進行數(shù)據(jù)同步的過程出現(xiàn)延時
-
Eventually consistent最終一致性
強調(diào)的是系統(tǒng)中所有的數(shù)據(jù)副本，在經(jīng)過一段時間的同步后，最終達到一個一致的狀態(tài)
-
分布式一致性協(xié)議算
-
2pc
即二階段提交，絕大部分的關(guān)系型數(shù)據(jù)庫都是采用二階段提交協(xié)議來完成分布式事務(wù)處理。即將事務(wù)的提交過程分為了兩個階段來處理
[圖片上傳中...(2pc.png-4fad1c-1597757563590-0)]
-
階段一：請求/表決階段
-
1.事務(wù)詢問
協(xié)調(diào)者向參與者發(fā)起事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)操作，并等待響應(yīng)
-
2.執(zhí)行事務(wù)
各參與者執(zhí)行事務(wù)操作，并將undo和redo信息記錄到事務(wù)日志中
-
3.各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)
協(xié)調(diào)者根據(jù)所有的參與者是否都響應(yīng)了yes或者no來進行表決事務(wù)是否執(zhí)行或者不執(zhí)行
-
-
階段二：提交/執(zhí)行/回滾階段
-
情況1.執(zhí)行事務(wù)提交
-
1.發(fā)起提交請求
協(xié)調(diào)者向參與者發(fā)起commit請求
-
2.事務(wù)提交
參與者收到commit請求后，正式執(zhí)行事務(wù)提交，完成之后釋放資源
-
3.反饋事務(wù)提交結(jié)果
參與者完成事務(wù)之后，向協(xié)調(diào)者發(fā)送ack消息
-
4.完成事務(wù)
協(xié)調(diào)者收到所有參與者返回的ack消息，完成事務(wù)
-
-
-
情況2.中斷事務(wù)
-
1.發(fā)送回滾請求
協(xié)調(diào)者向參與者發(fā)起rollback請求
-
2.事務(wù)回滾
參與者收到rollback請求后，利用undo信息執(zhí)行事務(wù)回滾操作,完成之后釋放資源
-
3.反饋事務(wù)回滾結(jié)果
參與者完成事務(wù)之后，向協(xié)調(diào)者發(fā)送ack
-
4.中斷事務(wù)
協(xié)調(diào)者接收到所有參與者反饋的ack,完成事務(wù)中斷
-
-
二階段提交的問題
-
1.性能問題
從流程上看，在執(zhí)行過程中節(jié)點都處于阻塞狀態(tài)。各個操作數(shù)據(jù)庫的節(jié)點都占用數(shù)據(jù)庫資源，只有當(dāng)所有節(jié)點準(zhǔn)備完畢后，事務(wù)協(xié)調(diào)者才會通知進行全局commit/rollback，參與者進行本地事務(wù)commit/rollback之后才會釋放資源，對性能影響較大
-
2.單點故障問題
事務(wù)協(xié)調(diào)者是整個分布式事務(wù)的核心，一旦事務(wù)協(xié)調(diào)者出現(xiàn)故障，會導(dǎo)致參與者收不到commit/rollback的通知，從而導(dǎo)致參與者節(jié)點一直處于事務(wù)無法完成的中間狀態(tài)
-
3.數(shù)據(jù)不一致
在第二階段的時候，如果發(fā)生局部網(wǎng)絡(luò)問題，一部分事務(wù)參與者收不到commit/rollback消息，就會導(dǎo)致節(jié)點間數(shù)據(jù)不一致
-
4.太多保守
必須 收到所有參與的正反饋才提交事務(wù)如果有任意一個事務(wù)參與者的響應(yīng)沒有收到，則整個事務(wù)失敗回滾
-
-
3pc
基于2pc出現(xiàn)的一些問題，3pc進行了改進，也就是三階段提交，將2pc的第二個階段進行了一份為二，形成了CanCommit（提交詢問）、Precommit（預(yù)提交）、doCommit階段(最終提交)三個階段；其實3pc和2pc的不同點在于3pc增加了超時機制。
-
階段1:CanCommit(提交詢問)
-
1.事務(wù)詢問
協(xié)調(diào)者向所有參與者發(fā)送一個請求，詢問是否可以執(zhí)行事務(wù)提交操作，然后開始等待所有響應(yīng)者的響應(yīng)
-
2.各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)
正常情況下，所有參與者會反饋yes，然后進入預(yù)備狀態(tài)，否則反饋No
-
-
階段2:PreCommit(預(yù)提交)
-
情況1:執(zhí)行事務(wù)預(yù)提交(即所有參與者都響應(yīng)yes)
-
1.發(fā)起預(yù)提交請求
協(xié)調(diào)者向所有參與者發(fā)出preCommit請求，并進入準(zhǔn)備階段
-
2.事務(wù)預(yù)提交
參與者接收到preCommit請求后，執(zhí)行事務(wù)操作，然后將undo和redo信息記錄到事務(wù)日志中
3.各參與者向協(xié)調(diào)者反饋事務(wù)執(zhí)行的響應(yīng)
-
-
情況2:中斷事務(wù)(任何一個參與者反饋no或者超時就會中斷事務(wù))
- 1.發(fā)送中斷請求
- 2.中斷事務(wù)
-
-
階段3:doCommit(最終提交)
- 情況1:執(zhí)行提交
- 1.發(fā)送提交請求
- 2.事務(wù)提交
- 3.反饋事務(wù)提交結(jié)果
- 4.完成事務(wù)
- 情況2:中斷事務(wù)
- 1.發(fā)送中斷請求
- 2.事務(wù)回滾
- 3.反饋事務(wù)回滾結(jié)果
- 4.中斷事務(wù)
- 情況1:執(zhí)行提交
-
3pc特點
1.降低了參與者阻塞范圍,增加了超時自動處理的機制
2.能夠在出現(xiàn)單點故障后繼續(xù)保持一致
-
3.網(wǎng)絡(luò)分區(qū)會出現(xiàn)不一致的問題
即參與者接收到了preCommit消息后，出現(xiàn)了網(wǎng)絡(luò)分區(qū)，即協(xié)調(diào)者和參與者無法進行正常通信，這個時候該參與者依然會進行事務(wù)的提交，就會出現(xiàn)數(shù)據(jù)不一致的情況
-
Paxos
Paxos算法要解決的問題就是如何保證數(shù)據(jù)一致性，這是一種基于消息傳遞且具有高度容錯特的一致性算法
首先要引入拜占庭問題
拜占庭問題：即不同軍隊的將軍之間必須制定一個統(tǒng)一的行動計劃，但是在地理上都是分隔開來的，只能依靠通訊員進行通信，但是通訊員可能會存在叛徒，對消息進行篡改，從而欺騙將軍。
這種消息篡改的情況在同一個局域網(wǎng)內(nèi)幾乎不會出現(xiàn)，或者簡單通過校驗算法進行避免。但是在實際工程實踐中，可以假設(shè)不存在拜占庭問題，基于這種假設(shè)如何保證一致性呢？這個時候又引入Paxos的故事
古希臘有一個Paxos小島，島上采用會議的形式來通過法令，議會上的議員通過信使來傳遞消息，注意信使和議員都是兼職的，有可能隨時會離開議會，而且信使有可能會重復(fù)傳遞消息，也有可能一去不返。那么在這種情況下議會協(xié)議也要保證法令能夠正確選舉出來，而且不會產(chǎn)生沖突。
根據(jù)這個故事也就衍生出了Paxos算法，該算法有3個角色：
- 1.Proposer（提議者，用來發(fā)起提案的，相當(dāng)于zk中的leader角色）
- 2.Acceptor(接受者，可以接受或拒絕提案，相當(dāng)于zk中的follower角色)
- 3.Learner(學(xué)習(xí)者，學(xué)習(xí)被選定的提案，相當(dāng)于zk中的observer角色)
注意這里講解的是Basic Paxos，基于Baisc Paxos演化出了Multi Paxos,這里不做過多講解，有興趣的同學(xué)可自行查閱
大致流程就是首先選舉出一個Leader，也就是Proposer用來發(fā)起提案，然后發(fā)送給所有的Acceptor來進行投票，當(dāng)超過一半投通過票的時候，該提案也就通過了，那么這個時候Proposer會將該提案進行同步所有機器進行學(xué)習(xí)
也就是說Paxos是基于議會制，以少數(shù)服從多數(shù)的核心思想來保證一致性的
-
Raft
該算法不做過多講解，想要了解，請查看http://thesecretlivesofdata.com/raft/網(wǎng)址
Raft算法是一個分布式共識算法，有三個角色
1.Leader
-
2.follower
如果follower接收不到leader的心跳時，會變?yōu)閏andidate(這里會有150s~300s的等待時間)，發(fā)起投票是否成為新的leader
3.candidate(候選人)
核心思想：少數(shù)服從多數(shù)！
-
ZAB協(xié)議
zookeeper是基于該協(xié)議(zookeeper原子廣播協(xié)議)實現(xiàn)的。這里只做簡單介紹，該協(xié)議比較重要，后面會和zookeeper相關(guān)文章結(jié)合單獨進行講解！
該協(xié)議有兩種模式:
1.奔潰恢復(fù)
2.消息廣播
它和Paxos的區(qū)別聯(lián)系在于:
- 1.都存在類似于Leader角色，負責(zé)協(xié)調(diào)多個Follower進程的運行
- 2.Leader進程都會等待超過半數(shù)的Follower做出正確反饋后，才會將一個提案進行提交
- 3.zab協(xié)議中，每個proposal都包含一個epoch值,用了代表當(dāng)前Leader周期；Paxos中也存在同樣的標(biāo)識，名字為Ballot
- 4.zab協(xié)議主要用于構(gòu)建一個高可用的分布數(shù)數(shù)據(jù)主備系統(tǒng)
- 5.Paxos算法主要用于構(gòu)建一個分布式的一致性狀態(tài)機系統(tǒng)
后期將持續(xù)更新文章，更多喜歡請關(guān)注公眾號"初學(xué)大數(shù)據(jù)"
