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实现布隆过滤器的方法及原理，希望对大家有所帮助
相关文章
- 这篇文章主要介绍了详解如何清理redis集群的所有数据，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-18
- 这篇文章主要介绍了Redis连接池配置及初始化实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-29
详解redis desktop manager安装及连接方式
这篇文章主要介绍了redis desktop manager安装及连接方式，本文图文并茂给大家介绍的非常详细，具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-15- 这篇文章主要介绍了浅谈redis key值内存消耗以及性能影响，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-07
- 最近在工作中遇到了一个问题，通过查找相关资料才得知原因是因为返回结果的问题，下面这篇文章主要给大家介绍了关于lua读取redis数据的null判断的相关资料，文中通过示例代码介绍的非常详细，需要的朋友可以参考下...2020-06-30
- 这篇文章主要介绍了SpringBoot集成Redis实现消息队列的方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-10
redis setIfAbsent和setnx的区别与使用说明
这篇文章主要介绍了redis setIfAbsent和setnx的区别与使用，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教...2021-08-04- 这篇文章主要介绍了Redis的Expire与Setex区别说明，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-15
- Redis 是一个开源、高性能的Key-Value数据库，被广泛应用在服务器各种场景中。本文介绍几个查看Redis内存信息的命令，包括常用的info memory、info keyspace、bigkeys等。...2021-01-15
- 在本篇文章里小编给大家整理的是关于Redis的持久化方案详解，有兴趣的朋友们可以参考下。...2021-01-15
- 这篇文章主要介绍了@CacheEvict + redis实现批量删除缓存方式，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教...2021-10-12
JAVA中 redisTemplate 和 jedis的配合使用操作
这篇文章主要介绍了JAVA中 redisTemplate 和 jedis的配合使用操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-13- 这篇文章主要介绍了redis 交集、并集、差集的具体使用，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
解决redisTemplate中leftPushAll隐性bug的问题
这篇文章主要介绍了解决redisTemplate中leftPushAll隐性bug的问题，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-13- 这篇文章主要介绍了Redis集群水平扩展、集群中添加以及删除节点的操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-25
- 这篇文章主要介绍了Redis开启远程访问及密码的教程，文中给大家提到了Redis启动报错解决方法,需要的朋友可以参考下...2021-01-15
- 这篇文章主要给大家介绍了关于如何利用Redis如何实现自动补全功能的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用Redis具有一定的参考学习价值，需要的朋友们下面来一起学习学习吧...2020-04-17
- pipeline 只是把多个redis指令一起发出去，redis并没有保证这些指定的执行是原子的；multi相当于一个redis的transaction的，保证整个操作的原子性，避免由于中途出错而导致最后产生的数据不一致。本文详细的介绍，感兴趣的可以了解一下...2021-06-02
springboot +redis 实现点赞、浏览、收藏、评论等数量的增减操作
这篇文章主要介绍了springboot +redis 实现点赞、浏览、收藏、评论等数量的增减操作，本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-15- 这篇文章主要介绍了使用Redis获取数据转json,解决动态泛型传参的问题，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-15