摘要：收到所有參與者回應(yīng)后，完成事務(wù)。不管是還是，都是通過節(jié)點間的交換消息去達到一致的狀態(tài)，這也是分布式系統(tǒng)的常用做法。從業(yè)期間，負責過訂閱系統(tǒng)制作云服務(wù)開源平臺分布式任務(wù)調(diào)度系統(tǒng)等產(chǎn)品的設(shè)計研發(fā)工作。

接著上一篇的內(nèi)容，詳細介紹一些主流數(shù)據(jù)庫在分布式場景下用到的算法和思想，主要提及數(shù)據(jù)一致性相關(guān)的一些策略，并分析其利弊和典型應(yīng)用場景。

對于數(shù)據(jù)庫來說，可能關(guān)心的最多的就是數(shù)據(jù)的一致性了，由此衍生出了不同場景下的算法和策略。
在上一篇末尾提及了兩種集群結(jié)構(gòu)：中心化和去中心化。

一種是中心化的，由中心節(jié)點去存儲集群信息并管理集群狀態(tài)，其它節(jié)點只需響應(yīng)數(shù)據(jù)請求，而無需知道集群中其它節(jié)點的情況。
這種模式的核心便是選舉或者指定一個節(jié)點作為集群的管理者，由管理者去協(xié)調(diào)跨節(jié)點的操作、備份數(shù)據(jù)和處理故障等。

一般的，對于跨節(jié)點的操作，為了保證事務(wù)的原子性，提出了兩步提交協(xié)議或三步提交協(xié)議，下面分別介紹。

兩步提交協(xié)議，顧名思義，就是將數(shù)據(jù)的提交分為兩步：投票和決策。

首先，在第一階段，

中心節(jié)點（在這里我們稱之為協(xié)調(diào)者）發(fā)起事務(wù)操作請求，包含事務(wù)內(nèi)容，詢問是否可以執(zhí)行提交操作并等待響應(yīng)；

其它節(jié)點（在這里稱之為參與者）執(zhí)行事務(wù)操作并記錄undo/redo log，最后返回是否同意提交。

然后，在第二階段，協(xié)調(diào)者根據(jù)所有參與者的投票結(jié)果，如果是都同意則通知所有參與者提交事務(wù)，否則回滾事務(wù)。
收到所有參與者回應(yīng)后，完成事務(wù)。

接著，我們考慮下兩步提交過程中如果發(fā)生異常，會出現(xiàn)什么樣的情況，會不會影響結(jié)果的一致性，并嘗試解決。

在第一階段時，有節(jié)點宕機

有參與者宕機，此時協(xié)調(diào)者接收到錯誤響應(yīng)，可認為是失敗，將中斷事務(wù)。

協(xié)調(diào)者宕機，此時參與者等待協(xié)調(diào)者的操作通知，事務(wù)會阻塞直到協(xié)調(diào)者恢復(fù)。
對于此種情況，解決的辦法是可以設(shè)置多個協(xié)調(diào)者，一主多從，宕機后指定一臺從作為新的主。

參與者也需要記錄事務(wù)的投票狀態(tài)，以便新的協(xié)調(diào)者重新找回事務(wù)狀態(tài)。

參與者和協(xié)調(diào)者都宕機了，如上一條，新的協(xié)調(diào)者將會獲取不到參與者的事務(wù)狀態(tài)（該參與者的狀態(tài)只有自己和原協(xié)調(diào)者知道），會一直阻塞地等待所有參與者恢復(fù)。
其它參與者也會處于兩階段之間，直到宕機的參與者恢復(fù)。

在第二階段，有節(jié)點宕機

有參與者宕機，此時未宕機的參與者會正常地提交／回滾事務(wù)，而由于并不知道宕機的時機，所以可能會導(dǎo)致數(shù)據(jù)的不一致。

協(xié)調(diào)者宕機，若是在發(fā)送通知前，那么參與者將阻塞地等待協(xié)調(diào)者恢復(fù)?？赏ㄟ^設(shè)置協(xié)調(diào)者的備份來解決，要求參與者記錄事務(wù)狀態(tài)。若是在發(fā)送通知后，不影響可忽略。

