Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

深入解析Bloom Filter(中)

本篇将介绍:

  • d-left hashing
  • d-left counting bloom filter

上篇文章,我们介绍了Standard Bloom Filter(SBF)和Counting Bloom Filter(CBF)。简单回顾下,我们大概思路和历程是:为了解决允许false positive下的membership问题,我们设计了哈希表算法,由于它所需空间巨大,我们引入bitmap方法;因为它false positive possibility太大,我们引入了SBF,它使用多个独立的、均匀分布的哈希函数。而SBF的一个缺点是不支持删除操作,为了能够删除,我们引入了CBF,然而,CBF存在一个问题。

什么问题呢?那就是空间利用率不高。这可以通过简单的数学计算知道大概:

考察某个位置,该位置的计数器counter的值$\xi$

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$

若二项分布B(n,p)里n很大,p很小时,二项分布的极限近似分布是泊松分布$P(\lambda=k) = \frac{\lambda^k}{k!}{e}^{-\lambda}$,其中$\lambda=np=\frac{km}{n}$,并结合$k = \frac{n}{m}ln2$,可以得到,counter的期望值为:

$E(\xi) = \lambda = np = ln2 \approx 0.7$

即大量的counter的值都是0,空间效率不高。

在介绍新的Bloom Filter之前,我们一起先看看什么是所谓的d-left hashing。

d-left hashing

在d-left hashing中,我们有d张哈希子表(序号分别为1,2,…d,并且假设是从左到右),每张子表都包含B个bucket,每个bucket都包含w个cell,每个cell可以存放一个元素。

为了插入一个元素x,我们:

1,首先通过一个哈希函数hf,得到x的哈希函数值value = hf(x)

2,通过value,得到d个位置(每个位置对应每张子表),表示为:

(1,$B_1$) , (2,$B_2$),… (d,$B_d$)

其中(i,$B_i$)表示第i张子表,Bucket的index为$B_i$。

那么,到底插入哪张表呢?d-left hashing选择$B_i$中负载最小(已经存放的元素最少)的位置。注意,这里说的是bucket的负载,不是子表的负载。如果有多个子表对应的位置负载都是最小,那么选择最左边(序号最小)的子表插入。

为了查找该元素,我们需要检查d个位置,wd个cell(元素)。

d-left counting bloom filter

在基于d-left hashing的CBF中,我们有d张哈希子表(序号分别为1,2,…d,并且假设是从左到右),每张子表都包含B个bucket,每个bucket都包含w个cell,每个cell可以存放一个counter和一个fingerprint。

为了插入一个元素x,我们:

1,首先通过一个哈希函数hf,得到x的哈希函数值value = hf(x)

2,通过value,得到d个位置(每个位置对应每张子表)和对应的fingerprint,表示为d个位置向量:

(1,$B_1$,$fp_1$) , (2,$B_2$,$fp_2$),… (d,$B_d$,$fp_d$)

其中位置向量(i,$B_i$,$fp_i$)表示第i张子表,Bucket的index为$B_i$,fingerprint为$fp_i$。

3,通过d-left hashing将x插入,如果插入的位置(i,$B_i$,$fp_i$)上已经有cell的fingerprint等于$fp_i$,那么只需要将它的counter++即可。

举个栗子,假设某时刻,我们有:

d-leftcbf1

2张子表(d=2),每张子表有6个bucket(B=6),每个bucket包括3个cell(w=3),每个cell可以存放一个counter(4位表示,最大值为16)和fingerprint(6位表示)。

假如我们要插入元素x,我们对它进行hash,得到两个位置向量:

(1, 1, 010100)和(2, 2, 010101)

$d_1$子表中index为1的bucket的负载,要小于$d_2$子表中index为2的bucket的负载,因此,我们选择插入$d_1$中,如下:

d-leftcbf2

如果得到的位置向量分别是(1, 1, 001100)和(2, 2, 010101)呢?那么,还是插入到$d_1$中index为1的bucket中,但是只需要将第二个cell里的counter++即可,如下图:

d-leftcbf3

看起来很完美,但是这种方案在删除时会有问题。比如说,还是刚才的例子,我们欲插入x和y。分别得到x和y的位置向量们:

x: (1, 1, 010100)和(2, 2, 010100)

y: (1, 1, 010100)和(2, 4, 010100)

根据d-left hashing,x被插入到$d_1$中index为1的bucket中;y被插入到$d_2$中index为4的bucket中。好,这没问题。如果现在要删除y呢?我们需要检查两个位置,$d_1$中的index为1的bucket,以及$d_2$中index为4的bucket,要删哪个?fp都是010100啊。这就出现问题。

什么时候会出现这种问题?当以下条件满足时:

1,两个元素的有公共【重合】的位置向量。位置向量相同,表示同一个子表,同一个bucket,以及相同的fingerprint。

