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

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

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

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

HFile原理概述

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

 

HFile在生成之前，數(shù)據(jù)在內(nèi)存中已經(jīng)是按序組織的。存放用戶數(shù)據(jù)的KeyValue，被存儲在一個個默認(rèn)為64kb大小的Data Block中，在Data Index部分存儲了每一個Data Block的索引信息{Offset，Size，F(xiàn)irstKey}，而Data Index的索引信息{Data Index Offset, Data Block Count}被存儲在HFile的Trailer部分。除此以外，在Meta Block部分還存儲了Bloom Filter的數(shù)據(jù)。下圖更直觀的表達出了HFile V1中的數(shù)據(jù)組織結(jié)構(gòu)：

 

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

Data Block Index究竟有多大?

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

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

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

 

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

1.分層索引

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

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“區(qū)域，Region Open時會被加載到內(nèi)存中?；镜乃饕壿嫗椋河蒖oot Data Index索引到Intermediate Block Index，再由Intermediate Block Index索引到Leaf Index Block，最后由Leaf Index Block查找到對應(yīng)的Data Block。在實際場景中，Intermediate Block Index基本上不會存在，文末部分會通過詳細的計算闡述它基本不存在的原因，因此，索引邏輯被簡化為：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的對應(yīng)的Data Block。

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

2.交叉存放

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

3.按需讀取

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

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

HFile生成流程

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

起初，HFile中并沒有任何Block，數(shù)據(jù)還存在于MemStore中。

Flush發(fā)生時，創(chuàng)建HFile Writer，第一個空的Data Block出現(xiàn)，初始化后的Data Block中為Header部分預(yù)留了空間，Header部分用來存放一個Data Block的元數(shù)據(jù)信息。

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

 

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

 

2.在預(yù)留的Header區(qū)，寫入該Data Block的元數(shù)據(jù)信息，包含{壓縮前的大小，壓縮后的大小，上一個Block的偏移信息，Checksum元數(shù)據(jù)信息}等信息，下圖是一個Header的完整結(jié)構(gòu)：

 

3.生成Checksum信息。

 

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

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

 

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

 

此時，已輸出的Scanned Block Section部分的構(gòu)成如下：

 

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

 

從Root Index到Leaf Data Block再到Data Block的索引關(guān)系如下：

 

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

1.寫入最后一個Data Block。

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

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

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

4.寫Root Block Index Chunk部分?jǐn)?shù)據(jù)：

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

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

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

6.寫入FileInfo信息，F(xiàn)ileInfo中包含：

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

7.寫入Bloom Filter元數(shù)據(jù)與索引數(shù)據(jù)。

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

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

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

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

 

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

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

 

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

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

 

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

 

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

12 + firstKey.length 

假設(shè)一個Leaf Index Block可以容納的Data Block的數(shù)量為x：

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

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

 

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

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

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

 

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

12 + 1 + 50 = 63 

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

這樣， 一個Root Index Chunk所關(guān)聯(lián)的Data Blocks的總量應(yīng)該為：

1986 * 2080 = 4,130,880 

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

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

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

如果實際的RowKey小于50 Bytes，或者將Data Block的Size調(diào)大，一個128KB的Root Index Chunk所關(guān)聯(lián)的HFile文件將會更大。因此，在大多數(shù)場景中，Intermediate Index Block并不會存在。

附錄2 關(guān)于HFile數(shù)據(jù)查看工具

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

 

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