分布式原理：一文了解 Gossip 協議

gossip 協議（gossip protocol）又稱 epidemic 協議（epidemic protocol），是基于流行病傳播方式的節點或者進程之間信息交換的協議，在分布式系統中被廣泛使用，比如我們可以使用 gossip 協議來確保網絡中所有節點的數據一樣。

從 gossip 單詞就可以看到，其中文意思是八卦、流言等意思，我們可以想象下緋聞的傳播（或者流行病的傳播）；gossip 協議的工作原理就類似于這個。gossip 協議利用一種隨機的方式將信息傳播到整個網絡中，并在一定時間內使得系統內的所有節點數據一致。Gossip 其實是一種去中心化思路的分布式協議，解決狀態在集群中的傳播和狀態一致性的保證兩個問題。

gossip 優勢

可擴展性（Scalable）

gossip 協議是可擴展的，一般需要 O（logN）輪就可以將信息傳播到所有的節點，其中 N 代表節點的個數。每個節點僅發送固定數量的消息，并且與網絡中節點數目無法。在數據傳送的時候，節點并不會等待消息的 ack，所以消息傳送失敗也沒有關系，因為可以通過其他節點將消息傳遞給之前傳送失敗的節點。系統可以輕松擴展到數百萬個進程。

容錯（Fault-tolerance）

網絡中任何節點的重啟或者宕機都不會影響 gossip 協議的運行。

健壯性（Robust）

gossip 協議是去中心化的協議，所以集群中的所有節點都是對等的，沒有特殊的節點，所以任何節點出現問題都不會阻止其他節點繼續發送消息。任何節點都可以隨時加入或離開，而不會影響系統的整體服務質量（QOS）

最終一致性（Convergent consistency）

Gossip 協議實現信息指數級的快速傳播，因此在有新信息需要傳播時，消息可以快速地發送到全局節點，在有限的時間內能夠做到所有節點都擁有最新的數據。

gossip 協議的類型

前面說了節點會將信息傳播到整個網絡中，那么節點在什么情況下發起信息交換？這就涉及到 gossip 協議的類型。目前主要有兩種方法：

Anti-Entropy（反熵）：以固定的概率傳播所有的數據

Rumor-Mongering（謠言傳播）：僅傳播新到達的數據

Anti-Entropy

Anti-Entropy 的主要工作方式是：每個節點周期性地隨機選擇其他節點，然后通過互相交換自己的所有數據來消除兩者之間的差異。Anti-Entropy 這種方法非常可靠，但是每次節點兩兩交換自己的所有數據會帶來非常大的通信負擔，以此不會頻繁使用。

Anti-Entropy 使用“simple epidemics”的方式，所以其包含兩種狀態：susceptible 和 infective，這種模型也稱為 SI model。處于 infective 狀態的節點代表其有數據更新，并且會將這個數據分享給其他節點；處于 susceptible 狀態的節點代表其并沒有收到來自其他節點的更新。

Rumor-Mongering

Rumor-Mongering 的主要工作方式是：當一個節點有了新的信息后，這個節點變成活躍狀態，并周期性地聯系其他節點向其發送新信息。直到所有的節點都知道該新信息。因為節點之間只是交換新信息，所有大大減少了通信的負擔。

Rumor-Mongering 使用“complex epidemics”方法，相比 Anti-Entropy 多了一種狀態：removed，這種模型也稱為 SIR model。處于 removed 狀態的節點說明其已經接收到來自其他節點的更新，但是其并不會將這個更新分享給其他節點。

因為 Rumor 消息會在某個時間標記為 removed，然后不會發送給其他節點，所以 Rumor-Mongering 類型的 gossip 協議有極小概率使得更新不會達到所有節點。

一般來說，為了在通信代價和可靠性之間取得折中，需要將這兩種方法結合使用。

gossip 協議的通訊方式

不管是 Anti-Entropy 還是 Rumor-Mongering 都涉及到節點間的數據交互方式，節點間的交互方式主要有三種：Push、Pull 以及 Push&Pull。

Push：發起信息交換的節點 A 隨機選擇聯系節點 B，并向其發送自己的信息，節點 B 在收到信息后更新比自己新的數據，一般擁有新信息的節點才會作為發起節點。

Pull：發起信息交換的節點 A 隨機選擇聯系節點 B，并從對方獲取信息。一般無新信息的節點才會作為發起節點。

Push&Pull：發起信息交換的節點 A 向選擇的節點 B 發送信息，同時從對方獲取數據，用于更新自己的本地數據。

gossip 算法實現

Gossip 協議是按照流言傳播或流行病傳播的思想實現的，所以，Gossip 協議的實現算法也是很簡單的，下面分別是 Anti-Entropy 和 Rumor-Mongering 的實現偽代碼。