Skip to content

布隆过滤器(Bloom Filter)的原理及应用

约 1154 字大约 4 分钟

大数据

2024-03-12

布隆过滤器是一种概率数据结构,用于检查集合中是否存在项目,在 LSM Tree 以及其他的大数据场景中有广泛的应用。

使用场景

布隆过滤器主要的使用场景是用于 快速判断一个元素是否在一个集合之中。通常用于过滤海量的数据请求以及提高对于数据的查找效率。例如刷抖音的时候,想要判断该视频是否已经被当前用户所收藏就是一个判断某元素是否在一个集合的问题,我们可以使用布隆过滤器来提高查询的效率。

基本原理

布隆过滤器是一种具有空间优势的概率数据结构,核心就是一个超大的位数组和哈希函数,用于回答一个元素是否存在于一个集合中这样的问题,但是可能会出现误判——即一个元素不在集合但被认为在集合中。

  1. 给定长度为 N 个 bits 的哈希空间。
  2. 选取 d 个哈希函数,每个哈希函数将给定的元素映射到 [0, N-1] 的一个位置上,并将该位置为 1。
  3. 将需要被判断的元素也用 2 中的 d 个哈希函数算出 d 个位置 a1,a2,,ada_1, a_2, \dots , a_d
  4. 如果 a1,a2,,ada_1, a_2, \dots , a_d 对应的位有一个不为 1,则该元素一定不在集合中。
  5. 如果 a1,a2,,ada_1, a_2, \dots , a_d 对应的位全为 1,则该元素可能存在于集合中。
布隆过滤基本原理
布隆过滤基本原理

参数

从上面可以看出,一个布隆过滤器应该起码有以下参数:

  1. 哈希空间大小,记为 mm。以上示例中 mm = 20 bits。
  2. 元素集合大小,记为 nn。以上示例中 nn = 2。
  3. 哈希函数个数,记为 kk。以上示例中 kk = 2。
  4. 因为 BF 是 Allowable Errors 的,可能会出现一个元素原本不在集合中,但是被错判为存在于集合中,这个错判的概率叫 false postive,记为 ε\varepsilon

当错误率最小的时候,各个参数之间会有如下关系:

k=mnln2k = \frac{m}{n} \ln2

m=nlnϵ(ln2)2m = - \frac{n \ln \epsilon}{(\ln 2)^2}

mn=log2ϵln21.44log2ϵ\frac{m}{n}=- \frac{\log_2 \epsilon}{\ln 2} \approx -1.44 \log_2 \epsilon

如何选择哈希函数?

从概率计算和速度角度,哈希函数需满足:

  1. 独立且均匀分布。
  2. 计算速度快。

这里推荐了解 murmur 算法。

优缺点

优点

  • 内存效率高。
  • 查询速度快。
  • 可并行处理。

缺点

  • 存在误判率。主要取决于哈希函数的数量和位数组的大小,较大的位数组可以降低误判率,但会增加内存消耗,因此需要权衡。
  • 存在哈希冲突。
  • 不支持删除。
  • 不能获取原始数据。

应用

  • 数据库防止穿库。使用 BloomFilter 来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
  • 业务场景中判断用户是否阅读过某视频或文章。比如抖音或头条。

Demo

Go 语言中我们可以使用下面这个 package 来轻松实现一个布隆过滤器。

main.go

性能比较

输入数据量 0.01Bloom 内存/ CPU 峰值map 内存/ CPU 峰值内存节省
1w0.8MB1.18MB32.5%
5w1.5MB3.3MB54.5%
10w1.37MB3.66MB62%
50w2.24MB23.2MB90%
100w2.7MB46.1MB94%
500w9.3MB191.4MB95%
1000w17.6MB382.5MB95%
5000w61.7MB1705.2MB96%

内存占用 Bloom 减少 60% - 90% 的内存占用

输入数据量 0.01Bloom 查询耗时map 查询耗时耗时增加
1w1+1=2ms508+508=1ms200%
5w5.6+4.8=10.5ms3.2+3.0=6.3ms166%
10w12+9.6=21.8ms9+6=15ms145%
50w61.1+52.1=113.2ms51.6+47.6=99.1ms114%
100w125.9+109.4=235.3ms136.5+121.5=258ms91%
500w665.5+592=1.26s723.5+711.8=1.4s90%
1000w1.87+1.5=3.9s1.48+1.4=2.9s134%
3000w16.5s9.8s168%
5000w15+13=28s7.6+7.6=15.2s184%

全量插入 + 全量查询的耗时记录




贡献者

更新日志

2025/3/4 09:14
查看所有更新日志
  • 580df-improve(docs): use chinese punctuation
  • d0d75-improve(docs): use chinese punctuation
  • 42218-fix(docs): text typo
  • 1289a-improve(docs): delete extra whitespace and blank lines
  • d8792-feat(docs): add new english articles
  • c2111-modify(docs): remanage folders and rename files
  • 6f2e3-docs: update docs
  • 96e66-docs: update docs
  • 8f99a-整理图片和文章
  • 7b24f-整理文章代码格式

Keep It Simple