Hbase中LSM Tree怎么用

寫流程

1. 向zookeeper發(fā)起請求，從ROOT表中獲得META所在的region，再根據(jù)table，namespace，rowkey，去meta表中找到目標(biāo)數(shù)據(jù)對應(yīng)的region信息以及regionserver

2. 把數(shù)據(jù)分別寫到HLog和MemStore上一份，若MemStore中的數(shù)據(jù)有丟失，則可在HLog上恢復(fù)

3. 當(dāng)memstore數(shù)據(jù)達(dá)到閾值（默認(rèn)是64M），將數(shù)據(jù)刷到硬盤，將內(nèi)存中的數(shù)據(jù)刪除同時(shí)刪除Hlog中的歷史數(shù)據(jù)。

4. 當(dāng)多個(gè)StoreFile文件達(dá)到一定的大小后，會(huì)觸發(fā)Compact合并操作，合并為一個(gè)StoreFile，這里同時(shí)進(jìn)行版本的合并和數(shù)據(jù)刪除。

5. 當(dāng)Compact后，逐步形成越來越大的StoreFIle后，會(huì)觸發(fā)Split操作，把當(dāng)前的StoreFile分成兩個(gè)，這里相當(dāng)于把一個(gè)大的region分割成兩個(gè)region

6. 當(dāng)hregionser宕機(jī)后，將hregionserver上的hlog拆分，然后分配給不同的hregionserver加載，修改.META.

讀流程

1. 首先用MemStoreScanner搜索MemStore里是否有所查的rowKey（這一步在內(nèi)存中，很快），

2. 同時(shí)也會(huì)用Bloom Block通過一定算法過濾掉大部分一定不包含所查rowKey的HFile，

3. 上面提到在RegionServer啟動(dòng)的時(shí)候就會(huì)把Trailer，和Load-on-open-section里的block先后加載到內(nèi)存，所以接下來會(huì)查Trailer，因?yàn)樗涗浟嗣總€(gè)HFile的偏移量，可以快速排除掉剩下的部分HFile。

4. 經(jīng)過上面兩步，剩下的就是很少一部分的HFile了，就需要根據(jù)Index Block索引數(shù)據(jù)（這部分的Block已經(jīng)在內(nèi)存）快速查找rowkey所在的block的位置；

5. 找到block的位置后，檢查這個(gè)block是否在blockCache中，在則直接去取，如果不在的話把這個(gè)block加載到blockCache進(jìn)行緩存，

6. 最后掃描這些讀到內(nèi)存中的Block（可能有多個(gè)，因?yàn)橛卸喟姹荆业綄?yīng)rowKey返回需要的版本。

熟悉了HBase的讀寫流程后（尤其是寫流程），了解lsm tree就會(huì)變得容易很多了。Log-Structured Merge-Tree中文翻譯是日志結(jié)構(gòu)合并樹。那我們就從日志結(jié)構(gòu)與合并樹這兩個(gè)方面來講。

日志結(jié)構(gòu)

我們知道磁盤隨機(jī)讀寫性能是比順序讀寫慢至少3個(gè)數(shù)量級的，日志的特點(diǎn)是它是順序追加寫的，可以保證非常好的寫操作性能，但是從日志文件中讀一些數(shù)據(jù)將會(huì)比寫操作需要更多的時(shí)間，需要倒序掃描，直接找到所需的內(nèi)容。
因此日志適用的場景非常有限：

1. 數(shù)據(jù)是被整體訪問，像大部分?jǐn)?shù)據(jù)庫的WAL(write-ahead log)、HDFS

2. 記錄了文件明確的偏移量，比如Kafka

為了為更復(fù)雜的讀場景（比如按key或者range）提供高效的性能，人們發(fā)明了幾種方式：

二分查找: 將文件數(shù)據(jù)有序保存，使用二分查找來完成特定key的查找。

哈希：用哈希將數(shù)據(jù)分割為不同的bucket

B+樹：使用B+樹 或者 ISAM 等方法，可以減少外部文件的讀取

外部文件： 將數(shù)據(jù)保存為日志，并創(chuàng)建一個(gè)hash或者查找樹映射相應(yīng)的文件。

所有的方法都可以有效的提高了讀操作的性能（最少提供了O(log(n)) )，但是，卻丟失了日志文件超好的寫性能。上面這些方法，都強(qiáng)加了總體的結(jié)構(gòu)信息在數(shù)據(jù)上，數(shù)據(jù)被按照特定的方式放置，所以可以很快的找到特定的數(shù)據(jù)，但是卻對寫操作不友善，讓寫操作性能下降。更糟糕的是，當(dāng)我們需要更新hash或者B+樹的結(jié)構(gòu)時(shí)，需要同時(shí)更新文件系統(tǒng)中特定的部分，這就是上面說的比較慢的隨機(jī)讀寫操作。這種隨機(jī)的操作要盡量減少。

此時(shí)，LSM 被發(fā)明了， LSM 使用一種不同于上述四種的方法，保持了日志文件寫性能，以及微小的讀操作性能損失。本質(zhì)上就是通過把隨機(jī)寫的數(shù)據(jù)寫到內(nèi)存，然后定期flush到磁盤，對于磁盤來說，讓所有的操作順序化，而不是隨機(jī)讀寫。

合并樹

LSM樹原理把一棵大樹拆分成N棵小樹，它首先寫入內(nèi)存中即是小樹，隨著小樹越來越大，會(huì)flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優(yōu)化讀性能。
lsm tree，理論上，可以是內(nèi)存中樹的一部分和磁盤中第一層樹做merge，對于磁盤中的樹直接做update操作有可能會(huì)破壞物理block的連續(xù)性，但是實(shí)際應(yīng)用中，一般lsm有多層，當(dāng)磁盤中的小樹合并成一個(gè)大樹的時(shí)候，可以重新排好順序，使得block連續(xù)，優(yōu)化讀性能。
hbase在實(shí)現(xiàn)中，是把整個(gè)內(nèi)存在一定閾值后，flush到disk中，形成一個(gè)file，這個(gè)file的存儲(chǔ)也就是一個(gè)小的B+樹，因?yàn)閔base一般是部署在hdfs上，hdfs不支持對文件的update操作，所以hbase這么整體內(nèi)存flush，而不是和磁盤中的小樹merge update，這個(gè)設(shè)計(jì)也就能講通了。內(nèi)存flush到磁盤上的小樹，定期也會(huì)合并成一個(gè)大樹。整體上hbase就是用了lsm tree的思路。