首页综合 > 正文

布隆过滤器 - 实现和特征

2023-06-28 09:06:40来源:互联网

基本概念

布隆过滤器(英语: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/profilehttps://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 (具体的长度和存储规模有关)

显著降低碰撞、性能优良的哈希函数

Murmur3,FNV 系列和 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))

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

Bloom Filter Calculator

开源库

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

安装组件

$goget-ugithub.com/bits-and-blooms/bloom/v3

示例

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

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

packagemainimport"github.com/bits-and-blooms/bloom"funcmain(){//初始化能够接收100万个元素且误判率为1%的布隆过滤器filter:=bloom.NewWithEstimates(1000000,0.01)hw:=[]byte(`helloworld`)hg:=[]byte(`hellogolang`)filter.Add(hw)println(filter.Test(hw))//trueprintln(filter.Test(hg))//false}

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

$gorunmain.gotruefalse

源码分析

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

哈希算法选择

modulegithub.com/bits-and-blooms/bloom/v3go1.14require(github.com/bits-and-blooms/bitsetv1.3.1github.com/twmb/murmur3v1.1.6)

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

BloomFilter

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

typeBloomFilterstruct{muint//哈希空间大小kuint//哈希函数个数b*bitset.BitSet//bitmap}

初始化过滤器

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

funcNewWithEstimates(nuint,fpfloat64)*BloomFilter{m,k:=EstimateParameters(n,fp)returnNew(m,k)}funcEstimateParameters(nuint,pfloat64)(muint,kuint){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)fori:=uint(0);ibaseHashes 函数返回哈希函数计算出的哈希值,其内部调用了 murmur3 算法。

funcbaseHashes(data[]byte)[4]uint64{...}

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

funclocation(h[4]uint64,iuint)uint64{...}

检测元素

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

func(f*BloomFilter)Test(data[]byte)bool{h:=baseHashes(data)fori:=uint(0);i调用流程图调用流程图

小结

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

优点

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

缺点

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

Reference

布隆过滤器 - 维基百科[3]

bits-and-blooms/bloom[4]

Bloom Filters[5]

经典论文解读——布隆过滤器

白话布隆过滤器 BloomFilter

Bloom and Cuckoo Filters - Awesome Go[6]

redis bitmap[7]

CUCKOO FILTER:设计与实现[8]

链接

[1]

在线工具: https://hur.st/bloomfilter/

[2]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[3]

布隆过滤器 - 维基百科: https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

[4]

bits-and-blooms/bloom: https://github.com/bits-and-blooms/bloom

[5]

Bloom Filters: https://www.jasondavies.com/bloomfilter/

[6]

Bloom and Cuckoo Filters - Awesome Go: https://awesome-go.com/bloom-and-cuckoo-filters/

[7]

redis bitmap: https://redis.io/commands/?group=bitmap

[8]

CUCKOO FILTER:设计与实现: https://coolshell.cn/articles/17225.html

推荐阅读

Go:详解布隆过滤器原理与实现

福利

我为大家整理了一份从入门到进阶的Go学习资料礼包,包含学习建议:入门看什么,进阶看什么。关注公众号 「polarisxu」,回复ebook获取;还可以回复「进群」,和数万 Gopher 交流学习。

关键词:

便民

点击加载更多

频道推荐

  • 服饰
  • 时尚
  • 物流
  • 灯饰
  • 养老