詳解分布式一致性機(jī)制

-     前言    -

分布式中一致性是非常重要的，分為弱一致性和強(qiáng)一致性。現(xiàn)在主流的一致性協(xié)議一般都選擇的是弱一致性的特殊版本：最終一致性。下面就從分布式系統(tǒng)的基本原則講起，再整理一些遵循這些原則的協(xié)議或者機(jī)制，爭取通俗易懂。但是要真正實(shí)施起來把這些協(xié)議落地，可不是一篇文章能說清楚的，有太多的細(xì)節(jié)，要自己去看論文吶（順著維基百科找就行了）。

-     基本原則與理論    -

CAP（Consistency一致性，Availability可用性，Partition tolerance分區(qū)容錯(cuò)性）理論是當(dāng)前分布式系統(tǒng)公認(rèn)的理論，亦即一個(gè)分布式系統(tǒng)不可能同時(shí)滿足這三個(gè)特性，只能三求其二。對于分布式系統(tǒng)，P是基本要求，如果沒有P就不是分布式系統(tǒng)了，所以一般都是在滿足P的情況下，在C和A之間尋求平衡。

ACID（Atomicity原子性，Consistency一致性，Isolation隔離性，Durability持久性）是事務(wù)的特點(diǎn)，具有強(qiáng)一致性，一般用于單機(jī)事務(wù)，分布式事務(wù)若采用這個(gè)原則會(huì)喪失一定的可用性，屬于CP系統(tǒng)。

BASE（Basically Availabe基本可用，Soft state軟狀態(tài)，Eventually consistency最終一致性）理論是對大規(guī)模的互聯(lián)網(wǎng)分布式系統(tǒng)實(shí)踐的總結(jié)，用弱一致性來換取可用性，不同于ACID，屬于AP系統(tǒng)。

-     2PC    -

2 Phase Commit，兩階段提交，系統(tǒng)有兩個(gè)角色協(xié)調(diào)者和參與者，事務(wù)提交過程分為兩階段：

1. 提交事務(wù)請求（投票階段）
• 協(xié)調(diào)者向參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，等待響應(yīng)
• 參與者執(zhí)行事務(wù)操作，并將undo和redo日志記錄
• 參與者回復(fù)協(xié)調(diào)者，執(zhí)行成功則回Yes否則No
2. 執(zhí)行事務(wù)提交（執(zhí)行階段）
• 如果都是參與者都回復(fù)Yes，則協(xié)調(diào)者向參與者發(fā)送提交請求，否則發(fā)送回滾請求
• 參與者根據(jù)協(xié)調(diào)者的請求執(zhí)行事務(wù)提交或回滾，并向協(xié)調(diào)者發(fā)送Ack消息
• 協(xié)調(diào)者收到所有的Ack消息過后判斷事務(wù)的完成或者中斷

該協(xié)議可以視為強(qiáng)一致的算法，通常用來保證多份數(shù)據(jù)操作的原子性，也可以實(shí)現(xiàn)數(shù)據(jù)副本之間的一致性，實(shí)現(xiàn)簡單，但是缺點(diǎn)也很多，比如單點(diǎn)故障（協(xié)調(diào)者掛了整個(gè)系統(tǒng)就沒法對外服務(wù)，任一節(jié)點(diǎn)掛了事務(wù)就沒法執(zhí)行，沒有容錯(cuò)機(jī)制）、阻塞（兩個(gè)階段都涉及同步等待阻塞，極大降低了吞吐量）、數(shù)據(jù)不一致（參與者回復(fù)Yes/No后如果因?yàn)榫W(wǎng)絡(luò)原因沒有收到提交/中斷請求，此時(shí)它就不知道該如何操作了，導(dǎo)致集群數(shù)據(jù)不一致）……

2PC有些優(yōu)化手段：超時(shí)判斷機(jī)制，比如協(xié)調(diào)者發(fā)出事務(wù)請求后等待所有參與者反饋，若超過時(shí)間沒有搜集完畢所有回復(fù)則可以多播消息取消本次事務(wù)；互詢機(jī)制，參與者P回復(fù)yes后，等待協(xié)調(diào)者發(fā)起最終的commitabort，如果沒收到那么可以詢問其他參與者Q來決定自身下一步操作，避免一直阻塞（如果其他參與者全都是等待狀態(tài)，那么P也只能一直阻塞了）。所以2PC的阻塞問題是沒辦法徹底解決的。

當(dāng)然，如果網(wǎng)絡(luò)環(huán)境較好，該協(xié)議一般還是能很好的工作的，2PC廣泛應(yīng)用于關(guān)系數(shù)據(jù)庫的分布式事務(wù)處理，如mysql的內(nèi)部與外部XA都是基于2PC的，一般想要把多個(gè)操作打包未原子操作也可以用2PC。

