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