在前面我寫了B、B+樹、Wisckey的總結(jié)。不過我覺得應(yīng)該將今天的內(nèi)容放在總結(jié)Wisckey之前。因為wisckey就是針對LSM進行效率上的提升。所以本文我們重點介紹LSM與LevelDB。

LSM

1 LSM概念介紹

首先我們簡單的介紹一下LSM的思想。而具體的操作過程我們放在LevelDB中進行講述。

實際上，要是給LSM的命名斷句，Log和Structured這兩個詞是合并在一起的，LSM-Tree應(yīng)該斷句成Log-Structured、Merge、Tree三個詞匯，這三個詞匯分別對應(yīng)以下三點LSM的關(guān)鍵性質(zhì)：

將數(shù)據(jù)形成Log-Structured：由于數(shù)據(jù)會首先寫入內(nèi)存，而內(nèi)存存在斷電丟失的情況。所以在將數(shù)據(jù)寫入LSM內(nèi)存結(jié)構(gòu)之前，先記錄log。這樣LSM就可以將有易失性的內(nèi)存看做永久性存儲器。

• 在將數(shù)據(jù)寫入LSM內(nèi)存結(jié)構(gòu)之前，先記錄log。這樣LSM就可以將有易失性的內(nèi)存看做永久性存儲器。并且信任內(nèi)存上的數(shù)據(jù)，等到內(nèi)存容量達到門限再集體寫入磁盤。將數(shù)據(jù)形成Log-Structured，也是將整體存儲結(jié)構(gòu)轉(zhuǎn)換成了“內(nèi)存(in-memory)”存儲結(jié)構(gòu)。

• 由于磁盤隨機讀寫比順序讀寫慢3個數(shù)量級，LSM盡量將磁盤隨機讀寫轉(zhuǎn)換成順序讀寫。

對于B樹來說，雖然其查找非常高效，但是如果磁盤是隨機讀寫的情況，那么就會由于大量尋道導(dǎo)致其性能不佳。而對于LSM，它將所有數(shù)據(jù)不組織成一個整體索引結(jié)構(gòu)，而組織成有序的文件集。每次LSM面對磁盤寫，將數(shù)據(jù)寫入一個或幾個新生成的文件，順序?qū)懭肭也荒苄薷钠渌募?，這樣就將隨機讀寫轉(zhuǎn)換成了順序讀寫。LSM將一次性集體寫入的文件作為一個level，磁盤上劃分多l(xiāng)evel，level與level之間互相隔離。這就形成了，以寫入數(shù)據(jù)時間線形成的邏輯上、而非物理上的層級結(jié)構(gòu)，這也就是為什么LSM被命名為”tree“，但不是“tree”。

• 之后將數(shù)據(jù)按key排序。為了防止不同file、level上存在文件更新或者相同空間從而造成冗余和降低讀性能。所以我們要將數(shù)據(jù)按key排序，并合并不同file、level上的數(shù)據(jù)。

很明顯，LSM犧牲了一部分讀的性能和增加了合并的開銷，換取了高效的寫性能。那LSM為什么要這么做？實際上，這就關(guān)系到對于磁盤寫（直接寫的效率）已經(jīng)沒有什么優(yōu)化手段了，而對于磁盤讀，不論硬件還是軟件上都有優(yōu)化的空間。通過多種優(yōu)化后，讀性能雖然仍是下降，但可以控制在可接受范圍內(nèi)。實際上，用于磁盤上的數(shù)據(jù)結(jié)構(gòu)不同于用于內(nèi)存上的數(shù)據(jù)結(jié)構(gòu)，用于內(nèi)存上的數(shù)據(jù)結(jié)構(gòu)性能的瓶頸就在搜索復(fù)雜度，而用于磁盤上的數(shù)據(jù)結(jié)構(gòu)性能的瓶頸在磁盤IO，甚至是磁盤IO的模式。

2 LSM結(jié)構(gòu)

• 一、WAL

在設(shè)計數(shù)據(jù)庫的時候經(jīng)常被使用，當(dāng)插入一條數(shù)據(jù)時，數(shù)據(jù)先順序?qū)懭?到WAL 文件中，之后插入到內(nèi)存中的 MemTable 中。這樣就保證了數(shù)據(jù)的持久化，不會丟失數(shù)據(jù)，并且都是順序?qū)懀俣群芸?。?dāng)程序掛掉重啟時，可以從 WAL 文件中重新恢復(fù)內(nèi)存中的 MemTable。

• 二、MemTable

MemTable 對應(yīng)的就是 WAL 文件，是該文件內(nèi)容在內(nèi)存中的存儲結(jié)構(gòu)，通常用 SkipList 來實現(xiàn)。MemTable 提供了 k-v 數(shù)據(jù)的寫入、刪除以及讀取的操作接口。其內(nèi)部將 k-v 對按照 key 值有序存儲，這樣方便之后快速序列化到 SSTable 文件中，仍然保持數(shù)據(jù)的有序性。而MemTable 就是直接與寫入的數(shù)據(jù)直接接觸。由于在內(nèi)存中且為順序直接保存，所以其寫入效率是極高的。

• 三、Immutable Memtable

顧名思義，Immutable Memtable 就是在內(nèi)存中的只讀 MemTable，由于內(nèi)存是有限的，通常我們會設(shè)置一個閥值，當(dāng) MemTable 占用的內(nèi)存達到閥值后就自動轉(zhuǎn)換為 Immutable Memtable，Immutable Memtable 和 MemTable 的區(qū)別就是它是只讀的，系統(tǒng)此時會生成新的 MemTable 供寫操作繼續(xù)寫入。

之所以要使用 Immutable Memtable，就是為了避免將 MemTable 中的內(nèi)容序列化到磁盤中時會阻塞寫操作。

