Redis中怎么实现一个布隆过滤器

本篇文章为大家展示了Redis中怎么实现一个布隆过滤器，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

布隆过滤器（BloomFilter）是一个很长的二进制向量和一系列随机映射函数，我们也可以简单的理解为它是一个不怎么精确的set结构。本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的List、Set、Map等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，但是我们不必过于担心它不够精确，只要参数设置合理，它的精度可以控制到足够的精确。

适用场景：

• 大数据是否存在的问题，比如上述的刷抖音去重问题

• 解决缓存击穿问题，如果数据请求一直是一个不存在的内容，那么它会越过缓存直接请求数据库，造成缓存击穿，布隆过滤器也可以解决此类问题

• 解决爬虫爬到重复url内容等等

布隆过滤器有二个基本指令，bf.add添加元素，bf.exists查询元素是否存在，它的用法和set集合的sadd和sismember差不多。注意bf.add只能一次添加一个元素，如果想要一次添加多个，就需要用到bf.madd指令。同样如果需要一次查询多个元素是否存在，就需要用到bf.mexists指令。

> bf.add user user1(integer) 1> bf.add user user2(integer) 1> bf.add user user3(integer) 1> bf.exists user user1(integer) 1> bf.exists user user4(integer) 0> bf.madd user user4 user5 user61) (integer) 12) (integer) 13) (integer) 1> bf.mexists user user4 user5 user6 user71) (integer) 12) (integer) 13) (integer) 14) (integer) 0

上面使用的布隆过过滤器只是默认参数的布隆过滤器，它在我们第一次add的时候自动创建。Redis也提供了可以自定义参数的布隆过滤器，只需要在add之前使用bf.reserve指令显式创建就好了。如果对应的key已经存在，bf.reserve会报错。bf.reserve有三个参数，分别是key、error_rate(错误率)和initial_size：
error_rate越低，需要的空间越大
initial_size表示预计放入的元素数量，当实际数量超过这个值时，误判率就会提升，所以需要提前设置一个较大的数值避免超出导致误判率升高；
如果不适用bf.reserve，默认的error_rate是0.01，默认的initial_size是100。

add操作

每个布隆过滤器对应到Redis的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。向布隆过滤器中添加key时，会使用多个hash函数对key进行hash算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作。

exists操作

exists操作跟add一样，也会把hash的几个位置都算出来，看看位数组中这几个位置是否都是1，只要有一个位为0，那么说明布隆过滤器中这个key不存在。如果都是1，这并不能说明这个key就一定存在，只是极有可能存在，因为这些位被置为1可能是因为其它的key存在所致。

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

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

布隆过滤器有两个参数，第一个是预计元素的数量n，第二个是错误率f。公式根据这两个输入得到两个输出，第一个输出是位数组的长度l，也就是需要的存储空间大小(bit)，第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

从公式中可以看出

• 1.位数组相对越长(l/n)，错误率f越低，这个和直观上理解是一致的

• 位数组相对越长(l/n)，hash函数需要的最佳数量也越多，影响计算效率

• 当一个元素平均需要1个字节(8bit)的指纹空间时(l/n=8)，错误率大约为 2%

有人会问如果实际的元素超过了预算元素，错误率会如何变化，会不会错误率非常高？我们引入一个公式

f=(1-0.5^t)^k#极限近似， k 是 hash 函数的最佳数量#t表示实际元素和预计元素的倍数

错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%
错误率为 1% 时，倍数比为 2 时，错误率升至 15%
错误率为 0.1%，倍数比为 2 时，错误率升至 5%

上述内容就是Redis中怎么实现一个布隆过滤器，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注亿速云行业资讯频道。