Redis知识梳理(5) [ BloomFilter 布隆过滤器 ]

女爷i 2022-02-03 12:45 301阅读 0赞

Redis官方提供的布隆过滤器到了 Redis4.0提供了插件功能之后才正式登场。布 隆过)洁、器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能 。

布隆过滤器可以理解为一个不怎么精确的 set 结构，

当你使用它的 contains 方 法判断某个对象是否存在时，它可能会误判。

但是布隆过滤器也不是特别不精 确，只要参数设置的合理，

它的精确度可以控制的相对足够精确，只会有小小的 误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在;当它说不存在时，那就肯定 不存在。

打个比方，当它说不认识你时，肯定就不认识;当它说见过你时，可能 根本就没见过面，

不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系 数组合)，所以误判以前见过你。

套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没 有看过的新内容，

它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能 准确识别。

这样就可以完全保证推荐给用户的内容都是无重复的。

下面我们来体验一下 Redis 4.0 的布隆过滤器，为了省去繁琐安装过程，我们直 接用 Docker 吧。

> docker pull redislabs/rebloom \# 拉取镜像  
> docker run -p6379:6379 redislabs/rebloom \# 运行容器

> redis-cli \# 连接容器中的 redis 服务

布隆过滤器有二个基本指令， **bf.add** 添加元素， **bf.exists** 查询元素是否存 在，

它的用法和 set 集合的 sadd 和 sismember 差不多。

> **注意:**
> 
> **bf.add 只能一 次添加一个元素，如果想要一次添加多个，就需要用到 bf.madd 指令。**
> 
> **同样如 果需要一次查询多个元素是否存在，就需要用到 bf.mexists 指令。**

127.0.0.1:6379> bf.add codehole user1  
(integer) 1  
127.0.0.1:6379> bf.add codehole user2  
(integer) 1  
127.0.0.1:6379> bf.add codehole user3  
(integer) 1  
127.0.0.1:6379> bf.exists codehole user1  
(integer) 1  
127.0.0.1:6379> bf.exists codehole user2  
(integer) 1  
127.0.0.1:6379> bf.exists codehole user3  
(integer) 1  
127.0.0.1:6379> bf.exists codehole user4  
(integer) 0  
127.0.0.1:6379> bf.madd codehole user4 user5 user6  
1) (integer) 1  
2) (integer) 1  
3) (integer) 1  
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7  
1) (integer) 1  
2) (integer) 1  
3) (integer) 1  
4) (integer) 0

> 注: 数据量大的时候,会不准确!!!

Redis 其实还提供了自定义参数的布隆过滤器，需要我们在 add 之前使用 **bf.reserve** 指令显式创建。

如果对应的 key 已经存在，bf.reserve 会报错。

**bf.reserve** 有三个参数，分别是 **key, error\_rate** 和 **initial\_size** 。

错误率越低，需要的空间越大。

**initial\_size** 参数表示预计放 入的元素数量，当实际数量超出这个数值时，误判率会上升。

所以需要提前设置一个较大的数值避免超出导致误判率升高。

**如果不使用 bf.reserve，默认的 error\_rate 是 0.01，默认的 initial\_size 是 100。**

布隆过滤器的 initial\_size 估计的过大，会浪费存储空间，估计的过小，就会 影响准确率，

用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上 一定的冗余空间以避免实际元素可能会意外高出估计值很多。

布隆过滤器的 error\_rate 越小，需要的存储空间就越大，对于不需要过于精确 的场合， error\_rate 设置稍大一点也无伤大雅。

比如在新闻去重上而言，误判 率高一点只会让小部分文章不能让合适的人看到，

文章的整体阅读量不会因为这 点误判率就带来巨大的改变。

布隆过滤器的原理

![img][]

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一 样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个 整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会 算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都 算出来，看看位数组中这几个位置是否都位 1，只要有一个位为 0，那么说明布 隆过滤器中这个 key 不存在。如果都是 1，这并不能说明这个 key 就一定存 在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所 致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤， 这个概率就会降低。具体的概率计算公式比较复杂，感兴趣可以阅读扩展阅读， 非常烧脑，不建议读者细看。

使用时不要让实际元素远大于初始化大小，当实际元素开始超出初始化大小时， 应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历 史元素批量 add 进去 (这就要求我们在其它的存储器中记录所有的历史元素)。 因为 error\_rate 不会因为数量超出就急剧增加，这就给我们重建过滤器提供了较 为宽松的时间。

# 空间占用估计 #

第一个是预计元素的数量 n，第二个是错误率 f。

公式 根据这两个输入得到两个输出，第一个输出是位数组的长度 l，也就是需要的存 储空间大小 (bit)，

第二个输出是 hash 函数的最佳数量 k。

hash 函数的数量也 会直接影响到错误率，最佳的数量会有最低的错误率。

> k=0.7\*(l/n) \# 约等于  
> f=0.6185^(l/n) \# ^ 表示次方计算，也就是 math.pow

从公式中可以看出

1.  位数组相对越长 (l/n)，错误率 f 越低，这个和直观上理解是一致的
2.  位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率
3.  当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (l/n=8)，错误率大约为2%
4.  错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为5bit
5.  错误率为 1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为10bit
6.  错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为15bit

# 实际元素超出时，误判率会怎样变化 #

当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓 地上升，这就需要另外一个公式，引入参数 t 表示实际元素和预计元素的倍数 t

f=(1-0.5t)k \# 极限近似，k 是 hash 函数的最佳数量

当 t 增大时，错误率，f 也会跟着增大，分别选择错误率为 10%,1%,0.1% 的 k 值，画出它的曲线进行直观观察

![img][img 1]

从这个图中可以看出曲线还是比较陡峭的

1.  错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%，这个就比 较危险了
2.  错误率为 1% 时，倍数比为 2 时，错误率升至 15%，也挺可怕的
3.  错误率为 0.1%，倍数比为 2 时，错误率升至 5%，也比较悬了

[img]: /images/20220203/3d0bf784a49f444280d985048ba684a1.png
[img 1]: /images/20220203/bdd757f4686448be8ab2f58dbed5aaef.png