引言

前面我們已經(jīng)講了分布式 CAP、BASE 理論及分布式事務(wù)的 8 種解決方案，今天我們來(lái)聊一聊常見(jiàn)的 4 種分布式算法。

1. Paxos 算法

Paxos 算法的業(yè)務(wù)場(chǎng)景就好比是在一個(gè)大公司的董事會(huì)選舉中心選出新董事長(zhǎng)，但這個(gè)過(guò)程是在烏云密布的風(fēng)雨天進(jìn)行，通信極度不穩(wěn)定，董事們時(shí)不時(shí)被困在電梯里或是在高爾夫球場(chǎng)打不了電話。

在 Paxos 算法中，每個(gè)董事（參與者）都是獨(dú)立操作的，而這個(gè)算法就是確保即便在通信可能失敗，董事們也能達(dá)成一致。

它通過(guò)一系列的提議（proposal）和承諾（promise）來(lái)保證最終的一致性。

業(yè)務(wù)場(chǎng)景

假設(shè)，現(xiàn)在有 3 個(gè)董事候選人在爭(zhēng)奪董事長(zhǎng)職位，用 Paxos 算法來(lái)表示這個(gè)過(guò)程，可分為三個(gè)階段：

1. 準(zhǔn)備階段（Prepare）:

• 候選董事 A 向所有董事會(huì)成員（不包含其它候選人）發(fā)送一個(gè)帶有特定提議編號(hào)的請(qǐng)求。
• 其他董事會(huì)成員在確保該提議編號(hào)高于任何之前收到的提案編號(hào)的情況下，會(huì)承諾不會(huì)接受編號(hào)更低的提議，它們響應(yīng)說(shuō)：“好的，你是編號(hào)最高的候選人，我聽(tīng)聽(tīng)你的是啥提案”。

2. 批準(zhǔn)階段（Accept）:

• 當(dāng)候選董事 A 收到了多數(shù)董事會(huì)成員的承諾后，它會(huì)向那些承諾過(guò)的成員發(fā)送詳細(xì)的提案內(nèi)容。

• 如果這些董事會(huì)成員沒(méi)有對(duì)更高編號(hào)的提案做出過(guò)承諾，它們就會(huì)接受這個(gè)提案。

3. 學(xué)習(xí)階段（Learn）:

• 一旦提案被多數(shù)董事會(huì)成員批準(zhǔn)，這個(gè)候選人就被選為新董事，每個(gè)董事會(huì)成員會(huì)記錄下來(lái)這個(gè)結(jié)果。

• 此時(shí)，所有其他員工或股東都需要知道這個(gè)結(jié)果，這樣新董事的確立就在全公司范圍內(nèi)達(dá)到了一致。

在這過(guò)程中，Paxos 算法又將系統(tǒng)中的節(jié)點(diǎn)分為三類：

圖片

• 提議者（Proposer）：提議者負(fù)責(zé)創(chuàng)建提案，并向 Acceptor（接受者） 發(fā)送提案。提案包括一個(gè)序號(hào)和提議值，假設(shè)為 [n, v]，提議者需要確保它提出的提案編號(hào) n 是獨(dú)一無(wú)二的，例如董事候選人和他的候選編號(hào)。
• 接受者（Aceeptor）：接受或拒絕提案，當(dāng)接受提案后，接受者會(huì)作出 承諾（Promise）不再接受比當(dāng)前提案接受者編號(hào)更低的提案，并繼續(xù)接受具有更高編號(hào)的提案，就像例子中的董事會(huì)成員那樣。
• 告知者（Learner）：被告知投票的結(jié)果，不參與投票過(guò)程，公司股東或者其他員工。

提議的時(shí)候，包含倆字段：[n, v]，其中 n 為序號(hào)，v 為提議值。每個(gè) Aceeptor 在接收提議請(qǐng)求的時(shí)候，會(huì)比對(duì)其中的序號(hào) n：

• 當(dāng)前序號(hào)小于已存在的 n 時(shí)，則不予理會(huì)；
• 當(dāng)前序號(hào)大于 n 時(shí)，會(huì)返回響應(yīng)，表示接受了這個(gè)序號(hào)為 n 的提議，并承諾（Promise）不再接受比當(dāng)前提案編號(hào)更低的提案。

