Load-on-open-section:这部分数据在RegionServer启动时,实例化Region并创建HStore时会将所有StoreFile的Load-on-open-section加载进内存,主要存放了Root Data Index,meta Index,File Info及BooleamFilter的metadata等。除了Fields for midkey外,每部分都是一个HFileBlock.下面会详细去讲这块。
Header:header total size is HFILEBLOCK_HEADER_SIZE
blockType:
onDiskSizeWithoutHeader:
uncompressedSizeWithoutHeader:
prevBlockOffset:The offset of the previous block of the same type (8 bytes). This is used to navigate to the previous block without having to go to the block index。
onDiskDataSizeWithHeader:the size of data 'on disk', including header, excluding checksums (4 bytes)
Raw/Compressed/Encrypted/Encoded data: The compression algorithm is the same for all the blocks in an HFile。If compression is NONE, this is just raw, serialized Cells.
在结构上每个位数组对应HFile中一个Bloom Block,为了方便根据Key定位具体需要加载哪个位数组,HFile V2又设计了对应的索引Bloom Index Block,对应的内存和逻辑结构图如下:
Bloom Index Block结构中totalByteSize表示位数组的bit数,numChunks表示Bloom Block的个数,hashCount表示hash函数的个数,hashType表示hash函数的类型,totalKeyCount表示bloom filter当前已经包含的key的数目,totalMaxKeys表示bloom filter当前最多包含的key的数目, Bloom Index Entry对应每一个bloom filter block的索引条目,作为索引分别指向’scanned block section’部分的Bloom Block,Bloom Block中就存储了对应的位数组。
Bloom Index Entry的结构见上图左边所示,BlockOffset表示对应Bloom Block在HFile中的偏移量,FirstKey表示对应BloomBlock的第一个Key。根据上文所说,一次get请求进来,首先会根据key在所有的索引条目中进行二分查找,查找到对应的Bloom Index Entry,就可以定位到该key对应的位数组,加载到内存进行过滤判断。也就是说加载到内存中的并不是一个HFile中全部的位数组,减少了内存的占用量。
在trailer中并没有布隆过滤器的偏移,如何读到Bloom Index Block的?在trailer中有一个loadOnOpen区,即这个HFile一开始就会加载到内存的区域,对应在HfileReader中维持了一个List<HFileBlock> loadOnOpenBlocks = new ArrayList<HFileBlock>(); 而这个HFileBlock的list中有布隆过滤器的meta 数据信息。
V2版本Index Block有两类:Root Index Block和NonRoot Index Block,其中NonRoot Index Block又分为Intermediate Index Block和Leaf Index Block两种。HFile中索引结构类似于一棵树,Root Index Block表示索引数根节点,Intermediate Index Block表示中间节点,Leaf Index block表示叶子节点,叶子节点直接指向实际数据块。
HFile中除了Data Block需要索引之外,上文提到过Bloom Block也需要索引,索引结构实际上就是采用了single-level结构,文中Bloom Index Block就是一种Root Index Block。
对于Data Block,由于HFile刚开始数据量较小,索引采用single-level结构,只有Root Index一层索引,直接指向数据块。当数据量慢慢变大,Root Index Block满了之后,索引就会变为mutil-level结构,由一层索引变为两层,根节点指向叶子节点,叶子节点指向实际数据块。如果数据量再变大,索引层级就会变为三层。
下面就针对Root index Block和NonRoot index Block两种结构进行解析,因为Root Index Block已经在上文分析过,此处简单带过,重点介绍NonRoot Index Block结构(InterMediate Index Block和Ieaf Index Block在内存和磁盘中存储格式相同,都为NonRoot Index Block格式)。
Root Index Block
Root Index Block表示索引树根节点索引块,可以作为bloom的直接索引,也可以作为data索引的根索引。而且对于single-level和mutil-level两种索引结构对应的Root Index Block略有不同,本文以mutil-level索引结构为例进行分析(single-level索引结构是mutual-level的一种简化场景),在内存和磁盘中的格式如下图所示:
Root Index Block会在HFile解析的时候直接加载到内存中,也就是我们前面提到的List<HFileBlock> loadOnOpenBlocks = new ArrayList<HFileBlock>();中,此处需要注意在Trailer Block中有一个字段为dataIndexCount,就表示此处Index Entry的个数。因为Index Entry并不定长,只有知道Entry的个数才能正确的将所有Index Entry加载到内存。
NonRoot Index Block
当HFile中Data Block越来越多,single-level结构的索引已经不足以支撑所有数据都加载到内存,需要分化为mutil-level结构。mutil-level结构中NonRoot Index Block作为中间层节点或者叶子节点存在,无论是中间节点还是叶子节点,其都拥有相同的结构,如下图所示:
和Root Index Block相同,NonRoot Index Block中最核心的字段也是Index Entry,用于指向叶子节点块或者数据块。不同的是,NonRoot Index Block结构中增加了block块的内部索引entry Offset字段,entry Offset表示index Entry在该block中的相对偏移量(相对于第一个index Entry),用于实现block内的二分查找。所有非根节点索引块,包括Intermediate index block和leaf index block,在其内部定位一个key的具体索引并不是通过遍历实现,而是使用二分查找算法,这样可以更加高效快速地定位到待查找key。
类HFileBlockIndex分析:该类应该是代表了RootIndex
类中说明,root level index会加载到内存中,同时root-level index 也应该有一个entries个数numEntries,在Root Index Block的图示中并没有给出。
类中有一个静态类BlockIndexReader,其中有一个searchTreeLevel属性,The number of levels in the block index tree. One if there is only root level, two for root and leaf levels, etc。
在BlockIndexReader中,还有以下属性:
其中blockKey应该是各个entry起始的key(First keys of the key range corresponding to each index entry)。BlockKeys,blockOffsets,blockDataSize三者是一一对应的。