常見分佈式協議和算法的說明和對比

開發分佈式系統最關鍵的就是根據場景特點，選擇合適的算法，在一致性和可用性之間妥協折中，而妥協折中的關鍵就在於能否理解各算法的特點。

分佈式一致性的背景

一致性的分類

我們講分佈式系統的一致性，一般來說，有如下幾個分類：

強一致性。對一致性要求最高的，是強一致的，保證寫操作完成後，任何後續訪問都能讀到更新後的值。。但是性能較弱，在互聯網系統裏面用的較少，但是在金融領域使用的較多。因爲是同步的，因此性能會比較低。
弱一致性。寫操作完成後，系統不能保證後續的訪問都能讀到更新後的值。
最終一致性。是弱一致性的一個特定形式，如果對某個對象沒有新的寫操作了，最終所有後續訪問都能讀到相同的最近更新的值，但是是在最終某個時間點才能保證。弱一致性（最終一致性）都是異步的，因此性能會比較好。

一般而言，在需要系統狀態的一致性時，你可以考慮採用二階段提交協議、TCC。在需要數據訪問是的強一致性時，你可考慮 Raft 算法。在可用性優先的系統，你可以採用 Gossip 協議來實現最終一致性，並實現 Quorum NWR 來提供強一致性。

如何理解分佈式一致性

設計分佈式系統的兩大初衷：橫向擴展（scalability）和高可用性（availability），橫向擴展的目的也是爲了解決單點問題從而保障可用性，因此分佈式系統的核心訴求也就是可用性，爲了保證可用性，一個分佈式系統通常由多個節點組成，而這些節點各自維護一份數據，因此我們需要能夠保證每個節點上的數據都是相同的，也就是要保證一致性，這就是我們所說的分佈式一致性，他通過給定的一系列操作，在協議（共識算法）的保障下，試圖使得它們對處理結果達成某種程度的一致。

分佈式系統的核心問題

前面說到，分佈式一致性，是通過給定的一系列操作，在協議（共識算法）的保障下，試圖使得它們對處理結果達成某種程度的一致。這裏，也就是整個分佈式系統的核心問題，怎麼保證多個節點間的數據是一致的，這就需要我們對分佈式協議（共識算法）要能夠有比較深刻的理解，然後才能很好的解決分佈式數據的一致性，掌握分佈式協議（共識算法）也是你面試架構師、技術專家等高端崗位時的敲門磚。

拜占庭容錯和非拜占庭容錯

拜占庭錯誤是一個錯誤模型，描述了一個完全不可信的場景，除了存在故障行爲，還存在惡意行爲。拜占庭容錯（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭錯誤了。拜占庭容錯是分佈式領域最複雜的容錯模型，是你必須要了解的。在一個完全不可信的環境中（比如有人作惡），如果需要達成共識，那麼我們就必須考慮拜占庭容錯算法，常用的拜占庭容錯算法有 POW 算法、PBFT 算法，它們在區塊鏈中應用廣泛。從概率角度，PBFT 系列算法是確定的，一旦達成共識就不可逆轉；而 PoW 系列算法則是不確定的，隨着時間推移，被推翻的概率越來越小。

而非拜占庭容錯，又叫故障容錯（Crash Fault Tolerance，CFT），解決的是分佈式系統中存在故障，但不存在惡意節點的共識問題。實際上，這種故障是非常場景的，比如進程奔潰、服務器硬件故障、網絡中斷、響應延遲等等。針對非拜占庭錯誤的解決方案，業界一般採用 Paxos、Raft 及其各種變種的協議。

共識 vs 一致性

共識算法解決的是對某個提案（Proposal）讓大家都達成一致意見的過程，而這個提案可以認爲任何需要達成一致的信息都是一個提案，如多個事件發生的順序、某個鍵對應的值等等。在實踐中，一致性的結果還需要客戶端的支持，比如通過訪問足夠多個服務節點來驗證確保獲取共識後結果。

但是由於分佈式系統會存在各種非拜占庭容錯，因此要達成共識就比較困難，需要一些共識算法來解決。這裏需要注意，共識（Consensus）和一致性（Consistency）是兩個完全不同的概念。共識是指各節點就指定值（Value）達成共識，而且達成共識後的值，就不再改變了。一致性是指寫操作完成後，能否從各節點上讀到最新寫入的數據，如果立即能讀到，就是強一致性，如果最終能讀到，就是最終一致性。

