引言

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

1. Paxos 算法

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

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

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

業務場景

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

1. 準備階段（Prepare）:

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

2. 批準階段（Accept）:

• 當候選董事 A 收到了多數董事會成員的承諾后，它會向那些承諾過的成員發送詳細的提案內容。

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

3. 學習階段（Learn）:

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

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

在這過程中，Paxos 算法又將系統中的節點分為三類：

圖片

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

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

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

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

2. Raft 算法

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

• 領頭結點 Leader
• 從節點 Follower
• 候選節點 Candidate

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

1）業委會主任選舉 —— 領導選舉（Leader Election）

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

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

2）管理社區大事 —— 日志復制（Log Replication）

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

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

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

3）主任更替 —— 容錯和恢復

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

每個 Follower 都會接收 Leader 周期性的心跳，一般為 150~300ms，如果一段時間之后還未收到心跳包，Follower 就變為 Candidate，又開始重復第 1）步。

3. Gossip算法

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

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

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

Gossip 協議被廣泛應用于 P2P 網絡，同時一些分布式的數據庫，如 Redis 集群的消息同步使用的也是 Gossip 協議，另一個重大應用是被用于比特幣的交易信息和區塊鏈里信息的傳播。

圖片

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

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

4. 一致性hash算法

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

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

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

圖片

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

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

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

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

圖片

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

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

那就是加新節點！

圖片

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

5. 小結

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

接著，Raft 算法以其直觀的領導選舉和日志復制機制，為分布式一致性提供了通俗易懂的實現。

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