講LSM樹(shù)之前，需要提下三種基本的存儲(chǔ)引擎，這樣才能清楚LSM樹(shù)的由來(lái)：

• 哈希存儲(chǔ)引擎 ?是哈希表的持久化實(shí)現(xiàn)，支持增、刪、改以及隨機(jī)讀取操作，但不支持順序掃描，對(duì)應(yīng)的存儲(chǔ)系統(tǒng)為key-value存儲(chǔ)系統(tǒng)。對(duì)于key-value的插入以及查詢(xún)，哈希表的復(fù)雜度都是O(1)，明顯比樹(shù)的操作O(n)快,如果不需要有序的遍歷數(shù)據(jù)，哈希表就是your Mr.Right
• B樹(shù)存儲(chǔ)引擎是B樹(shù)（關(guān)于B樹(shù)的由來(lái)，數(shù)據(jù)結(jié)構(gòu)以及應(yīng)用場(chǎng)景可以看之前一篇博文）的持久化實(shí)現(xiàn)，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描（B+樹(shù)的葉子節(jié)點(diǎn)之間的指針），對(duì)應(yīng)的存儲(chǔ)系統(tǒng)就是關(guān)系數(shù)據(jù)庫(kù)（Mysql等）。
• LSM樹(shù)（Log-Structured Merge Tree）存儲(chǔ)引擎和B樹(shù)存儲(chǔ)引擎一樣，同樣支持增、刪、讀、改、順序掃描操作。而且通過(guò)批量存儲(chǔ)技術(shù)規(guī)避磁盤(pán)隨機(jī)寫(xiě)入問(wèn)題。當(dāng)然凡事有利有弊，LSM樹(shù)和B+樹(shù)相比，LSM樹(shù)犧牲了部分讀性能，用來(lái)大幅提高寫(xiě)性能。

通過(guò)以上的分析，應(yīng)該知道LSM樹(shù)的由來(lái)了，LSM樹(shù)的設(shè)計(jì)思想非常樸素：將對(duì)數(shù)據(jù)的修改增量保持在內(nèi)存中，達(dá)到指定的大小限制后將這些修改操作批量寫(xiě)入磁盤(pán)，不過(guò)讀取的時(shí)候稍微麻煩，需要合并磁盤(pán)中歷史數(shù)據(jù)和內(nèi)存中最近修改操作，所以寫(xiě)入性能大大提升，讀取時(shí)可能需要先看是否命中內(nèi)存，否則需要訪問(wèn)較多的磁盤(pán)文件。極端的說(shuō)，基于LSM樹(shù)實(shí)現(xiàn)的HBase的寫(xiě)性能比Mysql高了一個(gè)數(shù)量級(jí)，讀性能低了一個(gè)數(shù)量級(jí)。

LSM樹(shù)原理把一棵大樹(shù)拆分成N棵小樹(shù)，它首先寫(xiě)入內(nèi)存中，隨著小樹(shù)越來(lái)越大，內(nèi)存中的小樹(shù)會(huì)flush到磁盤(pán)中，磁盤(pán)中的樹(shù)定期可以做merge操作，合并成一棵大樹(shù)，以?xún)?yōu)化讀性能。

?

以上這些大概就是HBase存儲(chǔ)的設(shè)計(jì)主要思想，這里分別對(duì)應(yīng)說(shuō)明下：

• 因?yàn)樾?shù)先寫(xiě)到內(nèi)存中，為了防止內(nèi)存數(shù)據(jù)丟失，寫(xiě)內(nèi)存的同時(shí)需要暫時(shí)持久化到磁盤(pán)，對(duì)應(yīng)了HBase的MemStore和HLog
• MemStore上的樹(shù)達(dá)到一定大小之后，需要flush到HRegion磁盤(pán)中（一般是Hadoop DataNode），這樣MemStore就變成了DataNode上的磁盤(pán)文件StoreFile，定期HRegionServer對(duì)DataNode的數(shù)據(jù)做merge操作，徹底刪除無(wú)效空間，多棵小樹(shù)在這個(gè)時(shí)機(jī)合并成大樹(shù)，來(lái)增強(qiáng)讀性能。

?

關(guān)于LSM Tree，對(duì)于最簡(jiǎn)單的二層LSM Tree而言，內(nèi)存中的數(shù)據(jù)和磁盤(pán)你中的數(shù)據(jù)merge操作，如下圖

圖來(lái)自lsm論文

lsm tree，理論上，可以是內(nèi)存中樹(shù)的一部分和磁盤(pán)中第一層樹(shù)做merge，對(duì)于磁盤(pán)中的樹(shù)直接做update操作有可能會(huì)破壞物理block的連續(xù)性，但是實(shí)際應(yīng)用中，一般lsm有多層，當(dāng)磁盤(pán)中的小樹(shù)合并成一個(gè)大樹(shù)的時(shí)候，可以重新排好順序，使得block連續(xù)，優(yōu)化讀性能。

hbase在實(shí)現(xiàn)中，是把整個(gè)內(nèi)存在一定閾值后，flush到disk中，形成一個(gè)file，這個(gè)file的存儲(chǔ)也就是一個(gè)小的B+樹(shù)，因?yàn)閔base一般是部署在hdfs上，hdfs不支持對(duì)文件的update操作，所以hbase這么整體內(nèi)存flush，而不是和磁盤(pán)中的小樹(shù)merge update，這個(gè)設(shè)計(jì)也就能講通了。內(nèi)存flush到磁盤(pán)上的小樹(shù)，定期也會(huì)合并成一個(gè)大樹(shù)。整體上hbase就是用了lsm tree的思路。

總結(jié)

以上是生活随笔為你收集整理的HBase总结（七）LSM理解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。