一、什么是布隆过滤器在实际开发中我们经常会遇到这样的场景用户请求查询一个不存在的数据GET /user/999999999系统流程请求 ↓ API ↓ Redis ↓ MySQL如果 Redis 没有数据Redis miss ↓ 查询 MySQL但是这个用户根本不存在。大量恶意请求user/10000001user/10000002user/10000003…会导致大量请求绕过缓存 ↓ 数据库压力增大 ↓ 数据库宕机这就是经典的缓存穿透问题解决方案之一布隆过滤器Bloom Filter二、布隆过滤器解决什么问题布隆过滤器用于判断一个元素是否一定不存在或者可能存在。例如用户 ID1001100210031004加入布隆过滤器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)2hash2(hello)5hash3(hello)8设置0 0 1 0 0 1 0 0 1 0继续加入world计算hash1(world)1hash2(world)5hash3(world)7结果0 1 1 0 0 1 0 1 1 0查询hello计算258发现bit[2]1bit[5]1bit[8]1说明可能存在查询 test计算349发现bit[4]0说明一定不存在四、为什么使用多个 Hash如果只有一个 Hashhash(data)5冲突概率很高。例如hello - 5world - 5两个不同数据认为一样。多个 Hashhash1()hash2()hash3()组合判断准确率更高。五、布隆过滤器空间复杂度假设存储1000万个用户 ID如果使用 mapmap[int64]bool大概几十 MB 甚至几百 MB。布隆过滤器只需要bit数组。例如1000万个数据可能只需要几十 MB。所以布隆过滤器优势内存占用低查询速度快O(k)其中k 哈希函数数量。六、Go 实现布隆过滤器我们实现支持AddExists1. 定义结构packagebloomimport(hash/fnv)typeBloomFilterstruct{bits[]bytesizeuinthashCountuint}2. 创建过滤器funcNewBloomFilter(sizeuint,hashCountuint,)*BloomFilter{returnBloomFilter{bits:make([]byte,size),size:size,hashCount:hashCount,}}七、Hash 函数设计使用FNVGo 标准库提供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);ibf.hashCount;i{index:bf.hash(data,i,)bf.bits[index]1}}九、判断是否存在func(bf*BloomFilter)Exists(datastring,)bool{fori:uint(0);ibf.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,),)}输出truefalse十一、实际项目中的使用方式场景缓存穿透防护原流程请求 ↓ 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 FilterRedisBloom十三、布隆过滤器和 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. 黑名单过滤例如IP1.1.1.1快速判断。十五、总结布隆过滤器核心思想用极小空间换取快速判断能力。特点优点✅ 内存占用低✅ 查询速度快✅ 适合海量数据缺点❌ 存在误判❌ 不支持删除❌ 容量固定