當(dāng)一個(gè) Proposer 接收到超過(guò)半數(shù)的 Aceeptor 響應(yīng)時(shí)，說(shuō)明該提議值被 Paxos 選擇了出來(lái)，這時(shí)候，由 Acceptor 負(fù)責(zé)通知給所有的 Learner。

2. Raft 算法

引入主節(jié)點(diǎn)，通過(guò)競(jìng)選來(lái)獲取主節(jié)點(diǎn)。節(jié)點(diǎn)分為三類：

• 領(lǐng)頭結(jié)點(diǎn) Leader
• 從節(jié)點(diǎn) Follower
• 候選節(jié)點(diǎn) Candidate

想象咱們身處一個(gè)居民社區(qū)里面，這個(gè)社區(qū)需要選舉出一位業(yè)委會(huì)主任來(lái)負(fù)責(zé)新年的社區(qū)大事，Raft 算法會(huì)經(jīng)歷如下 3 個(gè)階段。

1）業(yè)委會(huì)主任選舉 —— 領(lǐng)導(dǎo)選舉（Leader Election）

• 業(yè)委會(huì)主任的選舉開(kāi)始了，大家需要從眾多熱心的業(yè)主中選出一位來(lái)?yè)?dān)任這個(gè)角色。
• 就在這時(shí)，業(yè)主張三挺身而出，他告訴大家：“我愿意擔(dān)任業(yè)委會(huì)主任，大家看我行不行”？這就相當(dāng)于 Raft 算法中的一個(gè)節(jié)點(diǎn)（Candidate）發(fā)起了一次領(lǐng)導(dǎo)選舉。
• 隨后，張三需要讓大家投票支持他。如果在規(guī)定的時(shí)間內(nèi)，大多數(shù)業(yè)主（即節(jié)點(diǎn)的多數(shù)）都支持張三，那么張三就當(dāng)選成為了新的業(yè)委會(huì)主任。這個(gè)過(guò)程類似于 Raft 算法中通過(guò)選票獲得多數(shù)同意后，成為 領(lǐng)導(dǎo)者（Leader）。

Candidate 發(fā)送投票消息給其它所有存活節(jié)點(diǎn)，其它節(jié)點(diǎn)會(huì)對(duì)其請(qǐng)求進(jìn)行回復(fù)，如果超過(guò)半數(shù)的節(jié)點(diǎn)回復(fù)了競(jìng)選請(qǐng)求，那么該 Candidate 就會(huì)變成 Leader 節(jié)點(diǎn)。

2）管理社區(qū)大事 —— 日志復(fù)制（Log Replication）

• 當(dāng)張三當(dāng)選為業(yè)委會(huì)主任后，他就要開(kāi)始負(fù)責(zé)社區(qū)的日常大事了，比如決定花園里要種些什么花，什么時(shí)候修繕社區(qū)的健身設(shè)施。
• 張三會(huì)把他的想法寫在公告板上，然后請(qǐng)其他業(yè)主（即其他節(jié)點(diǎn)）照著去做——就像在 Raft 算法中領(lǐng)導(dǎo)者（Leader）把要執(zhí)行的操作作為日志條目（Log Entry）復(fù)制給其它節(jié)點(diǎn)。
• 業(yè)主們看到公告板的內(nèi)容后，會(huì)按照張三的計(jì)劃去執(zhí)行，并把執(zhí)行的情況反饋給張三。這一過(guò)程對(duì)應(yīng)于 Raft 算法中從節(jié)點(diǎn)（Follower）接受并應(yīng)用日志條目，并反饋成功的消息給領(lǐng)導(dǎo)者。

新 Leader 周期性發(fā)送心跳包給 Follower，F(xiàn)ollower 收到心跳包以后重新計(jì)時(shí)。這時(shí)，Leader 如果接收到了客戶端請(qǐng)求，會(huì)將數(shù)據(jù)變更寫入日志中，并把數(shù)據(jù)復(fù)制到所有 Follower。

當(dāng)大多數(shù) Follower 進(jìn)行修改后，將數(shù)據(jù)變更操作提交。然后，Leader 會(huì)通知所有的 Follower 讓它們提交修改，此時(shí)所有節(jié)點(diǎn)的數(shù)據(jù)達(dá)成一致。

