吃透Redis系列(四):布隆(bloom)过滤器详细介绍

2024-09-03 01:32

本文主要是介绍吃透Redis系列(四):布隆(bloom)过滤器详细介绍,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Redis系列文章:

吃透Redis系列(一):Linux下Redis安装

吃透Redis系列(二):Redis六大数据类型详细用法

吃透Redis系列(三):Redis管道,发布/订阅,事物,过期时间 详细介绍

吃透Redis系列(四):布隆(bloom)过滤器详细介绍

吃透Redis系列(五):RDB和AOF持久化详细介绍

吃透Redis系列(六):主从复制详细介绍

吃透Redis系列(七):哨兵机制详细介绍

吃透Redis系列(八):集群详细介绍

吃透Redis系列(九):Redis代理twemproxy和predixy详细介绍

吃透Redis系列(十):Redis内存模型详细介绍

吃透Redis系列(十一):Jedis和Lettuce客户端详细介绍

文章目录

      • 布隆过滤器应用场景
      • 布隆过滤器简介
        • 1,添加数据
        • 2,判断数据是否存在?
        • 3,布隆过滤器优缺点
      • Redis实现布隆过滤器
      • Redis安装布隆过滤器模块
        • 1,访问github地址,下载模块源码
        • 2,执行make编译动态库
        • 3,启动redis加载该动态库
      • Redis使用布隆过滤器
        • 1,常用命令
        • 2,布隆过滤器准确率
        • 3,在项目中使用

本篇博客我们主要介绍如何用Redis实现布隆过滤器,但是在介绍布隆过滤器之前,我们首先介绍一下,为啥要使用布隆过滤器。

布隆过滤器应用场景

  • 解决缓存穿透的问题

一般情况下,先查询缓存是否有该条数据,缓存中没有时,再查询数据库。当数据库也不存在该条数据时,每次查询都要访问数据库,这就是缓存穿透。缓存穿透带来的问题是,当有大量请求查询数据库不存在的数据时,就会给数据库带来压力,甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题,把已存在数据的key存在布隆过滤器中。当有新的请求时,先到布隆过滤器中查询是否存在,如果不存在该条数据直接返回;如果存在该条数据再查询缓存查询数据库。

  • 黑名单校验

发现存在黑名单中的,就执行特定操作。比如:识别垃圾邮件,只要是邮箱在黑名单中的邮件,就识别为垃圾邮件。假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中,再收到邮件时,判断邮件地址是否在布隆过滤器中即可。

**场景一:**原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中?

解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了,但是速度会比较慢。

解决办法二:将10亿号码放入内存中,比如Redis缓存中,这里我们算一下占用内存大小:10亿*8字节=8GB,通过内存查询,准确性和速度都有了,但是大约8gb的内存空间,挺浪费内存空间的。

**场景二:**购物网站搜索商品,客户在商品搜索栏输入商品,首先要判断此商品在我数据库中存不存在,如果存在才会去执行数据库查询操作!

那么对于类似这种,大数据量集合,如何准确快速的判断某个数据是否在大数据量集合中,并且不占用内存,布隆过滤器应运而生了。

布隆过滤器简介

带着上面的几个疑问,我们来看看到底什么是布隆过滤器。

布隆过滤器:一种数据结构,是由一串很长的二进制向量组成,可以将其看成一个二进制数组。既然是二进制,那么里面存放的不是0,就是1,但是初始默认值都是0。

如下所示:

在这里插入图片描述

1,添加数据

介绍概念的时候,我们说可以将布隆过滤器看成一个容器,那么如何向布隆过滤器中添加一个数据呢?

如下图所示:当要向布隆过滤器中添加一个元素key时,我们通过多个hash函数,算出一个值,然后将这个值所在的方格置为1。

比如,下图hash1(key)=1,那么在第2个格子将0变为1(数组是从0开始计数的),hash2(key)=7,那么将第8个格子置位1,依次类推。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5gSG4wfS-1610099908069)(/home/bobo/.config/Typora/typora-user-images/image-20210108084745498.png)]

2,判断数据是否存在?

知道了如何向布隆过滤器中添加一个数据,那么新来一个数据,我们如何判断其是否存在于这个布隆过滤器中呢?

很简单,我们只需要将这个新的数据通过上面自定义的几个哈希函数,分别算出各个值,然后看其对应的地方是否都是1,如果存在一个不是1的情况,那么我们可以说,该新数据一定不存在于这个布隆过滤器中。

反过来说,如果通过哈希函数算出来的值,对应的地方都是1,那么我们能够肯定的得出:这个数据一定存在于这个布隆过滤器中吗?

答案是否定的,因为多个不同的数据通过hash函数算出来的结果是会有重复的,所以会存在某个位置是别的数据通过hash函数置为的1。

我们可以得到一个结论:布隆过滤器可以判断某个数据一定不存在,但是无法判断一定存在

