likes
comments
collection
share

布隆过滤器的原理解析与应用实践

作者站长头像
站长
· 阅读数 28

布隆过滤器，起源于 20 世纪 70 年代，是一种高效的数据过滤算法。它基于二进制数组和多哈希函数的结合，以极低的空间占用和高效率著称。由于其底层采用位存储方式，使得存储成本大幅降低，例如，仅需 10KB 的空间便能存储高达百万个元素的数组。

布隆过滤器的过程

布隆过滤器的原理解析与应用实践

下面我们看看布隆过滤器的过程。如图所示，我们现在要存储字符串 ABC，我们需要对字符串 ABC 先进行哈希。不同的是，图中的布隆过滤器有 3 个哈希函数，最终会产出 3 个不同的哈希值，并记录到二进制数组的 3 个位置。下一次如果再碰到字符串 ABC，我们只需要去数组中查找即可判断 ABC 是否存在。就像现在的 AI 人脸识别，也采用了类似的原理，通过多个哈希方法提取人面部的特征矩阵来比较数据库中的特征是否和你的面部特征一致。

进行布隆过滤器时，我们需要多个哈希函数来验证。为什么这样做呢？

因为不同的字符串哈希出来的结果可能相同，也可能不同。这就是为什么我们需要多个哈希函数来验证。类似地，我们在人脸识别的时候，会让我们转动脖子、抬头、眨眼、低头，这几个动作其实就是不同的哈希函数。

由于我们选择的哈希函数总是不见得完美，所以布隆过滤器有可能误判，对于 2 个不同的对象，哈希结果相同也是有可能的。听上去布隆过滤器没什么用啊，不能判断元素存在，只能判断元素不存在。那你想想看，什么情况下我们会用到这个功能？

对！就是缓存穿透。网络攻击者构造了很多不存在的数据请求你的 URL，这些垃圾请求绕过了你的 Redis 直接打在了数据库上，时间长了就会导致数据库挂死。布隆过滤器就是面试问题“如何处理缓存穿透”的官方解法。

接下来，我们具体看一下 单机版布隆过滤器 和 分布式场景下的布隆过滤器。

单机版布隆过滤器的使用

Google 的 Guava 库中有布隆过滤器器的实现类 BloomFilter。下面的代码我们创建了一个布隆过滤器器，其中 10000 是指这个布隆过滤器器可以容纳 10000 个字符串，0.1 代表布隆过滤器器误判的几率不超过十分之一。

// 创建布隆过滤器器对象
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.stringFunnel(Charsets.UTF_8),
    10000,
    0.1);
// 判断指定元素是否存在
System.out.println(filter.mightContain("ABC"));
// 将元素添加进布隆过滤器器
filter.put("ABC");
System.out.println(filter.mightContain("ABC"));

当 mightContain 方法返回 false 时，我们可以 100％确定 ABC 不存在。

Guava 库提供了很多便捷的功能和高质量的代码，除了布隆过滤器器还有本地 Cache，但是 Guava 的组件都是基于单机的，这很好理解，毕竟 Guava 只是一个 Jar 包嘛。

如果是分布式场景下使用布隆过滤器器该怎么做呢？我们就需要求助 Redis 了。

Redis 中的布隆过滤器

布隆过滤器器是 Redis 的一个插件，所以需要单独安装一下。RedisBloom 是 Redis 官方推荐的布隆过滤器器插件，可以通过 github.com/RedisBloom/… 来下载。

也可以通过 Docker 快速安装部署：

~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
~ docker exec -it redis-redisbloom bash
root@dsmall.ys:/data# redis-cli
127.0.0.1:6379>

安装好了以后，具体该怎么使用呢？我们来看看常用的几个命令：

首先我们需要知道，如何向布隆过滤器器添加一个元素。命令bf.add就可以实现这个功能，格式是：
bf.add test user1

这里的 test 是布隆过滤器器的名称，如果 test 不存在，bf.add 会自动创建 test 过滤器。

下面你会想一个一个添加元素有点麻烦，有没有批量添加的方法？命令bf.madd可以满足你，实现批量添加的功能，格式是：
bf.madd test user1 user2

就是把 user1 和 user2 都放进 test，如果 test 不存在，bf.madd 会自动创建 test 过滤器。

下面我们介绍一个判断元素是否存在的命令。

bf.exists test user1

bf.exists 判断 user1 是否在 test 过滤器中，与之对应的有一个 bf.mexists 命令可以批量判断多个元素是否存在：

bf.mexists test user1 user2

最后我们介绍最重要的命令 bf.reserve，它的功能是创建一个布隆过滤器器，格式如下：

bf.reserve {key} {error_rate} {size} [expansin]

下面我介绍一下每个参数的含义：

  • key：布隆过滤器器的名称。

  • error_rate : 误报率，这是一个小数。例如，error_rate 则配置为 0.01 表示误报率为 1％。该数字越小，服务器资源消耗就越大。考虑到资源占用，通常我们不会把这个指标设置得太小，可以把 error_rate 设置的稍大一些，因为我们使用布隆过滤器器就是来判断某个元素不存在的，而判断某个元素存在的业务场景非常少。

  • size: 过滤器的容量。建议根据业务场景来配置，若空间不足会增加误判的几率。

  • expansion：作为最后一个参数，这个参数不是必须的，默认是 2。当布隆过滤器器满了之后，布隆过滤器器会自动创建默认容量是自己 2 倍的新的过滤器。

以下就是执行命令所返回的结果：
127.0.0.1:6379> BF.ADD test yafeng
(integer) 1
127.0.0.1:6379> BF.ADD test geektime
(integer) 1
127.0.0.1:6379> BF.EXISTS test geektime
(integer) 1
127.0.0.1:6379> BF.EXISTS test yafeng
(integer) 1
127.0.0.1:6379> BF.EXISTS test geekbang
(integer) 0

总结

今天我们聊了布隆过滤器器，布隆过滤器器就是利用一系列哈希函数对元素的特征进行提取，这个过程很像人脸识别的原理。布隆过滤器器使用位数组来存储数据，性能非常好，同时位数组的使用也大大节省了空间。

接着我们 从单机和分布式 2 个方面讲了布隆过滤器器的实战，其中单机版的布隆过滤器器推荐 Google Guava 库的类 BloomFilter，BloomFilter 是一个非常不错的实现，封装的 API 也非常方便，有兴趣的同学可以看看 BloomFilter 的源码。

另外，在分布式场景下我们介绍了 RedisBloom 的安装和使用，实战中 RedisBloom 用得更多。和 BloomFilter 一样，RedisBloom 提供的 API 也非常简洁、方便。

转载自:https://juejin.cn/post/7389644611261136931
评论
请登录