本文共 9205 字，大约阅读时间需要 30 分钟。

1 布隆过滤器介绍

Hash、Set、String的BitMap等可以实现判断元素是否存在的功能，但这些实现方式要么随着元素增多会占用大量内存（Hash、Set），要么无法动态伸缩和保持误判率不变（BitMap）。因此，我们非常需要一种可以高效判断大量数据是否存在且允许一定误判率的数据结构。

1.1 什么是布隆过滤器（Bloom Filter）

布隆过滤器由Burton Howard Bloom于1970年提出，用于判断一个元素是否在集合中。

  布隆过滤器（Bloom filter）是一种非常节省空间的概率数据结构（space-efficient probabilistic data structure），运行速度快（时间效率），占用内存小（空间效率），但是有一定的误判率且无法删除元素。本质上由一个很长的二进制向量和一系列随机映射函数组成。

1.2 布隆过滤器特点

• 一个很长的二进制向量 （位数组）
• 一系列随机函数 (哈希)
• 空间效率和查询效率高
• 有一定的误判率（哈希表是精确匹配）
• 布隆过滤器支持添加元素、检查元素，但是不支持删除元素；
• 检查结果分为2种：一定不在集合中、可能在集合中（误判率问题）；

检查到的结果：

1.元素不存在该集合，就一定不存在该集合 2.元素存在该集合，就不一定是存在（此处是误判率的问题）

1.3 redisbloom 布隆过滤器原理

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k

以上图为例，具体的操作流程：假设集合里面有3个元素{x,y,z},哈希函数的个数为3,。首先将位数组进行初始化，将里面每个位都设置为0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值就对应维数组上面一个点，然后将为位数组对应的位置标记为1。查询W元素是否存在集合宏的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在该集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中看到，假设某个元素通过映射对应下表为4,5,6这3个点。虽然这个3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

总结：redisbloom主要以二进制向量（2进制方式）方式标记元素是否存在于过滤器中，空间效率和查询效率高，允许添加，删除，不支持修改，有一定的误判率；

1.4 布隆过滤器误判率统计

• 如果m代表位向量长度
• n代表需要判断的元素个数
• k代表hash函数个数。
  下表是m与n比值在k个hash函数下面的误判率
  误判率统计：

m/n	k	k=1	k=2	k=3	k=4	k=5	k=6	k=7	k=8
2	1.39	0.393	0.400
3	2.08	0.283	0.237	0.253
4	2.77	0.221	0.155	0.147	0.160
5	3.46	0.181	0.109	0.092	0.092	0.101
6	4.16	0.154	0.0804	0.0609	0.0561	0.0578	0.0638
7	4.85	0.133	0.0618	0.0423	0.0359	0.0347	0.0364
8	5.55	0.118	0.0489	0.0306	0.024	0.0217	0.0216	0.0229
9	6.24	0.105	0.0397	0.0228	0.0166	0.0141	0.0133	0.0135	0.0145
10	6.93	0.0952	0.0329	0.0174	0.0118	0.00943	0.00844	0.00819	0.00846
11	7.62	0.0869	0.0276	0.0136	0.00864	0.0065	0.00552	0.00513	0.00509
12	8.32	0.08	0.0236	0.0108	0.00646	0.00459	0.00371	0.00329	0.00314
13	9.01	0.074	0.0203	0.00875	0.00492	0.00332	0.00255	0.00217	0.00199
14	9.7	0.0689	0.0177	0.00718	0.00381	0.00244	0.00179	0.00146	0.00129
15	10.4	0.0645	0.0156	0.00596	0.003	0.00183	0.00128	0.001	0.000852
16	11.1	0.0606	0.0138	0.005	0.00239	0.00139	0.000935	0.000702	0.000574
17	11.8	0.0571	0.0123	0.00423	0.00193	0.00107	0.000692	0.000499	0.000394
18	12.5	0.054	0.0111	0.00362	0.00158	0.000839	0.000519	0.00036	0.000275
19	13.2	0.0513	0.00998	0.00312	0.0013	0.000663	0.000394	0.000264	0.000194
20	13.9	0.0488	0.00906	0.0027	0.00108	0.00053	0.000303	0.000196	0.00014
21	14.6	0.0465	0.00825	0.00236	0.000905	0.000427	0.000236	0.000147	0.000101
22	15.2	0.0444	0.00755	0.00207	0.000764	0.000347	0.000185	0.000112	7.46e-05
23	15.9	0.0425	0.00694	0.00183	0.000649	0.000285	0.000147	8.56e-05	5.55e-05
24	16.6	0.0408	0.00639	0.00162	0.000555	0.000235	0.000117	6.63e-05	4.17e-05
25	17.3	0.0392	0.00591	0.00145	0.000478	0.000196	9.44e-05	5.18e-05	3.16e-05
26	18	0.0377	0.00548	0.00129	0.000413	0.000164	7.66e-05	4.08e-05	2.42e-05
27	18.7	0.0364	0.0051	0.00116	0.000359	0.000138	6.26e-05	3.24e-05	1.87e-05
28	19.4	0.0351	0.00475	0.00105	0.000314	0.000117	5.15e-05	2.59e-05	1.46e-05
29	20.1	0.0339	0.00444	0.000949	0.000276	9.96e-05	4.26e-05	2.09e-05	1.14e-05
30	20.8	0.0328	0.00416	0.000862	0.000243	8.53e-05	3.55e-05	1.69e-05	9.01e-06
31	21.5	0.0317	0.0039	0.000785	0.000215	7.33e-05	2.97e-05	1.38e-05	7.16e-06
32	22.2	0.0308	0.00367	0.000717	0.000191	6.33e-05	2.5e-05	1.13e-05	5.73e-06

