Gossip是什么
Gossip協(xié)議是一個(gè)通信協(xié)議疙驾，一種傳播消息的方式杠河，靈感來(lái)自于：瘟疫氢架、社交網(wǎng)絡(luò)等傻咖。使用Gossip協(xié)議的有：Redis Cluster、Consul岖研、Apache Cassandra等没龙。
六度分隔理論
說(shuō)到社交網(wǎng)絡(luò)，就不得不提著名的六度分隔理論缎玫。1967年硬纤，哈佛大學(xué)的心理學(xué)教授Stanley Milgram想要描繪一個(gè)連結(jié)人與社區(qū)的人際連系網(wǎng)。做過(guò)一次連鎖信實(shí)驗(yàn)赃磨，結(jié)果發(fā)現(xiàn)了“六度分隔”現(xiàn)象筝家。簡(jiǎn)單地說(shuō)：“你和任何一個(gè)陌生人之間所間隔的人不會(huì)超過(guò)六個(gè)，也就是說(shuō)邻辉，最多通過(guò)六個(gè)人你就能夠認(rèn)識(shí)任何一個(gè)陌生人溪王。
數(shù)學(xué)解釋該理論：若每個(gè)人平均認(rèn)識(shí)260人，其六度就是260↑6 =1,188,137,600,000值骇。消除一些節(jié)點(diǎn)重復(fù)莹菱，那也幾乎覆蓋了整個(gè)地球人口若干多多倍，這也是Gossip協(xié)議的雛形吱瘩。
原理
Gossip協(xié)議基本思想就是：一個(gè)節(jié)點(diǎn)想要分享一些信息給網(wǎng)絡(luò)中的其他的一些節(jié)點(diǎn)道伟。于是，它周期性的隨機(jī)選擇一些節(jié)點(diǎn)使碾，并把信息傳遞給這些節(jié)點(diǎn)蜜徽。這些收到信息的節(jié)點(diǎn)接下來(lái)會(huì)做同樣的事情，即把這些信息傳遞給其他一些隨機(jī)選擇的節(jié)點(diǎn)票摇。一般而言拘鞋，信息會(huì)周期性的傳遞給N個(gè)目標(biāo)節(jié)點(diǎn)，而不只是一個(gè)矢门。這個(gè)N被稱(chēng)為fanout（這個(gè)單詞的本意是扇出）盆色。
用途
Gossip協(xié)議的主要用途就是信息傳播和擴(kuò)散：即把一些發(fā)生的事件傳播到全世界灰蛙。它們也被用于數(shù)據(jù)庫(kù)復(fù)制，信息擴(kuò)散隔躲，集群成員身份確認(rèn)缕允，故障探測(cè)等。
基于Gossip協(xié)議的一些有名的系統(tǒng)：Apache Cassandra蹭越，Redis（Cluster模式）障本，Consul等。
圖解
接下來(lái)通過(guò)多張圖片剖析Gossip協(xié)議是如何運(yùn)行的响鹃。如下圖所示驾霜，Gossip協(xié)議是周期循環(huán)執(zhí)行的。圖中的公式表示Gossip協(xié)議把信息傳播到每一個(gè)節(jié)點(diǎn)需要多少次循環(huán)動(dòng)作买置，需要說(shuō)明的是粪糙，公式中的20表示整個(gè)集群有20個(gè)節(jié)點(diǎn)，4表示某個(gè)節(jié)點(diǎn)會(huì)向4個(gè)目標(biāo)節(jié)點(diǎn)傳播消息：
如下圖所示忿项，紅色的節(jié)點(diǎn)表示其已經(jīng)“受到感染”蓉冈，即接下來(lái)要傳播信息的源頭，連線表示這個(gè)初始化感染的節(jié)點(diǎn)能正常連接的節(jié)點(diǎn)（其不能連接的節(jié)點(diǎn)只能靠接下來(lái)感染的節(jié)點(diǎn)向其傳播消息）轩触。并且N等于4寞酿，我們假設(shè)4根較粗的線路，就是它第一次傳播消息的線路：
第一次消息完成傳播后脱柱，新增了4個(gè)節(jié)點(diǎn)會(huì)被“感染”伐弹，即這4個(gè)節(jié)點(diǎn)也收到了消息。這時(shí)候榨为，總計(jì)有5個(gè)節(jié)點(diǎn)變成紅色：
那么在下一次傳播周期時(shí)惨好，總計(jì)有5個(gè)節(jié)點(diǎn)，且這5個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)都會(huì)向4個(gè)節(jié)點(diǎn)傳播消息随闺。最后日川，經(jīng)過(guò)3次循環(huán)，20個(gè)節(jié)點(diǎn)全部被感染（都變成紅色節(jié)點(diǎn)）矩乐，即說(shuō)明需要傳播的消息已經(jīng)傳播給了所有節(jié)點(diǎn)：
需要說(shuō)明的是龄句，20個(gè)節(jié)點(diǎn)且設(shè)置fanout=4，公式結(jié)果是2.16绰精，這只是個(gè)近似值撒璧。真實(shí)傳遞時(shí)，可能需要3次甚至4次循環(huán)才能讓所有節(jié)點(diǎn)收到消息笨使。這是因?yàn)槊總€(gè)節(jié)點(diǎn)在傳播消息的時(shí)候，是隨機(jī)選擇N個(gè)節(jié)點(diǎn)的僚害，這樣的話(huà)硫椰，就有可能某個(gè)節(jié)點(diǎn)會(huì)被選中2次甚至更多次繁调。
發(fā)送消息
由前面對(duì)Gossip協(xié)議圖解分析可知，節(jié)點(diǎn)傳播消息是周期性的靶草，并且每個(gè)節(jié)點(diǎn)有它自己的周期蹄胰。另外，節(jié)點(diǎn)發(fā)送消息時(shí)的目標(biāo)節(jié)點(diǎn)數(shù)由參數(shù)fanout決定奕翔。至于往哪些目標(biāo)節(jié)點(diǎn)發(fā)送裕寨，則是隨機(jī)的。
一旦消息被發(fā)送到目標(biāo)節(jié)點(diǎn)派继，那么目標(biāo)節(jié)點(diǎn)也會(huì)被感染宾袜。一旦某個(gè)節(jié)點(diǎn)被感染，那么它也會(huì)向其他節(jié)點(diǎn)傳播消息驾窟，試圖感染更多的節(jié)點(diǎn)庆猫。最終，每一個(gè)節(jié)點(diǎn)都會(huì)被感染绅络，即消息被同步給了所有節(jié)點(diǎn)：
可擴(kuò)展性
Gossip協(xié)議是可擴(kuò)展的月培，因?yàn)樗恍枰狾(logN) 個(gè)周期就能把消息傳播給所有節(jié)點(diǎn)。某個(gè)節(jié)點(diǎn)在往固定數(shù)量節(jié)點(diǎn)傳播消息過(guò)程中恩急，并不需要等待確認(rèn)（ack）杉畜，并且，即使某條消息傳播過(guò)程中丟失衷恭，它也不需要做任何補(bǔ)償措施寻行。大哥比方，某個(gè)節(jié)點(diǎn)本來(lái)需要將消息傳播給4個(gè)節(jié)點(diǎn)匾荆，但是由于網(wǎng)絡(luò)或者其他原因拌蜘，只有3個(gè)消息接收到消息，即使這樣牙丽，這對(duì)最終所有節(jié)點(diǎn)接收到消息是沒(méi)有任何影響的简卧。
如下表格所示，假定fanout=4烤芦，那么在節(jié)點(diǎn)數(shù)分別是20举娩、40、80构罗、160時(shí)铜涉，消息傳播到所有節(jié)點(diǎn)需要的循環(huán)次數(shù)對(duì)比，在節(jié)點(diǎn)成倍擴(kuò)大的情況下遂唧，循環(huán)次數(shù)并沒(méi)有增加很多芙代。所以，Gossip協(xié)議具備可擴(kuò)展性：
失敗容錯(cuò)
Gossip也具備失敗容錯(cuò)的能力盖彭，即使網(wǎng)絡(luò)故障等一些問(wèn)題纹烹，Gossip協(xié)議依然能很好的運(yùn)行页滚。因?yàn)橐粋€(gè)節(jié)點(diǎn)會(huì)多次分享某個(gè)需要傳播的信息，即使不能連通某個(gè)節(jié)點(diǎn)铺呵，其他被感染的節(jié)點(diǎn)也會(huì)嘗試向這個(gè)節(jié)點(diǎn)傳播信息裹驰。
健壯性
Gossip協(xié)議下，沒(méi)有任何扮演特殊角色的節(jié)點(diǎn)（比如leader等）片挂。任何一個(gè)節(jié)點(diǎn)無(wú)論什么時(shí)候下線或者加入幻林，并不會(huì)破壞整個(gè)系統(tǒng)的服務(wù)質(zhì)量。
然而音念，Gossip協(xié)議也有不完美的地方沪饺，例如，拜占庭問(wèn)題（Byzantine）症昏。即随闽，如果有一個(gè)惡意傳播消息的節(jié)點(diǎn)，Gossip協(xié)議的分布式系統(tǒng)就會(huì)出問(wèn)題肝谭。
