百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术文章 > 正文

布隆过滤器应用——解决Redis缓存穿透问题

nanshan 2024-12-12 14:06 14 浏览 0 评论


1. 布隆过滤器

  • 简要介绍布隆过滤器的概念和特点,详细知识请参考几篇参考文献或其它文章。

1.1 概念

简单点说,布隆过滤器本质是一个位数组

  • 当一个元素加入过滤器时,使用多个hash函数对元素求值,并将位数组中对应位置为1;
  • 判断一个元素是否在过滤器中时,使用多个函数对元素求值,并判断位数组对应位置是否为1。如果都为1,认为元素在过滤器中;否则认为元素不在过滤器中。

1.2 特点

  • 布隆过滤器判断元素存在,可能存在误判;但判断元素不存在,必然不存在。
  • 布隆过滤器通过多个hash函数来降低冲突,增加hash函数数目可以降低冲突率
  • 当过滤器中元素达到一定数目时,增加hash函数不能有效降低冲突率。
  • 使用位数组,占用数据空间小
  • 删除元素困难。

2

3. 布隆过滤器解决缓存穿透问题

3.1 为什么使用布隆过滤器来解决缓存穿透问题

(1)布隆过滤器与redis set结果对比

为什么不将所有value都存储在redis的set中,在请求数据库之前先访问查询value是否存在?主要有以下几点原因:

  • 缓存穿透问题是因为查询了一个数据库中没有的值,需要能够在请求数据库之前判断数据库中是否存在该值
  • 由于redis用来作缓存,本身不可能存储所有的数据(因为内存是昂贵的,就算有32G内存,和T级的存储相比也显得渺小),只能用来存储热点数据。但是又需要有一个速度很快的内存结构来存储所有值,显然没法使用常规的map和set(空间开销巨大)
  • 布隆过滤器使用位数组,占用空间极小
  • 布隆过滤器以较低的误判率换取了大量的空间。(存在较低的假阳性,会使得向数据库请求极少的不存在的值,带来较少的时间开销)

布隆过滤器与set空间消耗对比:



(2)布隆过滤器与md5等单向映射算法对比

在value占用空间较大大时(比如网址),还可以将所有的value通过算法单向映射成一个值(比如使用md5),这样只存储映射后的值,而不需要存储value,从而达到节约空间的目的。

布隆过滤器与单向映射后取值空间消耗对比

假设仍有100亿条URL,那么大概需要一个34位(4.25b)的value来表示才能保证较低的冲突率,仍需要大约42.5GB的空间大小,对应布隆过滤器方案如(1)所示只需要25GB

2^34=171 7986 9184

(3)几种方案对比可参考:



3.2 如何使用布隆过滤器解决缓存穿透问题

3.2.1 基本步骤

应用布隆过滤器解决Redis缓存穿透问题主要有以下步骤:

  • (1)在添加数据库记录时,向过滤器中增加元素。
  • (2)收到请求时,先查询redis缓存,缓存中没有查询布隆过滤器;布隆过滤器中没有直接返回,有查询数据库;
  • (3)暂时还不清楚需不需要对过滤器中元素进行删除,以及如何删除,是否可以考虑定时对过滤器进行清空动作?还是需要使用CountBloomFilter结构来实现删除?

3.2.2 请求流程

增加了布隆过滤器的Redis作缓存系统的一次请求过程如下:



4. Redis布隆过滤器实现

4.1.1 借助Redis原生位图实现布隆过滤器

借助位图的话,需要自行实现多个hash函数,以及布隆过滤器的其它特性,可参考:用Redis快速实现BloomFilter

4.1.2 使用Redisson封装的RBloomFilter

redisson封装实体类RBloomFilter,分析源码同样是使用位图实现的,相关细节可分析源码。
RBloomFilter使用代码示例:

public void test1() {
    String filterName = "filterA";

    RBloomFilter<String> bloomFilter = redissonService.redissonClient().getBloomFilter(filterName);
    bloomFilter.tryInit(1000000L, 0.01);

    bloomFilter.add("value1");
    boolean value1Exists = bloomFilter.contains("value1");
    boolean value2Exists = bloomFilter.contains("value2");

    System.out.println("1. Redisson value1 exists: " + value1Exists);
    System.out.println("1. Redisson value2 exists: " + value2Exists);
}

