可合并摘要 | Codeboy's Blog

形式陈述

接口性质

对数据流模型中的流片段 $A$ ，摘要算法产生有限状态 $S(A)$ 。若存在只读取两个状态的操作 merge，使

\operatorname{merge}(S(A),S(B)) \approx S(A\circ B),

就称摘要可合并。符号 $\approx$ 不是装饰：它必须说明状态完全相同、输出分布相同，还是两边都满足同一 $(\varepsilon,\delta)$ 误差保证。

接口至少要固定 summarize、merge 与 query。merge 不得重新扫描 $A,B$ 的原始项；否则它只是集中重算。若分布式归约树会任意改变括号次序，合并还应在语义上结合；无序分片要进一步说明是否交换。

严格与近似可合并

严格可合并要求兼容状态满足

\operatorname{merge}(S(A),S(B))=S(A\circ B)

或至少具有与集中运行完全相同的分布。计数器是最简单的例子：状态为整数，merge 是加法，形成一个幺半群。

近似可合并允许状态不同，但 query 的误差仍在声明范围内。此时要证明两件事：状态运算没有引入未计入的偏差，归约树的层数也不会让误差或失败概率无限累加。一个在每次 merge 都重新做有损压缩的摘要，可能需要按树深调整精度。

线性 sketch在共享线性映射 $L$ 时天然满足

L(f_A+f_B)=L(f_A)+L(f_B).

这给出严格的状态合并式，但 query 从 sketch 恢复统计量仍可能是随机近似；“线性”解决组合，不自动消除估计误差。

直觉

摘要能被序列化并不表示它能被统计上正确地拼接。可合并性要求状态运算与“先合并原始数据再摘要”相容，并把随机种子、顺序、重复和误差合成都纳入契约；归约树上的任意括号变化才不会悄悄改变答案分布。

两个 HyperLogLog 分片摘要逐寄存器取最大值得到并集摘要 — 可合并摘要的逐坐标合并

例子与边界

HyperLogLog 的寄存器合并

HyperLogLog 用共享哈希函数把元素分配到寄存器，并在寄存器中记录观察到的最大前导零等级。两个分片状态逐寄存器取最大值：

R_j^{A\cup B}=\max(R_j^A,R_j^B).

这与在并集流上逐元素更新完全相同，因为 max 既结合、交换又幂等。

例如四个寄存器的分片状态为

R^A=(3,1,0,2),\qquad R^B=(1,4,2,2).

合并得到 $(3,4,2,2)$ 。同一用户若同时出现在两片，只会重复提交相同的寄存器与等级，max 不会把它数两次；最后再由统一的基数估计公式读取寄存器。

该例成立的前提是寄存器数、哈希种子、位切分方式和估计器版本一致。若两个分片用独立哈希种子，寄存器下标不再表示同一随机试验，逐位 max 没有上述并集语义。

随机性是状态契约的一部分

摘要的 schema 不只包含字节布局，还包含随机性约定。共享随机投影、哈希族和采样优先级通常要由作业级 seed 派生，使任意节点能验证兼容性。merge 遇到不兼容 seed 应拒绝，而不是静默组合。

有些算法允许独立随机副本并通过平均降低方差，但那是“合并估计值”的另一项定理。它不能代替对原摘要状态的合并证明。失败概率若对每个分片分别为 $\delta$ ，直接用并集界可能得到 $p\delta$ ；共享 sketch 往往能让最终状态对应一次全局试验。

Reservoir sample 的反例

分片 $A$ 含 1000 项，分片 $B$ 含 10 项，各自保留一个均匀 reservoir 样本。若把两个样本放在一起再等概率选一个，最终来自 $B$ 的概率为 $1/2$ ；全局均匀样本应来自 $B$ 的概率却是

\frac{10}{1010}.

内存表示很容易拼接，不代表统计分布正确。

对样本量 1，可按分片长度加权，分别以 $1000/1010$ 与 $10/1010$ 选择。一般 $k$ 的连续优先级构造属于理想比较模型：给每个出现位置独立同分布的连续随机优先级，各片保留最小的 $k$ 项，合并时再取候选并集的前 $k$ 。局部被丢弃的位置已有至少 $k$ 个更小同片位置，因此不会进入全局前 $k$ ；连续性使并列概率为零。无限精度优先级不属于固定字长的有限状态；若改用有限哈希，必须额外处理碰撞及其分布误差，确定性打破并列不自动给出精确均匀性。

