分布式系統(tǒng)的“流言蜚語(yǔ)”
你也許用過(guò)Redis，Cassandra，Amazon S3, BitTorrent 等著名的軟件，但是也許你不知道，它們?cè)诘讓油ㄐ艜r(shí)都采用了一個(gè)叫做Gossip(流言蜚語(yǔ))的協(xié)議。
我一直以來(lái)都想寫一下這個(gè)Gossip， 但是苦于找不到合適的方式，今天看到這Gossip模擬器(點(diǎn)閱讀原文查看)，我就知道不用我寫了，我給大家搬運(yùn)一下就行了。
開(kāi)始之前，我的習(xí)慣還是得先講講問(wèn)題，有了問(wèn)題，你才會(huì)知道這個(gè)技術(shù)到底想解決什么問(wèn)題。
假設(shè)你有一個(gè)集群，這個(gè)集群中有上千臺(tái)服務(wù)器，現(xiàn)在客戶對(duì)服務(wù)器A上的一個(gè)數(shù)據(jù)做了改動(dòng)，你想讓這個(gè)改動(dòng)迅速地傳遍整個(gè)集群中的服務(wù)器，換句話說(shuō)，讓這些服務(wù)器的數(shù)據(jù)都達(dá)到一致性的狀態(tài)， 你會(huì)怎么辦呢?
最簡(jiǎn)單的辦法
讓客戶的數(shù)據(jù)改動(dòng)，保存到一個(gè)穩(wěn)定的服務(wù)器X上，然后其他的服務(wù)器A,B,C,D.... 都從服務(wù)器X中去定期地拉取數(shù)據(jù)不就行了?
但是在分布式的情況下，至少會(huì)有兩個(gè)問(wèn)題：
1. 服務(wù)器X雖然很穩(wěn)定，但還是可能會(huì)掛掉，一旦掛掉，整個(gè)系統(tǒng)就完了。
還可以給服務(wù)器X做備份嘛，讓數(shù)據(jù)同步到服務(wù)器X1, X2,X3....中，這樣就不怕服務(wù)器X掛掉了，但是問(wèn)題又出現(xiàn)了，如何讓數(shù)據(jù)在這些服務(wù)器X, X1,X2,X3之間達(dá)成一致呢?
2. 由于網(wǎng)絡(luò)原因(這是非常常見(jiàn)的)，如果某一臺(tái)服務(wù)器H無(wú)法連接服務(wù)器X， 它也無(wú)法拉取數(shù)據(jù)了，即使服務(wù)器H能連上其他服務(wù)器也不行。
這就是一個(gè)典型的分布式系統(tǒng)中的一致性的問(wèn)題，科學(xué)家們已經(jīng)研究出了很多中算法出來(lái)，比如Paxos, Raft，今天我們要介紹的就是其中之一：Gossip協(xié)議，也可以叫做流言蜚語(yǔ)協(xié)議，這個(gè)協(xié)議就類似于社交網(wǎng)絡(luò)中小道消息的傳播，一傳十，十傳百，迅速傳遍整個(gè)網(wǎng)絡(luò)。
圖解Gossip
流言蜚語(yǔ)協(xié)議是怎么玩的呢? 我們來(lái)看看這個(gè)圖：
圖中有40個(gè)花花綠綠的圓圈，表示40個(gè)節(jié)點(diǎn)，就認(rèn)為是服務(wù)器吧。
接下來(lái)，我選擇了一個(gè)節(jié)點(diǎn)，假設(shè)數(shù)據(jù)改動(dòng)發(fā)生在它這里：
接下里我可以顯示這個(gè)節(jié)點(diǎn)所知道的那些“相鄰節(jié)點(diǎn)”, 如圖中的綠線所示。
其中有4根線比較粗，那就意味著這個(gè)節(jié)點(diǎn)從相鄰節(jié)點(diǎn)中隨機(jī)地選擇了4個(gè)來(lái)發(fā)送消息。
數(shù)目4 被稱為Fanout
接下里就可以發(fā)送消息了，注意，消息發(fā)送完以后，這4個(gè)節(jié)點(diǎn)也變紅了，這就意味著他們已經(jīng)收到了數(shù)據(jù)的更新。
用病毒傳播的術(shù)語(yǔ)來(lái)說(shuō)，有4個(gè)節(jié)點(diǎn)被感染了。
接下來(lái)，所有的紅色節(jié)點(diǎn)(擁有數(shù)據(jù)更新的、被“感染”的節(jié)點(diǎn))遵循開(kāi)始那一個(gè)節(jié)點(diǎn)的策略，從自己知道的節(jié)點(diǎn)中隨機(jī)選擇4個(gè)，傳播這次的數(shù)據(jù)改動(dòng)。
于是，更多的節(jié)點(diǎn)被“感染”了，變紅了。
如此循環(huán)下去，被感染的節(jié)點(diǎn)持續(xù)隨機(jī)傳播“病毒”(數(shù)據(jù)改動(dòng))，然后所有的節(jié)點(diǎn)都被傳染了，達(dá)到了一致性的狀態(tài)。
來(lái)一張動(dòng)圖，看一看整體的過(guò)程，感興趣的同學(xué)可以直接點(diǎn)擊閱讀原文去網(wǎng)站玩一下，非常有意思。
這里展示的是40個(gè)節(jié)點(diǎn)的情況，可以看到，經(jīng)過(guò)3輪次以后，所有的節(jié)點(diǎn)都被感染了，數(shù)據(jù)保持一致了。
優(yōu)點(diǎn)
1. 可伸縮性
剛才展示的是40個(gè)節(jié)點(diǎn)， 如果是80個(gè)節(jié)點(diǎn)呢? 經(jīng)過(guò)多少輪傳播才能達(dá)成一致?
大家可以自己玩一下，實(shí)際上僅僅需要4輪就可以了，
從理論上講， Gossip協(xié)議的的復(fù)雜度是O(logN) , 如果每次隨機(jī)選取4個(gè)節(jié)點(diǎn)作為Fanout 的話：
40個(gè)節(jié)點(diǎn)： 2.66 輪
80個(gè)節(jié)點(diǎn)： 3.16 輪
120個(gè)節(jié)點(diǎn)： 3.45 輪
....
可見(jiàn)流言蜚語(yǔ)協(xié)議對(duì)付節(jié)點(diǎn)的增長(zhǎng)是非常有效的。
2. 容錯(cuò)性
假設(shè)節(jié)點(diǎn)A和節(jié)點(diǎn)B之間是有連接的，A可以向B發(fā)送消息， A-> B
突然有一天由于網(wǎng)絡(luò)原因，A無(wú)法連接上B，消息發(fā)不過(guò)去，怎么辦?
不用擔(dān)心，總會(huì)有另外一個(gè)節(jié)點(diǎn)從另外一個(gè)路徑發(fā)送給它，例如C->B
從下面的動(dòng)圖中能看得更加清楚， 我把兩個(gè)消息傳輸?shù)穆窂浇o刪除了，但是對(duì)應(yīng)的節(jié)點(diǎn)還是從其他途徑收到了消息。
3. 收斂的一致性
Gossip 協(xié)議能以一傳十，十傳百這種指數(shù)級(jí)快速傳播信息，當(dāng)一個(gè)消息到達(dá)以后，能夠快速傳遍整個(gè)網(wǎng)絡(luò)，系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂，消息傳播速度是log(N)
4. 極端去中心化
Gossip 協(xié)議不要求任何中心的關(guān)鍵節(jié)點(diǎn)，所有節(jié)點(diǎn)都可以是對(duì)等的，任何一個(gè)節(jié)點(diǎn)無(wú)需知道整個(gè)網(wǎng)絡(luò)狀況，只要網(wǎng)絡(luò)是連通的，任意一個(gè)節(jié)點(diǎn)就可以把消息散播到全網(wǎng)。
其他通信模式
這個(gè)模擬器展示的只是一種通信模式： Push ， 也就是說(shuō)一個(gè)節(jié)點(diǎn)把數(shù)據(jù)推送給其他節(jié)點(diǎn)。
還有拉的方式(Pull)： 節(jié)點(diǎn)A 將本地?cái)?shù)據(jù)的版本告訴其他節(jié)點(diǎn)，其他節(jié)點(diǎn)將比A新的數(shù)據(jù)發(fā)給節(jié)點(diǎn)A, A再來(lái)更新數(shù)據(jù)。
當(dāng)然還可以有推拉結(jié)合(Push-Pull)結(jié)合的方式。
缺點(diǎn)
世界上沒(méi)有免費(fèi)的午餐，流言蜚語(yǔ)協(xié)議也有弱點(diǎn)：
消息是有延遲的
Gossip協(xié)議雖然傳播得很快，但是還需要經(jīng)過(guò)幾個(gè)輪次的傳播才能到達(dá)全網(wǎng)的所有節(jié)點(diǎn)， 這就不適合對(duì)實(shí)時(shí)性要求很高的場(chǎng)景了。 或者說(shuō)，Gossip協(xié)議只能達(dá)到最終一致性。
消息是有冗余的
從動(dòng)圖中可以清楚地看出，消息的發(fā)送是有冗余的，尤其是到了后面幾輪，大多數(shù)節(jié)點(diǎn)已經(jīng)收到了消息，但是還在持續(xù)選擇節(jié)點(diǎn)發(fā)送，消息數(shù)可以說(shuō)是蔚為壯觀啊。
【本文為51CTO專欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)coderising獲取授權(quán)】
