布隆过滤器优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器,感兴趣的朋友跟随小编一起看看吧

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器。

应用

1、50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog)
2、客户端看时,它会不断推荐新的内容,每次推荐时都要去重,那么如何实现去重?
3、爬虫URL去重?
4、NoSQL数据库领域数据库的IO请求数量?
5、邮箱系统的垃圾邮件过滤?

布隆过滤器(Bloom Filter)就是专门来解决这种问题的,它起到去重的同时,在空间上还能节省90%以上,只是存在一定的误判概率。

认识布隆过滤器

布隆过滤器是一种类似set的数据结构,只是不太准确,当用bf.exists判断元素是否存在时返回结果存在但真实不一定存在;当返回不存在时肯定是不存在,所以判断去重时有一定的误判概率。
当然,误判只会发生在过滤器没有添加过的元素,对于添加过的元素不会发生误判。
特点:高效地插入和查询,占用空间少,返回的结果是不确定性的。

布隆过滤器原理

每个布隆过滤器对应到Redis的数据结构中就是一个大型的位数组和几个不同的无偏hash函数,无偏表示分布均匀。

添加key时,使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,每个hash函数都会得到一个不同的位置,将这几个位置都置1就完成了add操作。

查询同理,只要有一位是0就表示这个key不存在,但如果都是1,则不一定存在对应的key。

空间占用估计

布隆过滤器的空间占用有一个简单的计算公式,但推导比较繁琐。布隆过滤器有两个参数,预计元素数量n,错误率f,公式得到两个输出,位数组长度L(即存储空间大小bit),hash函数的数量k。

k = 0.7*(1/n)
f = 0.6185^(L/n)

1、位数组相对长度越长,错误率越低;
2、位数组相对长度越长,需要的hash函数越多;
3、当一个元素平均需要一个字节(8bit)的指纹空间时(L/n=8),错误率大约为2%。

实际元素超出时,误判率会怎样变化?

f = (1-0.5^t)^k  # t为实际元素与预计元素的倍数
1、当错误率为10%时,倍数比为2时,错误率接近40%;
2、当错误率为1%,倍数比为2时,错误率15%;
3、当错误率为0.1%,倍数为2时,错误率5%

Redis实现简单Bloom Filter

要想使用redis提供的布隆过滤器,必须添加redis 4.0版本以上的插件才行,具体参照网上安装步骤。

布隆过滤器有两个基本指令,bf.add添加元素,bf.exists查询元素是否存在,bf.madd一次添加多个元素,bf.mexists一次查询多个元素。

> bf.add spiderurl www.baidu.com
> bf.exists spiderurl www.baidu.com
> bf.madd spiderurl www.sougou.com www.jd.com
> bf.mexists spiderurl www.jd.com www.taobao.com

布隆过滤器在第一次add的时候自动创建基于默认参数的过滤器,Redis还提供了自定义参数的布隆过滤器。

在add之前使用bf.reserve指令显式创建,其有3个参数,key,error_rate, initial_size,错误率越低,需要的空间越大,error_rate表示预计错误率,initial_size参数表示预计放入的元素数量,当实际数量超过这个值时,误判率会上升,所以需要提前设置一个较大的数值来避免超出。

默认的error_rate是0.01,initial_size是100。

利用布隆过滤器磁盘 IO 或者网络请求,因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。

总结

以上所述是小编给大家介绍的Redis实现布隆过滤器的方法及原理,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

最新资讯
“支付江湖”B端争夺战升级 拉卡拉携手华为推手机POS

“支付江湖”B端争夺

新一轮支付与收单方式之争正在升级。随着支付C端市场
5G最新标准:纳米级“舞蹈”提升手机八成上行速率

5G最新标准:纳米级“舞

广为人知的5G特性之一“高带宽”,有一个潜在定语“下载
液晶电视主板不能保修 今年或纳入3年质保

液晶电视主板不能保修

TCL方面称,三包法规定逻辑组件保修3年,若主板集成逻辑电
携程旗下订票网站Skyscanner宣布裁员五分之一

携程旗下订票网站Skys

Skyscanner宣布计划裁员五分之一,即300人左右,其中包括
格力电器上半年净利预降5成 线下渠道变革备受关注

格力电器上半年净利预

回看近十年,京海担保曾先后进行了两次减持格力电器,2011
马斯克身家超巴菲特

马斯克身家超巴菲特

近两周,特斯拉股价累计涨幅已经超过40%,市值继超越全球
最新文章
从一个小需求感受Redis的独特魅力(需求设计)

从一个小需求感受Redi

Redis在实际应用中使用的非常广泛,本篇文章就从一个简
详解redis desktop manager安装及连接方式

详解redis desktop ma

这篇文章主要介绍了redis desktop manager安装及连接
Redis集群下过期key监听的实现代码

Redis集群下过期key监

这篇文章主要介绍了Redis集群下过期key监听的实现代码
Redis集群增加节点与删除节点的方法详解

Redis集群增加节点与

这篇文章主要给大家介绍了关于Redis集群增加节点与删
Linux 下redis5.0.0安装教程详解

Linux 下redis5.0.0安

这篇文章主要介绍了Linux 下redis5.0.0安装教程,本文图
Redis 实现“附近的人”功能

Redis 实现“附近的人

Redis基于geohash和有序集合提供了地理位置相关功能。