-     3PC    -

3 Phase Commit，三階段提交，是二階段提交的改進(jìn)，系統(tǒng)也有兩個(gè)角色協(xié)調(diào)者和參與者，事務(wù)提交過程分為三階段：

1. 事務(wù)詢問（canCommit）
• 協(xié)調(diào)者向參與者發(fā)送一個(gè)包含事務(wù)內(nèi)容的詢問請求，詢問是否可以執(zhí)行事務(wù)并等待
• 參與者根據(jù)自己狀態(tài)判斷并回復(fù)yes、no
2. 執(zhí)行事務(wù)預(yù)提交（preCommit）
• 若協(xié)調(diào)者收到全是yes，就發(fā)送preCommit請求否則發(fā)布abort請求
• 參與者若收到preCommit則執(zhí)行事務(wù)操作并記錄undo和redo然后發(fā)送Ack，若收到abort或者超時(shí)則中斷事務(wù)
3. 執(zhí)行事務(wù)提交（doCommit）
• 協(xié)調(diào)者收到所有的Ack則發(fā)送doCommit請求，若收到了No或者超時(shí)則發(fā)送abort請求
• 參與者收到doCommit就執(zhí)行提交并發(fā)送ACk，否則執(zhí)行回滾并發(fā)送Ack
• 協(xié)調(diào)者收到Ack判斷是完成事務(wù)還是中斷事務(wù)

三階段相對于兩階段的改善就是把準(zhǔn)備階段一分為二，亦即多了一個(gè)canCommit階段，按我理解這樣就類似于TCP的三步握手，多了一次確認(rèn)，增大了事務(wù)執(zhí)行成功的概率。而且3PC的協(xié)調(diào)者即使出了故障，參與者也能繼續(xù)執(zhí)行事務(wù)所以解決了2PC的阻塞問題，但是也可能因此導(dǎo)致集群數(shù)據(jù)不一致。

-     Paxos    -

上面兩個(gè)協(xié)議的協(xié)調(diào)者都需要人為設(shè)置而無法自動(dòng)生成，是不完整的分布式協(xié)議，而Paxos 就是一個(gè)真正的完整的分布式算法。系統(tǒng)一共有幾個(gè)角色：Proposer（提出提案）、Acceptor（參與決策）、Learner（不參與提案，只負(fù)責(zé)接收已確定的提案，一般用于提高集群對外提供讀服務(wù)的能力），實(shí)踐中一個(gè)節(jié)點(diǎn)可以同時(shí)充當(dāng)多個(gè)角色。提案選定過程也大概分為2階段：

1. Prepare階段
• Proposer選擇一個(gè)提案編號(hào)M，向Acceptor某個(gè)超過半數(shù)的子集成員發(fā)送該編號(hào)的Prepare請求
• Acceptor收到M編號(hào)的請求時(shí)，若M大于該Acceptor已經(jīng)響應(yīng)的所有Prepare請求的編號(hào)中的最大編號(hào)N，那么他就將N反饋給Proposer，同時(shí)承諾不會(huì)再批準(zhǔn)任何編號(hào)小于M的提案
2. Accept階段
• 如果Proposer收到超過半數(shù)的Acceptor對于M的prepare請求的響應(yīng)，就發(fā)送一個(gè)針對[M,V]提案的Accept請求給Acceptor，其中V是收到的響應(yīng)編號(hào)中編號(hào)的最大的提案值，如果響應(yīng)中不包括任何提案值，那么他就是任意值
• Acceptor收到這個(gè)針對[M,V]的Accept請求只要改Acceptor尚未對大于M編號(hào)的提案做出過響應(yīng)，他就通過這個(gè)提案
3. Learn階段（本階段不屬于選定提案的過程）
• Proposer將通過的提案同步到所有的Learner
  
  

Paxos協(xié)議的容錯(cuò)性很好，只要有超過半數(shù)的節(jié)點(diǎn)可用，整個(gè)集群就可以自己進(jìn)行Leader選舉，也可以對外服務(wù)，通常用來保證一份數(shù)據(jù)的多個(gè)副本之間的一致性，適用于構(gòu)建一個(gè)分布式的一致性狀態(tài)機(jī)。

Google的分布式鎖服務(wù)Chubby就是用了Paxos協(xié)議，而開源的ZooKeeper使用的是Paxos的變種ZAB協(xié)議。

-     Raft    -

Raft協(xié)議對標(biāo)Paxos，容錯(cuò)性和性能都是一致的，但是Raft比Paxos更易理解和實(shí)施。系統(tǒng)分為幾種角色：Leader（發(fā)出提案）、Follower（參與決策）、Candidate（Leader選舉中的臨時(shí)角色）。

