Redis 实现布隆过滤器

11月 12, 2019

布隆过滤器（Bloom Filter，BF），能够确定一个东西一定不存在或可能存在，常用于在海量并发情况下防止缓存击穿，相比较传统的 List、Set、Map 数据结构，布隆过滤器能够在大数据量的情况下，相比其他结构更能节省大量的内存空间。

实现原理 #

哈希函数 #

布隆过滤器实现了 K 个不同的哈希函数，假设初始的二进制数组长度为 N，K 对 N 取模，就得到了 K 个位置，当加入一个变量时，就将这 K 个位置的值置为 1。当需要验证一个变量时，经过取模运算，验证这 K 个位置的值是否都为 1：

• 都为 1，说明这个变量可能存在；
• 有任何一个点的值为 0，说明这个变量一定不存在。

可能存在的原因是因为：

1. 哈希函数之间本身是有碰撞可能性的。
2. 取模运算也会使具体的哈希值失真，不同哈希值取模后的值也有概率会重复，这个概率和数组的长度有关。

特点 #

可见只要布隆过滤器的长度足够长，不出现全部为 1 的情况，就可以实现一定条件的有效过滤，从而减轻后续业务的大量 I/O 运算。另外对“可能存在”的误判率（False Positive Probability），会随着数组逐渐被填满而越来越大。

缺点 #

布隆过滤器无法删除元素，如果删除元素要将数组元素的 1 置为 0 的话，其他可能存在的元素也会被判为一定不存在，从而提高了误判率，这时就需要引入更高复杂度的计数布隆过滤器（Counting Bloom Filter）¹。

在 Redis 中的实现 #

布隆过滤器可以通过 Redis 的位图（bitmap）实现，Redis 官方在 5.0 版本提供了专门的插件 RedisBloom，并提供了一系列命令方便操作，RedisBloom 同时提供了布谷鸟过滤器（Cuckoo Filter，CF）功能²。

布隆过滤器的基本指令 #

BF.ADD 添加元素到布隆过滤器：

127.0.0.1:6379> BF.ADD newFilter foo
(integer) 1

BF.EXISTS 判断元素是否在布隆过滤器：

127.0.0.1:6379> BF.EXISTS newFilter foo
(integer) 1

127.0.0.1:6379> BF.EXISTS newFilter notpresent
(integer) 0

BF.MADD 添加多个元素到布隆过滤器：

127.0.0.1:6379> BF.MADD myFilter foo bar baz
1) (integer) 1
2) (integer) 1
3) (integer) 1

BF.MEXISTS 判断多个元素是否在布隆过滤器：

127.0.0.1:6379> BF.MEXISTS myFilter foo nonexist bar
1) (integer) 1
2) (integer) 0
3) (integer) 1

Redis 还支持自定义误报率，使存储的元素在 600000 以内的误报率保持在 0.0001 以下：

127.0.0.1:6379> BF.RESERVE customFilter 0.0001 600000
OK

其中：

• error_rate（0.0001）是误报率，这个值越低数组占用的空间越大；
• capacity（600000）是过滤器的容量，超过这个容量后误报率会上升。

应用场景 #

根据业务场景的不同，布隆过滤器也有不同的实现，比如：

• Google Chrome 浏览器使用了布隆过滤器加速安全浏览服务。
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章。
• 大数据中广告等业务对 DAU 等准确性要求不是很高的实时统计场景。
• 从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。
• URL 去重或者黑名单系统。
• 解决缓存穿透问题。

参考 #

什么是 BloomFilter - JavaKeeper