HBase實現分析：HFile

在這里主要分析一下HFile V2的各個組成部分的一些細節，重點分析了HFile V2的多級索引的機制，接下去有時間的話會分析源碼中對HFile的讀寫掃描操作。

HFile和流程：

如下圖，HFile的組成分成四部分，分別是Scanned Block（數據block）、Non-Scanned block（元數據block）、Load-on-open（在hbase運行時，HFile需要加載到內存中的索引、bloom filter和文件信息）以及trailer（文件尾）。

在HFile中根據一個key搜索一個data的過程：
1、先內存中對HFile的root index進行二分查找。如果支持多級索引的話，則定位到的是leaf/intermediate index，如果是單級索引，則定位到的是data block

2、如果支持多級索引，則會從緩存/hdfs（分布式文件系統）中讀取leaf/intermediate index chunk，在leaf/intermediate chunk根據key值進行二分查找（leaf/intermediate index chunk支持二分查找），找到對應的data block。

3、從緩存/hdfs中讀取data block

4、在data block中遍歷查找key。

接下去我們分析一個HFile的各個組成部分的詳細細節，重點會分析一下HFile V2的多級索引。

1 Hbase的KeyValue結構

KeyValue結構是hbase存儲的核心，每個數據都是以keyValue結構在hbase中進行存儲。KeyValue結構是一個有固定格式的byte數組，其結構在內存和磁盤中的格式如下：

The KeyValue格式:

• Keylength
• valuelength
• key
• value

其中keylength和valuelength都是整型，表示長度。

而key和value都是byte數據，key是有固定的數據，而value是raw data。Key的格式如下。

The Key format:

• rowlength
• row (i.e., the rowkey)
• columnfamilylength
• columnfamily
• columnqualifier
• timestamp
• keytype

keytype有四種類型，分別是Put、Delete、 DeleteColumn和DeleteFamily。

特別說明：在key的所有組成成員中，columnquallfier的長度不固定，不需要用qualifier_len字段來標示其長度，因為可以通過key_len - （（key固定長度） + row_len + columnFamily_len）獲得，其中Key固定長度為 sizeof(Row_len) + sizeof(columnFamily_len) + sizeof(timestamp) + sizeof(keytype)。KeyValue是字節流形式，所以不需要考慮字節對齊。

2 File Trailer

fixedFileTrailer記錄了HFile的基本信息、各個部分的偏移值和尋址信息。fileTailer擁有固定的長度，下圖是 HFile V1和HFile V2的差別。在FileTrailer中存儲著加載一個HFile的所有信息。FileTrailer在磁盤中的分布如下圖所示：

HFile V2見圖右邊。下面列舉一下各個字段的含義和作用

BlockType：block類型。

FileInfoOffset：fileInfo的起始偏移地址。

LoadOnOpenDataOffset：需要被加載到內存中的Hfile部分的起始地址。

DataIndexEntriesNum：data index的root index chunk包含的index entry數目。

UncompressedDataIndexSize：所有的未經壓縮的data index的大小 。

TmetaIndexEntriesNum：meta index entry的數目。

totalUncompressedBytes：key value對象未經壓縮的總大小。

numEntries：key value對象的數目。

compressionCodec：編解碼算法。

numDataIndexLeves：data block的index level。

firstDataBlockOffset：第一個data block的起始偏移地址。Scan操作的起始。

lastDataBlockOffset：最后一個data block的之后的第一個byte地址。記錄scan的邊界。

version：版本號。

讀取一個HFile的流程如下：

1、 首先讀取文件尾的4字節Version信息（FileTrailer的version字段）。

2、 根據Version信息得到Trailer的長度（不同版本有不同的長度），然后根據trailer長度，加載FileTrailer。

3、 加載load-on-open部分到內存中，起始的文件偏移地址是trailer中的loadOnOpenDataOffset，load-on-open部分長度等于（HFile文件長度 - HFileTrailer長度）

如下圖所示：

Load-on-open各個部分的加載順序如下：

依次加載各部分的HFileBlock（load-on-open所有部分都是以HFileBlock格式存儲）：data index block、meta index block、FileInfo block、generate bloom filter index、和delete bloom filter。HFileBlock的格式會在下面介紹。

3 Load on open

這部分數據在HBase的region server啟動時，需要加載到內存中。包括FileInfo、Bloom filter block、data block index和meta block index。

3.1 FileInfo

FileInfo中保存一些HFile的基本信息，并以PB格式寫入到磁盤中。在0.96中是以PB格式進行保存。

3.2 HFileBlock

在hfile中，所有的索引和數據都是以HFileBlock的格式存在在hdfs中，

