先说一个扎心的事实：很多号称"高并发"的系统，QPS 的水分全在无效请求上。爬虫拿着不存在的商品 ID 疯狂试探，脚本小子拿随机 UUID 打接口，你的缓存明明命中率 99%，却因为那 1% 的穿透把数据库按在地上摩擦。

于是加锁、限流、加机器——最后发现机器越多烧得越快，因为每个机器都在认真回答一个"根本不存在"的问题。

布隆过滤器（Bloom Filter）就是来解决这个问题的：用一块几乎不占地方的内存，把绝大多数不存在的请求挡在缓存和数据库之前。它的误判率可以低到 0.1% 以下，代价是"可能把不存在的说成存在"（false positive），但绝不会"把存在的说成不存在"（绝不会漏判）。

有意思的是，这个结论和"布隆过滤器只支持添加不支持删除"的经典印象有点冲突——我们最后会讲怎么绕过它。

一、先搞清楚它到底在做什么

布隆过滤器本质上是一个位数组（bit array）加一组哈希函数。判断"某个 key 是否可能存在"的过程朴素得令人发指：

// 伪代码
func (b *Bloom) MayContain(key string) bool {
    for _, h := range b.hashFuncs {   // 比如 7 个哈希函数
        idx := h(key) % b.m            // 映射到位数组的某个位置
        if !b.bit[idx] {
            return false              // 只要有一位是 0 → 一定不存在
        }
    }
    return true                       // 全是 1 → "可能存在"

插入也是同一套逻辑：把这几个位置全部置 1。

整个过程的复杂度是 O(k)，k 是哈希函数个数，典型值 4~7，也就是说我判断一个 key 大概是几次内存访问和几个位运算，比一次 Redis 往返便宜两个数量级，比一次 SQL 便宜三个数量级。

关键洞察：它的"假阳性"不是 bug，而是它的设计代价。位数组被填得越满，误判率越高，所以我们必须精心挑选位数组大小。

二、误判率怎么算？为什么你现在的参数一定是错的

公式不复杂，但绝大多数人凭感觉设参数，比如"一百万个元素，开个 10MB 数组，够了吧"。我们来算算。

设位数组长度 m，哈希函数个数 k，插入元素个数 n。填满的概率推下来，误判率 p 的近似公式是：

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

当 k 取最优值 k = m/n × ln2 时，误判率最小，此时：

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

我们用 Python 快速验证并给一张速查表（n = 100 万）：

import math
n = 1_000_000
for ratio, p in [(10, None), (12, None), (16, None), (20, None), (8, None)]:
    m = int(n * ratio)
    k = max(1, round(m / n * math.log(2)))
    p = (1 - math.exp(-k * n / m)) ** k
    print(f"m/n={ratio:>2}  m={m/1024/1024:>5.1f}MB  k={k:>2}  p={p:.6f}")

输出大致是：

m/n=10  m=  9.5MB  k= 7  p=0.008194
m/n=12  m= 11.4MB  k= 8  p=0.003065
m/n=16  m= 15.3MB  k=11  p=0.000455
m/n=20  m= 19.1MB  k=14  p=0.000061
m/n= 8  m=  7.6MB  k= 6  p=0.016807

看出规律了吗？

• 每给一个元素多留 1 个 bit，误判率大致乘以 0.618，指数级下降，不是线性。
• 从 8 bit/元素 提到 10 bit/元素，误判率只从 1.68% 降到 0.82%；但从 16 提到 20，就是从 0.045% 降到 0.006%，差了 7 倍多。
• 所以"内存够就多开点"是个错误直觉。低于 16 bit/元素 的时候，内存的边际收益还没榨干；超过 24 bit/元素，再堆内存就纯属烧钱。

实战建议：你能接受 1% 的误判率吗？1% 听起来很低，但你的接口 QPS 是 10 万/秒的话，就是 1000 次/秒的假阳性查询打到数据库。所以面向数据库保护的场景，我一般直接按 16 bit/元素 起，配 k≈11，误判率 0.05% 左右。

三、哈希函数：为什么你需要 k 个，而不是 1 个

如果只用 1 个哈希函数，所有哈希到同一位置的元素会互相"连坐"——那个位一置 1，一大票 key 全都变成"可能存在"，误判率会离谱地高。

多个哈希函数能降低这个聚集效应。有个巧妙的取巧方式：不需要真的实现 k 个不同的哈希函数，用两个就够了。

h1 = murmur(key)
h2 = murmur(key + 0x9e3779b9)   // 或另一个 seed

for i := 0; i < k; i++ {
    idx := (h1 + i*h2) % m     // 双哈希法
    ...
}

这个技巧叫 double hashing，效果和 Kirsch-Mitzenmacher 那套组合哈希几乎等价，但省掉了 k-1 次哈希计算。Kirsch-Mitzenmacher 的组合哈希做一次就是：

idx = (h1 + i*h2) % m

等等，这俩不是一样吗？—— 组合哈希理论上是 g(d) = h1(x) + i·h2(x) mod m，而双哈希是 (h1 + i·h2) mod m，形式相同但第二项是常量而非再哈希一次。生产里两者效果差异可以忽略，双哈希的常数因子更小，因为我们只算两次 murmur 而不是 k 次。

四、Go 实现：一个能用的 Counting Bloom Filter

先写个最朴素的版本，注意位数组用 []uint64 而不是 []bool——用 bool 的话每个 bit 占一个字节，内存直接翻 64 倍，这坑我见过太多人踩。

package bloom

import (
    "hash/maphash"
    "math/bits"
)

type Bloom struct {
    bits   []uint64
    m      uint64
    k      uint
    seeds  [2]uint64
}

func New(n uint64, bitsPerElem float64) *Bloom {
    m := uint64(float64(n) * bitsPerElem)
    m = (m + 63) / 64 * 64 // 对齐到 64
    k := uint(float64(m)/float64(n) * 0.6931) // ln2
    if k < 1 {
        k = 1
    }
    return &Bloom{
        bits:  make([]uint64, m/64),
        m:     m,
        k:     k,
        seeds: [2]uint64{0x9e3779b97f4a7c15, 0xbf58476d1ce4e5b9},
    }
}

func (b *Bloom) idx(h1, h2 uint64, i uint) uint64 {
    return (h1 + uint64(i)*h2) % b.m
}

func (b *Bloom) set(pos uint64) {
    b.bits[pos/64] |= 1 << (pos % 64)
}

func (b *Bloom) get(pos uint64) bool {
    return b.bits[pos/64]&(1<<(pos%64)) != 0
}

func (b *Bloom) Add(key string) {
    h1, h2 := b.hash(key)
    for i := uint(0); i < b.k; i++ {
        b.set(b.idx(h1, h2, i))
    }
}

func (b *Bloom) MayContain(key string) bool {
    h1, h2 := b.hash(key)
    for i := uint(0); i < b.k; i++ {
        if !b.get(b.idx(h1, h2, i)) {
            return false
        }
    }
    return true
}

哈希部分可以复用 hash/maphash（Go 1.19+ 自带，带随机 seed，天然防哈希碰撞攻击）：

var seed = maphash.MakeSeed()

func (b *Bloom) hash(key string) (uint64, uint64) {
    var s1, s2 maphash.Hash
    s1.SetSeed(seed)
    s2.SetSeed(seed)
    s1.WriteString(key)
    s2.WriteString(key + "#2")
    return s1.Sum64(), s2.Sum64()
}

这个版本能用，但有个致命问题：不支持删除。因为一旦有位是多个 key 共享的，你无法确定这个位能不能清零。删掉一个 key 却让另一个 key 失效，缓存穿透直接变成缓存雪崩。

五、想删除？上计数布隆过滤器

Counting Bloom Filter 的思路很朴素：把每个 bit 换成一个 4 位或 8 位的计数器。插入时 +1，删除时 -1，归零就等价于清零那个 bit。

const counterBits = 4  // 0~15
const countersPerWord = 64 / counterBits // 16 个计数器塞进一个 uint64

type CountingBloom struct {
    words   []uint64
    m       uint64
    k       uint
    counters []uint8 // 简化版：用 uint8 存，牺牲内存换清晰
}

更工程一点的做法是用 uint64 打包 16 个 4-bit 计数器：

func (c *CountingBloom) inc(pos uint64, delta int8) {
    w := pos / countersPerWord
    o := (pos % countersPerWord) * counterBits
    cur := (c.words[w] >> o) & 0xF
    v := int(cur) + int(delta)
    if v < 0 { v = 0 }
    if v > 15 { v = 15 }
    c.words[w] = (c.words[w] &^ (0xF << o)) | (uint64(v) << o)
}

代价很明确：4 位计数器让内存变成普通布隆过滤器的 4 倍。也就是说你原本 16 bit/元素的设计，现在实际是 64 bit/元素。对"用内存换 CPU"的场景这很划算；但如果你的内存预算很紧，请老老实实接受"不支持删除"，改用 定期重建。

另一个务实的思路：逻辑删除 + 定期重建。删除时先把 key 写进一个"墓碑集合"，查询时如果命中墓碑就强制穿透到 DB 并异步删除；墓碑集合超过阈值就重建整个过滤器。很多业务场景下这就够用了。

六、布谷鸟哈希：更省内存，但不支持删除

布隆过滤器的空间效率其实还有优化空间。布谷鸟哈希（Cuckoo Filter）的思路是：每个 key 有两个候选位置（用两个哈希函数算出），如果某个位置被占了，就把里面的"客人"赶走，让它去它的另一个候选位置；如果两个位置都满了且赶不动，就扩容。

关键优化在于：每个槽位（slot）只存一个 8 位 fingerprint，而不是完整 key。于是同样的误判率下，内存占用大约是布隆过滤器的 1.23 倍以内、而空间效率比标准布隆好 20%~30%（取决于你需要的误判率）。

// 简化版思路
func (c *CuckooFilter) Insert(key string) bool {
    fp := fingerprint(key)      // 8 bit
    i1 := hash1(key) % numSlots
    i2 := hash2(key) % numSlots
    if c.slots[i1].empty() { c.slots[i1] = fp; return true }
    if c.slots[i2].empty() { c.slots[i2] = fp; return true }
    // 踢人循环：把占位者挪到它的备选位置
    cur, pos := fp, i1
    for i := 0; i < maxKicks; i++ {
        cur, pos = c.slots[pos], c.alt(cur, pos)
        if c.slots[pos].empty() { c.slots[pos] = cur; return true }
    }
    return false // 装不下 → 扩容
}

布谷鸟哈希最大的硬伤：无法删除。因为一个槽位里的 fingerprint 可能对应好几个 key，你删一个把整个槽清空，其他 key 就一起失效了。这个缺陷比布隆过滤器更硬，除非你能容忍"只增不减 + 定期重建"，否则老老实实用布隆。

七、Redis 里的实战：RedisBloom 模块

大多数时候你不需要自己实现。Redis 4.0 之后官方 RedisBloom 模块提供了 BF.ADD / BF.EXISTS / BF.MADD / BF.RESERVE，以及计数版本 CF.ADD / CF.DEL / CF.COUNT。

# 预估容量 100 万，误判率 0.1%，RedisBloom 会自动算好 m 和 k
BF.RESERVE bloom:users 1000000 0.001

BF.ADD bloom:users user:1001 user:1002
BF.EXISTS bloom:users user:1001   # (integer) 1
BF.EXISTS bloom:users user:9999   # (integer) 0

如果不确定未来元素数量，可以不 RESERVE，直接 BF.ADD，RedisBloom 会在 100% 填充率时自动扩容（代价是那一刻的卡顿，能想象吗）。生产环境请务必先 RESERVE，把容量规划做完。

应用层的标准接法是这样的：

func GetUser(ctx context.Context, id string) (*User, error) {
    // 第一道门：布隆过滤器
    exists, err := rdb.Exists(ctx, "bloom:users", id).Result()
    if err != nil {
        // Redis 挂了怎么办？放行，别因为过滤器把业务拖死
        log.Warn("bloom check failed, fallback to db", "err", err)
    } else if !exists {
        // 确认不存在，直接返回空，连缓存都不用查
        return nil, ErrNotFound
    }

    // 第二道门：缓存
    if v := rcache.Get(ctx, "user:"+id); v != nil {
        return v, nil
    }

    // 第三道门：数据库
    u, err := db.QueryUser(ctx, id)
    if err != nil {
        return nil, err
    }
    if u == nil {
        return nil, ErrNotFound
    }
    rcache.Set(ctx, "user:"+id, u, time.Hour)
    return u, nil
}

注意那个 fallback 分支：Redis 故障时必须"放行"而不是"拦截"。布隆过滤器是个优化，不是安全边界，把它当依赖硬失败，Redis 抖一下你的整个接口就跟着挂，这是常见的过度设计。

八、还有几个真实的坑

坑一：数据全量重建时的高峰期。重建期间新旧过滤器必然不一致：新数据只写新过滤器，旧过滤器还没这段数据，于是"明明存在"的 key 会被误判为不存在 → 缓存击穿 → 数据库雪崩。解法是双缓冲：老过滤器继续服务，后台重建新过滤器，完成后原子切换（用一个指针或者 Redis 的 RENAME）。

坑二：别把布隆过滤器当权威数据源。它回答的是"可能存在"，不是"存在"。任何依赖"精确答案"的逻辑（权限校验、订单归属）都别指望它。

坑三：分布式环境的过滤器怎么建？不要每个实例各建各的本地过滤器——那样每个实例都得装载全量 key，内存 × 实例数，扩容即噩梦。正确做法是全量数据放一个共享的 RedisBloom，所有实例共享；或者本地只做"热点 key 的负缓存"，用带 TTL 的 LRU 存最近查询失败的 key。

坑四：key 的规范化必须一致。过滤器和 DB 用的 key 要一模一样（包括大小写、前后缀、大小写折叠规则）。曾经有个团队把 key 统一成小写，过滤器里存小写，查询时传大写，结果过滤器 100% 失效，防护形同虚设——而且因为"有时能挡住"，很难排查。

坑五：误判率不是"漏一个没关系"。如果你的 DB 查询本身很贵（多表 join、聚合），0.05% 的假阳性打到 QPS 10 万的系统上，依然是每秒 50 次重查询。这时候要么把误判率压到 0.001%，要么在 DB 前面再挡一层轻量缓存。

九、什么时候你不需要布隆过滤器

不是所有场景都值得上：

• 数据量小（比如几万条），直接用 Set 存全量 key，内存占用可能比布隆还小，还没有误判率这一说。
• 更新极其频繁且需要删除，布隆和布谷鸟都不支持删除，得靠墓碑 + 重建，复杂度直接翻倍。
• 攻击有随机性：如果攻击者每次都带随机参数（`?id=random&nonce=123`），那每个请求都是新 key，过滤器挡不住任何东西——因为随机 key 会被直接判为"不存在"从而被拦截……好吧，其实这种情况反而挡得很好。但如果攻击者用真实存在的 key 变形（比如 `user:1001` vs `user_1001`），filter 会判定为不存在，恰好也拦住了。真正的绕过方式是遍历真实存在的 key 空间，那属于另一类问题。

结语

布隆过滤器的美妙之处在于：它用"承认错误"换来了极致的空间效率。1 bit 一个元素，误判率千分之一，这是数学上能压到的极限区间。它不保证正确，但它保证不漏——在"保护数据库"这个目标上，这正是我们需要的性质。

但也别把它神化：

过滤器的价值不在于"挡住多少请求"，而在于"让每一个真实存在的请求，都不再需要为不存在的数据付出代价"。

如果你正在为一个读多写少的热点接口做优化，先算清楚"穿透 QPS × 单次 DB 查询成本"这笔账，如果这笔账让你肉疼，一块几十兆的内存就能把问题解决一大半。这大概是内存最划算的一次投资。

最后一句：别再对着 QPS 曲线自我感动了，先看看那 99% 的请求里，有多少压根不该到达你的数据库。