五分鐘技術(shù)趣談 | 淺談HBase數(shù)據(jù)結(jié)構(gòu)和系統(tǒng)架構(gòu)

作者：張程、張俊杰，單位：中國移動智慧家庭運(yùn)營中心智慧互聯(lián)產(chǎn)品部

Apache HBase是以谷歌的BigTable為模型，一種分布式的、面向列的開源數(shù)據(jù)庫，用于收集數(shù)據(jù)并為各種谷歌服務(wù)（如地圖、金融、地球等）提供請求，最初是Powerset for Natural Language Search公司的一個項(xiàng)目，用于處理大量稀疏的數(shù)據(jù)集，于2007年2月首次發(fā)布，2008年1月成為Apache Hadoop的一個子項(xiàng)目，2010年，HBase成為Apache的頂級項(xiàng)目。

Part 01●?LSM樹模型?●

常見的的關(guān)系型數(shù)據(jù)庫，如MySQL、SQL Server、Oracle等，使用B+ Tree作為數(shù)據(jù)存儲與索引的基本結(jié)構(gòu)，非葉子節(jié)點(diǎn)只存放索引數(shù)據(jù)，葉子節(jié)點(diǎn)存放所有數(shù)據(jù)和指向相鄰節(jié)點(diǎn)的指針，具有高效的范圍查詢和穩(wěn)定的查找效率，以及具有較小的讀放大和空間放大。采用磁盤隨機(jī)讀寫方式，且以磁盤數(shù)據(jù)頁作為最小的讀寫單元，隨著數(shù)據(jù)大量插入，導(dǎo)致葉子節(jié)點(diǎn)不斷分裂，最終導(dǎo)致邏輯連續(xù)的數(shù)據(jù)存放到不同物理磁盤塊位置，產(chǎn)生大量的讀隨機(jī) I/O，從而導(dǎo)致范圍查詢效率下降和讀寫放大，磁盤隨機(jī)讀寫成為 B+Tree 的瓶頸，適用于讀多寫少的場景。

Log Structured Merge Tree (日志結(jié)構(gòu)合并樹) ，一種先于BigTable出現(xiàn)的文件組織方式，最早可以追溯到1996年 Patrick O'Neil等人的論文，因其獨(dú)特的數(shù)據(jù)組織方式（Log Structured）和需要在后臺通過不斷合并（Merge）的維護(hù)方式而得名，在BigTable出現(xiàn)之后，開始被重視被廣泛應(yīng)用于 HBase、Cassandra、ClickHouse、LevelDB、RocksDB 和 TiDB 等寫密集型 KV 數(shù)據(jù)庫和存儲引擎上。

LSM 樹實(shí)際上并非是一種具體的數(shù)據(jù)結(jié)構(gòu)，而是一種具備順序追加、多層數(shù)據(jù)結(jié)構(gòu)和定期合并等特性的數(shù)據(jù)處理邏輯。將離散的隨機(jī)寫轉(zhuǎn)化為批量的順序?qū)懀瑴p少了磁盤尋道時間提高了寫入性能，適用于寫密集型應(yīng)用，在Patrick O'Neil的論文中給出了多級的日志結(jié)構(gòu)合并樹的結(jié)構(gòu)。

C0 tree在內(nèi)存中，C1到Ck tree在磁盤上，Ck tree是一個有序的樹狀結(jié)構(gòu)，數(shù)據(jù)的寫入流轉(zhuǎn)從C0 tree 內(nèi)存開始，不斷被合并到磁盤上更大容量的Ck tree上。由于內(nèi)存的讀寫速率都比外存要快非常多，因此數(shù)據(jù)寫入的效率很高。并且數(shù)據(jù)從內(nèi)存刷入磁盤時是預(yù)排序的，也就是說，LSM樹將原本的隨機(jī)寫操作轉(zhuǎn)化成了順序?qū)懖僮?，寫性能大幅提升。但是讀取時需要將內(nèi)存中的數(shù)據(jù)和磁盤中的數(shù)據(jù)合并，犧牲了一部分讀性能。

