Gossip 协议

Gossip protocol 也叫 Epidemic Protocol （流行病协议）。从名字就可以猜到这个算法的作用主要在服务器集群中进行数据的传播，这种传播方式类似于人群中的流行病一样一传十十传百，随着时间推移接收请求的服务器节点将会越来越多。

Gossip protocol 最早是在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出。主要用在分布式数据库系统中各个副本节点同步数据之用，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络，这区别与之前介绍的用于结构化网络中的 DHT 算法 Kadmelia。

我们知道，很多知名的 P2P 网络或区块链项目，比如 IPFS，Ethereum 等，都使用了 Kadmelia 算法，而大名鼎鼎的 Bitcoin 则是使用了 Gossip 协议来传播交易和区块信息

实际上，只要仔细分析一下场景就知道，Ethereum 使用 DHT 算法并不是很合理，因为它使用节点保存整个链数据，不像 IPFS 那样分片保存数据，因此 Ethereum 真正适合的协议应该像 Bitcoin 那样，是 Gossip 协议。

Gossip执行过程：Gossip过程由某个种子节点发起，当该节点由状态需要更新到网络中的其他节点时，他会随机选择周围几个节点散播消息，收到消息的节点也会重复这个过程，直至最终网络中所有的节点都收到了消息。这个过程要有一段时间，而且无法保证某个时刻所有的节点都能收到消息，但是能保证最终整个集群中的节点都会收到消息，因此他是一个最终一致性协议。

类似水滴，在水滴滴下后往周围传播波。

由于需要进行大量的网络请求，因此对于Gossip节点来说，他们的网络请求都应该是异步的，而且发出请求后不需要等待响应；因此会产生大量的消息冗余。这就类似于图的广度优先搜索，一圈一圈往外传播。

由于是异步的网络请求，因此Gossip可以十分频繁地进行传播。通常一个请求周期为一秒。Gossip在传播的过程中会选择相邻的节点，通常选择3个节点进行散播。每次收到消息的节点都选择尚未发送过的节点进行散播。收到消息的节点不再往发送节点散播，即A -> B，B在散播的时候不会再发往A。

演示如下：

• 首先节点1发起传播：
  
  传播到2和7后，由2、7继续这一过程
  
  直到整个集群的节点都收到消息
  

Gossip的特点

1. 扩展性
   网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致
2. 容错
   网络中任何节点的宕机和重启都不会影响Gossip消息的传播，Gossip协议具有天然的分布式系统容错特性
3. 去中心化
   Gossip协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是联通的，任意一个节点就可以把消息散播到全网
4. 一致性收敛
   Gossip协议中的消息会以一传十、十传百一样的指数级速度再网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了logN
5. 简单
   Gossip协议的过程及其简单，实现起来几乎没有太多复杂性

Gossip的缺点

1. 消息延迟：
   节点随机像少数几个几点发送消息，消息最终是通过多个轮次的散播而到达全网，不可避免地造成消息延迟
2. 消息冗余：
   节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此不可避免地引起同一节点多次接收同意消息，增加消息处理的压力。一次通信会对网络带宽、CPU资源造成很大的负载，而这些负载又受限于通信频率，该频率又影响着算法收敛的速度。
3. 拜占庭问题：
   如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出现问题

由于没有中心节点，所以没有一个同一的消息校验规则。只能区分消息的正确与否，无法区分消息的好坏。

上诉缺点的本质是因为Gossip是一个带冗余的容错算法，是一个最终一致性算法，无法保证在某一时刻所有节点状态一直，但可以保证“最终所有节点一致”，但这个最终时间是一个理论无法明确的时间点。所以适合AP场景的数据一致性处理，常见的有：P2P网络通信、Apache Cassandra、Redis Cluster、Consul

Márk Jelasity 在它的 Gossip一书中对其进行了归纳：

Gossip模块由两个线程组成：活动线程与被动线程。一个用于发起Gossip请求，一个用于接收其他节点传递过来的Gossip请求。

在这两段伪代码中:

• push表示发起信息交换的节点A随机选择联系节点B，并向其发送自己的信息，节点B在收到信息后更新比自己新的数据，一般有新信息的节点才会作为发起节点。
• pull表示发起信息交换的节点A随机选择联系节点B，并从对方获取信息。一般无新信息的节点才会作为发起节点
• push/pull表示发起信息交换的节点A像选择的节点B发送信息，同时从对方获取数据，用于更新自己的本地数据

活动线程

在一个循环中，每经过T段时间就发起一次Gossip请求。

1. 首先从selectPeer()函数中随机获取一个联系节点p
2. 如果是push的通信方式
               a. 发送方根据自身的网络信息以及跳数（默认0）生成描述符
               b. 将自身描述符与自身信息合并
               c. 将合并后的信息发送给p
               d. 如果没有新消息要发给p则直接发送一个空信号（为什么直接不发送呢？）
3. 如果是pull的通信方式
               a. 从p中获取他的信息
               b. 给他的跳数递增
               c. 将p的信息与本地的信息合并

被动线程

1. 从网络队列中获取节点p的消息
2. 将这个消息的跳数递增
3. 如何这个消息类型是pull
               a. 接收方根据自身的网络信息以及初始跳数（默认0）生成自身的描述符
               b. 将描述符与自身数据结合后返回给p
4. 将p的数据跟自身的数据合并

总结

从上面两种方式（pull、push）可以发现Gossip主要有两种请求方式：

• 将最新的变更传播出去
• 与其他节点进行数据交换，并将其他节点中的最新数据合并到本地，同时与其交换的结点也会更新到最新数据