在各色數據庫系統百花齊放的今天，能讓大家銘記的，往往是一個數據庫所能帶給大家的差異化能力。正如梁寧老師的產品思維課程中所講到的，這是一個數據庫系統所能帶給產品使用者的"確定性"。

差異化能力通常需要從數據庫底層開始構筑，而數據存儲方式顯得至關重要，因為它直接關乎數據寫入與讀取的效率。在一個系統中，這兩方面的能力需要進行很好的權衡：如果設計有利于數據的快速寫入，可能意味著查詢時需要需要花費較大的精力去組織數據，反之，如果寫入時花費精力去更好的組織數據，查詢就會變的非常輕松。

探討數據庫的數據存儲方式，其實就是探討數據如何在磁盤上進行有效的組織。因為我們通常以如何高效讀取和消費數據為目的，而不是數據存儲本身。在RDBMS領域，因為鍵與數據的組織方式的區別，有兩種表組織結構最為常見，一種是鍵與數據聯合存儲的索引組織表結構，在這種表結構下，查到鍵值意味著查找到數據;另外一種是鍵與數據分離存儲的堆表結構。在這種表結構下，查找到鍵以后，只是拿到了數據記錄的物理地址，還需要基于該物理地址去查找具體的數據記錄。在大數據分析領域，有幾種通用的文件格式，如Parquet, RCFile, ORCFile，CarbonData等等，這些文件大多基于列式的設計結構，來加速通用的分析型查詢。但在實時數據庫領域，卻以各種私有的文件格式最為常見，如Bigtable的SSTable，HBase的HFile，Kudu的DiskRowSets，Cassandra的變種SSTable，MongoDB支持的每一種Storage Engine都是私有的文件格式設計，等等。

本文將詳細探討HBase的HFile設計，第一部分為HFile原理概述，第二部分介紹了一個HFile從無到有的生成過程，最后部分列出了幾點與HFile有關的附加信息。

HFile原理概述

最初的HFile格式(HFile V1)，參考了Bigtable的SSTable以及Hadoop的TFile(HADOOP-3315)。如下圖所示：

 

HFile在生成之前，數據在內存中已經是按序組織的。存放用戶數據的KeyValue，被存儲在一個個默認為64kb大小的Data Block中，在Data Index部分存儲了每一個Data Block的索引信息{Offset，Size，FirstKey}，而Data Index的索引信息{Data Index Offset, Data Block Count}被存儲在HFile的Trailer部分。除此以外，在Meta Block部分還存儲了Bloom Filter的數據。下圖更直觀的表達出了HFile V1中的數據組織結構：

 

這種設計簡單、直觀。但用過0.90或更老版本的同學，對于這個HFile版本所存在的問題應該深有痛楚：Region Open的時候，需要加載所有的Data Block Index數據，另外，第一次讀取時需要加載所有的Bloom Filter數據到內存中。一個HFile中的Bloom Filter的數據大小可達百MB級別，一個RegionServer啟動時可能需要加載數GB的Data Block Index數據。這在一個大數據量的集群中，幾乎無法忍受。

Data Block Index究竟有多大?

一個Data Block在Data Block Index中的索引信息包含{Offset, Size, FirstKey}，BlockOffset使用Long型數字表示，Size使用Int表示即可。假設用戶數據RowKey的長度為50bytes，那么，一個64KB的Data Block在Data Block Index中的一條索引數據大小約為62字節。

假設一個RegionServer中有500個Region，每一個Region的數量為10GB(假設這是Data Blocks的總大小)，在這個RegionServer上，約有81920000個Data Blocks，此時，Data Block Index所占用的大小為81920000*62bytes，約為4.7GB。

這是HFile V2設計的初衷，HFile V2期望顯著降低RegionServer啟動時加載HFile的時延，更希望解決一次全量加載數百MB級別的BloomFilter數據帶來的時延過大的問題。下圖是HFile V2的數據組織結構：

 

較之HFile V1，我們來看看HFile V2的幾點顯著變化：

1.分層索引

無論是Data Block Index還是Bloom Filter，都采用了分層索引的設計。

Data Block的索引，在HFile V2中做多可支持三層索引：最底層的Data Block Index稱之為Leaf Index Block，可直接索引到Data Block;中間層稱之為Intermediate Index Block，最上層稱之為Root Data Index，Root Data index存放在一個稱之為”Load-on-open Section“區域，Region Open時會被加載到內存中。基本的索引邏輯為：由Root Data Index索引到Intermediate Block Index，再由Intermediate Block Index索引到Leaf Index Block，最后由Leaf Index Block查找到對應的Data Block。在實際場景中，Intermediate Block Index基本上不會存在，文末部分會通過詳細的計算闡述它基本不存在的原因，因此，索引邏輯被簡化為：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的對應的Data Block。

