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

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

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

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

HFile原理概述

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

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

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

Data Block Index究竟有多大?

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

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

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

較之HFile V1，我們來(lái)看看HFile V2的幾點(diǎn)顯著變化：

1.分層索引

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

Data Block的索引，在HFile V2中做多可支持三層索引：最底層的Data Block Index稱之為L(zhǎng)eaf Index Block，可直接索引到Data Block;中間層稱之為Intermediate Index Block，最上層稱之為Root Data Index，Root Data index存放在一個(gè)稱之為”Load-on-open Section“區(qū)域，Region Open時(shí)會(huì)被加載到內(nèi)存中。基本的索引邏輯為：由Root Data Index索引到Intermediate Block Index，再由Intermediate Block Index索引到Leaf Index Block，最后由Leaf Index Block查找到對(duì)應(yīng)的Data Block。在實(shí)際場(chǎng)景中，Intermediate Block Index基本上不會(huì)存在，文末部分會(huì)通過(guò)詳細(xì)的計(jì)算闡述它基本不存在的原因，因此，索引邏輯被簡(jiǎn)化為：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的對(duì)應(yīng)的Data Block。

Bloom Filter也被拆成了多個(gè)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.按需讀取

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

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

HFile生成流程

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

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

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

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

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

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

3.生成Checksum信息。

4.Data Block以及Checksum信息通過(guò)HFile Writer中的輸出流寫(xiě)入到HDFS中。

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

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

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

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

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

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

1.寫(xiě)入最后一個(gè)Data Block。

2.寫(xiě)入最后一個(gè)Leaf Index Block。

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

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

4.寫(xiě)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部分。

如果未超出大小，則直接輸出為L(zhǎng)oad-On-Open Section部分的Root Index Block。

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

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

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

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

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

8.寫(xiě)入Trailer部分信息， Trailer中包含：

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

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

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

詳細(xì)信息，大家可以直接參考Wiki，這里不做過(guò)多展開(kāi)。Bloom Filter包含Bloom元數(shù)據(jù)(Hash函數(shù)類型，Hash函數(shù)個(gè)數(shù)等)與位圖數(shù)據(jù)(BloomData)，為了避免每一次讀取時(shí)加載所有的Bloom Data，HFile V2中將BloomData部分分成了多個(gè)小的Bloom Block。BloomData數(shù)據(jù)也被當(dāng)成一類Inline Block，與Data Block、Leaf Index Block交叉存在，而關(guān)于Bloom Filter的元數(shù)據(jù)與多個(gè)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

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

curTotalNonRootEntrySize是在每次寫(xiě)入一個(gè)新的Entry的時(shí)候累加的：

這樣子，可以看出來(lái)，每一次新增一個(gè)Entry，則累計(jì)的值為：

12 + firstKey.length 

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

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

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

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

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

我們?cè)賮?lái)看看Root Index Chunk大小的計(jì)算方法：

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

12 + 1 + 50 = 63 

因此，一個(gè)128KB的Root Index Chunk可以至少存儲(chǔ)2080個(gè)Entries，即可存儲(chǔ)2080個(gè)Leaf Index Block。

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

1986 * 2080 = 4,130,880 

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

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

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

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

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

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

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