算法与数据结构 / 概率型 sketch · 用固定内存换有界误差 / Redis 的 probabilistic 命令与选型 待审核 7 / 7
PF · BF · CF · CMS · TOPK · TDIGEST

Redis 的 probabilistic 命令与选型

前六页的结构在 Redis 里都有对应的命令。HyperLogLog 一直在核心里（PFADD 一族），其余五个来自 RedisBloom 模块，自 Redis 8 起随 Redis 一并发行（核对于 2026-08）。

1 · 命令与结构的对应

要回答的问题 结构 命令
有多少个不同的 key HyperLogLog PFADD / PFCOUNT / PFMERGE
xx 在不在（不需删除） Bloom filter BF.RESERVE / BF.ADD / BF.EXISTS
xx 在不在（需要删除） cuckoo filter CF.RESERVE / CF.ADD / CF.EXISTS / CF.DEL
这个 key 出现几次 Count-Min Sketch CMS.INITBYPROB / CMS.INCRBY / CMS.QUERY / CMS.MERGE
出现最多的那几个 HeavyKeeper TOPK.RESERVE / TOPK.ADD / TOPK.LIST
p50 / p99 是多少 t-digest TDIGEST.CREATE / TDIGEST.ADD / TDIGEST.QUANTILE / TDIGEST.MERGE
图 1-1 · 从「要回答哪一问」落到具体命令，逐项列出创建方式、内存、合并能力与需要留意之处。可切换问题查看对应的一组命令。

三个 MERGE 命令的存在与缺席都不是偶然。PFMERGE、CMS.MERGE、TDIGEST.MERGE 对应的三个结构状态可加；CF.* 与 TOPK.* 没有合并命令，因为这两个结构本身合不了（见 固定内存与有界误差 §3）。

2 · 参数与内存

各命令暴露的参数粒度差别很大。

PFADD 一族不给任何精度参数。pp 在 hyperloglog.c 里写死为 14，稠密编码固定 12288 字节，标准误 0.81%。要更高精度只能换结构。可调的只有 hll-sparse-max-bytes（默认 3000），它决定何时从稀疏转稠密：实测 p=14p = 14 时基数 1676 起越过这个阈值（见 HyperLogLog §6）。

CMS.INITBYPROB key error probability 直接吃 (ε,δ)(\varepsilon, \delta)，内部按 w=⌈e/ε⌉w = \lceil e/\varepsilon \rceil、d=⌈ln⁡(1/δ)⌉d = \lceil \ln(1/\delta) \rceil 算维度；另有 CMS.INITBYDIM 直接给 ww 与 dd。两个入口对应本系列 core/cms.ts 里的 cmsWidthFor 与 cmsDepthFor。

TDIGEST.CREATE key COMPRESSION c 的 COMPRESSION 就是 delta\text{delta}，默认 100，即约 50 个 centroid、不到 1KB。要报 p99.99 得把它提上去（t-digest §4 的警示给了实测数）。

CF.RESERVE 除容量外还给 BUCKETSIZE 与 MAXITERATIONS，分别对应本系列引擎的 bb 与踢出预算。默认 BUCKETSIZE 为 2，而本系列取 4——实测 b=2b = 2 的最高负载 0.708，b=4b = 4 是 0.963，装同样多的元素时前者要多分配三分之一的位置。

3 · RedisBloom 的实现分歧

TOPK.* 最初被当作 Space-Saving 的直接实现来对齐，读 RedisBloom 的文档后发现不是。它实现的是 HeavyKeeper：一个 width×depth\text{width} \times \text{depth} 的计数矩阵加一个 kk 项的堆，新元素命中已被占用的格子时，按 decay−c\text{decay}^{-c} 的概率把那一格的计数减一，而不是无条件加。

后果是它的误差形式与 Space-Saving 不同。Space-Saving 给的是区间 [count−error,count][\text{count} - \text{error}, \text{count}]，真值必在其中，且「真实频次超过 N/kN/k 一定还在槽内」可以证明。HeavyKeeper 靠衰减把低频项挤出格子，误差是概率性的，既可能高估也可能低估。TOPK.RESERVE 的第四个参数 decay 直接调这个衰减速率，本系列的引擎里没有对应旋钮。

另一处是 Bloom filter 的容量。BF.RESERVE 要求预先给出 capacity，装满之后 RedisBloom 不报错而是追加一层新的 sub-filter，查询要逐层看。为让总误判率仍收敛到给定值，每一层的误判率按几何级数递减。这条自动扩容在本系列的引擎里同样没有——它是工程行为而非算法性质，但它决定了「误判率 1%」这句承诺在超容量之后还成立多少。

警示 · CF.DEL 的前置条件容易忽略。它只能对确实加过的元素调用；对一个从未加过、但恰好指纹冲突的 key 调用，它会清掉别人的指纹，制造一个真的假阴性。CF.EXISTS 返回真不足以作为调用 CF.DEL 的依据，那个真本身就可能是假阳性。要安全删除，得在别处保留一份「确实加过什么」的记录。

4 · 选型判据的顺序

判据的顺序值得写清楚，因为最常被先问的那个（精度）实际排在最后。

第一问是要回答哪一问。§1 那张表六行答六个不同的问题，选错了行，误差调到多小都没用。基数与频次最常被混淆：「有多少个不同的访客」用 PFADD，「这个访客来了几次」用 CMS.INCRBY，两者不能互相顶替。

第二问是要不要跨实例合并。要合并就只剩 PF、CMS、TDIGEST 三族。这一问排在精度之前，因为它是结构性的：精度可以加内存换，合并能力换不来。

第三问才是精度。到这一步选择空间已经很小：PFADD 连参数都不给；CMS 给 (ε,δ)(\varepsilon, \delta)；TDIGEST 给一个 COMPRESSION；BF 与 CF 给目标误判率。

5 · 参考文献

  1. Redis. Probabilistic data types. redis.io/docs/latest/develop/data-types/probabilistic/.
  2. RedisBloom. RedisBloom — Probabilistic Datatypes Module for Redis. github.com/RedisBloom/RedisBloom.
  3. Gong, J., Yang, T., Zhang, H., Li, H., Uhlig, S., Chen, S., Uden, L., & Li, X. (2018). HeavyKeeper: an accurate algorithm for finding top-k elephant flows. USENIX ATC 2018, 909–921.
  4. Almeida, P. S., Baquero, C., Preguiça, N., & Hutchison, D. (2007). Scalable Bloom filters. Information Processing Letters, 101(6), 255–261.
  5. Sanfilippo, S. (2014). Redis new data structure: the HyperLogLog. antirez.com.