來源 | 架構之美

責編 | 寇雪芹

頭圖 | 下載于視覺中國

起源

Gossip protocol 也叫 Epidemic Protocol （流行病協議）。Gossip protocol在1987年8月由施樂-帕洛阿爾托研究中心發表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協議執行過程：

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

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

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

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

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

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

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

消息類型

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

反熵傳播是以固定的概率傳播所有的數據。所有參與節點只有兩種狀態：Suspective(病原)、Infective(感染)。這種節點狀態又叫做simple epidemics(SI model)。過程是種子節點會把所有的數據都跟其他節點共享，以便消除節點之間數據的任何不一致，它可以保證最終、完全的一致。缺點是消息數量非常龐大，且無限制；通常只用于新加入節點的數據初始化。

謠言傳播是以固定的概率僅傳播新到達的數據。所有參與節點有三種狀態：Suspective(病原)、Infective(感染)、Removed(愈除)。這種節點狀態又叫做complex epidemics(SIR model)。過程是消息只包含最新 update，謠言消息在某個時間點之后會被標記為 removed，并且不再被傳播。缺點是系統有一定的概率會不一致，通常用于節點間數據增量同步。

通信方式

Gossip 協議最終目的是將數據分發到網絡中的每一個節點。根據不同的具體應用場景，網絡中兩個節點之間存在三種通信方式：推送模式、拉取模式、Push/Pull。

• Push: 節點 A 將數據 (key,value,version) 及對應的版本號推送給 B 節點，B 節點更新 A 中比自己新的數據

• Pull：A 僅將數據 key, version 推送給 B，B 將本地比 A 新的數據（Key, value, version）推送給 A，A 更新本地

• Push/Pull：與 Pull 類似，只是多了一步，A 再將本地比 B 新的數據推送給 B，B 則更新本地

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

總結

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

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

• 容錯：任意節點的宕機和重啟都不會影響 Gossip 消息的傳播，具有天然的分布式系統容錯特性。

• 去中心化：無需中心節點，所有節點都是對等的，任意節點無需知道整個網絡狀況，只要網絡連通，任意節點可把消息散播到全網。

• 一致性收斂：消息會以“一傳十的指數級速度”在網絡中傳播，因此系統狀態的不一致可以在很快的時間內收斂到一致。消息傳播速度達到了 logN。

• 簡單。

同樣也存在以下缺點：

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

• 消息冗余：節點定期隨機選擇周圍節點發送消息，而收到消息的節點也會重復該步驟；不可避免的引起同一節點消息多次接收，增加消息處理壓力。

綜上所述，Gossip協議可以用于AP場景的數據一致性處理，常見應用有：P2P網絡通信、Apache Cassandra、Redis Cluster、Consul等。

更多閱讀推薦

• 看穿容器的外表，Linux容器實現原理演示

• 用三國殺講分布式算法，舒適了吧？

• 云原生體系下的技海浮沉

• 如何通過 Serverless 輕松識別驗證碼？
  

• 5G與金融行業融合應用的場景探索

總結

以上是生活随笔為你收集整理的信息如何实现病毒式传播？一文看懂Gossip协议的全部內容，希望文章能夠幫你解決所遇到的問題。

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