大数据去重之Bloom Filter

Bloom Filter是一种高效利用空间的概率数据结构，由Burton HowardBloom于1970年发明，用于检测一个元素是否属于一个集合，但是并不严格要求100%正确的场合。

Bloom-Filter解决的问题

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

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

将访问过的URL保存到数据库。

用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。

URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

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：消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。

  实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

Bloom-Filter的基本思想

  上述方法4，单个Hash函数高概率的冲突（碰撞）的问题，为了减少冲突，我们可以多引入几个Hash函数，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。

原理要点：一是位数组， 而是k个独立hash函数。

1）位数组：

  假设Bloom Filter使用一个m比特的数组来保存信息，初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0，即BF整个数组的元素都设置为0。

image

2）添加元素，k个独立hash函数

  为了表达S=这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到的范围中。

  当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i个哈希函数映射的位置hashi(x)就会被置为1（1≤i≤k）。

  注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=2，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。

image

3）判断元素是否存在集合

  在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hashi(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2可能属于这个集合，并不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive。

image

4）删除元素

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

算法优化

通过上面的解释我们可以知道，如果想设计出一个好的布隆过滤器，我们必须遵循以下准则：

好的哈希函数能够尽可能的返回宽范围的哈希值。

位数组的大小（用m表示）非常重要：如果太小，那么所有的位很快就都会被赋值为1，这样就增加了误判的几率。

哈希函数的个数（用k表示）对索引值的均匀分配也很重要。

计算m的公式如下：

这里p为可接受的误判率。

计算k的公式如下：

这里k=哈希函数个数，m=位数组个数，n=待检测元素的个数。

Bloom-Filter的应用

由于存在false positive，会导致不在BF中的值，被误判在其中；所以可以添加一个白名单；当BF返回告诉你这个值存在的时候，需要去storage中查找，如下图：

image

Bloom-Filter的java实现

  BitSet是位操作的对象，值只有0或1（即true 和 false），内部维护一个long数组，初始化只有一个long segement，所以BitSet最小的size是64；随着存储的元素越来越多，BitSet内部会自动扩充，一次扩充64位，最终内部是由N个long segement 来存储；

  默认情况下，BitSet所有位都是0即false；

测试函数：

guava中Bloom-Filter

pom.xml:

用法如下：

指定fpp：

判断是否已经存在