文章目錄

• Gossip協(xié)議
• • 直接郵寄
  • 反熵
  • 謠言傳播
  • 閉環(huán)反熵
  • 總結(jié)

---

Gossip協(xié)議

Gossip協(xié)議（Gossip Protocol）又稱Epidemic協(xié)議（Epidemic Protocol），是基于謠言傳播方式的節(jié)點(diǎn)或者進(jìn)程之間信息交換的協(xié)議，在分布式系統(tǒng)中被廣泛使用，比如我們可以使用Gossip協(xié)議來確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)的數(shù)據(jù)一致。

說到社交網(wǎng)絡(luò)，就不得不提著名的六度分隔理論。1967年，哈佛大學(xué)的心理學(xué)教授Stanley Milgram想要描繪一個(gè)連結(jié)人與社區(qū)的人際連系網(wǎng)。做過一次連鎖信實(shí)驗(yàn)，結(jié)果發(fā)現(xiàn)了“六度分隔”現(xiàn)象。簡(jiǎn)單地說：“你和任何一個(gè)陌生人之間所間隔的人不會(huì)超過六個(gè)，也就是說，最多通過六個(gè)人你就能夠認(rèn)識(shí)任何一個(gè)陌生人。

數(shù)學(xué)解釋該理論：若每個(gè)人平均認(rèn)識(shí)260人，其六度就是260↑6 =1,188,137,600,000。消除一些節(jié)點(diǎn)重復(fù)，那也幾乎覆蓋了整個(gè)地球人口若干多多倍，這也是Gossip協(xié)議的雛形。

Gossip基于六度分隔理論，每個(gè)節(jié)點(diǎn)像謠言傳播一樣，隨機(jī)的將信息傳播到其他節(jié)點(diǎn)上，不斷重復(fù)這個(gè)過程，直到將信息傳播到整個(gè)網(wǎng)絡(luò)中，并在一定時(shí)間內(nèi)，使得系統(tǒng)內(nèi)的所有節(jié)點(diǎn)數(shù)據(jù)一致。

Gossip主要有以下三個(gè)功能：

• 直接郵寄（Direct Mail）
• 反熵（Anti-entropy）
• 謠言傳播（Rumor mongering）

直接郵寄

直接發(fā)送需要更新的數(shù)據(jù)到其他節(jié)點(diǎn)，當(dāng)數(shù)據(jù)發(fā)送失敗時(shí)，將數(shù)據(jù)緩存到隊(duì)列中，然后進(jìn)行重傳。

直接郵寄

從上面可以看出，這種方法實(shí)現(xiàn)簡(jiǎn)單切數(shù)據(jù)同步及時(shí)，但是可能會(huì)因?yàn)橹卦嚨木彺骊?duì)列滿了而丟數(shù)據(jù)，從而無法實(shí)現(xiàn)最終一致性。

那么我們?nèi)绾螌?shí)現(xiàn)最終一致性呢？

這時(shí)候就需要借助到了Gossip協(xié)議中的反熵。

反熵

熵指混亂程度，反熵就是消除不同節(jié)點(diǎn)間數(shù)據(jù)的差異，提升節(jié)點(diǎn)間數(shù)據(jù)的相似度。

反熵的過程如下：

集群中的節(jié)點(diǎn)每隔一段時(shí)間就隨機(jī)選取某個(gè)其他節(jié)點(diǎn)

互相交換數(shù)據(jù)來消除兩個(gè)節(jié)點(diǎn)之間的差異

實(shí)現(xiàn)數(shù)據(jù)的最終一致性

反熵主要通過三種方式進(jìn)行：

• 推（Push）

  • 節(jié)點(diǎn)A將數(shù)據(jù)（key,value,version）推送給節(jié)點(diǎn)B，節(jié)點(diǎn)B將A中比自己新的數(shù)據(jù)更新過來。

• 拉（Pull）

  • 節(jié)點(diǎn)A僅將數(shù)據(jù)（key,version）推送給 B，B將本地比A新的數(shù)據(jù)（key, value, version）推送給A，A更新本地?cái)?shù)據(jù)。

• 推拉（Push/Pull）

  • 同時(shí)執(zhí)行上述兩個(gè)步驟，同時(shí)修復(fù)兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)。

從上面的三種反熵方式可以看出，反熵是需要節(jié)點(diǎn)兩兩交換和比對(duì)自己所有的數(shù)據(jù)，這樣來看的話，通訊成本是很高的，而在實(shí)際場(chǎng)景下這種頻繁的交換會(huì)大大影響性能。

那有沒有辦法來減少反熵的次數(shù)呢？

我們可以通過引入如校驗(yàn)和，如奇偶校驗(yàn)、CRC校驗(yàn)和格雷碼校驗(yàn)等來降低需要對(duì)比的數(shù)據(jù)量和通訊信息。

執(zhí)行反熵時(shí)，相關(guān)節(jié)點(diǎn)都是已知的，且節(jié)點(diǎn)數(shù)量不能太多。如果節(jié)點(diǎn)動(dòng)態(tài)變化或節(jié)點(diǎn)數(shù)過多，反熵就不合適。

那在這種場(chǎng)景下，有沒有辦法來解決動(dòng)態(tài)、多節(jié)點(diǎn)的最終一致性呢？

答案是有的，那這時(shí)候就要用到Gossip協(xié)議中的謠言傳播。

謠言傳播

謠言傳播，就像是一個(gè)謠言的產(chǎn)生流程一樣，每個(gè)人都會(huì)向自己身邊的人傳播，知道謠言散布各地。

