常見分布式協(xié)議和算法的說明和對比

開發(fā)分布式系統(tǒng)最關(guān)鍵的就是根據(jù)場景特點(diǎn)，選擇合適的算法，在一致性和可用性之間妥協(xié)折中，而妥協(xié)折中的關(guān)鍵就在于能否理解各算法的特點(diǎn)。

分布式一致性的背景

一致性的分類

我們講分布式系統(tǒng)的一致性，一般來說，有如下幾個分類：

• 強(qiáng)一致性。對一致性要求最高的，是強(qiáng)一致的，保證寫操作完成后，任何后續(xù)訪問都能讀到更新后的值。。但是性能較弱，在互聯(lián)網(wǎng)系統(tǒng)里面用的較少，但是在金融領(lǐng)域使用的較多。因?yàn)槭峭降模虼诵阅軙容^低。
• 弱一致性。寫操作完成后，系統(tǒng)不能保證后續(xù)的訪問都能讀到更新后的值。
• 最終一致性。是弱一致性的一個特定形式，如果對某個對象沒有新的寫操作了，最終所有后續(xù)訪問都能讀到相同的最近更新的值，但是是在最終某個時間點(diǎn)才能保證。弱一致性（最終一致性）都是異步的，因此性能會比較好。

一般而言，在需要系統(tǒng)狀態(tài)的一致性時，你可以考慮采用二階段提交協(xié)議、TCC。在需要數(shù)據(jù)訪問是的強(qiáng)一致性時，你可考慮 Raft 算法。在可用性優(yōu)先的系統(tǒng)，你可以采用 Gossip 協(xié)議來實(shí)現(xiàn)最終一致性，并實(shí)現(xiàn) Quorum NWR 來提供強(qiáng)一致性。

如何理解分布式一致性

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

分布式系統(tǒng)的核心問題

前面說到，分布式一致性，是通過給定的一系列操作，在協(xié)議（共識算法）的保障下，試圖使得它們對處理結(jié)果達(dá)成某種程度的一致。這里，也就是整個分布式系統(tǒng)的核心問題，怎么保證多個節(jié)點(diǎn)間的數(shù)據(jù)是一致的，這就需要我們對分布式協(xié)議（共識算法）要能夠有比較深刻的理解，然后才能很好的解決分布式數(shù)據(jù)的一致性，掌握分布式協(xié)議（共識算法）也是你面試架構(gòu)師、技術(shù)專家等高端崗位時的敲門磚。

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

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

而非拜占庭容錯，又叫故障容錯（Crash Fault Tolerance，CFT），解決的是分布式系統(tǒng)中存在故障，但不存在惡意節(jié)點(diǎn)的共識問題。實(shí)際上，這種故障是非常場景的，比如進(jìn)程奔潰、服務(wù)器硬件故障、網(wǎng)絡(luò)中斷、響應(yīng)延遲等等。針對非拜占庭錯誤的解決方案，業(yè)界一般采用 Paxos、Raft 及其各種變種的協(xié)議。

共識 vs 一致性

共識算法解決的是對某個提案（Proposal）讓大家都達(dá)成一致意見的過程，而這個提案可以認(rèn)為任何需要達(dá)成一致的信息都是一個提案，如多個事件發(fā)生的順序、某個鍵對應(yīng)的值等等。在實(shí)踐中，一致性的結(jié)果還需要客戶端的支持，比如通過訪問足夠多個服務(wù)節(jié)點(diǎn)來驗(yàn)證確保獲取共識后結(jié)果。

但是由于分布式系統(tǒng)會存在各種非拜占庭容錯，因此要達(dá)成共識就比較困難，需要一些共識算法來解決。這里需要注意，共識（Consensus）和一致性（Consistency）是兩個完全不同的概念。共識是指各節(jié)點(diǎn)就指定值（Value）達(dá)成共識，而且達(dá)成共識后的值，就不再改變了。一致性是指寫操作完成后，能否從各節(jié)點(diǎn)上讀到最新寫入的數(shù)據(jù)，如果立即能讀到，就是強(qiáng)一致性，如果最終能讀到，就是最終一致性。

提到共識算法，Paxos 是一個必須要提及的話題，而且 ZAB 協(xié)議、Raft 算法都可以看作是 Paxos 變種，Paxos 和 Raft 是共識算法。所以，你需要了解 Paxos 算法。但因?yàn)?Paxos 算法的可理解性和可編程性痛點(diǎn)突出，所以在實(shí)際場景中，最常的共識算法是 Raft，我們可以基于 Raft 實(shí)現(xiàn)強(qiáng)一致性系統(tǒng)，Raft 是需要徹底掌握的。

8 條荒謬的分布式假設(shè)

Fallacies of Distributed Computing 是英文維基百科上的一篇文章，講的是剛剛進(jìn)入分布式計(jì)算領(lǐng)域的程序員常會有的 8 條假定，隨著時間的推移，每一條都會被證明是錯誤的，也都會導(dǎo)致嚴(yán)重的問題，以及痛苦的學(xué)習(xí)體驗(yàn)：

