布隆过滤器详解：从原理到 Go 实现，解决缓存穿透问题

一、什么是布隆过滤器？

在实际开发中，我们经常会遇到这样的场景：

用户请求查询一个不存在的数据：

GET /user/999999999

系统流程：

请求 ↓ API ↓ Redis ↓ MySQL

如果 Redis 没有数据：

Redis miss ↓ 查询 MySQL

但是这个用户根本不存在。

大量恶意请求：

user/10000001
user/10000002
user/10000003
…

会导致：

大量请求绕过缓存 ↓ 数据库压力增大 ↓ 数据库宕机

这就是经典的：

缓存穿透问题

解决方案之一：

布隆过滤器（Bloom Filter）

二、布隆过滤器解决什么问题？

布隆过滤器用于判断：

一个元素是否一定不存在，或者可能存在。

例如：

用户 ID：

1001
1002
1003
1004

加入布隆过滤器：

Bloom Filter

查询：

1001

结果：

可能存在

查询：

9999

结果：

一定不存在

注意：

布隆过滤器存在：

假阳性（False Positive）

例如：

实际：

用户9999不存在

但是：

Bloom Filter 返回存在

然后：

继续查询数据库

这是允许的。

但是：

不会假阴性（False Negative）
如果返回：不存在
那么一定不存在。

总结：

情况结果
不存在一定不存在
存在可能存在

三、布隆过滤器原理

布隆过滤器核心：

位数组 + 多个哈希函数

例如：
创建一个长度为10的数组：

bit:
0 0 0 0 0 0 0 0 0 0

加入：

hello

经过三个哈希函数：

hash1(hello)=2
hash2(hello)=5
hash3(hello)=8

设置：

0 0 1 0 0 1 0 0 1 0

继续加入：

world

计算：

hash1(world)=1
hash2(world)=5
hash3(world)=7

结果：

0 1 1 0 0 1 0 1 1 0

查询：

hello

计算：

2
5
8

发现：

bit[2]=1
bit[5]=1
bit[8]=1

说明：可能存在

查询： test
计算：

3
4
9

发现：

bit[4]=0

说明：一定不存在

四、为什么使用多个 Hash？

如果只有一个 Hash：

hash(data)=5

冲突概率很高。
例如：

hello -> 5
world -> 5

两个不同数据认为一样。

多个 Hash：

hash1()
hash2()
hash3()

组合判断：准确率更高。

五、布隆过滤器空间复杂度

假设：

存储：

1000万个用户 ID

如果使用 map：

map[int64]bool

大概：

几十 MB 甚至几百 MB。

布隆过滤器：

只需要：

bit数组。

例如：

1000万个数据：

可能只需要：

几十 MB。

所以：

布隆过滤器优势：

  • 内存占用低
  • 查询速度快
  • O(k)

其中：

k = 哈希函数数量。

六、Go 实现布隆过滤器

我们实现：
支持：

  • Add
  • Exists

1. 定义结构

packagebloomimport("hash/fnv")typeBloomFilterstruct{bits[]bytesizeuinthashCountuint}

2. 创建过滤器

funcNewBloomFilter(sizeuint,hashCountuint,)*BloomFilter{return&BloomFilter{bits:make([]byte,size),size:size,hashCount:hashCount,}}

七、Hash 函数设计

使用：FNV
Go 标准库提供：

hash/fnv

实现：

func(bf*BloomFilter)hash(datastring,seeduint,)uint{h:=fnv.New64a()h.Write([]byte(fmt.Sprintf("%d-%s",seed,data,),),)returnuint(h.Sum64()%uint64(bf.size),)}

八、添加数据

流程：

数据 ↓ 多个hash ↓ 设置bit

代码：

func(bf*BloomFilter)Add(datastring,){fori:=uint(0);i<bf.hashCount;i++{index:=bf.hash(data,i,)bf.bits[index]=1}}

九、判断是否存在

func(bf*BloomFilter)Exists(datastring,)bool{fori:=uint(0);i<bf.hashCount;i++{index:=bf.hash(data,i,)ifbf.bits[index]==0{returnfalse}}returntrue}

十、测试

funcmain(){bf:=NewBloomFilter(100000,5,)bf.Add("user:1001",)fmt.Println(bf.Exists("user:1001",),)fmt.Println(bf.Exists("user:9999",),)}

输出：

true
false

十一、实际项目中的使用方式

场景：缓存穿透防护

原流程：

请求 ↓ Redis ↓ MySQL

优化：

请求 ↓ Bloom Filter ↓ +------不存在 ↓ 返回空 ↓ Redis ↓ MySQL

代码：

funcGetUser(idint64){key:=fmt.Sprintf("user:%d",id,)if!bloom.Exists(key){returnnil}user:=redis.Get(key)ifuser!=nil{returnuser}returnmysql.Find(id)}

十二、布隆过滤器缺点

1. 不支持删除

例如：

添加：user1001
删除：user1001

无法知道：
哪个 bit 属于它。

解决：
使用：
Counting Bloom Filter
把：bit
变成：计数器
例如：

0 1 2 3

删除时：减1。

2. 容量固定

创建：100万个数据
超过：500万个误判率增加。
解决：

  • 扩容 Bloom Filter
  • RedisBloom

十三、布隆过滤器和 Redis

生产环境常用：
RedisBloom
例如：创建

BF.RESERVE user_filter 0.01 1000000

添加：

BF.ADD user_filter user:1001

查询：

BF.EXISTS user_filter user:1001

十四、布隆过滤器适合什么场景？

适合：

1. 缓存穿透

例如：

用户不存在查询。

2. 防重复提交

例如：

订单号：order123
判断是否处理过。

3. 爬虫 URL 去重

url列表 ↓ Bloom Filter ↓ 是否抓取过

4. 黑名单过滤

例如：

IP：1.1.1.1
快速判断。

十五、总结

布隆过滤器核心思想：

用极小空间换取快速判断能力。

特点：

优点：

✅ 内存占用低
✅ 查询速度快
✅ 适合海量数据

缺点：

❌ 存在误判
❌ 不支持删除
❌ 容量固定