布隆过滤器：用误判换取空间效率

我最开始接触“布隆过滤器：用误判换取空间效率”时，先遇到的是这个问题：一个可能误判的结构到底有什么用，我很长时间都想不通；把它放到缓存穿透和海量去重里以后，这个取舍才变得具体。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。

布隆过滤器用一个位数组和多组哈希函数表示集合。插入元素时，把多个哈希位置设为 1；查询时，只要任一位置为 0，就能确定元素从未被加入。若所有位置都是 1，只能说它“可能存在”。

它从哪里来

Burton Howard Bloom 在 1970 年提出 Bloom Filter。它面对的是“元素太多，完整保存集合成本太高”的问题，于是用位数组和多个哈希函数换取极低空间，并明确接受一种可控结果：可能误报存在，但不会漏报不存在。

工作过程

布隆过滤器位数组写入、查询和假阳性形成图

图：任一哈希位为 0 代表一定不存在，全部为 1 只代表可能存在

不同元素可能共享位，因此全为 1 时不能反推出是哪一个元素设置的，这就是假阳性的来源。

一个教学版实现

public final class BloomFilter {
    private final java.util.BitSet bits;
    private final int bitSize;
    private final int hashCount;

    public BloomFilter(int bitSize, int hashCount) {
        if (bitSize <= 0 || hashCount <= 0) throw new IllegalArgumentException();
        this.bitSize = bitSize;
        this.hashCount = hashCount;
        this.bits = new java.util.BitSet(bitSize);
    }

    public void add(String value) {
        long h1 = mix(value.hashCode());
        long h2 = mix(h1 ^ 0x9E3779B97F4A7C15L);
        for (int i = 0; i < hashCount; i++) bits.set(index(h1 + i * h2));
    }

    public boolean mightContain(String value) {
        long h1 = mix(value.hashCode());
        long h2 = mix(h1 ^ 0x9E3779B97F4A7C15L);
        for (int i = 0; i < hashCount; i++) {
            if (!bits.get(index(h1 + i * h2))) return false;
        }
        return true;
    }

    private int index(long hash) {
        return (int) Math.floorMod(hash, bitSize);
    }

    private static long mix(long x) {
        x ^= x >>> 33; x *= 0xff51afd7ed558ccdl;
        x ^= x >>> 33; x *= 0xc4ceb9fe1a85ec53l;
        return x ^ (x >>> 33);
    }
}

这是理解原理的实现，不应用于安全场景，也没有处理并发、序列化和跨语言哈希一致性。生产中优先使用成熟库或 RedisBloom 等受维护组件。

参数怎样估算

预计插入元素数为 n、位数组长度为 m、哈希函数数量为 k，假阳性率近似：

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

给定目标假阳性率 p，常用估算为：

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

例如目标数据量扩大一倍却不扩容，位数组会更快被填满，假阳性率明显上升。上线时必须监控实际元素量，而不只是初始化时计算一次。

一个具体参数例子

预计保存一百万个键，希望假阳性率不高于 1%：

n = 1,000,000
p = 0.01
m ≈ 9,585,059 bit ≈ 1.14 MiB
k ≈ 6.64，取 7

约 1.14 MiB 就能完成百万级成员初筛，这是它的空间优势。但若实际写入两百万个键而不重建，误判率会远高于 1%。

哈希函数不一定真的实现七套。常用双重哈希从两个基础哈希派生：h(i) = h1 + i * h2，减少计算成本。跨语言使用时必须固定编码、哈希算法、种子、符号和取模规则。

为什么普通 Bloom Filter 不支持删除

一个位可能被多个元素共同设置。删除某元素时直接把位清零，可能让另一个仍存在的元素出现假阴性。Counting Bloom Filter 用小计数器替代单比特，插入加一、删除减一，但会增加空间并带来计数溢出等问题。

Counting Bloom 删除仍要求调用方保证元素确实加入过、删除次数不超过加入次数。否则计数被错误减小，同样会产生假阴性。Cuckoo Filter 保存指纹并支持删除，但负载过高时插入可能失败，需要扩容或重建。

Scalable Bloom Filter 在接近容量时追加新的过滤层，新查询需要检查多层。它降低预估失误的风险，却增加查询计算和总误差管理复杂度。

缓存穿透场景

过滤器通常放在缓存和数据库之前。它返回“不存在”时可挡住请求；返回“可能存在”时继续查询。还需要解决数据一致性：新增数据应先写权威存储，再可靠更新过滤器；重建期间可采用双版本或旁路策略，避免漏加导致假阴性。

布隆过滤器不是“加上就能防穿透”的装饰件。它需要容量规划、构建来源、增量更新、重建流程、监控和降级策略共同组成完整方案。

一个更完整的读取流程是：

布隆过滤器防缓存穿透的数据流图

图：Bloom 负责快速排除，缓存和数据库负责最终确认

Bloom 服务不可用时，系统通常应该限流后回源，而不是把“无法判断”当作“不存在”。否则基础设施故障会变成业务数据假阴性。

新增、删除与一致性

新增数据一般先提交权威数据库，再写 Bloom。两步之间短暂窗口会让新数据被过滤，可使用事务消息、outbox 或变更日志可靠补写。若业务不能接受窗口，应在创建成功后让请求携带旁路信息，或暂时绕过 Bloom。

删除数据无需立即清位，残留只会增加假阳性，数据库仍会给出最终不存在。大量删除后通过重建回收误差空间。这个单向容错特性正是 Bloom 易于工程落地的原因。

持久化、并发与监控

位图可保存在进程内、内存映射文件或 Redis。进程内速度快但实例不一致且重启丢失；Redis 便于共享和持久化，但每次查询多个 bit 会产生网络开销，可通过 Lua 或模块减少往返。

并发设置 bit 通常可以通过原子位操作完成，重建切换则需要版本指针。监控至少包括：

估计写入元素数与设计容量比。
位图中 1 的比例。
Bloom 拒绝率和放行后数据库未命中率。
重建水位、耗时、失败次数和版本。
查询延迟与后端节省的请求量。

测试清单

已插入元素绝不能返回不存在。
对独立未插入样本统计实际假阳性率。
序列化、重启加载后结果一致。
多线程写入不丢位。
容量达到 50%、100%、150% 时观察误差变化。
重建切换期间新增数据不丢失。
Bloom 故障时降级策略不会返回错误业务结论。