Redis布隆过滤器BloomFilter

2023-12-26 07:26:59
  • 👏作者简介:大家好,我是爱吃芝士的土豆倪,24届校招生Java选手,很高兴认识大家
  • 📕系列专栏:Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术
  • 🔥如果感觉博主的文章还不错的话,请👍三连支持👍一下博主哦
  • 🍂博主正在努力完成2023计划中:源码溯源,一探究竟
  • 📝联系方式:nhs19990716,加我进群,大家一起学习,一起进步,一起对抗互联网寒冬👀

Redis布隆过滤器BloomFilter

经典面试题

  • 现有50亿个电话号码,现有10个电话号码,如何要快速准确的判断这些电话号码是否已经存在?

1、通过数据库查询-------实现快速有点难。

2、数据预放到内存集合中:50亿*8字节大约40G,内存太大了。

  • 判断是否存在,布隆过滤器了解过吗?
  • 安全连接网址,全球数10亿的网址判断
  • 黑名单校验,识别垃圾邮件
  • 白名单校验,识别出合法用户进行后续处理

简介

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

在这里插入图片描述

目的减少内存占用
方式不保存数据信息,只是在内存中做一个是否存在的标记flag

本质上就是判断具体数据是否存在于一个大的集合中

布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。

它实际上是一个很长的二进制数组(00000000)+一系列随机hash算法映射函数,主要用于判断一个元素是否在集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景,一般想到的是将集合中所有元素保存起来,然后通过比较确定。

链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间也会呈现线性增长,最终达到瓶颈。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时候,布隆过滤器(Bloom Filter)就应运而生

作用

高效地插入和查询,占用空间少,返回的结果是不确定性+不够完美

重点:一个元素如果判定结果:存在时,元素不一定存在,但是判断结果为不存在时,则一定不存在

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

总结

如果存在,是可能存在

如果不存在,则一定不存在,可以保证的是,如果布隆过滤器判断一个元素不在一个集合中,那么这个元素一定不会在集合中

原理

基本原理和数据结构

布隆过滤器原理

布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。

实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成,用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样,它也一样有那么一点点不精确,也存在一定的误判概率

添加key时

使用多个hash函数对key进行hash运算得到一个整数索引值,对位数组长度进行取模运算得到一个位置,

每个hash函数都会得到一个不同的位置,将这几个位置都置1就完成了add操作。

查询key时

只要有其中一位是零就表示这个key不存在,但如果都是1,则不一定存在对应的key。

结论:有,是可能有 无,是肯定无

hash冲突导致数据不准确

当有变量被加入集合时,通过N个映射函数将这个变量映射成位图中的N个点,

把它们置为 1(假定有两个变量都通过 3 个映射函数)。

在这里插入图片描述

查询某个变量的时候我们只要看看这些点是不是都是 1, 就可以大概率知道集合中有没有它了

如果这些点,有任何一个为零则被查询变量一定不在,

如果都是 1,则被查询变量很可能存在,

为什么说是可能存在,而不是一定存在呢?那是因为映射函数本身就是散列函数,散列函数是会有碰撞的。(见上图3号坑两个对象都1)

在这里插入图片描述

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

在这里插入图片描述

如果两个散列值是不相同的(根据同一函数)那么这两个散列值的原始输入也是不相同的。

这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。

散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,

这种情况称为“散列碰撞(collision)”。

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

使用步骤

布隆过滤器 本质上 是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为 0

在这里插入图片描述

当我们向布隆过滤器中添加数据时,为了尽量地址不冲突,会使用多个 hash 函数对 key 进行运算,算得一个下标索引值,然后对位数组长度进行取模运算得到一个位置,每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

例如,我们添加一个字符串wmyskxz,对字符串进行多次hash(key) → 取模运行→ 得到坑位

在这里插入图片描述

向布隆过滤器查询某个key是否存在时,先把这个 key 通过相同的多个 hash 函数进行运算,查看对应的位置是否都为 1,

只要有一个位为零,那么说明布隆过滤器中这个 key 不存在;

如果这几个位置全都是 1,那么说明极有可能存在;

因为这些位置的 1 可能是因为其他的 key 存在导致的,也就是前面说过的hash冲突。。。。。

就比如我们在 add 了字符串wmyskxz数据之后,很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的;

此时我们查询一个没添加过的不存在的字符串inexistent-key,它有可能计算后坑位也是1/3/5 ,这就是误判了…笔记见最下面

在这里插入图片描述

布隆过滤器误判率,为什么不要删除

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了,这样就无法判断究竟是哪个输入产生的,

因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题,因为布隆过滤器的每一个 bit 并不是独占的,很有可能多个元素共享了某一位

如果我们直接删除这一位的话,会影响其他的元素

特性

布隆过滤器可以添加元素,但是不能删除元素。因为删掉元素会导致误判率增加。

小总结

是否存在:有,是很可能有,无,是肯定无

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

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

使用场景

解决缓存穿透问题,和redis结合bitmap使用

缓存穿透是什么

一般情况下,先查询缓存redis是否有该条数据,缓存中没有时,再查询数据库。

当数据库也不存在该条数据时,每次查询都要访问数据库,这就是缓存穿透。

缓存透带来的问题是,当有大量请求查询数据库不存在的数据时,就会给数据库带来压力,甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题

把已存在数据的key存在布隆过滤器中,相当于redis前面挡着一个布隆过滤器。

当有新的请求时,先到布隆过滤器中查询是否存在:

如果布隆过滤器中不存在该条数据则直接返回;

如果布隆过滤器中已存在,才去查询缓存redis,如果redis里没查询到则再查询Mysql数据库

在这里插入图片描述

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

发现存在黑名单中的,就执行特定操作。比如:识别垃圾邮件,只要是邮箱在黑名单中的邮件,就识别为垃圾邮件。

假设黑名单的数量是数以亿计的,存放起来就是非常耗费存储空间的,布隆过滤器则是一个较好的解决方案。

把所有黑名单都放在布隆过滤器中,在收到邮件时,判断邮件地址是否在布隆过滤器中即可。

布隆过滤器实现步骤

结合bitmap类型手写一个简单的布隆过滤器,体会设计思想

在这里插入图片描述

设计步骤

redis的setbit/getbit

在这里插入图片描述

setbit构建过程
  • @PostConstruct初始化白名单数据
  • 计算元素的hash值
  • 通过上一步hash值算出对应的二进制数组的坑位
  • 将对应坑位的值修改为数字1,表示存在
getbit查询是否存在
  • 计算元素的hash值
  • 通过上一步hash值算出对应的二进制数组的坑位
  • 返回对应坑位的值,零表示无,1表示存在

文章来源:https://blog.csdn.net/qq_40851232/article/details/135197017
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。