gossip：藉助流言蜚語實現數據一致性

楔子

在上一篇文章中我們介紹了 CAP 理論和 BASE 理論，其中 BASE 理論廣泛應用在大型互聯網的後臺當中，它的核心思想就是基本可用和最終一致性。但是問題來了，數據如何才能達成最終一致呢？而這就是本文的主題，通過 gossip 協議實現數據的最終一致。

什麼是 gossip 協議

gossip 翻譯過來是謠言，所以該協議的特點也顯而易見，就是利用一種隨機並帶有傳染性的方式，將信息傳播到網絡中。最終像流言蜚語一樣，一傳十十傳百，經過一定時間後，使得集羣內所有節點的數據達成一致。

可能有人覺得這種方式無法保證可靠性啊，是的，gossip 協議不保證可靠性。它的行爲類似 COVID-19，就是不斷地傳播，直到所有人都感染爲止。

而 gossip 實現最終一致性主要有三種方式：

下面我們來分別解釋這三種方式。

直接郵寄

首先是直接郵寄，它比較簡單，就是直接發送更新數據，當數據發送失敗時，將數據緩存下來，然後重傳。

直接郵寄實現起來比較容易，數據同步也很及時，但可能會因爲緩存隊列滿了而丟數據。也就是說，只採用直接郵寄是無法實現最終一致性的。

反熵

反熵是一種通過異步修復實現最終一致性的方法，它指的是集羣中的節點，每隔一段時間就隨機選擇某個其它節點，然後通過互相交換自己的所有數據來消除兩者之間的差異，實現數據的最終一致性。

gossip 協議的反熵每次是隨機選擇，但實際生產上也可以不這麼做。

常見的最終一致性系統（比如 Cassandra），都實現了反熵功能。

假設集羣中的 A 節點選擇了 D 節點，然後兩者交換數據，實現反熵。而實現方式有三種：

也許有很多人會覺得反熵是一個很奇怪的名詞（個人覺得很酷），但其實很好理解。首先熵這個概念我們在化學課上學過，它表示物體的混亂程度，一個孤立的體系總是沿着熵增大的方向。

而對於當前而言，熵則代表兩個節點之間的數據差異，差異越大則熵越大。所以反熵就是採取一些措施，來消除節點之間的數據差異，降低熵值。否則的話，節點之間的數據差異就會越來越大，因爲自然情況下總是沿着熵增大的方向。

實驗表明，反熵雖然可靠，但因爲需要節點之間兩兩交換和對比所有的副本數據，所以執行反熵時通訊成本會很高，導致傳播更新的速度比直接郵寄慢得多。因此不建議在實際場景中頻繁執行反熵，而是可以通過引入校驗和（Checksum）等機制，降低需要對比的數據量和通訊消息等。

另外執行反熵的時候還需要滿足一個條件，就是相關的節點都是已知的，而且節點數量不能太多。如果在一個動態變化或節點數比較多的分佈式環境（比如在 DevOps 環境中檢測節點故障，並動態維護集羣節點狀態），這時反熵就不適用了。那麼當面臨這個情況要怎樣實現最終一致性呢？答案就是謠言傳播。

謠言傳播

很好理解，它指的是當一個節點有了新數據後，這個節點變成活躍狀態（被感染了），並週期性地向其它節點（還未被感染）發送新數據，將其感染。然後其它節點再向其它節點發送，直到所有的節點都存儲了新數據。

比如小 A 和小 B 在一起喫飯，碰巧被小 C 看到了，然後小 C 告訴小 D 了，小 D 再告訴別人。就這樣到四處傳播，到最後大家都知道了，小 A 和小 B 在一起喫飯這件事。

所以反熵和謠言傳播之間的區別就是，前者需要傳遞所有的數據，而後者只需要傳遞新數據，而且一個人可以同時傳遞給多個人。

但需要注意的是，謠言傳播有以下幾個特點：

可以看到謠言傳播非常適合動態變化的分佈式系統，那麼它的優缺點是什麼呢？

優點：

1）可擴展性：擴展性極好，允許節點的任意增加和減少，新增加的節點的狀態最終會與其他節點一致，並且只需要 O(logN) 輪就可以將信息傳播到所有的節點。這就允許集羣管理的節點規模能橫向擴展到幾千幾萬個，而集羣內的消息通信成本卻不會增加很多。

