布隆过滤器

布隆过滤器

redis原生不自带布隆过滤器，需要自己去编译该插件进行安装

安装

从github进行下载https://github.com/RedisBloom/RedisBloom/tags，进入下载目录进行编译make，生成redisbloom.so文件

修改redis.conf加载插件 loadmodule /usr/local/myself/redis/module/RedisBloom-2.2.18/redisbloom.so，重启redis

基本命令

• bf.add 添加元素

  127.0.0.1:6379> bf.add art user1
  (integer) 1
  127.0.0.1:6379> bf.add art user2
  (integer) 1

• bf.exists 查询元素是否存在

  127.0.0.1:6379> BF.EXISTS art user3
  (integer) 0
  127.0.0.1:6379> BF.EXISTS art user1
  (integer) 1

原理

布隆过滤器就是一个大的bitmap和几个hash函数组成的。当向布隆过滤器添加key时，会使用多个hash函数对key进行hash计算得到一个索引值，然后对位数长度进行取模得到一个位置。每个hash函数都会算出一个不同的位置，将这几个位置都置为1就完成了add操作。

同样的，判断是否存在时，也会使用hash函数来计算，查看对应的几个位置是否都为1，只要有一个位为0，则表示key不存在。但是如果都为1，也不一定表示key一定存在，所以有一定的误差