← 中文资源

简体中文版本

反熵

反熵是后台协调机制,通过比较副本并修复差异,找回故障、分区或提示丢失期间遗漏的写入。

阅读英文原文

工作原理

两个副本需要在不传输整个数据集的情况下找出差异。它们构建 Merkle 树:叶子散列单个键或范围,父节点散列其子节点。比较根散列很便宜;如果相同,副本一致。如果不同,只下降到有差异的分支,并交换受影响的行。最终传输量与差异成正比,而不是与数据量成正比。

修复可以是全量或增量。全量修复扫描所有范围,昂贵但彻底。增量修复跟踪已修复范围,聚焦最近写入,但依赖元数据准确性和墓碑处理。有些系统流式传输快照,与在线副本比较,然后应用缺失的变更。

删除与墓碑

删除会让协调变得复杂。如果一个副本删除了键,之后又从对等节点收到旧值,值可能复活。因此存储会写入墓碑,其保留期长于预期的最长修复间隔。如果修复频率低于墓碑保留期,已删除的数据可能复活。

何时使用

对所有需要持久性和最终收敛的最终一致存储使用反熵:Cassandra、Riak、Dynamo 风格系统以及多区域缓存。也应对搜索索引或物化视图等派生存储运行核对作业,因为源数据可能在索引不可用期间发生变化。

权衡与示例

修复消耗磁盘 I/O、网络带宽和 CPU,可能影响延迟。安排在非高峰并限流会有帮助。Merkle 树减少传输,但需要稳定的范围边界和一致性哈希。全量修复更简单、更可信;增量修复更快,却更容易出错。

示例:一个节点离线两天,超过了提示窗口。修复按令牌范围比较 Merkle 树,发现 40,000 个不匹配的键,只流式传输这些行。没有修复,这些写入会永久缺失,即使集群看起来健康。