2021SC@SDUSC hbase代码分析(十二)HFile分析(4)

2021SC@SDUSC hbase源码分析(十二)HFile分析(四)

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

目录

布隆过滤器相关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,对应的内存和逻辑结构如下图:

2021SC@SDUSC hbase代码分析(十二)HFile分析(4)

整个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,否则有可能存在。

上一篇:设计模式之模板方法模式


下一篇:Laravel5.8反序列化复现分析