布隆过滤器 详解

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

它是一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

它是一种space efficient的概率型数据结构,在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素,但不可以删除已有元素。其中的元素越多,false positive rate(误报率)越大,但是false negative (漏报)是不可能的。

基本概念

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 $O_{(n)}$,$O_{(\log n)}$,$O_{(n/k)}$。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 $O_{(k)}$。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k和m相同,使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。

节约缓存空间(空值的映射),不再需要空值映射。

减少数据库或缓存的请求次数。

提升业务的处理效率以及业务隔离性。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

时间和空间上的优势

当可以承受一些误报时,布隆过滤器比其它表示集合的数据结构有着很大的空间优势。例如self-balance BST, tries, hash table或者array, chain,它们中大多数至少都要存储元素本身,对于小整数需要少量的bits,对于字符串则需要任意多的bits(tries是个例外,因为对于有相同prefixes的元素可以共享存储空间);而chain结构还需要为存储指针付出额外的代价。对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为$O_{(k)}$,与集合中元素的多少无关,这是其他数据结构都不能完成的。

如果可能元素范围不是很大,并且大多数都在集合中,则使用确定性的bit array远远胜过使用布隆过滤器。因为bit array对于每个可能的元素空间上只需要1 bit,add和query的时间复杂度只有$O_{(1)}$。注意到这样一个哈希表(bit array)只有在忽略collision并且只存储元素是否在其中的二进制信息时,才会获得空间和时间上的优势,而在此情况下,它就有效地称为了k=1的布隆过滤器。

而当考虑到collision时,对于有m个slot的bit array或者其他哈希表(即k=1的布隆过滤器),如果想要保证1%的误判率,则这个bit array只能存储m/100个元素,因而有大量的空间被浪费,同时也会使得空间复杂度急剧上升,这显然不是space efficient的。解决的方法很简单,使用k>1的布隆过滤器,即k个hash function将每个元素改为对应于k个bits,因为误判度会降低很多,并且如果参数k和m选取得好,一半的m可被置为为1,这充分说明了布隆过滤器的space efficient性。

实例一

为了说明Bloom Filter存在的重要意义,举一个实例:

假设要你写一个网络爬虫程序(web crawler)。由于网络间的链接错综复杂,爬虫在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道爬虫程序已经访问过那些URL。给一个URL,怎样知道爬虫程序是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。
  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。

方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。

下面引入本篇的主角–Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。

Bloom Filter算法如下:

创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1 。

加入字符串过程

下面是每个字符串处理的过程,首先是将字符串str“记录”到BitSet中的过程:对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1。

很简单吧?这样就将字符串str映射到BitSet中的k个二进制位了。

检查字符串是否存在的过程

下面是检查字符串str是否被BitSet记录过的过程:

对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在。

若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)

但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。

删除字符串过程

字符串加入了就被不能删除了,因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF),这是一种基本Bloom Filter的变体,CBF将基本Bloom Filter每一个Bit改为一个计数器,这样就可以实现删除字符串的功能了。

Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。

实例二

以垃圾邮件过滤中黑白名单为例:现有1亿个email的黑名单,每个都拥有8 bytes的指纹信息,则可能的元素范围为$2^{64} = 8 * 10^{18} bits = 10^9 GB$,对于bit array来说是根本不可能的范围,而且元素的数量(即email列表)为 $10^8$,相比于元素范围过于稀疏,而且还没有考虑到哈希表中的collision问题。

若采用哈希表,由于大多数采用open addressing来解决collision,而此时的search时间复杂度为 :
$$
\cfrac{1}{1-\cfrac{n}{m}}
$$

即若哈希表半满(n/m = 1/2),则每次search需要probe 2次,因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes,总空间为:
$$
\cfrac{10^8*8 bytes}{50\%} = 1.6 GB
$$

若采用Perfect hashing(这里可以采用Perfect hashing是因为主要操作是search/query,而并不是add和remove),虽然保证worst-case也只有一次probe,但是空间利用率更低,一般情况下为50%,worst-case时有不到一半的概率为25%。

若采用布隆过滤器,取k=8。因为n为1亿,所以总共需要$8*10^8$bits被置位为1,又因为在保证误判率低且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为:
$$
m = \cfrac{10^8*8 bits}{50\%} = 1.6*10^9 bits = 200MB
$$

所需空间比上述哈希结构小得多,并且误判率在万分之一以下。

误判概率的证明和计算

假设布隆过滤器中的hash function满足simple uniform hashing假设:每个元素都等概率地hash到m个slot中的任何一个,与其它元素被hash到哪个slot无关。若m为bit数,则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:
$$
1 - \cfrac{1}{m}
$$
则k个hash function中没有一个对其置位的概率为:
$$
(1 - \cfrac{1}{m})^k
$$
如果插入了n个元素,但都未将其置位的概率为:
$$
(1 - \cfrac{1}{m})^{kn}
$$
则此位被置位的概率为:
$$
1-(1 - \cfrac{1}{m})^{kn}
$$
现在考虑query阶段,若对应某个待query元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:
$$
(1-(1 - \cfrac{1}{m})^{kn})^k
$$
由于$(1+x)^{\cfrac{1}{x}} \backsim e$,当 $x\to0$时,并且$-\cfrac{1}{m}$当m很大时趋近于0,所以
$$
(1-(1-\cfrac{1}{m})^{kn})^k = (1-(1-\cfrac{1}{m})^{-m*\cfrac{-kn}{m}})^k \backsim (1-e^{-\cfrac{nk}{m}})^k
$$
从上式中可以看出,当m增大或n减小时,都会使得误判率减小,这也符合直觉。

