Press "Enter" to skip to content

【数据挖掘】BloomFilter在HBase的应用

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

导言:在计算机领域中,会遇到一个问题就是: 如何高效判断元素w是否存在于集合A之中? 首先想到的解决方法就是使用哈希搜索,把集合A中的元素一个个放到哈希表中,然后在哈希表中查一下元素w即可。 哈希搜索的解决方法可以解决小数据量场景下元素存在性判定,但是如果A中元素数据量巨大,甚至数据量远远超过机器内存空间,该如何解决问题? 针对大数据量场景,可以实现一个基于磁盘和内存的哈希索引来解决。 而另一种低成本的方式就是借助布隆过滤器来实现。

 

01

 

什幺是布隆过滤器?

 

布隆过滤器 (Bloom Filter)是1970年由布隆提出的。它是由一个长度为N的 二进制 数据array和一系列随机 映射函数 组出 。布隆过滤器的算法,首先将数组array每个元素初始设为0。然后,对集合A中的每个元素w, 做k次哈希,第i次哈希值对N取模得到一个index(i),  即index(i)=HASH_i(w)%N,将array数组中的array[index(i)]设置为1。最终array变成一个某些元素为1的01数组。

 

下面举个例子,如下图1所示,条件:A={x, y, z}, N=18, K=3。

 

 

1) 初始化时,array=00000000000000000。

 

2)对于元素x,HASH_0(x) % N=1, HASH_1(x) % N=5, HASH_2(x) % N=13, 所以array=010001000000010000

 

3)对于元素y,HASH_0(y) % N=4, HASH_1(y) % N=11, HASH_2(y) % N=16, 所以array=010011000001010010

 

4)对于元素z,HASH_0(z) % N=3, HASH_1(z) % N=5, HASH_2(z) % N=11, 所以array=010111000001010010

 

经过上诉步骤,集合A最终得到的布隆过滤器串为:010111000001010010

 

那幺对于元素w,HASH_0(w) % N=4, HASH_1(w) % N=13, HASH_2(w) % N=15

 

可以发现,布隆过滤器串中的第15位为0,因此可以确认w肯定不在集合A中。因为如果w在A中,那幺第15位必定为1。

 

如果有另外一个元素t,HASH_0(t) % N=5, HASH_1(t) % N=11, HASH_2(t) % N=13。我们发现第5、11、13位都是1,但是却没法肯定t一定在A中。

 

因此,布隆过滤器的一个重要的特性, 对任意给定元素w, 给出的存在性结果为两种:

 

 

w可能存在于集合A中

 

w肯定不在集合A中

 

 

感兴趣的读者,可以阅读论文:

 

Burton Howard Bloom 于 1970 年所提出《 Space/Time Trade-offs in Hash Coding with Allowable Errors 》。

 

在论文中证明了,当 N = K*|A|/In2时(|A|表示集合A的个数),能保证最佳误判率(过滤器判定元素可能在集合中但实际不在集合中的占比 )。 举个例子,若集合 由 20个元素,K取3时,则设计一个N=3*20/In2=87二进制串来保存布隆过滤器串较为合适。

 

02

 

HBase与布隆过滤器

 

HBase:Hadoop Database,是一个高 可靠 性、高性能、面向列、可伸缩的 分布式存储系统 ,利用HBase技术可在廉价PC Server上搭建起大规模 结构 化 存储 集群。

 

经过上面对于布隆过滤器的介绍,可以知道布隆过滤器只需占用极小的空间,便可给出“可能存在”和“肯定不存在”的存在性判断,因此可以利用布隆过滤器过滤很多不必要的数据块,从而节省大量的磁盘IO。HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块,从而节省大量磁盘IO。

 

举个例子,集合A中的元素在HBase里按照顺序存储在不同的数据分块中,如下图2所示。每个Block数据块计算出一个布隆过滤器串,对于元素w计算每个数据块的过滤串的存在性结果,通过与每个块的布隆过滤串对比计算,就可以知道元素w肯定不在哪些block块。HBase的GET操作只需要查找那些可能存在的数据Block中,从而节省了大量的磁盘IO。

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注