Redis–布隆过滤器–使用/原理/实例

admin • • 数据库

原文网址：Redis--布隆过滤器--使用/原理/实例_IT利刃出鞘的博客-CSDN博客

简介

说明

        本文介绍Redis的布隆过滤器的原理，优缺点，使用场景，实例。

        布隆过滤器由n个Hash函数和一个二进制数组组成，主要用于判断一个元素是否在一个集合中。

        布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。

        布隆过滤器是Java后端面试中常见的问题。

原理

1.初始状态

一开始，二进制数组里是没有值的

2.存储操作

发来一个请求数据hello
对数据hello经过三次hash运算，分别得到三个值（假设1，3，5）。
在对应的二进制数组里，将下标为1，3，5的值置为1。

3.查询操作

发来一个请求数据hello
对数据hello经过三次hash运算，分别得到三个值（假设1，3，5）。
在二进制数组里，将下标为1，3，5的值取出来，如果都为1，则表示该数据已经存在。

4.删除操作

布隆过滤器很难进行删除操作。

如果hash2(hello)结果为3，hash2(world)结果也为3，那么如果删除了hello的值，就意味着world的值也会被其删除。

5.误判率

假设保存两个值，hello和world
hello对应的index（也就是hash计算后的值）为1，3，5
world对应的index（也就是hash计算后的值）为2，4，6

        而此时来了一个值java，对应的index为1，4，5，查询得出结果：exist(java) = true，但其实，java这个数据并不存在，这就会产生一定的误判。

优缺点

布隆过滤器优点

  1. 不需要存储元素本身，节省了大量的空间
  2. 查询速度很快

布隆过滤器缺点

  1. 有一定的误识别率，不适合对误判率要求较高的场景。
  2. 无法删除数据

        为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

使用场景

  1. 数据库防止穿库
    1. Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
  2. 业务去重
    1. 判断用户是否阅读过某视频或文章。比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
  3. 缓存宕机、缓存穿透
    1. 一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
  4. WEB拦截器
    1. 如果相同请求则拦截，防止重复被攻击。
    2. 用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。
    3. Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务
  5. 文档存储系统
    1. Venti 文档存储系统采用了布隆过滤器来检测先前存储的数据。
  6. 模型检测器
    1. SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

代码实现

已经有现成的布隆过滤器的实现了，不需要我们自己手写了。

单机版的布隆过滤器：Guava 的 BloomFilter；分布式的布隆过滤器：Redis的RedisBloom。

Guava

引入依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

使用

public class GuavaBloomFilterDemo {

    public static void main(String[] args) {
        //后边两个参数：预计包含的数据量；允许的误差值
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
        for (int i = 0; i < 100000; i++) {
            bloomFilter.put(i);
        }
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(100001));

        //bloomFilter.writeTo();
    }
}

Redis

简介

        Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

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

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式：

直接编译进行安装

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make     #编译 会生成一个rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so   #运行redis时加载布隆过滤器模块
redis-cli    # 启动连接容器中的 redis 客户端验证

使用Docker进行安装

docker pull redislabs/rebloom:latest # 拉取镜像
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest #运行容器
docker exec -it redis-redisbloom bash
redis-cli     

使用

布隆过滤器基本指令：

  • bf.add 添加元素到布隆过滤器
  • bf.exists 判断元素是否在布隆过滤器
  • bf.madd 添加多个元素到布隆过滤器，bf.add 只能添加一个
  • bf.mexists 判断多个元素是否在布隆过滤器
127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.add user John
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Linda
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器，bf.reserve 过滤器名 error_rate initial_size

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

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错

127.0.0.1:6379> bf.reserve user 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve topic 0.01 1000
OK

Java操作

 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson

public class RedissonBloomFilterDemo {

    public static void main(String[] args) {

        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
        // 初始化布隆过滤器，预计统计元素数量为55000000，期望误差率为0.03
        bloomFilter.tryInit(55000000L, 0.03);
        bloomFilter.add("Tom");
        bloomFilter.add("Jack");
        System.out.println(bloomFilter.count());   //2
        System.out.println(bloomFilter.contains("Tom"));  //true
        System.out.println(bloomFilter.contains("Linda"));  //false
    }
}

其他网址

布隆过滤器，没那么难 - SegmentFault 思否
布隆过滤器原理和基于BloomFilter的误判率展示_二祥的工作历程-CSDN博客
布隆过滤器_huangshanchun的专栏-CSDN博客_布隆过滤器

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>