背景

Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議）舆蝴，實(shí)際上它還有很多別名，比如：“流言算法”丢氢、“疫情傳播算法”等聊记。

這個(gè)協(xié)議的作用就像其名字表示的意思一樣，非常容易理解召娜，它的方式其實(shí)在我們?nèi)粘Ｉ钪幸埠艹Ｒ娫送剩热珉娔X病毒的傳播，森林大火，細(xì)胞擴(kuò)散等等秸讹。

Gossip protocol 最早是在 1987 年發(fā)表在 ACM 上的論文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出胁后。主要用在分布式數(shù)據(jù)庫系統(tǒng)中各個(gè)副本節(jié)點(diǎn)同步數(shù)據(jù)之用，這種場景的一個(gè)最大特點(diǎn)就是組成的網(wǎng)絡(luò)的節(jié)點(diǎn)都是對等節(jié)點(diǎn)嗦枢，是非結(jié)構(gòu)化網(wǎng)絡(luò)攀芯，這區(qū)別與之前介紹的用于結(jié)構(gòu)化網(wǎng)絡(luò)中的 DHT 算法 Kadmelia。

我們知道文虏，很多知名的 P2P 網(wǎng)絡(luò)或區(qū)塊鏈項(xiàng)目侣诺，比如 IPFS，Ethereum 等氧秘，都使用了 Kadmelia 算法年鸳，而大名鼎鼎的 Bitcoin 則是使用了 Gossip 協(xié)議來傳播交易和區(qū)塊信息。

實(shí)際上丸相，只要仔細(xì)分析一下場景就知道搔确，Ethereum 使用 DHT 算法并不是很合理，因?yàn)樗褂霉?jié)點(diǎn)保存整個(gè)鏈數(shù)據(jù)灭忠，不像 IPFS 那樣分片保存數(shù)據(jù)膳算，因此 Ethereum 真正適合的協(xié)議應(yīng)該像 Bitcoin 那樣，是 Gossip 協(xié)議弛作。

這里先簡單介紹一下 Gossip 協(xié)議的執(zhí)行過程：

Gossip 過程是由種子節(jié)點(diǎn)發(fā)起涕蜂，當(dāng)一個(gè)種子節(jié)點(diǎn)有狀態(tài)需要更新到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)時(shí)，它會隨機(jī)的選擇周圍幾個(gè)節(jié)點(diǎn)散播消息映琳，收到消息的節(jié)點(diǎn)也會重復(fù)該過程机隙，直至最終網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到了消息肉盹。這個(gè)過程可能需要一定的時(shí)間沉填，由于不能保證某個(gè)時(shí)刻所有節(jié)點(diǎn)都收到消息，但是理論上最終所有節(jié)點(diǎn)都會收到消息央勒，因此它是一個(gè)最終一致性協(xié)議谎脯。

下面葱跋，我們通過一個(gè)具體的實(shí)例來體會一下 Gossip 傳播的完整過程

為了表述清楚，我們先做一些前提設(shè)定：

（1）Gossip 是周期性的散播消息穿肄，把周期限定為 1 秒
（2）被感染節(jié)點(diǎn)隨機(jī)選擇 k 個(gè)鄰接節(jié)點(diǎn)（fan-out）散播消息年局，這里把 fan-out 設(shè)置為 3际看，每次最多往 3 個(gè)節(jié)點(diǎn)散播咸产。
（3）每次散播消息都選擇尚未發(fā)送過的節(jié)點(diǎn)進(jìn)行散播
（4）收到消息的節(jié)點(diǎn)不再往發(fā)送節(jié)點(diǎn)散播，比如 A -> B仲闽，那么 B 進(jìn)行散播的時(shí)候脑溢，不再發(fā)給 A。

這里一共有 16 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn) 1 為初始被感染節(jié)點(diǎn)屑彻，通過 Gossip 過程验庙，最終所有節(jié)點(diǎn)都被感染：

下面來總結(jié)一下

Gossip 的特點(diǎn)（優(yōu)勢）

