redis中的布隆过滤器

Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

1.Dcoker向redis中装布隆过滤器

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


或者
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

2.redis 布隆过滤器主要就两个命令：

• bf.add 添加元素到布隆过滤器中：bf.add urls https://jaychen.cc。
• bf.exists 判断某个元素是否在过滤器中：bf.exists urls https://jaychen.cc。

上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。(其实也就是位数组大了碰撞率低了,容错率自然低了)
• initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

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

bf.reserve urls 0.01 100

三个参数的含义：

第一个值是过滤器的名字。

第二个值为错误率 error_rate 的值。

第三个值为预期容量 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists

另外,我们错误率越低,预期容量越高的情况下需要在redis里申请的bit数组(空间)就越大,这点需要注意下

如果对布隆过滤器有一定的疑惑可以查看 https://cloud.tencent.com/developer/article/2002126

详细demo的话可以看看https://www.cnblogs.com/ysocean/p/12594982.html

3. demo

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilter {

    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.14.104:6379");
        config.useSingleServer().setPassword("123");
        //构造Redisson
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
        //初始化布隆过滤器：预计元素为100000000L,误差率为3%
        bloomFilter.tryInit(100000000L,0.03);
        //将号码10086插入到布隆过滤器中
        bloomFilter.add("10086");

        //判断下面号码是否在布隆过滤器中
        System.out.println(bloomFilter.contains("123456"));//false
        System.out.println(bloomFilter.contains("10086"));//true
    }
}

4、判断数据是否存在？

知道了如何向布隆过滤器中添加一个数据，那么新来一个数据，我们如何判断其是否存在于这个布隆过滤器中呢？ 很简单，我们只需要将这个新的数据通过上面自定义的几个哈希函数，分别算出各个值，然后看其对应的地方是否都是1，如果存在一个不是1的情况，那么我们可以说，该新数据一定不存在于这个布隆过滤器中。 反过来说，如果通过哈希函数算出来的值，对应的地方都是1，那么我们能够肯定的得出：这个数据一定存在于这个布隆过滤器中吗？ 答案是否定的，因为多个不同的数据通过hash函数算出来的结果是会有重复的，所以会存在某个位置是别的数据通过hash函数置为的1。 我们可以得到一个结论：布隆过滤器可以判断某个数据一定不存在，但是无法判断一定存在。

5、布隆过滤器优缺点

优点：优点很明显

• 二进制组成的数组，占用内存极少
• 插入和查询速度都足够快。

缺点：

• 随着数据的增加，误判率会增加；
• 无法判断数据一定存在；
• 无法删除数据。