1.5 使用传统数组或hash方式存储数据与redisboom比较：

项目中存储1亿个邮箱，邮箱平均30个字符1.数组，hash占用的空间（utf-8）	1亿（英文字符）	1B字节（一个英文字符占用一个字节）	(1亿*1字节*30字符)=3,000,000,000B / 1024 = 2,929,687.5 KB /1024 = 2,861.02294921875 MB /1024= 2.8 G	占用：2.8 G2. redisbloom占用空间	n (代表需要判断的元素个数)	m (代表位向量长度)	k (代表hash函数个数)	n=1亿	m/n=4	m=4亿	4亿/8b=50,000,000B /1024=48,828.125 KB /1024= 47.6837158203125 MB /1024= 0.04 G	占用空间：0.04 G 总结： 	1.1亿邮箱使用hash或数组存储，占用空间是 2.8 G	2.1亿邮箱使用redisbloom存储，占用空间是0.04G说明：1B（字节 byte）= 8 (位 bit)1KB=1024B1MB=1024KB1GB=1024MB另，哈希表的空间利用率一般只有50%

官方redisboom地址：

https://docs.redislabs.com/latest/modules/redisbloom/ https://oss.redislabs.com/redisbloom/Quick_Start/ https://oss.redislabs.com/redisbloom/#command-references https://docs.redislabs.com/latest/modules/redisbloom/redisbloom-quickstart/?_ga=2.234894149.555262092.1603270995-1549265601.1603270995

2.安装redis

#下载[root@localhost redis]# /root/redis[root@localhost redis]# wget https://download.redis.io/releases/redis-5.0.5.tar.gz#解压安装[root@localhost redis]# tar -zxvf redis-5.0.5.tar.gz[root@localhost redis]# lsredis-5.0.5  redis-5.0.5.tar.gz[root@localhost redis]# cd redis-5.0.5[root@localhost redis-5.0.5]# make

3.下载redisbloom插件

redis官网下载即可

https://github.com/RedisLabsModules/redisbloom/

tag:https://github.com/RedisBloom/RedisBloom/tags

3.1 下载压缩包

[root@localhost redis]# wget https://github.com/RedisBloom/RedisBloom/archive/v2.2.1.tar.gz

3.2 解压并安装，生成.so文件

[root@localhost redis]# tar -zxf v2.2.1.tar.gz [root@localhost redis]# lsredis-5.0.5  redis-5.0.5.tar.gz  RedisBloom-2.2.1  v2.2.1.tar.gz[root@localhost redis]# cd RedisBloom-2.2.1/[root@localhost RedisBloom-2.2.1]# make[root@localhost RedisBloom-2.2.1]# lschangelog  contrib  Dockerfile  docs  LICENSE  Makefile  mkdocs.yml  ramp.yml  README.md  redisbloom.so  rmutil  src  tests

3.3 在redis配置文件(redis.conf)中加入该模块即可

[root@localhost redis-5.0.5]# pwd/root/redis/redis-5.0.5[root@localhost redis-5.0.5]# ls00-RELEASENOTES  CONTRIBUTING  deps     Makefile   README.md   runtest          runtest-moduleapi  sentinel.conf  testsBUGS             COPYING       INSTALL  MANIFESTO  redis.conf  runtest-cluster  runtest-sentinel   src            utils[root@localhost redis-5.0.5]# ls |grep redis.confredis.conf#配置文件添加.so文件[root@localhost redis-5.0.5]# vim redis.conf

4 启动redis

[root@localhost redis-5.0.5]# ./src/redis-server ./redis.conf &#查看是否启动成功[root@localhost redis-5.0.5]# ps -ef|grep 6379root       4234   4176  0 22:12 pts/0    00:00:07 ./redis-server *:6379root       8744   4176  0 23:06 pts/0    00:00:00 grep --color=auto 6379#连接客户端[root@localhost redis-5.0.5]# ./src/redis-cli 127.0.0.1:6379> keys *(empty list or set)127.0.0.1:6379>

5 操作redisbloom

基本操作命令：