1）擴(kuò)展性
網(wǎng)絡(luò)可以允許節(jié)點(diǎn)的任意增加和減少，新增加的節(jié)點(diǎn)的狀態(tài)最終會與其他節(jié)點(diǎn)一致社牲。

2）容錯
網(wǎng)絡(luò)中任何節(jié)點(diǎn)的宕機(jī)和重啟都不會影響 Gossip 消息的傳播粪薛，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯特性。

3）去中心化
Gossip 協(xié)議不要求任何中心節(jié)點(diǎn)搏恤，所有節(jié)點(diǎn)都可以是對等的违寿，任何一個(gè)節(jié)點(diǎn)無需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)是連通的熟空，任意一個(gè)節(jié)點(diǎn)就可以把消息散播到全網(wǎng)藤巢。

4）一致性收斂
Gossip 協(xié)議中的消息會以一傳十、十傳百一樣的指數(shù)級速度在網(wǎng)絡(luò)中快速傳播息罗，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致掂咒。消息傳播速度達(dá)到了 logN。

5）簡單
Gossip 協(xié)議的過程極其簡單迈喉，實(shí)現(xiàn)起來幾乎沒有太多復(fù)雜性绍刮。

Márk Jelasity 在它的 《Gossip》一書中對其進(jìn)行了歸納：

Gossip 的缺陷

分布式網(wǎng)絡(luò)中，沒有一種完美的解決方案挨摸，Gossip 協(xié)議跟其他協(xié)議一樣录淡，也有一些不可避免的缺陷，主要是兩個(gè)：

1）消息的延遲
由于 Gossip 協(xié)議中油坝，節(jié)點(diǎn)只會隨機(jī)向少數(shù)幾個(gè)節(jié)點(diǎn)發(fā)送消息嫉戚，消息最終是通過多個(gè)輪次的散播而到達(dá)全網(wǎng)的，因此使用 Gossip 協(xié)議會造成不可避免的消息延遲澈圈。不適合用在對實(shí)時(shí)性要求較高的場景下彬檀。

2）消息冗余
Gossip 協(xié)議規(guī)定，節(jié)點(diǎn)會定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息瞬女，而收到消息的節(jié)點(diǎn)也會重復(fù)該步驟窍帝，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點(diǎn)的情況，造成了消息的冗余诽偷，同時(shí)也增加了收到消息的節(jié)點(diǎn)的處理壓力坤学。而且，由于是定期發(fā)送而且不反饋报慕，因此深浮，即使節(jié)點(diǎn)收到了消息，還是會反復(fù)收到重復(fù)消息眠冈，加重了消息的冗余飞苇。

Gossip 類型

Gossip 有兩種類型：

• Anti-Entropy（反熵）：以固定的概率傳播所有的數(shù)據(jù)
• Rumor-Mongering（謠言傳播）：僅傳播新到達(dá)的數(shù)據(jù)

Anti-Entropy 是 SI model，節(jié)點(diǎn)只有兩種狀態(tài)，Suspective 和 Infective布卡，叫做 simple epidemics雨让。
Rumor-Mongering 是 SIR model，節(jié)點(diǎn)有三種狀態(tài)忿等，Suspective栖忠，Infective 和 Removed，叫做 complex epidemics贸街。

其實(shí)娃闲，Anti-Entropy 反熵是一個(gè)很奇怪的名詞，之所以定義成這樣匾浪，Jelasity 進(jìn)行了解釋皇帮，因?yàn)?Entropy 是指混亂程度（disorder），而在這種模式下可以消除不同節(jié)點(diǎn)中數(shù)據(jù)的 disorder蛋辈，因此 Anti-Entropy 就是 anti-disorder属拾。換句話說，它可以提高系統(tǒng)中節(jié)點(diǎn)之間的 similarity冷溶。

在 SI model 下渐白，一個(gè)節(jié)點(diǎn)會把所有的數(shù)據(jù)都跟其他節(jié)點(diǎn)共享，以便消除節(jié)點(diǎn)之間數(shù)據(jù)的任何不一致逞频，它可以保證最終纯衍、完全的一致。

