可合并摘要

接口性质 ​

对流片段 (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 是加法，形成一个幺半群公理库幺半群Monoid具有双侧单位元的半群。。

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

线性 sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。在共享线性映射 (L) 时天然满足 [ L(f_A+f_B)=L(f_A)+L(f_B). ] 这给出严格的状态合并式，但 query 从 sketch 恢复统计量仍可能是随机近似；“线性”解决组合，不自动消除估计误差。

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)，直接用 union bound 可能得到 (p\delta)；共享 sketch 往往能让最终状态对应一次全局试验。

Reservoir sample 的反例 ​

分片 (A) 含 1000 项，分片 (B) 含 10 项，各自保留一个均匀 reservoir 样本。若把两个样本放在一起再等概率选一个，最终来自 (B) 的概率为 (1/2)；全局均匀样本应来自 (B) 的概率却是 [ \frac{10}{1010}. ] 内存表示很容易拼接，不代表统计分布正确。

对样本量 1，可按分片长度加权，分别以 (1000/1010) 与 (10/1010) 选择。对一般 (k)，可给每个原始元素使用全局可比较的随机优先级并保留最优 (k) 项，或采用经证明的加权合并算法；简单并集后随意截断不够。

重复、顺序与误差合成 ​

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

顺序统计量还可能不交换。若摘要表示字符串哈希或有限自动机状态，(A\circ B) 与 (B\circ A) 不同；merge 可以结合，却必须保留分片顺序。把可结合误写成可任意乱序，是分布式实现中的实际错误。

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

能序列化状态只说明它可以传输，不能说明两个状态能正确组合。能把两个数组连接也只说明表示闭合，不能证明 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.