什么是『布隆过滤器』
布隆过滤器是一个神奇的数据结构，可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求：目标网站 URL 千千万，怎么判断某个 URL 爬虫是否宠幸过？简单点可以爬虫每采集过一个 URL，就把这个 URL 存入数据库中，每次一个新的 URL 过来就到数据库查询下是否访问过。
select id from table where url = 'https://jaychen.cc'
但是随着爬虫爬过的 URL 越来越多，每次请求前都要访问数据库一次，并且对于这种字符串的 SQL 查询效率并不高。除了数据库之外，使用 Redis 的 set 结构也可以满足这个需求，并且性能优于数据库。但是 Redis 也存在一个问题：耗费过多的内存。这个时候布隆过滤器就很横的出场了：这个问题让我来。
相比于数据库和 Redis，使用布隆过滤器可以很好的避免性能和内存占用的问题。
布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 B 的空间。布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
- 根据得到的哈希值，在位数组中把对应下标的值置为 1。
举个🌰，假设布隆过滤器有 3 个哈希函数：f1, f2, f3 和一个位数组 arr。现在要把 https://jaychen.cc 插入布隆过滤器中：
- 对值进行三次哈希计算，得到三个值 n1, n2, n3。
- 把位数组中三个元素 arr[n1], arr[n2], arr[3] 置为 1。
当要判断一个值是否在布隆过滤器中，对元素再次进行哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
看不懂文字看下面的灵魂画手的图解释👇👇👇
看了上面的说明，必然会提出一个问题：当插入的元素原来越多，位数组中被置为 1 的位置就越多，当一个不在布隆过滤器中的元素，经过哈希计算之后，得到的值在位数组中查询，有可能这些位置也都被置为 1。这样一个不存在布隆过滤器中的也有可能被误判成在布隆过滤器中。但是如果布隆过滤器判断说一个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。简单来说：
- 布隆过滤器说某个元素在，可能会被误判。
- 布隆过滤器说某个元素不在，那么一定不在。
这个布隆过滤器的缺陷放到上面爬虫的需求中，可能存在某些没有访问过的 URL 可能会被误判为访问过，但是如果是访问过的 URL 一定不会被误判为没访问过。
Redis 中的布隆过滤器
redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
redis 布隆过滤器主要命令：
- BF.RESERVE <key> <error_rate> <capacity> 创建一个大小为capacity，错误率为error_rate的空的TairBloom。
- BF.ADD <key> <item> 在key指定的TairBloom中添加一个元素item。bf.add urls test1url。
- BF.MADD <key> <item> [item...] 在key指定的TairBloom中一次性添加多个元素。
- BF.EXISTS <key> <item> 检查一个元素是否存在于key指定的TairBloom中。bf.exists urls test1url。
- BF.MEXISTS <key> <item> [item...] 同时检查多个元素是否存在于key指定的TairBloom中。
- BF.DEBUG <key> 可以查看key指定的TairBloom内部信息，如当前层数和每一层的元素个数、错误率等。
- DEL <key> [key ...] 使用原生Redis的DEL命令可以删除一条或多条TairBloom数据。
- BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item...> 在key指定的TairBloom中一次性添加多个元素，添加时可以指定大小和错误率，且可以控制在TairBloom不存在的时候是否自动创建。
注意：
已加入TairBloom数据中的元素无法单独删除，您可以使用DEL命令删除整条TairBloom数据。
BF.RESERVE
语法
BF.RESERVE <key> <error_rate> <capacity>时间复杂度：O(1)
命令描述：创建一个大小为capacity，错误率为error_rate的空的TairBloom。
-
参数及选项说明
- key : TairBloom的key，用于指定作为命令调用对象的TairBloom。
- error_rate : 期望的错误率（False Positive Rate），该值必须介于0和1之间。该值越小，TairBloom的内存占用量越大，CPU使用率越高。
- capacity : TairBloom的初始容量，即期望添加到TairBloom中的元素的个数。
当实际添加的元素个数超过该值时，TairBloom将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降的，这是因为TairBloom的扩容是通过增加Bloom Filter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层Bloom Filter来完成，每一层的容量都是上一层的两倍。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生扩容操作。
返回值
成功：OK。
其它情况返回相应的异常信息。注意
使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：
BF.ADD
语法： BF.ADD <key> <item>
时间复杂度： O(log N) ，其中N是TairBloom的层数。
命令描述： 在key指定的TairBloom中添加一个元素。
-
参数及选项说明
- key TairBloom的key，用于指定作为命令调用对象的TairBloom。
- item 需要添加到TairBloom的元素。
返回值
元素一定不存在：1。
元素可能已经存在：0。
其它情况返回相应的异常信息。
BF.MADD
语法：BF.MADD <key> <item> [item...]
时间复杂度： O(log N) ，其中N是TairBloom的层数。
命令描述： 在key指定的TairBloom中添加多个元素。
-
参数及选项说明
- key TairBloom的key，用于指定作为命令调用对象的TairBloom。
- item 需要添加到TairBloom的元素，可设置多个。
返回值
成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为1，当item可能已经存在时数组元素值为0。
其它情况返回相应的异常信息。
BF.EXISTS
语法： BF.EXISTS <key> <item>
时间复杂度：O(log N) ，其中N是TairBloom的层数。
命令描述：检查一个元素是否存在于key指定的TairBloom中。
-
参数及选项说明
- key TairBloom的key，用于指定作为命令调用对象的TairBloom。
- item 需要查询的元素。
返回值
元素一定不存在：0。
元素可能存在：1。
其它情况返回相应的异常信息。
BF.MEXISTS
语法：BF.MEXISTS <key> <item> [item...]
时间复杂度：O(log N) ，其中N是TairBloom的层数。
命令描述：同时检查多个元素是否存在于key指定的TairBloom中。
-
参数及选项说明
- key TairBloom的key，用于指定作为命令调用对象的TairBloom。
- item 需要查询的元素，可设置多个。
返回值
成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为0，当item可能已经存在时数组元素值为1。
其它情况返回相应的异常信息。
BF.INSERT
语法：BF.INSERT <key> [CAPACITY cap] [ERROR error] [NOCREATE] ITEMS <item...>
时间复杂度：O(log N) ，其中N是TairBloom的层数。
命令描述：在key指定的TairBloom中一次性添加多个元素，添加时可以指定大小和错误率，且可以控制在TairBloom不存在的时候是否自动创建。
-
参数及选项说明
key TairBloom的key，用于指定作为命令调用对象的TairBloom。
CAPACITY 指定TairBloom的容量，即期望添加到TairBloom中的元素的个数，当TairBloom已经存在时该值将被忽略。
当实际添加的元素个数超过该值时，TairBloom将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降的，这是因为TairBloom的扩容是通过增加Bloom Filter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层Bloom Filter来完成，每一层的容量都是上一层的两倍。因此，如果对性能非常的敏感，需要在使用前充分评估要添加到TairBloom的元素个数，避免发生扩容操作。
ERROR 期望的错误率（False Positive Rate），当TairBloom已经存在时该值将被忽略。该值必须介于0和1之间。该值越小，TairBloom的内存占用量越大，CPU使用率越高。
NOCREATE 设置该选项后，当指定的TairBloom不存在的时候不要自动创建该TairBloom。该参数不能与CAPACITY和ERROR同时设置。ITEMS 需要添加到TairBloom中的所有元素。
返回值：
成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素为1，当item可能已经存在时数组元素值为0。
其它情况返回相应的异常信息。
BF.DEBUG
语法：BF.DEBUG <key>
时间复杂度：O(log N) ，其中N是TairBloom的层数。
命令描述：可以查看key指定的TairBloom内部信息，如当前层数和每一层的元素个数、错误率等。
-
参数及选项说明
- key TairBloom的key，用于指定作为命令调用对象的TairBloom。
返回值
成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素为1，当item可能已经存在时数组元素值为0。
其它情况返回相应的异常信息。
内存占用测试结果
版本要求:
- redis 在 4.0 以及以上版本
转载地址 : https://help.aliyun.com/document_detail/145972.html?spm=5176.11065259.1996646101.searchclickresult.4f0e72c25d0D88#section-9lv-mn2-z93