现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:
$$
f_{(k)}=(1-e^{-\cfrac{nk}{m}})^k
$$
设$b=e^{\cfrac{n}{m}}$,则简化为$f_{(k)}=(1-b^{-k})^k$
两边取对数$\ln f_{(k)}=k*\ln (1-b^{-k})$
两边对k求导
$$
\cfrac{1}{f_{(k)}}*f^{\prime}_{(k)} = \ln (1-b^{-k})+k*\cfrac{1}{1-b^{-k}}*(-b^{-k})*\ln b*(-1)=\ln (1-b^{-k})+k*\cfrac{b^{-k}*\ln b}{1-b^{-k}}
$$

下面求最值
$$
\ln (1-b^{-k})+k*\cfrac{b^{-k}*\ln b}{1-b^{-k}} = 0 \\
\Rightarrow (1-b^{-k})*\ln (1-b^{-k}) = -k*b^{-k}*\ln b \\
\Rightarrow (1-b^{-k})*\ln (1-b^{-k}) = b^{-k}*\ln b^{-k} \\
\Rightarrow 1-b^{-k} = b^{-k} \\
\Rightarrow b^{-k}=\cfrac{1}{2} \\
\Rightarrow e^{-\cfrac{kn}{m}}=\cfrac{1}{2} \\
\Rightarrow \cfrac{kn}{m} = \ln 2 \\
\Rightarrow k = \ln 2*\cfrac{m}{n}=0.7*\cfrac{m}{n}
$$
因此,即当$k=0.7*\cfrac{m}{n}$时误判率最低,此时误判率为:$P_{(error)}=(1-\cfrac{1}{2})^k=2^{(-k)}=2^{-\ln 2*\cfrac{m}{n}} \approx 0.6185^{\cfrac{m}{n}}$

可以看出若要使得误判率≤1/2,则:
$$
k \geqslant 1 \Rightarrow \cfrac{m}{n} \geqslant\cfrac{1}{\ln 2}
$$
这说明了若想保持某固定误判率不变,布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。

设计和应用布隆过滤器的方法

应用时首先要先由用户决定要add的元素数n和希望的误差率P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数,之后的所有参数将由系统计算,并由此建立布隆过滤器。

系统首先要计算需要的内存大小m bits:

$$
P=2^{-\ln 2*\cfrac{m}{n}} \Rightarrow \ln P = \ln 2*(-\ln 2)*\cfrac{m}{n} \Rightarrow m = -\cfrac{n*\ln P}{(\ln 2)^2}
$$

再由m,n得到hash function的个数:
$$
k = \ln 2*\cfrac{m}{n} = 0.7*\cfrac{m}{n}
$$
至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行query。

根据公式,当k最优时:
$$
P_{(error)}=2^{-k} \\
\Rightarrow\log_2P=-k\\
\Rightarrow k=\log_2\cfrac{1}{P}\\
\Rightarrow\ln 2\cfrac{m}{n}=\log_2\cfrac{1}{P}\\
\Rightarrow\cfrac{m}{n}=\ln 2*\log_2\cfrac{1}{P}=1.44*\log_2\cfrac{1}{P}
$$
因此可验证当P=1%时,存储每个元素需要9.6 bits:
$$
\cfrac{m}{n}=1.44*\log_2\cfrac{1}{0.01}=9.6 bits
$$
而每当想将误判率降低为原来的1/10,则存储每个元素需要增加4.8 bits:
$$
\cfrac{m}{n}=1.44*(log_210a-log_2a)=1.44*log_210=4.8bits
$$

这里需要特别注意的是,9.6 bits/element不仅包含了被置为1的k位,还把包含了没有被置为1的一些位数。此时的
$$
k=0.7*\cfrac{m}{n}=0.7*9.6=6.72bits
$$
才是每个元素对应的为1的bit位数。
$k=0.7*\cfrac{m}{n}$从而使得$P_{(error)}$最小时,我们注意到:$P_{(error)}=(1-e^{-\cfrac{nk}{m}})^k$中的$e^{-\cfrac{nk}{m}}=\cfrac{1}{2}$即$(1-\cfrac{1}{m})^{kn}=\cfrac{1}{2}$此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。

Bloom Filter参数选择

哈希函数选择

哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。

m,n,k值,我们如何取值

我们定义:

可能把不属于这个集合的元素误认为属于这个集合(False Positive)

不会把属于这个集合的元素误认为不属于这个集合(False Negative)。

哈希函数的个数k、位数组大小m、加入的字符串数量n的关系。哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889 ,即10万次的判断中,会存在9次误判,对于一天1亿次的查询,误判的次数为9000次。

算法分析

我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时,这个位数组中某一位还是0的概率是:
$$
p^\prime = (1-\cfrac{1}{m})^{kn} \approx e^{-kn/m}
$$

False Positive的概率是:
$$
(1-(1-\cfrac{1}{m})^{kn})^k \approx (1-e^{kn/m})^k
$$

$p\prime$表示1的概率,k次方表示8次hash都为1的概率

当 $k = \ln 2*m/n$ 时,右边的等式值最小,此时等式转变成:

$$
(\cfrac{1}{2})^k = (0.6185)^{m/n}
$$


- - - - - - - - End Thank For Your Reading - - - - - - - -