Gossip协议简介

一. 引言&背景

Gossip 协议（gossip protocol）又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用。利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。

该协议在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出。主要用在分布式数据库系统中各个副本节点同步数据之用，这种场景的一个最大特点就是组成的网络的节点都是对等节点的非结构化网络。

二. 原理剖析

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

Márk Jelasity 在它的 《Gossip》一书中对其步骤进行了归纳，如下：

前面说了节点会将信息传播到整个网络中，那么节点在什么情况下发起信息交换？这就涉及到 gossip 协议的类型。目前主要有两种方法：

• Anti-Entropy（反熵）：以固定的概率传播所有的数据

• Rumor-Mongering（谣言传播）：仅传播新到达的数据

Anti-Entropy

Anti-Entropy 的主要工作方式是：每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。Anti-Entropy 这种方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，以此不会频繁使用。

Anti-Entropy 使用“simple epidemics”的方式，所以其包含两种状态：susceptible 和 infective，这种模型也称为 SI model。处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。

Rumor-Mongering

Rumor-Mongering 的主要工作方式是：当一个节点有了新的信息后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新信息。直到所有的节点都知道该新信息。因为节点之间只是交换新信息，所有大大减少了通信的负担。

Rumor-Mongering 使用“complex epidemics”方法，相比 Anti-Entropy 多了一种状态：removed，这种模型也称为 SIR model。处于 removed 状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

因为 Rumor 消息会在某个时间标记为 removed，然后不会发送给其他节点，所以 Rumor-Mongering 类型的 gossip 协议有极小概率使得更新不会达到所有节点。

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。不管是 Anti-Entropy 还是 Rumor-Mongering 都涉及到节点间的数据交互方式，节点间的交互方式主要有三种：Push、Pull 以及 Push&Pull。

Push-based 的 Gossip 协议：

• 网络中的某个节点随机选择N个节点作为数据接收对象

• 该节点向其选中的N个节点传输相应数据

• 接收到数据的节点对数据进行存储

• 接收到数据的节点再从第一步开始周期性执行

Pull-based 的 Gossip 协议，正好相反：

• 集群内的所有节点，随机选择其它 k 个节点询问有没有新数据

• 接收到请求的节点，返回新数据

三. 缺陷

分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要是两个：

1）消息的延迟

由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。

2）消息冗余

Gossip 协议规定，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。

Gossip与DSP

DSP Labs 正在打造新一代的互联网协议层的基础网络，专注于提供高效，稳定，安全的底层文件数据存储分发网络协议，它将是一个可以服务于任何基于分布式存储网络的下一代应用的基础设施；很显然，在DSP的愿景网络里，会有海量的交互分发的数据；针对分发诉求的数据，有的是对时间敏感的，有的是不敏感的；针对时间非敏感数据，DSP LABS建议考虑使用Gossip协议，进行数据分发。延寻gossip的分发思想，不仅可以提高网络资源的利用率，同时满足上层对数据全网覆盖的诉求。是一个可以两全兼顾的策略。