2,其中一个元素被插入了公共位置向量对应的位置,另外一个元素没有。

3,欲删除未使用公共位置向量的元素(比如说上例中的y)

为了解决这个问题,作者做了两点改进:

I 引入d轮随机置换。

置换,即一一映射。假设置换为P,输入为a和b,那么将满足:

如果$a = b$,那么$P(a) = P(b)$

如果$a \neq b$ ,那么 $P(a) \neq P(b)$

为了插入x,我们首先通过一个哈希函数hf,计算它的哈希函数值value = hf(x)。然后,我们对value进行d轮随机置换,得到d个位置向量:

$P_1(value) = (1, B_1, fp_1)$

$P_2(value) = (2, B_2, fp_2)$

……

$P_d(value) = (d, B_d, fp_d)$

这里面有一个小问题:如果要插入的元素x和y不等,那么它们的置换可能相等吗?当然可能。因为x和y虽然不等,但是它们的hash value可能相等,这样它们的置换结果即位置向量可能相同。

别忘了,我们是对x和y的hash value进行置换,不是对x和y进行置换。

网上流传很广的这篇文章的解释是错误的,小心!!!

II 插入修正

当得到d个位置向量后,和上面介绍的过程稍微不同:我们首先需要根据d个位置向量,从第1个子表开始,对每个子表$d_i$,去对应的位置$B_i$处查找是否有cell中的fp等于$fp_i$,如果有,我们把相应的counter++,插入动作完成,不用再继续检查后续子表了。

否则,当所有d个子表都没有对应的$fp_i$时,我们运用d-left hashing,插入x。

综合运用这两点,我们知道上面所说的删除时的问题已经不存在了。

假如欲插入x和y,分别对它们的hash value进行d轮(这里d=2)随机置换后,有没有可能得到如下的位置向量?

x: (1, 1, 010100)和(2, 2, 010101)

y: (1, 1, 010100)和(2, 4, 010111)

不可能。

注意到,x和y的第一个位置向量(对应第一张子表)完全相同(bucket index相同,fp也相同),也就是

$P_1(hf(x)) = P_1(hf(y))$

那么可以推出hf(x) = hf(y),也就是x和y的哈希函数值相等,那么对于任何的i都有$P_i(hf(x)) = P_i(hf(y))$。

因此:

如果$hf(x) = hf(y)$,那么$P_i(hf(x)) = P_i(hf(y))$ (i=1,2,3…d),假如先插入x后插入y,插入y的时候,会更新counter。后续删除x或者y都不存在上述问题。

如果$hf(x) \neq hf(y)$,那么$P_i(hf(x)) \neq P_i(hf(y))$ (i=1,2,3…d),那么x和y没有公共的位置向量。后续删除x或者y都不存在上述问题。

附录

如何随机置换

作者提供了一个简单的函数:

$P_i(value) = (a * value ) mod 2^B$

其中value的范围是[0, $2^B$],a是随机的一个奇数。

数学分析

首先,如果z是false positive,那么它的哈希函数值会和集合S中的某个元素的哈希函数值相等。也就是

hf(z) = hf(e) 其中 $e\in S$

这是因为,如果z是false positive,那么

$p_i(hf(z)) = p_i(hf(e))$

根据置换的性质,可得hf(z) = hf(e)

因此,false positive possibility为

$P = 1 - (1 - \frac{1}{B}*\frac{1}{2^r})^m$

根据伯努利公式,当x很小时,$(1+x)^a \approx 1 + ax$,所以

$P \approx 1 - (1 - m * \frac{1}{B} * \frac{1}{2^r}) \approx \frac{m}{B*2^r}$

那么d-left CBF的false positive和空间利用情况如何?我们下面简单分析一下:

比较嘛,肯定是相同的空间利用,比较谁的false positive possibility小;相同的false positive possibility下,谁所需空间少。

在CBF中,假设counter需要c位(上次我们分析过,c取4足矣),那么所需的空间是cn。结合$k = \frac{n}{m}ln2$,false positive possibility大约为$(0.6185)^{\frac{n}{m}}$。

在d-left CBF中,我们选择d=4,B=$\frac{m}{24}$,w=8(平均负载为6,这样$4 * \frac{m}{24} * 6 = m$),counter占用2位,fingerprint占用r位。那么它的空间占用为

$4 * \frac{m}{24} * 8 * (2+r) = \frac{4m(r+2)}{3}$

而false positive possibility的大概为 $\frac{m}{B*2^r} = 24 * \frac{1}{2^r}$ (别忘了,B=$\frac{m}{24}$ )

通过计算不难发现,当空间占用相等时,d-left CBF的false positive possibility是CBF的百分之一;当false positive possibility相等时,d-left CBF所需空间是CBF的一半。

感谢

特别感谢汪立大神参与讨论。