【Redis从入门到入土】布隆过滤器简介、特点和原理

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云原生内存数据库 Tair,内存型 2GB
云数据库 Redis 版,经济版 1GB 1个月
简介: 【6月更文挑战第1天】布隆过滤器是一种节省内存的不确定数据结构,用于判断元素是否可能在一个集合中。它由位数组和多个哈希函数组成,能快速插入和查询,但存在误判风险:可能存在假阳性(判断存在但实际不存在),但绝无假阴性(判断不存在则确实不存在)。适用于大规模数据的去重问题,如电话号码判断、安全网站链接检查、黑名单和白名单校验。其工作原理是通过多个哈希函数将元素映射到位数组中,添加时设置相应位置为1,查询时所有位置都为1则可能存在,有0则肯定不存在。由于哈希冲突,可能导致误判,且一旦添加元素无法删除,以避免影响其他元素。

面试场景题

  1. 共有50亿个电话号码,现在有10万个电话号码,如何要快速准确的判断这些电话号码是否已经存在?
  1. 通过数据库查询 -- 无法实现快速

  2. 数据预放到内存集合里,50亿*8字节大概40G,占用的内存很大

  1. 判断是否存在,布隆过滤器了解过吗

  2. 安全连接网站,全球数10亿的网址判断

  3. 黑名单校验,识别垃圾邮件

  4. 白名单校验,识别出合法用户进行后续处理

简介

由一个初值都为0的bit数组和多个哈希函数构成,用来快速判断集合中是否存在某个元素。

设计思想:目的是减少内存占用;实现方式是不保存数据信息,只是在内存中做一个是否存在的标记flag。

备注:布隆过滤器是一种类似set的数据结构,只是统计结果在巨量数据下有点小瑕疵,不够完美。

通常情况下我们会遇到很多要判断一个元素是否在某个集合中的业务场景,一般想到的是将集合中的所有元素保存起来,然后通过比较进行确定。比如链表、树、哈希表等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间也会呈现线性增长,最终速度也会越来越慢,上述三种结构的检索时间复杂度分别是O(n),O(logn),O(1)

特点

可以高效地插入和查询,占用空间少,但是返回的结果是不确定性的。

一个元素进行判断的时候,如果判断结果是存在,那么结果不一定存在;但是如果判断结果为不存在,则一定不存在。

原因:通过哈希算法后可能会存在冲突,在某一位上为1,也可能是别的元素存在导致这一位为1

布隆过滤器可以添加元素,但不能删除元素。由于涉及hashcode判断依据,删掉元素可能会导致误判率增加。

实现原理和数据结构

是一种专门来解决去重问题的高级数据结构,实质上就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。

添加key时

使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,每个hash函数都会得到一个不同的位置,将这几个位置都置为1就完成了add操作。

查询key时

只要有一位为0就表示这个key不存在;但是如果都是1,则不一定存在对应的key

hash冲突导致数据不精准

当有变量被加入集合时,通过N个映射函数将这个变量映射成位图中的N个点,把他们设置为1。假设有两个变量都通过三个映射函数。

查询某个变量的时候,我们只需要看看这些点是不是都是1,就可以知道是否存在了。

2024-05-27-21-23-24-image.png

如果这些点,有任何一个值为0则查询变量一定不存在;但是如果都是1,则查询变量可能存在。原因是映射函数本身就是散列函数,散列函数是会有碰撞的。

改进应用:

因为布隆过滤器的快速检测特性,我们可以把数据写入数据库时,使用布隆过滤器做个标记。当缓存缺失后,应用查询数据库时,可以通过查询布隆过滤器快速判断数据是否存在。如果不存在,就不用去数据库查询了。这种情况下,即使发生缓存穿透,大量请求也只会查询Redis和布隆过滤器,而不会积压到数据库,就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现,本身就能承担较大的并发访问压力。

哈希函数

哈希函数的概念是将任意大小的输入数据转换成特定大小的输出数据的函数,转换后的数据称为哈希值或散列值。

