硬核|redis布隆(bloomfilter)过滤器原理与实战(代码片段)

码哥字节 码哥字节     2022-11-29     648

关键词:

在Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?中我们说到可以使用布隆过滤器避免「缓存穿透」。

码哥,布隆过滤器还能在哪些场景使用呀?

比如我们使用「码哥跳动」开发的「明日头条」APP 看新闻,如何做到每次推荐给该用户的内容不会重复,过滤已经看过的内容呢?

你会说我们只要记录了每个用户看过的历史记录,每次推荐的时候去查询数据库过滤存在的数据实现去重

实际上,如果历史记录存储在关系数据库里,去重就需要频繁地对数据库进行 exists 查询,当系统并发量很高时,数据库是很难扛住压力的。

码哥,我可以使用缓存啊,把历史数据存在 Redis 中。

万万不可,这么多的历史记录那要浪费多大的内存空间,所以这个时候我们就能使用布隆过滤器去解决这种去重问题。又快又省内存,互联网开发必备杀招!

当你遇到数据量大,又需要去重的时候就可以考虑布隆过滤器,如下场景:

  • 解决 Redis 缓存穿透问题(面试重点);
  • 邮件过滤,使用布隆过滤器实现邮件黑名单过滤;
  • 爬虫爬过的网站过滤,爬过的网站不再爬取;
  • 推荐过的新闻不再推荐;
  • 什么是布隆过滤器

    布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出,它是一种 space efficient 的概率型数据结构,用于判断一个元素是否在集合中

    当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不存在时,那么这个数据一定不存在。

    哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的 1/8 或 1/4 的空间复杂度就能完成同样的问题。

    布隆过滤器可以插入元素,但不可以删除已有元素。

    其中的元素越多,false positive rate(误报率)越大,但是 false negative (漏报)是不可能的。

    布隆过滤器原理

    BloomFilter 的算法是,首先分配一块内存空间做 bit 数组,数组的 bit 位初始值全部设为 0。

    加入元素时,采用 k 个相互独立的 Hash 函数计算,然后将元素 Hash 映射的 K 个位置全部设置为 1。

    检测 key 是否存在,仍然用这 k 个 Hash 函数计算出 k 个位置,如果位置全部为 1,则表明 key 存在,否则不存在。

    如下图所示:

    布隆过滤器原理

    哈希函数会出现碰撞,所以布隆过滤器会存在误判。

    这里的误判率是指,BloomFilter 判断某个 key 存在,但它实际不存在的概率,因为它存的是 key 的 Hash 值,而非 key 的值。

    所以有概率存在这样的 key,它们内容不同,但多次 Hash 后的 Hash 值都相同。

    对于 BloomFilter 判断不存在的 key ,则是 100% 不存在的,反证法,如果这个 key 存在,那它每次 Hash 后对应的 Hash 值位置肯定是 1,而不会是 0。布隆过滤器判断存在不一定真的存在。

    码哥,为什么不允许删除元素呢?

    删除意味着需要将对应的 k 个 bits 位置设置为 0,其中有可能是其他元素对应的位。

    因此 remove 会引入 false negative,这是绝对不被允许的。

    Redis 集成布隆过滤器

    Redis 4.0 的时候官方提供了插件机制,布隆过滤器正式登场。以下网站可以下载官方提供的已经编译好的可拓展模块。

    https://redis.com/redis-enterprise-software/download-center/modules/

    RedisModules

    码哥推荐使用 Redis 版本 6.x,最低 4.x 来集成布隆过滤器。如下指令查看版本,码哥安装的版本是 6.2.6。

    redis-server -v
    Redis server v=6.2.6 sha=00000000:0 malloc=libc bits=64 build=b5524b65e12bbef5
    文件。

    error_rate = 0.1 ,初始容量为 10000000 的布隆过滤器:

    0.01capacity是 100。

    布隆过滤器的 error_rate 越小,需要的存储空间就越大,对于不需要过于精确的场景,error_rate 设置稍大一点也可以。

    布隆过滤器的 capacity 设置的过大,会浪费存储空间,设置的过小,就会影响准确率,所以在使用之前一定要尽可能地精确估计好元素数量,还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。

    的布隆过滤器添加 10086 这个元素。

    如果是多个元素同时添加,则使用 BF.MADD key item ...,如下:

    BF.MADD orders 10087 10089
    1) (判断一个元素是否存在于BloomFilter,返回值 = 1 表示存在。

    如果需要批量检查多个元素是否存在于布隆过滤器则使用 BF.MEXISTS,返回值是一个数组:

  • 1:存在;
  • 0:不存在。
  • # BF.MEXISTS key item
    BF.MEXISTS orders 100 10089
    1) (integer) 0
    2) (integer) 1

    总体说,我们通过BF.RESERVE、BF.ADD、BF.EXISTS三个指令就能实现避免缓存穿透问题。

    码哥,如何查看创建的布隆过滤器信息呢?

    BF.INFO key查看,如下:

    BF.INFO orders
     1) Capacity
     2) (integer) 10000000
     3) Size
     4) (integer) 7794184
     5) Number of filters
     6) (integer) 1
     7) Number of items inserted
     8) (integer) 3
     9) Expansion rate
    10) (integer) 2

    返回值:

  • Capacity:预设容量;
  • Size:实际占用情况,但如何计算待进一步确认;
  • Number of filters:过滤器层数;
  • Number of items inserted:已经实际插入的元素数量;
  • Expansion rate:子过滤器扩容系数(默认 2);
  • 码哥,如何删除布隆过滤器呢?

    目前布隆过滤器不支持删除,布谷过滤器Cuckoo Filter是支持删除的。

    Bloom 过滤器在插入项目时通常表现出更好的性能和可伸缩性(因此,如果您经常向数据集添加项目,那么 Bloom 过滤器可能是理想的)。布谷鸟过滤器在检查操作上更快,也允许删除。

    大家有兴趣可可以看下:https://oss.redis.com/redisbloom/Cuckoo_Commands/)

    码哥,我想知道你是如何掌握这么多技术呢?

    其实我也是翻阅官方文档并做一些简单加工而已,这篇的文章内容实战就是基于 Redis 官方文档上面的例子:https://oss.redis.com/redisbloom/。

    大家遇到问题一定要耐心的从官方文档寻找答案,培养自己的阅读和定位问题的能力。

    Redission 布隆过滤器实战

    码哥的样例代码基于 Spring Boot 2.1.4,代码地址:https://github.com/MageByte-Zero/springboot-parent-pom。

    添加 Redission 依赖:

    <dependency>
      <groupId>org.redisson</groupId>
      <artifactId>redisson-spring-boot-starter</artifactId>
      <version>3.16.7</version>
    </dependency>

    使用 Spring boot 默认的 Redis 配置方式配置 Redission:

    spring:
      application:
        name: redission

      redis:
        host: 127.0.0.1
        port: 6379
        ssl: false

    创建布隆过滤器

    @Service
    public class BloomFilterService 

        @Autowired
        private RedissonClient redissonClient;

        /**
         * 创建布隆过滤器
         * @param filterName 过滤器名称
         * @param expectedInsertions 预测插入数量
         * @param falseProbability 误判率
         * @param <T>
         * @return
         */

        public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) 
            RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
            bloomFilter.tryInit(expectedInsertions, falseProbability);
            return bloomFilter;
        


    单元测试

    @Slf4j
    @RunWith(SpringRunner.class)
    @SpringBootTest(classes 
    = RedissionApplication.class)
    public class BloomFilterTest 


        @Autowired
        private BloomFilterService bloomFilterService;

        @Test
        public void testBloomFilter() 
            // 预期插入数量
            long expectedInsertions = 10000L;
            // 错误比率
            double falseProbability = 0.01;
            RBloomFilter<Long> bloomFilter = bloomFilterService.create("ipBlackList", expectedInsertions, falseProbability);

            // 布隆过滤器增加元素
            for (long i = 0; i < expectedInsertions; i++) 
                bloomFilter.add(i);
            
            long elementCount = bloomFilter.count();
            log.info("elementCount = .", elementCount);

            // 统计误判次数
            int count = 0;
            for (long i = expectedInsertions; i < expectedInsertions * 2; i++) 
                if (bloomFilter.contains(i)) 
                    count++;
                
            
            log.info("误判次数 = .", count);
            bloomFilter.delete();
        


    注意事项:如果是 Redis Cluster 集群,则需要 RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");

    文末福利

    送 4 本《大型网站架构实战》给一直关注并支持码哥的读者。

    中奖规则:在本文留言并将此文转发到朋友圈,我从留言中随机抽取 4 位幸运读者,凭借朋友圈分享记录截图领取。免费包邮到手!

    截止:2022 年 3 月 24 20:00

    大型网站系统有很多功能,一次性明确所有的功能需求并设计出一个庞大的业务架构是一件费力不讨好的事情。因为在项目前期,难免会忽视一些琐碎功能,而随着开发的进行,也会有很多新的想法产生,基本上不会存在完全按照最初的业务架构设计完成的软件产品。因此,业务架构不仅要做到“规整功能模块,厘清产品业务逻辑”,更重要的是如何做到“有规划性地应对项目过程中的需求变更”。

    好文推荐

    Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?

    Redis 突然变慢了如何排查并解决?

    Redis 面霸篇:从高频问题透视核心原理

    点击下方卡片关注我

    加我微信:MageByte1024,进入专属技术读者群一起成长。


    好文记得「点赞」「分享」「收藏」三连,感激不尽。



    参考资料

    1.https://blog.csdn.net/u010066934/article/details/122026625 

    2.https://juejin.cn/book/6844733724618129422/section/6844733724706209806 

    3.https://www.cnblogs.com/heihaozi/p/12174478.html 

    4.https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html 

    5.https://oss.redis.com/redisbloom/Bloom_Commands/ 

    6.https://oss.redis.com/redisbloom/ 

    7.https://redis.com/blog/rebloom-bloom-filter-datatype-redis

    redis11_布隆过滤器bloomfilter的概述优缺点使用场景底层原理布谷鸟过滤器(代码片段)

    文章目录①.布隆过滤器BloomFilter的概述②.布隆过滤器优缺点③.布隆过滤器的使用场景④.布隆过滤器原理⑤.布谷鸟过滤器(了解)①.布隆过滤器BloomFilter的概述①.它实际上是一个很长的二进制数组(初始值为0的bit数组)+一系列随... 查看详情

    redis11_布隆过滤器bloomfilter的概述优缺点使用场景底层原理布谷鸟过滤器(代码片段)

    文章目录①.布隆过滤器BloomFilter的概述②.布隆过滤器优缺点③.布隆过滤器的使用场景④.布隆过滤器原理⑤.布谷鸟过滤器(了解)①.布隆过滤器BloomFilter的概述①.它实际上是一个很长的二进制数组(初始值为0的bit数组)+一系列随... 查看详情

    redis07_布隆过滤器bloomfilter的概述优缺点使用场景底层原理布谷鸟过滤器(代码片段)

    文章目录①.布隆过滤器BloomFilter的概述②.布隆过滤器优缺点③.布隆过滤器的使用场景④.布隆过滤器原理⑤.布谷鸟过滤器(了解)①.布隆过滤器BloomFilter的概述①.它实际上是一个很长的二进制数组+一系列随机hash算法映射函数&#... 查看详情

    redis07_布隆过滤器bloomfilter的概述优缺点使用场景底层原理布谷鸟过滤器(代码片段)

    文章目录①.布隆过滤器BloomFilter的概述②.布隆过滤器优缺点③.布隆过滤器的使用场景④.布隆过滤器原理⑤.布谷鸟过滤器(了解)①.布隆过滤器BloomFilter的概述①.它实际上是一个很长的二进制数组+一系列随机hash算法映射函数&#... 查看详情

    布隆(bloomfilter)过滤器——全面讲解,建议收藏(代码片段)

    本文已收录于专栏❤️《Redis之大厂必备技能包》❤️欢迎各位关注、三连博主的文章及专栏,全套Redis学习资料,大厂必备技能! 目录1、什么是布隆过滤器2、布隆过滤器的使用场景3、布隆过滤器的原理3.1数据结构... 查看详情

    布隆(bloomfilter)过滤器——全面讲解,建议收藏(代码片段)

    本文已收录于专栏❤️《Redis之大厂必备技能包》❤️欢迎各位关注、三连博主的文章及专栏,全套Redis学习资料,大厂必备技能! 目录1、什么是布隆过滤器2、布隆过滤器的使用场景3、布隆过滤器的原理3.1数据结构... 查看详情

    redis安装布隆(bloomfilter)过滤器(代码片段)

    本文已收录于专栏❤️《Redis之大厂必备技能包》❤️欢迎各位关注、三连博主的文章及专栏,全套Redis学习资料,大厂必备技能!目录一、版本要求二、安装&编译2.1下载插件压缩包2.2解压2.3编译插件三、Redis集成3... 查看详情

    redisredis添加bloomfilter布隆过滤器插件(代码片段)

    前言redis在4.0版本以后可通过插件的形式添加布隆过滤器,以下为具体操作。操作在https://github.com/RedisBloom/RedisBloom下载最新的release源码,在编译服务器进行解压编译:tarzxvfRedisBloom-1.1.1.tar.gzcdRedisBloom-1.1.1make得到动态库rebloom.so启... 查看详情

    布隆过滤器详解(bloomfilter)以及其实现介绍

    一、三种去重方式1.HashSet使用java中的HashSet不能重复的特点去重。优点是容易理解。使用方便。缺点:占用内存大,性能较低。2.Redis去重使用Redis的set进行去重。优点是速度快(Redis本身速度就很快),而且去... 查看详情

    布隆过滤器(bloomfilter)

    一、概念1.布隆过滤器是一个数据结构:bit数组+随机映射函数2.作用:高效判断某个元素是否在给定的集合中3.缺点:有一定的错误识别率,随着数据量越大,错误识别率越大;并且不容易删除 二、原理1.加入元素:a.使用布... 查看详情

    布隆过滤器详解(bloomfilter)以及其实现介绍(代码片段)

    一、三种去重方式1.HashSet使用java中的HashSet不能重复的特点去重。优点是容易理解。使用方便。缺点:占用内存大,性能较低。2.Redis去重使用Redis的set进行去重。优点是速度快(Redis本身速度就很快),而且去... 查看详情

    bloomfilter布隆过滤器

    http://blog.csdn.net/pipisorry/article/details/64127666BloomFilter简介   BloomFilter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。布隆过滤器(英语:BloomFilter)是19... 查看详情

    redis中布隆过滤器使用详解(代码片段)

    ...过滤器实战1.引入redisson依赖2.创建订单表3.配置redis4.配置BloomFilter5.创建订单6.单元测试总结一、布隆过滤器介绍1、什么是布隆过滤器布隆过滤器(英语:BloomFilter)是1970年由布隆提出的。它实际上是一个很长的二进... 查看详情

    布隆过滤器(bloomfilter)从入门到出土

    文章目录问题引入布隆过滤器(BloomFilter)布隆过滤器概念布隆过滤器作用布隆过滤器的核心包括两部分:布隆过滤器的工作原理:布隆过滤器优缺点问题引入想象一下遇到下面的场景你会如何处理:手机号是... 查看详情

    布隆过滤器总结

    一:布隆过滤器简介:  BloomFilter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。BloomFilter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,... 查看详情

    布隆过滤器(bloomfilter)(代码片段)

    布隆过滤器(BloomFilter)是一种基于Hash的高效查找数据结构,它能够快速答复“某个元素是否存在”的问题。布隆过滤器只能用于添加元素与查询元素,不能够用于删除元素。在布隆过滤器之前,使用的是基于Hash的快速查找算法。... 查看详情

    海量信息库,查找是否存在(bloomfilter布隆过滤器)

    BloomFilter(布隆过滤器)布隆过滤器用于测试某一元素是否存在于给定的集合中,是一种空间利用率很高的随机数据结构(probabilisticdatastructure),存在一定的误识别率(falsepositive),即布隆过滤器报告某一元素存在于某集合中... 查看详情

    hbase布隆过滤器bloomfilter介绍

    1、主要功能提高随机读的性能2、存储开销bloomfilter的数据存在StoreFile的meta中,一旦写入无法更新,由于StoreFile是不可变的。Bloomfilter是一个列族(cf)级别的配置属性,假设你在表中设置了Bloomfilter,那么HBase会在生成StoreFile时... 查看详情