歡迎光臨
每天分享高質量文章

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

你也許用過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協議只能達到最終一致性。

訊息是有冗餘的

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

赞(0)

分享創造快樂