起源
Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議）晦款，是基于流行病傳播方式的節(jié)點或者進程之間信息交換的協(xié)議草则。样傍。Gossip protocol在1987年8月由施樂公司帕洛阿爾托研究中心研究員艾倫·德默斯（Alan Demers）發(fā)表在ACM上的論文《Epidemic Algorithms for Replicated Database Maintenance》中被提出缸榄。
Gossip協(xié)議是基于六度分隔理論（Six Degrees of Separation）哲學(xué)的體現(xiàn)，簡單的來說巾乳，一個人通過6個中間人可以認識世界任何人。數(shù)學(xué)公式是：
n表示復(fù)雜度鸟召，N表示人的總數(shù)胆绊，W表示每個人的聯(lián)系寬度。依據(jù)鄧巴數(shù)欧募，即每個人認識150人压状，其六度就是1506 ＝11,390,625,000,000（約11.4萬億）。
基于六度分隔理論槽片，任何信息的傳播其實非常迅速何缓，而且網(wǎng)絡(luò)交互次數(shù)不會很多。比如Facebook在2016年2月4號做了一個實驗：研究了當(dāng)時已注冊的15.9億使用者資料还栓，發(fā)現(xiàn)這個神奇數(shù)字的“網(wǎng)絡(luò)直徑”是4.57碌廓，翻成白話文意味著每個人與其他人間隔為4.57人。
基礎(chǔ)原理
Gossip協(xié)議在計算機系統(tǒng)通常以隨機的“對等選擇”形式實現(xiàn)：以給定的頻率剩盒，每臺計算機隨機選擇另一臺計算機谷婆，并共享任何消息。定義十分簡單，所以實現(xiàn)方式非常多纪挎，可能有幾百種Gossip協(xié)議變種期贫。因為每個使用場景都可能根據(jù)組織的特定需求進行定制，維基百科上這樣寫：
There are probably hundreds of variants of specific Gossip-like protocols because each use-scenario is likely to be customized to the organization's specific needs.
下文解說一種比較原始的Gossip協(xié)議實現(xiàn)的執(zhí)行過程异袄、消息類型通砍、通訊方式，以下為Gossip協(xié)議執(zhí)行過程：
種子節(jié)點周期性的散播消息 【假定把周期限定為 1 秒】烤蜕。
被感染節(jié)點隨機選擇N個鄰接節(jié)點散播消息【假定fan-out(扇出)設(shè)置為6封孙，每次最多往6個節(jié)點散播】。
節(jié)點只接收消息不反饋結(jié)果讽营。
每次散播消息都選擇尚未發(fā)送過的節(jié)點進行散播虎忌。
收到消息的節(jié)點回傳散播：A -> B，那么B進行散播的時候橱鹏，不再發(fā)給 A膜蠢。
Goosip 協(xié)議的信息傳播和擴散通常需要由種子節(jié)點發(fā)起。整個傳播過程可能需要一定的時間莉兰，由于不能保證某個時刻所有節(jié)點都收到消息挑围，但是理論上最終所有節(jié)點都會收到消息，因此它是一個最終一致性協(xié)議贮勃。
Gossip協(xié)議是一個多主協(xié)議贪惹，所有寫操作可以由不同節(jié)點發(fā)起，并且同步給其他副本寂嘉。Gossip內(nèi)組成的網(wǎng)絡(luò)節(jié)點都是對等節(jié)點奏瞬，是非結(jié)構(gòu)化網(wǎng)絡(luò)。
消息類型
Gossip 協(xié)議的消息傳播方式有兩種：Anti-Entropy(反熵傳播)和Rumor-Mongering(謠言傳播)泉孩。
反熵傳播使用“simple epidemics(SI model)”的方式：以固定的概率傳播所有的數(shù)據(jù)硼端。所有參與節(jié)點只有兩種狀態(tài)：
Suspective(病原)：處于 susceptible 狀態(tài)的節(jié)點代表其并沒有收到來自其他節(jié)點的更新。
Infective(感染)：處于 infective 狀態(tài)的節(jié)點代表其有數(shù)據(jù)更新寓搬，并且會將這個數(shù)據(jù)分享給其他節(jié)點珍昨。
反熵傳播過程是每個節(jié)點周期性地隨機選擇其他節(jié)點，然后通過互相交換自己的所有數(shù)據(jù)來消除兩者之間的差異句喷。
反熵傳播方法每次節(jié)點兩兩交換自己的所有數(shù)據(jù)會帶來非常大的通信負擔(dān)镣典，因此不會頻繁使用，通常只用于新加入節(jié)點的數(shù)據(jù)初始化唾琼。
謠言傳播使用“complex epidemics”(SIR model)的方式:以固定的概率僅傳播新到達的數(shù)據(jù)兄春。所有參與節(jié)點有三種狀態(tài)：Suspective(病原)、Infective(感染)锡溯、Removed(愈除)赶舆。
Removed(愈除):其已經(jīng)接收到來自其他節(jié)點的更新哑姚，但是其并不會將這個更新分享給其他節(jié)點。
謠言傳播過程是消息只包含最新 update芜茵，謠言消息在某個時間點之后會被標記為removed叙量，并且不再被傳播。缺點是系統(tǒng)有一定的概率會不一致九串，通常用于節(jié)點間數(shù)據(jù)增量同步绞佩。
一般來說，為了在通信代價和可靠性之間取得折中猪钮，需要將這兩種方法結(jié)合使用征炼。
通訊方式
Gossip 協(xié)議最終目的是將數(shù)據(jù)分發(fā)到網(wǎng)絡(luò)中的每一個節(jié)點。不管是 Anti-Entropy 還是 Rumor-Mongering 都涉及到節(jié)點間的數(shù)據(jù)交互方式躬贡，Gossip網(wǎng)絡(luò)中兩個節(jié)點之間存在三種通信方式：Push、Pull 以及 Push&Pull：
Push: 發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B眼坏，并向其發(fā)送自己的信息拂玻，節(jié)點 B 在收到信息后更新比自己新的數(shù)據(jù)，一般擁有新信息的節(jié)點才會作為發(fā)起節(jié)點
Pull：發(fā)起信息交換的節(jié)點 A 隨機選擇聯(lián)系節(jié)點 B宰译，并從對方獲取信息檐蚜。一般無新信息的節(jié)點才會作為發(fā)起節(jié)點
Push/Pull：發(fā)起信息交換的節(jié)點 A 向選擇的節(jié)點 B 發(fā)送信息，同時從對方獲取數(shù)據(jù)沿侈，用于更新自己的本地數(shù)據(jù)闯第。
如果把兩個節(jié)點數(shù)據(jù)同步一次定義為一個周期，則在一個周期內(nèi)缀拭，Push 需通信 1 次咳短，Pull 需 2 次，Push/Pull 則需 3 次蛛淋。雖然消息數(shù)增加了咙好，但從效果上來講，Push/Pull 最好褐荷，理論上一個周期內(nèi)可以使兩個節(jié)點完全一致勾效。直觀上，Push/&Pull 的收斂速度也是最快的叛甫。
總結(jié)
綜上所述层宫，Gossip 協(xié)議是按照流言傳播或流行病傳播的思想實現(xiàn)的，所以其监，Gossip 協(xié)議的實現(xiàn)算法也是很簡單的萌腿，下面分別是 Anti-Entropy 和 Rumor-Mongering 的實現(xiàn)偽代碼：
Gossip是一種去中心化的分布式協(xié)議，數(shù)據(jù)通過節(jié)點像病毒一樣逐個傳播棠赛。因為是指數(shù)級傳播哮奇，整體傳播速度非程鸥快，很像現(xiàn)在美國失控的2019-nCoV(新冠)一樣鼎俘。它具備以下優(yōu)勢：
可擴展性（Scalable）：允許節(jié)點的任意增加和減少哲身，新增節(jié)點的狀態(tài)最終會與其他節(jié)點一致。
容錯（Fault-tolerance）：網(wǎng)絡(luò)中任何節(jié)點的重啟或者宕機都不會影響 gossip 協(xié)議的運行贸伐，具有天然的分布式系統(tǒng)容錯特性勘天。
健壯性（Robust）：gossip 協(xié)議是去中心化的協(xié)議，所以集群中的所有節(jié)點都是對等的捉邢，沒有特殊的節(jié)點脯丝，所以任何節(jié)點出現(xiàn)問題都不會阻止其他節(jié)點繼續(xù)發(fā)送消息。任何節(jié)點都可以隨時加入或離開伏伐，而不會影響系統(tǒng)的整體服務(wù)質(zhì)量宠进。
最終一致性（Convergent consistency）：謠言傳播可以是指數(shù)級的快速傳播，因此新信息傳播時藐翎，消息可以快速地發(fā)送到全局節(jié)點材蹬，在有限的時間內(nèi)能夠做到所有節(jié)點都擁有最新的數(shù)據(jù)。
簡單
同樣也存在以下缺點：
消息延遲：節(jié)點隨機向少數(shù)幾個節(jié)點發(fā)送消息吝镣，消息最終是通過多個輪次的散播而到達全網(wǎng)堤器，不可避免的造成消息延遲。
消息冗余：節(jié)點定期隨機選擇周圍節(jié)點發(fā)送消息末贾，而收到消息的節(jié)點也會重復(fù)該步驟闸溃，因此不可避免地引起同一節(jié)點多次接收同一消息，增加消息處理的壓力拱撵。一次通信會對網(wǎng)路帶寬辉川、CUP資源造成很大的負載，而這些負載又受限于 通信頻率裕膀，該頻率又影響著算法收斂的速度员串。
拜占庭問題：如果有一個惡意傳播消息的節(jié)點，Gossip協(xié)議的分布式系統(tǒng)就會出問題昼扛。
上述優(yōu)缺點的本質(zhì)是因為Gossip是一個帶冗余的容錯算法寸齐，是一個最終一致性算法，雖然無法保證在某個時刻所有節(jié)點狀態(tài)一致抄谐，但可以保證在“最終所有節(jié)點一致”渺鹦，“最終”的時間是一個理論無法明確的時間點。所以適合于AP場景的數(shù)據(jù)一致性處理蛹含，常見應(yīng)用有：P2P網(wǎng)絡(luò)通信毅厚、Apache Cassandra、Redis Cluster浦箱、Consul吸耿。
文章出處：https://mp.weixin.qq.com/s?src=11×tamp=1598337993&ver=2543&signature=SSNB6V1XKeSIg7*-vNFJEOiSHHZFZvjChH0080gEt0CvGxGRIzKMw9v5TYHrtnMUcX-bbQ-GVZYX6nNUPcQ972bWX950VYC6yeFsI3EmIC6hE15EbkvJCJofvruaUDTv&new=1
