Gossip算法學習

1. 概述
gossip，顧名思義，類似于流言傳播的概念，是一種可以按照自己的期望，自行選擇與之交換信息的節點的通信方式
gossip, or anto-entropy,  is an attractive way of replicating state that does not have strong consistency requirements

2. 算法描述

假設有 {p, q, ...} 為協議參與者。 每個參與者都有關于一個自己信息的表。
用編程語言可以描述為：
記 InfoMap = Map<Key, (Value, Version)>， 那么每個參與者要維護一個 InfoMap 類型的變量 localInfo。 同時每一個參與者要知道所有其他參與者的信息, 即要維護一個全局的表，即 Map<participant, InfoMap> 類型的變量 globalMap。每個參與者更新自己的 localInfo， 而由 Gossip 協議負責將更新的信息同步到整個網絡上。
每個節點和系統中的某些節點成為 peer (如果系統的規模比較小，和系統中所有的其他節點成為 peer)。 有三種不同的同步信息的方法：
1）push-gossip: 最簡單的情況下， 一個節點 p 向 q 發送整個 GlobalMap
2）pull-gossip: p 向 q 發送 digest, q 根據 digest 向 p 發送 p 過期的 (key, (value, version)) 列表
3）push-pull-gossip:與pull-gossip類似，只是多了一步，A再將本地比B新的數據推送給B，B更新本地

3. 特點
gossip不要求節點知道所有其他節點，因此具有去中心化的特點，節點之間完全對等，不需要任何的中心節點。
gossip算法又被稱為反熵（Anti-Entropy），熵是物理學上的一個概念，代表雜亂無章，而反熵就是在雜亂無章中尋求一致，這充分說明了Gossip的特點：
在一個有界網絡中，每個節點都隨機地與其他節點通信，經過一番雜亂無章的通信，最終所有節點的狀態都會達成一致。每個節點可能知道所有其他節點，也可能僅知道幾個鄰節點，只要這些節可以通過網絡連通，最終他們的狀態都是一致的。
gossip算法是一個最終一致性算法，其無法保證在某個時刻所有節點狀態一致，但可以保證在”最終“所有節點一致，”最終“是一個現實中存在，但理論上無法證明的時間點

4. 協調機制
協調機制是討論在每次2個節點通信時，如何交換數據能達到最快的一致性，也即消除兩個節點的不一致性。
協調所面臨的最大問題是，因為受限于網絡負載，不可能每次都把一個節點上的數據發送給另外一個節點，也即每個Gossip的消息大小都有上限。在有限的空間上有效率地交換所有的消息是協調要解決的主要問題。
“Efficient Reconciliation and Flow Control for Anti-Entropy Protocols”中描述了兩種同步機制
1）precise reconciliation
precise reconciliation希望在每次通信周期內都非常準確地消除雙方的不一致性，具體表現為相互發送對方需要更新的數據，因為每個節點都在并發與多個 節點通信，理論上很難做到。precise reconciliation需要給每個數據項獨立地維護自己的version，在每次交互是把所有的(key,value,version)發送到目標 進行比對，從而找出雙方不同之處從而更新。但因為Gossip消息存在大小限制，因此每次選擇發送哪些數據就成了問題。當然可以隨機選擇一部分數據，也可 確定性的選擇數據。對確定性的選擇而言，可以有最老優先（根據版本）和最新優先兩種，最老優先會優先更新版本最新的數據，而最新更新正好相反，這樣會造成 老數據始終得不到機會更新，也即饑餓。
2）Scuttlebutt Reconciliation
Scuttlebutt Reconciliation 與precise reconciliation不同之處是，Scuttlebutt Reconciliation不是為每個數據都維護單獨的版本號，而是為每個節點上的宿主數據維護統一的version。比如節點P會為 (p1,p2,...)維護一個一致的全局version，相當于把所有的宿主數據看作一個整體，當與其他節點進行比較時，只需比較這些宿主數據的最高version，如果最高version相同說明這部分數據全部一致，否則再進行precise reconciliation。

5. Merkle tree
信息同步無疑是gossip的核心，Merkle tree(MT)是一個非常適合同步的數據結構。
簡單來說 Merkle tree就是一顆hash樹，在這棵樹中，葉子節點的值是一些hash值、非葉節點的值均是 由其子節點值計算hash得來的，這樣，一旦某個文件被修改，修改時間的信息就會迅速傳播到根目錄。需要同步的系統只需要不斷查詢跟節點的hash，一旦 有變化，順著樹狀結構就能夠在logN級 別的時間找到發生變化的內容，馬上同步。
在Dynamo中，每個節點保存一個范圍內的key值，不同節點間存在有相互交迭的key值范圍。在去熵操作中，考慮的僅僅是某兩個節點間共有的key值 范圍。MT的葉子節點即是這個共有的key值范圍內每個key的hash，通過葉子節點的hash自底向上便可以構建出一顆MT。Dynamo首先比對 MT根處的hash，如果一致則表示兩者完全一致，否則將其子節點交換并繼續比較的過程。

6.總結
Gossip常見于大規模、無中心的網絡系統，可以用于眾多能接受“最終一致性”的領域：失敗檢測、路由同步、Pub/Sub、動態負載均衡。

7.參考文獻
paper： Efficient Reconciliation and Flow Control for Anti-Entropy Protocols
http://tianya23.blog.51cto.com/1081650/530743
http://ultimatearchitecture.net/index.php/2010/09/12/merkle-tree/

轉自：http://blog.csdn.net/yfkiss/article/details/6943682