Bloom Filter也被拆成了多個Bloom Block，在”Load-on-open Section”區域中，同樣存放了所有Bloom Block的索引數據。

2.交叉存放

在”Scanned Block Section“區域，Data Block(存放用戶數據KeyValue)、存放Data Block索引的Leaf Index Block(存放Data Block的索引)與Bloom Block(Bloom Filter數據)交叉存在。

3.按需讀取

無論是Data Block的索引數據，還是Bloom Filter數據，都被拆成了多個Block，基于這樣的設計，無論是索引數據，還是Bloom Filter，都可以按需讀取，避免在Region Open階段或讀取階段一次讀入大量的數據，有效降低時延。

從0.98版本開始，社區引入了HFile V3版本，主要是為了支持Tag特性，在HFile V2基礎上只做了微量改動。在下文內容中，主要圍繞HFile V2的設計展開。

HFile生成流程

在本章節，我們以Flush流程為例，介紹如何一步步生成HFile的流程，來加深大家對于HFile原理的理解。

起初，HFile中并沒有任何Block，數據還存在于MemStore中。

Flush發生時，創建HFile Writer，第一個空的Data Block出現，初始化后的Data Block中為Header部分預留了空間，Header部分用來存放一個Data Block的元數據信息。

而后，位于MemStore中的KeyValues被一個個append到位于內存中的第一個Data Block中：

 

注：如果配置了Data Block Encoding，則會在Append KeyValue的時候進行同步編碼，編碼后的數據不再是單純的KeyValue模式。Data Block Encoding是HBase為了降低KeyValue結構性膨脹而提供的內部編碼機制。上圖中所體現出來的KeyValue，只是為了方便大家理解。當Data Block增長到預設大小(默認64KB)后，一個Data Block被停止寫入，該Data Block將經歷如下一系列處理流程：1.如果有配置啟用壓縮或加密特性，對Data Block的數據按相應的算法進行壓縮和加密。

 

2.在預留的Header區，寫入該Data Block的元數據信息，包含{壓縮前的大小，壓縮后的大小，上一個Block的偏移信息，Checksum元數據信息}等信息，下圖是一個Header的完整結構：

 

3.生成Checksum信息。

 

4.Data Block以及Checksum信息通過HFile Writer中的輸出流寫入到HDFS中。

5.為輸出的Data Block生成一條索引記錄，包含這個Data Block的{起始Key，偏移，大小}信息，這條索引記錄被暫時記錄到內存的Block Index Chunk中：

 

注：上圖中的firstKey并不一定是這個Data Block的第一個Key，有可能是上一個Data Block的最后一個Key與這一個Data Block的第一個Key之間的一個中間值。具體可參考附錄部分的信息。至此，已經寫入了第一個Data Block，并且在Block Index Chunk中記錄了關于這個Data Block的一條索引記錄。隨著Data Blocks數量的不斷增多，Block Index Chunk中的記錄數量也在不斷變多。當Block Index Chunk達到一定大小以后(默認為128KB)，Block Index Chunk也經與Data Block的類似處理流程后輸出到HDFS中，形成第一個Leaf Index Block：

 

此時，已輸出的Scanned Block Section部分的構成如下：

 

正是因為Leaf Index Block與Data Block在Scanned Block Section交叉存在，Leaf Index Block被稱之為Inline Block(Bloom Block也屬于Inline Block)。在內存中還有一個Root Block Index Chunk用來記錄每一個Leaf Index Block的索引信息：

 

從Root Index到Leaf Data Block再到Data Block的索引關系如下：

 

我們先假設沒有Bloom Filter數據。當MemStore中所有的KeyValues全部寫完以后，HFile Writer開始在close方法中處理最后的”收尾”工作：

1.寫入最后一個Data Block。

2.寫入最后一個Leaf Index Block。

如上屬于Scanned Block Section部分的”收尾”工作。

3.如果有MetaData則寫入位于Non-Scanned Block Section區域的Meta Blocks，事實上這部分為空。

4.寫Root Block Index Chunk部分數據：

如果Root Block Index Chunk超出了預設大小，則輸出位于Non-Scanned Block Section區域的Intermediate Index Block數據，以及生成并輸出Root Index Block(記錄Intermediate Index Block索引)到Load-On-Open Section部分。

如果未超出大小，則直接輸出為Load-On-Open Section部分的Root Index Block。

5.寫入用來索引Meta Blocks的Meta Index數據(事實上這部分只是寫入一個空的Block)。

6.寫入FileInfo信息，FileInfo中包含：

Max SequenceID, MajorCompaction標記，TimeRanage信息，最早的Timestamp, Data BlockEncoding類型，BloomFilter配置，最大的Timestamp，KeyValue版本，最后一個RowKey，平均的Key長度，平均Value長度，Key比較器等。

