背景
Gossip protocol 也叫 Epidemic Protocol （流行病協(xié)議）活烙，實(shí)際上它還有很多別名沃斤，比如：“流言算法”、“疫情傳播算法”等馋评。
這個(gè)協(xié)議的作用就像其名字表示的意思一樣诗芜，非常容易理解瞳抓，它的方式其實(shí)在我們?nèi)粘Ｉ钪幸埠艹Ｒ姡热珉娔X病毒的傳播伏恐，森林大火孩哑，細(xì)胞擴(kuò)散等等。
Gossip protocol 最早是在 1987 年發(fā)表在 ACM 上的論文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出翠桦。主要用在分布式數(shù)據(jù)庫(kù)系統(tǒng)中各個(gè)副本節(jié)點(diǎn)同步數(shù)據(jù)之用横蜒，這種場(chǎng)景的一個(gè)最大特點(diǎn)就是組成的網(wǎng)絡(luò)的節(jié)點(diǎn)都是對(duì)等節(jié)點(diǎn)，是非結(jié)構(gòu)化網(wǎng)絡(luò)销凑，這區(qū)別與之前介紹的用于結(jié)構(gòu)化網(wǎng)絡(luò)中的 DHT 算法 Kadmelia丛晌。
我們知道，很多知名的 P2P 網(wǎng)絡(luò)或區(qū)塊鏈項(xiàng)目斗幼，比如 IPFS澎蛛，Ethereum 等，都使用了 Kadmelia 算法蜕窿，而大名鼎鼎的 Bitcoin 則是使用了 Gossip 協(xié)議來(lái)傳播交易和區(qū)塊信息谋逻。
實(shí)際上，只要仔細(xì)分析一下場(chǎng)景就知道桐经，Ethereum 使用 DHT 算法并不是很合理毁兆，因?yàn)樗褂霉?jié)點(diǎn)保存整個(gè)鏈數(shù)據(jù)，不像 IPFS 那樣分片保存數(shù)據(jù)阴挣，因此 Ethereum 真正適合的協(xié)議應(yīng)該像 Bitcoin 那樣荧恍，是 Gossip 協(xié)議。
這里先簡(jiǎn)單介紹一下 Gossip 協(xié)議的執(zhí)行過程：
Gossip 過程是由種子節(jié)點(diǎn)發(fā)起屯吊，當(dāng)一個(gè)種子節(jié)點(diǎn)有狀態(tài)需要更新到網(wǎng)絡(luò)中的其他節(jié)點(diǎn)時(shí)，它會(huì)隨機(jī)的選擇周圍幾個(gè)節(jié)點(diǎn)散播消息摹菠，收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該過程盒卸，直至最終網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到了消息。這個(gè)過程可能需要一定的時(shí)間次氨，由于不能保證某個(gè)時(shí)刻所有節(jié)點(diǎn)都收到消息蔽介，但是理論上最終所有節(jié)點(diǎn)都會(huì)收到消息，因此它是一個(gè)最終一致性協(xié)議。
下面虹蓄，我們通過一個(gè)具體的實(shí)例來(lái)體會(huì)一下 Gossip 傳播的完整過程
為了表述清楚犀呼，我們先做一些前提設(shè)定：
（1）Gossip 是周期性的散播消息，把周期限定為 1 秒
（2）被感染節(jié)點(diǎn)隨機(jī)選擇 k 個(gè)鄰接節(jié)點(diǎn)（fan-out）散播消息薇组，這里把 fan-out 設(shè)置為 3外臂，每次最多往 3 個(gè)節(jié)點(diǎn)散播。
（3）每次散播消息都選擇尚未發(fā)送過的節(jié)點(diǎn)進(jìn)行散播
（4）收到消息的節(jié)點(diǎn)不再往發(fā)送節(jié)點(diǎn)散播律胀，比如 A -> B宋光，那么 B 進(jìn)行散播的時(shí)候，不再發(fā)給 A炭菌。
這里一共有 16 個(gè)節(jié)點(diǎn)罪佳，節(jié)點(diǎn) 1 為初始被感染節(jié)點(diǎn)，通過 Gossip 過程黑低，最終所有節(jié)點(diǎn)都被感染：
下面來(lái)總結(jié)一下
Gossip 的特點(diǎn)（優(yōu)勢(shì)）
1）擴(kuò)展性
網(wǎng)絡(luò)可以允許節(jié)點(diǎn)的任意增加和減少赘艳，新增加的節(jié)點(diǎn)的狀態(tài)最終會(huì)與其他節(jié)點(diǎn)一致。
2）容錯(cuò)
網(wǎng)絡(luò)中任何節(jié)點(diǎn)的宕機(jī)和重啟都不會(huì)影響 Gossip 消息的傳播克握，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯(cuò)特性蕾管。
3）去中心化
Gossip 協(xié)議不要求任何中心節(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)勋眯。
4）一致性收斂
Gossip 協(xié)議中的消息會(huì)以一傳十婴梧、十傳百一樣的指數(shù)級(jí)速度在網(wǎng)絡(luò)中快速傳播，因此系統(tǒng)狀態(tài)的不一致可以在很快的時(shí)間內(nèi)收斂到一致客蹋。消息傳播速度達(dá)到了 logN塞蹭。
5）簡(jiǎn)單
Gossip 協(xié)議的過程極其簡(jiǎn)單，實(shí)現(xiàn)起來(lái)幾乎沒有太多復(fù)雜性讶坯。
Márk Jelasity 在它的 《Gossip》一書中對(duì)其進(jìn)行了歸納：
Gossip 的缺陷
分布式網(wǎng)絡(luò)中番电，沒有一種完美的解決方案，Gossip 協(xié)議跟其他協(xié)議一樣辆琅，也有一些不可避免的缺陷漱办，主要是兩個(gè)：
1）消息的延遲
由于 Gossip 協(xié)議中，節(jié)點(diǎn)只會(huì)隨機(jī)向少數(shù)幾個(gè)節(jié)點(diǎn)發(fā)送消息婉烟，消息最終是通過多個(gè)輪次的散播而到達(dá)全網(wǎng)的娩井，因此使用 Gossip 協(xié)議會(huì)造成不可避免的消息延遲。不適合用在對(duì)實(shí)時(shí)性要求較高的場(chǎng)景下似袁。
2）消息冗余
Gossip 協(xié)議規(guī)定洞辣，節(jié)點(diǎn)會(huì)定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息咐刨，而收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該步驟，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點(diǎn)的情況扬霜，造成了消息的冗余定鸟，同時(shí)也增加了收到消息的節(jié)點(diǎn)的處理壓力。而且著瓶，由于是定期發(fā)送而且不反饋联予，因此，即使節(jié)點(diǎn)收到了消息蟹但，還是會(huì)反復(fù)收到重復(fù)消息躯泰，加重了消息的冗余。
Gossip 類型
Gossip 有兩種類型：
Anti-Entropy（反熵）：以固定的概率傳播所有的數(shù)據(jù)
Rumor-Mongering（謠言傳播）：僅傳播新到達(dá)的數(shù)據(jù)
Anti-Entropy 是?SI model华糖，節(jié)點(diǎn)只有兩種狀態(tài)麦向，Suspective 和 Infective，叫做 simple epidemics客叉。
Rumor-Mongering 是?SIR model诵竭，節(jié)點(diǎn)有三種狀態(tài)，Suspective兼搏，Infective 和 Removed卵慰，叫做 complex epidemics。
其實(shí)佛呻，Anti-Entropy 反熵是一個(gè)很奇怪的名詞裳朋，之所以定義成這樣，Jelasity 進(jìn)行了解釋吓著，因?yàn)?Entropy 是指混亂程度（disorder）鲤嫡，而在這種模式下可以消除不同節(jié)點(diǎn)中數(shù)據(jù)的 disorder，因此 Anti-Entropy 就是 anti-disorder绑莺。換句話說(shuō)暖眼，它可以提高系統(tǒng)中節(jié)點(diǎn)之間的 similarity。
在?SI model?下纺裁，一個(gè)節(jié)點(diǎn)會(huì)把所有的數(shù)據(jù)都跟其他節(jié)點(diǎn)共享诫肠，以便消除節(jié)點(diǎn)之間數(shù)據(jù)的任何不一致，它可以保證最終欺缘、完全的一致栋豫。
由于在 SI model 下消息會(huì)不斷反復(fù)的交換，因此消息數(shù)量是非常龐大的谚殊，無(wú)限制的（unbounded）笼才，這對(duì)一個(gè)系統(tǒng)來(lái)說(shuō)是一個(gè)巨大的開銷。
但是在?Rumor Mongering (SIR Model)?模型下络凿，消息可以發(fā)送得更頻繁骡送，因?yàn)橄⒅话钚?update，體積更小絮记。而且摔踱，一個(gè) Rumor 消息在某個(gè)時(shí)間點(diǎn)之后會(huì)被標(biāo)記為 removed，并且不再被傳播怨愤，因此派敷，SIR model 下，系統(tǒng)有一定的概率會(huì)不一致撰洗。
而由于篮愉，SIR Model 下某個(gè)時(shí)間點(diǎn)之后消息不再傳播，因此消息是有限的差导，系統(tǒng)開銷小试躏。
Gossip 中的通信模式
在 Gossip 協(xié)議下，網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間有三種通信方式:
Push: 節(jié)點(diǎn) A 將數(shù)據(jù) (key,value,version) 及對(duì)應(yīng)的版本號(hào)推送給 B 節(jié)點(diǎn)设褐，B 節(jié)點(diǎn)更新 A 中比自己新的數(shù)據(jù)
Pull：A 僅將數(shù)據(jù) key, version 推送給 B颠蕴，B 將本地比 A 新的數(shù)據(jù)（Key, value, version）推送給 A，A 更新本地
Push/Pull：與 Pull 類似助析，只是多了一步犀被，A 再將本地比 B 新的數(shù)據(jù)推送給 B，B 則更新本地
如果把兩個(gè)節(jié)點(diǎn)數(shù)據(jù)同步一次定義為一個(gè)周期外冀，則在一個(gè)周期內(nèi)寡键，Push 需通信 1 次，Pull 需 2 次雪隧，Push/Pull 則需 3 次西轩。雖然消息數(shù)增加了，但從效果上來(lái)講膀跌，Push/Pull 最好遭商，理論上一個(gè)周期內(nèi)可以使兩個(gè)節(jié)點(diǎn)完全一致。直觀上捅伤，Push/Pull 的收斂速度也是最快的劫流。
復(fù)雜度分析
對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為 N 的網(wǎng)絡(luò)來(lái)說(shuō)，假設(shè)每個(gè) Gossip 周期丛忆，新感染的節(jié)點(diǎn)都能再感染至少一個(gè)新節(jié)點(diǎn)祠汇，那么 Gossip 協(xié)議退化成一個(gè)二叉樹查找，經(jīng)過 LogN 個(gè)周期之后熄诡，感染全網(wǎng)可很，時(shí)間開銷是 O(LogN)。由于每個(gè)周期凰浮，每個(gè)節(jié)點(diǎn)都會(huì)至少發(fā)出一次消息我抠，因此苇本，消息復(fù)雜度（消息數(shù)量 = N * N）是 O(N^2) 。注意菜拓，這是 Gossip 理論上最優(yōu)的收斂速度瓣窄，但是在實(shí)際情況中，最優(yōu)的收斂速度是很難達(dá)到的纳鼎。
假設(shè)某個(gè)節(jié)點(diǎn)在第 i 個(gè)周期被感染的概率為 pi俺夕，第 i+1 個(gè)周期被感染的概率為 pi+1 ，
1）則 Pull 的方式:
2）Push 方式：
可見贱鄙，Pull 的收斂速度大于 Push 劝贸，而每個(gè)節(jié)點(diǎn)在每個(gè)周期被感染的概率都是固定的 p (0<p<1)，因此 Gossip 算法是基于 p 的平方收斂逗宁，也稱為概率收斂映九，這在眾多的一致性算法中是非常獨(dú)特的。
全文完疙剑！
