病毒传播：全靠 Gossip 协议
病毒传播：全靠 Gossip 协议
一、背景
假如我是一个小病毒，其他病毒都叫我小 B，我长得就是下图这个样子了。
我现在已经有 100 nm 大小了，我还有很多触角，人类把我的触角称为冠，所以给我起了个学术名：冠状病毒。对于这个学术名，我一直不满意，怎么能用外貌来取名呢，这是以貌取毒。
我出生在一个蝙蝠身上，每到晚上，这只动物就到处觅食，它最喜欢的就是在森林中觅食，但最近森林的范围急剧减少，它不得不到人类居住的城市来觅食，看着五颜六色的灯光，我如痴如醉。
这只蝙蝠携带了 100 多种病毒，比如埃博拉病毒、MERS 病毒，我每天和这些病毒一起嬉戏游玩。SARS 病毒是我的近亲，2002 年的时候，它还造成了一次不小的传染病疫情，轰动了整个病毒界，人类称它为非典。
二、意外
这天晚上，乌云密布，空气混浊，蝙蝠飞到了密林深处，突然浑身被一股电流击中，猝然倒地，一只大网将其捕获，随之而来的是穿着一袭黑色大衣的人类把蝙蝠关进了笼子里面。
随后的几天，蝙蝠一直被关在笼子里面，直到有一天，蝙蝠被带到了一个随处可见野生动物的地方，但这些动物要么是被粗绳绑起来了，要么是被关在铁笼里。一个肥头大耳的人类走进了蝙蝠，他将手里攒着的一大叠钞票给了黑衣人后，带走了蝙蝠。
蝙蝠可能与肥头大耳的人类走得太近，我被传到了人类的的手上，随后又通过他接触的食物进入到了他的口中，进而进入到了他的体内。
三、种子节点
进入到人体中后，我欺骗了人类的免疫系统，顺利进入到人体细胞中，释放自己的 RNA，通过正常细胞的 RNA 聚合酶来复制自己的 RNA，从而复制出更多的病毒，进而攻击人体肺部器官。
过了几天后，这名人类出现了发烧现象，同时伴有咳嗽症状，而我的同伴也通过喷嚏传到了其他人体中，同样开始大量复制自己。
一传十，十传百，这个地级市已有数千名人类被病毒感染。而我就被称作种子节点，而那名人类被称作零号病人。
四、Gossip 协议
人体内的正常细胞对我的传染性非常感兴趣。
正常细胞：“冠状大哥，你是怎么这么快进行传播的啊？”
我：“其实我是利用了
Gossip协议。”我：Gossip 主要有三大功能，直接邮寄、反熵、谣言传播。
Gossip 的中文意思就是流言蜚语，该协议就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。这个就是实现了最终一致性的协议。
4.1 直接邮寄
直接发送需要更新的数据到其他节点，当数据发送失败时，将数据缓存下来，然后重传。如下图所示，人类 A 直接将病毒传染给了 C 和 E，而 B 和 D 没有被感染到，需要重新传染。
优点：实现容易，数据同步及时。
缺点：可能会因为重试的缓存队列满了而丢数据。无法实现最终一致性。
那如何实现最终一致性呢？那就要用到第二种功能了：反熵。
4.2 反熵
反熵这个名词怎么理解呢？
熵指混乱程度，反熵就是消除不同节点间数据的差异，提升节点间数据的相似度。
反熵的过程：
- （1）集群中的节点，每隔段时间就随机选择某个其他节点。
- （2）互相交换自己的所有数据来消除两者之间的差异。
- （3）实现数据的最终一致性。
下面举个病毒传染的例子来说明反熵。
首先人类 A 被感染了两种病毒，分别是病毒 T 和病毒 R，如下图所示：
人类 E 被感染了三种病毒，分别是病毒 T、病毒 S、病毒 Y，如下图所示：
人类 A 将携带的病毒 T 和 R 传染给了人类 E，而 E 本来就携带了病毒 T，所以最后会被传染四种病毒：T、S、Y、R。也就是说通过反熵的方式，修复了人类 E 中缺失的病毒 R。如下图所示：
其实，反熵主要有三种方式：推、拉、推和拉。
4.2.1 推
推：将自己的副本数据推给对象，修复对方副本中的熵。
如下图所示，人类 A 将病毒 R 传染（推）给了人类 E，E 中就包含所有 A 的病毒了。
4.2.2 拉
拉：拉取对方中的所有副本数据，修复自己副本中的熵。
如下图所示：人类 A 只有病毒 T 和 R，经过主动拉方式后，将人类 E 的病毒 S 和 病毒 Y 同步到人类 A 身上了，最后，人类 A 携带四种病毒：T、R、S、Y。
4.2.3 推拉
推拉：同时修复自己副本和对象副本中的熵。
如下图所示：人类 A 和 人类 E 通过推拉的方式最后都被感染了相同的四种病毒：T、R、S、Y。
4.2.4 反熵的缺点
（1）通过上面推、拉、推拉的方式，我们可以主要到，反熵是需要节点两两交换和比对自己所有的数据，这样来看的话，通讯成本是很高的，所以不建议实际场景中频繁地执行反熵。
那有没有办法来减少反熵的次数呢？
答案是有的，我们可以通过引入校验和等机制来降低需要对比的数据量和通讯信息。
（2）执行反熵时，相关节点都是已知的，且节点数量不能太多。如果节点动态变化或节点数过多，反熵就不合适。
那有没有办法来解决动态、多节点的最终一致性呢？
答案是有的，那就要用到 Gossip 协议的第三种传播功能了，谣言传播或者叫流行病传播。
4.3 流行病传播
4.3.1 过程
Gossip 协议的第三种传播功能，流行病传播，也就是广泛地散播病毒。
如下图所示：A 传染给了 B 和 E，B 传染给了 C 和 D，D 传染给了 F 和 G。最后 ABCDEFG 都被感染了。
在分布式系统中，当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有节点都存储了该数据，可以理解为之前讲的反熵中的推的方式。如下图所示：
4.3.2 缺点
流行病传播的方式有如下缺点：
- 时间随机：所有节点达到一致性是一个随机性的概率。可以改进反熵的流程：使用闭环修复。
- 消息冗余：同一节点会多次接收同一消息，增加消息处理的压力，每一次通信都会对网络带宽、CPU 资源造成负载，进而影响达到最终一致性的时间。
- 拜占庭问题：如果有恶意节点出现，那么其他节点也会出问题。所以需要先修复故障节点。
4.3.3 优点
- 支持动态、多节点：允许动态增加或减少节点，支持非常多的节点。
- 大多数节点：不需要大多数节点正常运行也能达到最终一致性
- 容错：任何节点重启或宕机都不会影响 Gossip 协议的运行，天然的分布式系统容错特性。
- 去中心化：节点都是对等的，没有特殊节点。任何节点出现问题都不会阻止其他节点继续执行反熵。
- 速度快：因为每个节点都可以进行传播，所以速度是指数级的，就像现在的新冠病毒一样。
因为 Gossip 协议是一个带冗余的容错算法，为了保证最终一致性的算法。虽然所有节点达到一致的时间点不明确，但也可以通过改进反熵的执行过程来达到可预测，比如闭环反熵（不在本文展开论述）。
五、总结
本文通过一个携带冠状病毒的蝙蝠传染人类的故事来讲解了 Gossip 协议。
Gossip 协议是一种
异步修复、实现最终一致性的协议。优先考虑反熵。反熵在
存储组件中用得比较多。比如 Cassandra、InfluxDB。谣言传播（流行病传播）具有传染性，节点之间
相互传染。适合动态变化的分布式系统。比如 Cassandra 动态管理集群的节点状态。实际场景，
直接邮寄一定要实现，性能损耗最低。通过发送更新数据或缓存重传就能修复数据的不一致。在存储组件中，节点已知，采用
反熵修复数据副本的不一致。集群节点变化时，或节点较多时，采用
谣言传播方式，来同步更新多节点的数据，来实现最终一致性。Gossip 的三种功能其实都是为了实现反熵，第一种用消息队列，第二种用推拉消息，第三种用散播谣言。
如果节点出现
故障，需要先修复故障节点。