本页目录
反熵与数据修复
read repair 只修被读到的数据,冷数据可能长期不一致。反熵用 Merkle tree 在后台系统性地比对和修复副本——gossip 驱动的增量比对最终把所有副本推向收敛。
概述
上一节讲了 read repair 和 hinted handoff 怎么在读写路径上"顺手"修数据。这些是被动修复——只修被读到的那条,大量冷数据可能长期不一致。反熵(anti-entropy)是主动的、系统的修复过程:后台持续比对副本,把不一致的都找出来修好,最终把所有副本推向一致(收敛)。这节的引擎是 Merkle tree——一种能高效比对两个数据集差异的树形结构。
为什么 read repair 不够
read repair 有三个盲区:
- 只修被读到的数据:冷数据一个月没被读,不一致就一个月没人管。
- 只修单个 key:不发现"整个副本都落后了"的情况。
- 不处理节点重加入:节点宕机一周后恢复,错过了大量写,hinted handoff 已过期——需要一次系统性的全量补齐。
反熵解决的就是这三个盲区。
Merkle tree:比对差异的引擎
两个节点上的数据(可能是几 GB 的 key-value 集合),怎么高效找出哪些 key 不一致?一条条比对太慢。Merkle tree 把比对变成 ~O(log n):
构建方法:
- 把本节点的所有 key 按范围分成若干 bucket(Merkle tree 的叶子)。
- 每个 bucket 计算 hash(该 bucket 内所有 key-value 的聚合 hash)。
- 上层节点 = hash(子节点 hash 的拼接)。
- root hash 标识整个数据集。
比对两个节点的数据:交换 root hash → 相同则一致;不同则递归比对子节点 hash → 定位到不一致的 bucket → 只对该 bucket 内的 key 做逐条比对和修复。两节点只需交换 hash,不需要传实际数据,找到不一致的 bucket 后才传那部分数据。
工程细节
- 动态构建:Merkle tree 不常驻——需要比对时才根据当前数据构建,比完丢弃。Cassandra 的
nodetool rebuild就触发构建。 - bucket 粒度:太细则 tree 太大、构建慢;太粗则定位不准、修太多。Cassandra 默认 15 层。
- 构建成本:需要扫全部数据算 hash,对大型数据集较重——所以反熵是后台低频(如每天一次),不是实时。
两种反熵模式
gossip 反熵:Dynamo 的做法
Gossip 协议不仅用于成员发现,也用于反熵。每个节点周期性随机选一个对端:
- 双方交换各自的 Merkle tree root hash。
- root 不一致 → 递归比对,找到不一致的 bucket。
- 对不一致的 key,用版本向量(or 最后写入时间戳)决定谁更新——不是简单地"我有你没有就推给你",因为双方都可能更新了同一个 key(冲突见冲突解决)。
- 更新的版本推给对方。
随机选对端的 gossip 反熵有良好数学性质:在 N 个节点间,若每次随机选一个对端,不一致数据在 O(log N) 轮内以高概率被修复——这是 Demers 1987 年 "Epidemic Algorithms" 的核心结论。
全量修复:节点重加入
节点宕机后重加入,错过大量写,hinted handoff 可能已过期,需要一次性补齐:
- 新节点从其他副本全量拉取自己负责的 token range 的数据(或增量:只拉宕机期间的变化——如果有 changelog)。
- 拉取时用 Merkle tree 做校验(确认拉回来的完整正确)。
- 拉完后构建本地索引和 Bloom filter。
Cassandra 的 nodetool rebuild、Riak 的 riak-admin transfers、HDFS DataNode 的 block report 都是这个模式。
一致性与修复的互动
一个反直觉的点:反熵修的是"最终一致性"的债;如果系统用强一致性(如 Raft),在正常运行时不需要反熵——Raft 的日志复制已经保证了 committed entry 在 majority 上一致。只有以下情况 Raft 才需要"修":
- snapshot 传输:新加入的 follower 落后太多,leader 已截断日志 → leader 发 snapshot(全量状态机快照),这本质是一次全量修复。
- 磁盘损坏:单节点本地数据损坏 → 从其他节点重新拉全量(与反熵的"节点重加入"类似)。
所以反熵的工程形态取决于一致性模型:复制策略越偏向最终一致性,反熵越重要,越需要工程化的 Merkle tree + gossip;越偏向强一致性,反熵越被"共识协议的日志复制 + snapshot"取代——但"重新拉全量"的需求还在,只是触发条件和工程实现不同。
修复调度与限流
反熵不是无代价的:构建 Merkle tree 扫全量数据(CPU + IO),传递 hash 和实际数据吃网络带宽。需要控制:
- 限流:限制修复占用的吞吐。Cassandra 的
compaction_throughput_mb_per_sec也影响修复期间的 streaming。 - 调度:避开业务高峰;或在低峰触发全量修复,高峰只做 read repair。
- 增量优先:如果系统有 changelog(最近变化的 key 列表),先修这部分,再全量校验。
权衡与失败模式
- read repair 当反熵用:冷数据永远修不到 → 定期全量反熵。
- Merkle tree 构建压垮 IO:反熵期间节点 CPU/磁盘飙升、影响正常读写 → 限流 + 低峰调度。
- 全量修复占满网络:拉取数 GB 数据时打满带宽 → streaming 限流 + 并行度控制。
- 版本冲突解决错误:反熵时用"最后写入胜出"盖掉并发更新 → 用版本向量而非时间戳(见冲突解决)。
参考
- 论文: "Dynamo"(反熵 via Merkle tree, 2007)、"Epidemic Algorithms for Replicated Database Maintenance"(Demers 1987)
Keywords: anti-entropy, Merkle tree, hash tree, incremental comparison, gossip repair, read repair, hinted handoff, replica migration, consistent hashing rebalance, full vs incremental repair, repair scheduling, repair throttling, version vector, epidemic algorithm