數(shù)據(jù)庫使用到的LSM指的是什么

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

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

特點(diǎn)

總的來說就是通過將大量的隨機(jī)寫轉(zhuǎn)換為順序?qū)?，從而極大地提升了數(shù)據(jù)寫入的性能，雖然與此同時(shí)犧牲了部分讀的性能。

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

存儲模型

WAL

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

MemTable

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

Immutable Memtable

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

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

SSTable

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ù)達(dá)到指定閥值后會在 Level 0 層創(chuàng)建一個(gè)新的 SSTable。當(dāng)某個(gè) Level 下的文件數(shù)超過一定值后，就會將這個(gè) Level 下的一個(gè) SSTable 文件和更高一級的 SSTable 文件合并，由于 SSTable 中的 k-v 數(shù)據(jù)都是有序的，相當(dāng)于是一個(gè)多路歸并排序，所以合并操作相當(dāng)快速，最終生成一個(gè)新的 SSTable 文件，將舊的文件刪除，這樣就完成了一次合并過程。

常用操作的實(shí)現(xiàn)

寫入

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

更新

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

刪除

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

Compaction

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

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

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

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

2. 當(dāng)一層的文件達(dá)到指定數(shù)量后，其中的一個(gè)文件會被合并進(jìn)入上一層的文件中。

讀取

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

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

優(yōu)化讀取

因?yàn)檫@樣的讀取效率非常差，通常會進(jìn)行一些優(yōu)化，例如 LevelDB 中的 Mainfest 文件，這個(gè)文件記錄了 SSTable 文件的一些關(guān)鍵信息，例如 Level 層數(shù)，文件名，最小 key 值，最大 key 值等，這個(gè)文件通常不會太大，可以放入內(nèi)存中，可以幫助快速定位到要查詢的 SSTable 文件，避免頻繁讀取。

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

LSM Tree 的思想非常實(shí)用，將隨機(jī)寫轉(zhuǎn)換為順序?qū)憗泶蠓岣邔懭氩僮鞯男阅?，但是犧牲了部分讀的性能。

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

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