分布式系統(tǒng)的“流言蜚語”

作者：劉欣 2019-03-18 16:29:01

開發(fā)

開發(fā)工具

分布式 你也許用過Redis，Cassandra，Amazon S3, BitTorrent 等著名的軟件，但是也許你不知道，它們在底層通信時都采用了一個叫做Gossip(流言蜚語)的協(xié)議。

創(chuàng)新互聯(lián)作為成都網(wǎng)站建設(shè)公司，專注成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計，有關(guān)成都企業(yè)網(wǎng)站定制方案、改版、費用等問題，行業(yè)涉及垃圾桶等多個領(lǐng)域，已為上千家企業(yè)服務(wù)，得到了客戶的尊重與認(rèn)可。

你也許用過Redis，Cassandra，Amazon S3, BitTorrent 等著名的軟件，但是也許你不知道，它們在底層通信時都采用了一個叫做Gossip(流言蜚語)的協(xié)議。

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

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

假設(shè)你有一個集群，這個集群中有上千臺服務(wù)器，現(xiàn)在客戶對服務(wù)器A上的一個數(shù)據(jù)做了改動，你想讓這個改動迅速地傳遍整個集群中的服務(wù)器，換句話說，讓這些服務(wù)器的數(shù)據(jù)都達(dá)到一致性的狀態(tài)， 你會怎么辦呢?

[[259785]]

最簡單的辦法

讓客戶的數(shù)據(jù)改動，保存到一個穩(wěn)定的服務(wù)器X上，然后其他的服務(wù)器A,B,C,D.... 都從服務(wù)器X中去定期地拉取數(shù)據(jù)不就行了?

[[259785]]

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

1. 服務(wù)器X雖然很穩(wěn)定，但還是可能會掛掉，一旦掛掉，整個系統(tǒng)就完了。

還可以給服務(wù)器X做備份嘛，讓數(shù)據(jù)同步到服務(wù)器X1, X2,X3....中，這樣就不怕服務(wù)器X掛掉了，但是問題又出現(xiàn)了，如何讓數(shù)據(jù)在這些服務(wù)器X, X1,X2,X3之間達(dá)成一致呢?

2. 由于網(wǎng)絡(luò)原因(這是非常常見的)，如果某一臺服務(wù)器H無法連接服務(wù)器X， 它也無法拉取數(shù)據(jù)了，即使服務(wù)器H能連上其他服務(wù)器也不行。

這就是一個典型的分布式系統(tǒng)中的一致性的問題，科學(xué)家們已經(jīng)研究出了很多中算法出來，比如Paxos, Raft，今天我們要介紹的就是其中之一：Gossip協(xié)議，也可以叫做流言蜚語協(xié)議，這個協(xié)議就類似于社交網(wǎng)絡(luò)中小道消息的傳播，一傳十，十傳百，迅速傳遍整個網(wǎng)絡(luò)。

圖解Gossip

流言蜚語協(xié)議是怎么玩的呢? 我們來看看這個圖：

圖中有40個花花綠綠的圓圈，表示40個節(jié)點，就認(rèn)為是服務(wù)器吧。[[259785]]

接下來，我選擇了一個節(jié)點，假設(shè)數(shù)據(jù)改動發(fā)生在它這里：

[[259785]]

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

其中有4根線比較粗，那就意味著這個節(jié)點從相鄰節(jié)點中隨機(jī)地選擇了4個來發(fā)送消息。

數(shù)目4 被稱為Fanout

[[259785]]

接下里就可以發(fā)送消息了，注意，消息發(fā)送完以后，這4個節(jié)點也變紅了，這就意味著他們已經(jīng)收到了數(shù)據(jù)的更新。

用病毒傳播的術(shù)語來說，有4個節(jié)點被感染了。

[[259785]]

接下來，所有的紅色節(jié)點(擁有數(shù)據(jù)更新的、被“感染”的節(jié)點)遵循開始那一個節(jié)點的策略，從自己知道的節(jié)點中隨機(jī)選擇4個，傳播這次的數(shù)據(jù)改動。

于是，更多的節(jié)點被“感染”了，變紅了。

[[259785]]

如此循環(huán)下去，被感染的節(jié)點持續(xù)隨機(jī)傳播“病毒”(數(shù)據(jù)改動)，然后所有的節(jié)點都被傳染了，達(dá)到了一致性的狀態(tài)。

[[259785]]

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

這里展示的是40個節(jié)點的情況，可以看到，經(jīng)過3輪次以后，所有的節(jié)點都被感染了，數(shù)據(jù)保持一致了。

優(yōu)點

1. 可伸縮性

剛才展示的是40個節(jié)點， 如果是80個節(jié)點呢? 經(jīng)過多少輪傳播才能達(dá)成一致?

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

從理論上講， Gossip協(xié)議的的復(fù)雜度是O(logN) , 如果每次隨機(jī)選取4個節(jié)點作為Fanout 的話：

40個節(jié)點： 2.66 輪

80個節(jié)點： 3.16 輪

120個節(jié)點： 3.45 輪

....

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

2. 容錯性

假設(shè)節(jié)點A和節(jié)點B之間是有連接的，A可以向B發(fā)送消息， A-> B

突然有一天由于網(wǎng)絡(luò)原因，A無法連接上B，消息發(fā)不過去，怎么辦?

不用擔(dān)心，總會有另外一個節(jié)點從另外一個路徑發(fā)送給它，例如C->B

從下面的動圖中能看得更加清楚， 我把兩個消息傳輸?shù)穆窂浇o刪除了，但是對應(yīng)的節(jié)點還是從其他途徑收到了消息。

3. 收斂的一致性

Gossip 協(xié)議能以一傳十，十傳百這種指數(shù)級快速傳播信息，當(dāng)一個消息到達(dá)以后，能夠快速傳遍整個網(wǎng)絡(luò)，系統(tǒng)狀態(tài)的不一致可以在很快的時間內(nèi)收斂，消息傳播速度是log(N)

4. 極端去中心化

Gossip 協(xié)議不要求任何中心的關(guān)鍵節(jié)點，所有節(jié)點都可以是對等的，任何一個節(jié)點無需知道整個網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)是連通的，任意一個節(jié)點就可以把消息散播到全網(wǎng)。

其他通信模式

這個模擬器展示的只是一種通信模式： Push ， 也就是說一個節(jié)點把數(shù)據(jù)推送給其他節(jié)點。

還有拉的方式(Pull)： 節(jié)點A 將本地數(shù)據(jù)的版本告訴其他節(jié)點，其他節(jié)點將比A新的數(shù)據(jù)發(fā)給節(jié)點A, A再來更新數(shù)據(jù)。

當(dāng)然還可以有推拉結(jié)合(Push-Pull)結(jié)合的方式。

缺點

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

消息是有延遲的

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

消息是有冗余的

從動圖中可以清楚地看出，消息的發(fā)送是有冗余的，尤其是到了后面幾輪，大多數(shù)節(jié)點已經(jīng)收到了消息，但是還在持續(xù)選擇節(jié)點發(fā)送，消息數(shù)可以說是蔚為壯觀啊。

【本文為51CTO專欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號coderising獲取授權(quán)】

戳這里，看該作者更多好文

當(dāng)前文章：分布式系統(tǒng)的“流言蜚語”
轉(zhuǎn)載來于：http://uogjgqi.cn/article/dhhjsod.html