Gossip协议

Gossip 是什么？

Gossip协议是一个通信协议，一种传播消息的方式， 传播方式类似传染病毒， 也被也叫 称为Epidemic Protocol （流行病协议）。Gossip协议的主要用途就是信息传播和扩散，也被用于数据库复制，信息扩散，集群成员身份确认，故障探测等。

常见使用Gossip协议的分布式网络应用有：Redis Cluster、Consul、Apache Cassandra等，区块链网络中Bitcoin、Hyperldeger Fabric也是采用Gossip协议进行数据传播，而IPFS，Ethereum等使用了 Kadmelia 算法。

Gossip 协议原理

Gossip协议基本思想就是：一个节点想要分享一些信息给网络中的其他的一些节点。于是，它周期性的随机选择一些节点，并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情，即把这些信息传递给其他一些随机选择的节点。一般而言，信息会周期性的传递给N个目标节点，而不只是一个。这个N被称为fanout。

下面利用图解说明Gossip协议传播过程，如下图所示，Gossip协议是周期循环执行的。图中的公式表示Gossip协议把信息传播到每一个节点需要多少次循环动作，需要说明的是，各种颜色的圆圈代表节点，公式中的20表示整个集群有20个节点，base 4表示某个节点会随机选择4个目标节点传播消息。

如下图所示，红色的节点表示其已经“受到感染”，即传播信息的源头，连线表示这个初始化感染的节点能正常连接的节点（其不能连接的节点只能靠接下来感染的节点向其传播消息）。设置N等于4，所有连线中较粗的线路代表它第一次传播消息的随机选出的4个节点路线。

第一次消息完成传播后，新增了4个节点会被“感染”，即这4个节点也收到了消息。这时候，总计有5个节点变成红色。如下图：

那么在下一次传播周期时，总计有5个节点，且这5个节点每个节点都随机选择4个节点传播消息。最后，经过3次循环，20个节点全部被感染（都变成红色节点），即说明需要传播的消息已经传播给了所有节点：

需要说明的是，20个节点且设置fanout=4，公式结果是2.16，这只是个近似值。真实传递时，可能需要3次甚至4次循环才能让所有节点收到消息。这是因为每个节点在传播消息的时候，是随机选择N个节点的，这样的话，就有可能某个节点会被选中2次甚至更多次。

Gossip协议是可扩展的，因为它只需要O(logN) 个周期就能把消息传播给所有节点，在节点成倍扩大的情况下，循环次数指数增长比较缓慢，如fanout=4时， 80、320节点分别也只需要约3.16、4.16次循环。

Gossip 协议的优势

• 扩展性：网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。集群节点的数量增加，每个节点的负载也不会增加很多，这为大规模传播提供了可能性。

• 容错：网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。一个节点会多次分享某个需要传播的信息，即使不能连通某个节点，其他被感染的节点也会尝试向这个节点传播信息。

• 去中心化：Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。

• 一致性收敛：Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。

• 简单：Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

Gossip 协议的缺陷

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

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

Gossip 类型

Gossip 有两种类型：Anti-Entropy（反熵）：以固定的概率传播所有的数据；Rumor-Mongering（谣言传播）：仅传播新到达的数据。

Anti-Entropy（反熵）

Anti-Entropy 是 SI model，节点只有两种状态，Suspective 和 Infective，叫做 simple epidemics。

在 SI model 下，一个节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一致。由于在 SI model 下消息会不断反复的交换，因此消息数量是非常庞大的，无限制的（unbounded），这对一个系统来说是一个巨大的开销。

Rumor-Mongering（谣言传播）

在 Rumor Mongering (SIR Model) 模型下，消息可以发送得更频繁，因为消息只包含最新 update，体积更小。而且，一个 Rumor 消息在某个时间点之后会被标记为 removed，并且不再被传播，因此，SIR model 下，系统有一定的概率会不一致。

由于SIR Model 下某个时间点之后消息不再传播，因此消息是有限的，系统开销小。

Gossip 中通讯模式

在 Gossip 协议下，网络中两个节点之间有三种通信方式:

• 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 的收敛速度也是最快的。

参考：

https://www.jianshu.com/p/54eab117e6ae

https://www.jianshu.com/p/8279d6fd65bb