• 網(wǎng)絡(luò)是穩(wěn)定的。
• 網(wǎng)絡(luò)傳輸?shù)难舆t是零。
• 網(wǎng)絡(luò)的帶寬是無窮大。
• 網(wǎng)絡(luò)是安全的。
• 網(wǎng)絡(luò)的拓?fù)洳粫淖儭?/li>
• 只有一個系統(tǒng)管理員。
• 傳輸數(shù)據(jù)的成本為零。
• 整個網(wǎng)絡(luò)是同構(gòu)的。

為什么我們要深刻地認(rèn)識這 8 個錯誤？是因?yàn)?，這要我們清楚地認(rèn)識到，在分布式系統(tǒng)中錯誤是不可能避免的，我們能做的不是避免錯誤，而是要把錯誤的處理當(dāng)成功能寫在代碼中。這 8 個需要避免的錯誤不僅對于中間件和底層系統(tǒng)開發(fā)者及架構(gòu)師是重要的知識，而且對于網(wǎng)絡(luò)應(yīng)用程序開發(fā)者也同樣重要。分布式系統(tǒng)的其他部分，如容錯、備份、分片、微服務(wù)等也許可以對應(yīng)用程序開發(fā)者部分透明，但這 8 點(diǎn)則是應(yīng)用程序開發(fā)者也必須知道的。

常見分布式算法的對比

從拜占庭容錯、一致性、性能和可用性四個緯度來分析如下（來自極客時間-韓健-分布式協(xié)議與算法實(shí)戰(zhàn)）：

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

采用 Gossip 協(xié)議實(shí)現(xiàn)的最終一致性系統(tǒng)的可用性是最高的，因?yàn)槟呐轮挥幸粋€節(jié)點(diǎn)，集群還能在運(yùn)行并提供服務(wù)。其次是 Paxos 算法、ZAB 協(xié)議、Raft 算法、Quorum NWR 算法、PBFT 算法、POW 算法，它們能容忍一定數(shù)節(jié)點(diǎn)故障。最后是二階段提交協(xié)議、TCC，只有當(dāng)所有節(jié)點(diǎn)都在運(yùn)行時，才能工作，可用性最低。

采用 Gossip 協(xié)議的 AP 型分布式系統(tǒng)，具備水平擴(kuò)展能力，讀寫性能是最高的。其次是 Paxos 算法、ZAB 協(xié)議、Raft 算法，因?yàn)樗鼈兌际穷I(lǐng)導(dǎo)者模型，寫性能受限于領(lǐng)導(dǎo)者，讀性能取決于一致性實(shí)現(xiàn)。最后是二階段提交協(xié)議和 TCC，因?yàn)樵趯?shí)現(xiàn)事務(wù)時，需要預(yù)留和鎖定資源，性能相對低。

2PC【強(qiáng)一致性】

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

二階段提交在達(dá)成提交操作共識的算法中應(yīng)用廣泛，比如 XA 協(xié)議、TCC、Paxos、Raft 等。Paxos、Raft 等強(qiáng)一致性算法，也采用了二階段提交操作，在“提交請求階段”，只要大多數(shù)節(jié)點(diǎn)確認(rèn)就可以，而具有 ACID 特性的事務(wù)，則要求全部節(jié)點(diǎn)確認(rèn)可以。所以可以將具有 ACID 特性的操作，理解為最強(qiáng)的一致性。

三階段提交協(xié)議（3PC，Three-phase_commit_protocol）是在 2PC 之上擴(kuò)展的提交協(xié)議，主要是為了解決兩階段提交協(xié)議的阻塞問題，從原來的兩個階段擴(kuò)展為三個階段，增加了超時機(jī)制。但目前兩階段提交、三階段提交存在如下的局限性，并不適合在微服務(wù)架構(gòu)體系下使用：

• 所有的操作必須是事務(wù)性資源（比如數(shù)據(jù)庫、消息隊(duì)列），存在使用局限性
• 由于是強(qiáng)一致性，資源需要在事務(wù)內(nèi)部等待，性能影響較大，吞吐率不高，不適合高并發(fā)與高性能的業(yè)務(wù)場景；

Paxos【強(qiáng)一致性】

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

• 一個是 Basic Paxos 算法，描述的是多節(jié)點(diǎn)之間如何就某個值（提案 Value）達(dá)成共識；
• 另一個是 Multi-Paxos 思想，描述的是執(zhí)行多個 Basic Paxos 實(shí)例就一系列值達(dá)成共識。Basic Paxos 是 Multi-Paxos 思想的核心。

Raft【強(qiáng)一致性】

Raft 算法是 Paxos 算法的一種簡化實(shí)現(xiàn)，其實(shí) Raft 不是一致性算法而是共識算法，是一個 Multi-Paxos 算法，實(shí)現(xiàn)的是如何就一系列值達(dá)成共識。Raft 算法是在蘭伯特 Multi-Paxos 思想的基礎(chǔ)上，做了一些簡化和限制，比如增加了日志必須是連續(xù)的，只支持領(lǐng)導(dǎo)者、跟隨者和候選人三種狀態(tài)，在理解和算法實(shí)現(xiàn)上都相對容易許多。

ZAB【最終一致性】

