作者：京東物流 馮鴻儒

1 簡介

Gossip是一種p2p的分散式協議。它的核心是在去中心化結構下，通過將信息部分傳遞，達到全集群的狀態信息傳播，傳播的時間收斂在O（Log（N））以內，其中N是節點的數量。基於gossip協議，可以構建出狀態一致的各種解決方案。
一些常見的分散式協議如二階段提交協議和 Raft 演算法，你發現它們都需要全部節點或者大多數節點正常運行，才能穩定運行。而Gossip即使只有一個節點可用也能提供服務。

1.1 適用場景

適用於AP 場景的數據一致性處理：分散式資料庫中節點同步數據使用（如Apache Cassandra、Redis Cluster）；
其他場景如信息擴散、集群成員身份確認、故障探測等（如Consul）。

1.2 優勢

• 學習成本：實現簡單
• 擴展性：允許節點的任意增加和減少，新增節點的狀態 最終會與其他節點一致。
• 容錯：任意節點的宕機和重啟都不會影響 Gossip 消息的傳播，具有天然的分散式系統容錯特性。可以在一定程度上避免網路分割帶來的問題。
• 去中心化：無需中心節點，所有節點都是對等的，任意節點無需知道整個網路狀況，只要網路連通，任意節點可把消息散播到全網。
• 性能：指數級一致性收斂。消息會以“一傳十的指數級速度”在網路中傳播，因此系統狀態的不一致可以在很快的時間內收斂到一致。消息傳播速度達到了 logN。
  Gossip協議的最大的好處是，即使集群節點的數量增加，每個節點的負載也不會增加很多，幾乎是恆定的。如Consul管理的集群規模能橫向擴展到數千個節點。

1.3 劣勢

• 消息延遲：節點隨機向少數幾個節點發送消息，消息最終是通過多個輪次的散播而到達全網；不可避免的造成消息延遲。
• 消息冗餘：節點定期隨機選擇周圍節點發送消息，而收到消息的節點也會重覆該步驟；不可避免的引起同一節點消息多次接收，增加消息處理壓力。

2 細節介紹

2.1 傳播方式

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

2.1.1 反熵傳播

• 定義：反熵（指消除不同節點中數據的差異，提升節點間數據的相似度，降低熵值）。反熵傳播：以固定的概率傳播所有的數據，可用來避免因為UDP數據包丟失或者新節點的加入而導致的集群元數據不一致問題。
• 過程：集群中的節點，每隔段時間就隨機選擇某個其他節點，然後通過互相交換自己的所有數據來消除兩者之間的差異，實現數據的最終一致性。
• 適用場景：執行反熵時，相關的節點都是已知的，而且節點數量不能太多，如果是一個動態變化或節點數比較多的分散式環境（比如在 DevOps 環境中檢測節點故障，並動態維護集群節點狀態），這時反熵就不適用了。
• 缺點：消息數量非常龐大，且無限制；通常只用於新加入節點的數據初始化。可以通過引入校驗和（Checksum）等機制，降低需要對比的數據量和通訊消息等。

2.1.2 謠言傳播

• 定義：當一個節點有了新數據後，這個節點變成活躍狀態，並周期性地聯繫其他節點向其發送新數據，直到所有的節點都存儲了該新數據。
• 過程：消息只包含最新 update，謠言消息在某個時間點之後會被標記為 removed，並且不再被傳播。
• 當一個新節點A連接到Gossip集群內的某個節點B時，A節點會將自己的信息發送給B節點，然後B節點會在集群中隨機選取幾個未被傳染的節點，向他們廣播A節點的信息（首次傳染），集群中的其他節點收到A節點的信息後，又會像B節點那樣廣播A節點的信息給其他未被傳染的節點（二次傳染）。直至多次傳染後，集群所有節點都收到了A節點的信息，同步完成。
• 適用場景：適合動態變化的分散式系統。
• 缺點：系統有一定的概率會不一致，通常用於節點間數據增量同步。

2.2 通信方式

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 的收斂速度也是最快的。

2.3 執行示例

2.3.1 狀態的傳播

以Gossip協議同步狀態的思路類似於流言的傳播,如下圖所示。