一个精确的有限状态方案使用两片独立运行的蓄水池样本。设片长为 $m_A,m_B$ ，各保留大小 $\min(k,m_A)$ 、 $\min(k,m_B)$ 的均匀位置子集。令 $s=\min(k,m_A+m_B)$ ，先抽取来自 A 的配额 $J$ ，其超几何分布为

\Pr(J=j)=\frac{\binom{m_A}{j}\binom{m_B}{s-j}}{\binom{m_A+m_B}{s}}, \qquad \max(0,s-m_B)\le j\le\min(s,m_A).

随后用新随机性从 A 的 reservoir 均匀抽 $j$ 项、从 B 的 reservoir 均匀抽 $s-j$ 项，输出其并集。所需配额都不超过各片保存量。

均匀样本再均匀取较小子集，仍是原片段的均匀子集。固定一个大小为 $s$ 、其中 $j$ 项来自 A 的目标位置集，其输出概率恰为

\frac{\binom{m_A}{j}\binom{m_B}{s-j}}{\binom{m_A+m_B}{s}} \frac1{\binom{m_A}{j}}\frac1{\binom{m_B}{s-j}} =\frac1{\binom{m_A+m_B}{s}}.

这个计算需要片段样本相互独立，且配额、子抽样使用相应独立新币。空片段、总长度小于 $k$ 及 $k=0$ 都由同一式子处理，约定 $\binom00=1$ 。

实现配额时可逐次从剩余 $a$ 个 A 位置和 $b$ 个 B 位置中均匀选一个颜色：抽 $[1,a+b]$ 中的整数，前 $a$ 个结果选 A，否则选 B，并递减相应计数，重复 $s$ 次。它只保存计数与有限样本，不必构造无限精度优先级。均匀整数可由拒绝采样精确生成，随机位消耗和运行时间按该实现另计；在独立分片上逐层合并时，刚才的联合分布证明可沿合并树归纳。

重复、顺序与误差合成

频率向量摘要通常把重复事件视为计数增加；集合摘要则需让同一键的重复不改变集合语义。若分片不是互斥时间段，而是有重放或副本，sum 型 sketch 会重复计数，max 型集合 sketch 可能仍正确。数据所有权条件应成为接口前置条件。

Bottom-k不同键摘要给这一重放区别一个可逐项核查的接口：局部前k候选先合并去重，再截为并集前k，用共同样本判断交集；complete位还须检测候选并集是否超容量。优先级抽样的加权总量版本则保留前k+1名以恢复阈值，本文实现只合并互斥记录ID，不能将同键的局部权重当成一条已聚合记录。

依赖顺序的摘要也可能只结合而不交换。对有限自动机，片段 $A$ 可以用其诱导的整个状态转移映射 $T_A:Q\to Q$ 摘要；串接 $A\circ B$ 对应 $T_B\circ T_A$ 。函数复合结合，通常不交换，所以合并时须保留分片次序。单个指定初态运行后的末状态则通常不足以组成这样的摘要：它只给出 $T_A$ 在一个输入上的值，无法确定 $B$ 从另一个状态继续时的结果。

推论与应用

与序列化和批处理的区别

能序列化状态只说明它可以传输，不能说明两个状态能正确组合。能把两个数组连接也只说明表示闭合，不能证明 query 无偏。可合并性是一项带统计保证的代数接口性质。

完整报告应列出状态大小、update 与 merge 时间、兼容性字段、误差类型、失败概率如何随归约树变化，以及重复数据假设。缺少任一项，调用者都无法判断它是否适合并行流处理。

参考资料

Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei and Ke Yi, Mergeable Summaries, ACM Transactions on Database Systems, 2013.
Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier, HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm, AOFA, 2007.
Graham Cormode and S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and Its Applications, Journal of Algorithms, 2005.

形式陈述 ​

接口性质 ​

严格与近似可合并 ​

HyperLogLog 的寄存器合并 ​

随机性是状态契约的一部分 ​

Reservoir sample 的反例 ​

重复、顺序与误差合成 ​

与序列化和批处理的区别 ​

反向链接