命令	格式	说明
bf.reserve	bf.reserve {key} {error_rate} {initial_size}	创建一个大小为initial_size位向量长度，错误率为error_rate的空的Bloom过滤器
bf.add	bf.add{key} {item}	向key指定的Bloom中添加一个元素item
bf.madd	bf.madd {key} {item} {item2} {item3} …	一次添加多个元素
bf.exists	bf.exists {key} {item}	查询元素是否存在
bf.mexists	bf.mexists {key} {item} {item2} {item3} …	检查多个元素是否存在
bf.info	bf.info {key}	查询key指定的Bloom的信息
bf.debug	bf.debug {key}	查看BloomFilter的内部详细信息（如每层的元素个数、错误率等）
cf.reserve	cf.reserve {key} {initial_size}	创建一个initial_size位向量长度的空的Bloom过滤器
cf.add	cf.add {key} {item}	向key指定的Bloom中添加一个元素item
cf.exists	cf.exists {key} {item}	检查该元素是否存在
bf.scandump	bf.scandump {key} {iter}	(key：布隆过滤器的名字,iter：首次调用传值0，或者上次调用此命令返回的结果值)对Bloom进行增量持久化操作（增量保存）
bf.localchunk	bf.localchunk {key} {iter} {data}	加载SCANDUMP持久化的Bloom数据（key：目标布隆过滤器的名字，iter：SCANDUMP返回的迭代器的值，和data一一对应，data：SCANDUMP返回的数据块（data chunk））

【说明redis布隆过滤器不支持修改元素，只能重新创建】

redis中有两个值决定布隆过滤器的准确率：

值	说明
error_rate	允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间就越大 （默认值0.01）
initial_size	布隆过滤器可以存储的元素个数(位存储)，当实际存在的元素个数超过这个值之后，过滤器的准确率会下降（默认值100）

redis 设置redisbloom的这两个值：

demo：bf.reserve test 0.1 100000000 说明： bf.reserve 过滤器的名字 错误率(error_rate 的值） 位向量长度(initial_size 的值）

参数	说明
test	是过滤器的名字
0.1	错误率（ error_rate 的值）
1000000	位向量长度（initial_size 的值）

(注意必须在add之前使用bf.reserve指令显式创建，如果对应的key已经存在，bf.server会报错。同事设置的错误率越低，需要的空间越大。如果不使用bf.serve，默认的error_rate是0.01，默认的initial_size是100)

注意事项

• initial_size估计的过大会浪费存储空间，因此在使用前要尽可能精确估计好元素数量+冗余空间。
• error_rate越小，需要的存储空间越大。

6 redisbloom示例

6.1 redis-cli操作

#新建一个过滤器127.0.0.1:6379> bf.reserve test 0.1 1000000     # test是布隆过滤器名称，0.1是误判率，1000000是位向量长度OK#向过滤器中添加元素127.0.0.1:6379> bf.add test one  (integer) 1127.0.0.1:6379> bf.add test two(integer) 1#test是布隆过滤器名称，one，two是需要判断的元素#批量添加127.0.0.1:6379> bf.madd test 1 2 3 41) (integer) 12) (integer) 13) (integer) 14) (integer) 1#判断元素是否在过滤器中127.0.0.1:6379> bf.exists test one(integer) 1127.0.0.1:6379> bf.exists test two(integer) 1127.0.0.1:6379> bf.exists test three(integer) 0	#test是布隆过滤器名称，one，two是需要判断的元素存在返回1，不存在返回0#批量判断该元素是否存在127.0.0.1:6379> bf.mexists test 1 2 3 51) (integer) 12) (integer) 13) (integer) 14) (integer) 0#查看指定的key的Bloom信息127.0.0.1:6379> bf.info test 1) Capacity 2) (integer) 1000000 3) Size 4) (integer) 779555 5) Number of filters 6) (integer) 1 7) Number of items inserted 8) (integer) 7 9) Expansion rate10) (integer) 2#查看BloomFilter的内部详细信息（如每层的元素个数、错误率等）127.0.0.1:6379> bf.debug test1) "size:7"2) "bytes:779403 bits:6235224 hashes:5 hashwidth:64 capacity:1000000 size:7 ratio:0.05"#添加一个位向量长度为100000000的空的布隆过滤器127.0.0.1:6379> cf.reserve test3 100000000OK#添加元素127.0.0.1:6379> cf.add test3 1(integer) 1127.0.0.1:6379> cf.add test3 2(integer) 1#检查该元素是否存在127.0.0.1:6379> cf.exists test3 2(integer) 1#对Bloom进行增量持久化操作（增量保存127.0.0.1:6379> bf.scandump test 01) (integer) 12) "\a\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\x8b\xe4\x0b\x00\x00\x00\x00\x00X$_\x00\x00\x00\x00\x00\a\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@B\x0f\x00\x00\x00\x00\x00\x00"

6.2 php使用

#添加php-redisbloom.php文件
   connect('127.0.0.1',6379);$result=$redis->rawCommand('bf.exists','test','one');var_dump($result);              #执行[root@localhost redis]# php php-redisbloom.php int(1)

【添加：在向redis set值的之后，调用bf.add添加到过滤器。 检查：在穿过了redis去到Mysql之前，调用bf.exists检查一下，如果不存在则不连接mysql查询】