3）主任更替 —— 容錯(cuò)和恢復(fù)

• 如果張三因?yàn)槟承┰蛲蝗徊荒軗?dān)任業(yè)委會(huì)主任的職責(zé)了，比如他長(zhǎng)時(shí)間沒(méi)有發(fā)表任何公告或指示，大家就會(huì)認(rèn)為需要再選一個(gè)新的業(yè)委會(huì)主任來(lái)接替張三。
• 這時(shí)候業(yè)主李四站出來(lái)，并說(shuō)：“咱們?cè)賮?lái)選一次主任吧，我愿意嘗試這個(gè)角色”。如果李四也得到了大多數(shù)業(yè)主的支持，那他就會(huì)成為新的業(yè)委會(huì)主任。
• 在這期間，無(wú)論主任是張三還是李四，社區(qū)的日常運(yùn)營(yíng)都要繼續(xù)，這就要求整個(gè)選舉過(guò)程快速進(jìn)行，不影響其他社區(qū)事務(wù)，確保社區(qū)管理不受影響。這和 Raft 算法強(qiáng)調(diào)系統(tǒng)可用性和穩(wěn)定性的目的完全一致。

每個(gè) Follower 都會(huì)接收 Leader 周期性的心跳，一般為 150~300ms，如果一段時(shí)間之后還未收到心跳包，F(xiàn)ollower 就變?yōu)?Candidate，又開(kāi)始重復(fù)第 1）步。

3. Gossip算法

眾所周知，八卦是無(wú)處不在的！Gossip 算法，顧名思義，正是閑話家常、傳聞秘事的大師，就像在某些公司的八卦圈子，你可以在里面聽(tīng)到各種各樣奇葩的公司傳聞。

Gossip 算法在網(wǎng)絡(luò)世界中的角色，就像是各個(gè)小圈子中的消息傳遞者。一開(kāi)始，只有幾個(gè)人知道秘密，然后開(kāi)始低聲嘀咕，緊接著全場(chǎng)都知道了，傳播速度之快，就像病毒一樣，所以它又被稱為流行病算法。

雖然不是每個(gè)圈子都能在相同的時(shí)間得知消息，但最終服務(wù)器群的所有節(jié)點(diǎn)都會(huì)知曉同一個(gè)事實(shí)，Gossip 協(xié)議確保的是分布式集群的最終一致性。

Gossip 協(xié)議被廣泛應(yīng)用于 P2P 網(wǎng)絡(luò)，同時(shí)一些分布式的數(shù)據(jù)庫(kù)，如 Redis 集群的消息同步使用的也是 Gossip 協(xié)議，另一個(gè)重大應(yīng)用是被用于比特幣的交易信息和區(qū)塊鏈里信息的傳播。

圖片

Gossip 協(xié)議在工作時(shí)會(huì)設(shè)定一個(gè)周期時(shí)間 T，以及每個(gè)節(jié)點(diǎn)每個(gè)周期傳播消息的節(jié)點(diǎn)數(shù) K，然后，我們就能大致繪出這個(gè)八卦圈子的傳播路線了：

1. 節(jié)點(diǎn) A 得知了八卦，并立即更新了狀態(tài)。
2. 然后，A 會(huì)把這個(gè)八卦告訴緊挨著的 B 和 C（直連的節(jié)點(diǎn)）。
3. B 和 C 各自把這個(gè)消息告訴自己周圍的小伙伴們，但不會(huì)再傳回給 A。
4. 經(jīng)過(guò)一段時(shí)間，整個(gè)群體都知曉了這個(gè)八卦，達(dá)到了一種奇妙的一致性。

4. 一致性hash算法

一致性哈希（Consistent Hashing）算法，乍一聽(tīng)大家可能覺(jué)得這是高大上的技術(shù)名詞，但其實(shí)它在分布式系統(tǒng)中無(wú)疑是個(gè)解決大難題的土方法，就像是中國(guó)的傳統(tǒng)醫(yī)術(shù)在現(xiàn)代仍能醫(yī)治各種疑難雜癥一樣。

