详解布隆过滤器

一、引言

假设我们想要开发一个邮件系统,那么如何实现垃圾邮件的过滤呢。

垃圾邮件过滤

最简单的办法就是把确定为是垃圾邮件的地址都保存起来,存入黑名单中。当用户接收到黑名单地址的邮件时,直接将邮件归类到垃圾箱中。

垃圾邮件的地址数量可能是巨大的,因此除了被存储在数据库中,程序实际使用的时候一定是需要借助缓存的。不论是使用本地缓存还是内存缓存,当数据量达到一定数量级时,都是不太合适的。

咳咳,如果你的数量级连百万都不到的话,那么其实布隆过滤器好像用处不大哈,缓存+容错处理似乎就能解决了。

假设存在 1000W 个垃圾邮件地址,每个地址就按 10 个字节来算,内存占用就已经达到 100MB 了。如果地址扩大到1亿个呢,内存占用就达到 1GB 了。

所以你是用 HashMap 还是用 Redis 的 Set 结构,亦或者其他来存储,可能都不太合适了。

二、布隆过滤器

2.1 基本特点

布隆过滤器(Bloom Filter),它的特点是:当它说某个 key 不存在时,key一定不存在;当它说某个 key 存在时,key 可能存在

上面提到的只是一个为了引出布隆过滤器的例子,可能不太严谨。布隆过滤器的另一个主要应用是应对缓存穿透,缓存穿透指查询一个一定不存在的数据,因为缓存中数据不存在,出于容错考虑,会从数据库中读取数据。这将导致这个不存在的数据每次请求都要查询数据库,缓存相当于被绕过。在流量大或被恶意攻击时,缓存 IO 会急剧上升甚至导致宕机。

布隆过滤器就是应对缓存穿透的一个解决方案,首先将存在的数据都加载入布隆过滤器中,当查询一个不存在的数据时,布隆过滤器就会返回不存在,这样就能将无效的请求先行拦截掉。

由于布隆过滤器认为存在时,并不是一定存在,因此会存在一定的误判率。如果你不能够接受它的误判率,你应当在后续继续做处理,例如在缓存中查询为空时,缓存一个过期时间很短的空结果,来减低缓存穿透的风险。

如果你能够接受它的误判率,以引言中的垃圾过滤需求为例,可能会导致一些正常的邮件被归类到垃圾箱中。

布隆过滤器的应用流程

事先说明的是我目前在实际业务中并没有使用过布隆过滤器,因此有点纸上谈兵的味道。如果在今后实际项目中应用的流程和上图有出入的话,我会再更新下这张图。

上图是我画的布隆过滤器的一个使用图。在 ③ 步中,查询 DB 时应当采用互斥查询,避免导致缓存击穿问题,一个常见的互斥锁实现就是 Redis 的 setnx 指令。

需要注意的是,setnx 指令应当和 expire 指令同时设置,避免死锁问题。自 Redis 2.8 起,原生支持 setnx 和 expire 的原子性执行,无需再引用第三方分布式锁。用法例如:

1
2
3
>sex lock:info true ex 5 nx # 设置一个叫做 lock:info 的 key,如果设置成功的话,同时设置过期时间为 5s
>....
>del lock:info # 删除该 key(即释放锁)

在第 ⑤ 步中,对于不存在的记录,缓存一个过期时间短的值,这也是预防缓存穿透的一个办法。这样当下次该非法请求访问时,无需再查询 DB。

2.2 实现原理

了解了布隆过滤器的基本特点后,下面来了解下它的实现原理吧。布隆过滤器包含两大部分,一个位数组,以及多个无偏 Hash 函数

以下图为例,最底下的就是布隆过滤器实际存储的一个位数组,而图中的 f、g、h 就是无偏 Hash 函数。当我们要存储元素 key1 时,将 key1 分别代入到每个 hash 函数,将哈希后的结果作为位数组的下标,并将该位置为 1。存储 key2 时同理。

布隆过滤器原理

进行查询时,将查询值代入每一个 hash 函数,只有所有函数的返回结果在位数组中的值均为1,返回查询成功。只要有一个数组中值为 0,返回失败。

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

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

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

2.3 支持删除

了解了原理后,不难理解布隆过滤器是不支持元素删除的,因为位数组上的某一位有可能被多个 key 所公用。还是以上图为例,如果删除了 key1,把 key1 在位数组中的每一位置 0,那么 key2 查询时就变成不存在了。

想要解决这个问题,似乎得对数组每一位再来个计数,删除时计数删除,这样就会加大内存的占用。当然这也是我的纸上谈兵。

2.4 降低误判

如果让你来考虑,咋降低布隆过滤器的误判率呢,第一感觉就是让它的位数组变长一点不就好了。

不论我们使用哪种布隆过滤器的实现,基本上都可以显式的指定预计存放的元素个数,以及误判率。误判率设置的越低,那么所需的空间自然也就越大,具体设置多大跟你指定的元素个数也有关系。因此你应当合理的设置元素个数,不然一旦超出预设值,误判率就会升高,你可能就得考虑重建过滤器了。

2.5 空间占用

本节参考书籍:《Redis深度历险:核心原理和应用实践》,公式推倒过程如下比较复杂,有兴趣的可以看下这篇文章:《大数据量处理利器:布隆过滤器》

