2021SC@SDUSC hbase源码分析（十二）HFile分析（四）

2021SC@SDUSC 2021SC@SDUSC
2021SC@SDUSC 2021SC@SDUSC

目录

• 2021SC@SDUSC hbase源码分析（十二）HFile分析（四）
• • 布隆过滤器相关Block
  • • 布隆过滤器简介
    • Bloom Index Block结构
  • 相关源码分析
  • • 元数据相关
    • 指向Bloom Block 的索引项
  • 总结

布隆过滤器相关Block

布隆过滤器简介

布隆过滤器对HBase的数据读取性能优化至关重要。前面几个博客，介绍过HBase是基于LSM树结构构建的数据库系统，数据首先写入内存，然后异步f lush到磁盘形成文件。这种架构天然对写入友好，而对数据读取并不十分友好，因为随着用户数据的不断写入，系统会生成大量文件，用户根据Key获取对应的Value，理论上需要遍历所有文件，在文件中查找指定的Key，这无疑是很低效的做法。使用布隆过滤器可以对数据读取进行相应优化，对于给定的Key，经过布隆过滤器处理就可以知道该HFile中是否存在待检索Key，如果不存在就不需要遍历查找该文件，这样就可以减少实际IO次数，提高随机读性能。布隆过滤器通常会存储在内存中，所以布隆过滤器处理的整个过程耗时基本可以忽略。

HBase会为每个HFile分配对应的位数组，KeyValue在写入HFile时会先对Key经过多个hash函数的映射，映射后将对应的数组位置为1，get请求进来之后再使用相同的hash函数对待查询Key进行映射，如果在对应数组位上存在0，说明该get请求查询的Key肯定不在该HFile中。当然，如果映射后对应数组位上全部为1，则表示该文件中有可能包含待查询Key，也有可能不包含，需要进一步查找确认。

可以想象，HFile文件越大，里面存储的KeyValue值越多，位数组就会相应越大。一旦位数组太大就不适合直接加载到内存了，因此HFile V2在设计上将位数组进行了拆分，拆成了多个独立的位数组（根据Key进行拆分，一部分连续的Key使用一个位数组）。这样，一个HFile中就会包含多个位数组，根据Key进行查询时，首先会定位到具体的位数组，只需要加载此位数组到内存进行过滤即可，从而降低了内存开销。

Bloom Index Block结构

HFile V2设计了相应的索引Bloom Index Block，对应的内存和逻辑结构如下图：

整个HFile中仅有一个Bloom Index Block数据块，位于load-on-open部分。Bloom Index Block 从大的方面看由两部分内容构成，其一是HFile中布隆过滤器的元数据基本信息，其二是构建了指向Bloom Block的索引信息。

相关源码分析

元数据相关

Bloom Index Block结构中TotalByteSize表示位数组大小，NumChunks表示Bloom Block的个数，HashCount表示hash函数的个数，HashType表示hash函数的类型，TotalKeyCount表示布隆过滤器当前已经包含的Key的数目，TotalMaxKeys表示布隆过滤器当前最多包含的Key的数目。

/**
 * At read time, the total number of chunks. At write time, the number of
 * chunks created so far. The first chunk has an ID of 0, and the current
 * chunk has the ID of numChunks - 1.
 */
protected int numChunks;

/**
 * The Bloom filter version. There used to be a DynamicByteBloomFilter which
 * had version 2.
 */
public static final int VERSION = 3;

/** Target error rate for configuring the filter and for information */
protected float errorRate;

/** The total number of keys in all chunks */
protected long totalKeyCount;
protected long totalByteSize;
protected long totalMaxKeys;

/** Hash function type to use, as defined in {@link org.apache.hadoop.hbase.util.Hash} */
protected int hashType;
/** Comparator used to compare Bloom filter keys */
protected CellComparator comparator;


private int hashCount;

上述代码中的NumChunks、TotalKeyCount、TotalMaxKeys等属性属于CompoundBloomFilterBase类，而hashCount属性在CompoundBloomFilter类中，其继承于CompoundBloomFilterBase类，并实现了BloomFilter类。

相关属性的赋值方法：

