【摘要】 1. Gossip协议简介
2. 协议原理
  2.1 执行过程
  2.2 消息类型
  2.3 通信方式
3. 总结
  3.1. 协议优点
  3.2 协议缺点

1. Gossip协议简介
  Gossip protocol 也叫 Epidemic Protocol （流行病协议）。Gossip protocol在1987年8…

2. 协议原理

2.2 消息类型

2.3 通信方式

3. 总结

3.1. 协议优点

3.2协议缺点

1. Gossip协议简介

Gossip protocol 也叫 Epidemic Protocol （流行病协议）。Gossip protocol在1987年8月由施乐-帕洛阿尔托研究中心发表ACM上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出。原本用于分布式数据库中节点同步数据使用，后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络。很多知名的 P2P 网络或区块链项目，比如 IPFS，Ethereum 等，都使用了 Kadmelia 算法，而大名鼎鼎的 Bitcoin 则是使用了 Gossip 协议来传播交易和区块信息。

2. 协议原理

2.1 执行过程

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

1）Gossip 是周期性的散播消息，把周期限定为 1 秒；

2）被感染节点随机选择 k 个邻接节点（扇出，fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。

3）每次散播消息都选择尚未发送过的节点进行散播

4）收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。

2.2 消息类型

Gossip 协议的消息传播方式有两种：Anti-Entropy(反熵传播)和Rumor-Mongering(谣言传播)。

反熵传播：反熵传播是以固定的概率传播所有的数据。所有参与节点只有两种状态：Suspective(病原)、Infective(感染)。这种节点状态又叫做simple epidemics(SI model)。过程是种子节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一致。缺点是消息数量非常庞大，且无限制；通常只用于新加入节点的数据初始化。
谣言传播：谣言传播是以固定的概率仅传播新到达的数据。所有参与节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。这种节点状态又叫做complex epidemics(SIR model)。过程是消息只包含最新 update，谣言消息在某个时间点之后会被标记为 removed，并且不再被传播。缺点是系统有一定的概率会不一致，通常用于节点间数据增量同步。

2.3 通信方式

Gossip 协议最终目的是将数据分发到网络中的每一个节点。根据不同的具体应用场景，网络中两个节点之间存在三种通信方式：推送模式、拉取模式、Push/Pull。

Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
Pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push/Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push/Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push/Pull 的收敛速度也是最快的。

3. 总结

gossip就是一个并行的图广度优先遍历算法。假设A得到某些信息，更新了自身的信息，A需要将信息告诉B、C等，然后B、C告诉其他的D、E、F、G，一直遍历。如果节点B收到A的消息，发现自己早就知道这个消息就直接忽略，从而可以防止图重复遍历。和路由器使用的路由表同步算法类似，只不过路由器还会维护每个路径的cost。gossip常用于维护集群的拓扑结构（路由器也是），被redis、consul使用。