HFile version2的Block格式如下兩圖所示，有兩種類型，第一種類型是沒有checksum；第二種是包含checksum。對于block，下圖中的綠色和淺綠色的內存是block header；深紅部分是block data；粉紅部分是checksum。

第一種block的header長度= 8 + 2 * 4 + 8;

第二種block的header長度=8 + 2 * 4 + 8 + 1 + 4 * 2；

                      圖3.1 不支持checksum的block

                    圖 3.2 支持checksum的block

BlockType：8個字節的magic，表示不同的block 類型。

CompressedBlockSize：表示壓縮的block 數據大小（也就是在HDFS中的HFileBlock數據長度），不包括header長度。

UncompressedBlockSize：表示未經壓縮的block數據大小，不包括header長度。

PreBlockOffset：前一個block的在hfile中的偏移地址；用于訪問前一個block而不用跳到前一個block中，實現類似于鏈表的功能。

CheckSumType：在支持block checksum中，表示checksum的類型。

bytePerCheckSum：在支持checksum的block中，記錄了在checksumChunk中的字節數；records the number of bytes in a checksum chunk。

SizeDataOnDisk：在支持checksum的block中，記錄了block在disk中的數據大小，不包括checksumChunk。

DataBlock

DataBlock是用于存儲具體kv數據的block，相對于索引和meta（這里的meta是指bloom filter）DataBlock的格式比較簡單。

在DataBlock中，KeyValue的分布如下圖，在KeyValue后面跟一個timestamp。

3.3 HFileIndex

HFile中的index level是不固定的，根據不同的數據類型和數據大小有不同的選擇，主要有兩類，一類是single-level（單級索引），另一類是multi-level（多級索引，索引block無法在內存中存放，所以采用多級索引）。

HFile中的index chunk有兩大類，分別是root index chunk、nonRoot index chunk。而nonRoot index chunk又分為interMetadiate index chunk和leaf index chunk，但intermetadiate index chunk和leaf index chunk在內存中的分布是一樣的。

對于meta block和bloom block，采用的索引是single-level形式，采用single-level時，只用root index chunk來保存指向block的索引信息（root_index-->xxx_block）。

而對于data，當HFile的data block數量較少時，采用的是single level(root_index-->data_block)。當data block數量較多時，采用的是multi-level，一般情況下是兩級索引，使用root index chunk和leaf index chunk來保存索引信息(root_index-->leaf_index-->data_block)；但當data block數量很多時，采用的是三級索引，使用root index chunk、intermetadiate index chunk和leaf index chunk來保存指向數據的索引（root_index-->intermediate_index-->leaf_index-->data_block）。

所有的index chunk都是以HFileBlock格式進行存放的，首先是一個HFileBlock Header，然后才是index chunk的內容。

Root Index

Root index適用于兩種情況：

1、作為data索引的根索引。

2、作為meta和bloom的索引。

在Hfile Version2中，Meta index和bloom index都是single-level，也都采用root索引的格式。Data index可以single-level和multi-level的這形式。Root index可以表示single-level index也可以表示multi-level的first level。但這兩種表示方式在內存中的存儲方式是由一定差別，見圖3.3和3.4。

                         圖3.3 single-level root index

                              圖3.4 multi-level root index

Single-level

root索引是會被加載到內存中。在磁盤的格式見圖3.4。

index entry的組成含義如下：

1、Offset (long)：表示索引對應的block在Hfile文件中的偏移值。

2、On-disk size (int)：表示索引對應的block在disk（Hfile文件）中的長度。

3、Key：Key是在內存中存儲的byte array，分成兩部分，其中一部分是key長度，另一部分是key數據。 Key值應該是index entry對應的data block的first row key。不論這個block是leaf index chunk還是data block或者是meta block。

Mid-key and multi-level

對于multi-level root index，除了上面index entry數組之外還帶有格外的數據mid-key的信息，這個mid-key是用于在對hfile進行split時，快速定位HFile的中間位置所使用。Multi-level root index在硬盤中的格式見圖3.4。

Mid-key的含義：如果HFile總共有n個data block，那么mid-key就是能定位到第(n - 1)/2個data block的信息。

Mid-key的信息組成如下：

1、Offset：所在的leaf index chunk的起始偏移量

2、On-disk size：所在的leaf index chunk的長度

3、Key：在leaf index chunk中的位置。

如下圖所示：第(n – 1)/2個data block位于第i個LeafIndexChunk，如果LeafIndexChunk[i]的第一個data block的序號為k，那么offset、on-disk size以及key的值如下：

Offset為 LeafIndexChunk[i] 的offset

On-disk size為LeafIndexChunk[i] 的size

Key為(n – 1)/2 – k

                                              圖 3.6 mid-key示意圖

NonRoot index

