反熵与数据修复

复制把新写入传播到副本，修复把已经出现的差异找出来并消除。节点长期离线、提示记录过期、迁移中断或介质损坏，都可能留下正常请求路径未覆盖的问题。

读写路径 中的读修复只覆盖被访问的数据与参与读取的副本。反熵通过主动比较共同负责的数据范围，把冷数据也纳入检查。它不是某一个特定命令，而是一类让副本重新趋于一致的机制。

收敛需要哪些条件

设两个副本最终都收到同一组更新。如果它们使用相同且适当的冲突合并规则，就应产生相同状态。要实现这个目标，至少需要更新最终可达、差异可发现、修复有资源执行，以及删除和版本信息没有过早丢弃。

因此，最终一致性并不等于“放着总会自己好”。网络永久分区、修复始终被饿死、版本比较规则不同，都可能阻止收敛。对这些前提的运维保障，本身就是一致性设计的一部分。

Merkle tree：用摘要排除相同范围

逐条交换整个数据集可以发现差异，但传输成本高。Merkle tree 将相同划分下的数据范围映射为叶摘要，再逐层对孩子摘要求哈希。若根摘要相同，在哈希碰撞可忽略和编码一致的前提下，可以跳过整个范围；否则向不同的子树继续下降。

比较双方必须使用相同的 key 范围、顺序、编码与版本口径。若一方将墓碑纳入哈希，另一方只哈希当前值，摘要差异可能来自比较规则而非副本故障。

树的作用是减少不必要的交换，不是把所有修复成本变成 O(log n)。构建 n 条记录的摘要通常至少需要扫描相应数据；单个局部差异的定位可沿树高下降，但大量差异会触及很多节点，最后还要传输实际记录。树若持久维护，更新也有额外成本。

用八个固定范围，实际定位一个差异

下面让双方预先约定八个范围，每个范围保存按 key 排序的记录，记录格式为 (key, version, value)。模型只使用字符串、整数和 null；双方共享 JSON 编码约定，叶节点与内部节点分别加类型前缀。这样比较的不只是当前 value，还包括版本与删除信息。

from hashlib import sha256
import json

def tree(ranges):
    n = len(ranges)
    if n == 0 or n & (n - 1):
        raise ValueError("这个示例要求范围数为 2 的幂")
    nodes = [b""] * (2 * n)
    for i, records in enumerate(ranges):
        data = json.dumps(sorted(records, key=lambda r: r[0]),
                          ensure_ascii=True, separators=(",", ":")).encode("ascii")
        nodes[n + i] = sha256(b"leaf:" + data).digest()
    for i in range(n - 1, 0, -1):
        nodes[i] = sha256(b"node:" + nodes[2*i] + nodes[2*i+1]).digest()
    return nodes

def differences(left, right):
    if len(left) != len(right):
        raise ValueError("树的范围划分必须一致")
    n, compared, changed = len(left) // 2, 0, []
    def visit(i):
        nonlocal compared
        compared += 1
        if left[i] == right[i]:
            return
        if i >= n:
            changed.append(i - n)
        else:
            visit(2*i)
            visit(2*i+1)
    visit(1)
    return changed, compared

A = [[(f"k{i}", 1, "old")] for i in range(8)]
B = [list(records) for records in A]
B[6] = [("k6", 2, "new")]
assert differences(tree(A), tree(B)) == ([6], 7)
assert differences(tree(A), tree(A)) == ([], 1)
C = [[(f"k{i}", 2, "new")] for i in range(8)]
assert differences(tree(A), tree(C)) == (list(range(8)), 15)
assert tree([[("k", 1, "same")]]) != tree([[("k", 2, "same")]])
assert tree([[("k", 2, None)]]) != tree([[]])  # 墓碑不等于无记录
assert tree([[('b', 1, 'v'), ('a', 1, 'v')]]) == tree([[('a', 1, 'v'), ('b', 1, 'v')]])

一个差异时比较 7 对摘要：根一次，每层比较两个孩子，共三层。范围 0–3 和 4–5 的相同子树不再展开，最终只定位到范围 6。八个范围都不同时，需要比较全部 15 个节点；“树高只有 3”并不能让所有差异都只花 3 次比较。

计数只包含两棵已经构建好的树之间的摘要比较，没有包含每个范围的扫描、排序、哈希，以及差异记录的传输。单个叶范围也可能有百万条记录，定位到叶子后仍需要进一步比较。范围边界必须由相同元数据固定，不能因为两边记录数不同就各自按数量平分，否则相同位置的叶子已不是同一批 key。

差异变多时，树还能跳过多少范围？

摘要相同意味着可以跳过相应子树，摘要不同则只提供继续比较的理由，并不告诉我们谁更新。下面用真实 SHA-256 计算两棵树；改变一个叶子可看到比较路径，改变全部叶子会触及全部 15 个节点。短哈希只用于显示，比较使用完整摘要，计数也只统计已建好树之间的比较。

从发现不同到决定如何修

假设某个范围里，A 有 key=X, version=7，B 有 version=5。只有当版本规则证明 7 覆盖 5 时，才可把 7 当作新状态。两个向量版本并发时，摘要只告诉我们不同，不能替应用选择赢家。

