作者：京東物流 馮鴻儒

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協議是很多開源中間件和區塊鏈實作的一種底層通信機制，掌握它的原理和細節能更好的理解中間件和區塊鏈的一些行為和分布式特性，

標籤：架構設計

上一篇：如何創建干凈的C++工程

下一篇：資料同步gossip協議原理與應用場景介紹