摘要：收到所有參與者回應后，完成事務。不管是還是，都是通過節點間的交換消息去達到一致的狀態，這也是分布式系統的常用做法。從業期間，負責過訂閱系統制作云服務開源平臺分布式任務調度系統等產品的設計研發工作。

接著上一篇的內容，詳細介紹一些主流數據庫在分布式場景下用到的算法和思想，主要提及數據一致性相關的一些策略，并分析其利弊和典型應用場景。

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

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

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

兩步提交協議，顧名思義，就是將數據的提交分為兩步：投票和決策。

首先，在第一階段，

中心節點（在這里我們稱之為協調者）發起事務操作請求，包含事務內容，詢問是否可以執行提交操作并等待響應；

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

然后，在第二階段，協調者根據所有參與者的投票結果，如果是都同意則通知所有參與者提交事務，否則回滾事務。
收到所有參與者回應后，完成事務。

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

在第一階段時，有節點宕機

有參與者宕機，此時協調者接收到錯誤響應，可認為是失敗，將中斷事務。

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

參與者也需要記錄事務的投票狀態，以便新的協調者重新找回事務狀態。

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

在第二階段，有節點宕機

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

協調者宕機，若是在發送通知前，那么參與者將阻塞地等待協調者恢復。可通過設置協調者的備份來解決，要求參與者記錄事務狀態。若是在發送通知后，不影響可忽略。

參與者與協調者都宕機了，如上兩條，可能會導致數據的不一致或阻塞。

注意，以上的宕機如果替換為網絡分區，也會是同樣的情況。

可以看出，2pc的優點是簡單直接，缺點是：

當有故障發生會阻塞事務的執行，進而影響到相關資源的釋放；

協調者的單點問題；

當二階段有參與者宕機或者網絡分區時，可能會導致數據不一致。

針對這些缺陷，出現了3pc。

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

第一階段時，協調者詢問各參與者是否可以執行事務提交，包含事務內容，并等待參與者的響應。
參與者收到請求后，如果認為可以成功執行事務，則返回同意，否則中止事務。

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

第三階段時，協調者根據第二階段的響應，決定通知參與者提交／回滾事務，收到響應后完成事務。

3pc相比于2pc的優點在于：

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

提供了協調者的主備方案，避免了單點問題。

缺點：

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

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

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

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

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

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

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

現在，如果新增一個節點，那么分配結果變為：

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

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

新增一個節點：

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

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

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

在運行過程的一些錯誤并不能通過底層的策略完全規避，需要根據具體業務在上層做相應的容錯措施。

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

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

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

作者信息
本文系力譜宿云LeapCloud旗下MaxLeap團隊_基礎服務組成員：呂舜 【原創】
力譜宿云LeapCloud 首發：https://blog.maxleap.cn/archi...
呂舜，主攻Java，對Python、數據分析也有關注。從業期間，負責過訂閱系統、App制作云服務、開源BaaS平臺、分布式任務調度系統等產品的設計研發工作。現任MaxLeap基礎服務與架構成員，負責云服務系統相關的設計與開發。

相關文章
微服務實戰：從架構到發布（一）
微服務實戰：從架構到發布（二）
移動云平臺的基礎架構之旅（一）：云應用
從應用到平臺 – 云服務架構的演進過程

作者往期佳作
RabbitMQ在分布式系統的應用
關于分布式系統的思考

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