常見分布式協(xié)議和算法的說明和對比
開發(fā)分布式系統(tǒng)最關鍵的就是根據(jù)場景特點，選擇合適的算法，在一致性和可用性之間妥協(xié)折中，而妥協(xié)折中的關鍵就在于能否理解各算法的特點。
分布式一致性的背景
一致性的分類
我們講分布式系統(tǒng)的一致性，一般來說，有如下幾個分類：
- 強一致性。對一致性要求最高的，是強一致的，保證寫操作完成后，任何后續(xù)訪問都能讀到更新后的值。。但是性能較弱，在互聯(lián)網系統(tǒng)里面用的較少，但是在金融領域使用的較多。因為是同步的，因此性能會比較低。
- 弱一致性。寫操作完成后，系統(tǒng)不能保證后續(xù)的訪問都能讀到更新后的值。
- 最終一致性。是弱一致性的一個特定形式，如果對某個對象沒有新的寫操作了，最終所有后續(xù)訪問都能讀到相同的最近更新的值，但是是在最終某個時間點才能保證。弱一致性（最終一致性）都是異步的，因此性能會比較好。
一般而言，在需要系統(tǒng)狀態(tài)的一致性時，你可以考慮采用二階段提交協(xié)議、TCC。在需要數(shù)據(jù)訪問是的強一致性時，你可考慮 Raft 算法。在可用性優(yōu)先的系統(tǒng)，你可以采用 Gossip 協(xié)議來實現(xiàn)最終一致性，并實現(xiàn) Quorum NWR 來提供強一致性。
如何理解分布式一致性
設計分布式系統(tǒng)的兩大初衷：橫向擴展（scalability）和高可用性（availability），橫向擴展的目的也是為了解決單點問題從而保障可用性，因此分布式系統(tǒng)的核心訴求也就是可用性，為了保證可用性，一個分布式系統(tǒng)通常由多個節(jié)點組成，而這些節(jié)點各自維護一份數(shù)據(jù)，因此我們需要能夠保證每個節(jié)點上的數(shù)據(jù)都是相同的，也就是要保證一致性，這就是我們所說的分布式一致性，他通過給定的一系列操作，在協(xié)議（共識算法）的保障下，試圖使得它們對處理結果達成某種程度的一致。
分布式系統(tǒng)的核心問題
前面說到，分布式一致性，是通過給定的一系列操作，在協(xié)議（共識算法）的保障下，試圖使得它們對處理結果達成某種程度的一致。這里，也就是整個分布式系統(tǒng)的核心問題，怎么保證多個節(jié)點間的數(shù)據(jù)是一致的，這就需要我們對分布式協(xié)議（共識算法）要能夠有比較深刻的理解，然后才能很好的解決分布式數(shù)據(jù)的一致性，掌握分布式協(xié)議（共識算法）也是你面試架構師、技術專家等高端崗位時的敲門磚。
拜占庭容錯 和 非拜占庭容錯
拜占庭錯誤是一個錯誤模型，描述了一個完全不可信的場景，除了存在故障行為，還存在惡意行為。拜占庭容錯（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭錯誤了。拜占庭容錯是分布式領域最復雜的容錯模型，是你必須要了解的。在一個完全不可信的環(huán)境中（比如有人作惡），如果需要達成共識，那么我們就必須考慮拜占庭容錯算法，常用的拜占庭容錯算法有 POW 算法、PBFT 算法，它們在區(qū)塊鏈中應用廣泛。從概率角度，PBFT 系列算法是確定的，一旦達成共識就不可逆轉；而 PoW 系列算法則是不確定的，隨著時間推移，被推翻的概率越來越小。
而非拜占庭容錯，又叫故障容錯（Crash Fault Tolerance，CFT），解決的是分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點的共識問題。實際上，這種故障是非常場景的，比如進程奔潰、服務器硬件故障、網絡中斷、響應延遲等等。針對非拜占庭錯誤的解決方案，業(yè)界一般采用 Paxos、Raft 及其各種變種的協(xié)議。
共識 vs 一致性
共識算法解決的是對某個提案（Proposal）讓大家都達成一致意見的過程，而這個提案可以認為任何需要達成一致的信息都是一個提案，如多個事件發(fā)生的順序、某個鍵對應的值等等。在實踐中，一致性的結果還需要客戶端的支持，比如通過訪問足夠多個服務節(jié)點來驗證確保獲取共識后結果。
但是由于分布式系統(tǒng)會存在各種非拜占庭容錯，因此要達成共識就比較困難，需要一些共識算法來解決。這里需要注意，共識（Consensus）和一致性（Consistency）是兩個完全不同的概念。共識是指各節(jié)點就指定值（Value）達成共識，而且達成共識后的值，就不再改變了。一致性是指寫操作完成后，能否從各節(jié)點上讀到最新寫入的數(shù)據(jù)，如果立即能讀到，就是強一致性，如果最終能讀到，就是最終一致性。
提到共識算法，Paxos 是一個必須要提及的話題，而且 ZAB 協(xié)議、Raft 算法都可以看作是 Paxos 變種，Paxos 和 Raft 是共識算法。所以，你需要了解 Paxos 算法。但因為 Paxos 算法的可理解性和可編程性痛點突出，所以在實際場景中，最常的共識算法是 Raft，我們可以基于 Raft 實現(xiàn)強一致性系統(tǒng)，Raft 是需要徹底掌握的。
8 條荒謬的分布式假設
Fallacies of Distributed Computing 是英文維基百科上的一篇文章，講的是剛剛進入分布式計算領域的程序員常會有的 8 條假定，隨著時間的推移，每一條都會被證明是錯誤的，也都會導致嚴重的問題，以及痛苦的學習體驗：
- 網絡是穩(wěn)定的。
- 網絡傳輸?shù)难舆t是零。
- 網絡的帶寬是無窮大。
- 網絡是安全的。
- 網絡的拓撲不會改變。
- 只有一個系統(tǒng)管理員。
- 傳輸數(shù)據(jù)的成本為零。
- 整個網絡是同構的。
為什么我們要深刻地認識這 8 個錯誤？是因為，這要我們清楚地認識到，在分布式系統(tǒng)中錯誤是不可能避免的，我們能做的不是避免錯誤，而是要把錯誤的處理當成功能寫在代碼中。這 8 個需要避免的錯誤不僅對于中間件和底層系統(tǒng)開發(fā)者及架構師是重要的知識，而且對于網絡應用程序開發(fā)者也同樣重要。分布式系統(tǒng)的其他部分，如容錯、備份、分片、微服務等也許可以對應用程序開發(fā)者部分透明，但這 8 點則是應用程序開發(fā)者也必須知道的。
常見分布式算法的對比
從拜占庭容錯、一致性、性能和可用性四個緯度來分析如下（來自極客時間-韓健-分布式協(xié)議與算法實戰(zhàn)）：
一般而言，在可信環(huán)境（比如企業(yè)內網）中，系統(tǒng)具有故障容錯能力就可以了，常見的算法有二階段提交協(xié)議（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 協(xié)議、Raft 算法、Gossip 協(xié)議、Quorum NWR 算法。而在不可信的環(huán)境（比如有人做惡）中，這時系統(tǒng)需要具備拜占庭容錯能力，常見的拜占庭容錯算法有 POW 算法、PBFT 算法。
采用 Gossip 協(xié)議實現(xiàn)的最終一致性系統(tǒng)的可用性是最高的，因為哪怕只有一個節(jié)點，集群還能在運行并提供服務。其次是 Paxos 算法、ZAB 協(xié)議、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它們能容忍一定數(shù)節(jié)點故障。最后是二階段提交協(xié)議、TCC，只有當所有節(jié)點都在運行時，才能工作，可用性最低。
采用 Gossip 協(xié)議的 AP 型分布式系統(tǒng)，具備水平擴展能力，讀寫性能是最高的。其次是 Paxos 算法、ZAB 協(xié)議、Raft 算法，因為它們都是領導者模型，寫性能受限于領導者，讀性能取決于一致性實現(xiàn)。最后是二階段提交協(xié)議和 TCC，因為在實現(xiàn)事務時，需要預留和鎖定資源，性能相對低。
2PC【強一致性】
兩階段提交（2PC，Two-phase Commit Protocol）是非常經典的強一致性協(xié)議，在各種事務和一致性的解決方案中，都能看到兩階段提交的應用，二階段提交協(xié)議，不僅僅是協(xié)議，也是一種非常經典的思想。2PC 的流程就是第一階段做投票，第二階段做決定的一個算法。
二階段提交在達成提交操作共識的算法中應用廣泛，比如 XA 協(xié)議、TCC、Paxos、Raft 等。Paxos、Raft 等強一致性算法，也采用了二階段提交操作，在“提交請求階段”，只要大多數(shù)節(jié)點確認就可以，而具有 ACID 特性的事務，則要求全部節(jié)點確認可以。所以可以將具有 ACID 特性的操作，理解為最強的一致性。
三階段提交協(xié)議（3PC，Three-phase_commit_protocol）是在 2PC 之上擴展的提交協(xié)議，主要是為了解決兩階段提交協(xié)議的阻塞問題，從原來的兩個階段擴展為三個階段，增加了超時機制。但目前兩階段提交、三階段提交存在如下的局限性，并不適合在微服務架構體系下使用：
- 所有的操作必須是事務性資源（比如數(shù)據(jù)庫、消息隊列），存在使用局限性
- 由于是強一致性，資源需要在事務內部等待，性能影響較大，吞吐率不高，不適合高并發(fā)與高性能的業(yè)務場景；
Paxos【強一致性】
Paxos 算法基本上來說是個民主選舉的算法——大多數(shù)的決定會成個整個集群的統(tǒng)一決定。任何一個點都可以提出要修改某個數(shù)據(jù)的提案，是否通過這個提案取決于這個集群中是否有超過半數(shù)的結點同意（所以Paxos算法需要集群中的結點是單數(shù)）。蘭伯特提出的 Paxos 算法包含 2 個部分：
- 一個是 Basic Paxos 算法，描述的是多節(jié)點之間如何就某個值（提案 Value）達成共識；
- 另一個是 Multi-Paxos 思想，描述的是執(zhí)行多個 Basic Paxos 實例就一系列值達成共識。Basic Paxos 是 Multi-Paxos 思想的核心。
Raft【強一致性】
Raft 算法是 Paxos 算法的一種簡化實現(xiàn)，其實 Raft 不是一致性算法而是共識算法，是一個 Multi-Paxos 算法，實現(xiàn)的是如何就一系列值達成共識。Raft 算法是在蘭伯特 Multi-Paxos 思想的基礎上，做了一些簡化和限制，比如增加了日志必須是連續(xù)的，只支持領導者、跟隨者和候選人三種狀態(tài)，在理解和算法實現(xiàn)上都相對容易許多。
ZAB【最終一致性】
ZAB 協(xié)議和 ZooKeeper 代碼耦合在一起了，無法單獨使用 ZAB 協(xié)議，所以一般而言，只需要理解 ZAB 協(xié)議的架構和基礎原理就可以了。
TCC【最終一致性】
TCC 是一個分布式事務的處理模型，將事務過程拆分為 Try、Confirm、Cancel 三個步驟，在保證強一致性的同時，最大限度提高系統(tǒng)的可伸縮性與可用性，又被稱補償事務。它的核心思想是針對每個操作都要注冊一個與其對應的確認操作和補償操作（也就是撤銷操作）
二階段提交協(xié)議實現(xiàn)的是數(shù)據(jù)層面的事務，比如 XA 規(guī)范采用的就是二階段提交協(xié)議；TCC 實現(xiàn)的是業(yè)務層面的事務，TCC 可以理解為是一個業(yè)務層面的協(xié)議，可以當做為一個編程模型來看待，因此這個的應用還是非常廣泛的。，TCC 的 3 個操作是需要在業(yè)務代碼中編碼實現(xiàn)的，為了實現(xiàn)一致性，確認操作和補償操作必須是等冪的，因為這 2 個操作可能會失敗重試。
TCC 不依賴于數(shù)據(jù)庫的事務，而是在業(yè)務中實現(xiàn)了分布式事務，這樣能減輕數(shù)據(jù)庫的壓力，但對業(yè)務代碼的入侵性也更強，實現(xiàn)的復雜度也更高。所以，推薦在需要分布式事務能力時，優(yōu)先考慮現(xiàn)成的事務型數(shù)據(jù)庫（比如 MySQL XA），當現(xiàn)有的事務型數(shù)據(jù)庫不能滿足業(yè)務的需求時，再考慮基于 TCC 實現(xiàn)分布式事務。
Gossip【最終一致性】
Gossip 協(xié)議利用一種隨機、帶有傳染性的方式，將信息傳播到整個網絡中，并在一定時間內，使得系統(tǒng)內的所有節(jié)點數(shù)據(jù)一致。掌握這個協(xié)議不僅能很好地理解這種最常用的，實現(xiàn)最終一致性的算法，也能在后續(xù)工作中得心應手地實現(xiàn)數(shù)據(jù)的最終一致性。
Gossip 主要通過三個步驟：直接郵寄（Direct Mail）、反熵（Anti-entropy）和謠言傳播（Rumor mongering） 來實現(xiàn)最終一致性。實現(xiàn)數(shù)據(jù)副本的最終一致性時，一般而言，直接郵寄的方式是一定要實現(xiàn)的。在節(jié)點都是已知的情況下，一般采用反熵修復數(shù)據(jù)副本的一致性。當集群節(jié)點是變化的，或者集群節(jié)點數(shù)比較多時，這時要采用謠言傳播的方式來實現(xiàn)最終一致。
Quorum NWR【最終一致性】
Quorum NWR 算法非常實用，能有效彌補 AP 型系統(tǒng)缺乏強一致性的痛點，給業(yè)務提供了按需選擇一致性級別的靈活度。實際應用中，一般的 AP 型分布式系統(tǒng)中（比如 Dynamo、Cassandra、InfluxDB 企業(yè)版的 DATA 節(jié)點集群）都會實現(xiàn) Quorum NWR 的功能。掌握 Quorum NWR，不僅是掌握一種常用的實現(xiàn)一致性的方法，同時可以根據(jù)業(yè)務的特點來靈活地指定一致性級別。
N、W、R 值的不同組合，會產生不同的一致性效果：
- 當 W + R > N 的時候，對于客戶端來講，整個系統(tǒng)能保證強一致性，一定能返回更新后的那份數(shù)據(jù)。
- 當 W + R <= N 的時候，對于客戶端來講，整個系統(tǒng)只能保證最終一致性，可能會返回舊數(shù)據(jù)。
如何設置 N、W、R 值，取決于我們想優(yōu)化哪方面的性能。比如，N 決定了副本的冗余備份能力；如果設置 W = N，讀性能比較好；如果設置 R = N，寫性能比較好；如果設置 W = (N + 1) / 2、R = (N + 1) / 2，容錯能力比較好，能容忍少數(shù)節(jié)點（也就是 (N - 1) / 2）的故障。
POW【拜占庭容錯】
區(qū)塊鏈中有此應用
PBFT【拜占庭容錯】
區(qū)塊鏈中有此應用
本文轉載自微信公眾號「 后端系統(tǒng)和架構」
