分散式系統的“流言蜚語”

你也許用過Redis，Cassandra，Amazon S3, BitTorrent 等著名的軟體，但是也許你不知道，它們在底層通訊時都採用了一個叫做Gossip（流言蜚語）的協議。

我一直以來都想寫一下這個Gossip， 但是苦於找不到合適的方式，今天看到這Gossip模擬器（點閱讀原文檢視），我就知道不用我寫了，我給大家搬運一下就行了。

開始之前，我的習慣還是得先講講問題，有了問題，你才會知道這個技術到底想解決什麼問題。

假設你有一個叢集，這個叢集中有上千臺伺服器，現在客戶對伺服器A上的一個資料做了改動，你想讓這個改動迅速地傳遍整個叢集中的伺服器，換句話說，讓這些伺服器的資料都達到一致性的狀態， 你會怎麼辦呢？

最簡單的辦法

讓客戶的資料改動，儲存到一個穩定的伺服器X上，然後其他的伺服器A,B,C,D…. 都從伺服器X中去定期地拉取資料不就行了？

但是在分散式的情況下，至少會有兩個問題：

1.  伺服器X雖然很穩定，但還是可能會掛掉，一旦掛掉，整個系統就完了。

還可以給伺服器X做備份嘛，讓資料同步到伺服器X1, X2,X3….中，這樣就不怕伺服器X掛掉了，但是問題又出現了，如何讓資料在這些伺服器X, X1,X2,X3之間達成一致呢？

2.  由於網路原因（這是非常常見的），如果某一臺伺服器H連不上伺服器X， 它也無法拉取資料了，即使伺服器H能連上其他伺服器也不行。

這就是一個典型的分散式系統中的一致性的問題，科學家們已經研究出了很多中演演算法出來，比如Paxos, Raft，今天我們要介紹的就是其中之一：Gossip協議，也可以叫做流言蜚語協議，這個協議就類似於社交網路中小道訊息的傳播，一傳十，十傳百，最後迅速傳遍整個網路。

圖解Gossip

流言蜚語協議是怎麼玩的呢？ 我們來看看這個圖：

圖中有40個花花綠綠的圓圈，表示40個節點，就認為是伺服器吧。

接下來，我選擇了一個節點，假設資料改動發生在它這裡：

接下里我可以顯示這個節點所知道的那些“相鄰節點”,  如圖中的綠線所示。

其中有4根線比較粗，那就意味著這個節點從相鄰節點中隨機地選擇了4個來傳送訊息。

數目4 被稱為Fanout

接下里就可以傳送訊息了，註意，訊息傳送完以後，這4個節點也變紅了，這就意味著他們已經收到了資料的更新。

用病毒傳播的術語來說，有4個節點被感染了。

接下來，所有的紅色節點（擁有資料更新的、被“感染”的節點）遵循第一個節點的策略，從自己知道的節點中隨機選擇4個，傳播這次的資料改動。

於是，更多的節點被“感染”了，變紅了。

如此迴圈下去，被感染的節點持續隨機傳播“病毒”（資料改動），最後所有的節點都被傳染了，達到了一致性的狀態。

來一張動圖，看一看整體的過程，感興趣的同學可以直接點選閱讀原文去網站玩一下，非常有意思。

這裡展示的是40個節點的情況，可以看到，經過3輪次以後，所有的節點都被感染了，資料保持一致了。

優點

1. 可伸縮性

剛才展示的是40個節點， 如果是80個節點呢？ 經過多少輪傳播才能達成一致？

大家可以自己玩一下，實際上僅僅需要4輪就可以了，

從理論上講， Gossip協議的的複雜度是O(logN) , 如果每次隨機選取4個節點作為Fanout 的話：

40個節點：  2.66 輪

80個節點：  3.16 輪

120個節點： 3.45 輪

….

可見流言蜚語協議對付節點的增長是非常有效的。

2. 容錯性

假設節點A和節點B之間是有連線的，A可以向B傳送訊息， A-> B

突然有一天由於網路原因，A無法連線上B，訊息發不過去，怎麼辦？

不用擔心，總會有另外一個節點從另外一個路徑傳送給它，例如C->B

從下麵的動圖中能看得更加清楚， 我把兩個訊息傳輸的路徑給刪除了，但是對應的節點還是從其他途徑收到了訊息。

3. 收斂的一致性

Gossip 協議能以一傳十，十傳百這種指數級快速傳播資訊，當一個訊息到達以後，能夠快速傳遍整個網路，系統狀態的不一致可以在很快的時間內收斂，訊息傳播速度是log(N)

4. 極端去中心化

Gossip 協議不要求任何中心的關鍵節點，所有節點都可以是對等的，任何一個節點無需知道整個網路狀況，只要網路是連通的，任意一個節點就可以把訊息散播到全網。

其他通訊樣式

這個模擬器展示的只是一種通訊樣式： Push ， 也就是說一個節點把資料推送給其他節點。

還有拉的方式（Pull）： 節點A 將本地資料的版本告訴其他節點，其他節點將比A新的資料發給節點A,  A再來更新資料。

當然還可以有推拉結合(Push-Pull）結合的方式。

缺點

世界上沒有免費的午餐，流言蜚語協議也有弱點：

訊息是有延遲的

Gossip協議雖然傳播得很快，但是還需要經過幾個輪次的傳播才能到達全網的所有節點， 這就不適合對實時性要求很高的場景了。 或者說，Gossip協議只能達到最終一致性。

訊息是有冗餘的

從動圖中可以清楚地看出，訊息的傳送是有冗餘的，尤其是到了後面幾輪，大多數節點已經收到了訊息，但是還在持續選擇節點傳送，訊息數可以說是蔚為壯觀啊。