這個(gè)算法自從 1997 年由麻省理工學(xué)院的博士生提出后，就在分布式系統(tǒng)中扮演著至關(guān)重要的角色。一致性哈希算法在分布式系統(tǒng)中的地位可比咱們生活中的在線記賬軟件，解決了數(shù)據(jù)存放位置的大問(wèn)題。

傳統(tǒng)的哈希算法在節(jié)點(diǎn)增減時(shí)面臨著數(shù)據(jù)重新分配的巨大代價(jià)，就像如果你用紙質(zhì)的賬本，每次賬目中間有變動(dòng)（比如，中間有幾天忘了記賬）時(shí)都得整本重寫一遍，想想都頭疼。而一致性哈希通過(guò)精妙地圓環(huán)結(jié)構(gòu)使得節(jié)點(diǎn)變動(dòng)只影響鄰近的一小部分?jǐn)?shù)據(jù)，大大降低了系統(tǒng)維護(hù)的復(fù)雜度。

圖片

說(shuō)到一致性哈希算法的基本概念，想象我們有一張圓桌，桌面上標(biāo)著從 0 到 2^32（假設(shè)用的是 32 位的哈希函數(shù)）的數(shù)字，形成一個(gè)閉環(huán)：

• 每當(dāng)有個(gè)新服務(wù)器來(lái)了，我們就給它一個(gè)或多個(gè)哈希值，讓它在這張圓桌的某個(gè)地方坐下
• 每次我們有數(shù)據(jù)要存儲(chǔ)時(shí)，就按照數(shù)據(jù)的哈希值找到在此值之后的第一個(gè)服務(wù)器，把數(shù)據(jù)放在那兒
• 如果這個(gè)服務(wù)器忙碌了，它會(huì)找一個(gè)最近的鄰居節(jié)點(diǎn)來(lái)幫助存儲(chǔ)數(shù)據(jù)
• 這樣，每當(dāng)服務(wù)器來(lái)來(lái)去去時(shí)，我們只需要重新調(diào)整它們附近的數(shù)據(jù)即可

這個(gè)算法的魅力在于，不管你的網(wǎng)絡(luò)多么巨大，每次添加或刪除一個(gè)節(jié)點(diǎn)，都只涉及到節(jié)點(diǎn)旁邊的一小部分?jǐn)?shù)據(jù)，而不是整個(gè)網(wǎng)絡(luò)。這就像在一個(gè)巨大的停車場(chǎng)里找車位，即便是一個(gè)區(qū)域的停車位滿了，你也不用擔(dān)心其他地區(qū)的車位會(huì)被遷移。

當(dāng)然，這個(gè)算法也有它的缺點(diǎn)。有時(shí)候，所有人似乎都想停在同一個(gè)車位上，這就造成了負(fù)載不均，即哈希環(huán)傾斜的情況。

圖片

這時(shí)，你可能需要一些“虛擬車位”，也即是虛擬節(jié)點(diǎn)，讓這個(gè)停車場(chǎng)的車輛更加均勻地分布。

這種情況我們可以這么理解：項(xiàng)目中某個(gè)區(qū)域的緩存快滿了怎么辦？

那就是加新節(jié)點(diǎn)！

圖片

為了讓緩存數(shù)據(jù)均勻分布，我們通常會(huì)采用哈希后取模的方式來(lái)確定數(shù)據(jù)歸屬的節(jié)點(diǎn)。而在加減節(jié)點(diǎn)的過(guò)程中，一致性哈希算法可以保證大多數(shù) key 照舊停留在原有的車位上，而不需要把整個(gè)車場(chǎng)的車全部重新停一遍。

5. 小結(jié)

本文首先從 Paxos 算法說(shuō)起，其通過(guò)提案和承諾機(jī)制，巧妙地保證在故障頻發(fā)的環(huán)境下達(dá)成一致性。

接著，Raft 算法以其直觀的領(lǐng)導(dǎo)選舉和日志復(fù)制機(jī)制，為分布式一致性提供了通俗易懂的實(shí)現(xiàn)。

Gossip 算法的非正式信息傳播特性，使得數(shù)據(jù)在節(jié)點(diǎn)間傳遞就像病毒般迅速，確保了數(shù)據(jù)的最終一致性。