布隆过滤器根据预计元素数量 $n$,错误率 $f$,就能够计算出位数组的长度 $m$,也就是需要的存储空间大小(bit)。下面直接给出已经被证明的公式,hash 函数最佳数量 $k ≈ 0.7 ^{ \frac{m}{n}}$,误判率 $f ≈ 0.6185 ^ \frac{m}{n}$。

从公式中可以看出:

  1. 位数组相对越长 (m/n),错误率 f 越低,这个和直观上理解是一致的。
  2. 位数组相对越长 (m/n),hash 函数需要的数量也越多,影响计算效率。

当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (m/n=8),错误率大约为 2%

  • 错误率为 10%,一个元素需要的平均指纹空间为 4.792 个 bit,大约为 5bit
  • 错误率为 1%,一个元素需要的平均指纹空间为 9.585 个 bit,大约为 10bit
  • 错误率为 0.1%,一个元素需要的平均指纹空间为 14.377 个 bit,大约为 15bit

如果你觉得计算困难的话,有第三方网站提供在线的布隆计算器:Bloom Calculator

当实际元素超出预计元素时,错误率会有多大变化,它会急剧上升么,还是平缓地上升,这就需要另外一个公式,引入参数 $t$ 表示实际元素和预计元素的倍数:

$$
f = (1-0.5^t)^k
$$

当 t 增大时,错误率 f 也会跟着增大,分别选择错误率为 10%,1%,0.1% 的 k 值,画出它的曲线进行直观观察。

从这个图中可以看出曲线还是比较陡峭的:

  1. 错误率为 10% 时,倍数比为 2 时,错误率就会升至 40%
  2. 错误率为 1% 时,倍数比为 2 时,错误率升至 15%
  3. 错误率为 0.1%,倍数比为 2 时,错误率升至 5%

三、Java 中的布隆过滤器

Java 中的布隆过滤器常见的是 Guava 实现,在前几篇文章我介绍过 Guava 的 local cache,今天介绍下它的布隆过滤器。导入 Guava 依赖后,下面是一个简单的使用:

1
2
3
4
5
6
7
8
9
10
11
12
@Test
void guavaBloomTest() {
long star = System.currentTimeMillis();
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(), 10000000, 0.01);

for (int i = 0; i < 10000000; i++) {
filter.put(i);
assertTrue(filter.mightContain(i));
assertFalse(filter.mightContain(i+1));
}
}

构建时第一个参数为布隆过滤器中元素类型,一个 Funnel 实现类,第二个参数为预估元素个数,第三个参数为误差率。我这里构建了一个整型的布隆过滤器,其他支持的类型,大致如下图所示。通过调用put 方法向过滤器添加值, mightContain() 方法判断是否存在过滤器中。

Funnel

四、Redis 中的布隆过滤器

这里简单起见,只列出 redils-cli 中的使用,第三方客户端命令自己百度下哈。
注意:

  • Redis 支持布隆过滤器模块需要版本在 4.0+,之前版本需要使用第三方库,例如 orestes-bloomfilter 等等。
  • Redis 的 Java 客户端中 Lettuce 早早就支持布隆过滤器指令,Jedis 则必须要在 3.0+ 版本才能使用。

自从 Redis 4.0 开始,引入了模块系统,使得布隆过滤器能够以插件的形式加入 Redis 中,参考文档:Quick Start

文档中提供了两种方式,一种是以 Docker 方式,另一种就是编译插件的方式。如果你当前装有 Docker,那么使用 Docker 自然是最简单的。因为我这台机器上没有 Docker,因此采用编译插件方式,稍微复杂点。

有兴趣的同学可以看下我的这篇文章,回顾下动态库的知识:《Linux 静态库和动态库》

首先检查下版本,确保是 4.0 +,然后停止 Reids 服务:

1
2
3
[root@VM_120_243_centos bin]# ./redis-cli --version
redis-cli 4.0.8
[root@VM_120_243_centos bin]# ./redis-cli shutdown

然后就是将插件下载下来,并 make 编译,得到动态库:

1
2
3
4
5
[root@VM_120_243_centos redis]# git clone https://github.com/RedisBloom/RedisBloom.git
...
[root@VM_120_243_centos redis]# cd RedisBloom/
[root@VM_120_243_centos RedisBloom]# make
...

编译完毕后在当前文件夹下就会得到 redisbloom.so 这个动态库,即布隆过滤器的 Redis 模块。然后将其移动到合适的地方,这里我移动到了 Redis 配置文件的同级目录下:

1
2
[root@VM_120_243_centos redis]# ls
bin redisbloom.so redis.conf

下一步就是将该插件在 Redis 配置文件中加载,编辑 redis.conf,找到 MODULES 那一块配置,将插件的路径写入:

注意: 这里的路径请使用绝对路径,我一开始用相对路径导致 Redis 无法启动。

redis.conf

配置完毕后启动 Redis 即可,布隆过滤器的基本使用如下,命令还是很简单的,就不再详细介绍了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

最后补充下 Redis 中利用 bf.reserve 显式创建布隆过滤器,第一个参数为 key;第二个参数为错误率;默认为 0.01,第三个参数为预计大小,默认为 100。当 key 值存在时,创建失败。

1
2
3
4
127.0.0.1:6379> bf.reserve bloom 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve bloom1 0.01 100
OK

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×