Redis 之布隆过滤器(BloomFilter)

Myth丶恋晨 2023-06-07 10:33 27阅读 0赞

# 1. 认识BloomFilter #

## 1.1 原理 ##

布隆过滤器，英文叫BloomFilter，可以说是一个二进制向量和一系列随机映射函数实现。 可以用于检索一个元素是否在一个集合中。

下面来看看布隆过滤器是如何判断元素在一个集合中，如下图:

![format_png][]

有三个hash函数和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。

想必聪明的读者已经发现，如果bloom经过三个hash算法，需要判断 1、5、10位是否为1，恰好因为位数组中添加oracle和database导致1、5、10为1，则布隆过滤器会判断bloom会判断在集合中，这不是Bug吗，导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。

是的，这个是布隆过滤器的缺点，有一点的误识别率，但是布隆过滤器有2大优点，使得这个缺点在某些应用场景中是可以接受的，2大优点是空间效率和查询时间都远远高于一般的算法。常规的数据结构set，也是经过被用于判断一个元素是否在集合中，但如果有上百万甚至更高的数据，set结构所占的空间将是巨大的，布隆过滤器只需要上百万个位即可，10多Kb即可。

导致这个缺点是因为hash碰撞，但布隆过滤器通过多个hash函数来降低hash碰撞带来的误判率，如下图:

![format_png 1][]

当只有1个hash函数的时候，误判率很高，但4个hash函数的时候已经缩小10多倍，可以动态根据业务需求所允许的识别率来调整hash函数的个数，当然hash函数越多，所带来的空间效率和查询效率也会有所降低。

第二个缺点相对set来说，不可以删除，因为布隆过滤器并没有存储key，而是通过key映射到位数组中。

总结，敲黑板:

*  布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数实现。
 *  优点：
    
     *  空间效率高，所占空间小。
     *  查询时间短。
 *  缺点：
    
     *  元素添加到集合中后，不能被删除。
     *  有一定的误判率

## 1.2 应用场景 ##

*  数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
 *  业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。还有之前自己遇到的一个比赛类的社交场景中，需要判断用户是否在比赛中，如果在则需要更新比赛内容，也可以使用布隆过滤器，可以减少不在的用户查询db或缓存的次数。
 *  缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
 *  WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。

# 2. Redis-BloomFilter实践 #

Redis在4.0版本推出了 [module][] 的形式，可以将 module 作为插件额外实现Redis的一些功能。官网推荐了一个 [RedisBloom][] 作为 Redis 布隆过滤器的 Module。

除了这个还有别的方式可以实现，下面一一列举一下:

*  [RedisBloom - Bloom Filter Module for Redis][RedisBloom]
 *  [pyreBloom][]
 *  [lua脚本来实现][lua]
 *  原生语言，调用 Redis 的 bitmap 相关操作来实现

[https://juejin.im/post/5cfd060ee51d4556f76e8067][https_juejin.im_post_5cfd060ee51d4556f76e8067]

## 2.3 原生语言 + redis 实现 ##

Python 原生语言比较慢，如果是Go语言，没有找到合适的开源redis的BloomFilter，就可以自己用原生语言 + redis的 bitmap 相关操作实现。 Java 语言的话，RedisBloom项目里有实现 [JReBloom][]，因非Java开发者，这块可以自行了解。

[format_png]: /images/20230601/86ce06e928e8461098eff4ba3731b43c.png
[format_png 1]: /images/20230601/bc590d4c5f9e4fb0b74fdec861fc25b3.png
[module]: https://link.juejin.im?target=https%3A%2F%2Fredis.io%2Fmodules
[RedisBloom]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2FRedisBloom%2FRedisBloom
[pyreBloom]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2Fseomoz%2FpyreBloom
[lua]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2Ferikdubbelboer%2Fredis-lua-scaling-bloom-filter
[https_juejin.im_post_5cfd060ee51d4556f76e8067]: https://juejin.im/post/5cfd060ee51d4556f76e8067
[JReBloom]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2FRedisBloom%2FJReBloom