蛮荆

布隆过滤器

2023-06-20

基本概念

布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出,是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。 它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。 – 维基百科

查找问题建模

如何判断某个元素是否存在于一个集合中

比较直观的做法是将所有元素保存起来,然后逐个比较确认结果,建模转换为具体的数据结构:

  • 线性结构: 数组、链表等,时间复杂度为 O(N), 空间复杂度为 O(N)
  • 散列表结构: Map、HashTable 等, 时间复杂度为 O(1), 空间复杂度为 O(N)
  • 树形结构: AVL、RBTree 等, 时间复杂度为 O(logN), 空间复杂度为 O(N)

常见的数据结构随着元素的增加,存储空间也会越来越大,同时查询速度也会越来越慢 (散列表结构不受影响),如果我们希望在保持时间复杂度为 O(N) 的前提下, 尽可能地降低内存占用,就需要转换一下思路:保存特征数据,而非所有数据。什么是特征数据? 简单来说,就是能够唯一标识出其对应的源数据, 比如常见的 用户 ID游戏中奖 ID管理后台审批流 ID 等。

原理和应用场景

布隆过滤器的原理: 当一个元素被加入集合时,通过 K 个哈希函数 将元素映射到一个位图数据结构 (例如 bitmap) 中的 K 个位置上面,并将这些位置全部置为 1。 判断元素是否存在于集合时,只需查看 K 个哈希函数 映射后的 K 个位置上面的值即可。

如果这些位置任意一个为 0,则表示被检测元素一定不存在于集合中,如果都是 1,则表示被检测元素有较大可能存在于集合中

为什么不能检测 “一定存在” ?

检测元素时可以返回 “一定不存在” 和 “可能存在”,因为可能有多个元素映射到相同的 bit 上面,导致该位置为 1, 那么一个不存在的元素也可能会被误判为存在, 所以无法提供 “一定存在” 的语义保证。

为什么元素不允许被 “删除” ?

如果删除了某个元素,导致对应的 bit 位置为 0, 但是可能有多个元素映射到相同的 bit 上面,那么一个存在的元素会被误判为不存在 (这是不可接收的), 所以为了 “一定不存在” 的语义保证,元素不允许被删除。

PS: 虽然可以引入一个 删除计数器 来解决上述问题,不过这需要引入额外的空间,失去了使用过滤器的意义。

两个语义操作

  • Add : 添加一个元素到集合中
  • Test : 检查给定元素是否存在于集合中

示例

URL 去重

假设下面的 URL 列表为采集队列 (一共 100 条数据),我们希望采集完成的 URL 可以记录起来,避免多次采集,如果使用正常的字符串存储的话 (以 Go 语言为例,string 占用 16 bytes), 大概需要 16 bytes * 100 = 1600 bytes 内存空间。

https://www.example.com/u/101/profile
https://www.example.com/u/102/profile

...

https://www.example.com/u/200/profile

而如果我们改为 布隆过滤器 的方式来记录的话,假设哈希函数可以将每个链接转换为 1 个 0-255 的数字,通过将数据存入一个 bitmap, 那么理想情况下 (不发生任何碰撞) 最终只需要 1 个 byte 的内存空间即可,内存使用直接降低了 1600 倍

# 布隆过滤器记录 URL 只需要 1 个 byte

------------------------------------
| 0   | 1   | 2   | 3  | ... | 255 | 
------------------------------------
| URL | URL | URL |    |     | URL |
------------------------------------

网站用户性别

假设网站的用户数量为 1000万,每个用户性别存储需要 1 个 bytes, 如果正常存储的话,大概需要 1 byte * 1000 W ≈ 10 MB 内存空间。

而如果我们改为 布隆过滤器 的方式来记录的话,假设用户 ID 是一个数字,通过将数据存入一个 bitmap, 那么 1 byte 可以表示 256 个 用户性别, 理想情况下 (不发生任何碰撞) 最终只需要 1000 W / 256 * 1 byte ≈ 0.04 MB 内存空间,内存使用直接降低了 256 倍

# 布隆过滤器记录用户网站性别

--------------------------------------------------
| 0     | 1     | 2     | 3     | ...  | 9999999 | 
--------------------------------------------------
| User1 | User2 | User3 | User4 | ...  | User... |
--------------------------------------------------

其他应用场景

  • 垃圾邮件过滤
  • 防止缓存穿透
  • 业务记录计数器
  • Web 拦截

两个核心支撑点

通过上面两个简单的应用场景可以看到,要实现一个健壮的 布隆过滤器,需要规划设计好两个技术点:

  • 元素长度和用于存储哈希映射值的数据结构,一般使用 bitmap (具体的长度和存储规模有关)
  • 显著降低碰撞、性能优良的哈希函数

Murmur3FNV 系列和 Jenkins 等非密码学算法适合作为哈希函数,其中 Murmur3 因为易于实现,并且在速度和随机分布上有很好的权衡, 实践中多选用其作为 布隆过滤器 的哈希函数。

数学部分

一个 布隆过滤器 至少需要包含如下参数:

  • 哈希空间大小,记为 m
  • 元素集合大小,记为 n
  • 哈希函数个数,记为 k
  • 误判概率,记为 p (可能出现一个元素不在集合中,但是被误判为存在于集合中,这个误判的概率取值范围为 0 - 1)

