起源

Gossip protocol 也叫 Epidemic Protocol （流行病協議），是基于流行病傳播方式的節點或者進程之間信息交換的協議。。Gossip protocol在1987年8月由施樂公司帕洛阿爾托研究中心研究員艾倫·德默斯（Alan Demers）發表在ACM上的論文《Epidemic Algorithms for Replicated Database Maintenance》中被提出。

Gossip協議是基于六度分隔理論（Six Degrees of Separation）哲學的體現，簡單的來說，一個人通過6個中間人可以認識世界任何人。數學公式是：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?

n表示復雜度，N表示人的總數，W表示每個人的聯系寬度。依據鄧巴數，即每個人認識150人，其六度就是1506 ＝11,390,625,000,000（約11.4萬億）。

基于六度分隔理論，任何信息的傳播其實非常迅速，而且網絡交互次數不會很多。比如Facebook在2016年2月4號做了一個實驗：研究了當時已注冊的15.9億使用者資料，發現這個神奇數字的“網絡直徑”是4.57，翻成白話文意味著每個人與其他人間隔為4.57人。

基礎原理

Gossip協議在計算機系統通常以隨機的“對等選擇”形式實現：以給定的頻率，每臺計算機隨機選擇另一臺計算機，并共享任何消息。定義十分簡單，所以實現方式非常多，可能有幾百種Gossip協議變種。因為每個使用場景都可能根據組織的特定需求進行定制，維基百科上這樣寫：

There are probably hundreds of variants of specific Gossip-like protocols because each use-scenario is likely to be customized to the organization's specific needs.

下文解說一種比較原始的Gossip協議實現的執行過程、消息類型、通訊方式，以下為Gossip協議執行過程：

種子節點周期性的散播消息 【假定把周期限定為 1 秒】。

被感染節點隨機選擇N個鄰接節點散播消息【假定fan-out(扇出)設置為6，每次最多往6個節點散播】。

節點只接收消息不反饋結果。

每次散播消息都選擇尚未發送過的節點進行散播。

收到消息的節點回傳散播：A -> B，那么B進行散播的時候，不再發給 A。

?

Goosip 協議的信息傳播和擴散通常需要由種子節點發起。整個傳播過程可能需要一定的時間，由于不能保證某個時刻所有節點都收到消息，但是理論上最終所有節點都會收到消息，因此它是一個最終一致性協議。

Gossip協議是一個多主協議，所有寫操作可以由不同節點發起，并且同步給其他副本。Gossip內組成的網絡節點都是對等節點，是非結構化網絡。

消息類型

Gossip 協議的消息傳播方式有兩種：Anti-Entropy(反熵傳播)和Rumor-Mongering(謠言傳播)。

反熵傳播使用“simple epidemics(SI model)”的方式：以固定的概率傳播所有的數據。所有參與節點只有兩種狀態：

Suspective(病原)：處于 susceptible 狀態的節點代表其并沒有收到來自其他節點的更新。

Infective(感染)：處于 infective 狀態的節點代表其有數據更新，并且會將這個數據分享給其他節點。

反熵傳播過程是每個節點周期性地隨機選擇其他節點，然后通過互相交換自己的所有數據來消除兩者之間的差異。

反熵傳播方法每次節點兩兩交換自己的所有數據會帶來非常大的通信負擔，因此不會頻繁使用，通常只用于新加入節點的數據初始化。

謠言傳播使用“complex epidemics”(SIR model)的方式:以固定的概率僅傳播新到達的數據。所有參與節點有三種狀態：Suspective(病原)、Infective(感染)、Removed(愈除)。

Removed(愈除):其已經接收到來自其他節點的更新，但是其并不會將這個更新分享給其他節點。

謠言傳播過程是消息只包含最新 update，謠言消息在某個時間點之后會被標記為removed，并且不再被傳播。缺點是系統有一定的概率會不一致，通常用于節點間數據增量同步。

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

通訊方式

Gossip 協議最終目的是將數據分發到網絡中的每一個節點。不管是 Anti-Entropy 還是 Rumor-Mongering 都涉及到節點間的數據交互方式，Gossip網絡中兩個節點之間存在三種通信方式：Push、Pull 以及 Push&Pull：

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

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

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

如果把兩個節點數據同步一次定義為一個周期，則在一個周期內，Push 需通信 1 次，Pull 需 2 次，Push/Pull 則需 3 次。雖然消息數增加了，但從效果上來講，Push/Pull 最好，理論上一個周期內可以使兩個節點完全一致。直觀上，Push/&Pull 的收斂速度也是最快的。

總結

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

?

Gossip是一種去中心化的分布式協議，數據通過節點像病毒一樣逐個傳播。因為是指數級傳播，整體傳播速度非常快，很像現在美國失控的2019-nCoV(新冠)一樣。它具備以下優勢：

可擴展性（Scalable）：允許節點的任意增加和減少，新增節點的狀態最終會與其他節點一致。

容錯（Fault-tolerance）：網絡中任何節點的重啟或者宕機都不會影響 gossip 協議的運行，具有天然的分布式系統容錯特性。

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

最終一致性（Convergent consistency）：謠言傳播可以是指數級的快速傳播，因此新信息傳播時，消息可以快速地發送到全局節點，在有限的時間內能夠做到所有節點都擁有最新的數據。

簡單

同樣也存在以下缺點：

消息延遲：節點隨機向少數幾個節點發送消息，消息最終是通過多個輪次的散播而到達全網，不可避免的造成消息延遲。

消息冗余：節點定期隨機選擇周圍節點發送消息，而收到消息的節點也會重復該步驟，因此不可避免地引起同一節點多次接收同一消息，增加消息處理的壓力。一次通信會對網路帶寬、CUP資源造成很大的負載，而這些負載又受限于 通信頻率，該頻率又影響著算法收斂的速度。

拜占庭問題：如果有一個惡意傳播消息的節點，Gossip協議的分布式系統就會出問題。

上述優缺點的本質是因為Gossip是一個帶冗余的容錯算法，是一個最終一致性算法，雖然無法保證在某個時刻所有節點狀態一致，但可以保證在“最終所有節點一致”，“最終”的時間是一個理論無法明確的時間點。所以適合于AP場景的數據一致性處理，常見應用有：P2P網絡通信、Apache Cassandra、Redis Cluster、Consul

?注：Consistency（一致性）、 Availability（可用性）、Partition tolerance（分區容錯性）

?

總結

以上是生活随笔為你收集整理的Gossip协议详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。