布隆过滤器在HBase中的应用

块索引机制

在讨论布隆过滤器在HBase中的应用之前，先介绍一下HBase的块索引机制。块索引是HBase固有的一个特性，因为HBase的底层数据是存储在HFile中的，而每个HFile中存储的是有序的<key, value>键值对，HFile文件内部由连续的块组成，每个块中存储的第一行数据的行键组成了这个文件的块索引，这些块索引信息存储在文件尾部。当HBase打开一个HFile时，块索引信息会优先加载到内存；HBase首先在内存的块索引中进行二分查找，确定可能包含给定键的块，然后读取磁盘块找到实际想要的键。

注意这里的块不是HDFS的块，HBase块的默认大小是64KB。可以根据需要配置不同的大小，对于顺序访问较多的表，建议使用较大的块；随机访问较多的表，建议使用较小的块。

但实际应用中，仅仅只有块索引满足不了需求，这是因为，块索引能帮助我们更快地在一个文件中找到想要的数据，但是我们可能依然需要扫描很多文件。而布隆过滤器就是为解决这个问题而生。因为布隆过滤器的作用是，用户可以立即判断一个文件是否包含特定的行键，从而帮我们过滤掉一些不需要扫描的文件。如下图所示，块索引显示每个文件中都可能包含对应的行键，而布隆过滤器能帮我们跳过一些明显不包含对应行键的文件。

如上图所示，布隆过滤器不能明确指出哪一个文件一定包含所查找的行键，布隆过滤器的结果有误差存在。当布隆过滤器判断文件中不包含对应的行时，这个答案是绝对正确的；但是，当布隆过滤器判断得到文件中包含对应行时，这个答案却有可能是错的。也就是说，HBase还是有可能加载了不必要的块。尽管如此，布隆过滤器还是可以帮助我们跳过一些明显不需要扫描的文件。另外，错误率可以通过调整布隆过滤器所占空间的大小来调整，通常设置错误率为1%。


需要注意的是，使用布隆过滤器，并不一定能立即提升个别的get操作性能，因为同一时间可能有多个客户端向HBase发送请求，当负载过大时，HBase的性能受限于读磁盘的效率。但是，使用了布隆过滤器之后，可以减少不必要的块加载，从而可以提高整个集群的吞吐率。并且，因为HBase加载的块数量少了，缓存波动也降低了，进而提高了读缓存的命中率。


然而，相比与布隆过滤器的优点，它的缺点显得如此微不足道，就是需要占用少量的存储空间。在使用布隆过滤器时，需要注意两个问题

什么时候应该使用布隆过滤器

根据上面的描述，布隆过滤器的主要作用，是帮助HBase跳过那些显然不包括所查找数据的底层文件。那么，当所查找的数据均匀分布在所有文件中（当用户定期更新所有行时，就可能导致这种情况），布隆过滤器的作用就微乎其微，反而浪费了存储空间。相反，如果我们查找的数据只包含在少部分的文件中，就应该果断使用布隆过滤器。

选择行级还是行加列级布隆过滤器

布隆过滤器是hbase中的高级功能，它能够减少特定访问模式（get/scan）下的查询时间。不过由于这种模式增加了内存和存储的负担，所以被默认为关闭状态。

hbase支持如下类型的布隆过滤器：
1、NONE 不使用布隆过滤器
2、ROW 行键使用布隆过滤器
3、ROWCOL 列键使用布隆过滤器
其中ROWCOL是粒度更细的模式。

很显然，行加列级因为粒度更细，占用的存储空间也就越多。因此，如果用户总是读取整行的数据，行级布隆过滤器就够用了。在可以选择的情形下，尽可能使用行级布隆过滤器，因为它在额外的空间开销和利用过滤存储文件提升性能之间取得了更好的平衡。

例如：ROW 使用场景，假设有2个Hfile文件hf1和hf2， hf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v） hf2包含kv3（r3 cf:q1 v）、kv4（r4 cf:q1 v） 如果设置了CF属性中的bloomfilter（布隆过滤器）为ROW，那么get(r1)时就会过滤hf2，get(r3)就会过滤hf1 。

ROWCOL使用场景，假设有2个Hfile文件hf1和hf2， hf1包含kv1（r1 cf:q1 v）、kv2（r2 cf:q1 v） hf2包含kv3（r1 cf:q2 v）、kv4（r2 cf:q2 v） 如果设置了CF属性中的bloomfilter为ROW，无论get(r1,q1)还是get(r1,q2)，都会读取hf1+hf2；而如果设置了CF属性中的bloomfilter为ROWCOL，那么get(r1,q1)就会过滤hf2，get(r1,q2)就会过滤hf1。
注意：ROW和ROWCOL只是名字上有联系，但是ROWCOL并不是ROW的扩展，也不能取代ROW