3,布隆过滤器优缺点

优点:优点很明显,二进制组成的数组,占用内存极少,并且插入和查询速度都足够快。

缺点:随着数据的增加,误判率会增加;还有无法判断数据一定存在;另外还有一个重要缺点,无法删除数据。

Redis实现布隆过滤器

在Redis中是用bitmap来实现布隆过滤器的!

bitmap

我们知道计算机是以二进制位作为底层存储的基础单位,一个字节等于8位。

比如“big”字符串是由三个字符组成的,这三个字符对应的ASCII码分为是98、105、103,对应的二进制存储如下:

在这里插入图片描述

在Redis中,Bitmaps 提供了一套命令用来操作类似上面字符串中的每一个位。

设置值

setbit key offset value
127.0.0.1:6379> set k1 big
OK
127.0.0.1:6379> setbit k1 7 1
(integer) 0
127.0.0.1:6379> get k1
"cig"
127.0.0.1:6379> 

我们知道"b"的二进制表示为0110 0010,我们将第7位(从0开始)设置为1,那0110 0011 表示的就是字符“c”,所以最后的字符 “big”变成了“cig”。

获取位图指定范围值为1的个数

bitcount key [start end]

如果不指定,那就是获取全部值为1的个数。

注意:start和end指定的是字节的个数,而不是位数组下标。

127.0.0.1:6379> set k1 big
OK
127.0.0.1:6379> bitcount k1
(integer) 12
127.0.0.1:6379> bitcount k1 0 0
(integer) 3
127.0.0.1:6379> bitcount k1 0 1
(integer) 7
127.0.0.1:6379> 

Redis安装布隆过滤器模块

1,访问github地址,下载模块源码

https://github.com/RedisBloom/RedisBloom

直接用git clone或则下载zip

git clone https://github.com/RedisBloom/RedisBloom.git
2,执行make编译动态库
cd RedisBloom
make

执行完成之后,会生成一个redisbloom.so动态库

3,启动redis加载该动态库
# 我习惯把该库放到redis的安装目录下,这步骤看自己喜好
sudo cp redisbloom.so /opt/redis/
# 先停掉redis进程
sudo kill -9 pid
# 加载动态库
redis-server --loadmodule /opt/redis/redisbloom.so

出现下图显示加载完成:

在这里插入图片描述

然后就可以用redis-cli客户端来连接测试了

Redis使用布隆过滤器

1,常用命令

bf.add 添加元素

bf.exists 查询元素是否存在

bf.madd 一次添加多个元素

bf.mexists 一次查询多个元素是否存在

127.0.0.1:6379> bf.add k1 1
(integer) 1
127.0.0.1:6379> bf.add k1 2
(integer) 1
127.0.0.1:6379> bf.exists k1 1
(integer) 1
127.0.0.1:6379> bf.exists k1 5
(integer) 0
127.0.0.1:6379>
2,布隆过滤器准确率

在 redis 中有两个值决定布隆过滤器的准确率:

error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。

initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值:

bf.reserve test 0.01 100 

第一个值是过滤器的名字。

第二个值为 error_rate 的值。

第三个值为 initial_size 的值。

注意必须在add之前使用bf.reserve指令显式创建,如果对应的 key 已经存在,bf.reserve会报错。同时设置的错误率越低,需要的空间越大。如果不使用 bf.reserve,默认的error_rate是 0.01,默认的initial_size是 100。

3,在项目中使用

3.1

引入包

<dependency><groupId>com.redislabs</groupId><artifactId>jrebloom</artifactId><version>1.0.2</version>
</dependency>

JAR包里只有三个类,对连接方式 和 数据类型 的支持都不够

代码:

Client client = new Client(redisProperties.getHost(), redisProperties.getPort(), 10000, 100);
client.add("bobo", "123");
boolean bo = client.exists("bobo", "123");
System.out.println(bo);

3.2:Guava中的BloomFilter

google的guava包中提供了BloomFilter类,直接用的是服务器内存

导入包

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

代码:

private static int size = 1000000;
private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.0001);public void test2() {String bo = "bobo";bloomFilter.put(bo);System.out.println(bloomFilter.mightContain(bo));
}

这篇关于吃透Redis系列(四):布隆(bloom)过滤器详细介绍的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131639

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Redis中的常用的五种数据类型详解

《Redis中的常用的五种数据类型详解》:本文主要介绍Redis中的常用的五种数据类型详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis常用的五种数据类型一、字符串(String)简介常用命令应用场景二、哈希(Hash)简介常用命令应用场景三、列表(L

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Python实现html转png的完美方案介绍

《Python实现html转png的完美方案介绍》这篇文章主要为大家详细介绍了如何使用Python实现html转png功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 1.增强稳定性与错误处理建议使用三层异常捕获结构:try: with sync_playwright(