剛開始所有節(jié)點(diǎn)都是Follower狀態(tài)，然后進(jìn)行Leader選舉。成功后Leader接受所有客戶端的請求，然后把日志entry發(fā)送給所有Follower，當(dāng)收到過半的節(jié)點(diǎn)的回復(fù)（而不是全部節(jié)點(diǎn)）時(shí)就給客戶端返回成功并把commitIndex設(shè)置為該entry的index，所以是滿足最終一致性的。

Leader同時(shí)還會(huì)周期性地發(fā)送心跳給所有的Follower（會(huì)通過心跳同步提交的序號(hào)commitIndex），F(xiàn)ollower收到后就保持Follower狀態(tài)（并應(yīng)用commitIndex及其之前對應(yīng)的日志entry），如果Follower等待心跳超時(shí)了，則開始新的Leader選舉：首先把當(dāng)前term計(jì)數(shù)加1，自己成為Candidate，然后給自己投票并向其它結(jié)點(diǎn)發(fā)投票請求。直到以下三種情況：

• 它贏得選舉；
• 另一個(gè)節(jié)點(diǎn)成為Leader；
• 一段時(shí)間沒有節(jié)點(diǎn)成為Leader。

在選舉期間，Candidate可能收到來自其它自稱為Leader的寫請求，如果該Leader的term不小于Candidate的當(dāng)前term，那么Candidate承認(rèn)它是一個(gè)合法的Leader并回到Follower狀態(tài)，否則拒絕請求。

如果出現(xiàn)兩個(gè)Candidate得票一樣多，則它們都無法獲取超過半數(shù)投票，這種情況會(huì)持續(xù)到超時(shí)，然后進(jìn)行新一輪的選舉，這時(shí)同時(shí)的概率就很低了，那么首先發(fā)出投票請求的的Candidate就會(huì)得到大多數(shù)同意，成為Leader。

在Raft協(xié)議出來之前，Paxos是分布式領(lǐng)域的事實(shí)標(biāo)準(zhǔn)，但是Raft的出現(xiàn)打破了這一個(gè)現(xiàn)狀（raft作者也是這么想的，請看論文），Raft協(xié)議把Leader選舉、日志復(fù)制、安全性等功能分離并模塊化，使其更易理解和工程實(shí)現(xiàn)，將來發(fā)展怎樣我們拭目以待（挺看好）。

Raft協(xié)議目前被用于 cockrouchDB，TiKV等項(xiàng)目中，據(jù)我聽的一些報(bào)告來看，一些大廠自己造的分布式數(shù)據(jù)庫也在使用Raft協(xié)議。

-     Gossip    -

Gossip協(xié)議與上述所有協(xié)議最大的區(qū)別就是它是去中心化的，上面所有的協(xié)議都有一個(gè)類似于Leader的角色來統(tǒng)籌安排事務(wù)的響應(yīng)、提交與中斷，但是Gossip協(xié)議中就沒有Leader，每個(gè)節(jié)點(diǎn)都是平等的。

每個(gè)節(jié)點(diǎn)存放了一個(gè)key,value,version構(gòu)成的列表，每隔一定的時(shí)間，節(jié)點(diǎn)都會(huì)主動(dòng)挑選一個(gè)在線節(jié)點(diǎn)進(jìn)行上圖的過程（不在線的也會(huì)挑一個(gè)嘗試），兩個(gè)節(jié)點(diǎn)各自修改自己較為落后的數(shù)據(jù)，最終數(shù)據(jù)達(dá)成一致并且都較新。節(jié)點(diǎn)加入或退出都很容易。

去中心化的Gossip看起來很美好：沒有單點(diǎn)故障，看似無上限的對外服務(wù)能力……本來隨著Cassandra火了一把，但是現(xiàn)在Cassandra也被拋棄了，去中心化的架構(gòu)貌似難以真正應(yīng)用起來。歸根到底我覺得還是因?yàn)槿ブ行幕旧砉芾硖珡?fù)雜，節(jié)點(diǎn)之間溝通成本高，最終一致等待時(shí)間較長……往更高處看，一個(gè)企業(yè)（甚至整個(gè)社會(huì)）不也是需要中心化的領(lǐng)導(dǎo)（或者制度）來管理嗎，如果沒有領(lǐng)導(dǎo)（或者制度）管理，大家就是一盤散沙，難成大事啊。

事實(shí)上現(xiàn)代互聯(lián)網(wǎng)架構(gòu)只要把單點(diǎn)做得足夠強(qiáng)大，再加上若干個(gè)強(qiáng)一致的熱備，一般問題都不大。

-     NWR 機(jī)制    -

首先看看這三個(gè)字母在分布式系統(tǒng)中的含義：

