引言

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

1. Paxos 算法

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

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

它通過一系列的提議（proposal）和承諾（promise）來保證最終的一致性。

業(yè)務(wù)場景

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

1. 準備階段（Prepare）:

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

2. 批準階段（Accept）:

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

• 如果這些董事會成員沒有對更高編號的提案做出過承諾，它們就會接受這個提案。

3. 學習階段（Learn）:

• 一旦提案被多數(shù)董事會成員批準，這個候選人就被選為新董事，每個董事會成員會記錄下來這個結(jié)果。

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

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

圖片

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

提議的時候，包含倆字段：[n, v]，其中 n 為序號，v 為提議值。每個 Aceeptor 在接收提議請求的時候，會比對其中的序號 n：

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

當一個 Proposer 接收到超過半數(shù)的 Aceeptor 響應(yīng)時，說明該提議值被 Paxos 選擇了出來，這時候，由 Acceptor 負責通知給所有的 Learner。

2. Raft 算法

引入主節(jié)點，通過競選來獲取主節(jié)點。節(jié)點分為三類：

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

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

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

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

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

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

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

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

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

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

• 如果張三因為某些原因突然不能擔任業(yè)委會主任的職責了，比如他長時間沒有發(fā)表任何公告或指示，大家就會認為需要再選一個新的業(yè)委會主任來接替張三。
• 這時候業(yè)主李四站出來，并說：“咱們再來選一次主任吧，我愿意嘗試這個角色”。如果李四也得到了大多數(shù)業(yè)主的支持，那他就會成為新的業(yè)委會主任。
• 在這期間，無論主任是張三還是李四，社區(qū)的日常運營都要繼續(xù)，這就要求整個選舉過程快速進行，不影響其他社區(qū)事務(wù)，確保社區(qū)管理不受影響。這和 Raft 算法強調(diào)系統(tǒng)可用性和穩(wěn)定性的目的完全一致。

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

3. Gossip算法

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

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

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

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

圖片

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

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

4. 一致性hash算法

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

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

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

圖片

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

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

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

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

圖片

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

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

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

圖片

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

5. 小結(jié)

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

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

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