2萬字 | 寫了八篇分布式算法，我“悟空”了

本文主要內(nèi)容：

最近三個月更新了 8 篇分布式理論和算法的文章，發(fā)現(xiàn)這些知識點(diǎn)雖然有一丟丟小枯燥，但是非常重要，于是每篇我都用故事的方式進(jìn)行講解，力求每篇都能讓大家都能看懂，是不是很用心呢？

在寫的過程中，我慢慢地悟出了分布式理論和算法的真諦，且聽下文分解。

重要性

分布式理論和算法的重要性體現(xiàn)在哪呢？

你是不是經(jīng)常聽到 CA，AP 理論，CAP 三角不可能同時達(dá)成？

Zookeeper 怎么進(jìn)行 Leader 選舉的？

怎么進(jìn)行容錯？

這些問題的答案都是分布式理論和算法的精髓所在。而且說個很現(xiàn)實(shí)的問題，在現(xiàn)階段，掌握分布式算法也是出去面試架構(gòu)師、技術(shù)專家等高薪職位時，也是會被經(jīng)常問到的。但是求職者中只有少部分懂這一塊。

我為什么要強(qiáng)調(diào)分布式算法的重要性？不論是對技術(shù)深度的追求，還是長期職業(yè)發(fā)展的需要，都是可以提升你的核心競爭力的。

好學(xué)嗎？

現(xiàn)在很多開發(fā)同學(xué)對分布式的組件怎么使用都有一定經(jīng)驗(yàn)，也知道 CAP 理論和 BASE 理論的大致含義。但認(rèn)真去看分布式算法的真的很少，原因有三：

• 擔(dān)心算法過于復(fù)雜，所以花的時間很少。
• 網(wǎng)上的資料能用大白話將分布式算法講清楚的比較少。
• 學(xué)習(xí)分布式算法沒有一條清晰的路線。

學(xué)習(xí)分布式協(xié)議和算法的路線可以是先學(xué)習(xí)四大基礎(chǔ)理論，作為地基。然后再學(xué)習(xí)分布式協(xié)議和算法。就像是在地基上建房子，地基打好了，才能建更穩(wěn)固的高樓大廈。

而分布式理論主要有四大塊：

四大基礎(chǔ)理論

• 拜占庭將軍問題
• CAP 理論
• ACID 理論
• BASE 理論

分布式協(xié)議和算法主要有八種：

八大分布式協(xié)議和算法

• Paxos 算法
• Raft 算法
• 一致性 Hash 算法
• Gossip 協(xié)議算法
• Quorum NWR 算法
• FBFT 算法
• POW 算法
• ZAB 協(xié)議

如何高效地學(xué)習(xí)和掌握？

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

講真，如果認(rèn)真學(xué)習(xí)這些理論和算法，并清楚了每個算法的特點(diǎn)，適合怎樣的場景，當(dāng)開發(fā)分布式系統(tǒng)時，做到知己知彼，才能旗開得勝，實(shí)際場景中的問題也能分析清楚并解決掉。

那么這些算法有哪些特點(diǎn)和適用場景，該從哪些方面考量？

分布式算法的四大維度

四大維度：拜占庭容錯、一致性、性能、可用性。

這里我做了一個分布式算法四大維度的表格，大家可以對比下：

拜占庭容錯

拜占庭容錯就是《拜占庭將軍問題》中提出的一個模型，該模型描述了一個完全不可信的場景。不可信體現(xiàn)在：

• 故障行為。比如節(jié)點(diǎn)故障了。
• 惡意行為。比如惡意節(jié)點(diǎn)冒充正常節(jié)點(diǎn)，發(fā)出錯誤指令。

拜占庭容錯的另外一面就是非拜占庭容錯，又叫故障容錯，解決了分布式系統(tǒng)存在故障，但是不存在惡意節(jié)點(diǎn)共識的問題，譬如節(jié)點(diǎn)所在服務(wù)器硬件故障、節(jié)點(diǎn)的服務(wù)進(jìn)程崩潰等。

非拜占庭容錯算法

在可信的環(huán)境，只需要具有故障容錯能力，譬如 2PC、TCC、Paxos算法、Raft 算法、Gossip 協(xié)議、Ouorum NWR 算法、ZAB 協(xié)議。

拜占庭容錯算法

而在不可信的環(huán)境，需要具有拜占庭容錯能力，報錯 POW 算法、FBFT 算法。

一致性

一致性分為三種：

• 強(qiáng)一致性：保證寫操作完成后，任何后續(xù)訪問都能讀到更新后的值。
• 弱一致性：寫操作完成后，系統(tǒng)不能保證后續(xù)的訪問都能讀到更新后的值。
• 最終一致性：保證如果對某個對象沒有新的寫操作，最終所有后續(xù)訪問都能讀到相同的最近更新的值。