Part 02●?HBase系統(tǒng)架構(gòu)?●

HBase基LSM樹模型構(gòu)建一個分布式的列數(shù)據(jù)庫，HBase采用Master/Slave架構(gòu)搭建集群，隸屬于Hadoop生態(tài)系統(tǒng)，數(shù)據(jù)存儲于HDFS中，其整體的系統(tǒng)架構(gòu)如下圖所示：

一個RegionServer由一個(或多個)HLog、一個 BlockCache以及多個Region組成

· HLog用來保證數(shù)據(jù)寫入的可靠性；

· BlockCache可以將數(shù)據(jù)塊緩存在內(nèi)存中以提升數(shù)據(jù)讀取性能；

· Region是HBase中數(shù)據(jù)表的一個數(shù)據(jù)分片，一個RegionServer上通常會負(fù)責(zé)多個Region 的數(shù)據(jù)讀寫。

一張表會被水平切分成多個Region，每個 Region負(fù)責(zé)自己區(qū)域的數(shù)據(jù)讀寫請求。一個Region由多個Store組成，每個Store存放對應(yīng)列簇的數(shù)據(jù)，比如一個表中有兩個列簇，這個表的所有Region就都會包含兩個Store。每個Store包含一個MemStore和多個HFile，用戶數(shù)據(jù)寫入時會將對應(yīng)列簇數(shù)據(jù)寫入相應(yīng)的 MemStore，一旦寫入數(shù)據(jù)的內(nèi)存大小超過設(shè)定閾值，系統(tǒng)就會將MemStore中的數(shù)據(jù)落盤形成HFile文件。HFile存放在HDFS上，是一種定制化格式的數(shù)據(jù)存儲文件，方便用戶進(jìn)行數(shù)據(jù)讀取。

Part 03●?MemStore實(shí)現(xiàn)?●

MemStore是LSM中C0?Tree的實(shí)現(xiàn)，由一個可寫的Segment，以及一個或多個不可寫的Segments構(gòu)成，所有的數(shù)據(jù)寫入操作，會按順序先寫入日志HLog，再寫入MemStore，當(dāng)MemStore中數(shù)據(jù)大小超過閾值之后，再將這些數(shù)據(jù)批量寫入磁盤，生成一個新的StoreFile（HFile），最后多個StoreFile（HFile）又會進(jìn)行Compact。

·?通過MemStoreLAB（Local Allocation Buffer），使用堆外一段固定的內(nèi)存段Chunk來存儲KeyValue數(shù)據(jù)，當(dāng)Region執(zhí)行flush之后釋放的就是一段Chunk所占有的連續(xù)內(nèi)存，而不是KeyValue占有的零散內(nèi)存，很好地解決了內(nèi)存碎片的問題。

·?使用CellSet存放所有的KeyValue的數(shù)據(jù)，CellSet核心是一個ConcurrentSkipListMap，數(shù)據(jù)按照Key值有序存放，而且在高并發(fā)寫入時，性能遠(yuǎn)高于ConcurrentHashMap，通過跳表實(shí)現(xiàn)高效插入、更高的并發(fā)性。

在HBaseV2.x后，使用帶合并寫內(nèi)存的CompactingMemStore，MemStore中的Active的Segment數(shù)據(jù)先Flush成一個Immutable的Segment，多個Immutable Segments可在內(nèi)存中進(jìn)行Compaction，當(dāng)達(dá)到一定閾值以后才將內(nèi)存中的數(shù)據(jù)持久化成HDFS中的HFile文件。

Part 04●?HFile文件結(jié)構(gòu)?●

HBase使用列族式存儲，列族數(shù)據(jù)是存儲在一起的，列族式存儲介于行數(shù)存儲和列式存儲之間。

·?一張表，只設(shè)置一個列族，等同于行式存儲；

·?一張表，設(shè)置大量列族，每個列族下僅有一列，等同于行數(shù)存儲。

在將文件結(jié)構(gòu)前，先看下數(shù)據(jù)存儲格式，當(dāng)put到hbase一個key和value的時候，會增加一條記錄：

