HBase中BloomFilter是什么

这篇文章给大家分享的是有关HBase中BloomFilter是什么的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

成都一家集口碑和实力的网站建设服务商,拥有专业的企业建站团队和靠谱的建站技术,十余年企业及个人网站建设经验 ,为成都千余家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设,成都品牌网站建设,同时也为不同行业的客户提供成都网站设计、做网站、成都外贸网站建设公司的服务,包括成都电商型网站制作建设,装修行业网站制作建设,传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选创新互联建站

Bloom Filter 是什么?

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

在计算机科学中,我们常常会碰到时间换空间或者空间换时间的情况,即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素:错误率。在使用Bloom Filter判断一个元素是否属于某个集合时,会有一定的错误率。也就是说,有可能把不属于这个集合的元素误认为属于这个集合(False Positive),但不会把属于这个集合的元素误认为不属于这个集合(False Negative)。在增加了错误率这个因素之后,Bloom Filter通过允许少量的错误来节省大量的存储空间。简单地说就是宁可放过也不杀错

它的用法其实是很容易理解的,我们拿个HBase中应用的例子来说下,我们已经知道rowKey存放在HFile中,那么为了从一系列的HFile中查询某个rowkey,我们就可以通过 Bloom Filter 快速判断 rowkey 是否在这个HFile中,从而过滤掉大部分的HFile,减少需要扫描的Block

 

Bloom Filter的工作原理

BloomFilter对于HBase的随机读性能至关重要,对于get操作以及部分scan操作可以剔除掉不会用到的HFile文件,减少实际IO次数,提高随机读性能。在此简单地介绍一下Bloom Filter的工作原理,Bloom Filter使用位数组来实现过滤,初始状态下位数组每一位都为0,如下图所示:

HBase中BloomFilter是什么  

假如此时有一个集合S = {x1, x2, … xn},Bloom Filter使用k个独立的hash函数,分别将集合中的每一个元素映射到{1,…,m}的范围。对于任何一个元素,被映射到的数字作为对应的位数组的索引,该位会被置为1。比如元素x1被hash函数映射到数字8,那么位数组的第8位就会被置为1。下图中集合S只有两个元素x和y,分别被3个hash函数进行映射,映射到的位置分别为(0,3,6)和(4,7,10),对应的位会被置为1:

HBase中BloomFilter是什么  

现在假如要判断另一个元素是否是在此集合中,只需要被这3个hash函数进行映射,查看对应的位置是否有0存在,如果有的话,表示此元素肯定不存在于这个集合,否则有可能存在。下图所示就表示z肯定不在集合{x,y}中:

HBase中BloomFilter是什么  

从上面的内容我们可以得知,Bloom Filter有两个很重要的参数

哈希函数个数

位数组的大小

 

HFile中 Bloom Filter 相关的Block

我们来理一下 HFile 中和 Bloom Filter 相关的Block,

Scanned Block Section(扫描HFile时被读取):Bloom Block

Load-on-open-section(regionServer启动时加载到内存):BloomFilter Meta Block、Bloom Index Block

  • Bloom Block:Bloom数据块,存储Bloom的位数组

  • Bloom Index Block:Bloom数据块的索引

  • BloomFilter Meta Block:从HFile角度看bloom数据块的一些元数据信息,大小个数等等。

HBase中每个HFile都有对应的位数组,KeyValue在写入HFile时会先经过几个hash函数的映射,映射后将对应的数组位改为1,get请求进来之后再进行hash映射,如果在对应数组位上存在0,说明该get请求查询的数据不在该HFile中。

HFile中的Bloom Block中存储的就是上面说得位数组,当HFile很大时,Data Block 就会很多,同时KeyValue也会很多,需要映射入位数组的rowKey也会很多,所以为了保证准确率,位数组就会相应越大,那Bloom Block也会越大,为了解决这个问题就出现了Bloom Index Block,作用和 Data Index Block 类似,一个HFile中有多个Bloom Block(位数组),根据rowKey拆分,一部分连续的Key使用一个位数组。这样查询rowKey就要先经过Bloom Index Block(在内存中)定位到Bloom Block,再把Bloom Block加载到内存,进行过滤。

 

其他应用场景

谓词下推

1.Bloom Filter 在小表处生成;

2.广播到大表处;

3.大表根据 Bloom Filter 进行过滤;

4.剩下的数据传入 JoinNode 进行关联。

注意:Bloom Filter 处理 join 并不是总是有效地,如果JOIN两边的表并不能过滤到很多数据,例如左表和右表中Join键的差集并不大,这种情况下反而浪费了资源计算Bloom Filter和应用Bloom Filter

 

如何使用 Bloom Filter

Google Guava library为我们提供了Bloom Filter的实现,直接用就可以啦:com.google.common.hash.BloomFilter

private final BloomFilter bloomFilter = BloomFilter.create(new Funnel() {
        private static final long serialVersionUID = 1L;
        @Override
        public void funnel(String arg0, PrimitiveSink arg1) {
            arg1.putString(arg0, Charsets.UTF_8);
        }
    }, 1024*1024*32);

public synchronized boolean contains(String id){
        if(StringUtils.isEmpty(id)){
            return true;
        }
        boolean exists = bloomFilter.mightContain(id);  //布隆过滤器是否包含这个id
        if(!exists){
            bloomFilter.put(id);   //添加进布隆过滤器
        }
        return exists;
    }

感谢各位的阅读!关于“HBase中BloomFilter是什么”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!


网站标题:HBase中BloomFilter是什么
分享URL:http://hbruida.cn/article/gejsoe.html