Redis实现布隆过滤器（上）

什么是布隆过滤器

布隆过滤器底层就是由一个全是0的bit数组和N个哈希函数构成，当我们在布隆过滤器中标记某个值存在时，一般分为如下步骤

• 使用N个哈希函数，分别计算其哈希值。

• 将N个哈希值对bit数组的长度取模，得到存放的数组下标。

• 将得到的多个数组下标的值置为1。

上图存在3个哈希函数，也就是每次需要标记三个位置的值才能确定一个值是否存在，当我们需要依靠布隆过滤器确定值是否存在时我们只需要确定多个哈希值对应的数组下标是否全部为1，只要有一个为0那么值肯定不在数据库中，全部为1那么该值可能存在数据库中。

布隆过滤器为什么会存在一定的误判率呢？其主要原因还是因为哈希冲突，数组长度有限那么不同的值可能会映射到相同的位置上，所以降低误判的方法一般是增加哈希函数或者扩大bit数组的长度，这样做确实能降低误判率，但也带来一个问题那就是哈希函数的增加将影响计算性能，扩大内存会更加占用空间，所以我们在使用布隆过滤器时需要在性能、内存、误判率上面做取舍。

另外布隆过滤器一般不支持删除操作，因为删除值意味着需要将多个数组下标的值置为0，而这些数组下标并不是只有当前值使用，可能会和多个值共用某个数组下标，删除起来及其复杂，所以一般不支持删除操作。

Redis在4.0版本开始支持插件机制官网参考https://redis.com/redis-enterprise-software/download-center/modules/，布隆过滤器正式登场。

如果是4.0之前的版本那么只能依赖第三方库实现布隆过滤器如guava，Redis布隆过滤器官网介绍地址https://redis.io/docs/stack/bloom/

==注意：后面演示的Redis版本为6.0.6==

Redis布隆过滤器编译

布隆过滤器下载地址https://github.com/RedisBloom/RedisBloom/releases

本打算采用v2.2.15最新版本，但是下载后make编译报文件缺失

网上也没好的解决方案，所以我将版本降低至v2.2.14成功编译

官网教程中强调生成文件redisbloom.so表示手动编译成功

Redis集成布隆过滤器

修改redis.conf文件，让Redis在启动的时候加载布隆过滤器

### 这个路径就是上面make编译布隆过滤器生成的redisbloom.so文件的绝对路径
loadmodule /opt/redis/RedisBloom-2.2.14/redisbloom.so

1
2
3

保存退出，重启Redis的服务，如果是集群那么每个实例的redis.conf文件都需要修改。

布隆过滤器简单使用

布隆过滤器命令集合查询地址https://redis.io/commands/?name=bf.&group=bf

BF.ADD和BF.MADD

向布隆过滤器中添加元素

### 向布隆过滤器中添加元素，返回值为1添加成功，为0添加失败
### 如果不存在users名字的过滤器，系统会生成默认容量100，生成子过滤器的容量倍数默认2
127.0.0.1:6379> bf.add users 1001
(integer) 1
127.0.0.1:6379> bf.add users 1002
(integer) 1
### 相同元素添加会失败
127.0.0.1:6379> bf.add users 1001
(integer) 0
### 批量添加
127.0.0.1:6379> bf.madd users 1003 1004
1) (integer) 1
2) (integer) 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BF.EXISTS和BF.MEXISTS

### 检验值是否存在，存在返回1，不存在返回0
127.0.0.1:6379> BF.EXISTS users 1001
(integer) 1
127.0.0.1:6379> BF.EXISTS users 1003
(integer) 0
### 批量校验
127.0.0.1:6379> bf.mexists users 1001 1002 1003
1) (integer) 1
2) (integer) 1
3) (integer) 1

1
2
3
4
5
6
7
8
9
10
11

BF.INFO

### 检测布隆过滤器的基本信息
127.0.0.1:6379> bf.info users
 1) Capacity ### 布隆过滤器容量
 2) (integer) 1000
 3) Size 
 4) (integer) 936
 5) Number of filters ### 布隆过滤器数量，可能存在子过滤器
 6) (integer) 1
 7) Number of items inserted ### 布隆过滤器中添加的元素个数
 8) (integer) 4
 9) Expansion rate 
 ### 当Number of items inserted达到Capacity值后再往过滤器中添加元素，
 ### 生成子过滤器容量的倍数，子过滤器容量=现有容量Capacity*Expansion rate（默认2）