當HFile以multi-level來索引數據block時，會引入nonRoot index與root index一起構建整個索引。Nonroot索引包括Intermediate index和leaf index這兩種類型，這兩種索引在disk中的格式一致，都統一使用NonRoot格式進行存放，但用途和存放的位置不同。

Intermediate index是在當HFile的數據block太多或內存存在限制時，使用兩級數據索引時導致root index chunk超過其最大值，所以通過增加索引的級數，將intermediate index作為second level，以此來保證root index chunk的大小在一定限制內，減少加載到內存中時的內存消耗。

intermediate index chunk中的每個index Entry都指向一個leaf index chunk。Intermediate index chunk在加載時不會被加載到內存中。Intermediate index chunk在HFile中存儲的位置是緊挨著root index chunk。在寫入root index chunk時，會檢查root index chunk的容量是否超過最大值，如果超過，那么將root index chunk劃分成多個intermediate index chunk，然后重新生成一個root index entry，新root index entry中的每一個index entry都是指向intermediate index chunk。先將各個intermediate index chunk寫入到disk中，然后再寫入root index chunk，如下圖所示。

HFile使用multi-level index來索引data block時，Leaf index chunk是作為最末一級，leaf index chunk中的index entry是保存指向datablock的數據。Leaf index chunk也是以nonRoot格式來進行存儲的，見圖3.4，與intermediate index chunk一樣，都樣不會在加載hfile時被加載到內存中。

nonRoot索引增加了secondIndexOffset，作為二級索引，用于實現二分查找；而而nonRoot索引不會加載到內存中。增加 nonRoot索引的目的就是解決在存儲數據過大時導致索引的數量量也增加，無法加載到內存中，從而增加了seek和read時的開銷。NonRoot index在磁盤中的格式如下圖：

                                             圖 non Root index

1、BlockNumber：索引條目的數目。

2、secondaryIndexOffset：每一個secondaryIndexOffset都是表示index entry在leaf索引block中的相對偏移值（相對于第一個index entry），它是作為index entry的二級索引，用于實現快速搜索（二分法查找）。如下圖所示，第一個secondaryIndexOffset的偏移值為0，往后都是index entry在disk中的長度相加。

3、curTotalNonRootEntrySize：leaf索引塊中所有index entry在disk中總的大小。

4、Index Entries：每一個條目都包含三個部分

Offset：entry引用的block在文件中的偏移地址

On-disk size：block在硬盤中的大小

Key：block中的first row key. key不需要像在root索引中按照key length和keyvalue進行保存，因為有secondaryIndexOffset的存在，已經不需要通過key length來識別各個index entry的邊界。

NonRoot索引的二分查找實現

1、首先NonRoot索引中的Index_entry需要按照順序排列，這個順序是通過key值的大小來決定的。key值應該就是row的key值。

2、使用secondaryIndexOffset實現二分查找。

二分查找的原理

如果要查找一個InputKey所處的位置

    首先將位置初始化，row為0,high為BlockNumber - 1

   循環：

       mid= (low + high) / 2

       定位到中間位置的index Entry

       將index Entry的key值與InputKey進行比較

           如果 key > inputKey

               Row = mid + 1

           如果 key == inputKey

               找到正確對象，返回

           如果 key < inputKey

               High = mid – 1

快速定位

                          3.9 indexEntry偏移值計算

每一個secondaryIndexOffset是四個字節，secondaryIndexOffset的值是index Entry的相對偏移。見上圖，對于一個序號為i的index entry，其在leaf索引chunk中的絕對偏移值為

“( BlockNumber + 2 ) * sizeof( int ) + secondaryIndexOffset[i]”

       圖 3.10 key值相對于index Entry的偏移

見上圖，那么key的長度等于indexEntryOffset[i + 1] - （indexEntryOffset[i] + 4 * 8）

Bloom filter

在HFile中，bloom filter的meta index也是作為load-on-open的一部分保存，bloom fiter有兩種類型，一種是generate bloom filter，用于快速確定key是否存儲在hbase中；另一種是delete bloom filter，用于快速確定key是否已經被刪除。

Bloom filter meta index在硬盤中的格式如下：

Bloom meta index在磁盤中的格式如上圖所示。

Version：表示版本；

totalByteSize：表示bloom filter的位組的bit數。

HashCount：表示一個key在位組中用幾個bit位來進行定位。

HashType：表示hash函數的類型。

totalKeyCount：表示bloom filter當前已經包含的key的數目.

totalKeyMaxs：表示bloom filter當前最多包含的key的數目.

numChunks：表示bloom filter中包含的bloom filter block的數目.

comparatorName：表示比較器的名字.

接下去是每一個Bloom filter block的索引條目。