參與者與協(xié)調(diào)者都宕機了，如上兩條，可能會導(dǎo)致數(shù)據(jù)的不一致或阻塞。

注意，以上的宕機如果替換為網(wǎng)絡(luò)分區(qū)，也會是同樣的情況。

可以看出，2pc的優(yōu)點是簡單直接，缺點是：

當有故障發(fā)生會阻塞事務(wù)的執(zhí)行，進而影響到相關(guān)資源的釋放；

協(xié)調(diào)者的單點問題；

當二階段有參與者宕機或者網(wǎng)絡(luò)分區(qū)時，可能會導(dǎo)致數(shù)據(jù)不一致。

針對這些缺陷，出現(xiàn)了3pc。

三步提交協(xié)議，改進了2pc的一些缺陷，它增加了一個詢問是否可提交階段。如圖所示：

第一階段時，協(xié)調(diào)者詢問各參與者是否可以執(zhí)行事務(wù)提交，包含事務(wù)內(nèi)容，并等待參與者的響應(yīng)。
參與者收到請求后，如果認為可以成功執(zhí)行事務(wù)，則返回同意，否則中止事務(wù)。

第二階段時，協(xié)調(diào)者根據(jù)第一階段參與者的返回消息，決定是準備提交或是中止事務(wù)。如果都是同意，那么發(fā)送預(yù)提交請求。
參與者收到請求后，會執(zhí)行事務(wù)操作，并記錄undo/redo log, 最后返回提交／中止事務(wù)。

第三階段時，協(xié)調(diào)者根據(jù)第二階段的響應(yīng)，決定通知參與者提交／回滾事務(wù)，收到響應(yīng)后完成事務(wù)。

3pc相比于2pc的優(yōu)點在于：

在協(xié)調(diào)者和參與者端都添加了超時機制，其中：參與者超時未應(yīng)答均認為是失??；協(xié)調(diào)者在第二階段超時未發(fā)送請求視為失敗，而第三階段超時未發(fā)送請求視為成功，參與者在經(jīng)過了指定超時時間后提交事務(wù)。這樣便具備了一定的容錯性。
不僅如此，這樣還可以有效減少阻塞時間。

提供了協(xié)調(diào)者的主備方案，避免了單點問題。

缺點：

第二階段時，參與者在接收到預(yù)提交請求后發(fā)生網(wǎng)絡(luò)分區(qū)，此參與者在超時后提交事務(wù)，而協(xié)調(diào)者在超時后認為事務(wù)失敗并通知其它參與者回滾事務(wù)，最終導(dǎo)致數(shù)據(jù)不一致。若發(fā)生此情況，只能通過上層去協(xié)調(diào)解決這個問題，如上一篇提到的兩種解決方案。（2pc也有類似缺陷）

比2pc多了一個階段，意味著同等情況下，耗時要多一點。

另一種則是去中心化的，由節(jié)點之間互相通信去協(xié)商一致。比較有名的算法如Paxos。

Paxos算法在分布式領(lǐng)域具有非常重要的地位，Google Chubby的作者Mike Burrows曾經(jīng)說過，這個世界上只有一種一致性算法，那就是Paxos，其它的都是殘次品。

不過這個算法實在是難理解，難實現(xiàn)；以后有機會我會專門總結(jié)一篇文章分享下，有興趣的道友可以先去看看《Paxos Made Simple》，寫得很不錯。

此外，考慮到集群中的節(jié)點數(shù)量并不是一成不變的，所以如果使用的是一般的Hash算法，那么在集群新增節(jié)點或刪除節(jié)點時，會導(dǎo)致節(jié)點間大量數(shù)據(jù)的遷移，進而影響可用性，故而提出了一致性Hash算法以減少數(shù)據(jù)的遷移量。

一般的Hash算法，如對key取模然后分散到不同的節(jié)點中：假設(shè)有3個節(jié)點，共有key分別為1～7的數(shù)據(jù)，分配結(jié)果如下圖