10) (integer) 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BF.RESERVE

### 创建一个过滤器 
### 格式 BF.RESERVE key error_rate capacity [expansion] [NONSCALING]
### error_rate：错误率    capacity：容量
### expansion：当容量达到capacity后，需要创建额外的子过滤器，容量是现有的容量*expansion（默认是2）
### NONSCALING：当容量达到capacity后，不创建子过滤器，报错（默认会创建子过滤器）
127.0.0.1:6379> BF.RESERVE users 0.1 1000
OK

1
2
3
4
5
6
7
8

当使用默认参数时

##############测试创建一个过滤器，全部使用默认容量和默认创建子过滤器，初始容量为5#############
127.0.0.1:6379> BF.RESERVE test 0.01 5
OK
### 批量加入4个值
127.0.0.1:6379> BF.MADD test 1001 1002 1003 1004
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
### 哈希冲突，布隆过滤器认为在bit数组中已经存在，所以添加未生效
127.0.0.1:6379> bf.add test 1005
(integer) 0
127.0.0.1:6379> bf.info test
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 160
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted ### 布隆过滤器中只有四个值，容量是五个
 8) (integer) 4
 9) Expansion rate
10) (integer) 2
### 布隆过滤器中添加成功这时布隆过滤器中有五个值
127.0.0.1:6379> bf.add test 1006 
(integer) 1
### 布隆过滤器中包含的元素等于定义的容量时，还不会触发添加子过滤器，需要再往布隆过滤器中添加
127.0.0.1:6379> bf.info test
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 160
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 5
 9) Expansion rate
10) (integer) 2
### 添加成功
127.0.0.1:6379> bf.add test 1007
(integer) 1
127.0.0.1:6379> bf.info test
 1) Capacity
 2) (integer) 15  ### 总容量由5变为15计算公式为  Capacity + Capacity*Expansion rate
 3) Size
 4) (integer) 296
 5) Number of filters ### 添加了一个子过滤器
 6) (integer) 2
 7) Number of items inserted
 8) (integer) 6
 9) Expansion rate ### 可以在添加自定义过滤器时设置，默认为2
10) (integer) 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

证明了在默认情况下，布隆过滤器中添加元素个数达到设置的初始容量Capacity后，并不会马上生成子过滤器，而需要再次往布隆过滤器中添加数据时，才会触发新增子过滤器，子过滤器的容量计算就是Capacity*expansion，expansion不设置默认是2。

当设置不新增子过滤器时

#### 在自定义过滤器规则时添加 NONSCALING 参数，表示布隆过滤器中的元素个数达到capacity后
#### 再往布隆过滤器中添加元素会报错
127.0.0.1:6379> BF.RESERVE test2 0.01 5 NONSCALING
OK
#### 只成功了四个，1005因为哈希冲突没有添加成功
127.0.0.1:6379> bf.madd test2 1001 1002 1003 1004 1005
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 0
127.0.0.1:6379> bf.add test2 1006
(integer) 1
127.0.0.1:6379> bf.add test2 1007
(error) ERR non scaling filter is full

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

当设置扩容倍数

#### 在自定义布隆过滤器时，指定生成子过滤器的扩容大小为3
127.0.0.1:6379> BF.RESERVE test 0.01 5 EXPANSION 3
OK
127.0.0.1:6379> bf.madd test 1001 1002 1003 1004 1006
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
127.0.0.1:6379> bf.info test
 1) Capacity
 2) (integer) 5  ### 已添加元素等于capacity但还未生成子过滤器
 3) Size
 4) (integer) 160
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 5
 9) Expansion rate  ### 子过滤器的扩容大小从默认的2变为指定大小
