lsm簡析

lsm 更像是一種設計索引的思想。它把數(shù)據(jù)分為兩個部分，一部分放在內(nèi)存里，一部分是存放在磁盤上,內(nèi)存里面的數(shù)據(jù)檢索方式可以利用紅黑樹，跳表這種時間復雜度低的數(shù)據(jù)結(jié)構(gòu)進行檢索。

而當內(nèi)存數(shù)據(jù)到達一定閥值的時候則會將數(shù)據(jù)同步到一個新的磁盤文件上。此時寫入磁盤的方式是順序?qū)?，這也是為什么lsm寫入性能高的原因。

提問開始

打住，你說寫入性能高，但是我們知道內(nèi)存中的數(shù)據(jù)如果在處于正在同步到磁盤的過程中，如果此時有新數(shù)據(jù)的插入，則會帶來并發(fā)讀寫問題，要想解決就要給這片內(nèi)存區(qū)域加鎖了。加鎖會導致寫入過程阻塞，這樣性能會高嗎？

業(yè)界一般是這樣解決的，當內(nèi)存到達某個閥值后，就將這片內(nèi)存標記為可讀，然后新的數(shù)據(jù)插入將會寫到新的內(nèi)存區(qū)域，而舊的內(nèi)存因為是只讀的原因，便可以不加鎖的進行同步到磁盤的過程。

再來思考，由于每次同步是生成一個新的磁盤文件，那么lsm是如何再多個磁盤文件范圍里進行數(shù)據(jù)檢索的呢？ 由于內(nèi)存容量有限，每次生成的磁盤文件必然不會過大，這樣會不會產(chǎn)生大量的小容量的磁盤文件？

我來回答下, 查找數(shù)據(jù)的時候是從多個磁盤文件中讀取數(shù)據(jù)，然后對結(jié)果進行合并，只取最新的數(shù)據(jù)。

這里已經(jīng)可以看到和b+tree比較明顯的區(qū)別了，b+tree是插入的時候進行原地合并，而lsm則是讀取時進行數(shù)據(jù)合并。

由于數(shù)據(jù)在內(nèi)存中是有序的，所以在寫入磁盤時，也保證了每個小的磁盤文件是有序的。我們將這些小的磁盤文件稱作sstable。

但是這樣的設計還有沒有問題，如果僅僅保證sstable文件有序，不同sstable文件索引的范圍有重疊的話，我們查找一個值的時候就可能會在多個sstable文件里尋找，最差的情況可能要找所有的sstable文件，如圖：

有個索引范圍是1-1000的sstable，和值范圍為500-2000的sstable，當我們查找600時，無法一開始就知曉600在哪個sstable里。

因此，業(yè)界一般是這樣做，對多個小文件進行合并，讓磁盤文件之間不再有覆蓋關(guān)系。

將索引范圍合并后，兩個sstable之間將不再重疊，便能快速檢索到 查詢的值所在的sstable了。

還沒完，剛才提到了合并sstable文件，合并既能讓sstable文件之間不會產(chǎn)生索引范圍覆蓋，又能減少大量小體積的sstable，但是在什么時候進行合并呢？

如果在新增sstable時進行合并，新增一個sstable，發(fā)現(xiàn)現(xiàn)有的sstable和和新增的sstable索引的范圍都有重合關(guān)系，是不是要將新增的sstable全部與現(xiàn)有的sstable進行多路歸并排序，然后再生成新的一個或多個sstable。

這樣的效率真的會高嗎？ 新增的索引體積是比較小的，如果新增一個比較小的數(shù)量級的sstable文件就去合并所有的sstable文件顯然是不合理的，并且由于新增的sstable體積小，產(chǎn)生較為頻繁，如果每次都全量合并將會導致磁盤io在較長時間都處于一個比較高的值。

所以，最后業(yè)界的實現(xiàn)一般采用下面的多層次合并的方式。每一層的容量是上一層容量的10倍。

level0層 是標記為可讀的那片內(nèi)存直接順序?qū)懭氪疟P形成的sstable 文件的集合，只有4個文件，注意由于level0是內(nèi)存直接寫入生成的，所以level0層索引范圍是有重合的，而其他層的索引范圍將不會有重合產(chǎn)生。

