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