Redis----布隆过滤器

目录

背景

解决方案

什么是布隆过滤器

布隆过滤器的原理

一些其他运用

---

背景

比如我们在观看新闻或者刷微博的时候，会不停地给我们推荐新的内容，我们发现几乎没有重复的，说明后台已经进行了去重处理，基于如何去重，Redis给出了高效的方案---布隆过滤器

解决方案

1.记录已经浏览过的，再次推送时遍历记录。但是如果用户量很大的时候，性能大大受限。而且频繁从数据库中读存，并发量过高容易崩溃；

2.使用缓存？缓存撑的过一时撑不过一世；

什么是布隆过滤器

粗略的理解为一个不怎么精确的set，当用它自带的contains方法判断某个对象是否存在的时候，得到的结果可能是假的，他会误判，就是说如果他说有，这个对象可能不存在，但是如果他说没有，一定是没有的。这样的准确度其实已经非常不错了。

基于上面的背景，它很好的可以做到推送没有见过的内容，但也有一小部分已经被过滤（没看过），因为产生了误判，它以为有这个值，所以这样的话以一点点的代价实现了用户不会看到已经看过的内容。

布隆过滤器的原理

有上面的特点完全是由于他的数据结构决定的。

每个布隆过滤器对应到Redis的数据结构是一个大型的位数组（之前提到过位图Redis --- 位图，不了解的可以去看下这个链接） 和几个不一样的hash函数，并且这几个hash函数会把值算的很均匀。

原理来啦：：！！！

1. 当往布隆add的时候，添加的key会被多个hash函数进行计算，得到整数后对位数组长度进行取模运算，会得到多个位置，并且把这些位置都置为1.

2.当运行contains时，询问key是否存在，和add一样，也会把hash得到的位置都算出来，然后看一下对应位置的值是否是1，如果有一个为0，那么这个值一定不存在。但是如果都是1，也不一定说明它一定存在，只是有可能存在，因为多个值的key可能覆盖了这些位置。

思考一个问题，位数组稀疏的话，这个概率会大还是小？下方投票哦~

所以我们在使用的时候，如果实际元素远大于初始大小，需要尽快重建，重新分配一个更大size的过滤器，再将历史元素批量add进去。

一些其他运用

在爬虫系统中，我们需要对 URL 进行去重，已经爬过的网页就可以不用爬了。但是URL 太多了，几千万几个亿，如果用一个集合装下这些 URL 地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗，只不过也会使得爬虫系统错过少量的页面。

布隆过滤器在 NoSQL数据库领域使用非常广泛，我们平时用到的 HBase、Cassandra还有 LevelDB、RocksDB 内部都有布隆过滤器结构，布隆过滤器可以显著降低数据库的 10请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row 请求，然后再去磁盘进行查询。

邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低。