楔子
我们前面介绍过 HyperLogLog 可以用来做基数统计，但它统计的是总数量，而无法判断某个指定的值是否存在。那我们如果想在海量数据之中检索某个值存在与否，该怎么做呢？
因为是海量数据，所以我们不可能将每个键值都存起来，然后再从结果中检索数据。我们只能依靠专门处理此问题的特殊方法来实现数据的查找，而它就是我们今天的主角：布隆过滤器。
布隆过滤器实现原理
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的，它实际上是一个很长的二进制向量和一系列随机映射函数，可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。也就是说布隆过滤器的优点就是计算和查询速度很快，但是缺点也很明显，会存在一定的误差。
假设现在要存储一个键值对，但是布隆过滤器不会真的存储具体的数据，那样就太占空间了。它是利用几个不同的无偏哈希函数，把此元素的 hash 值均匀地映射在位数组中。
通过哈希函数对 key 进行运算，然后再对数组的长度取模，即可得到一个索引，然后将数组中该索引对应的元素设置为 1 即可。并且由于存在冲突，比如 key1 和 key2 映射到同一个槽，所以我们会选择多个哈希函数，毕竟多个哈希函数同时冲突的概率还是很低的。
也就是说，每次添加时会通过几个无偏哈希函数算出它的一些位置，把这些位置设置成 1 就完成了添加操作。
当判断元素存在与否时，查询此元素的几个哈希位置上的值是否为 1，如果全部为 1，则表示此值存在，只要有一个不为 1，则表示不存在。
比如 key2 在映射的时候，发现第一个哈希槽的元素是 1，而后两个哈希槽的元素是 0。说明 key2 是不存在的，第一个槽之所以为 1，是因为其它的 key 碰巧也映射到了这个槽。所以我们才选择多个哈希函数（无偏），为的就是减少哈希的随机性带来的误差，只有全部为 1，key 才存在，而有一个不是 1，那么 key 就不存在。
但很明显，当位数组存储的值比较稀疏的时候，查询的准确率会很高；而当位数组存储的值越来越多时，误差也会增大。比如某个 key 不存在，但它映射出的多个哈希槽里面的元素都是 1，这种情况是有可能发生的，而此时也说明布隆过滤器已经存储了非常多的数据。
因此可以得出结论：布隆过滤器判断某个 key 存在时，此 key 不一定存在；但判断某个 key 不存在时，此 key 一定不存在。
所以布隆过滤器和 Redis Hash 类型的实现原理是一样的，只不过 Redis Hash 的每个哈希槽存的是 *dictEntry，而布隆过滤器的每个哈希槽存的是 1 或 0。以及布隆过滤器在映射的时候会使用多个哈希函数（以减少冲突），而 Hash 类型只用一个哈希函数。
最后还有一个重点，布隆过滤器使用的数组是位数组，也就是说数组里面的每个元素存的是 bit 位，因为 1 和 0 只用一个 bit 位就能保存。但现代计算机操作的最小单位是字节，所以在实际使用数组的时候，我们会基于位运算，将里面的一个元素当成多个元素来用。
比如 int64 类型的数组，里面有 10 个元素，每个元素 8 字节、也就是 64 个 bit 位，那么我们会把它看成是一个长度为 64 * 10 的位数组。如果类型是 int16，那么就看成是长度为 16 * 10 的位数组。
假设类型是 int64，哈希映射之后的槽是 60，那么就将数组中第一个元素的第 61 个位设置为 1；如果映射之后的槽是 80，就将数组中第二个元素的第 17 个位设置为 1。
所以布隆过滤器除了用到了哈希表，还用到了位图。因为是海量数据，因此数组会很长，并且为了避免哈希冲突，我们会将数组申请的更长一些。因此为了减少内存使用，布隆过滤器还使用了位图的思想。
安装布隆过滤器
在 Redis 中不能直接使用布隆过滤器，但我们可以通过 Redis 4.0 版本之后提供的 modules（扩展模块）方式引入。
1）下载并安装布隆过滤器；
git clone https://github.com/RedisLabsModules/redisbloom.git cd redisbloom make # 编译redisbloom
编译完毕之后，会在主目录生成一个 redisbloom.so 文件。
2）启动 Redis 服务器；
./redis-server redis.conf --loadmodule redisbloom.so
其中 --loadmodule 为加载扩展模块的意思，后面跟的是 redisbloom.so 文件的路径。
或者更简便的做法，还可以使用 Docker。
# 拉取镜像 docker pull redislabs/rebloom # 运行容器 docker run -p 6379:6379 redislabs/rebloom
布隆过滤器的使用
布隆过滤器的命令不是很多，主要包含以下几个：
- bf.add：添加元素；
- bf.exists：判断某个元素是否存在；
- bf.madd：添加多个元素；
- bf.mexists：判断多个元素是否存在；
- bf.reserve：设置布隆过滤器的准确率；
下面举例说明。
1）添加元素
127.0.0.1:6379> bf.add user satori (integer) 1 127.0.0.1:6379> bf.add user koishi (integer) 1 127.0.0.1:6379> bf.add user marisa (integer) 1
2）判断元素是否存在
127.0.0.1:6379> bf.exists user satori (integer) 1 127.0.0.1:6379> bf.exists user satori1 (integer) 0
3）添加多个元素
127.0.0.1:6379> bf.madd user n1 n2 n3 1) (integer) 1 2) (integer) 1 3) (integer) 1
4）判断多个元素是否存在
127.0.0.1:6379> bf.mexists user n1 n2 n33 1) (integer) 1 2) (integer) 1 3) (integer) 0
可以看出以上结果没有任何误差，然后还有一个布隆过滤器的准确率，不过在介绍它之前，我们先使用 Python 操作一下 Redis 的布隆过滤器。
我们之前使用Python操作Redis使用第三方模块也叫redis，但是对于布隆过滤器来说，这个模块是不支持的。我们需要使用另一个第三方模块：redisbloom，直接 pip install redisbloom 安装即可。
其实 redisbloom 底层还是使用了我们之前的 redis 模块。
# 我们之前创建连接使用的是 redis.Redis # 而这个 Client 继承自 Redis from redisbloom.client import Client # 所以我们之前的一些操作，这里都可以用 client = Client(host="...", decode_responses="utf-8") # 添加单个元素 client.bfAdd("girl", "satori") # 添加多个元素 client.bfMAdd("girl", "koishi", "marisa") # 判断单个元素是否存在 print(client.bfExists("girl", "satori")) # 1 # 判断多个元素是否存在 print( client.bfMExists("girl", "satori", "koishi", "marisa", "xxx") ) # [1, 1, 1, 0]
最后是设置布隆过滤器的准确率：
# 对于一个已经存在的key，不可以使用bf.reserve 127.0.0.1:6379> bf.reserve user 0.01 200 (error) ERR item exists 127.0.0.1:6379> bf.reserve user1 0.01 200 OK
key 后面的两个值分别表示：error_rate、initial_size。
- error_rate：允许布隆过滤器的错误率，这个值越低，过滤器占用的空间也就越大，因为此值决定了位数组的大小。位数组是用来存储结果的，它的空间占用的越大（能存储的信息越多），错误率就越低，它的默认值是 0.01；
- initial_size：布隆过滤器能容纳的元素个数，实际存储的值大于此值，准确率就会降低，它的默认值是 100；
那么布隆过滤器一般都用在什么场景中呢？
- 垃圾邮件过滤；
- 爬虫里的 URL 去重；
- 判断一个值在亿级数据中是否存在；
布隆过滤器在数据库领域的使用也比较广泛，例如：HBase, Cassandra, LevelDB, RocksDB 内部都有使用布隆过滤器。对于布隆过滤器而言，数据量增大到一定程度之后误差也会随之增大。
小结
通过本文我们知道可以使用 Redis 4.0 之后提供的 modules 方式来开启布隆过滤器，并学习了布隆过滤器的几个重要操作方法。其中比较关键的是 bf.reserve，它有 2 个重要的参数：错误率和数组大小，错误率设置的越低，数组设置的越大，需要存储的空间就越大，相对来说查询的错误率也越低。具体需要如何设置，需要使用者根据实际情况进行调整。
另外布隆过滤器有一个最大的特点：当它查询有数据时，此数据不一定真的存在，当它查询没有此数据时，此数据一定不存在。