2）容錯能力：網絡中任何節點的宕機和重啓都不會影響消息的傳播，具有天然的分佈式系統容錯特性。

3）去中心化：不要求任何中心節點，所有節點都是對等的，並且節點無需知道整個網絡狀況，只要網絡是連通的，任意一個節點都可以把消息散播到全網。所以這就使得任何節點出現問題都不會阻止其它節點繼續發送消息，節點可以隨時加入或離開，而不會影響系統的整體服務質量。

4）一致性收斂：消息會以一傳十、十傳百一樣的指數級速度在網絡中快速傳播，因此係統狀態的不一致可以在很快的時間內收斂到一致，消息傳播速度達到了 logN 級別。

缺點：

1）消息延遲：節點隨機向少數幾個節點發送消息，消息最終是通過多個輪次的傳播而到達全網，不可避免會造成消息延遲。不適合於對實時性要求較高的場景。

2）消息冗餘：節點會定期隨機選擇周圍節點發送消息，而收到消息的節點也會重複該步驟，因此就不可避免的存在消息重複發送給同一節點的情況，造成了消息的冗餘，同時也增加了收到消息的節點的處理壓力。比如小 C 將消息告訴了小 D，雖然小 D 不會再告訴小 C，但它告訴小 E 之後，小 E 可能會再告訴小 C。因此小 C 就出現了消息冗餘，它要額外處理已經知道的消息。

3）拜占庭將軍問題：如果有惡意傳播消息的節點，Gossip 協議的分佈式系統就會出問題。當然如果不是做區塊鏈的話，那麼拜占庭將軍問題不需要太擔心，因爲我們平時使用的分佈式系統，節點之間都是可信賴的，也就是說可能會丟失消息，或者有消息重複，但不存在錯誤消息，或者僞造消息的情況。但要是在數字貨幣的區塊鏈當中的話，則必須要考慮這一點，因爲除了存在故障行爲，還存在惡意行爲，所以必須使用拜占庭容錯算法。

拜占庭將軍問題描述的是最困難的、也是最複雜的一種分佈式故障場景。

通過對比優缺點不難看出，達到一致性耗費的時間與網絡傳播中的消息冗餘量這兩個缺點存在一定對立，如果要改善其中一個，就會惡化另外一個。因此 gossip 設計出了可以互補的反熵和謠言傳播兩種方式。

其中反熵我們已經說過了，它的意思就是反混亂，以提升各個節點數據之間的相似度爲目標。所以在反熵模式下，會同步節點的全部數據，以消除節點之間的差異，目標是讓所有節點的數據完全一致。但它要求節點數量都是已知的，而且節點數量不能過多，否則會使得整個網絡中消息的數量變得非常龐大，給網絡帶來巨大的傳輸開銷。

因此反熵不能夠頻繁執行，於是就有了謠言傳播。謠言傳播僅僅發送新到達節點的數據，也就是隻對外發送變更信息，這樣消息數據量將顯著縮減，網絡開銷也相對較小。並且謠言傳播不需要節點都是已知的，正如兩個小情侶也不認識全校所有的人，但如果兩人偷偷接吻，被一個人看到了，很可能就全校都知道了。

通過反熵和謠言傳播互相搭配，就能以最小的代價實現節點之間的數據一致。

小結

在實際場景中，實現數據副本的最終一致性時，一般而言，直接郵寄的方式是一定要實現的，因爲不需要做一致性對比，只是通過發送更新數據或緩存重傳，來修復數據的不一致，性能損耗低。

如果在存儲組件中，節點都是已知的（並且不多），一般採用反熵修復數據副本的一致性。而且在選擇節點的時候，不一定非要按照 gossip 協議中說的隨機選擇，可以按照固定的順序，比如修到最後可以形成一個閉環。

另外使用反熵實現最終一致性時，需要通過一致性檢測發現數據副本的差異，而這是比較消耗性能的。因此可以考慮通過記錄節點數據是否變化，來進行增量對比。

但如果節點數量是變化的，或者節點數量很多時，就需要採用謠言傳播的方式，同步更新數據，實現最終一致（當然此時反熵也是需要有的，但不要頻繁執行）。

最後有一個網站，能夠以動畫的形式模擬 gossip 協議的同步過程。

https://flopezluis.github.io/gossip-simulator/

可以點進去玩一玩。

本文參考自：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ocZW6-iw5nY65LyL70uDHQ

猜你喜歡