A節點率先知道了某個流言（msg），它首先將此信息傳播到集群中的部分節點（比如相鄰的兩個節點）B和C，後者再將其傳遞到它們所選擇的“部分”節點，例如B選擇了D和E，C選擇了將流言傳播到B和F。以此類推，最終來自於A的這條流言在3輪交互後被傳播到了集群中的所有節點。
在分散式系統的實踐中，這個“流言”可能是：某個節點所感知到的關於其它節點是否宕機的認識；也可能是數據水平拆分的緩存集群中，關於哪些hash桶分佈在哪些節點上的信息。每個節點起初只掌握部分狀態信息，不斷地從其它節點收到gossip信息，每個節點逐漸地掌握到了整個集群的狀態信息。因此解決了狀態同步的第一個問題：全集狀態的獲取。
對於集群中出現的部分網路分割，消息也能通過別的路徑傳播到整個集群。如下圖所示：

2.3.2 狀態的一致

狀態同步的第二個問題：對於同一條狀態信息，不同的節點可能掌握的值不同，也能通過基於gossip通信思路構建的協議包版本得到解決。例如水平拆分的redis緩存集群，初始狀態下hash桶在各個節點的分佈如下圖所示：

此時各個節點預先通過某種協議（比如Gossip）得知了集群的狀態全集，此時新加入了節點D，如下圖所示：

D分擔了C的某個hash桶，此時C/D和集群中其它節點就C所擁有哪些hash這件事發生了分歧：A/B認為C目前有6/7/8個hash桶。此時通過為gossip消息體引入版本號，使得關於C的最新狀態信息（只有6/7兩個桶了）在全集群達到一致。例如B收到來自A和C的gossip消息時會將版本號更新的消息（來自C的v2）更新到自己的本地副本中。
各個節點的本地副本保存的集群全量狀態也可能用來表示各個節點的存活狀態。對於部分網路分割的情況如下圖所示：

例如A和C的網路斷開，但A和C本身都正常運行，此時A和C互相無法通信，C會將A標記為不可用狀態。對於中心化思路的協議，如果C恰好是中心節點，那麼A不可用的信息將會同步到集群的所有節點上，使得這些節點將其實可用的A也標記為宕機。而基於gossip這類去中心化的協議進行接收到消息後的實現邏輯擴展（例如只有當接收到大多數的節點關於A已經宕機的消息時，才更新A的狀態），最終保證A不被誤判為宕機。

3 開源軟體中的應用

3.1 Fabric

Fabric gossip使用push（從成員視圖隨機選出活躍鄰居，給他們轉發消息），pull（定期探測，請求遺失的消息）的方式擴散區塊。

3.2 Cassandra

Cassandra使用的是pull-push，這種方式是均等的，會有3次發送，但是發送完以後雙方都可以更新彼此的信息。利用pull-push方式，如果A要與B節點同步，需要進行如下圖的三個通信階段。

3.3 RedisCluster

Redis Cluster 在運行時，每個實例上都會保存 Slot 和實例的對應關係（也就是 Slot 映射表），以及自身的狀態信息。新節點加入、節點故障、Slot 變更等事件發生時，實例間也可以通過 gossip協議進行PING、PONG 消息的傳遞，完成集群狀態在每個實例上的同步。
redisCluster預設組建集群的方式：

• 通過cluster meet命令將一個節點跟集群中其中一個節點建立連接（此時只能被集群中這一個節點認識）
• 通過Gossip消息轉播給其他節點，其他節點收到消息後，再通過類似meet的命令來跟對新節點建立集群連接（需要一定時間的擴散）

使用gossip演算法利用PFAIL和FAIL flags的轉換和傳播來判定故障

3.4 Consul

一致性協議採用 Raft 演算法,用來保證服務的高可用.
成員管理和消息廣播 採用GOSSIP協議，支持ACL訪問控制。
consul是建立在serf之上的，它提供了一個完整的gossip協議，用在很多地方。Serf提供了成員，故障檢測和事件廣播。Gossip的節點到節點之間的通信使用了UDP協議。
Consul的每個Agent會利用Gossip協議互相檢查線上狀態，本質上是節點之間互Ping，分擔了伺服器節點的心跳壓力。如果有節點掉線，不用伺服器節點檢查，其他普通節點會發現，然後用Gossip廣播給整個集群。

4 總結

gossip協議是很多開源中間件和區塊鏈實現的一種底層通信機制，掌握它的原理和細節能更好的理解中間件和區塊鏈的一些行為和分散式特性。