Redis 应用-布隆过滤器

布隆过滤器是什么?

布隆过滤器可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的精确度可以控制的相对足够精确,只会有小小的误判概率。

当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。打个比方,当它说不认识你时,肯定就不认识;当它说见过你时,可能根本就没见过面,不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合),所以误判以前见过你。
套在上面的使用场景中,布隆过滤器能准确过滤掉那些已经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

布隆过滤器的原理

其本质就是一个只包含 0 和 1 的数组。具体操作当一个元素被加入到集合里面后,该元素通过 K 个 Hash 函数运算得到 K 个 hash 后的值,然后将 K 个值映射到这个位数组对应的位置,把对应位置的值设置为 1。查询是否存在时,我们就看对应的映射点位置如果全是 1,他就很可能存在(跟 hash 函数的个数和 hash 函数的设计有关),如果有一个位置是 0,那这个元素就一定不存在。

Redis 中的布隆过滤器

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中,给 Redis 提供了强大的布隆去重功能。

你可以使用 docker 镜像来体验

> docker pull redislabs/rebloom # 拉取镜像
> docker run -p6379:6379 redislabs/rebloom # 运行容器
> redis-cli # 连接容器中的 redis 服务

当然你也可以自己编译安装

下载编译安装Rebloom插件
wget https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz
解压 tar zxvf v1.1.1.tar.gz
cd rebloom-1.1.1
make
redis服启动添加对应参数
rebloom_module="/usr/local/rebloom/rebloom.so"
daemon --user ${REDIS_USER-redis} "$exec $REDIS_CONFIG --loadmodule $rebloom_module --daemonize yes --pidfile $pidfile"

重启redis服务

测试命令
bf.add test testValue
命令成功说明开启成功

布隆过滤器基本使用

主要命令有

  • bf.add 添加元素
  • bf.exists 查询元素是否存在
  • bf.madd 一次添加多个元素
  • bf.mexists 一次查询多个元素是否存在

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

  • error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。
  • initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值:

bf.reserve test 0.01 100 
  • 第一个值是过滤器的名字。
  • 第二个值为 error_rate 的值。
  • 第三个值为 initial_size 的值。

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

应用场景

主要是解决大规模数据下不需要精确过滤的场景,如检查垃圾邮件地址,爬虫 URL 地址去重,解决缓存穿透问题等。

延伸阅读

布隆过滤器 (Bloom Filter) 详解
布谷鸟过滤器

评论