鼴鼠也愛講八卦? Gossip Protocol：分散式系統中的「傳染病」傳播學

鼴鼠愛八卦

一、 前言：規模化的煩惱

當蚯蚓漢堡的分店不斷擴張，分店數來到了 10,000 家！在此情況下，總部的鼴鼠經理沒有辦法一家一家打電話，通知所有分店「菜單漲價」的消息。如果所有資訊都只能從總部發出，除了會大幅增加總部的人力需求以及時間成本之外，一旦總部發生斷網，全世界的分店都將變成資訊孤島，只能悶著頭自己賣自己的漢堡。

為此，鼴鼠需要引入 Gossip Protocol 來改善資訊傳播的效率。不靠總部，讓分店之間能夠像傳八卦一樣，「菜單漲價」的消息能夠在幾秒鐘內就傳遍全世界。

二、 八卦的傳播藝術：推、拉與雙向對話

透過傳染病模型 (Epidemic Model)，訊息能夠在地底世界迅速地像病毒一樣擴散，例如，當總部發出「菜單漲價」的消息給鄰近的三家分店，接下來，這三家分店繼續將「菜單漲價」的消息傳給鄰近的三家分店，以此類推。數學告訴我們，只要經過短短 7 至 9 輪的傳遞，就能夠讓消息傳遍 10,000 家分店。

然而，隨著知道「菜單漲價」的消息的分店數量越來越多，如果各分店繼續隨機地找三家分店來講八卦，會導致一直通知到已經知道消息的店家，不但浪費時間也浪費電話費，因此，發展出三大講八卦戰術：

• Push（主動推播）：剛收到總部通知「菜單漲價」的台北店，見人就說！適用於訊息剛產生的「爆發期」。
• Pull（被動拉取）：通常在八卦傳遞的尾聲才啟動，邊緣分店主動問鄰近的分店：「最近有啥新鮮事？」，適用於補足最後的資訊死角。
• Push-Pull（雙向交換）：最有效率的模式，兩家分店一通話就直接「交換清單」，互補有無，彼此都能更新到最新的消息。

為什麼只要短短 7 至 9 輪的傳遞就能夠傳遍地底世界的 10,000 家，我們可以算一下這場「地底八卦」的擴散速度。假設每一輪，知道消息的鼴鼠經理會打電話給 3 家還不知道消息的鼴鼠經理（假設鼴鼠經理很聰明，總是能找到不知道消息的分店）（扇出值 f = 3） ：

• 第 0 輪： 只有總部 1 位鼴鼠經理知道 。
• 第 1 輪： 總部告訴 3 位鼴鼠經理，現在有 1 + 3 = 4 隻鼴鼠經理知道（也就是 4¹） 。
• 第 2 輪： 這 4 位鼴鼠經理再分別去告訴 3 位不知道的鼴鼠經理，因為每位知情者再通知 3 位新人，所以知道的人數變成了 4 × 4 = 16 位（也就是 4²） 。
• 第 3 輪： 16 × 4 = 64 位（4³） 。
• ...
• 第 7 輪： 4⁷ = 16,384 位鼴鼠經理都知道了最新消息！

在數學模型中，我們假設每位鼴鼠經理都很聰明，總能找到「還不知道消息」的鄰居。但在現實的地底世界中，兩隻鼴鼠很有可能同時跑去告訴同一隻鼴鼠「菜單漲價了」，這種「訊息碰撞」會稍微拖慢一點速度。這就是為什麼在實務上，我們會說大約需要 7 至 9 輪 。即便如此，這依然比總部自己慢慢一家一家打電話更快速、且更穩健（就算其中幾隻鼴鼠經理偷懶不上班，消息還是能透過其他路徑傳出去！） 。

三、 反熵機制：不容許一絲混亂的「默克爾樹」

雖然 Gossip 協議能讓八卦在地底世界迅速傳開，但總有幾位鼴鼠經理因為「不想上班」或「隧道坍塌」而錯過了最新消息。當八卦的傳播結束後，我們要如何確保 10,000 家分店都獲得了最新消息？此時我們要請出 反熵 (Anti-Entropy) 機制——它不是為了快，而是為了「準」。

超級對帳工具 默克爾樹 (Merkle Tree)：如果兩家分店要對帳，必須把過去十年的「蚯蚓交易清單」逐筆唸給對方聽，那等到唸完大家都下班了。聰明的鼴鼠經理會使用一種叫 「默克爾樹」 的數位指紋技術，來快速比對雙方的資訊是否對齊。

