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