Gossip的原始论文：《Efficient Reconciliation and Flow Control for Anti-Entropy Protocols》
1 概述
1）特点
- 最终一致性：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。
- 分布式容错：节点重启或新加入，状态最终会与其他节点达成一致，不影响消息传播
- 去中心化：不要求节点知道所有其他节点，节点之间完全对等，不需要任何的中心节点
- 一致性收敛：消息以指数级速度传播，系统状态可在很快的时间内收敛到一致。
2）缺点
- 消息延迟：节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的
- 消息冗余：冗余通信会对网路带宽、CUP资源造成很大的负载，而这些负载又受限于通信频率，该频率又影响着算法收敛的速度
3）适用场景
Gossip 比较适合在没有很高一致性要求的场景中用于信息的同步。信息达到同步的时间大概是 log(N)。
2 通信方式
两个节点（A、B）之间存在三种通信方式:
- 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的收敛速度是最快的。
3 工作方式
Gossip节点的工作方式分两种：
- Anti-Entropy（反熵）：以固定的概率传播所有的数据。
- 有完全的容错性
- 有较大的网络、CPU负载。
- Rumor-Mongering（谣言传播）：仅传播新到达的数据
- 有较小的网络、CPU负载
- 难以定义“最新”的边界，难以保证完全容错
- 对失败重启且超过“最新”期限的节点，无法保证最终一致性
一般采用Anti-Entropy模式，并由协调机制进行优化
协调机制
协调是在通信方式下的数据交换机制，主要讨论节点通信时，如何在有限的网络空间下，有效率地交换所有消息，达到最快的一致性。
1）精确协调（Precise Reconciliation）
- 精确协调希望在每次通信周期内都非常准确地消除双方的不一致性，具体表现为相互发送对方需要更新的数据。
- 因为每个节点都在并发与多个节点通信，理论上精确协调很难做到。
- 需要给每个数据项独立地维护自己的version
- 因为消息存在大小限制，每次选择发送一部分数据
- 可以随机选择一部分数据
- 也可确定性的选择数据（有最老优先和最新优先两种）
2）整体协调（Scuttlebutt Reconciliation）
- 整体协调是为每个节点上的宿主数据维护统一的version。
- 当与其他节点进行比较时，对比最高version，如相同说明这部分数据全部一致，否则再进行精确协调
- 整体协调对数据的选择也有两种方法
- 广度优先：根据整体version大小排序，也称为公平选择
- 深度优先：根据包含数据多少的排序，也称为非公平选择。实用推荐。
4 Cassandra中的实现
Cassandra实现了基于整体协调的push/push模式。
Gossip作用
Cassandra主要是使用Gossip完成三方面的功能：
- 失败检测
- 动态负载均衡
- 去中心化的弹性扩展
启动流程
在 Cassandra 启动时，会启动 Gossip 服务，Gossip 服务启动后会启动一个任务 GossipTask，每秒钟运行一次，这个任务会周期性与其他节点进行通信。
- GossipTask 在 Gossip 启动后阻塞在 listenGate 变量上，当 Gossip 服务调用 listen 时才开始运行；
- 首先更新本节点的心跳版本号，然后构造需要发送给其他节点的消息 gDigests；
- 从存活节点中随机选择一个节点发送、从失效节点中随机选取一个发送。如果当前存活节点数小于种子数，向其中一个种子节点发送消息；
- 检查节点状态。
工作流程
每一秒钟，Gossiper 会随机选择集群内的一个节点，初始化和它之间的 Gossip 会话。每一轮 Gossip 需要三组数据；
- Gossip 初始化器选择一个节点发送一个 GossipDigestSynMessage；
- 当节点收到这个信息，它返回一个 GossipDigestAackMessage；
- 当初始化器从节点收到一个 ack 信息，它会发送给节点一个 GossipDigestAck2Message 以完成本轮 Gossip。