布隆过滤器
布隆过滤器介绍
布隆过滤器是一种利用bitmap的数据结构,存放的不是0就是1,高效的插入效率和查询效率。主要的目的就是用来判断一个东西是有还是没有。相对于普通的hash表,不需要把整个元素放进去,占用的空间的更少,功能也能达到。源码可以直接看Guava包下的BloomFilter。
原生布隆过滤器(BF:Bloom Filter)
优点:
- 内存消耗较少
- 实现简单
- 插入和查询速度快
缺点:
- 不支持删除
- 存在冲突(hash通病)和误判
布隆过滤器结构
布隆过滤器的基础结构利用的是bitmap位图数组(假设长度为8):
上层结构是bit数组,实际我们需要存的值即
0
或1
。下层是hash函数的值范围,不一定从某个固定数开始,确保hash函数最后的结果都在其中即可。初始状态下的BF,为全空状态。所以通常情况使用的时候,需要先对布隆过滤器进行预热。提前将我们要过滤的数据跑一遍布隆过滤器,将数据填进去,后面过滤的时候直接查询。
布隆过滤器插入冲突
当存入一个hello
之后,通常会额外指定几个hash函数来避免冲突,插入值:
这里指定三个函数来做不同的运算,然后得出不同的hash值(当然也有可能得出一样的hash值,那说明选的hash函数不对劲)。
hash函数越多也不是越高,越多的hash函数,对于每一个值的计算越复杂,慢慢趋向于CPU密集型,尤其是启动的时候最为明显,CPU猛涨。其次,hash值越多,这个BF的作用反而更加弱,误判的概率大大增加。
继续存入第二个元素world
,假设存在冲突:
这里假设计算后的值等于3的槽冲突,那么由于值已经是1了,所以不会变(实际上是覆盖了前面一个数的hash值的存在)。所以如果后面把
hello
这个值移除了,BF里无法知道值等于3的槽是不是hello
的存在标识,只能知道曾经有元素存在过,但不知道是谁(因为冲突覆盖导致)。即无法删除。
布隆过滤器查询误判
而BF随着利用率上去,误判的概率也会增加,这里mygod
来看看自己是否存在于BF中(并没有存过):
由图中可以看出,三个hash函数计算的值其实并不相同,与前面存入的值没有一个是完全符合的,但是计算出的三个槽位却已经被标识为存在过了,根据前面一个介绍的,BF无法判断元素是否被覆盖,无法识别当前元素是否以前命中过,所以就直接认为命中。产生误判。
嗯?:为了减少冲突 => 增加hash函数(BF填充速度过快,值过多容易产生误判)。为了减少误判 => 加大BF容量。结论:hash函数多 => CPU消耗高。BF容量大 => 内存占用变高。
布隆过滤器使用
布隆过滤器设置的大小以及hash函数的多少最终都是影响了误判几率。所以要如何选择布隆过滤器的大小与hash的选择是很重要的。
看下大佬的测试图:
上图参数:
k
:hash函数个数。m
:布隆过滤器长度。n
:插入元素的总数。p
:误判率。
则公式为:
简化后:
可反向推导验证:大小为m的BF中,经历k次哈希的值仍然为0的概率是,即插入n个数后,还是为0的概率就是,则为1的概率就是,所以一个元素一个哈希为1的概率确定了,那么k次哈希的概率就是
由于我们的目的是希望更快的确认一个数是否存在,所以最好是采用一些计算更快的hash函数。而像Sha-1,MD5等都不是好选择,更快的散列函数像MurmurHash算法,FNV hash算法,Jenkins hash算法等。
计数布隆过滤器(CBF:Counting Bloom Filter)
改进点:
- 支持删除
CBF的结构
存入第二个元素world
,假设存在冲突:
这里还是值为3的槽位发生冲突,这里的不同是原本是固定只有0、1的bit数组改成了计数值,变为了2。如果后期要移除时就可以直接减去1。减去之后,重新判断
hello
的值时仍然会命中。
计数Counter的选择
这个计数很简单就解决了布隆过滤器的无法删除问题,但是它本身还有问题,那就是它的值设置多少位合适呢?计数是为了解决在hash冲突的情况下,还可以对数据删除的问题,所以它的值肯定是不期望太大的,同时原来的1bit需要扩容到多少,太大与其他的hash结构就区别不大了,对于大量数据会消耗大量的内存。
参数定义不变:k
:hash函数个数。m
:布隆过滤器长度。n
:插入元素的总数。p
:误判率。
新增参数定义:Pr(max(c))
:过滤器溢出概率,随Counter取值变化。i
:Counter的取值。
根据论文中的描述公式(每一个Counter的值大于等于i
的概率如下):
前面BF里已经得出的:可以直接代入公式,得到简化后的公式:
给每个Counter分配4个bit,最大可表示到16,当Counter=16时的概率:
这个概率可以说非常非常小了,几乎可以忽略,所以绝大部分应用Counter4位是已经完全足够用了的。
频率计数布隆过滤器(SBF:Spectral Bloom Filter)
CBF的优化型之SBF是对CBF的优化的一种,主要侧重于对内存的严格控制,不浪费。
改进点:
- 不定长Counter,优化内存
待完善。
负载计数布隆过滤器(DLCBF:d-Left Counting Bloom Filter)
CBF的优化型之DLCBF是CBF的优化一种,主要侧重于对于BF的负载,利用fingerprint来置换冲突。
待完善。
精确计数布隆过滤器(ACBF:Accurate Counting Bloom Filter)
CBF的优化型之ACBF也是CBF的优化一种,主要侧重于对计数器向量化分级,快速过滤的同时进一步降低误判概率。同时支持海量数据的MapReduce的端连接控制。
- 多级计数器,进一步降低误判
- MapReduce过程,降低端连接
ACBF的结构
先看下假设存入3个有冲突的数x1,x2,x3
进入CBF的结构:
原生的CBF,冲突了就计数加1。删除的时候减1即可。
而ACBF的结构如下:
- 每一层都是一个简单的bit数组。
- 多级之间压缩了冲突的位。
ACBF由多级数组和空闲数组组成,每个数组的长度为(j是变量),判断时要经过k
个哈希函数。计算一个元素x
是否存在于ACBF中时的具体步骤如下:
- 遍历数组。
- 对于每一个长度为的数组,依次取
- 如果那么可以判断一定不在,直接返回。
- 否则继续进行下一个函数的计算,直到
k
个函数都执行完成。
待完善。论文没研究透…
参考资料
详解布隆过滤器的原理,使用场景和注意事项
Probabilistic Data structures: Bloom filter
布隆过滤器(Bloom Filter)的原理和实现
布隆过滤器实现原理及源码解析
Counting Bloom Filter 的原理和实现
Accurate Counting Bloom Filters for Large-Scale Data Processing
- 本文链接:https://github.com/moexiong/moexiong.github.io/tree/master/2021/06/06/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8/
- 版权声明:本博客所有文章除特别声明外,均默认采用 许可协议。