分布式原理：一文了解 Gossip 協(xié)議

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

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

gossip 優(yōu)勢

可擴展性（Scalable）

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

容錯（Fault-tolerance）

網(wǎng)絡中任何節(jié)點的重啟或者宕機都不會影響 gossip 協(xié)議的運行。

健壯性（Robust）

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

最終一致性（Convergent consistency）

Gossip 協(xié)議實現(xiàn)信息指數(shù)級的快速傳播，因此在有新信息需要傳播時，消息可以快速地發(fā)送到全局節(jié)點，在有限的時間內能夠做到所有節(jié)點都擁有最新的數(shù)據(jù)。

gossip 協(xié)議的類型

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

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

Rumor-Mongering（謠言傳播）：僅傳播新到達的數(shù)據(jù)

Anti-Entropy

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

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

Rumor-Mongering

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

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

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

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

gossip 協(xié)議的通訊方式

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

Push：發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B，并向其發(fā)送自己的信息，節(jié)點 B 在收到信息后更新比自己新的數(shù)據(jù)，一般擁有新信息的節(jié)點才會作為發(fā)起節(jié)點。

Pull：發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B，并從對方獲取信息。一般無新信息的節(jié)點才會作為發(fā)起節(jié)點。

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

gossip 算法實現(xiàn)

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