布隆过滤器的存储在哪

对于hbase而言，当我们选择采用布隆过滤器之后，HBase会在生成StoreFile（HFile）时包含一份布隆过滤器结构的数据，称其为MetaBlock；MetaBlock与DataBlock（真实的KeyValue数据）一起由LRUBlockCache维护。所以，开启bloomfilter会有一定的存储及内存cache开销。但是在大多数情况下，这些负担相对于布隆过滤器带来的好处是可以接受的。

采用布隆过滤器后，hbase如何get数据

在读取数据时，hbase会首先在布隆过滤器中查询，根据布隆过滤器的结果，再在MemStore中查询，最后再在对应的HFile中查询。

采用布隆过滤器后，hbase如何Scan数据

get操作会enable bloomfilter帮助剔除掉不会用到的Storefile,在scan初始化时（get会包装为scan）对于每个storefile会做shouldSeek的检查，如果返回false，则表明该storefile里没有要找的内容，直接跳过

if (memOnly == false    
            && ((StoreFileScanner) kvs).shouldSeek(scan, columns)) {    
          scanners.add(kvs);    
}

shouldSeek方法：如果是scan直接返回true表明不能跳过，然后根据bloomfilter类型检查。

if (!scan.isGetScan()) {    
        return true;    
}    
byte[] row = scan.getStartRow();    
switch (this.bloomFilterType) {    
  case ROW:    
    return passesBloomFilter(row, 0, row.length, null, 0, 0);    
   
  case ROWCOL:    
    if (columns != null && columns.size() == 1) {    
      byte[] column = columns.first();    
      return passesBloomFilter(row, 0, row.length, column, 0, column.length);    
    }    
    // For multi-column queries the Bloom filter is checked from the    
    // seekExact operation.    
    return true;    
   
  default:    
    return true;  
}

指明qualified的scan在配了rowcol的情况下会剔除不会用掉的StoreFile。
对指明了qualify的scan或者get进行检查：seekExactly

// Seek all scanners to the start of the Row (or if the exact matching row    
// key does not exist, then to the start of the next matching Row).    
if (matcher.isExactColumnQuery()) {    
  for (KeyValueScanner scanner : scanners)    
  scanner.seekExactly(matcher.getStartKey(), false);    
} else {    
  for (KeyValueScanner scanner : scanners)    
  scanner.seek(matcher.getStartKey());    
}

如果bloomfilter没命中，则创建一个很大的假的keyvalue，表明该storefile不需要实际的scan

public boolean seekExactly(KeyValue kv, boolean forward)    
      throws IOException {    
    if (reader.getBloomFilterType() != StoreFile.BloomType.ROWCOL ||    
        kv.getRowLength() == 0 || kv.getQualifierLength() == 0) {    
      return forward ? reseek(kv) : seek(kv);    
    }    
    
    boolean isInBloom = reader.passesBloomFilter(kv.getBuffer(),    
        kv.getRowOffset(), kv.getRowLength(), kv.getBuffer(),    
        kv.getQualifierOffset(), kv.getQualifierLength());    
    if (isInBloom) {    
      // This row/column might be in this store file. Do a normal seek.    
      return forward ? reseek(kv) : seek(kv);    
    }    
    
    // Create a fake key/value, so that this scanner only bubbles up to the top    
    // of the KeyValueHeap in StoreScanner after we scanned this row/column in    
    // all other store files. The query matcher will then just skip this fake    
    // key/value and the store scanner will progress to the next column.    
    cur = kv.createLastOnRowCol();    
    return true;    
}

这边为什么是rowcol才能剔除storefile纳，很简单，scan是一个范围，如果是row的bloomfilter不命中只能说明该rowkey不在此storefile中，但next rowkey可能在。


而rowcol的bloomfilter就不一样了，如果rowcol的bloomfilter没有命中表明该qualifiy不在这个storefile中，因此这次scan就不需要scan此storefile了！


1.任何类型的get（基于rowkey和基于row+col）bloomfilter都能生效，关键是get的类型要匹配bloomfilter的类型
2.基于row的scan是没办法优化的
3.row+col+qualify的scan可以去掉不存在此qualify的storefile，也算是不错的优化了，而且指明qualify也能减少流量，因此scan尽量指明qualify。