• 四、SSTable

image.png

SSTable分為許多級別（例如levelDB中的level0~level6）。

SSTable 就是 MemTable 中的數(shù)據(jù)在磁盤上的有序存儲，其內(nèi)部數(shù)據(jù)是根據(jù) key 從小到大排列的。通常為了加快查找的速度，需要在 SSTable 中加入數(shù)據(jù)索引，可以快讀定位到指定的 k-v 數(shù)據(jù)。

SSTable 通常采用的分級的結(jié)構(gòu)，例如 LevelDB 中就是如此。MemTable 中的數(shù)據(jù)達到指定閥值后會在 Level 0 層創(chuàng)建一個新的 SSTable。當(dāng)某個 Level 下的文件數(shù)超過一定值后，就會將這個 Level 下的一個 SSTable 文件和更高一級的 SSTable 文件合并，由于 SSTable 中的 k-v 數(shù)據(jù)都是有序的，相當(dāng)于是一個多路歸并排序，所以合并操作相當(dāng)快速，最終生成一個新的 SSTable 文件，將舊的文件刪除，這樣就完成了一次合并過程。

3 LSM基本操作

對于存儲相關(guān)的內(nèi)容無非設(shè)計“增、刪、改、查”四中操作。下面我們具體的看一看相關(guān)操作。

一、寫入

image.png

在 LSM Tree 中，寫入操作是相當(dāng)快速的，只需要在 WAL 文件中順序?qū)懭氘?dāng)次操作的內(nèi)容，成功之后將該 k-v 數(shù)據(jù)寫入 MemTable 中即可。盡管做了一次磁盤 IO，但是由于是順序追加寫入操作，效率相對來說很高，并不會導(dǎo)致寫入速度的降低。數(shù)據(jù)寫入 MemTable 中其實就是往 SkipList 中插入一條數(shù)據(jù)，過程也相當(dāng)簡單快速。

二、更新

更新操作并不是我們想象中的那樣，找到數(shù)據(jù)的位置然后將value修改掉balabala。而其和寫入一個 k-v 數(shù)據(jù)沒有什么不同。我們倘若要修改數(shù)據(jù)，那么不需要管理level-n中的數(shù)據(jù)，而是直接選擇插入新數(shù)據(jù)。由于數(shù)據(jù)在低層的數(shù)據(jù)比高層要新，所以我們從低到高讀出的數(shù)據(jù)是從新到舊的。所以這個機制也幫助了我們不少。

而對于這些多余的數(shù)據(jù)，也就是說此時在整個 LSM Tree 中可能會同時存在多個 key 值相同的數(shù)據(jù)，只有在之后合并 SSTable 文件的時候，才會將舊的值刪除。

三、刪除

如圖所示，我們key3就是刪除的操作。刪除一條記錄的操作比較特殊，并不立即將數(shù)據(jù)從文件中刪除，而是記錄下對這個 key 的刪除操作標(biāo)記，同插入操作相同，插入操作插入的是 k-v 值，而刪除操作插入的是 k-del 標(biāo)記，只有當(dāng)合并 SSTable 文件時才會真正的刪除。

四、Compaction

當(dāng)數(shù)據(jù)不斷從 Immutable Memtable 序列化到磁盤上的 SSTable 文件中時，SSTable 文件的數(shù)量就不斷增加，而且其中可能有很多更新和刪除操作并不立即對文件進行操作，而只是存儲一個操作記錄，這就造成了整個 LSM Tree 中可能有大量相同 key 值的數(shù)據(jù)，占據(jù)了磁盤空間。

為了節(jié)省磁盤空間占用，控制 SSTable 文件數(shù)量，需要將多個 SSTable 文件進行合并，生成一個新的 SSTable 文件。

比如說有 5 個 10 行的 SSTable 文件要合并成 1 個 50 行的 SSTable 文件，但是其中可能有 key 值重復(fù)的數(shù)據(jù)，我們只需要保留其中最新的一條即可，這個時候新生成的 SSTable 可能只有 40 行記錄。

通常在使用過程中我們采用分級合并的方法，其特點如下：

每一層都包含大量 SSTable 文件，key 值范圍不重復(fù)，這樣查詢操作只需要查詢這一層的一個文件即可。(第一層比較特殊，key 值可能落在多個文件中，并不適用于此特性）

image.png

當(dāng)一層的文件達到指定數(shù)量后，其中的一個文件會被合并進入下一層的文件中。

五、讀取

由于LSM更偏向?qū)懭霐?shù)據(jù)，所以其讀效率相對較低。

當(dāng)需要讀取指定 key 的數(shù)據(jù)時，先在內(nèi)存中的 MemTable 和 Immutable MemTable 中查找，如果沒有找到，則繼續(xù)從 Level 0 層開始，找不到就從更高層的 SSTable 文件中查找，如果查找失敗，說明整個 LSM Tree 中都不存在這個 key 的數(shù)據(jù)。

如果中間在任何一個地方找到這個 key 的數(shù)據(jù)，那么按照這個路徑找到的數(shù)據(jù)都是最新的。

image.png

在每一層的 SSTable 文件的 key 值范圍是不重復(fù)的，所以只需要查找其中一個 SSTable 文件即可確定指定 key 的數(shù)據(jù)是否存在于這一層中。Level 0 層比較特殊，因為數(shù)據(jù)是 Immutable MemTable 直接寫入此層的，所以 Level 0 層的 SSTable 文件的 key 值范圍可能存在重復(fù)，查找數(shù)據(jù)時有可能需要查找多個文件。

LevelDB

寫的比較詳細的原理介紹有：https://www.cnblogs.com/zhihaowu/p/7884424.html

LevelDB的官方網(wǎng)站：https://leveldb.org.cn/