当前位置: 首页 > 网站开发 > 正文

BloomFilter应用与D-Lelft BloomFilter实现

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

此篇文章是开发过程中对BloomFilter应用场景的一些介绍,另外项目中实现了D-Left BloomFilter,相关实现时一些注意的地方,简单介绍下!

首先看一些应用场景:

1.海量的黑白名单。

2.爬虫抓取时重复的URL处理。

3.数据key是否存在检测

4.(一些面试题几十亿不重复整数中判断其中一个整数是否存在的问题,BitMap/BloomFilter能很好的解决)

对于以上提出的三种场景,如果数据量相对较少,可以将数据存储在数据库,或者加载内存中判断对应的黑白名单是否存在判断即可。

可是当数据量达到很大时,比如1亿条的黑白名单,假如每个名单占用空间为10byte,对于查询中将遇到两种问题,如果数据都在数据库中且并发量很大,每次查询将给DB带来的压力不可想象的。 另外如果所有名单加载到缓存中,将占据的内存空间是:1G,如果数据量更大,所占空间更多。

对于以上问题,如果通过BloomFilter,通过牺牲一定的准确率,使用1G/80 和内存空间,就能解决此问题。

一.什么是BloomFilter?

BloomFilter是一种高效的随机数据结构,被用于检测一个元素是否是一个集合中的一个元素,这种检测只会对在集合内的数据错判,而不会对不是集合内的数据进行错判,这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况,即如果它判断元素不在集合里,此元素一定不是集合中的元素,如果判断元素在集合里,有可能存在一定的错误率,可见 Bloom filter 是牺牲了正确率换取时间和空间。(因此需要注意使用时应用场景)

二.BloomFilter实现:

Bloom filter 采用的是哈希函数(hash fucnction)的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突,解决方法就是使用 k 个哈希 函数对应 k 个点,如果所有点都是 1 的话,那么元素在集合内,如果有 0 的话,元素则不再集合内。(实现BloomFilter时,这个hash的k数可以设定,一般是4或者8)

BloomFilter测试发现,要想保持错误率低,最好让位数组有一半还空着。

三.BloomFilter应用的地方

BloomFilter在开源项目中有很多地方都有使用,其中Hadoop源码中实现了使用OpenBitSet实现了BloomFilter,另外还有CountingBloomFilter的实现。 另外Hbase源码中也有BloomFilter的实现,其中有BloomFilter的各种变种,都是跟据自己特定场景需要,进行相关实现。

四.BloomFilter的缺点:

标准的BloomFilter只支持插入和查找两种操作,如果表达的集合是静态集合的时候,在初始化集合大小,确定hash k的个数,控制错误率的基础上,BloomFilter可以很好的满足需求。但是对于一些动态集合,BloomFilter不满足需求了,其不支持删除操作,现引入Counting BloomFilter,能解决相关问题。

五.什么是Counting BloomFilter

Counting Bloom Filter,它将标准Bloom Filter位数组的每一位扩展为一个小的计数器(Counter),在插入元素时给对应的k(k为哈希函数个数)个Counter的值分别加1,删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价,给Bloom Filter增加了删除操作.如图示:
1353841394_1713
此方法实现是给每位增加一个4位的计数器,处理碰撞问题,即相当于原BloomFilter5倍的空间,可以动态维护BloomFilter, 当计数超过4位时,则溢出不处理,hash函数选择合理,数据集构造时合理,一般不会出现溢出。

Counting BloomFilter有删除操作后,其应用价值变得更广。

但是Counting BloomFilter也存在很明显的缺点:由于每个bucket负载不均衡,很多空间都被浪费掉了。因此引入了D Left BloomFilter.

六.D-Left Bloom Filter介绍

D-Left Bloom Filter也是BloomFilter的一种变种,它在比Counting BloomFilter使用更少的空间下,带来了删除操作,同时还能带来更少的错误率。
在引入D-Left Bloom Filter之间首先介绍下d-Left hash:有d个哈希表以及d个哈希函数,每一次插入时都先计算d个哈希值,然后通过计算出的地址h[key]来判断在这个位置上的负载是多少,把键值插入到负载小的表中,当负载一样时,则插入到Left表中。

