Paxos、Raft、ZAB 等分布式算法經(jīng)常會被稱作是“強一致性”的分布式共識協(xié)議，其實這樣的描述摳細節(jié)概念的話是很別扭的，會有語病嫌疑，但我們都明白它的意思其實是在說“盡管系統(tǒng)內(nèi)部節(jié)點可以存在不一致的狀態(tài)，但從系統(tǒng)外部看來，不一致的情況并不會被觀察到，所以整體上看系統(tǒng)是強一致性的”。與它們相對的，還有另一類被冠以“最終一致性”的分布式共識協(xié)議，這表明系統(tǒng)中不一致的狀態(tài)有可能會在一定時間內(nèi)被外部直接觀察到。一種典型且極為常見的最終一致的分布式系統(tǒng)就是DNS 系統(tǒng)，在各節(jié)點緩存的 TTL 到期之前，都有可能與真實的域名翻譯結(jié)果存在不一致。在本節(jié)中，筆者將介紹在比特幣網(wǎng)絡(luò)和許多重要分布式框架中都有應(yīng)用的另一種具有代表性的“最終一致性”的分布式共識協(xié)議：Gossip 協(xié)議。

Gossip 協(xié)議也叫 Epidemic Protocol（流行病協(xié)議），主要用于消息傳播，是一種一致性算法。協(xié)議也非常好理解，正如協(xié)議的名稱，如流行病一樣靠“感染”節(jié)點進行持續(xù)傳播。使用 Gossip 協(xié)議的有：Redis Cluster、Consul、Apache Cassandra等。

也把 Gossip 稱作是“共識協(xié)議”，但首先必須強調(diào)它所解決的問題并不是直接與 Paxos、Raft 這些共識算法等價的，只是基于 Gossip 之上可以通過某些方法去實現(xiàn)與 Paxos、Raft 相類似的目標而已。一個最典型的例子是比特幣網(wǎng)絡(luò)中使用到了 Gossip 協(xié)議，用它來在各個分布式節(jié)點中互相同步區(qū)塊頭和區(qū)塊體的信息，這是整個網(wǎng)絡(luò)能夠正常交換信息的基礎(chǔ)，但并不能稱作共識；比特幣使用工作量證明（Proof of Work，PoW）來對“這個區(qū)塊由誰來記賬”這一件事情在全網(wǎng)達成共識，這個目標才可以認為與 Paxos、Raft 的目標是一致的。

六度分隔理論

要說 Gossip 就不得不提“六度分隔理論”，簡單的說：你和任何一個陌生人之間所間隔的人不會超過五個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。由時任哈佛大學(xué)的心理學(xué)教授 Stanley Milgram 在1967年提出。

Facebook 研究了已注冊的15.9億使用者資料，在2016年公布標題為 “Three and a half degrees of separation” 的研究結(jié)果。發(fā)現(xiàn)世界比人們想象的更緊密，世界上的每個人（至少在 Facebook 活躍的15.9億人）平均通過3.57個人就可以與任意另外一個人產(chǎn)生聯(lián)系。

基于六度分隔理論，信息的傳播會非常迅速，而且網(wǎng)絡(luò)交互次數(shù)不會很多。Gossip 協(xié)議是基于六度分隔理論的很好實現(xiàn)。

協(xié)議原理

Gossip協(xié)議基本思想就是：一個節(jié)點想要分享一些信息給網(wǎng)絡(luò)中的其他的節(jié)點，于是隨機選擇一些節(jié)點進行信息傳遞。這些收到信息的節(jié)點接下來把這些信息傳遞給其他一些隨機選擇的節(jié)點。整體過程描述如下。

1. Gossip 是周期性的散播消息
2. 被感染節(jié)點隨機選擇 k 個鄰接節(jié)點（fan-out）散播消息，假設(shè)把 fan-out 設(shè)置為2，每次最多往2個節(jié)點散播
3. 每次散播消息都選擇尚未發(fā)送過的節(jié)點進行散播

4. 收到消息的節(jié)點不再往發(fā)送節(jié)點散播，比如 A -> B，那么 B 進行散播的時候，不再發(fā)給 A

   
   
   Gossip-Node-Spread

上圖是 Gossip 傳播過程的示意圖，根據(jù)示意圖和 Gossip 的過程描述，我們很容易發(fā)現(xiàn) Gossip 對網(wǎng)絡(luò)節(jié)點的連通性和穩(wěn)定性幾乎沒有任何要求，它一開始就將網(wǎng)絡(luò)某些節(jié)點只能與一部分節(jié)點部分連通（Partially Connected Network）而不是以全連通網(wǎng)絡(luò)（Fully Connected Network）作為前提；能夠容忍網(wǎng)絡(luò)上節(jié)點的隨意地增加或者減少，隨意地宕機或者重啟，新增加或者重啟的節(jié)點的狀態(tài)最終會與其他節(jié)點同步達成一致。Gossip 把網(wǎng)絡(luò)上所有節(jié)點都視為平等而普通的一員，沒有任何中心化節(jié)點或者主節(jié)點的概念，這些特點使得 Gossip 具有極強的魯棒性，而且非常適合在公眾互聯(lián)網(wǎng)中應(yīng)用。