提到共識算法，Paxos 是一個必須要提及的話題，而且 ZAB 協議、Raft 算法都可以看作是 Paxos 變種，Paxos 和 Raft 是共識算法。所以，你需要了解 Paxos 算法。但因爲 Paxos 算法的可理解性和可編程性痛點突出，所以在實際場景中，最常的共識算法是 Raft，我們可以基於 Raft 實現強一致性系統，Raft 是需要徹底掌握的。

8 條荒謬的分佈式假設

Fallacies of Distributed Computing 是英文維基百科上的一篇文章，講的是剛剛進入分佈式計算領域的程序員常會有的 8 條假定，隨着時間的推移，每一條都會被證明是錯誤的，也都會導致嚴重的問題，以及痛苦的學習體驗：

網絡是穩定的。
網絡傳輸的延遲是零。
網絡的帶寬是無窮大。
網絡是安全的。
網絡的拓撲不會改變。
只有一個系統管理員。
傳輸數據的成本爲零。
整個網絡是同構的。

爲什麼我們要深刻地認識這 8 個錯誤？是因爲，這要我們清楚地認識到，在分佈式系統中錯誤是不可能避免的，我們能做的不是避免錯誤，而是要把錯誤的處理當成功能寫在代碼中。這 8 個需要避免的錯誤不僅對於中間件和底層系統開發者及架構師是重要的知識，而且對於網絡應用程序開發者也同樣重要。分佈式系統的其他部分，如容錯、備份、分片、微服務等也許可以對應用程序開發者部分透明，但這 8 點則是應用程序開發者也必須知道的。

常見分佈式算法的對比

從拜占庭容錯、一致性、性能和可用性四個緯度來分析如下（來自極客時間 - 韓健 - 分佈式協議與算法實戰）：

一般而言，在可信環境（比如企業內網）中，系統具有故障容錯能力就可以了，常見的算法有二階段提交協議（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 協議、Raft 算法、Gossip 協議、Quorum NWR 算法。而在不可信的環境（比如有人做惡）中，這時系統需要具備拜占庭容錯能力，常見的拜占庭容錯算法有 POW 算法、PBFT 算法。

採用 Gossip 協議實現的最終一致性系統的可用性是最高的，因爲哪怕只有一個節點，集羣還能在運行並提供服務。其次是 Paxos 算法、ZAB 協議、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它們能容忍一定數節點故障。最後是二階段提交協議、TCC，只有當所有節點都在運行時，才能工作，可用性最低。

採用 Gossip 協議的 AP 型分佈式系統，具備水平擴展能力，讀寫性能是最高的。其次是 Paxos 算法、ZAB 協議、Raft 算法，因爲它們都是領導者模型，寫性能受限於領導者，讀性能取決於一致性實現。最後是二階段提交協議和 TCC，因爲在實現事務時，需要預留和鎖定資源，性能相對低。

2PC【強一致性】

兩階段提交（2PC，Two-phase Commit Protocol）是非常經典的強一致性協議，在各種事務和一致性的解決方案中，都能看到兩階段提交的應用，二階段提交協議，不僅僅是協議，也是一種非常經典的思想。2PC 的流程就是第一階段做投票，第二階段做決定的一個算法。

二階段提交在達成提交操作共識的算法中應用廣泛，比如 XA 協議、TCC、Paxos、Raft 等。 Paxos、Raft 等強一致性算法，也採用了二階段提交操作，在 “提交請求階段”，只要大多數節點確認就可以，而具有 ACID 特性的事務，則要求全部節點確認可以。所以可以將具有 ACID 特性的操作，理解爲最強的一致性。

三階段提交協議（3PC，Three-phase_commit_protocol）是在 2PC 之上擴展的提交協議，主要是爲了解決兩階段提交協議的阻塞問題，從原來的兩個階段擴展爲三個階段，增加了超時機制。但目前兩階段提交、三階段提交存在如下的侷限性，並不適合在微服務架構體系下使用：

所有的操作必須是事務性資源（比如數據庫、消息隊列），存在使用侷限性
由於是強一致性，資源需要在事務內部等待，性能影響較大，吞吐率不高，不適合高併發與高性能的業務場景；

Paxos【強一致性】

Paxos 算法基本上來說是個民主選舉的算法——大多數的決定會成個整個集羣的統一決定。任何一個點都可以提出要修改某個數據的提案，是否通過這個提案取決於這個集羣中是否有超過半數的結點同意（所以 Paxos 算法需要集羣中的結點是單數）。蘭伯特提出的 Paxos 算法包含 2 個部分：

