布隆过滤器的原理、误判率计算与 Java 实现

布隆过滤器用极少内存回答：“这个元素一定不存在，还是可能存在？”在过滤器未删除位、未损坏且写入同步可靠的前提下，它不会漏掉已经成功加入的元素，却允许一定概率把不存在元素判断为可能存在。工程中的“数据库已写入但过滤器尚未更新”仍会造成业务层面的假阴性，不能把数学性质误当作端到端一致性保证。这个不对称特性很适合挡住缓存穿透，但前提是理解容量、误判率和数据同步。

1. 工作原理

准备一个长度为 m 的位数组，初始全为 0。加入元素时使用 k 个哈希函数得到 k 个位置，并将它们置 1。查询时检查这些位置：

• 任一位置为 0：元素一定未加入；
• 全部为 1：元素可能加入，也可能是其他元素共同造成的碰撞。

item ─hash1→ 12 ┐
     ─hash2→ 57 ├─ 将位数组对应位置设为 1
     ─hash3→ 83 ┘

普通布隆过滤器不能安全删除元素，因为某个位可能被多个元素共享。直接清零会让其他已加入元素出现假阴性。需要删除时可用计数布隆过滤器，但内存和溢出处理更复杂。

2. 误判率如何估算

加入 n 个元素、位数组大小为 m、哈希函数数为 k 时，常用近似误判率：

p ≈ (1 - e^(-kn/m))^k

给定 n 和目标误判率 p，近似最优参数：

m ≈ -n × ln(p) / (ln 2)^2
k ≈ (m/n) × ln 2

例如预计 1000 万元素、目标误判率 1%，大约需要 9585 万 bit，即约 11.4 MiB，最优 k 约为 7。还要加实现元数据、复制和扩容余量。

容量估小后继续加入，误判率会快速恶化。因此必须监控实际插入量，不能只在首次上线时计算一次。

3. 使用 Guava

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8),
    10_000_000L,
    0.01
);

filter.put("product:1001");
boolean maybeExists = filter.mightContain("product:1001");

Guava 过滤器通常位于单个进程内。多实例服务要么各自构建并同步，要么从持久化快照加载；更新传播延迟可能造成“新数据被判断不存在”，破坏无假阴性的前提。

4. RedisBloom 的价值

RedisBloom 模块提供集中式布隆过滤器，典型命令：

BF.RESERVE products 0.01 10000000
BF.ADD products product:1001
BF.EXISTS products product:1001

集中存储便于多实例共享和原子更新，也带来网络访问、Redis 可用性和模块部署要求。应在创建时显式指定容量和错误率，理解自动扩展会增加多个子过滤器并影响查询成本。

5. 与数据库写入如何同步

错误顺序是先加入过滤器，再写数据库：数据库写失败后，过滤器产生假阳性，这通常只会多查一次库，尚可接受。更危险的是数据库写成功、过滤器未更新，查询会得到假阴性并直接拒绝真实数据。

可选方案：

• 数据库提交后同步更新，失败进入可靠重试；
• Outbox/CDC 异步更新；
• 新建数据短时间绕过过滤器或检查补偿集合；
• 定期由权威数据库重建过滤器并原子切换版本。

删除数据库记录无需从普通过滤器删除；残留位只增加少量假阳性。若 ID 会复用，则需重新评估语义。

6. 双重检查仍然必要

Product find(long id) {
    if (!bloom.mightContain(id)) return null;
    Product p = cache.get(id);
    if (p != null) return p;
    return repository.findById(id); // 最终以数据库为准
}

“可能存在”绝不能当作授权或业务真实性判断。布隆过滤器只减少明显无效查询，数据库或权威服务才给最终答案。

7. 什么时候不该用

• 数据量很小，空值缓存已足够；
• 必须列举过滤器中的所有元素；
• 需要精确删除且无法接受计数结构成本；
• 任何假阳性都不可接受；
• 数据频繁变化但没有可靠同步链路。

替代结构包括精确 HashSet、Cuckoo Filter、计数布隆过滤器或数据库索引，选择取决于删除、空间和错误率要求。

8. 检查清单

• 是否根据预计 n 和目标 p 计算 m、k？
• 是否为增长留出容量并监控插入量？
• 数据库提交后是否可靠更新过滤器？
• 重建时是否使用新版本并原子切换？
• 是否把“可能存在”误当成“确定存在”？
• 本地过滤器在多实例间如何同步？

布隆过滤器不是缓存，也不存业务值。它是一道概率型前置门：用可控假阳性换取空间效率，并把大量确定不存在的请求挡在数据库之前。