轉(zhuǎn)載自：http://blog.csdn.net/chen77716/article/details/6275762
Gossip算法因?yàn)镃assandra而名聲大噪，Gossip看似簡單，但要真正弄清楚其本質(zhì)遠(yuǎn)沒看起來那么容易。為了尋求Gossip的本質(zhì)，下面的內(nèi)容主要參考Gossip的原始論文：<<Efficient Reconciliation and Flow Control for Anti-Entropy Protocols>>。
1. Gossip背景
Gossip算法如其名，靈感來自辦公室八卦，只要一個(gè)人八卦一下，在有限的時(shí)間內(nèi)所有的人都會知道該八卦的信息，這種方式也與病毒傳播類似，因此Gossip有眾多的別名“閑話算法”、“疫情傳播算法”、“病毒感染算法”、“謠言傳播算法”。
但Gossip并不是一個(gè)新東西，之前的泛洪查找、路由算法都?xì)w屬于這個(gè)范疇，不同的是Gossip給這類算法提供了明確的語義、具體實(shí)施方法及收斂性證明。
2. Gossip特點(diǎn)
Gossip算法又被稱為反熵（Anti-Entropy），熵是物理學(xué)上的一個(gè)概念，代表雜亂無章，而反熵就是在雜亂無章中尋求一致，這充分說明了Gossip的特點(diǎn)：在一個(gè)有界網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都隨機(jī)地與其他節(jié)點(diǎn)通信，經(jīng)過一番雜亂無章的通信，最終所有節(jié)點(diǎn)的狀態(tài)都會達(dá)成一致。每個(gè)節(jié)點(diǎn)可能知道所有其他節(jié)點(diǎn)，也可能僅知道幾個(gè)鄰居節(jié)點(diǎn)，只要這些節(jié)可以通過網(wǎng)絡(luò)連通，最終他們的狀態(tài)都是一致的，當(dāng)然這也是疫情傳播的特點(diǎn)。
要注意到的一點(diǎn)是，即使有的節(jié)點(diǎn)因宕機(jī)而重啟，有新節(jié)點(diǎn)加入，但經(jīng)過一段時(shí)間后，這些節(jié)點(diǎn)的狀態(tài)也會與其他節(jié)點(diǎn)達(dá)成一致，也就是說，Gossip天然具有分布式容錯(cuò)的優(yōu)點(diǎn)。
3. Gossip本質(zhì)
Gossip是一個(gè)帶冗余的容錯(cuò)算法，更進(jìn)一步，Gossip是一個(gè)最終一致性算法。雖然無法保證在某個(gè)時(shí)刻所有節(jié)點(diǎn)狀態(tài)一致，但可以保證在”最終“所有節(jié)點(diǎn)一致，”最終“是一個(gè)現(xiàn)實(shí)中存在，但理論上無法證明的時(shí)間點(diǎn)。
因?yàn)镚ossip不要求節(jié)點(diǎn)知道所有其他節(jié)點(diǎn)，因此又具有去中心化的特點(diǎn)，節(jié)點(diǎn)之間完全對等，不需要任何的中心節(jié)點(diǎn)。實(shí)際上Gossip可以用于眾多能接受“最終一致性”的領(lǐng)域：失敗檢測、路由同步、Pub/Sub、動(dòng)態(tài)負(fù)載均衡。
但Gossip的缺點(diǎn)也很明顯，冗余通信會對網(wǎng)路帶寬、CUP資源造成很大的負(fù)載，而這些負(fù)載又受限于通信頻率，該頻率又影響著算法收斂的速度，后面我們會講在各種場合下的優(yōu)化方法。
4. Gossip節(jié)點(diǎn)的通信方式及收斂性
根據(jù)原論文，兩個(gè)節(jié)點(diǎn)（A、B）之間存在三種通信方式:
- push: A節(jié)點(diǎn)將數(shù)據(jù)(key,value,version)及對應(yīng)的版本號推送給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次，從效果上來講，push/pull最好，理論上一個(gè)周期內(nèi)可以使兩個(gè)節(jié)點(diǎn)完全一致。直觀上也感覺，push/pull的收斂速度是最快的。
假設(shè)每個(gè)節(jié)點(diǎn)通信周期都能選擇（感染）一個(gè)新節(jié)點(diǎn)，則Gossip算法退化為一個(gè)二分查找過程，每個(gè)周期構(gòu)成一個(gè)平衡二叉樹，收斂速度為O(n2 )，對應(yīng)的時(shí)間開銷則為O(logn )。這也是Gossip理論上最優(yōu)的收斂速度。但在實(shí)際情況中最優(yōu)收斂速度是很難達(dá)到的，假設(shè)某個(gè)節(jié)點(diǎn)在第i個(gè)周期被感染的概率為pi ,第i+1個(gè)周期被感染的概率為pi+1 ，則pull的方式:
而push為：
顯然pull的收斂速度大于push，而每個(gè)節(jié)點(diǎn)在每個(gè)周期被感染的概率都是固定的p(0<p<1)，因此Gossip算法是基于p的平方收斂，也成為概率收斂，這在眾多的一致性算法中是非常獨(dú)特的。
個(gè)Gossip的節(jié)點(diǎn)的工作方式又分兩種：
- Anti-Entropy（反熵）：以固定的概率傳播所有的數(shù)據(jù)
- Rumor-Mongering（謠言傳播）：僅傳播新到達(dá)的數(shù)據(jù)
Anti-Entropy模式有完全的容錯(cuò)性，但有較大的網(wǎng)絡(luò)、CPU負(fù)載；Rumor-Mongering模式有較小的網(wǎng)絡(luò)、CPU負(fù)載，但必須為數(shù)據(jù)定義”最新“的邊界，并且難以保證完全容錯(cuò)，對失敗重啟且超過”最新“期限的節(jié)點(diǎn)，無法保證最終一致性，或需要引入額外的機(jī)制處理不一致性。我們后續(xù)著重討論Anti-Entropy模式的優(yōu)化。
5. Anti-Entropy的協(xié)調(diào)機(jī)制
協(xié)調(diào)機(jī)制是討論在每次2個(gè)節(jié)點(diǎn)通信時(shí)，如何交換數(shù)據(jù)能達(dá)到最快的一致性，也即消除兩個(gè)節(jié)點(diǎn)的不一致性。上面所講的push、pull等是通信方式，協(xié)調(diào)是在通信方式下的數(shù)據(jù)交換機(jī)制。協(xié)調(diào)所面臨的最大問題是，因?yàn)槭芟抻诰W(wǎng)絡(luò)負(fù)載，不可能每次都把一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)發(fā)送給另外一個(gè)節(jié)點(diǎn)，也即每個(gè)Gossip的消息大小都有上限。在有限的空間上有效率地交換所有的消息是協(xié)調(diào)要解決的主要問題。
在討論之前先聲明幾個(gè)概念：
- 令N = {p,q,s,...}為需要gossip通信的server集合，有界大小
- 令(p1,p2,...)是宿主在節(jié)點(diǎn)p上的數(shù)據(jù)，其中數(shù)據(jù)有(key,value,version)構(gòu)成，q的規(guī)則與p類似。
為了保證一致性，規(guī)定數(shù)據(jù)的value及version只有宿主節(jié)點(diǎn)才能修改，其他節(jié)點(diǎn)只能間接通過Gossip協(xié)議來請求數(shù)據(jù)對應(yīng)的宿主節(jié)點(diǎn)修改。
5.1 精確協(xié)調(diào)（Precise Reconciliation）
精確協(xié)調(diào)希望在每次通信周期內(nèi)都非常準(zhǔn)確地消除雙方的不一致性，具體表現(xiàn)為相互發(fā)送對方需要更新的數(shù)據(jù)，因?yàn)槊總€(gè)節(jié)點(diǎn)都在并發(fā)與多個(gè)節(jié)點(diǎn)通信，理論上精確協(xié)調(diào)很難做到。精確協(xié)調(diào)需要給每個(gè)數(shù)據(jù)項(xiàng)獨(dú)立地維護(hù)自己的version，在每次交互是把所有的(key,value,version)發(fā)送到目標(biāo)進(jìn)行比對，從而找出雙方不同之處從而更新。但因?yàn)镚ossip消息存在大小限制，因此每次選擇發(fā)送哪些數(shù)據(jù)就成了問題。當(dāng)然可以隨機(jī)選擇一部分?jǐn)?shù)據(jù)，也可確定性的選擇數(shù)據(jù)。對確定性的選擇而言，可以有最老優(yōu)先（根據(jù)版本）和最新優(yōu)先兩種，最老優(yōu)先會優(yōu)先更新版本最新的數(shù)據(jù)，而最新更新正好相反，這樣會造成老數(shù)據(jù)始終得不到機(jī)會更新，也即饑餓。
當(dāng)然，開發(fā)這也可根據(jù)業(yè)務(wù)場景構(gòu)造自己的選擇算法，但始終都無法避免消息量過多的問題。
5.2 整體協(xié)調(diào)（Scuttlebutt Reconciliation）
整體協(xié)調(diào)與精確協(xié)調(diào)不同之處是，整體協(xié)調(diào)不是為每個(gè)數(shù)據(jù)都維護(hù)單獨(dú)的版本號，而是為每個(gè)節(jié)點(diǎn)上的宿主數(shù)據(jù)維護(hù)統(tǒng)一的version。比如節(jié)點(diǎn)P會為(p1,p2,...)維護(hù)一個(gè)一致的全局version，相當(dāng)于把所有的宿主數(shù)據(jù)看作一個(gè)整體，當(dāng)與其他節(jié)點(diǎn)進(jìn)行比較時(shí)，只需必須這些宿主數(shù)據(jù)的最高version，如果最高version相同說明這部分?jǐn)?shù)據(jù)全部一致，否則再進(jìn)行精確協(xié)調(diào)。
整體協(xié)調(diào)對數(shù)據(jù)的選擇也有兩種方法：
- 廣度優(yōu)先：根據(jù)整體version大小排序，也稱為公平選擇
- 深度優(yōu)先：根據(jù)包含數(shù)據(jù)多少的排序，也稱為非公平選擇。因?yàn)楹笳吒袑?shí)用價(jià)值，所以原論文更鼓勵(lì)后者
6. Cassandra中的實(shí)現(xiàn)
經(jīng)過驗(yàn)證，Cassandra實(shí)現(xiàn)了基于整體協(xié)調(diào)的push/push模式，有幾個(gè)組件：
三條消息分別對應(yīng)push/pull的三個(gè)階段：
- GossipDigitsMessage
- GossipDigitsAckMessage
- GossipDigitsAck2Message
還有三種狀態(tài)：
- EndpointState：維護(hù)宿主數(shù)據(jù)的全局version，并封裝了HeartBeat和ApplicationState
- HeartBeat：心跳信息
- ApplicationState：系統(tǒng)負(fù)載信息（磁盤使用率）
Cassandra主要是使用Gossip完成三方面的功能：
- 失敗檢測
- 動(dòng)態(tài)負(fù)載均衡
- 去中心化的彈性擴(kuò)展
7. 總結(jié)
Gossip是一種去中心化、容錯(cuò)而又最終一致性的絕妙算法，其收斂性不但得到證明還具有指數(shù)級的收斂速度。使用Gossip的系統(tǒng)可以很容易的把Server擴(kuò)展到更多的節(jié)點(diǎn)，滿足彈性擴(kuò)展輕而易舉。
唯一的缺點(diǎn)是收斂是最終一致性，不使用那些強(qiáng)一致性的場景，比如2pc。