現(xiàn)在，如果新增一個節(jié)點，那么分配結(jié)果變?yōu)椋?

可以發(fā)現(xiàn)大部分的節(jié)點都被重新分配到了不同的節(jié)點上，即遷移數(shù)據(jù)是O(n)復(fù)雜度（n為數(shù)據(jù)總量），無法平滑地擴縮容。
接下來再來看下一致性Hash，它的分配方式是對key和節(jié)點做相同的Hash運算，然后將key分配到剛好大于或等于它Hash值的節(jié)點上（若節(jié)點都比它Hash值小，則分配到最小的節(jié)點上，即形成一個“環(huán)”）；

還是上面的那個例子，對key和節(jié)點都做對7取模的Hash計算，然后分配。先是有三個節(jié)點：

新增一個節(jié)點：

可以看出，增加一個節(jié)點后只有少量數(shù)據(jù)從5節(jié)點移動到4節(jié)點，極大的減少了數(shù)據(jù)遷移量。
但是，一致性Hash也有缺陷：查找效率低。一般需要逐個去比較Hash值直到找到剛好大于等于的節(jié)點，故查找復(fù)雜度為O(k)（k為節(jié)點數(shù)量）。
可以通過在節(jié)點中冗余一份節(jié)點表來加快查找。

保證一致性，要么是通過共享存儲，要么是通過消息協(xié)調(diào)。
數(shù)據(jù)庫本身就是共享存儲。
不管是2pc、3pc還是paxos，都是通過節(jié)點間的交換消息去達到一致的狀態(tài)，這也是分布式系統(tǒng)的常用做法。
了解了這些策略的原理后，不管是用Zookeeper、RabbitMQ、Redis或其它消息組件（甚至是基于socket通信）去實現(xiàn)它，都是水到渠成的事情了。

超時是個好設(shè)計，因為它是不需詢問便可以察覺錯誤的方式（畢竟沒有錯誤就不會超時了），很多設(shè)計中都會將超時作為一種信號，并嘗試容錯／修復(fù)等操作。

在運行過程的一些錯誤并不能通過底層的策略完全規(guī)避，需要根據(jù)具體業(yè)務(wù)在上層做相應(yīng)的容錯措施。

冗余是個好設(shè)計，幾乎在各種組件的設(shè)計都能見到，通過犧牲一點空間較大地提高檢索效率。

有機會的話，之后的篇章我會收集并比較幾種典型分布式組件的具體實現(xiàn)，對這些組件有個更加直觀和深入的理解，以便充實和改進自己的知識結(jié)構(gòu)并分享出來。

最后為方便查詢，整理了下往期文章到github中：https://github.com/dengyuankai272/blog

作者信息
本文系力譜宿云LeapCloud旗下MaxLeap團隊_基礎(chǔ)服務(wù)組成員：呂舜 【原創(chuàng)】
力譜宿云LeapCloud 首發(fā)：https://blog.maxleap.cn/archi...
呂舜，主攻Java，對Python、數(shù)據(jù)分析也有關(guān)注。從業(yè)期間，負責過訂閱系統(tǒng)、App制作云服務(wù)、開源BaaS平臺、分布式任務(wù)調(diào)度系統(tǒng)等產(chǎn)品的設(shè)計研發(fā)工作?，F(xiàn)任MaxLeap基礎(chǔ)服務(wù)與架構(gòu)成員，負責云服務(wù)系統(tǒng)相關(guān)的設(shè)計與開發(fā)。

相關(guān)文章
微服務(wù)實戰(zhàn)：從架構(gòu)到發(fā)布（一）
微服務(wù)實戰(zhàn)：從架構(gòu)到發(fā)布（二）
移動云平臺的基礎(chǔ)架構(gòu)之旅（一）：云應(yīng)用
從應(yīng)用到平臺 – 云服務(wù)架構(gòu)的演進過程

作者往期佳作
RabbitMQ在分布式系統(tǒng)的應(yīng)用
關(guān)于分布式系統(tǒng)的思考

歡迎掃以下二維碼，關(guān)注我們的微信訂閱號：