修复需要与正常写入使用同一套合并规则。若业务保留并发 sibling，修复应传播必要版本；若采用 LWW，就要接受其时间戳排序与丢弃并发值的语义。详见 冲突解决。

Gossip 可以传播成员或调度信息，反熵负责数据差异；两者可以组合，但不是所有 Merkle 修复都由 gossip 驱动。理想化消息扩散的轮数也不能直接当成包含扫描、传输和合并的数据库修复耗时。

删除为什么也要复制：Tombstone

删除如果只是在本地移除记录，就无法告诉一个仍持有旧值的副本“这条记录被删过”。墓碑保留删除事实，使合并规则能判定旧值应被压过。

考虑 A、B 已记录删除，C 离线仍保留旧值。若 A、B 在 C 回来之前清除了唯一删除证据，后续修复可能把 C 的旧值重新传播回来。这就是删除复活问题。

墓碑保留期、最长离线时间、修复覆盖周期和节点重加入策略必须协同。并不是把一个过期参数设得很大就万事大吉：需要证明相关副本已经收到删除，或者在重加入时强制重建。Cassandra 的修复与 tombstone 约束见 Repair。

墓碑保留的是一条有版本的事实

为简化，只考虑同一 key 的严格递增版本：版本 5 是旧值，版本 6 是删除。None 表示该副本没有任何记录，(6, None) 才表示版本 6 的删除事实。

def merge(a, b):
    candidates = [record for record in (a, b) if record is not None]
    return max(candidates, key=lambda record: record[0]) if candidates else None

old = (5, "value")
deleted = (6, None)
assert merge(deleted, old) == deleted
assert merge(None, old) == old  # 提前丢掉删除证据，旧值就重新成为赢家
assert merge(deleted, (7, "recreated")) == (7, "recreated")

第三个断言也很关键：墓碑不是“以后永远禁止这个 key”。业务允许重新创建时，新的有效版本可以覆盖删除；被阻止的是旧值复活。实际系统若允许同版本不同内容，还必须定义确定的冲突规则，不能直接套用这个只比较版本号的函数。

安全清理需要覆盖证据：相关旧副本已收到删除，或被排除并在重新加入时完整重建。只看到两个在线副本摘要相同，不代表那个长期离线的第三副本已经安全。修复完成记录因此要包含副本集合及范围，不能只保存一个集群级“最近成功时间”。

全量、增量与节点重建

这些名称在不同产品中有不同实现。Cassandra 的 repair 与 rebuild 不能互相替代，增量修复也不等同于读取一个通用变更日志。操作范围和版本约束应查部署版本文档。

在持续写入下做摘要比较，还需要一致的数据视图或版本截点。否则刚比较完根摘要，数据又变化，反复扫描可能把活跃写入误当成无法修复的差异。快照、分阶段协议或重新验证用于界定本轮覆盖边界。

强一致复制也需要恢复与完整性检查

共识协议在自身故障模型下维护日志顺序和提交安全，落后 follower 可以补日志或安装快照。但静默磁盘损坏、错误的软件 apply、备份损坏等，可能超出协议假设。

所以不能写成“有 Raft 就不需要数据校验”。日志追赶、状态快照、校验和与副本一致性检查解决不同层面的问题。修复成功还应核对逻辑状态，而不只是网络传输返回成功。

修复预算如何估算

假设一轮需要传输 600 GB 的差异数据，给修复分配 50 MB/s 的持续带宽，仅传输理论上就约需 12000 秒，即 3.3 小时，尚未包含摘要构建、磁盘读取和合并。若需要在两小时内完成，当前预算显然不足。

若修复过程中仍以 10 MB/s 产生需要补齐的差异，净消除速率只有 40 MB/s。把所有量按十进制 GB、MB 计算：

from fractions import Fraction
backlog = 600 * 10**9
repair_rate, new_difference_rate = 50 * 10**6, 10 * 10**6
assert Fraction(backlog, repair_rate) == 12000
assert Fraction(backlog, repair_rate - new_difference_rate) == 15000
hours = Fraction(15000, 3600)
assert hours == Fraction(25, 6)  # 约 4.17 小时
required_rate = Fraction(backlog, 2 * 3600) + new_difference_rate
assert required_rate == Fraction(280_000_000, 3)  # 约 93.33 MB/s

因此两小时清空积压需要约 93.33 MB/s 的有效修复吞吐，且尚未计入额外 I/O 瓶颈。如果差异生成速率达到或超过修复速率，这个稳态模型没有有限的追平时间。这里的“新增差异”是尚未送达目标副本、确需修复的字节，不能直接拿整个业务写入吞吐替代；覆盖更新和压缩还可能改变实际待传字节。

这类估算用于反推并行度、运行窗口与资源余量。修复限流过低可能永远追不上新增差异，过高则与线上读写争用磁盘和网络。需要分别监测扫描、streaming、合并和未覆盖范围，不能只看“任务已启动”。

完整验收应回答：哪些 token/key 范围在何时被比较；哪些副本参与；是否有跳过或失败；删除保留期限之前能否覆盖完；修复后摘要或版本检查是否通过。

参考

• Dynamo：基于 Merkle tree 的副本同步
• Cassandra：Repair
• Cassandra：Read Repair
• Cassandra：Hints

关键词：anti-entropy、Merkle tree、收敛、tombstone、删除复活、full repair、incremental repair、rebuild