10) (integer) 3
127.0.0.1:6379>
127.0.0.1:6379> bf.add test 1007
(integer) 1
127.0.0.1:6379> bf.info test
 1) Capacity
 2) (integer) 20  ### 已生成子过滤器
 3) Size
 4) (integer) 304
 5) Number of filters
 6) (integer) 2
 7) Number of items inserted
 8) (integer) 6
 9) Expansion rate
10) (integer) 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

BF.INSERT

BF.INSERT官网是这么介绍的

BF.INSERT is a sugarcoated combination of BF.RESERVE and BF.ADD. It creates a new filter if the key does not exist using the relevant arguments (see BF.RESERVE)

BF.INSERT是BF.RESERVE和BF.ADD的组合。如果“key”（布隆过滤器名字）不存在，它会使用相关参数创建一个新的过滤器

### 命令 BF.INSERT key [capacity] [error] [expansion] [NOCREATE] [NONSCALING] ITEMS item [item ...]
### NOCREATE：表示如果key不存在不会自动创建布隆过滤器，那么NOCREATE和capacity混用就会报错
127.0.0.1:6379> BF.INSERT test1 capacity 10 error 0.01 expansion 6 items 1001
1) (integer) 1
127.0.0.1:6379> 
127.0.0.1:6379> bf.info test1
 1) Capacity
 2) (integer) 10
 3) Size
 4) (integer) 168
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 1
 9) Expansion rate
10) (integer) 6
### 指定NOCREATE，当test2不存在时，报错
127.0.0.1:6379> BF.INSERT test2 capacity 10 error 0.01 expansion 6 NOCREATE items 1005
(error) ERR not found

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

BF.SCANDUMP

用于对布隆过滤器的增量保存，这适用于不能正常保存和恢复的大型布隆过滤器，第一次调用此命令时，iter的值应为 0。此命令返回连续(iter, data)对，直到(0, NULL)指示完成。

命令格式：BF.SCANDUMP  {key布隆过滤器名称}  {iter第一次调用是0，后续是前面调用此命令的iter}

### 新增布隆过滤器test 放入两个元素
127.0.0.1:6379> bf.madd test 1001 1002
1) (integer) 1
2) (integer) 1
### 校验值是否存在
127.0.0.1:6379> BF.MEXISTS test 1001 1002 1003
1) (integer) 1
2) (integer) 1
3) (integer) 0
### 布隆过滤器的增量保存，第一次从0开始
127.0.0.1:6379> BF.SCANDUMP test 0
### 返回参数iter
1) (integer) 1
### 返回参数data
2) "\x02\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\x90\x00\x00\x00\x00\x00\x00\x00\x80\x04\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00{\x14\xaeG\xe1zt?\xe9\x86/\xb25\x0e&@\b\x00\x00\x00d\x00\x00\x00\x00\x00\x00\x00\x00"
### 1就是上一次BF.SCANDUMP返回值的iter
127.0.0.1:6379> BF.SCANDUMP test 1
1) (integer) 145
2) "@\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\b\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x10\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
### 返回值iter=0，data为"" 标识着增量保存结束
127.0.0.1:6379> BF.SCANDUMP test 145
1) (integer) 0
2) ""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

BF.LOADCHUNK

加载增量保存的布隆过滤器数据

命令格式：BF.LOADCHUNK {key布隆过滤器名称} {iter} {data}，其中iter和data是每次执行BF.SCANDUMP返回的结果值

### 加载前可以先清空，保证后续验证的元素是从BF.SCANDUMP保存的数据来的
127.0.0.1:6379> FLUSHALL
OK
127.0.0.1:6379> BF.MEXISTS test 1001 1002 1003
1) (integer) 0
2) (integer) 0
3) (integer) 0
### 加载的iter值和data值必须一一对应，如果不对应直接报错
127.0.0.1:6379> BF.LOADCHUNK test 1 "\x02\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\x90\x00\x00\x00\x00\x00\x00\x00\x80\x04\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00{\x14\xaeG\xe1zt?\xe9\x86/\xb25\x0e&@\b\x00\x00\x00d\x00\x00\x00\x00\x00\x00\x00\x00"
OK

127.0.0.1:6379> BF.MEXISTS test 1001 1002 1003
1) (integer) 1
2) (integer) 1
3) (integer) 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16