Gossip协议 / 八卦算法

(1) Gossip协议是什么

Gossip协议是一种”最终一致性”的分布式共识协议。

(1.1) Gossip工作过程

Gossip 的过程十分简单，它可以看作是以下两个步骤的简单循环：

1、如果有某一项信息(八卦消息)需要在整个网络(社交网络)所有节点中传播，那从信息源(第一个人)开始，选择一个固定的传播周期(譬如1秒)，随机选择它(关系好的k个人)相连接的k个节点(称为Fan-Out)来传播消息。

2、每一个节点收到消息(八卦消息)后，如果这个消息是它之前没有收到过的，将在下一个周期内，选择除了发送消息给它的那个节点外的其他相邻k个节点(关系好的人)发送相同的消息，直到最终网络中所有节点(所有人)都收到了消息，尽管这个过程需要一定时间，但是理论上最终网络的所有节点都会拥有相同的消息。

整个过程像八卦消息在人群中传播，也像病毒在人群中传播。

(2) Gossip协议的特点

(2.1) 优点

1、去中心化：节点都是对等的，任何节点出现问题都不会阻止其他节点继续传播。没有主节点概念，鲁棒性强。
2、速度快：因为每个节点都可以进行传播，所以速度是指数级的，就像病毒一样。
3、要求低：对网络节点的连通性和稳定性几乎没有任何要求。
4、支持动态、多节点：允许动态增加或减少节点，支持非常多的节点。
5、大多数节点：不需要大多数节点正常运行也能达到最终一致性
6、容错：任何节点重启或宕机都不会影响 Gossip 协议的运行，天然的分布式系统容错特性。

(2.1) 缺点

1、状态不一致：消息最终是通过多个轮次的散播而到达全网的，因此它必然会存在全网各节点状态不一致的情况。
2、时间随机：所有节点达到一致性是一个随机性的概率。由于是随机选取发送消息的节点，尽管可以在整体上测算出统计学意义上的传播速率，但对于个体消息来说，无法准确地预计到需要多长时间才能达成全网一致。
3、消息冗余：同一节点会多次接收同一消息，增加消息处理的压力，每一次通信都会对网络带宽、CPU 资源造成负载，进而影响达到最终一致性的时间。
4、拜占庭问题：如果有恶意节点出现，那么其他节点也会出问题。所以需要先修复故障节点。

(3) 反熵

如果有多个病毒在传播，要在所有节点间达成一致。
有多个八卦消息在传播，要让所有人知道。

(4) Gossip协议的应用

(4.1) Gossip协议在Redis Cluster通信时的应用

Redis Cluster 在运行时，每个实例上都会保存 Slot 和实例的对应关系（也就是 Slot 映射表），以及自身的状态信息。

为了让集群中的每个实例都知道其它所有实例的状态信息，实例之间会按照一定的规则进行通信。这个规则就是 Gossip协议。
Gossip 协议的工作原理可以概括成两点。

一是，每个实例之间会按照一定的频率，从集群中随机挑选一些实例，把 PING 消息发送给挑选出来的实例，用来检测这些实例是否在线，并交换彼此的状态信息。PING 消息中封装了发送消息的实例自身的状态信息、部分其它实例的状态信息，以及 Slot 映射表。
二是，一个实例在接收到 PING 消息后，会给发送 PING 消息的实例，发送一个 PONG 消息。PONG 消息包含的内容和 PING 消息一样。

Gossip 协议可以保证在一段时间后，集群中的每一个实例都能获得其它所有实例的状态信息。

这样一来，即使有新节点加入、节点故障、Slot 变更等事件发生，实例间也可以通过 PING、PONG 消息的传递，完成集群状态在每个实例上的同步。

(4.1.1) Redis Cluster间使用Gossip协议通信的不足

Redis Cluster 能保存的数据量以及支撑的吞吐量，跟集群的实例规模密切相关。Redis 官方给出了 Redis Cluster 的规模上限，就是一个集群运行 1000 个实例。

实例间的通信开销会随着实例规模增加而增大，在集群超过一定规模时（比如 800 节点），集群吞吐量反而会下降。

参考资料

[1] Gossip 协议
[2] 38 | 通信开销：限制Redis Cluster规模的关键因素
[3] 病毒传播：全靠 Gossip 协议