Redis 实现布隆过滤器

Redis 实现布隆过滤器

Nov 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)1

在 Redis 中的实现 #

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

布隆过滤器的基本指令 #

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


  1. https://cloud.tencent.com/developer/article/1136056 ↩︎

  2. https://oss.redis.com/redisbloom/Quick_Start/ ↩︎

本文共 1064 字,上次修改于 Oct 26, 2022,以 CC 署名-非商业性使用-禁止演绎 4.0 国际 协议进行许可。

相关文章

» Redis 基础知识

» 使用 Django 查询数据库的分表

» 说说实际工作中 GraphQL 的使用体验

» UTF、Unicode 和 ASCII 编码的关系

» Django 中 N+1 查询问题优化