N：有多少份數(shù)據(jù)副本；
W：一次成功的寫操作至少有w份數(shù)據(jù)寫入成功；
R：一次成功的讀操作至少有R份數(shù)據(jù)讀取成功。

NWR值的不同組合會(huì)產(chǎn)生不同的一致性效果，當(dāng)W+R>N的時(shí)候，讀取操作和寫入操作成功的數(shù)據(jù)一定會(huì)有交集，這樣就可以保證一定能夠讀取到最新版本的更新數(shù)據(jù)，數(shù)據(jù)的強(qiáng)一致性得到了保證，如果R+W<=N，則無法保證數(shù)據(jù)的強(qiáng)一致性，因?yàn)槌晒懞统晒ψx集合可能不存在交集，這樣讀操作無法讀取到最新的更新數(shù)值，也就無法保證數(shù)據(jù)的強(qiáng)一致性。

版本的新舊需要版本控制算法來判別，比如向量時(shí)鐘。

當(dāng)然R或者W不能太大，因?yàn)樵酱笮枰僮鞯母北驹蕉啵臅r(shí)越長。

-     Quorum 機(jī)制    -

Quorom機(jī)制，是一種分布式系統(tǒng)中常用的，用來保證數(shù)據(jù)冗余和最終一致性的投票算法，主要思想來源于鴿巢原理。在有冗余數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)當(dāng)中，冗余數(shù)據(jù)對象會(huì)在不同的機(jī)器之間存放多份拷貝。但是同一時(shí)刻一個(gè)數(shù)據(jù)對象的多份拷貝只能用于讀或者用于寫。

分布式系統(tǒng)中的每一份數(shù)據(jù)拷貝對象都被賦予一票。每一個(gè)操作必須要獲得最小的讀票數(shù)（Vr）或者最小的寫票數(shù)(Vw）才能讀或者寫。如果一個(gè)系統(tǒng)有V票（意味著一個(gè)數(shù)據(jù)對象有V份冗余拷貝），那么這最小讀寫票必須滿足：

• Vr + Vw > V
• Vw > V/2

第一條規(guī)則保證了一個(gè)數(shù)據(jù)不會(huì)被同時(shí)讀寫。當(dāng)一個(gè)寫操作請求過來的時(shí)候，它必須要獲得Vw個(gè)冗余拷貝的許可。而剩下的數(shù)量是V-Vw 不夠Vr，因此不能再有讀請求過來了。同理，當(dāng)讀請求已經(jīng)獲得了Vr個(gè)冗余拷貝的許可時(shí)，寫請求就無法獲得許可了。

第二條規(guī)則保證了數(shù)據(jù)的串行化修改。一份數(shù)據(jù)的冗余拷貝不可能同時(shí)被兩個(gè)寫請求修改。

Quorum機(jī)制其實(shí)就是NWR機(jī)制。

-     Lease 機(jī)制    -

master給各個(gè)slave分配不同的數(shù)據(jù)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都具有有效時(shí)間比如1小時(shí)，在lease時(shí)間內(nèi)，客戶端可以直接向slave請求數(shù)據(jù)，如果超過時(shí)間客戶端就去master請求數(shù)據(jù)。一般而言，slave可以定時(shí)主動(dòng)向master要求續(xù)租并更新數(shù)據(jù)，master在數(shù)據(jù)發(fā)生變化時(shí)也可以主動(dòng)通知slave，不同方式的選擇也在于可用性與一致性之間進(jìn)行權(quán)衡。

租約機(jī)制也可以解決主備之間網(wǎng)絡(luò)不通導(dǎo)致的雙主腦裂問題，亦即：主備之間本來心跳連線的，但是突然之間網(wǎng)絡(luò)不通或者暫停又恢復(fù)了或者太繁忙無法回復(fù)，這時(shí)備機(jī)開始接管服務(wù)，但是主機(jī)依然存活能對外服務(wù)，這是就發(fā)生爭奪與分區(qū)，但是引入lease的話，老主機(jī)頒發(fā)給具體server的lease必然較舊，請求就失效了，老主機(jī)自動(dòng)退出對外服務(wù)，備機(jī)完全接管服務(wù)。

參考：

https://en.wikipedia.org/wiki/Two-phase_commit_protocol
https://en.wikipedia.org/wiki/Three-phase_commit_protocol
https://en.wikipedia.org/wiki/Paxos_(computer_science)
https://raft.github.io/
https://en.wikipedia.org/wiki/Raft_(computer_science)
https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
http://www.infoq.com/cn/articles/raft-paper
https://en.wikipedia.org/wiki/Gossip_protocol
從Paxos到ZooKeeper
分布式j(luò)ava應(yīng)用
大數(shù)據(jù)日知錄
http://m635674608.iteye.com/blog/2343038

作者：mageek

來源：網(wǎng)絡(luò)