千万级数据同步与 ETL 实战（五）：桶摘要、Merkle Tree 与 IBLT 对账
两个节点各保存 1000 万条记录，直接交换全部身份键和行指纹可以得到精确差异，但通信量和排序成本很高。若双方已经维护稳定分桶和本地指纹状态，可以先交换小摘要，只对不一致区域继续下钻。差异条目很少时，还可以用 IBLT 直接恢复差集。
这些结构优化的是对账和差异定位。源端没有日志、版本或预存摘要时，首次生成全量状态仍需读取 $N$ 条记录。任何摘要结构都无法从未读取的数据中推断变化。
一、对账对象先固定
对账不能直接对任意行对象求 Hash。双方先约定：
datasetId
schemaId
canonicalizationVersion
identityKeyEncoding
rowFingerprintAlgorithm
partitionAlgorithmVersion
snapshotEpoch 或 comparisonBoundary每条记录映射为集合元素：
$$ x=encode(IdentityKey, RowFingerprint) $$
如果只比较身份键，只能发现新增和删除，无法发现内容更新。把身份和内容指纹共同编码后，同一键内容变化会表现为删除旧元素并新增新元素。结果解码后再按身份键合并成 UPDATE。
对账边界也要一致。节点 A 对应 10:00 的状态，节点 B 已处理到 10:05，摘要不同并不代表数据损坏。双方应冻结一个可比较 Epoch，或记录各分区的日志位置和 Watermark，在共同边界上生成摘要。
二、单个 Hash 无法解释差异
把所有元素排序后计算一个 SHA-256，可以判断“集合大概率相同”，但摘要不一致时无法定位哪条记录有问题。重新传输全量集合会失去摘要的工程价值。
只使用 XOR 也不够。定义：
$$ X(S)=\bigoplus_{x\in S}h(x) $$
XOR 可交换、可结合，相同元素能抵消，适合合并分片。不过它丢失了计数信息，重复元素会相互抵消，多组不同输入也可能得到相同结果。对账摘要可组合多个统计量：
$$ D(S)=\left( |S|, \bigoplus_{x\in S}h_1(x), \sum_{x\in S}h_2(x)\bmod p, \sum_{x\in S}h_3(x)^2\bmod p \right) $$
其中 $p$ 为足够大的素数，三个 Hash 使用独立种子或域分离标签。计数发现元素数量差异，XOR 和两个有限域矩降低不同集合产生同摘要的概率。
摘要支持分片合并。若 $A\cap B=\varnothing$，则：
$$ |A\cup B|=|A|+|B| $$
$$ X(A\cup B)=X(A)\oplus X(B) $$
$$ M_j(A\cup B)=M_j(A)+M_j(B)\pmod p $$
这种可合并性允许 Worker 分别生成局部摘要，再由控制面合并，无需集中传输全部元素。摘要相同仍是概率证据；高风险场景可对命中的桶再执行排序强摘要或逐条核对。
三、桶摘要减少无效下钻
Hash Wheel 已把数据分成 $M$ 个稳定桶。每个桶提交 Generation 时同时生成：
bucketId
generation
rowCount
digestTuple
strongHash
schemaId
completedAt两个节点先交换 $M$ 个固定大小摘要。1024 个桶、每个摘要 128 字节时，元数据约 128KB。只有摘要不同的桶需要进一步比较。若变化集中在少数桶，通信量可大幅下降。
桶摘要必须在完整 Generation 提交后发布。扫描中的临时摘要不能参与对账，否则“尚未看到”会被误解释成删除。摘要记录应绑定分桶算法和 Schema 版本，版本不同直接进入迁移流程。
四、Merkle Radix Tree 定位差异范围
Merkle Tree 的叶子保存有序键范围摘要，父节点摘要由子节点摘要组合得到。二叉树易于说明，但身份键天然是字节串，用 Radix 前缀构造多叉树更适合分区。
设使用十六进制前缀：
root
├── 0x0*
├── 0x1*
...
└── 0xF*第一层 16 个节点，第二层 256 个节点，第三层 4096 个节点。每个叶子对应一段稳定身份键前缀，保存记录数量和强摘要。父节点可 Hash 规范化后的子节点列表：
$$ H(parent)=H( prefix\parallel count\parallel H(child_0)\parallel\cdots\parallel H(child_{15}) ) $$
两个节点先比较根。根一致时结束；根不同则比较子节点，只进入摘要不同的分支。若共有 $d$ 个稀疏差异，树平衡且摘要已维护，访问节点数量可近似为：
$$ O(d\log_r N) $$
其中 $r$ 是分支数。这个复杂度描述已维护树上的定位成本，不包含首次扫描、叶子构建和变更时更新路径的成本。
叶子粒度存在权衡。叶子过大，命中后仍需传输大量键；叶子过小，节点元数据和更新写放大增加。可以以每叶 1000 至 10000 条记录为起点，用真实变化分布测量“树节点读取量 + 叶子明细传输量”。
Sparse Merkle Tree 的适用条件
Sparse Merkle Tree 以固定长度键空间为路径，未出现的子树使用预计算空 Hash。它的优点是根摘要结构稳定，成员证明和不在场证明清晰；代价是路径深、更新需要修改整条路径，工程实现和存储开销较高。
内部对账只需要定位差异时，压缩 Radix Tree 通常更直接。需要跨组织提供可验证证明、键空间固定且安全模型明确时，可以评估 Sparse Merkle Tree。不要只因其名称成熟就引入，先确认是否真的需要证明协议。
五、Merkle 更新与并发边界
每条记录指纹变化后，需要更新对应叶子及祖先摘要。若每次行更新都同步重算路径，会增加写放大。微批系统可以在 Batch 提交后合并同一叶子的变化，每个叶子只重算一次，再自底向上去重更新祖先。
树节点要绑定 Generation 或日志位置。节点 A 的父摘要由 Generation 18 的左子树和 Generation 17 的右子树组成时，它不是同一边界的完整快照。可以为一次对账冻结 Epoch，或使用 Copy-on-Write 节点构建新根，根发布后再回收旧版本。
摘要更新失败不能阻塞已正确写入的业务数据，但应将对账状态标记为 STALE，禁止继续声称根摘要代表当前数据。后台从受影响叶子重建，连续失败时由 Cold 通道全量重算。
六、IBLT 的数据结构
Invertible Bloom Lookup Table 用固定数量的 Cell 保存集合的可逆摘要。每个元素通过 $k$ 个 Hash 映射到 $k$ 个 Cell。典型 Cell 包含：
count
keySum
valueSum
hashSumkeySum、valueSum 和 hashSum 使用 XOR 聚合；count 使用整数加减。插入元素 $(key,value)$ 时，对每个 Cell 执行：
$$ count \leftarrow count+1 $$
$$ keySum \leftarrow keySum\oplus key $$
$$ valueSum \leftarrow valueSum\oplus value $$
$$ hashSum \leftarrow hashSum\oplus g(key,value) $$
删除或集合相减时执行相同 XOR，并让 count 减 1。节点 A 和 B 使用相同参数构造 IBLT，逐 Cell 相减后，公共元素在计数和 XOR 中抵消，剩余结构编码对称差：
$$ A\triangle B=(A\setminus B)\cup(B\setminus A) $$
count=1 且 hashSum=g(keySum,valueSum) 的 Cell 表示可验证的单个正元素；count=-1 表示负元素。解码器取出该元素，再从它映射到的所有 Cell 中剥离贡献，循环处理新产生的纯 Cell。
七、IBLT 为什么会解码失败
IBLT 是概率结构。Cell 数量 $m$、Hash 个数 $k$ 和实际差异数 $d$ 决定剥离图能否清空。若 $m$ 相对 $d$ 太小，剩余超图形成无法剥离的 2-core，解码停止。Hash 冲突和参数不一致也会失败。
工程上不能把容量写成一个永远正确的常数。可以根据近期对账差异估计 $\hat d$，按安全系数分配：
$$ m=c\times\hat d $$
c 的选择需要结合实现参数做模拟和压测。解码失败时扩大 IBLT 重试一次，仍失败则回退到 Merkle 叶子明细或排序集合比较。失败是协议分支，不应被当成数据丢失。
在容量合适且差异稀疏时，IBLT 传输和期望解码成本接近：
$$ O(d) $$
如果差异接近全量，IBLT 失去优势。此时交换大表的 IBLT 还可能比压缩后的排序键集合更贵。先用桶摘要或采样估计差异比例，再选择协议。
更新如何表示
IBLT 元素包含 (IdentityKey, RowFingerprint)。同一身份键内容从 $f_0$ 变为 $f_1$ 后，差集会出现：
仅 A 有：(key, f0)
仅 B 有：(key, f1)解码层按 key 聚合，得到 UPDATE。只在一侧出现身份键则为 INSERT 或 DELETE，方向取决于权威源。若两侧都可能独立写入，还需要冲突解决规则，集合对账结构本身不判断哪个值正确。
八、集合特征多项式的关系
把集合 $S={x_1,\ldots,x_n}$ 表示为有限域上的特征多项式：
$$ P_S(z)=\prod_{x\in S}(z-x) $$
两个集合的大量公共因子可以约去，剩余因子对应差异元素。若已知差异上界 $d$，在若干采样点交换多项式值，可以恢复低次数的差异多项式。该思路解释了“通信量随差异规模增长”的数学来源。
实际实现要处理有限域选取、元素编码、重根、插值和因式分解，复杂度和调试成本高于 IBLT。除非已有成熟库和严格协议需求，工程落地可先使用桶摘要、Merkle 和排序明细；特征多项式适合作为研究或特定带宽约束场景的后续选项。
九、分层选择对账协议
对账可以按成本逐层升级：
| 层级 | 交换内容 | 适用情况 | 失败后的动作 |
|---|---|---|---|
| 数据集根摘要 | 一个固定摘要 | 快速确认整体一致 | 比较一级前缀 |
| 桶摘要 | 数百到数千个摘要 | 差异只在少数桶 | 进入不一致桶 |
| Merkle 节点 | 不一致路径 | 差异分散但稀疏 | 定位叶子范围 |
| IBLT | 与估计差异量相关 | 差异很小且参数一致 | 扩容或回退明细 |
| 排序明细 | 身份键和指纹 | 差异大或概率结构失败 | 精确 Merge Diff |
排序明细是确定性兜底。双方按身份键排序后使用双指针合并，时间复杂度为 $O(n_A+n_B)$，若状态本来就按键有序，额外排序成本可以省去。高级结构必须保留这条回退路径，否则概率解码失败会让对账任务停在无法处理的状态。
十、验证算法和实现
单元测试覆盖摘要合并的交换律与结合律、重复元素策略、空集合、单元素差异、更新映射和域溢出。属性测试随机生成集合 A、B，验证 IBLT 解码成功时恢复的差集等于精确集合差；容量不足时必须明确返回失败，不能输出不完整结果。
性能测试按差异比例分层：0、$10^{-6}$、$10^{-4}$、1%、10% 和 100%。记录摘要构建时间、传输字节、访问的 Merkle 节点、IBLT 成功率、解码时间和回退成本。只测“两个集合几乎相同”的理想情况，会隐藏容量估计错误和大差异退化。
还要注入版本不一致：不同 Canonicalization、不同 Hash Seed、不同桶数、不同 Snapshot Epoch。协议应在交换头部时拒绝对账，不要等到所有摘要都不一致后再猜原因。
桶摘要、Merkle 和 IBLT 构成一条从固定小元数据到精确明细的升级路径。它们提供概率加速，正确性仍由版本化输入、强校验、明确失败和确定性回退共同保证。