goosip paper

     http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

 

     mark之。

 

基于goosip协议可以用来server端通信，解决数据不同问题，以简单的server端类似于谣言传播方式 能够以O(lgn)时间复杂度同步更新数据到所有server. 对于去中心化，减去成本昂贵的中心server有重要作用。但是这种传播方式，如何保证数据同步的time deadline就比较关键了。而且由于这种传播方式，所以flow control就显得比较关键了。针对基于goosip的去中心化，一定要考虑到网络带宽和更新数据的频率、数量等了。去中心化效费比还是中心化效费比高还是很难说。

Amazon的 dynamo 就是去中心化的数据存储。 而XX公司则一般都有中心节点。

以下来自： http://www.thoss.org.cn/mediawiki/index.php?title=Gossip-Protocol&diff=prev&oldid=136

Anti-entropy protocol

假设有 {p, q, ...} 这些参与者，每个参与者都有关于一个自己信息的表。用编程语言来描述的话： 记 InfoMap = Map<Key, (Value, Version)>， 那么每个参与者要维护一个 InfoMap 类型的变量 localInfo。 同时每一个参与者要知道所有参与者的信息, 即要维护一个全局的表， 记 Map<participant, InfoMap> 类型的变量 globalMap。 一个节点上的系统的其他模块只能更新自己的 localInfo， 而由 Gossip 协议模块负责从网络中接收信息并更新 globalMap 中的其他部分。

每个节点都和系统中的某些节点成为 peer (如果系统的规模比较小，和系统中所有的其他节点成为 peer)。 有三种不同的同步信息的方法：

• push-gossip: 最简单的情况下， 一个节点 p 向 q 发送整个 GlobalMap
• pull-gossip: p 向 q 发送 digest, q 根据 digest 向 p 发送 p 过期的 (key, (value, version)) 列表
• push-pull-gossip:

Tricky issues arise when gossip is used under high update load while available network bandwidth or CPU cycles are limited. If each participant introduces updates at the same rate. While expected latencies continue to grow logarithmic in N, the size of gossip messages grows linearly in N.

update item： (p, k, v, n)

 

Reconciliation

上面的给出了 gossip 协议的目标和基本的实现方法。有些细节

• 怎么选择 digest: 足够小， 而且要能从 digest 知道哪些更新要发送
• 在更新报文大小有限制的情况下，怎么选择要发送的 delta

precise reconciliation

Scuttlebutt:

• 记录 localInfo 中最大的 Version。