lsm簡析

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

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

提問開始

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)再有新的的sstable文件生成時(shí)，那么新的sstable就會和當(dāng)前層有重合的sstable合并到下一層。

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

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

這樣多層滾動合并的設(shè)計(jì)能很好的解決每次新的sstable產(chǎn)生可能引發(fā)的高磁盤io的情況，因?yàn)樗鼘⒅暗囊淮涡院喜磳哟畏謹(jǐn)偟搅硕啻?，將整個(gè)合并過程分?jǐn)偟搅瞬煌臅r(shí)間段，緩解了寫放大問題。

lsm 小結(jié)

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

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

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

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

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

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

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

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

最新評論