(Table, RowKey, Family, Qualifier, Timestamp) -> Value

該記錄以字節(jié)流的方式存儲，對應(yīng)到磁盤中的存儲格式為：

從HBase開始到現(xiàn)在，HFile經(jīng)歷了三個版本，主要變更如下：

·?HFile V1 ，HBase 0.92之前，結(jié)構(gòu)簡單，參考了Bigtable的SSTable以及Hadoop的TFile，Region Open的時候，需要加載所有的Data Block Index數(shù)據(jù)，另外，第一次讀取時需要加載所有的Bloom Filter數(shù)據(jù)到內(nèi)存中。一個HFile中的Bloom Filter的數(shù)據(jù)大小可達(dá)百M(fèi)B級別，一個RegionServer啟動時可能需要加載數(shù)GB的Data Block Index數(shù)據(jù)

·?HFile V2 ，使用分層索引，按需讀取Data Block的索引數(shù)據(jù)和Bloom Filter數(shù)據(jù)，避免在Region Open階段或讀取階段一次讀入大量的數(shù)據(jù)，有效降低時延。等load-on-open加載到完，regions server可以認(rèn)為完成啟動，加速啟動時間

·?HFile V3 ，從0.98版本開始引，主要是為了支持Tag特性，在HFile V2基礎(chǔ)上只做了微量改動

在下文內(nèi)容中，主要圍繞HFile V2的設(shè)計展開。

無論是Data Block Index，還是Bloom Filter，都采用了分層索引的設(shè)計，最多可支持三層索引：

·?最上層為Root Data Index，放在一個稱之為Load-on-open Section區(qū)域，Region Open時會被加載到內(nèi)存中，從Root Data Index 索引到 Intermediate Block Index

·?中間層為Intermediate Index Block，從Intermediate Block Index 索引到 Leaf Index Block

·?最底層為Leaf Index Block，可直接索引到Data Block

在實(shí)際場景中，Intermediate Block Index基本上不會存在，因此，索引邏輯被簡化為：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的對應(yīng)的Data Block。

Part 05●?HFile Compaction合并?●

HBase Compaction分為兩種：Minor Compaction和Major Compaction，通常我們簡稱為小合并、大合并，以短時間內(nèi)的IO消耗，以換取相對穩(wěn)定的讀取性能，下面是一個簡單示意圖：

Minor Compaction，指選取一些小的、相鄰的HFile將他們合并成一個更大的HFile。通過少量的 IO 減少文件個數(shù)，提高讀取操作的性能，適合較高頻率的跑。缺點(diǎn)是只合并了局部的數(shù)據(jù)，對于那些全局刪除操作，無法在合并過程中完全刪除。默認(rèn)情況下，minor compaction會刪除選取HFile中的TTL過期數(shù)據(jù)。

Major Compaction，指將一個Store中所有的HFile合并成一個HFile，這個過程會清理三類沒有意義的數(shù)據(jù)：被刪除的數(shù)據(jù)（打了Delete標(biāo)記的數(shù)據(jù)）、TTL過期數(shù)據(jù)、版本號超過設(shè)定版本號的數(shù)據(jù)。另外，一般情況下，Major Compaction時間會持續(xù)比較長，整個過程會消耗大量系統(tǒng)資源，對上層業(yè)務(wù)有比較大的影響。因此，生產(chǎn)環(huán)境下通常關(guān)閉自動觸發(fā)Major Compaction功能，改為手動在業(yè)務(wù)低峰期觸發(fā)。

Part 06●?總結(jié)?●

HBase基于LSM Tree模型，通過MemStore和StoreFile實(shí)現(xiàn)內(nèi)存和磁盤中的日志合并，使用順序追加、定期合并方式，提高數(shù)據(jù)的寫入性能，支持海量數(shù)據(jù)的存儲。通過Compaction合并，以短時間內(nèi)的IO消耗，獲取相對穩(wěn)定的讀取性能。在實(shí)際業(yè)務(wù)中，需要配置合適的合并策略，在讀放大、寫放大和空間放大中，做好權(quán)衡和取舍。