docs/distributed-system/protocol/gossip-protocol.md
在分布式系统中，不同节点间共享状态是一个基本需求。
一种简单的方法是 集中式广播：由中心节点向所有其他节点同步信息。这种方式适合中心化系统，但存在明显缺陷：当节点数量增加时，同步效率下降（O(N) 复杂度），且过度依赖中心节点，存在单点故障风险。
分散式传播 的 Gossip 协议 提供了一种去中心化的替代方案。
Gossip（闲话协议）也称 Epidemic 协议（流行病协议），灵感来源于流行病传播的随机特性。其核心思想是：每个节点周期性地随机选择若干其他节点交换信息，使数据像病毒传播一样扩散至整个网络。
Gossip 协议最早由 Demers 等人在 1987 年的论文 《Epidemic Algorithms for Replicated Database Maintenance》 中提出，用于解决分布式数据库的副本同步问题。
定义：Gossip 协议是一种去中心化的通信协议，通过节点间的随机信息交换，在非拜占庭且不存在永久网络分区、节点持续周期性交换的前提下，使集群内所有节点的状态达到最终一致性。
重要区分：Gossip 是信息传播协议，不是共识算法（如 Raft/Paxos）。共识算法保证强一致性与安全性，Gossip 只保证最终一致性，不适用于选主或状态机复制等需要强一致的场景。
关键特性：
Gossip 协议被广泛应用于分布式系统：
以 Redis Cluster（3.0+）为例：
Redis Cluster 是一个去中心化的分布式缓存方案，各节点通过 Gossip 协议交换集群状态，包括：节点信息、槽位分配、节点状态（在线/PFAIL/FAIL）。
Gossip 消息类型：
| 消息类型 | 用途 |
|---|---|
| MEET | 将指定节点添加进集群 |
| PING | 周期性发送，交换节点状态 |
| PONG | 响应 PING，携带自身状态信息 |
| FAIL | 广播节点故障标记 |
注：在实现上，MEET/PING/PONG 共享同一类消息结构；PONG 是对 PING/MEET 的响应，MEET 相当于"强制握手"的 PING。
故障检测流程：
cluster-node-timeout（常见为 15s，具体以配置为准）内未收到 B 的响应，将 B 标记为 PFAIL（疑似下线）下图就是主从架构的 Redis Cluster 的示意图，图中的虚线代表的就是各个节点之间使用 Gossip 进行通信，实线表示主从复制。
注：Redis Cluster 主要通过 PING/PONG 的增量 gossip 传播节点/槽位/故障信息（带时间戳/标志位等），而不是采用像 Dynamo 那样基于 Merkle tree 的反熵对账流程。
关于 Redis Cluster 的详细介绍，可以查看这篇文章 Redis 集群详解(付费)。
Gossip 协议有两种主要传播模式：反熵 和 谣言传播。
定义：节点间交换完整数据（或数据摘要），消除差异，实现最终一致。
熵的物理含义是系统混乱程度；反熵即降低节点间数据差异，提升一致性。
根据维基百科：
熵的概念最早起源于物理学，用于度量一个热力学系统的混乱程度。熵最好理解为不确定性的量度而不是确定性的量度，因为越随机的信源的熵越大。
在这里，你可以把反熵中的熵理解为节点之间数据的混乱程度/差异性，反熵就是指消除不同节点中数据的差异，提升节点间数据的相似度，从而降低熵值。
三种实现方式：
| 方式 | 描述 | 适用场景 |
|---|---|---|
| Push | 发送方将自己的全部数据推送给接收方 | 发送方有新数据 |
| Pull | 接收方拉取发送方的全部数据 | 接收方数据陈旧 |
| Push-Pull | 双向交换数据，并比较差异 | 最高效，最常用 |
伪代码如下：
收敛特性：在均匀随机选点、fanout 为常数的模型下，期望 O(log N) 轮覆盖全部节点（常见估算可用 log₂N 量级）
部分系统（如 InfluxDB）采用确定性闭环调度（如环形拓扑）代替随机选择，可在确定轮次内完成同步。这属于反熵的工程衍生实现，而非标准 Gossip 协议的核心机制。确定性调度牺牲了随机性的容错优势，换取可预测的收敛时间。
权衡：闭环调度可在确定时间内完成同步，但牺牲了容错性（环中节点故障影响传播路径），且难以适应节点动态增删。
适用场景：需要较低残留率（尽量不漏更新）、允许后台周期性对账修复；数据量大时必须依赖摘要/树等增量比对以控制成本。
生产级优化：在大规模分布式存储（如 Cassandra、DynamoDB）中，节点数据量可达 TB 级，直接交换完整数据不现实。生产系统使用 Merkle Tree（默克尔树） 进行增量差异比对：两节点先交换 Merkle Tree 根哈希，若有差异则递归比对子树，在树高 O(log M) 的层级上定位差异（M 为该范围内条目数），随后仅传输增量数据。
定义：当节点有新数据时，变为活跃节点，周期性地向随机节点广播该数据，直到所有节点都收到。
与反熵的区别：
去重机制：生产环境（如 Redis Cluster）通过版本号或消息 ID 去重，避免重复处理相同消息。
如下图所示（下图来自于INTRODUCTION TO GOSSIP 这篇文章）：
伪代码如下：
收敛特性：在均匀随机选点、fanout 为常数的模型下，O(log N) 轮后以高概率覆盖全部节点。
注意事项：
| 要点 | 反熵 | 谣言传播 |
|---|---|---|
| 传播内容 | 完整数据（或摘要） | 仅新增数据（Delta） |
| 适用场景 | 节点数量适中 | 节点数量较多/动态变化 |
| 消息开销 | 较大 | 较小 |
| 收敛范围 | 收敛到最新数据（全量同步） | 收敛到已知数据（增量传播） |
优势：
实现简单：协议逻辑简单，易于理解
容错性强：容忍节点宕机、网络分区、动态增删节点。新增或重启的节点在理想情况下最终一定会和其他节点的状态达到一致。
扩展性好：收敛时间为 O(log N)，当 N 较大（如 N > 100）时，并行传播通常比中心节点单播更快（后者需 O(N) 轮次）。在典型 rumor spreading 模型下代价是消息总量为 O(N log N)（具体取决于实现策略与停止条件），存在冗余开销。
缺陷：
最终一致：消息需通过多轮传播才能覆盖整个网络，存在不一致窗口期。达到一致的具体时间取决于网络状况、gossip 间隔（视实现配置而定，常见 100ms-1s）与节点规模。
不适用拜占庭环境：Gossip 协议的设计假设是非拜占庭环境，不处理恶意节点的情况（节点不会伪造或篡改消息）。
消息冗余：由于传播的随机性，同一节点可能重复收到相同消息，需配合去重机制。