【Redis】谈谈我对Redis布隆过滤器的理解

什么是布隆过滤器

• 布隆过滤器是一种占用空间很小的数据结构（位图）也可以理解为数组，用于检索一个元素是否在一个集合中；
• 空间效率和查询时间都比一般的算法要好的多，缺点是有一定的错误识别率和删除困难；

什么是位图

• 是一个有序的数组，只有两个值（0 和 1）；
• 0-代表不存在，1-代表存在；

举例

上面有说过，布隆过滤器的主要作用为：检索一个元素是否在一个集合；

举一个比较典型的例子：

• 如果你的网站被爬虫爬取了，而且这个爬虫还会经常切换ip，那么你就要获取到爬虫的ip，之后加入黑名单，等到爬虫再次访问时，服务就会拒绝响应；
• 那么这么多的ip，需要放在哪里呢？总不能放在数据库吧，这样每次都要请求数据库去查询数据，是很不明智的；
• 所以，使用布隆过滤器来存放ip是个不错的选择；

这里我只是举一个个例，同样的，布隆过滤器也可以解决缓存穿透的问题；

ip黑名单工作逻辑

• 拿黑名单ip的功能举例，假设检测出爬虫ip为：120.254.4.213，现在想将这个ip加入黑名单，那么就要将ip地址进行HASH()；

• 得到的值存放到位图上，此步骤也就是做关系映射，将ip地址映射到位图的位置上；

• 下次可以直接进行查询，如果下次查询得到的位置为1，那么这个ip很有可能在黑名单中（误判），否则，就一定不在黑名单中；

在这里引入一张偷来的图，在数组中为1的，既是某个ip对应的位置（一个ip对应一个位置）

hash冲突

• 在这里会出现一个问题，既然是通过hash算法去得到的值，肯定是会遇到hash碰撞的问题；
• 也许某一个ip并没有在黑名单中，但经过hash()算法之后，恰好对应的位置为1，这时就可以通过多次hash来避免这种情况；

目前Java已经有了很多布隆过滤器相关的开源库，首选Google的Guava库

解决缓存穿透工作逻辑

• 同样的，当客户端请求在redis中没有命中时，会去请求mysql，这逻辑看起来没有任何问题；
• 但当大量不存在的请求过来时，mysql数据库肯定是扛不住的；
• 这时候布隆过滤器就派上用场了，当请求过来时，先经过布隆过滤器，如果显示有数据，则去查询mysql；
• 如果布隆过滤器显示无此数据，则直接返回给前端；
• 这种逻辑就万无一失了

---

从容器的角度来说

• 如果布隆过滤器判断元素在集合中存在，那么不一定存在（学名叫 假阳性）
• 如果布隆过滤器判断不存在，那么就一定不存在