布隆过滤器

布隆过滤器介绍

布隆过滤器是一种利用bitmap的数据结构,存放的不是0就是1,高效的插入效率和查询效率。主要的目的就是用来判断一个东西是还是没有。相对于普通的hash表,不需要把整个元素放进去,占用的空间的更少,功能也能达到。源码可以直接看Guava包下的BloomFilter。

原生布隆过滤器(BF:Bloom Filter)

优点:

  • 内存消耗较少
  • 实现简单
  • 插入和查询速度快

缺点:

  • 不支持删除
  • 存在冲突(hash通病)和误判

布隆过滤器结构

布隆过滤器的基础结构利用的是bitmap位图数组(假设长度为8):
默认结构

上层结构是bit数组,实际我们需要存的值即01。下层是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:误判率。
则公式为:

p(1eknm)kp \approx (1 - e^\frac{-kn}{m})^k

简化后:

m=nlnp(ln2)2m = -\frac{nlnp}{(ln2)^2}

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

可反向推导验证:大小为m的BF中,经历k次哈希的值仍然为0的概率是(11m)k(1 - \frac{1}{m})^k,即插入n个数后,还是为0的概率就是(11m)nk(1 - \frac{1}{m})^{nk},则为1的概率就是1(11m)nk1 - (1 - \frac{1}{m})^{nk},所以一个元素一个哈希为1的概率确定了,那么k次哈希的概率就是[1(11m)nk]k(1eknm)k[1 - (1 - \frac{1}{m})^{nk}]^k \approx (1 - e^\frac{-kn}{m})^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的概率如下):

Pr(max(c)i)m(nki)1mim(enkim)iPr(max(c) \ge i) \le m\binom{nk}{i}\frac{1}{m^i} \le m(\frac{enk}{im})^i

前面BF里已经得出的:k=mnln2k = \frac{m}{n}ln2可以直接代入公式,得到简化后的公式:

Pr(max(c)i)m(eln2i)iPr(max(c) \ge i) \le m(\frac{eln2}{i})^i

给每个Counter分配4个bit,最大可表示到16,当Counter=16时的概率:

Pr(max(c)16)1.371015mPr(max(c) \ge 16) \le 1.37 * 10^{-15} * m

这个概率可以说非常非常小了,几乎可以忽略,所以绝大部分应用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的结构:
3数冲突CBF

原生的CBF,冲突了就计数加1。删除的时候减1即可。

而ACBF的结构如下:
ACBF结构

  1. 每一层都是一个简单的bit数组。
  2. 多级之间压缩了冲突的位。

ACBF由多级b1,b2,b3...bnb_1,b_2,b_3...b_n数组和brb_r空闲数组组成,每个bjb_j数组的长度为ljl_j(j是变量),判断时要经过k个哈希函数h1,h2...hnh_1,h_2...h_n。计算一个元素x是否存在于ACBF中时的具体步骤如下:

  1. 遍历b1,b2...bnb_1,b_2...b_n数组。
  2. 对于每一个长度为ljl_jbjb_j数组,依次取index=hi(x)modljindex = h_i(x)modl_j
  3. 如果bj[index]==0b_j[index] == 0那么可以判断一定不在,直接返回。
  4. 否则继续进行下一个函数的计算,直到k个函数都执行完成。

待完善。论文没研究透…

参考资料

详解布隆过滤器的原理,使用场景和注意事项
Probabilistic Data structures: Bloom filter
布隆过滤器(Bloom Filter)的原理和实现
布隆过滤器实现原理及源码解析
Counting Bloom Filter 的原理和实现
Accurate Counting Bloom Filters for Large-Scale Data Processing