在數(shù)據(jù)庫操作層面，我們多使用二階段提交協(xié)議（2PC）保證強(qiáng)一致性。在分布式系統(tǒng)中，多使用 Raft 算法來保證強(qiáng)一致性。如果考慮可用性，則使用 Gossip 協(xié)議實(shí)現(xiàn)最終一致性，配合 Quorum NWR 算法的三個參數(shù)來調(diào)節(jié)容錯能力。而 zookeeper 基于讀性能的考慮，通過 ZAB 協(xié)議提供最終一致性。

可用性

可用性表示能得到響應(yīng)數(shù)據(jù)，但不保證數(shù)據(jù)最新，強(qiáng)調(diào)服務(wù)可用。前提條件：訪問的是非故障節(jié)點(diǎn)。

可用性最強(qiáng)的就是 Gossip 協(xié)議了，即時只有一個節(jié)點(diǎn)，集群可以提供服務(wù)。然后是 Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法，能夠容忍部分節(jié)點(diǎn)故障。

而 2PC、TCC 要求所有節(jié)點(diǎn)都正常運(yùn)行，系統(tǒng)才能正常工作，可用性最低。

性能

性能和可用性聯(lián)系非常緊密，可用性越高，性能越強(qiáng)。

上面可用性的排序同樣適用于性能維度。Gossip 協(xié)議可用于 AP 型分布式系統(tǒng)，水平擴(kuò)展能力強(qiáng)，讀寫性能最強(qiáng)。

Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法都是領(lǐng)導(dǎo)者模型，寫性能依賴領(lǐng)導(dǎo)者，讀性能依賴一致性的實(shí)現(xiàn)。性能處于中等位置。

而 2PC、TCC 實(shí)現(xiàn)事務(wù)時，需要預(yù)留和鎖定資源，性能較差。

學(xué)習(xí)路線

第一講：拜占庭將軍問題

必須先把拜占庭將軍問題弄懂，這篇我用三國殺卡牌游戲中的四種身份牌來講解了拜占庭將軍問題。

《用三國殺講分布式算法，舒適了吧？》

第二講：CAP、BASE、ACID 理論

是針對 CAP、BASE、ACID 三大理論的講解，文中我用太極拳中的剛和柔來比喻 ACID 和 BASE，而如何平衡剛和柔就需要 CAP 理論了。

《用太極拳講分布式理論，真舒服！》

第三講：Paxos 算法

為了更好地理解 Paxos 算法，我用三國演義中的諸葛亮和龐統(tǒng)兩種角色充當(dāng)提議者對 Paxos 算法的細(xì)節(jié)進(jìn)行了分析。

《諸葛亮 VS 龐統(tǒng)，拿下分布式 Paxos》

第四講：Raft 算法

Raft 算法其實(shí)比較好理解，但是直接描述出來會讓人云里霧里，所以我借助了動圖，用動圖模擬 Raft 算法的選舉過程，輕松易懂。

《用動圖講解分布式 Raft》

第五講：一致性哈希

這個也算作分布式算法中的一種，常用在負(fù)載均衡、路由尋址中。該算法理解起來不難，但比較枯燥，所以我用韓信點(diǎn)兵的故事來進(jìn)行講解，詼諧有趣。

《韓信大招：一致性哈?！?/a>

《病毒入侵：全靠分布式 Gossip 協(xié)議》

第七講：Quorum NWR

N、W、R 這三個參數(shù)，比較晦澀，為了讓大家更容易理解，我用太上老君的煉丹爐比作節(jié)點(diǎn)，丹爐里面的藥比作數(shù)據(jù)，用煉造過程來體現(xiàn) NWR 這三個參數(shù)，更加形象化。

《太上老君的煉丹爐之分布式 Quorum NWR》

第八講：POW 算法

在學(xué)習(xí) POW 算法時，牽扯到區(qū)塊鏈的知識，于是我就去看了一本區(qū)塊鏈的書《區(qū)塊鏈：從數(shù)字貨幣到信用社會》，一本科普書，對我了解區(qū)塊鏈、比特幣幫助很大。而區(qū)塊鏈中用到的核心知識之一就是 POW 算法，也叫做工作量證明。我用紫霞仙子和至尊寶的故事對區(qū)塊鏈、比特幣、工作量證明進(jìn)行了講解，詼諧有趣。

《紫霞仙子：頂?shù)米^(qū)塊鏈的十二連問嗎？》

對了，F(xiàn)BFT 和 ZAB 協(xié)議還沒有給大家講解，后續(xù)可能得過一段時間才能補(bǔ)上，因?yàn)橛泻芏嘧x者朋友在催更我的開源項目 PassJava，所以得去倒騰開源項目了。

另外我將這八篇內(nèi)容整理成了一份 PDF 文檔，總共 2W+ 字，在公眾號后臺回復(fù)：【分布式】三個字即可獲取。