數據庫使用到的LSM指的是什么

這篇文章將為大家詳細講解有關數據庫使用到的LSM指的是什么，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

很多數據庫都使用了 LSM Tree 的存儲模型，包括 LevelDB，HBase，Google BigTable，Cassandra，InfluxDB 等。所以在面試過程中會經常被問到，最新重新又復習了一遍 LSM Tree 的原理。

特點

總的來說就是通過將大量的隨機寫轉換為順序寫，從而極大地提升了數據寫入的性能，雖然與此同時犧牲了部分讀的性能。

只適合存儲 key 值有序且寫入大于讀取的數據，或者讀取操作通常是 key 值連續的數據。

存儲模型

WAL

在設計數據庫的時候經常被使用，當插入一條數據時，數據先順序寫入 WAL 文件中，之后插入到內存中的 MemTable 中。這樣就保證了數據的持久化，不會丟失數據，并且都是順序寫，速度很快。當程序掛掉重啟時，可以從 WAL 文件中重新恢復內存中的 MemTable。

MemTable

MemTable 對應的就是 WAL 文件，是該文件內容在內存中的存儲結構，通常用 SkipList 來實現。MemTable 提供了 k-v 數據的寫入、刪除以及讀取的操作接口。其內部將 k-v 對按照 key 值有序存儲，這樣方便之后快速序列化到 SSTable 文件中，仍然保持數據的有序性。

Immutable Memtable

顧名思義，Immutable Memtable 就是在內存中只讀的 MemTable，由于內存是有限的，通常我們會設置一個閥值，當 MemTable 占用的內存達到閥值后就自動轉換為 Immutable Memtable，Immutable Memtable 和 MemTable 的區別就是它是只讀的，系統此時會生成新的 MemTable 供寫操作繼續寫入。

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

SSTable

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

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

常用操作的實現

寫入

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

更新

更新操作其實并不真正存在，和寫入一個 k-v 數據沒有什么不同，只是在讀取的時候，會從 Level0 層的 SSTable 文件開始查找數據，數據在低層的 SSTable 文件中必然比高層的文件中要新，所以總能讀取到最新的那條數據。也就是說此時在整個 LSM Tree 中可能會同時存在多個 key 值相同的數據，只有在之后合并 SSTable 文件的時候，才會將舊的值刪除。

刪除

刪除一條記錄的操作比較特殊，并不立即將數據從文件中刪除，而是記錄下對這個 key 的刪除操作標記，同插入操作相同，插入操作插入的是 k-v 值，而刪除操作插入的是 k-del 標記，只有當合并 SSTable 文件時才會真正的刪除。

Compaction

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

為了節省磁盤空間占用，控制 SSTable 文件數量，需要將多個 SSTable 文件進行合并，生成一個新的 SSTable 文件。比如說有 5 個 10 行的 SSTable 文件要合并成 1 個 50 行的 SSTable 文件，但是其中可能有 key 值重復的數據，我們只需要保留其中最新的一條即可，這個時候新生成的 SSTable 可能只有 40 行記錄。

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

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

2. 當一層的文件達到指定數量后，其中的一個文件會被合并進入上一層的文件中。

讀取

LSM Tree 的讀取效率并不高，當需要讀取指定 key 的數據時，先在內存中的 MemTable 和 Immutable MemTable 中查找，如果沒有找到，則繼續從 Level 0 層開始，找不到就從更高層的 SSTable 文件中查找，如果查找失敗，說明整個 LSM Tree 中都不存在這個 key 的數據。如果中間在任何一個地方找到這個 key 的數據，那么按照這個路徑找到的數據都是最新的。

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

優化讀取

因為這樣的讀取效率非常差，通常會進行一些優化，例如 LevelDB 中的 Mainfest 文件，這個文件記錄了 SSTable 文件的一些關鍵信息，例如 Level 層數，文件名，最小 key 值，最大 key 值等，這個文件通常不會太大，可以放入內存中，可以幫助快速定位到要查詢的 SSTable 文件，避免頻繁讀取。

另外一個經常使用的方法是布隆解析器(Bloom filter)，布隆解析器是一個使用內存判斷文件是否包含一個關鍵字的有效方法。

LSM Tree 的思想非常實用，將隨機寫轉換為順序寫來大幅提高寫入操作的性能，但是犧牲了部分讀的性能。

由于時間序列數據庫的特性，運用 LSM Tree 的算法非常合適。持續寫入數據量大，數據和時間相關，編碼到 key 值中很容易使 key 值有序。讀取操作相對來說較少，而且通常不是讀取單個 key 的值，而是一段時間范圍內的數據，這樣就把 LSM Tree 讀取性能差的劣勢縮小了，反而由于數據在 SSTable 中是按照 key 值順序排列，讀取大塊連續的數據時效率也很高。

關于數據庫使用到的LSM指的是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。