2024-05-27-21-31-51-image.png

如果两个散列值是不相同的,根据统一函数,那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数

散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也很可能不同,这种情况称为散列碰撞

用hash表存储大数据量时,空间效率还是很低,当只有一个hash函数时,很容易发送散列碰撞。

使用

初始化bitmap

所有位置全部初始化为0

添加占坑位

添加数据的时候,为了尽量地址不冲突,**使用多个hash函数对key进行运算**,得到下标索引值,对数组长度进行取模运算得到位置,每个hash函数都会得到一个不同的位置,再把位数组的这几位设置为1就完成了add操作。

判断是否存在

查询某个key是否存在的时候,先把这个key通过**相同的多个hash函数**进行运算,查看对应的位置是否都是1,只要有一个位是0,就说明布隆过滤器里这个key**不存在**;如果这几个位置全部是1,那么说明**可能存在**。

思考

思考1:为什么尽量避免在布隆过滤器删除元素?

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位设置位1了,这样就无法判断究竟是哪个输入产生的。因此误判的根源在于相同的bit位被多次映射且设置为1

这种情况也造成了布隆过滤器的删除问题,因为布隆过滤器的每一个bit都不是独占的,很有可能多个元素共享了某一位。如果直接删除这一位的话,会影响其他的元素,增加误判率。

思考2:使用技巧

不要让实际元素数量远大于初始化数量,一次给够避免扩容;

当实际元素数量超过初始化数量时,应该对布隆过滤器进行重建,重新分配一个size更大的过滤器,再将所有历史元素批量add进行。用重建替代删除

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
25天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
46 1
|
25天前
|
NoSQL Java Redis
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
Redis系列学习文章分享---第十八篇(Redis原理篇--网络模型,通讯协议,内存回收)
37 0
|
25天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
38 0
|
7天前
|
NoSQL Redis 数据库
|
25天前
|
NoSQL 容灾 Redis
Redis系列学习文章分享---第十一篇(Redis高级实战篇---RDB演示 +RDB的fork原理+A0F演示 +RDB和AOF)
Redis系列学习文章分享---第十一篇(Redis高级实战篇---RDB演示 +RDB的fork原理+A0F演示 +RDB和AOF)
22 0
|
26天前
|
存储 缓存 NoSQL
Redis为什么速度快:数据结构、存储及IO网络原理总结
Redis为什么速度快:数据结构、存储及IO网络原理总结
|
1月前
|
存储 NoSQL Linux
Linux下Redis简介、安装、设置、启动
Linux下Redis简介、安装、设置、启动
27 0
|
2月前
|
存储 缓存 NoSQL
由菜鸟到大神,谈谈redis的概念、实战、原理、高级使用方法
【5月更文挑战第18天】Redis是一个开源的内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串、哈希、列表、集合、有序集合等。
42 10
|
1月前
|
消息中间件 NoSQL Linux
详解Redis的主从同步原理
只不过在主节点中叫做master_repl_offset; 从节点也有一个偏移量叫做slave_repl_offset,用来记录从节点已经从主节点的repl_backlog_buffer中同步到的最新写指令的位置;
237 0
|
2月前
|
监控 NoSQL 算法
深入剖析Redis哨兵模式的原理和应用
Redis的哨兵模式是实现高可用性和自动故障转移的机制,当主服务器故障时,哨兵能自动检测并进行故障转移,确保服务连续和稳定性。哨兵模式通过监控主从服务器状态、自动故障转移、防止数据不一致,提高容错能力和负载均衡,降低运维成本,实现高可用性。哨兵通过检测主观下线和客观下线状态,以及选举Leader Sentinel来协调故障转移。Raft算法在其中用于领导者选举和状态一致性。哨兵模式通过综合考虑多种因素选举新主服务器并执行故障转移,保障集群稳定运行。
360 0
深入剖析Redis哨兵模式的原理和应用