Gossip協(xié)議的類型

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

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

Anti-Entropy

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

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

Rumor-Mongering

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

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

因為 Rumor 消息會在某個時間標記為 removed，然后不會發(fā)送給其他節(jié)點，所以 Rumor-Mongering 類型的 gossip 協(xié)議有極小概率使得更新不會達到所有節(jié)點。

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

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

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

• Push：發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B，并向其發(fā)送自己的信息，節(jié)點 B 在收到信息后更新比自己新的數(shù)據(jù)，一般擁有新信息的節(jié)點才會作為發(fā)起節(jié)點。
• Pull：發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B，并從對方獲取信息。一般無新信息的節(jié)點才會作為發(fā)起節(jié)點。
• Push&Pull：發(fā)起信息交換的節(jié)點 A 向選擇的節(jié)點 B 發(fā)送信息，同時從對方獲取數(shù)據(jù)，用于更新自己的本地數(shù)據(jù)。

Gossip算法實現(xiàn)

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

Gossip-Algorithm-SI.jpg

Gossip-Algorithm-SIR.jpg

協(xié)議優(yōu)缺點

優(yōu)點

擴展性

Gossip 協(xié)議的可擴展性極好，一般只需要 O(LogN) 輪就可以將信息傳播到所有的節(jié)點，其中 N 代表節(jié)點的個數(shù)。即使集群節(jié)點的數(shù)量增加，每個節(jié)點的負載也不會增加很多，幾乎是恒定的。這就允許集群管理的節(jié)點規(guī)模能橫向擴展到幾千幾萬個，集群內(nèi)的消息通信成本卻不會增加很多。

容錯

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

健壯性

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

最終一致性

消息傳播是指數(shù)級的快速傳播，因此當有新信息傳播時，消息可以快速地發(fā)送到全局節(jié)點。系統(tǒng)狀態(tài)的不一致可以在很快的時間內(nèi)收斂到一致。

缺點

消息延遲

節(jié)點隨機向少數(shù)幾個節(jié)點發(fā)送消息，消息最終是通過多個輪次的傳播而到達全網(wǎng)，不可避免的造成消息延遲。不適合于對實時性要求較高的場景。

消息冗余

節(jié)點會定期隨機選擇周圍節(jié)點發(fā)送消息，而收到消息的節(jié)點也會重復(fù)該步驟，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點的情況，造成了消息的冗余，同時也增加了收到消息的節(jié)點的處理壓力。

拜占庭問題

如果有一個惡意傳播消息的節(jié)點，Gossip協(xié)議的分布式系統(tǒng)就會出問題。

Gossip在工程上的使用

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

• Database replication
• 消息傳播
• Cluster membership
• Failure 檢測
• Overlay Networks
• Aggregations (比如計算平均值、最大值以及總和)

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

• Riak（https://github.com/basho/riak） 使用 gossip 協(xié)議來共享和傳遞集群的環(huán)狀態(tài)（ring state）和存儲桶屬性（bucket properties）。
• Cassandra：節(jié)點間的信息交換使用了 gossip 協(xié)議，因此所有節(jié)點都可以快速了解集群中的所有其他節(jié)點。
• Dynamo：采用基于 gossip 協(xié)議的分布式故障檢測和成員協(xié)議，這樣集群中添加或移除節(jié)點，其他節(jié)點可以快速檢測到。
• Consul：使用了稱為 SERF 的gossip 協(xié)議，主要有兩個目的：1、發(fā)現(xiàn)新的節(jié)點或者發(fā)現(xiàn)故障節(jié)點；2、為一些重要的事件（比如 Leader 選舉）傳播提供可靠、快速的傳播
• Amazon s3：使用 gossip 協(xié)議將服務(wù)的狀態(tài)傳遞給系統(tǒng)。
• Redis Cluster：集群中的 Nodes 之間使用 gossip 協(xié)議向其他 nodes 傳播集群信息，以達到自動發(fā)現(xiàn)的特性。
• 比特幣：著名的比特幣網(wǎng)絡(luò)在發(fā)送消息（比如發(fā)起一筆比特幣轉(zhuǎn)賬）的時候會使用 gossip 協(xié)議，比確保所有的結(jié)點都會收到。
• Akka Cluster：Akka 基于 gossip 協(xié)議提供了一種故障檢測機制，能夠自動發(fā)現(xiàn)出現(xiàn)故障而離開集群的成員節(jié)點，通過事件驅(qū)動的方式，將狀態(tài)傳播到整個集群的其它成員節(jié)點。

參考：

1. introduction-to-gossip