布隆过滤器(Bloom Filter)的原理和使用场景

chan 作者
阅读 1282 喜欢 1

什么是布隆过滤器?

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

场景

在使用 Reids 做数据缓存的时候,很有可能会遇到一个问题:用户想要查询一个数据,发现 redis 缓存没有命中,于是向数据库查询。发现也没有,于是本次查询失败。当用户很多的时候,缓存都没有命中,于是都去请求数据库。这会给数据库造成很大的压力,这时候就相当于出现了缓存穿透。

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

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

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

3、使用 Bloom Filter。
原理上和使用 HashMap 一样,但更省空间。

布隆过滤器的数据结构

布隆过滤器是一个 bit 数组,其结构如下:

一个英文字母 == 一字节 == 八位,在二进制中表示 0000 0000,布隆过滤器就是对位进行操作。

如果我们要映射一个值到布隆过滤器中,我们要使用 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 不存在,也有可能被误判存在。因此设置合适的数组长度也是需要考虑的,数组越大,误判的几率越小。

Redis 使用布隆过滤器

由于 Redis 支持 bit 操作(setbit,getbit),而且数据存储在内存当中,因此非常适合作为布隆过滤器使用。

全部评论1