一、LSM樹的原理
講LSM樹之前，需要提下三種基本的存儲(chǔ)引擎，這樣才能清楚LSM樹的由來：
-
哈希存儲(chǔ)引擎
是哈希表的持久化實(shí)現(xiàn)，支持增、刪、改以及隨機(jī)讀取操作，但不支持順序掃描，對應(yīng)的存儲(chǔ)系統(tǒng)為key-value存儲(chǔ)系統(tǒng)，如Redis。對于key-value的插入以及查詢，哈希表的復(fù)雜度都是O(1)，明顯比樹的操作O(n)快,如果不需要有序的遍歷數(shù)據(jù)，哈希表效率是很高的。 -
B樹存儲(chǔ)引擎
是B樹的持久化實(shí)現(xiàn)，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描（B+樹的葉子節(jié)點(diǎn)之間的指針），對應(yīng)的存儲(chǔ)系統(tǒng)就是關(guān)系數(shù)據(jù)庫（Mysql等）。 -
LSM樹（Log-Structured Merge Tree）存儲(chǔ)引擎
和B樹存儲(chǔ)引擎一樣，同樣支持增、刪、讀、改、順序掃描操作。而且通過批量存儲(chǔ)技術(shù)規(guī)避磁盤隨機(jī)寫入問題。當(dāng)然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
通過以上的分析，應(yīng)該知道LSM樹的由來了，LSM樹的設(shè)計(jì)思想非常樸素：將對數(shù)據(jù)的修改增量保持在內(nèi)存中，達(dá)到指定的大小限制后將這些修改操作批量寫入磁盤，不過讀取的時(shí)候稍微麻煩，需要合并磁盤中歷史數(shù)據(jù)和內(nèi)存中最近修改操作，所以寫入性能大大提升，讀取時(shí)可能需要先看是否命中內(nèi)存，否則需要訪問較多的磁盤文件。極端的說，基于LSM樹實(shí)現(xiàn)的HBase的寫性能比Mysql高了一個(gè)數(shù)量級，讀性能低了一個(gè)數(shù)量級。
LSM樹原理把一棵大樹拆分成N棵小樹，它首先寫入內(nèi)存中，隨著小樹越來越大，內(nèi)存中的小樹會(huì)flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優(yōu)化讀性能。
以上這些大概就是HBase存儲(chǔ)的設(shè)計(jì)主要思想，這里分別對應(yīng)說明下：
- 因?yàn)樾湎葘懙絻?nèi)存中，為了防止內(nèi)存數(shù)據(jù)丟失，寫內(nèi)存的同時(shí)需要暫時(shí)持久化到磁盤，對應(yīng)了HBase的MemStore和HLog
- MemStore上的樹達(dá)到一定大小之后，需要flush到HRegion磁盤中（一般是Hadoop DataNode），這樣MemStore就變成了DataNode上的磁盤文件StoreFile，定期HRegionServer對DataNode的數(shù)據(jù)做merge操作，徹底刪除無效空間，多棵小樹在這個(gè)時(shí)機(jī)合并成大樹，來增強(qiáng)讀性能。
二、HBase 的 LSM 實(shí)現(xiàn)
１、WAL 預(yù)寫日志支持
類似與 binlog 的作用，在寫入 MemTable 之前，往 WAL 寫入日志，避免宕機(jī)出現(xiàn)的數(shù)據(jù)丟失的情況發(fā)生。因此 HBase 算是一個(gè)不錯(cuò)的可靠性存儲(chǔ)。
這里有個(gè)很有趣的地方，某些測試環(huán)境下，機(jī)械硬盤的順序?qū)懶阅軙?huì)高于對內(nèi)存的隨機(jī)寫。因此 WAL 的寫入性能是非?？捎^的，我們不必對此過于介懷。
２、Minor vs Major Compaction
(1) Minor Compaction： 根據(jù)配置策略，自動(dòng)檢查小文件，合并到大文件，從而減少碎片文件，然而并不會(huì)立馬刪除掉舊 HFile 文件；
(2) Major Compaction： 每個(gè) CF 中，不管有多少個(gè) HFiles 文件，最終都是將 HFiles 合并到一個(gè)大的 HFile 中，并且把所有的舊 HFile 文件刪除，即CF 與 HFile 最終變成一一對應(yīng)的關(guān)系。
3、BlockCache
除了 MemStore（也就是 MemTable） 以外，HBase 還提供了另一種緩存結(jié)構(gòu)，BlockCache。
BlockCache 本質(zhì)上是將熱數(shù)據(jù)放到內(nèi)存里維護(hù)起來，避免 Disk I/O，當(dāng)然即使 BlockCache 找不到數(shù)據(jù)還是可以去 MemStore 中找的，只有兩邊都不存在數(shù)據(jù)的時(shí)候，才會(huì)讀內(nèi)存里的 HFile 索引尋址到硬盤，進(jìn)行一次 I/O 操作。
4、HFile 的數(shù)據(jù)結(jié)構(gòu)
參考：http://hbasefly.com/2016/03/25/hbase-hfile/
5、Bloom Filter
HFile 文件中包含了一個(gè) Bloom Block，這個(gè)是用來做布隆過濾的。Bloom Block 的數(shù)據(jù)是在啟動(dòng)的時(shí)候就已經(jīng)加載到內(nèi)存里，除了 Block Cache 和 MemStore 以外，這個(gè)也對 HBase 隨機(jī)讀性能的優(yōu)化起著至關(guān)重要的作用。
生成 HFile 的時(shí)候，會(huì)將 key 經(jīng)過三次 hash 最終落到 Bloom Block 位數(shù)組的某三位上，并將其由0更改成1，以此標(biāo)記該 key 的確存在這個(gè) HFile 文件之中，查詢的時(shí)候不需要將文件打開并檢索，避免了一次 I/O 操作。然而隨著 HFile 的膨脹，Bloom Block會(huì)越來越大。