由于在 SI model 下消息會不斷反復(fù)的交換苗胀，因此消息數(shù)量是非常龐大的襟诸，無限制的（unbounded），這對一個(gè)系統(tǒng)來說是一個(gè)巨大的開銷基协。

但是在 Rumor Mongering (SIR Model) 模型下歌亲，消息可以發(fā)送得更頻繁，因?yàn)橄⒅话钚?update澜驮，體積更小陷揪。而且，一個(gè) Rumor 消息在某個(gè)時(shí)間點(diǎn)之后會被標(biāo)記為 removed杂穷，并且不再被傳播悍缠，因此，SIR model 下耐量，系統(tǒng)有一定的概率會不一致飞蚓。

而由于，SIR Model 下某個(gè)時(shí)間點(diǎn)之后消息不再傳播拴鸵，因此消息是有限的玷坠，系統(tǒng)開銷小。

Gossip 中的通信模式

在 Gossip 協(xié)議下劲藐，網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間有三種通信方式:

• Push: 節(jié)點(diǎn) A 將數(shù)據(jù) (key,value,version) 及對應(yīng)的版本號推送給 B 節(jié)點(diǎn)八堡，B 節(jié)點(diǎn)更新 A 中比自己新的數(shù)據(jù)
• Pull：A 僅將數(shù)據(jù) key, version 推送給 B，B 將本地比 A 新的數(shù)據(jù)（Key, value, version）推送給 A聘芜，A 更新本地
• Push/Pull：與 Pull 類似兄渺，只是多了一步，A 再將本地比 B 新的數(shù)據(jù)推送給 B汰现，B 則更新本地
  如果把兩個(gè)節(jié)點(diǎn)數(shù)據(jù)同步一次定義為一個(gè)周期挂谍，則在一個(gè)周期內(nèi)，Push 需通信 1 次瞎饲，Pull 需 2 次口叙，Push/Pull 則需 3 次。雖然消息數(shù)增加了嗅战，但從效果上來講妄田，Push/Pull 最好，理論上一個(gè)周期內(nèi)可以使兩個(gè)節(jié)點(diǎn)完全一致驮捍。直觀上疟呐，Push/Pull 的收斂速度也是最快的。

復(fù)雜度分析

對于一個(gè)節(jié)點(diǎn)數(shù)為 N 的網(wǎng)絡(luò)來說东且，假設(shè)每個(gè) Gossip 周期启具，新感染的節(jié)點(diǎn)都能再感染至少一個(gè)新節(jié)點(diǎn)，那么 Gossip 協(xié)議退化成一個(gè)二叉樹查找珊泳，經(jīng)過 LogN 個(gè)周期之后鲁冯，感染全網(wǎng)，時(shí)間開銷是 O(LogN)色查。由于每個(gè)周期晓褪，每個(gè)節(jié)點(diǎn)都會至少發(fā)出一次消息，因此综慎，消息復(fù)雜度（消息數(shù)量 = N * N）是 O(N^2) 涣仿。注意，這是 Gossip 理論上最優(yōu)的收斂速度示惊，但是在實(shí)際情況中好港，最優(yōu)的收斂速度是很難達(dá)到的。

假設(shè)某個(gè)節(jié)點(diǎn)在第 i 個(gè)周期被感染的概率為 pi米罚，第 i+1 個(gè)周期被感染的概率為 pi+1 钧汹，

1）則 Pull 的方式:

2）Push 方式：

可見，Pull 的收斂速度大于 Push 录择，而每個(gè)節(jié)點(diǎn)在每個(gè)周期被感染的概率都是固定的 p (0<p<1)拔莱，因此 Gossip 算法是基于 p 的平方收斂碗降，也稱為概率收斂，這在眾多的一致性算法中是非常獨(dú)特的塘秦。

全文完讼渊！

如果你喜歡我的文章，可以關(guān)注我的微信公眾號：deliverit