Part 01 LSM樹模型
常見的的關(guān)系型數(shù)據(jù)庫，如MySQL、SQL Server、Oracle等，使用B+ Tree作為數(shù)據(jù)存儲與索引的基本結(jié)構(gòu)，非葉子節(jié)點只存放索引數(shù)據(jù)，葉子節(jié)點存放所有數(shù)據(jù)和指向相鄰節(jié)點的指針，具有高效的范圍查詢和穩(wěn)定的查找效率，以及具有較小的讀放大和空間放大。采用磁盤隨機讀寫方式，且以磁盤數(shù)據(jù)頁作為最小的讀寫單元，隨著數(shù)據(jù)大量插入，導(dǎo)致葉子節(jié)點不斷分裂，最終導(dǎo)致邏輯連續(xù)的數(shù)據(jù)存放到不同物理磁盤塊位置，產(chǎn)生大量的讀隨機 I/O，從而導(dǎo)致范圍查詢效率下降和讀寫放大，磁盤隨機讀寫成為 B+Tree 的瓶頸，適用于讀多寫少的場景。
Log Structured Merge Tree (日志結(jié)構(gòu)合并樹) ，一種先于BigTable出現(xiàn)的文件組織方式，最早可以追溯到1996年 Patrick O'Neil等人的論文，因其獨特的數(shù)據(jù)組織方式(Log Structured)和需要在后臺通過不斷合并(Merge)的維護方式而得名，在BigTable出現(xiàn)之后，開始被重視被廣泛應(yīng)用于 HBase、Cassandra、ClickHouse、LevelDB、RocksDB 和 TiDB 等寫密集型 KV 數(shù)據(jù)庫和存儲引擎上。
LSM 樹實際上并非是一種具體的數(shù)據(jù)結(jié)構(gòu)，而是一種具備順序追加、多層數(shù)據(jù)結(jié)構(gòu)和定期合并等特性的數(shù)據(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樹將原本的隨機寫操作轉(zhuǎn)化成了順序?qū)懖僮鳎瑢懶阅艽蠓嵘５亲x取時需要將內(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實現(xiàn)
MemStore是LSM中C0 Tree的實現(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，通過跳表實現(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á)百MB級別，一個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
在實際場景中，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ù)，提高讀取操作的性能，適合較高頻率的跑。缺點是只合并了局部的數(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實現(xiàn)內(nèi)存和磁盤中的日志合并，使用順序追加、定期合并方式，提高數(shù)據(jù)的寫入性能，支持海量數(shù)據(jù)的存儲。通過Compaction合并，以短時間內(nèi)的IO消耗，獲取相對穩(wěn)定的讀取性能。在實際業(yè)務(wù)中，需要配置合適的合并策略，在讀放大、寫放大和空間放大中，做好權(quán)衡和取舍。
