可合并摘要

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

HyperLogLog 的寄存器合并 ​

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

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

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

合并得到 $(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$ 的概率却是

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

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

重复、顺序与误差合成 ​

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

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

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

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

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