布隆过滤器的原理和使用场景详解

什么是布隆过滤器?

布隆过滤器是一种数据结构,特点是高效的插入和查询,而且非常节省空间。通过对位(bit)的操作,可以用来告诉你”某个值一定不存在或者可能存在“。相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是 hash 碰撞造成的误判。

场景

一般使用较多的场景就是避免缓存穿透,具体场景就是:在使用 Reids 做数据缓存的时候,很有可能会遇到一个问题:用户想要查询一个数据,发现 redis 缓存没有命中,于是向数据库查询。发现也没有,于是本次查询失败。当用户很多的时候,缓存都没有命中,于是都去请求数据库。这会给数据库造成很大的压力,这时候就相当于出现了缓存穿透。缓存穿透也是实际开发中必须要避免和提前预防的内容之一。

避免缓存穿透,有以下几种解决方案:

1、缓存空值。
当数据库查询不到数据时,也往缓存里写入空值,这样可以避免大量请求命中数据库。但缺点很明显,如果空值需要被缓存,意味着需要存储更多的 key 。而且即使对空值设置了过期时间,还会照成业务上的不一致。此种用法较初级,不推荐使用。

2、使用 HashMap。
将需要查询的 key 提前加载到 HashMap 中,因为 HashMap 查找的时间复杂度为 O(1) ,因此通过映射可以快速查找到相应的 Key 来判定 Key 是否存在 ,如果查不出来就没必要继续查找缓存了。但是这样做的话极其消耗宝贵的内存,数据量大的情况下成本也会上升。此种做法会对内容造成不可测的负担,不推荐使用。

3、使用 Bloom Filter。
原理上和使用 HashMap 一样,但更省空间。此种做法为主流做法,推荐使用布隆过滤器。

布隆过滤器的存储机制及数据结构

了解布隆过滤器原理之前,先回顾下 Hash 函数原理。

哈希函数

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



所有散列函数都有如下基本特性:

  • 如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数
  • 散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”。

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


布隆过滤器数据结构

BloomFilter 是由一个固定大小的二进制向量或者位图(bitmap)和一系列映射函数组成的。在初始状态时,对于长度为 m 的位数组,它的所有位都被置为0,如下图所示:

如果我们要映射一个值到布隆过滤器中,我们要使用 hash 算法,对 key 生成多个哈希值,生成的哈希值与布隆过滤器的位数组下标相对应,并将位从 0 更改为 1

假设现在有 3 个 key:分表为 a, b, c
将 a,b 映射到过滤器中,此时过滤器的状态如下:

当设置了过滤器,我们在查询 key 的时候首先会以同样的方法计算出 key 的哈希值,然后在过滤器中从查找,这样 a 的哈希值 1 4 6 对应的位都是 1 ,表明这个 key 是可能存在的,可以查询缓存或者数据库,而 c 的哈希值 3 6 7 所对应的位为有两个是 0,表明这个 key 是绝对不存在的,这时就可以直接返回结果给客户端,避免了空值查询数据库。

值得注意的是,固定长度的过滤器 key 存储的越多,hash 碰撞的几率就越大,越容易产生误判,比如说 c 哈希的值映射到位上碰巧都是1,那么即使 c 不存在,也有可能被误判存在。因此设置合适的数组长度也是需要考虑的,数组越大,误判的几率越小。

显而易见,如果布隆过滤器告诉你不存在,那么它肯定就不存在了,不然怎么会有某一个 hash 函数的值在位数组中不为 1 呢。

但是布隆过滤器告诉你存在,它却不一定存在。 因为当布隆过滤器中存储的数据越来越多,位数组的长度是有限的,那么就有可能多个不同的值哈希出来的值是一样的,就比如上图中的自左至右的第二个1其实就是两个不同的 key 哈希出相同的情况。

当 key 越来越多的情况下,就会出现某个 key 明明不存在,但是它在每个 hash 函数的结果都被其他 key 置为 1 的情况,这其实就是布隆过滤器误报的原因。

通过上面介绍可知,布隆过滤器包含两大部分,一个位数组,以及多个无偏 Hash 函数而对于如何减小误判率,也是从这2个角度来进行的,适当增加位数组的长度,已经增加无偏hash函数。

布隆过滤器的使用场景

Java 中的布隆过滤器常见的是 Guava 实现,在代码中直接引入相关API即可。但是,这种写法有使用场景,只能再单即的场景下使用,对于微服务多实例的场景下不能使用,微服务场景下的解决方案是借助redis在事项过滤器。具体代码及实现后续会有专门的文章来介绍,欢迎持续关注。


以上为全部内容。


祝:五一快乐。

相关文章

面试突击90:过滤器和拦截器有什么区别?

过滤器(Filter)和拦截器(Interceptor)都是基于 AOP(Aspect Oriented Programming,面向切面编程)思想实现的,用来解决项目中某一类问题的两种“工具”,但二...

Springboot过滤器和拦截器详解及使用场景

一、过滤器和拦截器的区别1、过滤器和拦截器触发时机不一样,过滤器是在请求进入容器后,但请求进入servlet之前进行预处理的。请求结束返回也是,是在servlet处理完后,返回给前端之前。2、拦截器可...

聊聊Redis布隆过滤器(原理+实践篇)

1 Bloom Filter 介绍布隆过滤器(Bloom Filter)是 Redis 4.0 版本提供的新功能,我们一般将它当做插件加载到 Redis 服务器中,给 Redis 提供强大的去重功能。...

一种基于布隆过滤器的大表计算优化方法

问题背景在大数据行业内,尤其是数仓建设中,一直有一个绕不开的难题,就是大表的分析计算(这里的大表指亿级以上)。特别是大表之间的 Join 分析,对任何公司数据部门都是一个挑战!主要有以下挑战:由于数据...

Java Web—Filter(过滤器)

web中的过滤器的作用:当访问服务器的资源时,过滤器可以将请求拦截下来,完成一些特殊的功能。web中过滤器的应用场景:一般用于完成通用的操作。如:登录验证、统一编码处理、敏感字符过滤...Filter...

JAVA:如何实现 Bloom 过滤器?它是做什么用的?

在处理大型数据集时,经常需要快速确定一个元素是否属于某个集合。虽然传统的数据结构如哈希表和树可以完成这项任务,但随着数据量的增加,它们对空间的需求也随之激增。Bloom过滤器提供了一种高度空间效率的概...