轉(zhuǎn)載自：http://blog.163.com/liaoxiangui@126/blog/static/795696402012121112831272/
1.背景
Gossip算法又被稱為反熵（Anti-Entropy），熵是物理學(xué)上的一個(gè)概念，代表雜亂無(wú)章，而反熵就是在雜亂無(wú)章中尋求一致，這充分說(shuō)明了Gossip的特點(diǎn)：在一個(gè)有界網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都隨機(jī)地與其他節(jié)點(diǎn)通信，經(jīng)過(guò)一番雜亂無(wú)章的通信，最終所有節(jié)點(diǎn)的狀態(tài)都會(huì)達(dá)成一致。每個(gè)節(jié)點(diǎn)可能知道所有其他節(jié)點(diǎn)，也可能僅知道幾個(gè)鄰居節(jié)點(diǎn)，只要這些節(jié)可以通過(guò)網(wǎng)絡(luò)連通，最終他們的狀態(tài)都是一致的，當(dāng)然這也是疫情傳播的特點(diǎn)。
要注意到的一點(diǎn)是，即使有的節(jié)點(diǎn)因宕機(jī)而重啟，有新節(jié)點(diǎn)加入，但經(jīng)過(guò)一段時(shí)間后，這些節(jié)點(diǎn)的狀態(tài)也會(huì)與其他節(jié)點(diǎn)達(dá)成一致，也就是說(shuō)，Gossip天然具有分布式容錯(cuò)的優(yōu)點(diǎn)。
Gossip是一個(gè)帶冗余的容錯(cuò)算法，更進(jìn)一步，Gossip是一個(gè)最終一致性算法。雖然無(wú)法保證在某個(gè)時(shí)刻所有節(jié)點(diǎn)狀態(tài)一致，但可以保證在”最終“所有節(jié)點(diǎn)一致，”最終“是一個(gè)現(xiàn)實(shí)中存在，但理論上無(wú)法證明的時(shí)間點(diǎn)。
因?yàn)镚ossip不要求節(jié)點(diǎn)知道所有其他節(jié)點(diǎn)，因此又具有去中心化的特點(diǎn)，節(jié)點(diǎn)之間完全對(duì)等，不需要任何的中心節(jié)點(diǎn)。實(shí)際上Gossip可以用于眾多能接受“最終一致性”的領(lǐng)域：失敗檢測(cè)、路由同步、Pub/Sub、動(dòng)態(tài)負(fù)載均衡。
但Gossip的缺點(diǎn)也很明顯，冗余通信會(huì)對(duì)網(wǎng)路帶寬、CPU資源造成很大的負(fù)載，而這些負(fù)載又受限于通信頻率，該頻率又影響著算法收斂的速度，后面我們會(huì)講在各種場(chǎng)合下的優(yōu)化方法。
2.基本概念
gossip分為兩種. 本文只討論anti-entropy
■anti-entropy 只要數(shù)據(jù)不同步，就開(kāi)始同步數(shù)據(jù)
■rumor mongering 每隔固定的時(shí)間同步數(shù)據(jù)
見(jiàn)公式(1). 此公式表示在節(jié)點(diǎn)p上，q節(jié)點(diǎn)的屬性k的值是v，其版本號(hào)是n。
為了保證一致性，規(guī)定數(shù)據(jù)的value及version只有宿主節(jié)點(diǎn)才能修改，其他節(jié)點(diǎn)只能間接通過(guò)Gossip協(xié)議來(lái)請(qǐng)求數(shù)據(jù)對(duì)應(yīng)的宿主節(jié)點(diǎn)修改，即m (p)只能由有節(jié)點(diǎn)p來(lái)修改。
anti-entropy協(xié)議通過(guò)版本號(hào)大小來(lái)對(duì)數(shù)據(jù)進(jìn)行更新。
兩個(gè)節(jié)點(diǎn)（A、B）之間存在三種通信方式:
■push-gossip: A節(jié)點(diǎn)將數(shù)據(jù)推送給B節(jié)點(diǎn)，B節(jié)點(diǎn)更新A中比自己新的數(shù)據(jù)
■pull-gossip：A僅將摘要數(shù)據(jù) (node,key,value,version)推送給B，B根據(jù)摘要數(shù)據(jù)來(lái)選擇那些版本號(hào)比A高的數(shù)據(jù)推送給A，A更新本地。
■push-pull gossip：與pull類似，只是多了一步，A再將本地比B新的數(shù)據(jù)推送給B，B更新本地。
如果把兩個(gè)節(jié)點(diǎn)數(shù)據(jù)同步一次定義為一個(gè)周期，則在一個(gè)周期內(nèi)，push需通信1次，pull需2次，push/pull則需3次。從效果上來(lái)講，push/pull最好，理論上一個(gè)周期內(nèi)可以使兩個(gè)節(jié)點(diǎn)完全一致。直觀上也感覺(jué)，push/pull的收斂速度是最快的。
3.數(shù)據(jù)同步(RECONCILIATION)
3.1精確同步(precise reconciliation)
精確同步希望在每次通信周期內(nèi)都非常準(zhǔn)確地消除雙方的不一致性，具體表現(xiàn)為相互發(fā)送所有對(duì)方需要更新的數(shù)據(jù)。實(shí)現(xiàn)過(guò)程中，精確同步很難做到。因?yàn)檎獢?shù)據(jù)過(guò)多，但Gossip消息存在大小限制。因此每次選擇發(fā)送哪些數(shù)據(jù)就成了問(wèn)題。
3.2整體同步(Scuttlebutt reconciliation)
節(jié)點(diǎn)會(huì)維護(hù)一個(gè)唯一的時(shí)間戳生成器， 時(shí)間戳生成器為各個(gè)屬性生成時(shí)間戳，時(shí)間戳的值單調(diào)遞增。節(jié)點(diǎn)在生成摘要數(shù)據(jù)時(shí)，每個(gè)節(jié)點(diǎn)只有一份數(shù)據(jù){node,最大時(shí)間戳)。需要傳輸?shù)恼獢?shù)據(jù)和同步的實(shí)體數(shù)據(jù)的量大大的減少了。
對(duì)于敏感的網(wǎng)絡(luò)而言，可能同步的實(shí)體數(shù)據(jù)還是太多，還存在選擇發(fā)送哪些數(shù)據(jù)的問(wèn)題，如下的原則需要遵守：Scuttlebutt requires that if a certain delta (r; k; v; n) is omitted, then all the deltas with higher version numbers for the same r should be omitted as well.。即低版本號(hào)的實(shí)體數(shù)據(jù)比高版本號(hào)的實(shí)體數(shù)據(jù)的優(yōu)先級(jí)高。
要實(shí)現(xiàn)上述原則有2種方法。
■廣度優(yōu)先(scuttle breadth)
出發(fā)點(diǎn)是對(duì)每個(gè)節(jié)點(diǎn)都公平。
It uses a ranking on deltas for the same participant. The delta with the lowest version number has rank 0, the next lowest rank 1, and so on. The deltas are first ordered by rank so that deltas with lower ranks are included before deltas with higher ranks.
■深度優(yōu)先(scuttle-depth)
相比廣度優(yōu)先，此方法對(duì)所有節(jié)點(diǎn)不公平。待傳輸?shù)臄?shù)據(jù)(delta data)越多，其優(yōu)先級(jí)越高。這個(gè)方法要好于以上方法，但是作者沒(méi)有進(jìn)行解釋。
4.流控(flow control)
待研究。。。。。