public CompoundBloomFilter(DataInput meta, HFile.Reader reader)
    throws IOException {
  this.reader = reader;

  totalByteSize = meta.readLong();
  hashCount = meta.readInt();
  hashType = meta.readInt();
  totalKeyCount = meta.readLong();
  totalMaxKeys = meta.readLong();
  numChunks = meta.readInt();
  byte[] comparatorClassName = Bytes.readByteArray(meta);
  // The writer would have return 0 as the vint length for the case of 
  // Bytes.BYTES_RAWCOMPARATOR.  In such cases do not initialize comparator, it can be
  // null
  if (comparatorClassName.length != 0) {
    comparator = FixedFileTrailer.createComparator(Bytes.toString(comparatorClassName));
  }

  hash = Hash.getInstance(hashType);
  if (hash == null) {
    throw new IllegalArgumentException("Invalid hash type: " + hashType);
  }
  // We will pass null for ROW block
  if(comparator == null) {
    index = new HFileBlockIndex.ByteArrayKeyBlockIndexReader(1);
  } else {
    index = new HFileBlockIndex.CellBasedKeyBlockIndexReader(comparator, 1);
  }
  index.readRootIndex(meta, numChunks);
}

指向Bloom Block 的索引项

Bloom Index Entry对应每一个Bloom Block的索引项，作为索引分别指向scannedblock部分的Bloom Block，Bloom Block中实际存储了对应的位数组。BloomIndex Entry的结构详见结构图中的中间部分，其中BlockKey是一个非常关键的字段，表示该Index Entry指向的Bloom Block中第一个执行Hash映射的Key。BlockOffset表示对应Bloom Block在HFile中的偏移量。

BlockOffset属性所在类：

static abstract class BlockIndexReader implements HeapSize {

  protected long[] blockOffsets;
  protected int[] blockDataSizes;
  protected int rootCount = 0;

  // Mid-key metadata.
  protected long midLeafBlockOffset = -1;
  protected int midLeafBlockOnDiskSize = -1;
  protected int midKeyEntry = -1;

  /**
   * The number of levels in the block index tree. One if there is only root
   * level, two for root and leaf levels, etc.
   */
  protected int searchTreeLevel;
    、、、
  }

BlockOffset相关赋值操作方法：

protected void add(final byte[] key, final long offset, final int dataSize) {
  blockOffsets[rootCount] = offset;
  // Create the blockKeys as Cells once when the reader is opened
  blockKeys[rootCount] = new KeyValue.KeyOnlyKeyValue(key, 0, key.length);
  blockDataSizes[rootCount] = dataSize;
  rootCount++;
}

blockKeys属性所在静态类的相关方法：

 static class ByteArrayKeyBlockIndexReader extends BlockIndexReader {

  private byte[][] blockKeys;

  public ByteArrayKeyBlockIndexReader(final int treeLevel) {
    // Can be null for METAINDEX block
  }

  @Override
  protected long calculateHeapSizeForBlockKeys(long heapSize) {
    // Calculating the size of blockKeys
    if (blockKeys != null) {
  }

  @Override
  public boolean isEmpty() {
    return blockKeys.length == 0;
  }

  /**
   * @param i
   *          from 0 to {@link #getRootBlockCount() - 1}
   */
  public byte[] getRootBlockKey(int i) {
    return blockKeys[i];
  }

  @Override
  public BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock,
      boolean cacheBlocks, boolean pread, boolean isCompaction,
      DataBlockEncoding expectedDataBlockEncoding,
      CachingBlockReader cachingBlockReader) throws IOException {
  }

  @Override
  public Cell midkey(CachingBlockReader cachingBlockReader) throws IOException {
  }

  @Override
  protected void initialize(int numEntries) {
    blockKeys = new byte[numEntries][];
  }

  @Override
  protected void add(final byte[] key, final long offset, final int dataSize) {
      、、、
            blockKeys[rootCount] = key;
      、、、
  }

  @Override
  public int rootBlockContainingKey(byte[] key, int offset, int length, CellComparator comp) {
  }

  @Override
  public int rootBlockContainingKey(Cell key) {
    // Should not be called on this because here it deals only with byte[]
  }

}

上述源代码中包括blockKeys的初始化操作方法：initialize，并且在add方法内对blockkeys属性进行了赋值操作。

总结

由上述代码分析，一次get请求根据布隆过滤器进行过滤查找需要执行以下三步操作：

1. 首先根据待查找Key在Bloom Index Block所有的索引项中根据BlockKey进行二分查找，定位到对应的Bloom Index Entry。

2. 再根据Bloom Index Entry中BlockOffset以及BlockOndiskSize加载该Key对应的位数组。

3. 对Key进行Hash映射，根据映射的结果在位数组中查看是否所有位都为1，如果不是，表示该文件中肯定不存在该Key，否则有可能存在。