文章目录
一、写在前面
官方中文文档：https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/bloom-filter/
布隆过滤器的概念就不重复啰嗦了（数据不存在则一定不存在，数据存在不一定不存在）。
redis8.0以前使用布隆过滤器是很麻烦的，基本上需要基于BitMap/BitSet自定义封装。
Redis8.0将布隆过滤器功能内置了，使用redis客户端可以直接使用布隆过滤器了。
二、使用
1、BF.RESERVE 创建布隆过滤器
# 语法
# error_rate：期望的误报率概率。该比率是一个介于 0 和 1 之间的十进制值。例如，对于期望的误报率 0.1%（千分之一），error_rate 应设置为 0.001。
# capacity：计划添加到过滤器的条目数量。如果您的过滤器允许扩容，添加的项目数量超过此值后，性能将开始下降。实际的下降程度取决于超出限制的多少。性能随 sub-filters 的数量呈线性下降。
#NONSCALING：阻止过滤器在达到初始容量后创建额外的子过滤器。非扩容过滤器所需的内存比其扩容对应物略少。当达到 capacity 时，过滤器将返回错误。
#EXPANSION expansion：当达到 capacity 时，会创建一个额外的子过滤器。新的子过滤器的大小是上一个子过滤器的大小乘以 expansion，指定为一个正整数。
#如果存储在过滤器中的项目数量未知，可以使用大于或等于 2 的 expansion 来减少子过滤器的数量。否则，使用 expansion 1 来减少内存消耗。默认值是 2。
BF.RESERVE key error_rate capacity [EXPANSION expansion] [NONSCALING]
创建一个空的布隆过滤器，其中包含一个子过滤器，用于初始指定容量并具有上限 error_rate。
默认情况下，当达到 capacity 时，过滤器会通过创建额外的子过滤器来自动扩容。新的子过滤器的大小是前一个子过滤器的大小乘以 expansion。
虽然过滤器可以通过创建子过滤器来扩容，但建议预留估计所需的 capacity，因为维护和查询子过滤器需要额外的内存（每个子过滤器使用额外的位和哈希函数）并消耗更多的 CPU 时间，这比创建时具有正确容量的同等过滤器要多。
最优哈希函数数量是 ceil(-ln(error_rate) / ln(2))。
给定期望的 error_rate 和最优哈希函数数量，每项所需的位数是 -ln(error_rate) / ln(2)^2。因此，过滤器所需的总位数是 capacity * -ln(error_rate) / ln(2)^2。
1% 的错误率需要 7 个哈希函数和每项 9.585 位。
0.1% 的错误率需要 10 个哈希函数和每项 14.378 位。
0.01% 的错误率需要 14 个哈希函数和每项 19.170 位。
# 误报率0.01、容量1000的布隆过滤器
127.0.0.1:6379> BF.RESERVE bf 0.01 1000
OK
# 不允许重复创建
127.0.0.1:6379> BF.RESERVE bf 0.01 1000
(error) ERR item exists
# 超出1000个元素后会创建子过滤器，但是性能会降低
127.0.0.1:6379> BF.RESERVE bf_exp 0.01 1000 EXPANSION 2
OK
# 超出1000个上限之后，再添加元素会返回错误
127.0.0.1:6379> BF.RESERVE bf_non 0.01 1000 NONSCALING
OK
2、BF.ADD添加元素
# 语法
# 如果 key 不存在，则创建一个新的 Bloom 过滤器，其错误率、容量和扩展因子使用默认值（详见 三、默认参数）。
BF.ADD key item
# 整型回复 - 其中 "1" 表示项已成功添加，"0" 表示该项已存在于过滤器中（这可能是错误的，有误判率）
# 错误时返回 []（参数无效、key 类型错误等），以及当过滤器已满时也返回 []
127.0.0.1:6379> BF.ADD bf item1
(integer) 1
127.0.0.1:6379> BF.ADD bf item1
(integer) 0
127.0.0.1:6379> BF.ADD bf item2
(integer) 1
3、BF.CARD 获取项目数
# 语法
BF.CARD key
# 示例
127.0.0.1:6379> BF.ADD bf item1
(integer) 1
127.0.0.1:6379> BF.ADD bf item2
(integer) 1
127.0.0.1:6379> BF.CARD bf
(integer) 2
4、BF.EXISTS 检查元素是否存在
# 语法
BF.EXISTS key item
# 示例
# 1表示可能存在（有误判率），0表示不存在或者布隆过滤器不存在
127.0.0.1:6379> BF.EXISTS bf item1
(integer) 1
127.0.0.1:6379> BF.EXISTS bf item3
(integer) 0
127.0.0.1:6379> BF.EXISTS bf1 item3
(integer) 0
5、BF.INFO 查看布隆过滤器信息
# 语法
# CAPACITY
#返回在需要扩展之前，此 Bloom 过滤器可以存储的唯一项的数量（包括已添加的项）。
#SIZE
#返回内存大小：为此 Bloom 过滤器分配的字节数。
#FILTERS
#返回子过滤器的数量。
#ITEMS
#返回添加到此 Bloom 过滤器并检测为唯一项的数量（这些项导致至少一个子过滤器中的至少一个位被设置）。
#EXPANSION
#返回扩展速率。
#未指定可选参数时：返回所有信息字段。
BF.INFO key [CAPACITY | SIZE | FILTERS | ITEMS | EXPANSION]
127.0.0.1:6379> BF.INFO bf
1) Capacity
2) (integer) 1000
3) Size
4) (integer) 1480
5) Number of filters
6) (integer) 1
7) Number of items inserted
8) (integer) 2
9) Expansion rate
10) (integer) 2
6、BF.INSERT 初始化并添加
# 语法
# 如果 key 不存在，则使用指定的错误率、容量和扩展因子创建一个新的布隆过滤器，然后将所有指定的项添加到布隆过滤器中。
#此命令类似于 BF.MADD，不同之处在于可以指定错误率、容量和扩展因子。它是 BF.RESERVE 和 BF.MADD 的便捷组合。
# NOCREATE
#指示如果过滤器不存在，则不应创建它。如果过滤器尚不存在，则返回错误而不是自动创建。这可以在需要严格区分过滤器创建和过滤器添加的场景下使用。同时指定 NOCREATE 和 CAPACITY 或 ERROR 将导致错误。
#CAPACITY capacity
#指定要创建的过滤器的期望 capacity。如果过滤器已存在，则忽略此参数。如果过滤器自动创建且此参数缺失，则使用模块级别的 capacity。有关此值的影响的更多信息，请参阅 BF.RESERVE。
#ERROR error
#指定新创建的过滤器的错误率 error（如果过滤器尚不存在）。如果过滤器自动创建且未指定 error，则使用模块级别的错误率。有关此值格式的更多信息，请参阅 BF.RESERVE。
#NONSCALING
#阻止过滤器在达到初始容量时创建额外的子过滤器。非扩展过滤器比其扩展版本所需的内存略少。当达到 capacity 时，过滤器将返回错误。
#EXPANSION expansion
#当达到 capacity 时，会创建一个额外的子过滤器。新子过滤器的大小是上一个子过滤器的大小乘以 expansion，以正整数指定。
#如果要存储在过滤器中的元素数量未知，请使用 expansion 为 2 或更大的值以减少子过滤器的数量。否则，使用 expansion 为 1 以减少内存消耗。默认值为 2。
BF.INSERT key [CAPACITY capacity] [ERROR error] [EXPANSION expansion] [NOCREATE] [NONSCALING] ITEMS item [item ...]
#向过滤器添加三个项，如果过滤器尚不存在，则使用默认参数创建过滤器。
BF.INSERT filter ITEMS foo bar baz
#向过滤器添加一个项，如果过滤器尚不存在，则创建一个容量为 10000 的过滤器。
BF.INSERT filter CAPACITY 10000 ITEMS hello
#向过滤器添加两个项，如果过滤器尚不存在，则返回错误。
BF.INSERT filter NOCREATE ITEMS foo bar
7、BF.SCANDUMP 保存布隆过滤器
开始对 Bloom 过滤器进行增量保存。
此命令对于无法适应 DUMP 和 RESTORE 模型的大型 Bloom 过滤器非常有用。
第一次调用此命令时，iter 的值应为 0。
此命令返回连续的 (iter, data) 对，直到返回 (0, NULL) 表示完成。
# 语法
# iterator：迭代器值；要么是 0，要么是之前调用此命令时返回的迭代器
BF.SCANDUMP key iterator
redis> BF.RESERVE bf 0.1 10
OK
redis> BF.ADD bf item1
1) (integer) 1
redis> BF.SCANDUMP bf 0
1) (integer) 1
2) "\x01\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\b\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x9a\x99\x99\x99\x99\x99\xa9?J\xf7\xd4\x9e\xde\xf0\x18@\x05\x00\x00\x00\n\x00\x00\x00\x00\x00\x00\x00\x00"
redis> BF.SCANDUMP bf 1
1) (integer) 9
2) "\x01\b\x00\x80\x00\x04 \x00"
redis> BF.SCANDUMP bf 9
1) (integer) 0
2) ""
redis> DEL bf
(integer) 1
redis> BF.LOADCHUNK bf 1 "\x01\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\b\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x9a\x99\x99\x99\x99\x99\xa9?J\xf7\xd4\x9e\xde\xf0\x18@\x05\x00\x00\x00\n\x00\x00\x00\x00\x00\x00\x00\x00"
OK
redis> BF.LOADCHUNK bf 9 "\x01\b\x00\x80\x00\x04 \x00"
OK
redis> BF.EXISTS bf item1
(integer) 1
# python代码
chunks = []
iter = 0
while True:
iter, data = BF.SCANDUMP(key, iter)
if iter == 0:
break
else:
chunks.append([iter, data])
# Load it back
for chunk in chunks:
iter, data = chunk
BF.LOADCHUNK(key, iter, data)
8、BF.LOADCHUNK 恢复布隆过滤器
# 语法
#iterator：与 data 关联的迭代器值（由 BF.SCANDUMP 返回）
#data：当前数据块（由 BF.SCANDUMP 返回）
BF.LOADCHUNK key iterator data
9、BF.MADD 批量添加
# 语法
BF.MADD key item [item ...]
# 示例
redis> BF.MADD bf item1 item2 item2
1) (integer) 1
2) (integer) 1
3) (integer) 0
10、BF.MEXISTS 批量判断存在
# 语法
BF.MEXISTS key item [item ...]
# 示例
redis> BF.MADD bf item1 item2
1) (integer) 1
2) (integer) 1
redis> BF.MEXISTS bf item1 item2 item3
1) (integer) 1
2) (integer) 1
3) (integer) 0
三、默认参数
1、bf-error-rate
布隆过滤器的默认误报率。
类型：双精度浮点数
有效范围：(0 … 1)。虽然有效范围是 (0 … 1)（对应于 > 0% 到 < 100% 的误报率），但任何大于 0.25 的值都将被视为 0.25。
默认值：0.01
2、bf-expansion-factor
在 v8.0.0 中添加。
布隆过滤器的扩展因子。
类型：整数
有效范围：[0 … 32768]。
默认值：2
3、bf-initial-size
布隆过滤器的初始容量。
类型：整数
有效范围：[1 … 1048576]
默认值：100