Anti-Entropy
熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致。本质上，反熵是一种通过异步修复实现最终一致性的方法。
--钝悟
节点周期性随机选择节点,交换全量数据消除差异.周期不会结束.
若运行时间较长会导致传递数据过大.
状态
Susceptible(易感): 节点还没接收到这条消息
Infective(传染性的): 节点已经持有这条消息，并且会周期性地向其他节点传播全量消息
过程
1. 节点周期性触发
- 节点 A 每隔固定时间 T (例如 5 秒) 执行 Anti-Entropy
- 随机选择一个邻居节点 B (fan-out=1,此时只会选择一个邻居节点)
2. 交换状态
- 节点 A 将自己完整状态发送给 B
- 节点 B 将自己完整状态发送给 A
3. 计算差异
- A 接收到 B 的状态 → 找出 B 拥有但自己缺失的部分 → 更新自己
- B 接收到 A 的状态 → 找出 A 拥有但自己缺失的部分 → 更新自己
4. 重复执行
- 节点 A 等待下一个周期，再随机选择一个节点执行同样操作
- 所有节点独立、周期性地执行这个流程
优点
最终一致性确定
节点周期性全量或差异同步，理论上所有节点最终必然一致。
容错能力强
即使某轮传播失败，下轮周期仍会补救，适应网络不稳定。
修复遗漏节点
无论之前哪个节点没收到消息，周期性同步最终都会把缺失数据同步过去。
适合大规模网络同步
不依赖单轮成功，概率模型收敛分析简单可靠。
缺点
传播速度相对慢
周期性触发可能导致新消息扩散比 Rumor-Mongering 慢。
带宽消耗大
全量或差异同步比单条消息增量传播消耗更多网络资源。
实现稍复杂
需要周期触发、状态摘要或差异计算(摘要和差异是现代实践,论文中没有)，以及节点间同步机制。
Rumor-Mongering
仅传播最新数据. 每次传播都随机选择节点进行传播, 如果节点已经持有消息(即传播失败), 或因网络超时传播失败, 计数器+1, 达到阈值后停止.
由于是增量传播,数据包小,不会无限制传播.
状态
Susceptible(易感): 节点还没接收到这条消息
Infective(传染性的): 节点已经持有这条消息，并且会周期性地向其他节点增量传播消息。
Removed: 当收到被传播节点持有此消息,或传播次数超过阈值时,停止传播这条消息
过程
论文传播停止是因为全网络节点已感染有点难理解,这里用工程实践版的
1. 收到消息
- 节点 A 收到消息
- 更新 infected 列表标记这个消息已知
2. 选择目标
- 节点 A 从自己的邻居列表中随机选择几个节点 (fan-out数量)
3. 尝试发送消息
对每个目标节点 B：
如果 B 没有收到过消息 M:
- B 接收消息 M,并在下一轮也会对自己的邻居进行 rumor-mongering 传播
- 节点 A 的计数器 不增加
如果 B 已经持有消息 M:
- 节点 A 的计数器 +1 (表示一次失败传播)
如果 B 网络超时:
- 节点节点 A 的计数器 +1 (表示一次失败传播)
4. 检查停止条件
节点 A 对消息 M 的传播计数器达到阈值 (例如 3):
- 节点 A 停止传播消息 M
- 节点 A 不再尝试发送 M 给其他节点
5. 下一轮传播
- 对于尚未停止的节点,重复 1-3
- 节点每轮随机选择邻居,尝试传播消息,直到自己的计数器达到阈值
优点
快速传播新消息
节点收到新消息就立即传播,消息扩散速度快
低带宽开销（增量传播）
只发送新消息,不发送全量状态
实现简单
逻辑只需随机选择邻居并推送消息,无需全局状态或复杂同步表
概率性最终一致性
随着轮次增加,高概率网络大部分节点最终会收到消息
缺点
潜在不一致问题
- 节点 A 向节点 B 传播消息 M，但因为网络超时/丢包, B 没有收到 → 本轮传播失败
- A 后续随机选择节点传播时 可能没再次选择 B
- A 的失败计数器达到阈值 → 停止传播
- 如果其他节点也因为随机选择没选择到 B,由于Rumor-mongering不会向Anti-Entropy主动周期性和邻居节点同步, 所以 B 在下次被传播前缺失了这条消息
结果：网络中存在少数节点缺失该消息 → 高概率最终一致,但不是强一致性
可靠性受网络不稳定影响大
网络超时或节点离线可能导致消息传播失败,且节点不会自动重新尝试
收敛不可预测
消息最终传播到全网的时间依赖于随机性和阈值,不保证精确收敛
不能保证强一致性
适合快速扩散场景,但不能保证每个节点最终状态完全一致
因此现代实践中先使用Rumor-mongering快速传播,再使用Anti-Entropy保证最终一致性
通信模式
Push
节点A全量推送自己所有数据给B节点,B节点对比差异更新自己
Pull
- 节点A将自己的key,version推送给B
- B对比本地数据,增量推送(包含key,value,version)比A新的数据给A
- A对比更新自己
Push-Pull
- 节点A将自己的key,version推送给B
- B对比本地数据,增量推送(包含key,value,version)比A新的数据给A
- A对比更新自己,再增量推送(包含key,value,version)比B新的数据给B
- B对比更新自己
注意: Anti-Entropy和Rumor-mongering可以随意选择Push,Pull,Push-Pull搭配,而不是固定的.
Reference
[]: https://dunwu.github.io/waterdrop/pages/88db2f5d "分布式算法 Gossip"
[]: https://chatgpt.com/ "ChatGPT"