雜湊 (Hash) 的威力： 鼴鼠會將每筆交易透過演算法濃縮成一個短代碼（Hash），然後兩兩成對，再算一次代碼，直到最後形成唯一的「樹根（Root Hash）」。這就像檢查貨箱外的條碼，而不是拆開每個箱子慢慢數蚯蚓的數量到底對不對，因此，當兩家分店的鼴鼠經理見面時，如果比對手上的「總樹根條碼」發現一模一樣，那就代表兩家分店的數萬筆資料完全一致，可以安心去喝咖啡了。

默克爾樹示意圖

如果鼴鼠經理比對「總樹根條碼」後發現不一樣，默克爾樹 提供了簡單的對帳方法，由於「總樹根條碼」是由「左子條碼」與「右子條碼」合併計算出來的，他們只需要向對方索取下一層的左子條碼與右子條碼，比對後排除相同的那半邊，再向對方索取下一層的兩個子條碼，透過重複執行「比對 → 排除一半 → 往下一層」，就能夠以 O(log N) 的超高速找出到底是哪一筆訂單有問題。

反熵機制通常在背景安靜執行，它是分散式系統達成「最終一致性」的最後一道防線，確保系統不會因為資料的累積而變得越來越混亂。

四、 死亡偵測：這家分店還在營業嗎？

在擁有 10,000 家蚯蚓漢堡分店的地底世界中，每天都有隧道塌方或是鼴鼠經理請假等的突發狀況。如果某間分店倒閉了（Node Failure），總部必須第一時間知道，否則還一直把訂單送過去，這些訂單也永遠不會有鼴鼠處理，將會大大降低我們蚯蚓漢堡的營運效率。但在大規模集群中，我們如何判定某間店是真的倒閉，還是只是暫時收訊不好？

傳統做法是所有分店每秒都向總部發一通「我還活著」的簡訊（Heartbeat）。然而， 當規模來到 10,000 家時，總部一秒鐘會收到一萬通簡訊，這種 O(N) 的網路流量肯定會讓總部的頻寬被塞爆而瞬間癱瘓。更何況，如果我們想讓「每家店都知道彼此的死活」而不依靠總部，傳統做法會變成每一家店都去問候其他所有店，在 10,000 個節點的規模下，每秒會產生 一億通 (O(N²)) 的訊息量，真是太可怖了！

地底的互助偵測法 SWIM 協議：鼴鼠帝國採用更聰明的 SWIM (Scalable Weakly-consistent Infection-style Process Group Membership Protocol) 協議，不靠總部監視各分店的死活，而是靠「鄰居互查」，舉例來說：

1. 直接探測： 台北分店隨機問一家分店（例如，高雄分店）：「在嗎？」
2. 間接確認： 如果高雄沒回，台北不會立刻宣判它死亡（可能只是因隧道坍塌而收不到訊號）。台北會請隨機兩家鄰近的分店幫忙問：「請求支援，你們連得到高雄嗎？」
3. 懷疑機制 (Suspicion)： 如果三家分店都聯繫不到高雄，高雄就會進入「被懷疑」狀態。此時高雄還有一個反駁的機會，只要它在限定時間內發出聲明「我只是剛好因為隧道坍塌收不到訊號」，系統就會撤銷「被懷疑」的標籤。

懷疑時間要多久才合理？這是一場關於「敏感度」的拉鋸戰：

• 懷疑時間太短： 系統反應超快，但誤判率飆升，分店整天在廣播澄清「我還活著」，使得地底世界的通訊系統仍然被塞爆。
• 懷疑時間太長： 系統很穩，但某間分店倒閉了半小時大家才發現，送給這家分店的訂單全都報銷。

因此，鼴鼠經理需要根據各家分店的實際運作情況，透過設定合適的「懷疑時間」，來取得「反應速度」與「判定準確度（或誤判率）」的平衡，進而維持整個帝國的運作韌性。

五、 結語：在混亂中建立秩序

從訊息擴散、數據對帳到故障偵測，蚯蚓漢堡體系在地底世界展示了分布式系統的精髓：

• 流言 (Gossip) 負責擴散速度。
• 反熵 (Anti-Entropy) 負責最終一致性。
• SWIM 負責集群健康。

只要透過個體之間簡單的八卦傳遞、條碼對帳與鄰居互助確認，即使沒有無所不知的中央總部，我們依然能在充滿不確定性的地底世界維持秩序。去中心化的韌性，正是現代分散式系統最核心的設計哲學。