2021SC@SDUSC hbase代码分析（十三）HFile分析（5）

2021SC@SDUSC hbase代码分析（十三）HFile分析（5） 2021SC@SDUSC hbase源码分析（十三）HFile分析（五）

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

目录

• 2021SC@SDUSC hbase源码分析（十三）HFile分析（五）
• • 索引相关Block
  • • HFile索引简介
    • 索引结构
  • 1. Root Index Block
  • • 简介
    • 源码分析
  • 2. NonRoot Index Block
  • • 简介
    • 相关分析

索引相关Block HFile索引简介

根据索引层级的不同，HFile中索引结构分为两种：single-level和multi-level，前者表示单层索引，后者表示多级索引，一般为两级或三级。HFile V1版本中只有single-level一种索引结构，V2版本中引入多级索引。之所以引入多级索引，是因为随着HFile文件越来越大，Data Block越来越多，索引数据也越来越大，已经无法全部加载到内存中，多级索引可以只加载部分索引，从而降低内存使用空间。同布隆过滤器内存使用问题一样，这也是V1版本升级到V2版本最重要的因素之一。

V2版本Index Block有两类：Root Index Block和NonRoot Index Block。NonRootIndex Block又分为Intermediate Index Block和Leaf Index Block两种。HFile中索引是树状结构，Root Index Block表示索引数根节点，Intermediate Index Block表示中间节点，Leaf Index Block表示叶子节点，叶子节点直接指向实际DataBlock

索引结构

HFile索引结构如下图：

1. Root Index Block 简介

Root Index Block表示索引树根节点索引块，可以作为Bloom Block的直接索引，也可以作为Data Block索引的根索引。在Single-Level和Multi-Level中两种索引结构对应的Root Index Block稍有差异，如图示：

源码分析

上图中的Index Entry表示具体的索引对象，每个索引对象由3个字段组成：

1. Block Offset表示索引指向Data Block的偏移量；

2. BlockDataSize表示索引指向Data Block在磁盘上的大小；

3. BlockKey表示索引指向Data Block中的第一个Key。

protected long[] blockOffsets;
protected int[] blockDataSizes;


public long getRootBlockOffset(int i) {
    return blockOffsets[i];
}


public int getRootBlockDataSize(int i) {
    return blockDataSizes[i];
}

除此之外，还有另外3个字段用来记录MidKey的相关信息，这些信息用于在对HFile进行split *** 作时，快速定位HFile的切分点位置。需要注意的是单层索引结构和多级索引结构相比，仅缺少与MidKey相关的这三个字段。

public void readMultiLevelIndexRoot(HFileBlock blk,
    final int numEntries) throws IOException {
  DataInputStream in = readRootIndex(blk, numEntries);
  // after reading the root index the checksum bytes have to
  // be subtracted to know if the mid key exists.
  int checkSumBytes = blk.totalChecksumBytes();
  if ((in.available() - checkSumBytes) < MID_KEY_metaDATA_SIZE) {
    // No mid-key metadata available.
    return;
  }
  midLeafBlockOffset = in.readLong();
  midLeafBlockonDiskSize = in.readInt();
  midKeyEntry = in.readInt();
}

上述代码是对MidKeyEntry实体进行赋值 *** 作的方法。

Root Index Block位于整个HFile的“ load-on-open ”部分，因此会在RegionServer打开HFile时直接加载到内存中。此处需要注意的是，在Trailer Block中有一个字段为DataIndexCount，表示Root Index Block中Index Entry的个数。

private int dataIndexCount;


@org.apache.hbase.thirdparty.com.google.common.annotations.VisibleForTesting
    HFileProtos.FileTrailerProto toProtobuf() {
    HFileProtos.FileTrailerProto.Builder builder = HFileProtos.FileTrailerProto.newBuilder()
        .setFileInfoOffset(fileInfoOffset)
        .setLoadOnOpenDataOffset(loadOnOpenDataOffset)
        .setUncompressedDataIndexSize(uncompressedDataIndexSize)
        .setTotalUncompressedBytes(totalUncompressedBytes)
        .setDataIndexCount(dataIndexCount)
        .setmetaIndexCount(metaIndexCount)
        .setEntryCount(entryCount)
        .setNumDataIndexLevels(numDataIndexLevels)
        .setFirstDataBlockOffset(firstDataBlockOffset)
        .setLastDataBlockOffset(lastDataBlockOffset)
        .setComparatorClassName(getHbase1CompatibleName(comparatorClassName))
        .setCompressionCodec(compressionCodec.ordinal());
    if (encryptionKey != null) {
        builder.setEncryptionKey(UnsafeByteOperations.unsafeWrap(encryptionKey));
    }
    return builder.build();
}

只有知道Entry的个数才能正确地将所有Index Entry加载到内存。

2. NonRoot Index Block 简介

当HFile中Data Block越来越多，单层结构的根索引会不断膨胀，超过一定阈值之后就会分裂为多级结构的索引结构。多级结构中根节点是Root Index Block。而索引树的中间层节点和叶子节点在Hbase中存储为NonRoot Index Block，但从Block结构的视角分析，无论是中间节点还是叶子节点，其都拥有相同的结构。其结构如下图：

相关分析

和Root Index Block相同，NonRoot Index Block中最核心的字段也是IndexEntry，用于指向叶子节点块或者Data Block。

但是Non-Root Index Block多了EntryOffset 和 numEntires

numEntires: 记录entry的数量

EntryOffset： 是Non-Root Index Block内部索引字段，表示Index Entry在该block中的相对偏移量，相对于第一个Index Entry，用于实现Block内部的二分查找，故针对Non-Root Index Block,在其内部定位一个key的具体索引，不是通过遍历而是通过二分查找实现，可以更加高效快速定位到待查找的key