當再有新的的sstable文件生成時，那么新的sstable就會和當前層有重合的sstable合并到下一層。

當新增一個sstable時，sstable的范圍是500 ~ 1000 ，那么這個范圍中l(wèi)evel0層有500 ~ 1000的sstable和300 ~ 1200的sstable都和新增的sstable有重合，所以需要將這3個sstable一起合并到下一層，而合并到下一層時，發(fā)現(xiàn)上一層需要合并的索引范圍是500 ~ 1200，所以找出level1層中與此索引范圍有重合的sstable，即level1 中標記為紅色的sstable，然后再與它們進行合并產(chǎn)生新的sstable。

如果合并后發(fā)現(xiàn)當前層的容量達到了某個閥值，那么就又會將當前層的sstable繼續(xù)合并到一層，一般我們會限制一個最大的層數(shù)，到達最大層數(shù)后就不再繼續(xù)合并了。

這樣多層滾動合并的設計能很好的解決每次新的sstable產(chǎn)生可能引發(fā)的高磁盤io的情況，因為它將之前的一次性合并按層次分攤到了多次，將整個合并過程分攤到了不同的時間段，緩解了寫放大問題。

lsm 小結(jié)

從lsm的實現(xiàn)上來看，已經(jīng)能夠明白它的一個數(shù)據(jù)寫入和檢索過程。這里再來總結(jié)一下。 lsm 寫入時，會先寫入到內(nèi)存，內(nèi)存里數(shù)據(jù)的檢索一般是比較高效的數(shù)據(jù)結(jié)構(gòu)，類似跳表，紅黑樹等，內(nèi)存中的數(shù)據(jù)是有序。 內(nèi)存到達某個閥值后，會將這片內(nèi)存標記為只讀，后續(xù)新的寫入將在新的內(nèi)存區(qū)域上進行，而只讀的內(nèi)存會將有序的數(shù)據(jù)寫入到磁盤level0層，形成sstable文件。當level0層的sstable文件超過4個后，將會與level1層sstable產(chǎn)生合并行為，level0層以后的層級的索引范圍都是沒有重合的。

lsm讀取數(shù)據(jù)時，同樣先從內(nèi)存中讀取，如果讀取不到則會從磁盤由低層到高層進行讀取，讀取到則返回，讀取不到則直至最后一層為止。由于level0層以后的 每層 sstable數(shù)據(jù)都是有序且不重合的，在快速檢索到數(shù)據(jù)所在的sstable 后，便能快速通過二分查找判斷數(shù)據(jù)是否在該層中，真實實現(xiàn)，在sstable還用上了布隆過濾，來快速判斷元素不在sstable的情況。如果該層找不到，則繼續(xù)往下一層尋找。

可以看到，在讀取數(shù)據(jù)時，最差的情況要遍歷所有的層次，這也是為什么說lsm適合寫多讀少的場景，在讀時也最好讀取最近的數(shù)據(jù)。

看看與b+tree的區(qū)別

b+tree的索引更新是原地更新，原地更新帶來的代價很明顯，第一個是要加鎖，第二個由于更新時各個節(jié)點之前的在磁盤位置并不相鄰帶來的隨機寫入問題。 但b+tree的隨機讀性能很好，上千萬的數(shù)據(jù)最多也只需要兩三次磁盤io。

而lsm在高效寫的優(yōu)勢下 帶來了讀放大問題，最壞的情況可能要在lsm多層磁盤索引結(jié)構(gòu)中，每個層次都找一遍。在寫頻繁的場景下，查詢也基本上是查最近數(shù)據(jù)時，lsm具有很好的性能。

問了一通之后，算是理清楚了lsm的原理了，平時我也傾向于向自己發(fā)問來不斷剖析問題，結(jié)尾我再問一個問題吧，這篇文章里，我一共問了幾個問題呢？

以上就是問哭自己lsm 索引原理及剖析的詳細內(nèi)容，更多關(guān)于lsm 索引原理的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論