ZAB 協(xié)議和 ZooKeeper 代碼耦合在一起了，無法單獨(dú)使用 ZAB 協(xié)議，所以一般而言，只需要理解 ZAB 協(xié)議的架構(gòu)和基礎(chǔ)原理就可以了。

TCC【最終一致性】

TCC 是一個分布式事務(wù)的處理模型，將事務(wù)過程拆分為 Try、Confirm、Cancel 三個步驟，在保證強(qiáng)一致性的同時，最大限度提高系統(tǒng)的可伸縮性與可用性，又被稱補(bǔ)償事務(wù)。它的核心思想是針對每個操作都要注冊一個與其對應(yīng)的確認(rèn)操作和補(bǔ)償操作（也就是撤銷操作）

二階段提交協(xié)議實(shí)現(xiàn)的是數(shù)據(jù)層面的事務(wù)，比如 XA 規(guī)范采用的就是二階段提交協(xié)議；TCC 實(shí)現(xiàn)的是業(yè)務(wù)層面的事務(wù)，TCC 可以理解為是一個業(yè)務(wù)層面的協(xié)議，可以當(dāng)做為一個編程模型來看待，因此這個的應(yīng)用還是非常廣泛的。，TCC 的 3 個操作是需要在業(yè)務(wù)代碼中編碼實(shí)現(xiàn)的，為了實(shí)現(xiàn)一致性，確認(rèn)操作和補(bǔ)償操作必須是等冪的，因?yàn)檫@ 2 個操作可能會失敗重試。

TCC 不依賴于數(shù)據(jù)庫的事務(wù)，而是在業(yè)務(wù)中實(shí)現(xiàn)了分布式事務(wù)，這樣能減輕數(shù)據(jù)庫的壓力，但對業(yè)務(wù)代碼的入侵性也更強(qiáng)，實(shí)現(xiàn)的復(fù)雜度也更高。所以，推薦在需要分布式事務(wù)能力時，優(yōu)先考慮現(xiàn)成的事務(wù)型數(shù)據(jù)庫（比如 MySQL XA），當(dāng)現(xiàn)有的事務(wù)型數(shù)據(jù)庫不能滿足業(yè)務(wù)的需求時，再考慮基于 TCC 實(shí)現(xiàn)分布式事務(wù)。

Gossip【最終一致性】

Gossip 協(xié)議利用一種隨機(jī)、帶有傳染性的方式，將信息傳播到整個網(wǎng)絡(luò)中，并在一定時間內(nèi)，使得系統(tǒng)內(nèi)的所有節(jié)點(diǎn)數(shù)據(jù)一致。掌握這個協(xié)議不僅能很好地理解這種最常用的，實(shí)現(xiàn)最終一致性的算法，也能在后續(xù)工作中得心應(yīng)手地實(shí)現(xiàn)數(shù)據(jù)的最終一致性。

Gossip 主要通過三個步驟：直接郵寄（Direct Mail）、反熵（Anti-entropy）和謠言傳播（Rumor mongering） 來實(shí)現(xiàn)最終一致性。實(shí)現(xiàn)數(shù)據(jù)副本的最終一致性時，一般而言，直接郵寄的方式是一定要實(shí)現(xiàn)的。在節(jié)點(diǎn)都是已知的情況下，一般采用反熵修復(fù)數(shù)據(jù)副本的一致性。當(dāng)集群節(jié)點(diǎn)是變化的，或者集群節(jié)點(diǎn)數(shù)比較多時，這時要采用謠言傳播的方式來實(shí)現(xiàn)最終一致。

Quorum NWR【最終一致性】

Quorum NWR 算法非常實(shí)用，能有效彌補(bǔ) AP 型系統(tǒng)缺乏強(qiáng)一致性的痛點(diǎn)，給業(yè)務(wù)提供了按需選擇一致性級別的靈活度。實(shí)際應(yīng)用中，一般的 AP 型分布式系統(tǒng)中（比如 Dynamo、Cassandra、InfluxDB 企業(yè)版的 DATA 節(jié)點(diǎn)集群）都會實(shí)現(xiàn) Quorum NWR 的功能。掌握 Quorum NWR，不僅是掌握一種常用的實(shí)現(xiàn)一致性的方法，同時可以根據(jù)業(yè)務(wù)的特點(diǎn)來靈活地指定一致性級別。

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

• 當(dāng) W + R > N 的時候，對于客戶端來講，整個系統(tǒng)能保證強(qiáng)一致性，一定能返回更新后的那份數(shù)據(jù)。
• 當(dāng) W + R <= N 的時候，對于客戶端來講，整個系統(tǒng)只能保證最終一致性，可能會返回舊數(shù)據(jù)。

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

POW【拜占庭容錯】

區(qū)塊鏈中有此應(yīng)用

PBFT【拜占庭容錯】

區(qū)塊鏈中有此應(yīng)用

本文轉(zhuǎn)載自微信公眾號「 后端系統(tǒng)和架構(gòu)」，作者「 AllenWu」，可以通過以下二維碼關(guān)注。

轉(zhuǎn)載本文請聯(lián)系「后端系統(tǒng)和架構(gòu)」公眾號。