布隆过滤器的应用

Bloom Filter的中文翻译叫做布隆过滤器，是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。如文章标题所述，本文只是做简单介绍，属于科普文章。 

 

应用场景 

在正式介绍Bloom Filter算法之前，先来看看什么时候需要用到Bloom Filter算法。 

1. HTTP缓存服务器、Web爬虫等 

主要工作是判断一条URL是否在现有的URL集合之中（可以认为这里的数据量级上亿）。 

对于HTTP缓存服务器，当本地局域网中的PC发起一条HTTP请求时，缓存服务器会先查看一下这个URL是否已经存在于缓存之中，如果存在的话就没有必要去原始的服务器拉取数据了（为了简单起见，我们假设数据没有发生变化），这样既能节省流量，还能加快访问速度，以提高用户体验。 

对于Web爬虫，要判断当前正在处理的网页是否已经处理过了，同样需要当前URL是否存在于已经处理过的URL列表之中。 

 

2. 垃圾邮件过滤 

假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤，那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通信邮件数量非常大（也可以认为数据量级上亿），那么也可以使用Bloom Filter算法。 

 

1、BloomFilter能解决什么问题? 

以少量的内存空间判断一个元素是否属于这个集合, 代价是有一定的错误率 

 

2、工作原理 

1. 初始化一个数组, 所有位标为0,  A={x1, x2, x3,…,xm}  (x1, x2, x3,…,xm 初始为0) 

2. 将已知集合S中的每一个数组, 按以下方式映射到A中 

2.0  选取n个互相独立的hash函数 h1, h2, … hk 

2.1  将元素通过以上hash函数得到一组索引值 h1(xi), h2(xi),…,hk(xi) 

2.2  将集合A中的上述索引值标记为1(如果不同元素有重复, 则重复覆盖为1, 这是一个觅等操作) 

3.  对于一个元素x, 将其根据2.0中选取的hash函数, 进行hash, 得到一组索引值 h1(x), h2(x), …,hk(x) 

如果集合A中的这些索引位置上的值都是1, 表示这个元素属于集合S, 否则则不属于S 

 

 

3、几个前提 

1. hash函数的计算不能性能太差, 否则得不偿失 

2. 任意两个hash函数之间必须是独立的. 

即任意两个hash函数不存在单一相关性, 否则hash到其中一个索引上的元素也必定会hash到另一个相关的索引上, 这样多个hash没有意义 

 

 

4、错误率 

工作原理的第3步, 的出来的结论, 一个是绝对靠谱的, 一个是不能100%靠谱的。在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。关于具体的错误率，这和最优的哈希函数个数以及位数组的大小有关，而这是可以估算求得一个最优解的： 

哈希函数个数k、位数组大小m及字符串数量n之间存在相互关系。相关文献证明了对于给定的m、n，当 k = ln(2)* m/n 时出错的概率是最小的。  具体的请看：http://blog.csdn.net/jiaomeng/article/details/1495500 

 

 

5、基本特征 

从以上对基本原理和数学基础的分析，我们可以得到Bloom filter的如下基本特征，用于指导实际应用。 

(1)存在一定错误率，发生在正向判断上（存在性），反向判断不会发生错误（不存在性）； 

(2)错误率是可控制的，通过改变位数组大小、hash函数个数或更低碰撞率的hash函数来调节；

(3)保持较低的错误率，位数组空位至少保持在一半以上; 

(4)给定m和n，可以确定最优hash个数，即k = ln2 * (m/n)，此时错误率最小； 

(5)给定允许的错误率E，可以确定合适的位数组大小，即m >= log2(e) * (n * log2(1/E))，继而确定hash函数个数k； 

(6)正向错误率无法完全消除，即使不对位数组大小和hash函数个数进行限制，即无法实现零错误率； 

(7)空间效率高，仅保存“存在状态”，但无法存储完整信息，需要其他数据结构辅助存储； 

(8)不支持元素删除操作，因为不能保证删除的安全性。 

 

 

6、应用场景举例： 

（1）拼写检查、数据库系统、文件系统 

（2）假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL，怎样知道蜘蛛是否已经访问过呢？ 

（3）网络应用 

P2P网络中查找资源操作，可以对每条网络通路保存Bloom Filter，当命中时，则选择该通路访问。 

广播消息时，可以检测某个IP是否已发包。 

检测广播消息包的环路，将Bloom Filter保存在包里，每个节点将自己添加入Bloom Filter。 

信息队列管理，使用Counter Bloom Filter管理信息流量。 

（4）垃圾邮件地址过滤 

像网易，QQ这样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址，就需要1.6GB 的内存（用哈希表实现的具体办法是将每一个email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有50%，因此一个email 地址需要占用十六个字节。一亿个地址大约要1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百GB 的内存。而Bloom Filter只需要哈希表1/8 到1/4 的大小就能解决同样的问题。Bloom Filter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。 

（5）Bloomfilter在HBase中的作用 

 HBase利用Bloomfilter来提高随机读（Get）的性能，对于顺序读（Scan）而言，设置Bloomfilter是没有作用的（0.92以后，如果设置了bloomfilter为ROWCOL，对于指定了qualifier的Scan有一定的优化，但不是那种直接过滤文件，排除在查找范围的形式） 

 Bloomfilter在HBase中的开销？ 

Bloomfilter是一个列族（cf）级别的配置属性，如果你在表中设置了Bloomfilter，那么HBase会在生成StoreFile时包含一份bloomfilter结构的数据，称其为MetaBlock；MetaBlock与DataBlock（真实的KeyValue数据）一起由LRUBlockCache维护。所以，开启bloomfilter会有一定的存储及内存cache开销。 

Bloomfilter如何提高随机读（Get）的性能？ 

对于某个region的随机读，HBase会遍历读memstore及storefile（按照一定的顺序），将结果合并返回给客户端。如果你设置了bloomfilter，那么在遍历读storefile时，就可以利用bloomfilter，忽略某些storefile。 

注意：hbase的bloom filter是惰性加载的，在写压力比较大的情况下，会有不停的compact并产生storefile，那么新的storefile是不会马上将bloom filter加载到内存的，等到读请求来的时候才加载。 

这样问题就来了，第一，如果storefile设置的比较大，max size为2G，这会导致bloom filter也比较大；第二，系统的读写压力都比较大。这样或许会经常出现单个 GET请求花费3-5秒的超时现象。