Redis的中BitMap的应用

一、应用场景

通常用于构建布隆过滤器

业务场景需要频繁的查询数据库里的数据，但是这些数据又不一定都存在，一些大量无效的数据库请求，占用了数据库的链接。

本质上保护数据库，减少无用的请求。

解决：

1、把查询的数据key放入redis Set中，只有存在才会去查询，问题就是set过于大，检查是否存在也会变慢

2、当库中不存在该值时，依然创建一个value设置为空值，等过期时间后，自行删除。有可能上一秒库中不存在，下一秒有了，拿走依然是空值，也不行。

3、布隆过滤器

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢。上述三种结构的检索时间复杂度分别为：

• O(n)：链表
• O(logn)：树
• O(1)：哈希表

这个时候，布隆过滤器（Bloom Filter）就应运而生。

1.1. 原理

当一个元素被加入集合时，通过N个Hash函数将这个元素进行Hash，算出一个整数索引值，然后对数组长度进行取模运算，从而得到一个位置，每个Hash函数都会得到一个不同的位置，然后再把位数组中的几个位置点都置为1。

检索时，也会把哈希的几个位置算出来，然后看看位数组中对应的几个位置是否都为1，只要有一个位为0，那么就说明布隆过滤器里不存在这个元素。

但是，这几个位置都为1，并不能完全说明这个元素就一定存在其中。因为散列函数是会有碰撞的，不同的输入，可能在哈希后为同一个位置。即有可能这些位置为1是因为其他元素的存在，这就是布隆过滤器会出现误判的原因。

因此查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

• 如果这些点有任何一个 0
• 如果都是 1，则被查询变量很可能存在。

1.2 特性与优缺点

1. 不存在时一定不存在

一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。

原因：布隆过滤器的误判是指多个输入经过哈希之后，在相同的bit位的值置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

2. 只增不删

布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

原因：上述原因中的情况，多个输入经过哈希之后，在相同的bit位的值置1了，也造成了布隆过滤器的删除问题。因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

如果需要删除一批元素，可以考虑重新初始化一个布隆过滤器，替换原来的。

3. 优点

• 占用空间极小，插入和查询速度极快；
• 布隆过滤器可以表示全集，其它任何数据结构都不能；

3. 缺点

• 误算率随着元素的增加而增加；
• 一般情况下无法删除元素；

1.3 应用场景

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

1. 大数据判断是否存在来实现去重

这就可以实现出上述的去重功能，如果你的服务器内存足够大的话，那么使用 HashMap 可能是一个不错的解决方案，理论上时间复杂度可以达到 O(1) 的级别，但是当数据量起来之后，还是只能考虑布隆过滤器。

2. 判断用户是否访问过

判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。

3. 爬虫/邮箱等系统的过滤

平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中，这就是使用布隆过滤器误判导致的。

4. 天然适合缓存穿透场景

布隆过滤器天然就能应对缓存穿透的场景。

首先，布隆过滤器的应用策略正好和缓存是相反的：

• 缓存策略：缓存中不存在的，再去查db。
• 布隆过滤器策略：过滤器中存在的，再去查缓存（db）。

然后，由于它的特性：一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。

这表明它的误判率并不影响它的策略：

• 当判断结果为存在时：不一定存在。带来的不好的结果，顶多就是多查一次缓存。
• 当判断结果为不存在时：一定不存在。策略中判断不存在时，当前请求就会被拦截，这方面是没有误判的。

所以说，布隆过滤器天然适合缓存穿透的场景，它的误判率对与该场景没有丝毫影响。

1.4 实现

有很多布隆过滤器的实现，就如同之前将限流器的实现有 guava 和 redisson，布隆过滤器的实现也一样。

下面两种实现方式十分相似，都会初始化两个参数：

• 初始容量：当实际元素的数量超过这个初始化容量时，误判率上升。设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。
• 期望错误率：期望错误率越低，需要的空间就越大。错误率越小，需要的存储空间就越大，对于不需要过于精确的场景，错误率设置稍大一点也可以。

参考文献：https://segmentfault.com/a/1190000043505315