7.寫入Bloom Filter元數據與索引數據。

注：前面每一部分信息的寫入，都以Block形式寫入，都包含Header與Data兩部分，Header中的結構也是相同的，只是都有不同的Block Type，在Data部分，每一種類型的Block可以有自己的定義。

8.寫入Trailer部分信息， Trailer中包含：

Root Index Block的Offset，FileInfo部分Offset，Data Block Index的層級，Data Block Index數據總大小，第一個Data Block的Offset，最后一個Data Block的Offset，Comparator信息，Root Index Block的Entries數量，加密算法類型，Meta Index Block的Entries數量，整個HFile文件未壓縮大小，整個HFile中所包含的KeyValue總個數，壓縮算法類型等。

至此，一個完整的HFile已生成。我們可以通過下圖再簡單回顧一下Root Index Block、Leaf Index Block、Data Block所處的位置以及索引關系：

 

簡單起見，上文中刻意忽略了Bloom Filter部分。Bloom Filter被用來快速判斷一條記錄是否在一個大的集合中存在，采用了多個Hash函數+位圖的設計。寫入數據時，一個記錄經X個Hash函數運算后，被映射到位圖中的X個位置，將位圖中的這X個位置寫為1。判斷一條記錄是否存在時，也是通過這個X個Hash函數計算后，獲得X個位置，如果位圖中的這X個位置都為1，則表明該記錄”可能存在”，但如果至少有一個為0，則該記錄”一定不存在”。

詳細信息，大家可以直接參考Wiki，這里不做過多展開。Bloom Filter包含Bloom元數據(Hash函數類型，Hash函數個數等)與位圖數據(BloomData)，為了避免每一次讀取時加載所有的Bloom Data，HFile V2中將BloomData部分分成了多個小的Bloom Block。BloomData數據也被當成一類Inline Block，與Data Block、Leaf Index Block交叉存在，而關于Bloom Filter的元數據與多個Bloom Block的索引信息，被存放在Load-On-Open Section部分。但需要注意的是，在FileInfo部分，保存了關于BloomFilter配置類型信息，共包含三種類型：不啟用，基于Row構建BloomFilter，基于Row+Column構建Bloom Filter。混合了BloomFilter Block以后的HFile構成如下圖所示：

 

附錄1 多大的HFile文件才存在Intermiate Index Block

每一個Leaf Index Block大小的計算方法如下(HFileBlockIndex$BlockIndexChunk#getNonRootSize)：

 

curTotalNonRootEntrySize是在每次寫入一個新的Entry的時候累加的：

 

這樣子，可以看出來，每一次新增一個Entry，則累計的值為：

12 + firstKey.length 

假設一個Leaf Index Block可以容納的Data Block的數量為x：

4 + 4 * (x + 1) + x * (12 + firstKey.length) 

進一步假設，firstKey.length為50bytes。而一個Leaf Index Block的默認最大大小為128KB：

 

4 + 4 * (x + 1) + x * (12 + 50) = 128 * 1024  
x ≈1986 

也就是說，在假設firstKey.length為50Bytes時，一個128KB的Leaf Index Block所能容納的Data Block數量約為1986個。

我們再來看看Root Index Chunk大小的計算方法：

 

基于firstKey為50 Bytes的假設，每往Root Index Chunk中新增一個Entry(關聯一個Leaf Index Block)，那么，curTotalRootSize的累加值為：

12 + 1 + 50 = 63 

因此，一個128KB的Root Index Chunk可以至少存儲2080個Entries，即可存儲2080個Leaf Index Block。

這樣， 一個Root Index Chunk所關聯的Data Blocks的總量應該為：

1986 * 2080 = 4,130,880 

而每一個Data Block默認大小為64KB，那么，這個HFile的總大小至少為：

4,130,880 * 64 * 1024 ≈ 252 GB 

即，基于每一個Block中的FirstKey為50bytes的假設，一個128KB的Root Index Block可容納的HFile文件總大小約為252GB。

如果實際的RowKey小于50 Bytes，或者將Data Block的Size調大，一個128KB的Root Index Chunk所關聯的HFile文件將會更大。因此，在大多數場景中，Intermediate Index Block并不會存在。

附錄2 關于HFile數據查看工具

HBase中提供了一個名為HFilePrettyPrinter的工具，可以以一種直觀的方式查看HFile中的數據，關于該工具的幫助信息，可通過如下命令查看：

 

hbase org.apache.hadoop.hbase.io.hfile.HFile  
References  
HBase Architecture 101 – Storage  
HBASE-3857: Change the HFile Format  
HBase Document: Appendix H: HFile format  
HADOOP-3315: New Binary file format 

SSTable and Log Structured Storage: LevelDB