一個是 Basic Paxos 算法，描述的是多節點之間如何就某個值（提案 Value）達成共識；
另一個是 Multi-Paxos 思想，描述的是執行多個 Basic Paxos 實例就一系列值達成共識。Basic Paxos 是 Multi-Paxos 思想的核心。

Raft【強一致性】

Raft 算法是 Paxos 算法的一種簡化實現，其實 Raft 不是一致性算法而是共識算法，是一個 Multi-Paxos 算法，實現的是如何就一系列值達成共識。Raft 算法是在蘭伯特 Multi-Paxos 思想的基礎上，做了一些簡化和限制，比如增加了日誌必須是連續的，只支持領導者、跟隨者和候選人三種狀態，在理解和算法實現上都相對容易許多。

ZAB【最終一致性】

ZAB 協議和 ZooKeeper 代碼耦合在一起了，無法單獨使用 ZAB 協議，所以一般而言，只需要理解 ZAB 協議的架構和基礎原理就可以了。

TCC【最終一致性】

TCC 是一個分佈式事務的處理模型，將事務過程拆分爲 Try、Confirm、Cancel 三個步驟，在保證強一致性的同時，最大限度提高系統的可伸縮性與可用性，又被稱補償事務。它的核心思想是針對每個操作都要註冊一個與其對應的確認操作和補償操作（也就是撤銷操作）

二階段提交協議實現的是數據層面的事務，比如 XA 規範採用的就是二階段提交協議；TCC 實現的是業務層面的事務，TCC 可以理解爲是一個業務層面的協議，可以當做爲一個編程模型來看待，因此這個的應用還是非常廣泛的。，TCC 的 3 個操作是需要在業務代碼中編碼實現的，爲了實現一致性，確認操作和補償操作必須是等冪的，因爲這 2 個操作可能會失敗重試。

TCC 不依賴於數據庫的事務，而是在業務中實現了分佈式事務，這樣能減輕數據庫的壓力，但對業務代碼的入侵性也更強，實現的複雜度也更高。所以，推薦在需要分佈式事務能力時，優先考慮現成的事務型數據庫（比如 MySQL XA），當現有的事務型數據庫不能滿足業務的需求時，再考慮基於 TCC 實現分佈式事務。

Gossip【最終一致性】

Gossip 協議利用一種隨機、帶有傳染性的方式，將信息傳播到整個網絡中，並在一定時間內，使得系統內的所有節點數據一致。掌握這個協議不僅能很好地理解這種最常用的，實現最終一致性的算法，也能在後續工作中得心應手地實現數據的最終一致性。

Gossip 主要通過三個步驟：直接郵寄（Direct Mail）、反熵（Anti-entropy）和謠言傳播（Rumor mongering）來實現最終一致性。實現數據副本的最終一致性時，一般而言，直接郵寄的方式是一定要實現的。在節點都是已知的情況下，一般採用反熵修復數據副本的一致性。當集羣節點是變化的，或者集羣節點數比較多時，這時要採用謠言傳播的方式來實現最終一致。

Quorum NWR【最終一致性】

Quorum NWR 算法非常實用，能有效彌補 AP 型系統缺乏強一致性的痛點，給業務提供了按需選擇一致性級別的靈活度。實際應用中，一般的 AP 型分佈式系統中（比如 Dynamo、Cassandra、InfluxDB 企業版的 DATA 節點集羣）都會實現 Quorum NWR 的功能。掌握 Quorum NWR，不僅是掌握一種常用的實現一致性的方法，同時可以根據業務的特點來靈活地指定一致性級別。

N、W、R 值的不同組合，會產生不同的一致性效果：

當 W + R > N 的時候，對於客戶端來講，整個系統能保證強一致性，一定能返回更新後的那份數據。
當 W + R <= N 的時候，對於客戶端來講，整個系統只能保證最終一致性，可能會返回舊數據。

如何設置 N、W、R 值，取決於我們想優化哪方面的性能。比如，N 決定了副本的冗餘備份能力；如果設置 W = N，讀性能比較好；如果設置 R = N，寫性能比較好；如果設置 W = (N + 1) / 2、R = (N + 1) / 2，容錯能力比較好，能容忍少數節點（也就是 (N - 1) / 2）的故障。

POW【拜占庭容錯】

區塊鏈中有此應用

PBFT【拜占庭容錯】