我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Redis 布隆(Bloom Filter)过滤器原理与实战

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Redis 布隆(Bloom Filter)过滤器原理与实战

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

如下图所示:

布隆过滤器原理

哈希函数会出现碰撞,所以布隆过滤器会存在误判。

这里的误判率是指,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
Redis server v=6.2.6 sha=00000000:0 malloc=libc bits=64 build=b5524b65e12bbef5

下载

我们自己编译安装,需要从 github 下载,目前的 release 版本是 v2.2.14,下载地址:https://github.com/RedisBloom/RedisBloom/releases/tag/v2.2.14。

Redis 布隆

解压编译

解压:

tar -zxvf RedisBloom-2.2.14.tar

编译插件:

cd RedisBloom-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.RESERVE orders 0.1 10000000
  • key:filter 的名字。
  • error_rate:期望的错误率,默认 0.1,值越低,需要的空间越大。
  • capacity:初始容量,默认 100,当实际元素的数量超过这个初始化容量时,误判率上升。
  • EXPANSION:可选参数,当添加到布隆过滤器中的数据达到初始容量后,布隆过滤器会自动创建一个子过滤器,子过滤器的大小是上一个过滤器大小乘以 expansion;expansion 的默认值是 2,也就是说布隆过滤器扩容默认是 2 倍扩容。
  • NONSCALING:可选参数,设置此项后,当添加到布隆过滤器中的数据达到初始容量后,不会扩容过滤器,并且会抛出异常((error) ERR non scaling filter 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 依赖:

<dependency>
<groupId>org.redissongroupId>
<artifactId>redisson-spring-boot-starterartifactId>
<version>3.16.7version>
dependency>

使用 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;

public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) {
RBloomFilter<T> 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<Long> 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")。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Redis 布隆(Bloom Filter)过滤器原理与实战

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Redis 布隆(Bloom Filter)过滤器原理与实战

布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出,它是一种 space efficient 的概率型数据结构,用于判断一个元素是否在集合中。

Redis中Bloom filter布隆过滤器的学习

目录1.概念2.guava实现2.1.依赖2.2.初始化布隆过滤器2.3.布隆过滤器2.4.添加元素或者判断是否存在3.Redisson实现3.1.依赖3.2.注入或测试1.概念​ 布隆过滤器是一个高空间利用率的概率性数据结构,主要目的是
2022-12-14

图解布隆过滤器和布谷鸟过滤器实现原理

我们元数据通过两个哈希函数函数之后得到2和7两个值,然后将2和7这个两个值对应的bit位上的值设置为1,这样我们就将元数据存放到布隆过滤器上。

redis布隆过滤器的工作原理是什么

Redis布隆过滤器是一种数据结构,用于快速判断一个元素是否存在于一个集合中。它基于位数组和多个哈希函数实现。工作原理如下:初始化:布隆过滤器包含一个位数组,所有位都初始化为0。同时,需要选择合适数量的哈希函数和哈希函数的种子。添加元素
redis布隆过滤器的工作原理是什么
2024-04-09

基于php+redis实现布隆过滤器

本文详细介绍了基于PHP+Redis实现布隆过滤器的方法,该过滤器是一种概率性数据结构,用于快速判断元素是否存在集合中。Redis提供原生布隆过滤器支持,可以使用自定义PHP类简化其使用。布隆过滤器具有高空间效率、快速查找、近似查询和可扩展性等优势,但也有误报、不可变和不支持删除的局限性。通过利用Redis布隆过滤器,开发人员可以优化PHP应用程序的集合成员资格测试和存储需求。
基于php+redis实现布隆过滤器
2024-04-02

SpringBoot+Redis如何实现布隆过滤器

小编给大家分享一下SpringBoot+Redis如何实现布隆过滤器,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!简述关于布隆过滤器的详细介绍,我在这里就不再赘述一遍了我们首先知道:BloomFilter使用长度为m bi
2023-06-29

Java布隆过滤器的原理和实现分析

数组、链表、树等数据结构会存储元素的内容,一旦数据量过大,消耗的内存也会呈现线性增长所以布隆过滤器是为了解决数据量大的一种数据结构。本文就来和大家详细说说布隆过滤器的原理和实现,感兴趣的可以了解一下
2022-11-13

Java中的布隆过滤器原理实现和应用

Java中的布隆过滤器是一种基于哈希函数的数据结构,能够高效地判断元素是否存在于一个集合中。它广泛应用于缓存、网络协议、数据查询等领域,在提高程序性能和减少资源消耗方面具有显著优势
2023-05-17

Redis处理高并发之布隆过滤器详解

这篇文章主要为大家介绍了Redis处理高并发之布隆过滤器详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
2022-12-29

冷饭新炒:理解布隆过滤器算法的实现原理

布隆过滤器是「一种空间高效概率性的数据结构」(百科中原文是a space-efficient probabilistic data structure),该数据结构于1970年由Burton Howard Bloom提出,「作用是测试一个元

布隆过滤器的原理以及使用场景

布隆过滤器主要是在redis中问的比较多,因此像这种数据结构类的,主要是考原理以及使用场景。下面一点一点开始逐步介绍。

Redis布隆过滤器的原理和应用场景,解决缓存穿透

布隆过滤器BloomFilter是一种专门用来解决去重问题的高级数据结果。

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录