布隆过滤器应用——解决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#查看...
你 发表评论:
欢迎- 一周热门
-
-
极空间如何无损移机,新Z4 Pro又有哪些升级?极空间Z4 Pro深度体验
-
UOS服务器操作系统防火墙设置(uos20关闭防火墙)
-
如何修复用户配置文件服务在 WINDOWS 上登录失败的问题
-
手机如何设置与显示准确时间的详细指南
-
如何在安装前及安装后修改黑群晖的Mac地址和Sn系列号
-
日本海上自卫队的军衔制度(日本海上自卫队的军衔制度是什么)
-
爱折腾的特斯拉车主必看!手把手教你TESLAMATE的备份和恢复
-
10个免费文件中转服务站,分享文件简单方便,你知道几个?
-
NAS:DS video/DS file/DS photo等群晖移动端APP远程访问的教程
-
FANUC 0i-TF数据备份方法(fanuc系统备份教程)
-
- 最近发表
- 标签列表
-
- linux 查询端口号 (58)
- docker映射容器目录到宿主机 (66)
- 杀端口 (60)
- yum更换阿里源 (62)
- internet explorer 增强的安全配置已启用 (65)
- linux自动挂载 (56)
- 禁用selinux (55)
- sysv-rc-conf (69)
- ubuntu防火墙状态查看 (64)
- windows server 2022激活密钥 (56)
- 无法与服务器建立安全连接是什么意思 (74)
- 443/80端口被占用怎么解决 (56)
- ping无法访问目标主机怎么解决 (58)
- fdatasync (59)
- 405 not allowed (56)
- 免备案虚拟主机zxhost (55)
- linux根据pid查看进程 (60)
- dhcp工具 (62)
- mysql 1045 (57)
- 宝塔远程工具 (56)
- ssh服务器拒绝了密码 请再试一次 (56)
- ubuntu卸载docker (56)
- linux查看nginx状态 (63)
- tomcat 乱码 (76)
- 2008r2激活序列号 (65)