先说说我们踩的这个坑
上周三凌晨两点，我把去重服务从 Redis SET 换成布隆过滤器，内存从 12GB 掉到 380MB。第二天下午业务就找上门了——用户投诉投放太频繁，运营想手动把某台设备从当天的去重名单里「捞」出来重投一次。布隆过滤器没有删除操作。我们只能把当天的 key 整个删掉重建，重建那 3 分钟里，2000 万条记录全丢了，等于当天所有用户都能被重复触达一次。
这事之后我把这几个方案重新捋了一遍，顺手把压测数据也翻出来看了。
背景交代一下：我们做投放系统的频次控制，判断「这台设备今天有没有被这个计划投过」。原始实现很朴素，Redis SET，key 是 freq:{plan_id}:{date}，value 是设备 ID 的 16 位十六进制字符串（安卓端取 OAID 的哈希）。单日峰值 1.2 亿个 ID，分散在大约 8000 个活跃计划上。12GB 内存，运维每周发一次告警。
内存到底怎么算（你可能就是搜这个来的）
布隆过滤器的位数组大小：
m = -n · ln(p) / (ln 2)²n 是预期元素数，p 是你能接受的误判率。哈希函数个数：
k = (m / n) · ln 2代入我们的数字，n = 1.2 × 10⁸，p = 0.01：
- m = 1.2e8 × 4.60517 / 0.480453 ≈ 1.15 × 10⁹ bit ≈ 137 MiB
- k = 9.585 × 0.693147 ≈ 6.64，取 7
所以理论值是 137 MiB，每个元素摊到 9.6 bit，也就是 1.2 字节。
但实际部署我们用了 380MB，接近理论值的 2.8 倍。为什么？因为我们不是一个大过滤器，是 8000 个小过滤器，每个计划一个。每个过滤器的 capacity 得按该计划自己的峰值单独设，没法共享。8000 个 key 各自按峰值预留之后，空间利用率大概只有 35%。这是个很容易被忽略的点：过滤器数量一多，容量预留的浪费会吃掉大部分收益。如果你的场景是全局一个 key（比如全站 UV），可以跳过这段。
反过来看 Redis SET 为什么那么贵。1.2 亿个 16 字符的字符串，每个元素的开销大概是：
- sds 字符串本体 16 字节 + 头部（sdshdr8）3 字节，jemalloc 对齐到 24 或 32 字节
- robj 对象头 16 字节
- dictEntry，三个指针，24 字节
- 哈希表桶位的摊销，负载因子 1 的话每个元素 8 字节左右
加起来 70 到 100 字节一个元素，1.2 亿 × 90 ≈ 10.8GB，跟实测的 12GB 对得上。
顺便说一句，很多人以为 Redis SET 存整数会自动走 intset 省内存。确实会，但 set-max-intset-entries 默认只有 512，超过就转 dict 了。512 这个阈值在生产环境里几乎没有意义，别指望它。
坑一：误判率不是线性的，超了容量会崩
我们第一版把 capacity 设成 1 亿，觉得留了 20% 余量够用。结果大促前那波流量，单个计划的实际写入冲到了 2 亿。
算一下这时候的误判率。m/n 从 9.585 掉到 4.79，k 还是 7：
p = (1 - e^(-kn/m))^k = (1 - e^(-7/4.79))^7 ≈ 0.15715.7%，不是 1%。
也就是说每 6 台设备里就有 1 台被误判成「已经投过」，直接被跳过。那天曝光量掉了 9%，我们查了三个小时才定位到。
教训是：capacity 至少按峰值的 1.5 倍设，RedisBloom 里就是 BF.RESERVE key 0.01 150000000 的第三个参数。写小了后面补不回来——布隆过滤器的位数组长度在创建时就定死了，扩容只能新建。
坑二：扩容是乘性的，而且查询会变慢
RedisBloom 有个 SCALING 参数，默认是 2。容量满了它会新加一层同大小的过滤器，查询时每一层都要查一遍。
误判率不是取最大值，是乘性叠加：
p_total = 1 - (1-p₁)(1-p₂)(1-p₃)...三层各 1% 的话，总误判率是 2.97%。听着还行，但如果 SCALING 设成 1（每次加固定大小），层数会失控，五层之后误判率就接近 5% 了。
延迟也是问题。我们压测的结果：单层 BF.EXISTS 大约 0.06ms，三层之后 P99 会抖到 0.3ms 以上。原因是 Redis 是单线程的，一次查询要算 7 个 murmur 哈希，每个哈希对应一次内存随机访问，基本上都是 cache miss。三层就是 21 次，全在单线程里排队。
顺带一提，如果你在做 7 天滑动窗口去重，保留 7 个日 key 分别查的话，这个开销要乘以 7。我们压测里 P99 从 0.06ms 抖到了 0.4ms 以上，晚高峰还出现过尖刺。
坑三：不能删除这件事，比你以为的贵
运营要撤销，这是第一步。后面还有退款回滚、风控误杀解封、AB 实验对照组重建，都需要「从这个集合里去掉一个元素」。布隆过滤器做不到。
我们的第一版是「删 key + 重建」，代价是 3 到 5 分钟空窗期，期间所有流量都不去重。后来改成双写 + 影子读：新 key 先写，查询时新老两个都查，等新 key 追平再切。这套切换逻辑加上监控和回滚开关，代码量比去重本身还多。
支持删除的选择是 Cuckoo Filter。但它也不是免费的：
- 空间上，95% 负载因子下每元素约 12 bit，比布隆的 9.6 bit 还大
- 插入可能失败。元素被踢出后要重新找位置，踢出链太长这次插入就直接失败
- 我们压测里确实出现过踢出链超过 500 的情况（项目里设的上限），插入失败率 0.03%
0.03% 看着小，但在 1.2 亿的量级上就是 3.6 万次插入失败。对频控来说，失败意味着这台设备今天可能被重复触达，得降级到 Redis 兜底。
换个思路：ID 是有界整数的话，别用布隆
这是这次迁移我最大的收获，也是我觉得「布隆过滤器省内存」这句话被过度简化了的地方。
Roaring Bitmap 的结构是：把 32 位整数切成高 16 位和低 16 位，高 16 位决定落在哪个 chunk，每个 chunk 是一个容器。容器有两种形态：
- Array Container：元素数 ≤ 4096 时，用有序的 uint16 数组，每个元素 2 字节
- Bitmap Container：元素数 > 4096 时，用固定 8KB 的位图
4096 × 2 = 8192 字节，正好等于 8KB。这个阈值不用背，算出来的。
现在假设我们的 ID 是 0 到 1 亿之间的稠密整数：
- 1e8 / 65536 ≈ 1526 个 chunk
- 每个 chunk 都是满的 65536 个值，走 bitmap container，8KB
- 总共 1526 × 8192 ≈ 12.5 MB
12.5 MB。精确、可删、还能做交并差。 对比布隆的 137 MiB 加 1% 误判，差 11 倍。
但反过来，如果 ID 是稀疏的——1.2 亿个设备哈希散落在 2³² 的空间上：每个 chunk 平均只有 1.2e8 / 65536 ≈ 1830 个元素，小于 4096，走 array container，2 字节一个元素，总共 240MB。比布隆的 137MiB 还大。
而且如果你的 ID 本来就是 64 位（比如雪花 ID 或者 UUID 哈希），Roaring64 能用，但每个 64 位值要额外维护一份高 32 位的映射表，查询性能掉一截，内存优势也基本没了。
所以结论不是「Roaring 比布隆好」，而是——先看你的键的分布，再看选哪个。这句话听着像废话，但我见过太多人直接抄一篇博客就上布隆过滤器了。
一张表，我自己的选型依据
| 场景 | 推荐 | 理由 |
|---|---|---|
| ID 是 32 位内、区间稠密（订单号、自增 ID、广告位 ID） | Roaring Bitmap | 12.5MB/亿，精确可删可交并 |
| ID 稀疏、64 位、只增不改 | 布隆过滤器 | 1.2 字节/元素基本是天花板了 |
| 需要删除 + 数据量 5000 万以内 | Cuckoo Filter 或直接 Redis SET | 别过早优化 |
| 千万级以下 | Redis SET / intset | 省下来的内存不够填运维成本 |
| 只要算 UV 基数，允许 1% 误差 | HyperLogLog | 12KB 固定开销，但只能估基数 |
最后一行可能有人要杠，HyperLogLog 确实不能做存在性判断，它是估基数的。我列进来是因为经常有人把这两个混为一谈，然后写出来的代码在「无重复数据」的测试用例上跑得好好的，一上生产就崩。
收个尾
如果你的场景是日粒度去重，还有个更笨但更稳的做法：老老实实保留 7 个日 key，查询时做 7 次 OR。
布隆过滤器做不了滑动窗口——你没法从位数组里「减掉」昨天。只能保留多个 key 分别查。如果换成 Roaring Bitmap，7 个 bitmap 的 OR 可以在应用进程内存里做，不走网络往返。这时候 Roaring 的优势就不只是内存了，还有延迟。
所以我现在给团队的建议是：先去统计你的 ID 分布，画一张直方图，再决定用哪个。别看别人用什么。
统计脚本其实二十行代码就能写完，比踩坑之后回滚便宜太多了。