「Redis」布隆过滤器「BloomFilter」

不积跬步，无以至千里；不积小流，无以成江海。

使用场景

本篇还是从一场景入手，比如我们在使用头条看新闻时，它会给我们不停地推荐新的内容，每次推荐时都会去掉那些已经看过的内容。 有没有想过 <strong>推送去重 是怎么实现的？

容易想到的方案：

方案一：

浏览记录存在 <strong>关系型 数据库里，去重时对数据库进行 <strong>exists 查询，但当系统 <strong>并发 量很高时，数据库扛的住吗？

方案二

使用set来实现这个功能。但如果数据量较大，使用set会非常消耗内存，日积月累能撑多久？还有上节提到的 BitMap 来提高性能。但 BitMap 仍然比较消耗内存，尤其是在数据比较稀疏的情况下，使用BitMap并不划算。

有了上节基础，更易于理解本节。

实际上，对于“<strong>去重”问题，业界有另外一个更优秀的数据结构来解决这类问题，那就是—— <strong>布隆过滤器(BloomFilter)。它在起到去重的同时，还能节省 90% 以上的空间，只是稍微有那么点不精确，也就是有一定的 <strong>误判概率。

对于上面这种情况 某篇新闻 看过与否 真的那么重要吗

Bloom Filter 是什么

布隆过滤器是Burton Howard Bloom在1970年提出来的，一种空间效率极高的 <strong>概率型算法 和 <strong>数据结构，主要用来判断一个元素 <strong>是否在集合中存在。

因为他是一个概率型的算法，所以会存在 <strong>一定的误差，当布隆过滤器说某个值存在时，这个值 <strong>可能 不存在；当它说不存在时，那就 <strong>肯定 不存在。

因此，Bloom Filter不适合那些“<strong>零错误”的应用场合。而在能容忍 <strong>低错误率 的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。

布隆过滤器原理

布隆过滤器与 BitMap 类似，底层也是一个 <strong>位数组。1表示有，0表示无。但布隆过滤器比BitMap需要更少的内存，它是怎么办到的呢？答案是 <strong>多个hash。

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

我们知道hash算法，是把一个数从较大范围的值，映射到较小范围值。比如我们有一个10位的数组，使用某个hash算法 对应 其数组上的表示：

hash('a') = 3

hash('b') = 5

0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0

这样，我们使用这个hash算法就能快速的判断一个字符串是不是存在一个集合里面了。但众所周知，hash算法是有可能发生 <strong>hash碰撞。比如可能有两个不同的字符串映射到同一个数：

hash(“a”) = 3;

hash(“aof”) = 3;

这种情况下，就不能准确得判断出某个字符串是不是存在于集合之中。

对于这种情况的处理方案是使用 多个 不同的 hash算法。比如：

h1(“a”) = 3, h2(“a”) = 5, h3(“a”) = 7;

h1(“aof”) = 5, h2(“aof”) = 6, h3(“aof”) = 7;

向布隆过滤器中 添加 key 时，会使用 <strong>多个 hash 函数对 key 进行 hash 算得一个整数 <strong>索引值,再把位数组的这几个位置都置为 1 就完成了 add 操作。

向布隆过滤器 查找 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都为 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。

如果<strong>都是 1，这并不能说明这个 key 就一定存在，只是<strong>极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。所以布隆过滤器 <strong>不能删除，因为一旦删除（即将相应的位置为0），就很大可能会影响其他元素。

如果这个位数组比较稀疏，判断正确的概率就会很大，如果这个位数组比较拥挤，判断正确的概率就会降低。

Redis 布隆过滤器

Redis的布隆过滤器不是原生自带的，而是要通过module加载进去。Redis在<strong>4.0版本

Redis 布隆过滤器有二个基本指令：

<strong>bf.add 添加元素 <strong>bf.exists 查询元素是否存在

它的用法和 set 集合的 sadd 和 sismember 差不多bf.add 只能一次添加一个元素，如果想要一次添加多个，就需要用到 <strong>bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到 <strong>bf.mexists 指令。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次add的时候自动创建。Redis还提供了自定义参数的布隆过滤器，需要在add之前使用 <strong>bf.reserve 指令显式创建。如果对应的key已经存在，bf.reserve会报错(error) ERR item exists

bf.reserve 过滤器名 error_rate initial_size

bf.reserve strs 0.01 100

参数含义

• 第一个值是过滤器的名字。
• 第二个值为 error_rate 的值：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• 第三个值为 initial_size 的值：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

布隆过滤器的 initial_size 估计的 <strong>过大，会<strong>浪费存储空间

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

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

空间占用

布隆过滤器的空间占用 有一个计算公式，这里略过，这里直接用网上专门的计算器

「 https://krisives.github.io/bloom-calculator/ 」

第一个是预计元素的数量

第二个是错误率

公式根据这两个输入得到两个输出

第一个输出是 hash 函数的最佳数量

第二个输出是位数组的长度，也就是需要的存储空间大小 (bit)

其他适用场景

在爬虫系统中，我们需要对 URL 进行去重，已经爬过的网页就可以不用爬了

QQ 邮箱的垃圾邮件判别

经典的缓存穿透问题

点关注 不迷路

以上就是这篇的全部内容，能看到这里的都是 人才。

如果你从本篇内容有收获，求 点赞，求 关注

如果本文有任何错误，请批评指教，不胜感激 ！

閱讀更多 不住隔壁的王老師 的文章

關鍵字: Redis 数据结构 某篇