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

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

创新互联建站是一家专业提供仪陇企业网站建设,专注与网站建设、成都网站建设成都h5网站建设、小程序制作等业务。10年已为仪陇众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

布隆过滤器的简介

布隆过滤器(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中怎么实现一个布隆过滤器

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

exists操作

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

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%

错误率
一个元素所需平均空间
空间数
10%4.792个bit5bit
1%9.585个bit10bit
0.1%14.377个bit15bit

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

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

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

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

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


标题名称:Redis中怎么实现一个布隆过滤器
文章分享:http://azwzsj.com/article/gohoss.html