常見分布式協定和算法的說明和對比

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

分布式一緻性的背景

一緻性的分類

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

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

一般而言，在需要系統狀态的一緻性時，你可以考慮采用二階段送出協定、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【拜占庭容錯】

區塊鍊中有此應用