d-left counting bloom filter的构造过程:在没有应用d-left hashing的情况下,我们使用一个哈希函数,把它的hash value分成两段,高位作存储地址,低位作fingerprint。现在要应用d-left hashing,有d个存储地址需要生成,我们仍然用一个哈希函数,但把它的hash value分成d+1段:高位的d段分别用作d个存储地址,每个子表对应一个,剩下的低位部分作为fingerprint在添加一个key时,先对它作一次hash,得到d个存储位置和一个fingerprint,然后判断d个位置中的负载情况,并在负载最轻的几个位置中选择最左边的插入。如果选择的位置已经存储了相同的fingerprint,就把那个cell的counter加1。在删除一个key时,同样地作一次hash,然后在d个存储位置查找相应的fingerprint,如果找到就将这个cell置空或者将相应的counter减1。

通过以上构造,对于不同元素,相同 fingerprint存在位置选择重合的问题!

给出的解决方案是:将hashing的整个操作分成两个阶段。第一阶段,我们用一个哈希函数H计算要插入元素x的hash value,记做fx;第二阶段,为了获得d个存储位置,我们另外引入d个随机置换(random permutation)。令H(x) = fx = (b, r),其中b是bucket index,表示存储位置;r是remainder,表示要存储的fingerprint。然后令d个置换为:

P1(fx) = (b1, r1), P2(fx) = (b2, r2), … ,Pd(fx) = (bd, rd).其中Pi(fx)对应着x在第i个子表的存储位置和fingerprint。我们知道置换意味着一一对应,因此不同元素(的hash value)作置换之后的值仍然不同。这样我们就达到了前面提到的让不同元素的d个位置选择完全没有重合的目标。

引入随机置换避免了位置重合之后,我们还需要在插入元素之前作一项工作。每次插入一个元素时,先要在它的d个位置选择中检查是否已经存有相同的fingerprint,如果有,就把相应cell的counter加1。由于不同元素的存储位置不会重合,因此只有在碰撞的情况下才会出现两个相同fingerprint能存入同一组存储位置的情况。而我们一旦在插入之前作了检测,再作删除操作时就永远不会发现d个位置中有两个完全相同的fingerprint。

至于选择什么样的置换,论文作者给出的建议是:简单的线性函数。如果哈希函数的取值范围为[2q],随机置换可以写成:

Pi(H(x)) = aH(x) mod 2q
 
其中a是区间[2q]中的随机奇数。

(对于我们实现中选择的奇数是定义的一常量,方便定义)

七.D-Left Bloom Filter实现

使用java 实现D-Left BloomFilte实现过程中,主要注意的地方有:

1.D-Left Bloom Filter对于子表数的选择的问题,跟据实现需要选择,跟据集合数据量,我们的数据量在百万级别,选用了四张子表,每张子表对应bsize个桶.
2.初始化集合m.
3.每个桶存储8个cell,每个cell存储x位手印,每个cell的计数为y bit,(x位手印数与y位计数器,跟据集合数据量选择手印的大小,count计数可为2位或者4)
4.采用数据结构建议使用byte[][]多维数组实现。bitsets不好控制。
5.对于hash函数的选择,可任意。(我们项目 中使用md5,128位,足够使用了).
6.实现过程中通过hash截取,以及相关组装,置换操作,通过位操作可以很高效的实现。(置换函数可以是:Pi(H(x)) = aH(x) mod 2q,  其中a为随机奇数,以及H(x)为新组装的高位地址+手印,2q为h(x)位数对应最大值)

相关测试数据:
经过简单测试,错误率在百万分之一左右。集合在50万左右。
在五十万元素后,增加一个元素的时间在0.2ms到0.3ms左右,查询一个元素是否存在0.1ms左右,删除在0.3到0.4ms左右。
对于元素的分配,插入五十万数据,每个表的分布如下:

table 0:135203
table 1:128226
table 2:122795
table 3:113776

相对而言,每个表的数据分配还是比较均匀,这样大大的节省了空间。

项目中使用D-Left BloomFilter主要是对于一个key的查询,由于外部查询时,很多不存在的key查询我们相关数据库,这样会对系统DB有很大的负担,通过缓存查,相应的命中率也很低,为了解决这些问题,我们把相应的此key的值会在系统初始化时通过D-Left BloomFilter时加载一次,相应的add,remove操作也支持,这样在能过滤掉大部分不存在系统中的key,而对于判断存在的key,由于存在部分错误率,我们再会从缓存或者数据库中去判断是否存在,这样相应的命中率就会很高,也保证了数据的正确性。

本文固定链接: http://www.chepoo.com/bloomfilter-d-lelft-bloomfilter-apply.html | IT技术精华网

BloomFilter应用与D-Lelft BloomFilter实现:等您坐沙发呢!

发表评论