分布式原理：一文了解 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ù)一樣。

從 gossip 單詞就可以看到，其中文意思是八卦、流言等意思，我們可以想象下緋聞的傳播（或者流行病的傳播）；gossip 協(xié)議的工作原理就類似于這個(gè)。gossip 協(xié)議利用一種隨機(jī)的方式將信息傳播到整個(gè)網(wǎng)絡(luò)中，并在一定時(shí)間內(nèi)使得系統(tǒng)內(nèi)的所有節(jié)點(diǎn)數(shù)據(jù)一致。Gossip 其實(shí)是一種去中心化思路的分布式協(xié)議，解決狀態(tài)在集群中的傳播和狀態(tài)一致性的保證兩個(gè)問題。

gossip 優(yōu)勢(shì)

可擴(kuò)展性（Scalable）

gossip 協(xié)議是可擴(kuò)展的，一般需要 O（logN） 輪就可以將信息傳播到所有的節(jié)點(diǎn)，其中 N 代表節(jié)點(diǎn)的個(gè)數(shù)。每個(gè)節(jié)點(diǎn)僅發(fā)送固定數(shù)量的消息，并且與網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目無法。在數(shù)據(jù)傳送的時(shí)候，節(jié)點(diǎn)并不會(huì)等待消息的 ack，所以消息傳送失敗也沒有關(guān)系，因?yàn)榭梢酝ㄟ^其他節(jié)點(diǎn)將消息傳遞給之前傳送失敗的節(jié)點(diǎn)。系統(tǒng)可以輕松擴(kuò)展到數(shù)百萬個(gè)進(jìn)程。

容錯(cuò)（Fault-tolerance）

網(wǎng)絡(luò)中任何節(jié)點(diǎn)的重啟或者宕機(jī)都不會(huì)影響 gossip 協(xié)議的運(yùn)行。

健壯性（Robust）

gossip 協(xié)議是去中心化的協(xié)議，所以集群中的所有節(jié)點(diǎn)都是對(duì)等的，沒有特殊的節(jié)點(diǎn)，所以任何節(jié)點(diǎn)出現(xiàn)問題都不會(huì)阻止其他節(jié)點(diǎn)繼續(xù)發(fā)送消息。任何節(jié)點(diǎn)都可以隨時(shí)加入或離開，而不會(huì)影響系統(tǒng)的整體服務(wù)質(zhì)量（QOS）

最終一致性（Convergent consistency）

Gossip 協(xié)議實(shí)現(xiàn)信息指數(shù)級(jí)的快速傳播，因此在有新信息需要傳播時(shí)，消息可以快速地發(fā)送到全局節(jié)點(diǎn)，在有限的時(shí)間內(nèi)能夠做到所有節(jié)點(diǎn)都擁有最新的數(shù)據(jù)。

gossip 協(xié)議的類型

前面說了節(jié)點(diǎn)會(huì)將信息傳播到整個(gè)網(wǎng)絡(luò)中，那么節(jié)點(diǎn)在什么情況下發(fā)起信息交換？這就涉及到 gossip 協(xié)議的類型。目前主要有兩種方法：

Anti-Entropy（反熵）：以固定的概率傳播所有的數(shù)據(jù)

Rumor-Mongering（謠言傳播）：僅傳播新到達(dá)的數(shù)據(jù)

Anti-Entropy

Anti-Entropy 的主要工作方式是：每個(gè)節(jié)點(diǎn)周期性地隨機(jī)選擇其他節(jié)點(diǎn)，然后通過互相交換自己的所有數(shù)據(jù)來消除兩者之間的差異。Anti-Entropy 這種方法非?？煽?，但是每次節(jié)點(diǎn)兩兩交換自己的所有數(shù)據(jù)會(huì)帶來非常大的通信負(fù)擔(dān)，以此不會(huì)頻繁使用。

Anti-Entropy 使用“simple epidemics”的方式，所以其包含兩種狀態(tài)：susceptible 和 infective，這種模型也稱為 SI model。處于 infective 狀態(tài)的節(jié)點(diǎn)代表其有數(shù)據(jù)更新，并且會(huì)將這個(gè)數(shù)據(jù)分享給其他節(jié)點(diǎn)；處于 susceptible 狀態(tài)的節(jié)點(diǎn)代表其并沒有收到來自其他節(jié)點(diǎn)的更新。

Rumor-Mongering

Rumor-Mongering 的主要工作方式是：當(dāng)一個(gè)節(jié)點(diǎn)有了新的信息后，這個(gè)節(jié)點(diǎn)變成活躍狀態(tài)，并周期性地聯(lián)系其他節(jié)點(diǎn)向其發(fā)送新信息。直到所有的節(jié)點(diǎn)都知道該新信息。因?yàn)楣?jié)點(diǎn)之間只是交換新信息，所有大大減少了通信的負(fù)擔(dān)。

Rumor-Mongering 使用“complex epidemics”方法，相比 Anti-Entropy 多了一種狀態(tài)：removed，這種模型也稱為 SIR model。處于 removed 狀態(tài)的節(jié)點(diǎn)說明其已經(jīng)接收到來自其他節(jié)點(diǎn)的更新，但是其并不會(huì)將這個(gè)更新分享給其他節(jié)點(diǎn)。

因?yàn)?Rumor 消息會(huì)在某個(gè)時(shí)間標(biāo)記為 removed，然后不會(huì)發(fā)送給其他節(jié)點(diǎn)，所以 Rumor-Mongering 類型的 gossip 協(xié)議有極小概率使得更新不會(huì)達(dá)到所有節(jié)點(diǎn)。

一般來說，為了在通信代價(jià)和可靠性之間取得折中，需要將這兩種方法結(jié)合使用。

gossip 協(xié)議的通訊方式

不管是 Anti-Entropy 還是 Rumor-Mongering 都涉及到節(jié)點(diǎn)間的數(shù)據(jù)交互方式，節(jié)點(diǎn)間的交互方式主要有三種：Push、Pull 以及 Push&Pull。

Push：發(fā)起信息交換的節(jié)點(diǎn) A 隨機(jī)選擇聯(lián)系節(jié)點(diǎn) B，并向其發(fā)送自己的信息，節(jié)點(diǎn) B 在收到信息后更新比自己新的數(shù)據(jù)，一般擁有新信息的節(jié)點(diǎn)才會(huì)作為發(fā)起節(jié)點(diǎn)。

Pull：發(fā)起信息交換的節(jié)點(diǎn) A 隨機(jī)選擇聯(lián)系節(jié)點(diǎn) B，并從對(duì)方獲取信息。一般無新信息的節(jié)點(diǎn)才會(huì)作為發(fā)起節(jié)點(diǎn)。

Push&Pull：發(fā)起信息交換的節(jié)點(diǎn) A 向選擇的節(jié)點(diǎn) B 發(fā)送信息，同時(shí)從對(duì)方獲取數(shù)據(jù)，用于更新自己的本地?cái)?shù)據(jù)。

gossip 算法實(shí)現(xiàn)

Gossip 協(xié)議是按照流言傳播或流行病傳播的思想實(shí)現(xiàn)的，所以，Gossip 協(xié)議的實(shí)現(xiàn)算法也是很簡單的，下面分別是 Anti-Entropy 和 Rumor-Mongering 的實(shí)現(xiàn)偽代碼。

gossip 在工程上的使用

gossip 協(xié)議可以支持以下需求：

Database replication

消息傳播

Cluster membership

Failure 檢測

Overlay Networks

Aggregations （比如計(jì)算平均值、最大值以及總和）

在下面的工程上使用到了 gossip 協(xié)議。