点击上方“码农沉思录”，选择“设为星标”

优质文章，及时送达

一、布隆过滤器简介

上一次我们学会了使用HyperLogLog来对大数据进行一个估算，它非常有价值，可以解决很多精确度不高的统计需求。但是如果我们想知道某一个值是不是已经在HyperLogLog结构里面了，它就无能为力了，它只提供了pfadd和pfcount方法，没有提供类似于contains的这种方法。

就举一个场景吧，比如你刷抖音：

你有刷到过重复的推荐内容吗？这么多的推荐内容要推荐给这么多的用户，它是怎么保证每个用户在看推荐内容时，保证不会出现之前已经看过的推荐视频呢？也就是说，抖音是如何实现推送去重的呢？

你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐短视频时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。问题是当用户量很大，每个用户看过的短视频又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么？

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行exists查询，当系统并发量很高时，数据库是很难抗住压力的。

你可能又想到了缓存，但是这么多用户这么多的历史记录，如果全部缓存起来，那得需要浪费多大的空间啊..(可能老板看一眼账单，看一眼你..)并且这个存储空间会随着时间呈线性增长，就算你用缓存撑得住一个月，但是又能继续撑多久呢？不缓存性能又跟不上，咋办呢？

如上图所示，布隆过滤器(BloomFilter)就是这样一种专门用来解决去重问题的高级数据结构。但是跟HyperLogLog一样，它也一样有那么一点点不精确，也存在一定的误判概率，但它能在解决去重的同时，在空间上能节省90%以上，也是非常值得的。

布隆过滤器是什么

布隆过滤器（BloomFilter）是年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(下面详细说)，实际上你也可以把它简单理解为一个不怎么精确的set结构，当你使用它的contains方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那么一定不存在。打个比方，当它说不认识你时，那就是真的不认识，但是当它说认识你的时候，可能是因为你长得像它认识的另外一个朋友(脸长得有些相似)，所以误判认识你。

布隆过滤器的使用场景

基于上述的功能，我们大致可以把布隆过滤器用于以下的场景之中：

大数据判断是否存在：这就可以实现出上述的去重功能，如果你的服务器内存足够大的话，那么使用HashMap可能是一个不错的解决方案，理论上时间复杂度可以达到O(1的级别，但是当数据量起来之后，还是只能考虑布隆过滤器。解决缓存穿透：我们经常会把一些热点数据放在Redis中当作缓存，例如产品详情。通常一个请求过来之后我们会先查询缓存，而不用直接读取数据库，这是提升性能最简单也是最普遍的做法，但是如果一直请求一个不存在的缓存，那么此时一定不存在缓存，那就会有大量请求直接打到数据库上，造成缓存穿透，布隆过滤器也可以用来解决此类问题。爬虫/邮箱等系统的过滤：平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中，这就是使用布隆过滤器误判导致的。二、布隆过滤器原理解析

布隆过滤器本质上是由长度为m的位向量或位列表（仅包含0或1位值的列表）组成，最初所有的值均设置为0，所以我们先来创建一个稍微长一些的位向量用作展示：

当我们向布隆过滤器中添加数据时，会使用多个hash函数对key进行运算，算得一个证书索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作，例如，我们添加一个wmyskxz：

向布隆过滤器查查询key是否存在时，跟add操作一样，会把这个key通过相同的多个hash函数进行运算，查看对应的位置是否都为1，只要有一个位为0，那么说明布隆过滤器中这个key不存在。如果这几个位置都是1，并不能说明这个key一定存在，只能说极有可能存在，因为这些位置的1可能是因为其他的key存在导致的。

就比如我们在add了一定的数据之后，查询一个不存在的key：

很明显，1/3/5这几个位置的1是因为上面第一次添加的wmyskxz而导致的，所以这里就存在误判。幸运的是，布隆过滤器有一个可以预判误判率的公式，比较复杂，感兴趣的朋友可以自行去阅读，比较烧脑..只需要记住以下几点就好了：

使用时不要让实际元素数量远大于初始化数量；当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进行；三、布隆过滤器的使用

Redis官方提供的布隆过滤器到了Redis4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到RedisServer中，给Redis提供了强大的布隆去重功能。下面我们来体验一下Redis4.0的布隆过滤器，为了省去繁琐安装过程，我们直接用Docker吧。

dockerpullredislabs/rebloom#拉取镜像dockerrun-p:redislabs/rebloom#运行容器redis-cli#连接容器中的redis服务

如果上面三条指令执行没有问题，下面就可以体验布隆过滤器了。

当然，如果你不想使用Docker，也可以在检查本机Redis版本合格之后自行安装插件，可以参考这里:

转载请注明:http://www.aideyishus.com/lktp/85.html