锐单电子商城 ， 一站式电子元器件采购平台！

  • 电话：400-990-0325

购物车

硬核 | Redis 布隆（Bloom Filter）过滤器原理与实战

时间：2022-10-24 23:30:03 33x压力变送器

在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 存在，否则不存在。

如下图所示：

6b59fe56f30303442fe2a152f3067219.png
布隆过滤器原理

哈希函数会碰撞，所以布隆过滤器会误判。

这里的误判率是指，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 Redisserverv=6.2.6sha=00000000:0malloc=libcbits=64build=b5524b65e12bbef5

下载

我们需要自己编译和安装 github 下载，目前 release 版本是 v2.2.14、下载地址：https://github.com/RedisBloom/RedisBloom/releases/tag/v2.2.14

Redis 布隆

解压编译

解压

tar-zxvfRedisBloom-2.2.14.tar

编译插件

cdRedisBloom-2.2.14 make

成功的编译，就会看到 redisbloom.so 文件。

安装集成

需要修改 redis.conf 文件，新增 loadmodule并重启配置 Redis。

loadmodule/opt/app/RedisBloom-2.2.14/redisbloom.so

若为集群，则需要添加每个例子的配置文件。

module 配置

并启动指定配置文件 Redis：

redis-server /opt/app/redis-6.2.6/redis.conf

加载成功的页面如下：

成功加载布隆过滤器

客户端连接 Redis 测试。

BF.ADD--在布隆素到布隆过滤器 BF.EXISTS--判断元素是否在布隆过滤器中 BF.MADD--在布隆过滤器中添加多个元素 BF.MEXISTS--判断布隆过滤器中是否有多个元素
测试

Redis 实战布隆过滤器

用布隆过滤器解决缓存穿透问题，缓存穿透：有特殊要求查询不存在的数据，即数据不存在 Redis 也不存在于数据库中。

当用户购买商品并创建订单时，我们经常 mq 发短信，下单 ID 添加到布隆过滤器。

订单同步到布隆过滤器

在添加布隆过滤器之前，我们通过它BF.RESERVE命令手动创建名称 orders error_rate = 0.1 ，初始容量为 10000000 布隆过滤器：

#BF.RESERVE{key}{error_rate}{capacity}[EXPANSION{expansion}][NONSCALING] BF.RESERVEorders0.110000000

  • key：filter 的名字；

  • error_rate：预期错误率，默认 0.1.值越低，空间越大；

  • capacity：初始容量，默认 当实际元素数量超过这个初始化容量时，误判率就会上升。

  • EXPANSION：可选参数，当添加到布隆过滤器中的数据达到初始容量后，布隆过滤器会自动创建一个子过滤器，子过滤器的大小是上一个过滤器大小乘以 expansion；expansion 的默认值是 2.也就是说，布隆过滤器的扩容是默认的 2 倍扩容；

  • NONSCALING：设置此项后，当添加到布隆过滤器中的数据达到初始容量时，可选参数不会扩大过滤器，并会抛出异常（(error) ERR non scaling filer is full） 说明：BloomFilter 的扩容是通过增加 BloomFilter 的层数来完成的。每增加一层，在查询的时候就可能会遍历多层 BloomFilter 来完成，每一层的容量都是上一层的两倍（默认）。

如果不使用BF.RESERVE命令创建，而是使用 Redis 自动创建的布隆过滤器，默认的 error_rate 是 0.01，capacity是 100。

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

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

添加订单 ID 到过滤器

# BF.ADD {key} {item}
BF.ADD orders 10086
(integer) 1

使用 BF.ADD向名称为 orders 的布隆过滤器添加 10086 这个元素。

如果是多个元素同时添加，则使用 BF.MADD key {item ...}，如下：

BF.MADD orders 10087 10089
1) (integer) 1
2) (integer) 1

判断订单是否存在

# BF.EXISTS {key} {item}
BF.EXISTS orders 10086
(integer) 1

BF.EXISTS 判断一个元素是否存在于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 依赖：


  org.redisson
  redisson-spring-boot-starter
  3.16.7

使用 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 
     * @return
     */
    public  RBloomFilter create(String filterName, long expectedInsertions, double falseProbability) {
        RBloomFilter 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 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 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

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

相关文章