系列文章
布隆过滤器是什么？
布隆过滤器可以理解为一个不怎么精确的 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) 详解
布谷鸟过滤器
本文亦在微信公众号【小道资讯】发布，欢迎扫码关注！
image
网友评论