哈希函数个数满足以下公式时,布隆过滤器 有最好的效果 (数学证明部分省略,数学渣暴露了 :( … )

k = [(ln2)(m/n)]

还是以刚才的 网站用户性别 为例,1000W 用户需要以不高于 0.00001% 误判率的的情况下被检测到,需要多少个哈希函数?需要耗费多少空间?

# 带入公式计算

n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))))
k = round((m / n) * log(2))

记不住数学公式?没关系,已经有大佬做好了一个 在线工具,可以通过输入参数直接生成对应的哈希函数个数。

Bloom Filter Calculator

开源库

笔者选择了 bits-and-blooms/bloom 作为研究 布隆过滤器 代码实现,版本为 v3.3.1

安装组件

$ go get -u github.com/bits-and-blooms/bloom/v3

示例

初始化过滤器时,需要知道对应的业务场景有多少元素(期望的容量),以及期望的误判概率。常见的误判率为 1%, 误报率越低,需要的内存就越多, 同时容量越大,需要的内存就越多。

初始化过滤器时,应该尽可能明确需要的元素数量,因为 布隆过滤器 不是动态数据结构,如果指定的元素数量太少,则可能会超出误判概率范围

package main

import "github.com/bits-and-blooms/bloom"

func main() {
	// 初始化能够接收 100 万个元素且误判率为 1% 的布隆过滤器
	filter := bloom.NewWithEstimates(1000000, 0.01)

	hw := []byte(`hello world`)
	hg := []byte(`hello golang`)

	filter.Add(hw)

	println(filter.Test(hw)) // true
	println(filter.Test(hg)) // false
}

我们只添加了 hello world 字符串到过滤器中,所以正常的输出应该是 true false:

$ go run main.go

true
false

源码分析

接下来,我们来简单分析下 bits-and-blooms/bloom 的实现代码。

哈希算法选择

module github.com/bits-and-blooms/bloom/v3

go 1.14

require (
	github.com/bits-and-blooms/bitset v1.3.1
	github.com/twmb/murmur3 v1.1.6
)

bits-and-blooms/bloom 的依赖包中,可以看到其选择了 murmur3 算法作为哈希函数实现。

BloomFilter

BloomFilter 结构体表示一个 布隆过滤器,包含 3 个字段,分别对应上文提到的 布隆过滤器 的必要参数。

type BloomFilter struct {
	m uint              // 哈希空间大小
	k uint              // 哈希函数个数
	b *bitset.BitSet    // bitmap
}

初始化过滤器

NewWithEstimates 方法创建一个 布隆过滤器,内部调用了 EstimateParameters 方法来计算 mk 的值, 最后通过 mk 初始化一个 BloomFilter 结构体并返回。

func NewWithEstimates(n uint, fp float64) *BloomFilter {
	m, k := EstimateParameters(n, fp)
	return New(m, k)
}

func EstimateParameters(n uint, p float64) (m uint, k uint) {
    m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
    k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))
    return
}

添加元素

BloomFilter.Add 方法添加一个元素到 布隆过滤器,返回当前的 BloomFilter 对象来支持链式调用。

func (f *BloomFilter) Add(data []byte) *BloomFilter {
	h := baseHashes(data)
	for i := uint(0); i < f.k; i++ {
		f.b.Set(f.location(h, i))
	}
	return f
}

baseHashes 函数返回哈希函数计算出的哈希值,其内部调用了 murmur3 算法。

func baseHashes(data []byte) [4]uint64 {
    ...
}

location 函数返回哈希值对应的 bitmap 的位置索引,通过将 bitmap 对应的位置进行设置,就可以将元素添加到 布隆过滤器 了。

func location(h [4]uint64, i uint) uint64 {
	...
}

检测元素

BloomFilter.Test 方法检测一个元素是否存在于 布隆过滤器 中,可以看到,其内部实现就是 BloomFilter.Add 方法的逆过程。

func (f *BloomFilter) Test(data []byte) bool {
	h := baseHashes(data)
	for i := uint(0); i < f.k; i++ {
		if !f.b.Test(f.location(h, i)) {
			return false
		}
	}
	return true
}

调用流程图

调用流程图

小结

本文简述了 布隆过滤器 的基本概念和原理,并通过开源库 bits-and-blooms/bloom 的实现代码分析了实现 布隆过滤器 的核心技术点, 最后引用维基百科关于 布隆过滤器 的优缺点作为文章结尾。

优点

布隆过滤器 在算法的空间复杂度和时间复杂度方面都有巨大的优势,AddTest 操作的时间复杂度都是常数 O(K) (K: 哈希函数个数)。 由于哈希函数相互之间没有关联,因此可以通过硬件并行实现计算加速,此外,由于 布隆过滤器 不存储源数据,在某些对数据保密要求非常严格的场景 (数据可用,但不可见) 有明显优势。 最后,在哈希空间向量长度相同的情况下,使用同一组哈希函数的两个 布隆过滤器集合相关运算可以使用位操作进行。

缺点

布隆过滤器 最明显的的缺点就是 误判率,随着元素数量增加,误判率 也随之增加,所以如果元素数量很少的情况下,使用 map 就可以了。 此外,布隆过滤器 不支持删除元素, 因为 布隆过滤器 只能确定元素一定不存在于集合中,无法确定元素一定存在于集合中,如果一定要删除某个元素, 则必须重新构建整个 布隆过滤器

Reference

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可,转载时请注明原文链接,图片在使用时请保留全部内容,商业转载请联系作者获得授权。