什么是布隆过滤器?

布隆过滤器是一种数据结构,特点是高效的插入和查询,而且非常节省空间。通过对位(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在事项过滤器。
以上为全部内容。欢迎持续关注。

Logo

华为云1024程序员节送福利,参与活动赢单人4000元礼包,更有热门技术干货免费学习

更多推荐