在分布式系統(tǒng)中，當(dāng)一個(gè)節(jié)點(diǎn)有了新數(shù)據(jù)后，這個(gè)節(jié)點(diǎn)變成活躍狀態(tài)，并周期性地聯(lián)系其他節(jié)點(diǎn)向其發(fā)送新數(shù)據(jù)，直到所有節(jié)點(diǎn)都存儲(chǔ)了該數(shù)據(jù)，可以理解為之前講的反熵中的推的方式。

謠言傳播

從上面可以看出，謠言傳播仍然具有以下缺點(diǎn)：

• 時(shí)間隨機(jī)：所有節(jié)點(diǎn)達(dá)到一致性是一個(gè)隨機(jī)性的概率。可以使用閉環(huán)反熵修復(fù)。
• 消息冗余：同一節(jié)點(diǎn)會(huì)多次接收同一消息，增加了消息處理的壓力，每一次通信都會(huì)對(duì)網(wǎng)絡(luò)帶寬、CPU等資源造成負(fù)載，進(jìn)而影響達(dá)到最終一致性的時(shí)間。
• 拜占庭問題：如果有惡意節(jié)點(diǎn)出現(xiàn)，那么其他節(jié)點(diǎn)也會(huì)出問題。所以需要先修復(fù)故障節(jié)點(diǎn)。

閉環(huán)反熵

對(duì)于謠言傳播，所有節(jié)點(diǎn)達(dá)到一致性是一個(gè)隨機(jī)性的概率，其達(dá)到最終一致性的時(shí)間并不可控，這并不滿足我們的期望，我們更希望能在一個(gè)確定的時(shí)間范圍內(nèi)實(shí)現(xiàn)數(shù)據(jù)副本的最終一致性，因此Gossip協(xié)議又引入了閉環(huán)反熵。

它按照一定順序來修復(fù)節(jié)點(diǎn)的數(shù)據(jù)差異，先隨機(jī)選擇一個(gè)節(jié)點(diǎn)，順著這個(gè)節(jié)點(diǎn)往下循環(huán)修復(fù)。每個(gè)節(jié)點(diǎn)都會(huì)對(duì)比自身與下一個(gè)節(jié)點(diǎn)，將本節(jié)點(diǎn)存在而下個(gè)節(jié)點(diǎn)不存在的缺失數(shù)據(jù)發(fā)送給下一個(gè)節(jié)點(diǎn)來進(jìn)行修復(fù)，如下圖：

閉環(huán)反熵

與上面的反熵不同，閉環(huán)反熵不再是一個(gè)節(jié)點(diǎn)不斷隨機(jī)選擇另一個(gè)節(jié)點(diǎn)，來修復(fù)副本上的熵，而是設(shè)計(jì)了一個(gè)閉環(huán)的流程，一次修復(fù)所有節(jié)點(diǎn)的副本數(shù)據(jù)不一致。通過這種方法我們就能夠?qū)⒆罱K一致性的時(shí)間范圍明確下來，使其可控。

總結(jié)

上面說了那么多缺點(diǎn)，下面也來講講Gossip的幾個(gè)優(yōu)點(diǎn)

• 拓展性：網(wǎng)絡(luò)可以允許節(jié)點(diǎn)的動(dòng)態(tài)增加和減少，新增加的節(jié)點(diǎn)的狀態(tài)最終會(huì)與其他節(jié)點(diǎn)一致。
• 容錯(cuò)：網(wǎng)絡(luò)中任何節(jié)點(diǎn)的宕機(jī)和重啟都不會(huì)影響 Gossip 消息的傳播，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯(cuò)特性。
• 去中心化：Gossip協(xié)議不要求任何中心節(jié)點(diǎn)，所有節(jié)點(diǎn)都可以是對(duì)等的，任何一個(gè)節(jié)點(diǎn)無需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)是連通的，任意一個(gè)節(jié)點(diǎn)就可以把消息散播到全網(wǎng)。
• 實(shí)現(xiàn)簡(jiǎn)單：Gossip 協(xié)議中的消息會(huì)以一傳十、十傳百一樣的指數(shù)級(jí)速度在網(wǎng)絡(luò)中快速傳播，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致。消息傳播速度達(dá)到了 logN。
• 高性能：Gossip 協(xié)議的過程極其簡(jiǎn)單，實(shí)現(xiàn)起來幾乎沒有太多復(fù)雜性。

Gossip的三種功能其實(shí)都是為了實(shí)現(xiàn)反熵，第一種用消息隊(duì)列，第二種用推拉消息，第三種用散播謠言，下面給出三個(gè)功能的使用場(chǎng)景

功能應(yīng)用場(chǎng)景

直接郵寄	實(shí)際場(chǎng)景，直接郵寄一定要實(shí)現(xiàn)，性能損耗最低。通過發(fā)送更新數(shù)據(jù)或緩存重傳就能修復(fù)數(shù)據(jù)的不一致。
反熵	在存儲(chǔ)組件中，節(jié)點(diǎn)都是已知的，采用反熵修復(fù)數(shù)據(jù)副本的不一致。
謠言傳播	集群節(jié)點(diǎn)變化時(shí)，或節(jié)點(diǎn)較多時(shí)，采用謠言傳播方式，來同步更新多節(jié)點(diǎn)的數(shù)據(jù)，來實(shí)現(xiàn)最終一致性。

總結(jié)

以上是生活随笔為你收集整理的散布谣言也能实现一致性?来看看Gossip协议如何活用六度分隔理论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。