吃透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

相关文章

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

SpringBoot中配置Redis连接池的完整指南

《SpringBoot中配置Redis连接池的完整指南》这篇文章主要为大家详细介绍了SpringBoot中配置Redis连接池的完整指南,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以... 目录一、添加依赖二、配置 Redis 连接池三、测试 Redis 操作四、完整示例代码(一)pom.

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Redis在windows环境下如何启动

《Redis在windows环境下如何启动》:本文主要介绍Redis在windows环境下如何启动的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis在Windows环境下启动1.在redis的安装目录下2.输入·redis-server.exe