执行结果:

1. Redisson value1 exists: true
1. Redisson value2 exists: false

4.2. RedisBloom模块

Redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中,所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。还可以使用 docker 可以直接在 redis 中布隆过滤器。

4.2.1 Redis集成布隆过滤器模块

参考网址:

https://oss.redislabs.com/redisbloom/Quick_Start/

(1)安装RedisBloom模块

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make

(2)启动redis-server

修改相应的server、conf、redisbloom.so的路径

./redis-server ./redis.conf --loadmodule ./redisbloom.so

4.2.2 主要命令

命令含义BF.ADD filterName value在过滤器中增加某个valueBF.MADD filterName value1 value2增加多个valueBF.EXISTS filterName value判断过滤器中是否存在某个valueBF.MEXISTS filterName value1 value2判断多个value是否存在BF.RESERVE <error_rate>显式创建过滤器

BF.RESERVE

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

错误率越小,需要的空间越大;预计元素个数越大,需要的空间越大。
示例:

bf.reserve urls 0.01 100

4.2.3 Java使用RedisBloom

在Java中如何使用RedisBloom模块呢?
考虑可以通过lua脚本(或其它可以执行原生Redis命令的方式)执行BF.ADD和BF.EXISTS等命令,RedisBloom官方中还推荐了JReBloom库。

(1)lua脚本执行原生命令

代码示例如下:

