sketch 家族 · 五个对照维度

固定内存与有界误差

「这个月有多少个不同的访客」「这条 URL 被请求了几次」「接口延迟的 p99 是多少」——三个问题的精确答法都要把数据留住：第一个要一张 Set，第二个要一张 Map，第三个要把全部样本存下来排序。留住的量与数据量同阶，日志规模一上来就撑不住。

概率型 sketch 换一条路：放弃精确答案，把状态钉成一个由参数决定的常数，再给出一个可以算出来的误差界。Bloom filter 是这一族里最早也最简单的一个，它只答「在不在」；本系列往后走的五个结构分别去答上面那三个问题，以及「谁出现得最多」。

1 · 精确统计的内存账

一份 100 万条事件的日志，key 服从 zipf 分布，出现过 87755 个不同的 key，平均 6.1 个字符。精确侧的账是这样的：一个 Set 要为每个 key 留一份字符串本体（V8 的一字节字符串加约 16 字节对象头）与一个表项（约 16 字节），合计约 3.3 MB。这个数是按 V8 的对象布局估的，不是量出来的堆快照；真实占用只会更高，Set 内部是开放寻址的哈希表，负载因子留了余量。

同一批数据，HyperLogLog 用 12288 字节报出 88387，相对误差 0.72%。两者相差约 270 倍。

图 1-1 · 内存随事件条数在对数坐标上的走势。精确 Set 与 cuckoo filter 是斜线，HLL、Count-Min 与 t-digest 是水平线。可调平均 key 字节与重复次数观察两组曲线的间距。

图里有一条线值得单独看：cuckoo filter 与精确 Set 平行，只是低了一个常数倍。成员判定类结构必须为每个元素留一段痕迹，斜率降不到零。所谓「内存与数据量无关」，说的是基数、频次与分位数这三类估计，不包括成员判定。

2 · 一族结构共享的形态

五个结构的内部长得毫不相似，但外部形态一致，都是三件东西：

一段固定大小的状态。大小由参数决定，一次分配到位，此后不再增长。
一个更新函数。吃一个元素，改状态；状态的每一位都只往一个方向走（HyperLogLog 的桶只增不减，Count-Min 的格子只加不减）。
一个估计函数。把状态折算成答案，不需要回看任何原始数据。

定义 2.1（sketch） 一个 sketch 是三元组 $(S, u, f)$ ：状态空间 $S$ 的大小与输入规模无关；更新函数 $u : S \times X \to S$ 只依赖当前状态与新元素；估计函数 $f : S \to \mathbb{R}$ 给出答案。若另有 $\oplus : S \times S \to S$ 使 $f(s_A \oplus s_B)$ 等于对 $A \cup B$ 直接建一份状态再估计的结果，则这个 sketch 是 mergeable 的。

更新函数的单调性是这一族最有用的技术性质。它意味着状态里不存在「需要撤销的历史」，而这正好解释了为什么删除普遍做不到：把桶从 5 降回 4 需要知道「那个 5 是谁写的」，而状态里没留这个信息。

可合并性则来自另一个方向：状态的每一位要能独立地「取并」。HyperLogLog 的桶存的是「落进本桶的最长前导零串」，两份状态逐桶取 max 恰好就是并集的答案；Count-Min 的格子存的是「落在本格的全部 key 的频次之和」，逐格相加同理。这两处的合并结果与直接建的那一份逐位相等，不是近似相等，可以逐位断言（见 core/hll.test.ts 与 core/cms.test.ts）。

3 · 五个对照维度

选型判据落在五列上：估计什么、误差是什么形式、内存多大、能不能合并、能不能删除。

图 3-1 · 六个结构在五个维度上的对照。可勾选需求筛掉不满足的行，例如同时勾「要能合并」与「要能删除」时无一行留下。

误差那一列刻意没有折算成一个数。写这一页时曾想给每个结构标一个统一的「内存换误差」分数，做不到：HyperLogLog 的误差是相对误差，Count-Min 的是绝对高估量，t-digest 的是 rank 误差，三者连单位都不同。硬折算只会造出一个看着可比、实则无意义的数。

误差形式本身分两条轴。第一条是相对还是绝对：HyperLogLog 报 $\pm 0.81\%$ ，与基数多大无关；Count-Min 报 $\pm \varepsilon N$ ，与被查 key 的频次无关，于是低频 key 的相对误差可以大得没有意义。第二条是单边还是双边：Count-Min 只会高估、永不低估，这条性质可以逐元素断言，比一个概率界好用得多。

注 · 「标准误」不是误差上限。 $1.04/\sqrt{m}$ 是相对误差这个随机量的标准差，单次估计落在 $\pm 1.04/\sqrt{m}$ 内的概率约 68%。实测 24 组独立数据、真实基数 40 万时，均方相对误差 0.788%，最大 1.647%——把区间说成「误差不超过 0.81%」是错的。

4 · 同一批数据上的实测

把 §1 那批数据同时喂给五个结构，各答自己那一问，真值由精确 Set / Map / 排序数组给出：

结构	参数	内存	答案	真值	误差
HyperLogLog	$p = 14$	12288 B	88387	87755	$+0.72\%$
Count-Min Sketch	$w = 2719$ ， $d = 5$	54380 B	逐 key 频次	逐 key 频次	平均高估 69.3，最大 405
Space-Saving	$k = 200$	4800 B	top-10	top-10	全对，零高估
t-digest	$\text{delta} = 100$	928 B	p50 = 120.29	120.11	$+0.15\%$
t-digest	同上	同上	p99 = 990.50	973.38	$+1.76\%$
cuckoo filter	$b = 4$ ， $f = 12$	196608 B	成员判定	成员判定	无假阴性，假阳率 0.18%

这张表里有两处值得停一下。

Space-Saving 用 4800 字节把 top-10 报得一个不差、零高估，而 Count-Min 用 54380 字节在同一批数据上对最热的 key 仍高估了几十。两者不矛盾：Space-Saving 只回答「它自己留下的那 200 个 key」，问它别的 key 一律没有答案；Count-Min 对任意 key 都给答案，代价是任意 key 都带误差。内存少一个数量级换来的是答题范围小一个数量级。

t-digest 的 p99 值误差（1.76%）比 p50（0.15%）大了一个量级。这与「t-digest 在两端更准」的常见说法方向相反——它准的是 rank，不是值，两者在长尾分布上会背道而驰。这一处在分位数与 t-digest §4 有逐 $q$ 的实测。

5 · 参考文献

Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science Proceedings, AH, 137–156.
Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58–75.
Metwally, A., Agrawal, D., & El Abbadi, A. (2005). Efficient computation of frequent and top-k elements in data streams. ICDT 2005, 398–412.
Dunning, T., & Ertl, O. (2019). Computing extremely accurate quantiles using t-digests. arXiv:1902.04023.
Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). Cuckoo filter: practically better than Bloom. CoNEXT 2014, 75–88.
Cormode, G., & Yi, K. (2020). Small Summaries for Big Data. Cambridge University Press.