Part 01 LSM樹模型
常見的的關(guān)系型數(shù)據(jù)庫(kù)，如MySQL、SQL Server、Oracle等，使用B+ Tree作為數(shù)據(jù)存儲(chǔ)與索引的基本結(jié)構(gòu)，非葉子節(jié)點(diǎn)只存放索引數(shù)據(jù)，葉子節(jié)點(diǎn)存放所有數(shù)據(jù)和指向相鄰節(jié)點(diǎn)的指針，具有高效的范圍查詢和穩(wěn)定的查找效率，以及具有較小的讀放大和空間放大。采用磁盤隨機(jī)讀寫方式，且以磁盤數(shù)據(jù)頁(yè)作為最小的讀寫單元，隨著數(shù)據(jù)大量插入，導(dǎo)致葉子節(jié)點(diǎn)不斷分裂，最終導(dǎo)致邏輯連續(xù)的數(shù)據(jù)存放到不同物理磁盤塊位置，產(chǎn)生大量的讀隨機(jī) I/O，從而導(dǎo)致范圍查詢效率下降和讀寫放大，磁盤隨機(jī)讀寫成為 B+Tree 的瓶頸，適用于讀多寫少的場(chǎng)景。
Log Structured Merge Tree (日志結(jié)構(gòu)合并樹) ，一種先于BigTable出現(xiàn)的文件組織方式，最早可以追溯到1996年 Patrick O'Neil等人的論文，因其獨(dú)特的數(shù)據(jù)組織方式(Log Structured)和需要在后臺(tái)通過不斷合并(Merge)的維護(hù)方式而得名，在BigTable出現(xiàn)之后，開始被重視被廣泛應(yīng)用于 HBase、Cassandra、ClickHouse、LevelDB、RocksDB 和 TiDB 等寫密集型 KV 數(shù)據(jù)庫(kù)和存儲(chǔ)引擎上。
LSM 樹實(shí)際上并非是一種具體的數(shù)據(jù)結(jié)構(gòu)，而是一種具備順序追加、多層數(shù)據(jù)結(jié)構(gòu)和定期合并等特性的數(shù)據(jù)處理邏輯。將離散的隨機(jī)寫轉(zhuǎn)化為批量的順序?qū)懀瑴p少了磁盤尋道時(shí)間提高了寫入性能，適用于寫密集型應(yīng)用，在Patrick O'Neil的論文中給出了多級(jí)的日志結(jié)構(gòu)合并樹的結(jié)構(gòu)。
圖片
C0 tree在內(nèi)存中，C1到Ck tree在磁盤上，Ck tree是一個(gè)有序的樹狀結(jié)構(gòu)，數(shù)據(jù)的寫入流轉(zhuǎn)從C0 tree 內(nèi)存開始，不斷被合并到磁盤上更大容量的Ck tree上。由于內(nèi)存的讀寫速率都比外存要快非常多，因此數(shù)據(jù)寫入的效率很高。并且數(shù)據(jù)從內(nèi)存刷入磁盤時(shí)是預(yù)排序的，也就是說，LSM樹將原本的隨機(jī)寫操作轉(zhuǎn)化成了順序?qū)懖僮鳎瑢懶阅艽蠓嵘５亲x取時(shí)需要將內(nèi)存中的數(shù)據(jù)和磁盤中的數(shù)據(jù)合并，犧牲了一部分讀性能。
Part 02 HBase系統(tǒng)架構(gòu)
HBase基LSM樹模型構(gòu)建一個(gè)分布式的列數(shù)據(jù)庫(kù)，HBase采用Master/Slave架構(gòu)搭建集群，隸屬于Hadoop生態(tài)系統(tǒng)，數(shù)據(jù)存儲(chǔ)于HDFS中，其整體的系統(tǒng)架構(gòu)如下圖所示：
圖片
一個(gè)RegionServer由一個(gè)(或多個(gè))HLog、一個(gè) BlockCache以及多個(gè)Region組成
· HLog用來保證數(shù)據(jù)寫入的可靠性;
· BlockCache可以將數(shù)據(jù)塊緩存在內(nèi)存中以提升數(shù)據(jù)讀取性能;
· Region是HBase中數(shù)據(jù)表的一個(gè)數(shù)據(jù)分片，一個(gè)RegionServer上通常會(huì)負(fù)責(zé)多個(gè)Region 的數(shù)據(jù)讀寫。
圖片
一張表會(huì)被水平切分成多個(gè)Region，每個(gè) Region負(fù)責(zé)自己區(qū)域的數(shù)據(jù)讀寫請(qǐng)求。一個(gè)Region由多個(gè)Store組成，每個(gè)Store存放對(duì)應(yīng)列簇的數(shù)據(jù)，比如一個(gè)表中有兩個(gè)列簇，這個(gè)表的所有Region就都會(huì)包含兩個(gè)Store。每個(gè)Store包含一個(gè)MemStore和多個(gè)HFile，用戶數(shù)據(jù)寫入時(shí)會(huì)將對(duì)應(yīng)列簇?cái)?shù)據(jù)寫入相應(yīng)的 MemStore，一旦寫入數(shù)據(jù)的內(nèi)存大小超過設(shè)定閾值，系統(tǒng)就會(huì)將MemStore中的數(shù)據(jù)落盤形成HFile文件。HFile存放在HDFS上，是一種定制化格式的數(shù)據(jù)存儲(chǔ)文件，方便用戶進(jìn)行數(shù)據(jù)讀取。
Part 03 MemStore實(shí)現(xiàn)
MemStore是LSM中C0 Tree的實(shí)現(xiàn)，由一個(gè)可寫的Segment，以及一個(gè)或多個(gè)不可寫的Segments構(gòu)成，所有的數(shù)據(jù)寫入操作，會(huì)按順序先寫入日志HLog，再寫入MemStore，當(dāng)MemStore中數(shù)據(jù)大小超過閾值之后，再將這些數(shù)據(jù)批量寫入磁盤，生成一個(gè)新的StoreFile(HFile)，最后多個(gè)StoreFile(HFile)又會(huì)進(jìn)行Compact。
· 通過MemStoreLAB(Local Allocation Buffer)，使用堆外一段固定的內(nèi)存段Chunk來存儲(chǔ)KeyValue數(shù)據(jù)，當(dāng)Region執(zhí)行flush之后釋放的就是一段Chunk所占有的連續(xù)內(nèi)存，而不是KeyValue占有的零散內(nèi)存，很好地解決了內(nèi)存碎片的問題。
· 使用CellSet存放所有的KeyValue的數(shù)據(jù)，CellSet核心是一個(gè)ConcurrentSkipListMap，數(shù)據(jù)按照Key值有序存放，而且在高并發(fā)寫入時(shí)，性能遠(yuǎn)高于ConcurrentHashMap，通過跳表實(shí)現(xiàn)高效插入、更高的并發(fā)性。
圖片
在HBaseV2.x后，使用帶合并寫內(nèi)存的CompactingMemStore，MemStore中的Active的Segment數(shù)據(jù)先Flush成一個(gè)Immutable的Segment，多個(gè)Immutable Segments可在內(nèi)存中進(jìn)行Compaction，當(dāng)達(dá)到一定閾值以后才將內(nèi)存中的數(shù)據(jù)持久化成HDFS中的HFile文件。
Part 04 HFile文件結(jié)構(gòu)
HBase使用列族式存儲(chǔ)，列族數(shù)據(jù)是存儲(chǔ)在一起的，列族式存儲(chǔ)介于行數(shù)存儲(chǔ)和列式存儲(chǔ)之間。
· 一張表，只設(shè)置一個(gè)列族，等同于行式存儲(chǔ);
· 一張表，設(shè)置大量列族，每個(gè)列族下僅有一列，等同于行數(shù)存儲(chǔ)。
在將文件結(jié)構(gòu)前，先看下數(shù)據(jù)存儲(chǔ)格式，當(dāng)put到hbase一個(gè)key和value的時(shí)候，會(huì)增加一條記錄：
(Table, RowKey, Family, Qualifier, Timestamp) -> Value
該記錄以字節(jié)流的方式存儲(chǔ)，對(duì)應(yīng)到磁盤中的存儲(chǔ)格式為：
圖片
從HBase開始到現(xiàn)在，HFile經(jīng)歷了三個(gè)版本，主要變更如下：
· HFile V1 ，HBase 0.92之前，結(jié)構(gòu)簡(jiǎn)單，參考了Bigtable的SSTable以及Hadoop的TFile，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ù)
· HFile V2 ，使用分層索引，按需讀取Data Block的索引數(shù)據(jù)和Bloom Filter數(shù)據(jù)，避免在Region Open階段或讀取階段一次讀入大量的數(shù)據(jù)，有效降低時(shí)延。等load-on-open加載到完，regions server可以認(rèn)為完成啟動(dòng)，加速啟動(dòng)時(shí)間
· HFile V3 ，從0.98版本開始引，主要是為了支持Tag特性，在HFile V2基礎(chǔ)上只做了微量改動(dòng)
在下文內(nèi)容中，主要圍繞HFile V2的設(shè)計(jì)展開。
圖片
無論是Data Block Index，還是Bloom Filter，都采用了分層索引的設(shè)計(jì)，最多可支持三層索引：
· 最上層為Root Data Index，放在一個(gè)稱之為L(zhǎng)oad-on-open Section區(qū)域，Region Open時(shí)會(huì)被加載到內(nèi)存中，從Root Data Index 索引到 Intermediate Block Index
· 中間層為Intermediate Index Block，從Intermediate Block Index 索引到 Leaf Index Block
· 最底層為L(zhǎng)eaf Index Block，可直接索引到Data Block
在實(shí)際場(chǎng)景中，Intermediate Block Index基本上不會(huì)存在，因此，索引邏輯被簡(jiǎn)化為：由Root Data Index直接索引到Leaf Index Block，再由Leaf Index Block查找到的對(duì)應(yīng)的Data Block。
Part 05 HFile Compaction合并
HBase Compaction分為兩種：Minor Compaction和Major Compaction，通常我們簡(jiǎn)稱為小合并、大合并，以短時(shí)間內(nèi)的IO消耗，以換取相對(duì)穩(wěn)定的讀取性能，下面是一個(gè)簡(jiǎn)單示意圖：
圖片
Minor Compaction，指選取一些小的、相鄰的HFile將他們合并成一個(gè)更大的HFile。通過少量的 IO 減少文件個(gè)數(shù)，提高讀取操作的性能，適合較高頻率的跑。缺點(diǎn)是只合并了局部的數(shù)據(jù)，對(duì)于那些全局刪除操作，無法在合并過程中完全刪除。默認(rèn)情況下，minor compaction會(huì)刪除選取HFile中的TTL過期數(shù)據(jù)。
Major Compaction，指將一個(gè)Store中所有的HFile合并成一個(gè)HFile，這個(gè)過程會(huì)清理三類沒有意義的數(shù)據(jù)：被刪除的數(shù)據(jù)(打了Delete標(biāo)記的數(shù)據(jù))、TTL過期數(shù)據(jù)、版本號(hào)超過設(shè)定版本號(hào)的數(shù)據(jù)。另外，一般情況下，Major Compaction時(shí)間會(huì)持續(xù)比較長(zhǎng)，整個(gè)過程會(huì)消耗大量系統(tǒng)資源，對(duì)上層業(yè)務(wù)有比較大的影響。因此，生產(chǎn)環(huán)境下通常關(guān)閉自動(dòng)觸發(fā)Major Compaction功能，改為手動(dòng)在業(yè)務(wù)低峰期觸發(fā)。
Part 06 總結(jié)
HBase基于LSM Tree模型，通過MemStore和StoreFile實(shí)現(xiàn)內(nèi)存和磁盤中的日志合并，使用順序追加、定期合并方式，提高數(shù)據(jù)的寫入性能，支持海量數(shù)據(jù)的存儲(chǔ)。通過Compaction合并，以短時(shí)間內(nèi)的IO消耗，獲取相對(duì)穩(wěn)定的讀取性能。在實(shí)際業(yè)務(wù)中，需要配置合適的合并策略，在讀放大、寫放大和空間放大中，做好權(quán)衡和取舍。