public void test2() {
    String filterName = "filterB";
    String addValueScript = "return redis.call('BF.ADD', KEYS[1], ARGV[1]); ";
    redisService.executeLuaScript(addValueScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value1"));

    String valueExistsScript = "return redis.call('BF.EXISTS', KEYS[1], ARGV[1]); ";

    Boolean value1Exists = redisService.executeLuaScript(valueExistsScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value1"));
    Boolean value2Exists = redisService.executeLuaScript(valueExistsScript,
            RScript.ReturnType.BOOLEAN,
            Lists.newArrayList(filterName),
            Lists.newArrayList("value2"));
    System.out.println("2. LuaScript value1 exists: " + value1Exists);
    System.out.println("2. LuaScript value2 exists: " + value2Exists);
}
复制代码

执行结果:

2. LuaScript value1 exists: true
2. LuaScript value2 exists: false

(2)JRedisBloom

引入jar包和仓库:

<dependency>
    <groupId>com.redislabs</groupId>
    <artifactId>jrebloom</artifactId>
    <version>2.0.0-SNAPSHOT</version>
</dependency>
<repository>
    <id>snapshots-repo</id>
    <url>https://oss.sonatype.org/content/repositories/snapshots</url>
</repository>

代码示例:

public void test3() {
    String filterName = "filterC";
    Client client = new Client("localhost", 7379);
    client.add(filterName, "value1");
    boolean value1Exists = client.exists(filterName, "value1"); // true
    boolean value2Exists = client.exists(filterName, "value2"); // False
    System.out.println("3. JRedisBloom value1 exists: " + value1Exists);
    System.out.println("3. JRedisBloom value2 exists: " + value2Exists);
}

执行结果:

3. JRedisBloom value1 exists: true
3. JRedisBloom value2 exists: false

5. 总结

布隆过滤器应用诸多,可用来过滤垃圾邮箱、海量URL识别等。用其来解决Redis缓存穿透问题,也只是缓存穿透问题的一种解决方案。

相关推荐

删库之后不要着急跑路,教你神不知鬼不觉找回数据

在工作中,我们误删数据或者数据库,我们一定需要跑路吗?我看未必,程序员一定要学会自救,神不知鬼不觉的将数据找回。在mysql数据库中,我们知道binlog日志记录了我们对数据库的所有操作,所以...

数据库告警不可用,增删改受阻(数据库限制删除)

前言:昨晚,突然出现服务不可用告警,查看日志上线报文入库到数据库很慢并受阻,出现数据不同步问题。排查问题查看发现服务都是在执行update、insert这些DML命令的时候,报的数据库执行超时。经过一...

Binlog实现MySQL复制,5个关键步骤,务必掌握!

复制是MySQL最重要的功能之一,MySQL集群的高可用、负载均衡和读写分离都是基于复制来实现的。Binlog就是实现主从复制的关键,主数据库将修改操作记录到Binlog中,从数据库通过解...

MySQL数据实时增量同步到Elasticsearch

Mysql到Elasticsearch的数据同步,一般用ETL来实现,但性能并不理想,目前大部分的ETL是定时查询Mysql数据库有没有新增数据或者修改数据,如果数据量小影响不大,但如果几百万上千万的...

MySQL 数据库恢复:如何执行时间点恢复(PITR)以挽救受损数据?

天津鸿萌科贸发展有限公司从事数据安全服务二十余年,致力于为各领域客户提供专业的数据恢复、数据备份、数据取证、数据迁移、网络安全、数据清除等解决方案,并针对企业面临的数据安全风险,提供专业的相关数据安全...

阿里面试:MySQL Binlog有哪些格式?底层原理?优缺点?

binlog的格式也有三种:STATEMENT、ROW、MIXED,下面我详解binlog三种模式@mikechenStatement模式Statement模式:是基于SQL语句的复制(statem...

快速带你读懂MySQL的binlog写入机制

深入讲解MySQL中的重要日志binlog的写入机制以及影响IO性能的关键配置,并且介绍了如何利用binlog去恢复数据,保证MySQL的可靠性。Q:binlog写入时机binlog的写入逻辑并...

MySQL 误删除数据恢复全攻略:基于 Binlog 的实战指南

在MySQL的世界里,二进制日志(Binlog)就是我们的"时光机"。它默默记录着数据库的每一个重要变更,就像一位忠实的史官,为我们在数据灾难中提供最后的救命稻草。本文将带您深入掌握如...

一文了解MySQL Binlog(一文了解肝脏有益和有害的食物)

MySQL的Binlog日志是一种二进制格式的日志,Binlog记录所有的DDL和DML语句(除了数据查询语句SELECT、SHOW等),以Event的形式记录,同时记录语句执行时...

数据丢失?别慌!MySQL备份恢复攻略

想象一下,某个晴朗的午后,你正享受着咖啡,突然接到紧急电话:你的网站或APP彻底挂了!系统崩溃,界面全白。虽然心头一紧,但你或许还能安慰自己:系统崩溃只是暂停服务,数据还在,修复修复就好了。然而,如果...

Mysql中的bin log、redo log、undo log的区别

最近在整理面试题,在看mvcc的时候看到了undolog,今天索性把这三个log都记录一遍。MySQL的逻辑架构说之前先说一下MySQL的基本架构,MySQL主要分为两层:Server层和存储引...

binlog日志定时清理(binlog清理规则)

binlog日志binlog是MySQL数据库的一种日志文件,用于记录所有对数据的修改操作。binlog全称为binarylog,它以二进制格式记录MySQL服务器上所有的修改操作,包括对哪个数据库...

茶水间炸锅了!菜鸟误删用户表,运维老张的MySQL救命三招!

(公司茶水间,运维老张、开发小王和新人小李围着咖啡机)小李:(紧张兮兮)张哥!我...我好像把测试库的用户表删了!下午演示咋办啊?老张:(淡定喝咖啡)慌啥?昨晚的备份是吃干饭的?走,教你恢复!一、基础...

解决运维痛点,提高运维安全性-雷池 SafeLine WAF新功能身份认证

雷池介绍使用雷池SafeLineWAF已经两年多了,在1.5.x版本时就已经开始测试使用,并在推出LTS版本后转入LTS分支。近期雷池SafeLineWAF重点更新了身份认证功能,并提供了SS...

【Docker 新手入门指南】第十五章:常见故障排除

一、前期准备:收集关键信息在排查问题前,建议先获取以下系统数据,便于精准定位故障:1.系统基础信息#查看Docker版本(确认是否为最新稳定版)dockerversion#查看...

取消回复欢迎 发表评论: