LSM Tree原理詳解

0 前言

對于存儲介質為磁盤或SSD的數(shù)據(jù)庫，長期以來主流使用B+樹這種索引結構來實現(xiàn)快速數(shù)據(jù)查找。當數(shù)據(jù)量不太大時，B+樹讀寫性能表現(xiàn)非常好。但是在海量數(shù)據(jù)情況下，B+樹越來越高，由于B+樹更新和刪除數(shù)據(jù)時需要沿著B+樹逐層進行頁分裂和頁合并，嚴重影響數(shù)據(jù)寫入性能。為了應對這種情況，google在論文《Bigtable: A Distributed Storage System for Structured Data》中介紹了一種新的數(shù)據(jù)組織結構LSM Tree(Log-Structured Merge Tree)，隨后，Bigtable主要作者Jeffrey Dean和 Sanjay Ghemawat開源了一款基于LSM Tree實現(xiàn)的數(shù)據(jù)庫LevelDB，讓大家對LSM Tree的思想和實現(xiàn)理解得更為透徹、深入。當前，比較流行的NoSQL數(shù)據(jù)庫，如Cassandra、RocksDB、HBase、LevelDB等，newSQL數(shù)據(jù)庫，如TiDB，均是使用LSM Tree來組織磁盤數(shù)據(jù)的。甚至像SQLite這種傳統(tǒng)的關系型數(shù)據(jù)庫和MongoDB這種傳統(tǒng)的文檔型數(shù)據(jù)庫都提供了基于LSM Tree的存儲引擎作為可選的存儲引擎。

1 基本原理簡述

LSM Tree的全稱為Log-Structured Merge Tree，是一個分層、有序、針對塊存儲設備（機械硬盤和SSD）特點而設計的數(shù)據(jù)存儲結構。它的核心理論基礎還是磁盤的順序寫速度比隨機寫速度快非常多，即使是SSD，由于塊擦除和垃圾回收的影響，順序寫速度還是比隨機寫速度快很多。

磁盤隨機寫與順序寫性能對比圖

LSM Tree將存儲數(shù)據(jù)切分為一系列的SSTable（Sorted String Table），一個SSTable內的數(shù)據(jù)是有序的任意字節(jié)組（即arbitrary byte string，并不是指編程語言中的String字符串），而且，SSTable一但寫入磁盤中，就像日志一樣不能再修改（這就是Log-Structured Merge Tree名字中Log-Structured一詞的由來）。當要修改現(xiàn)有數(shù)據(jù)時，LSM Tree并不直接修改舊數(shù)據(jù)，而是直接將新數(shù)據(jù)寫入新的SSTable中。同樣的，刪除數(shù)據(jù)時，LSM Tree也不直接刪除舊數(shù)據(jù)，而是寫一個相應數(shù)據(jù)的刪除標記的記錄到一個新的SSTable中。這樣一來，LSM Tree寫數(shù)據(jù)時對磁盤的操作都是順序塊寫入操作，而沒有隨機寫操作。

LSM Tree這種獨特的寫入方式，導致在查找數(shù)據(jù)時，LSM Tree就不能像B+樹那樣在一個統(tǒng)一的索引表中進行查找，而是從最新的SSTable到老的SSTable依次進行查找。如果在新SSTable中找到了需查找的數(shù)據(jù)或相應的刪除標記，則直接返回查找結果；如果沒有找到，再到老的SSTable中進行查找，直到最老的SSTable查找完。為了提高查找效率，LSM Tree對SSTable進行分層、有序組織，也就是說把SSTable組織成多層，同一層可以有多個SSTable，同一個數(shù)據(jù)在同一層的多個SSTable中可以不重復，而且數(shù)據(jù)可以做到在同一層中是有序的，即每一個SSTable內的數(shù)據(jù)是有序的，前一個SSTable的最大數(shù)據(jù)值小于后一個SSTable的最小數(shù)據(jù)值（實際情況比這個復雜，后面會介紹）。這樣可以加快在同一層SSTable中的數(shù)據(jù)查詢速度。同時，LSM Tree會將多個SSTable合并（Compact）為一個新的SSTable，這樣可以減少SSTable的數(shù)量，同時把修改前的數(shù)據(jù)或刪除的數(shù)據(jù)真正從SSTable中刪除，減小了SSTable的大?。ㄟ@就是Log-Structured Merge Tree名字中Merge一詞的由來），對提高查找性能極其重要（SSTable合并（Compact）過程對LSM Tree查找如此重要，以至于把它作為名字的一部分）。

2 讀寫過程詳述

2.1 LSM Tree框架圖

LSM Tree數(shù)據(jù)組織結構圖

上圖中，WAL（Write Ahead LOG）嚴格來說本身并不是LSM Tree數(shù)據(jù)結構的一部分，但是實際系統(tǒng)中，WAL是數(shù)據(jù)庫不可或缺的一部分，把WAL包括進來才能更準確的理解LSM Tree。

從圖中可知，LSM Tree的數(shù)據(jù)由兩部分組成：內存部分和持久到磁盤中的部分。內存部分由一個MemTable和一個或多個Immutable MemTable組成。磁盤中的部分由分布在多個level的SSTable組成。level級數(shù)越?。?code>level 0）表示處于該level的SSTable越新，level級數(shù)越大（level 1...level N）表示處于該level的SSTable越老，最大級數(shù)（level N）大小由系統(tǒng)設定。在本圖中，磁盤中最小的級數(shù)為level 0，也有的系統(tǒng)把內存中的Immutable MemTable定義為level 0，而磁盤中的數(shù)據(jù)從Level 1開始，這只是level定義的不同，并不影響系統(tǒng)的工作流程和對系統(tǒng)的理解。

WAL的結構和作用跟其他數(shù)據(jù)庫一樣，是一個只能在尾部以Append Only方式追加記錄的日志結構文件，它用來當系統(tǒng)崩潰重啟時重放操作，使MemTable和Immutable MemTable中未持久化到磁盤中的數(shù)據(jù)不會丟失。

MemTable往往是一個跳表（Skip List）組織的有序數(shù)據(jù)結構（當然，也可以是有序數(shù)組或紅黑樹等二叉搜索樹），跳表既支持高效的動態(tài)插入數(shù)據(jù)，對數(shù)據(jù)進行排序，也支持高效的對數(shù)據(jù)進行精確查找和范圍查找。

SSTable一般由一組數(shù)據(jù)block和一組元數(shù)據(jù)block組成。元數(shù)據(jù)block存儲了SSTable數(shù)據(jù)block的描述信息，如索引、BloomFilter、壓縮、統(tǒng)計等信息。因為SSTable是不可更改的，且是有序的，索引往往采用二分法數(shù)組結構就可以了。為了節(jié)省存儲空間和提升數(shù)據(jù)塊block的讀寫效率，可以對數(shù)據(jù)block進行壓縮。RocksDB的SSTable（sstfile）結構如下所示：

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]                  (see section: "filter" Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block]  (see section: "compression dictionary" Meta Block)
[meta block 4: range deletion block]          (see section: "range deletion" Meta Block)
[meta block 5: stats block]                   (see section: "properties" Meta Block)
...
[meta block K: future extended block]  (we may add more meta blocks in the future)
[metaindex block]
[Footer]                               (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

論文《BigTable》對SSTable的描述我覺得是比較清晰的，現(xiàn)摘錄如下，供大家參考：

An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Operations are provided to look up the value associated with a specified key, and to iterate over all key/value pairs in a specified key range. Internally, each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory, which allows us to perform lookups and scans without touching disk.

2.2 數(shù)據(jù)寫入過程

如上圖所示，LSM Tree寫入數(shù)據(jù)時，先寫一條記錄到WAL中，然后將數(shù)據(jù)寫入內存中的MemTable中，這樣寫入操作就完成了。

寫MemTable時，寫入新的數(shù)據(jù)，與修改現(xiàn)有數(shù)據(jù)的部分字段以及修改現(xiàn)有數(shù)據(jù)的所有字段，寫入操作過程幾乎是一樣的，都是把傳入的數(shù)據(jù)（合并）寫入到MemTable中。刪除數(shù)據(jù)時，則是在MemTable中寫入一條刪除標記。當MemTable的大小達到設定的大小（典型值是64KB）時，LSM Tree會把當前MemTable凍結為一個不可修改的Immutable MemTable，然后創(chuàng)建一個新的MemTable供新的數(shù)據(jù)寫入。同時，LSM Tree一般會有一些與寫入線程（或進程）相獨立的背景線程（或進程）負責將Immutable MemTable flush到磁盤中，將數(shù)據(jù)持久化。已經flush到磁盤中的Immutable MemTable對應的WAL就可以從磁盤中刪除了。而內存中Immutable MemTable數(shù)量的多少處決于Immutable MemTable flush的速度與Immutable MemTable生成的速度（數(shù)據(jù)寫入速度）的差值

從LSM Tree數(shù)據(jù)寫入過程可知，LSM Tree數(shù)據(jù)寫入的操作非常簡單，過程也非常少，只要寫WAL和內存中的MemTable即可。而寫WAL是以在文件末尾追加記錄方式的順序寫，無需操作任何數(shù)據(jù)結構，寫入速度非?？臁?code>MemTable雖然也需要進行跳表的插入和排序操作，但是MemTable是一個內存數(shù)據(jù)結構，同時MemTable的大小控制在一個非常非常小的規(guī)模（比如64KB），所以寫MemTable也是一個非常非常快的過程。

同時，我們還可以看到，數(shù)據(jù)的寫入速度與數(shù)據(jù)庫中數(shù)據(jù)總量的多少沒有關系。而且，不管是寫入新的數(shù)據(jù)，還是全量修改或部分修改現(xiàn)有數(shù)據(jù)，或是刪除現(xiàn)有數(shù)據(jù)，LSM Tree的寫入速度也幾乎沒多大差別。也就是說，LSM Tree的寫入速度是穩(wěn)定的，跟數(shù)據(jù)規(guī)模和數(shù)據(jù)更新類型都沒有關系。

2.3 數(shù)據(jù)查找過程

根據(jù)LSM Tree的寫入特點我們知道，如果一項數(shù)據(jù)更新多次，這項數(shù)據(jù)可能會存儲在多個不同的SSTable中，甚至一項數(shù)據(jù)的不同部分的最新數(shù)據(jù)內容存儲在不同的SSTable中（數(shù)據(jù)部分更新的場景）。LSM Tree把這種現(xiàn)象叫做空間放大（space amplification），因為一項數(shù)據(jù)在磁盤中存儲了多份副本，而老的副本是已經過時了的，不需要的，數(shù)據(jù)實際占用的存儲空間比有效數(shù)據(jù)需要的大。

空間放大這種現(xiàn)象導致LSM Tree的查找過程是這樣的：按新到老的順序查找SSTable，直到在某個（或某些個）SSTable中查找到了所需的數(shù)據(jù)，或者最老的SSTable查找完也沒有找到需要的數(shù)據(jù)。具體查找順序為：先在內存MemTable中查找，然后在內存中的Immutable MemTable中查找，然后在level 0 SSTable中查找，最后在level N SSTable中查找。

查找某個具體的SSTable時，一般先把SSTable的元數(shù)據(jù)block讀到內存中，根據(jù)BloomFilter可以快速確定數(shù)據(jù)在當前SSTable中是否存在，如果存在，則采用二分法確定數(shù)據(jù)在哪個數(shù)據(jù)block，然后將相應數(shù)據(jù)block讀到內存中進行精確查找。

從LSM Tree數(shù)據(jù)查找過程我們可以看到，為了查找到目標數(shù)據(jù)，我們需要讀取并查找不包含目標數(shù)據(jù)的SSTable，如果目標數(shù)據(jù)在最底層level N的SSTable中，我們需要讀取和查找所有的SSTable！LSM Tree把這種讀取和查找了無關SSTable的現(xiàn)象叫做讀放大(read amplification)。

讀放大現(xiàn)象嚴重影響了LSM Tree數(shù)據(jù)查找性能，甚至是災難性的（數(shù)據(jù)壓根不存在或在最老的SSTable中），論文《BigTable》提到了幾種提升數(shù)據(jù)查找性能的方法：

  1. 壓縮（Compression）

    介紹SSTable時已經提到了，對數(shù)據(jù)block進行壓縮，通過增加占用CPU壓縮和解壓縮資源來降低數(shù)據(jù)block磁盤空間占用和讀寫時間。

  2. BloomFilter

    描述查找過程時也已經提到了，BloomFilter可以快速確定數(shù)據(jù)不在SSTable中，而不用讀取數(shù)據(jù)block內容

  3. 緩存（Cache）

    因為SSTable是不可變的，非常適合緩存到內存中，這樣熱點數(shù)據(jù)不用訪問磁盤

  4. SSTable合并(Compaction)

    將多個SSTable合并為一個SSTable，刪除舊數(shù)據(jù)或物理刪除已經被刪除的數(shù)據(jù)，降低空間放大；同時減少SSTable數(shù)量，降低讀放大

其實這些優(yōu)化措施，除了SSTable合并是LSM Tree獨有的，前面三條都是數(shù)據(jù)庫通用的措施，甚至SSTable合并也不是LSM Tree獨有的，它與更早出現(xiàn)的lucene的段合并（Segment Merge）的原理和目標其實是有相似的地方的(當然他們的寫入和查找過程還是有本質區(qū)別的)。下面詳細介紹下SSTable合并

3 SSTable合并

從上述讀寫過程描述可以看到，LSM Tree雖然數(shù)據(jù)寫入速度非常快，但是存在空間放大和讀放大的現(xiàn)象，這些現(xiàn)象如果不進行抑制，可能導致讀性能的極端惡化和空間占用過于膨脹，最終導致LSM Tree在實際生產環(huán)境中不可用。SSTable合并就是用來緩解這種現(xiàn)象的。LSM Tree支持將多個SSTable合并為一個新的SSTable，合并過程中，會刪除舊的重疊數(shù)據(jù)，并真正物理刪除被刪除的數(shù)據(jù)，也減少了SSTable的數(shù)量，這樣消除了空間放大，同時也提升了數(shù)據(jù)查找的性能。但是，合并需要將合并涉及的SSTable讀入內存，并把合并后產生的新的SSTable寫入磁盤，會增加磁盤IO和CPU的消耗，這種寫入磁盤的數(shù)據(jù)量大于實際數(shù)據(jù)量現(xiàn)象成為寫放大（write amplification），當然合并也意味著讀放大。由此可見，SSTable合并是一把雙刃劍，有利也有弊，需要合理利用。

SSTable合并分為minor compaction和major compaction，minor compaction是指將內存中的Immutable MemTable內容flush到磁盤中形成SSTable時進行的數(shù)據(jù)處理過程。major compaction則是指相鄰的兩級level將數(shù)字小level（如level 0）的SSTable合并入數(shù)字大level（如level 1）的SSTable中的過程。

SSTable合并其實就是在空間放大、寫放大、讀放大幾個相互制約的因素間尋求平衡，不同的應用場景需要重點優(yōu)化解決某個問題，從而形成了幾種典型的SSTable合并策略：

3.1 leveled compaction

leveled compaction為每層level的SSTable數(shù)據(jù)總大小設置一個閾值，level數(shù)越大，閾值設置的也越大，比如level0閾值為10MB、level1閾值設置為100MB、level2閾值設置為1000MB。當某level層的數(shù)據(jù)總量大小超過設置的閾值時，則選取一個SSTable合并入高一級level層的一個或多個SSTable中。高level層涉及的SSTable的選擇處決于數(shù)據(jù)的分布，以合并后高level層中的所有SSTable數(shù)據(jù)是整體有序的為準（one sorted run），也就是說數(shù)據(jù)在同一層中不存在重疊的現(xiàn)象。

leveled compaction合并過程示意圖

leveled compaction因為會將SSTable合并入多個SSTable中，能保證同一層的SSTable中數(shù)據(jù)不會重疊，所以是一種最小化空間放大的策略。但是，合并時需要讀取多個SSTable，然后寫入多個更新后的SSTable，導致更大的寫放大和讀放大。但是在數(shù)據(jù)查找過程中，由于減少了需要查找SSTable的數(shù)量，降低了數(shù)據(jù)查找時的讀放大，提升了數(shù)據(jù)查找的性能。所以，leveled compaction適合比較關注數(shù)據(jù)查詢速度和控制磁盤空間占用的場景。比如，數(shù)據(jù)寫入一次，但是會被頻繁反復查詢；數(shù)據(jù)經常被修改，但是需要控制磁盤空間大小和保證數(shù)據(jù)查詢速度。

Cassandra的LCS（Leveled Compaction Strategy）和RocksDB的Classic Leveled Compaction采用的就是leveled compaction策略。

3.2 tiered compaction

tiered compaction當某level層的SSTable數(shù)量達到設定的閾值時，則將該層的多個SSTable合并為一個新的SSTable，并放入高一層level中。

tiered compaction合并過程示意圖

tiered compaction比較偏重于控制寫放大在一定程度的前提下降低空間放大和提升數(shù)據(jù)查詢性能。但是在同一層的SSTable中還是存在數(shù)據(jù)重疊，數(shù)據(jù)查詢性能不如leveled compaction。尤其是隨著level數(shù)越來越大，單個SSTable數(shù)據(jù)量也越來越大，合并觸發(fā)條件也越來越難，這些巨型SSTable中的重疊數(shù)據(jù)和被刪除的數(shù)據(jù)占用的空間也就越來越難被釋放掉。tiered compaction比較適合數(shù)據(jù)修改頻率不高，且最近寫入的數(shù)據(jù)查詢頻率比較高的場景。

Cassandra的STCS（Size Tiered Compaction Strategy）和RocksDB的universal Compaction使用的是tiered compaction策略。

3.3 leveled-tiered mixed compaction

結合leveled compaction和tiered compaction的優(yōu)勢，在部分level之間采用tiered compaction，在另一部分level之間采用leveled compaction。

RocksDB的leveled Compaction采用的是leveled-tiered mixed compaction策略。數(shù)據(jù)從Immutable MemTable flush到level 0時采用的是tiered compaction，也就是說level0中是存在重疊數(shù)據(jù)的。level0到levelN之間采用leveld compaction策略。

3.4 FIFO compaction

FIFO compaction在磁盤中只有一個level層級，SSTable按生成的時間順序排列，刪除過早生成的SSTable。

FIFO compaction適合時間序列數(shù)據(jù)，一旦生成數(shù)據(jù)就不會再修改。

Cassandra的TWCS（Time Window Compaction Strategy）、DTCS（Date Tiered Compaction Strategy）和RocksDB的FIFO compaction使用的是FIFO類型的合并策略。

4 LSM Tree原理對系統(tǒng)讀寫性能提升的幾點啟示

  1. 寫數(shù)據(jù)時盡量批量操作。LSM Tree數(shù)據(jù)寫入性能已經很高了，但是批量操作時可以節(jié)省網(wǎng)絡傳輸RTT時間。
  2. 將數(shù)據(jù)進行分片。這樣多個分片可以并行寫，如果數(shù)據(jù)路由處理得當，也可以提升數(shù)據(jù)查詢速度。但是增加了維護多個分片數(shù)據(jù)讀寫的復雜度。
  3. 選擇合適的主鍵。兩個比較流行的選擇是：1）采用遞增的數(shù)字作為主鍵；2）采用業(yè)務本身標識符作為主鍵。數(shù)字作為主鍵可以減少寫入和查詢時進行比較、排序等操作的時間，還能提升索引緩存的效率；遞增的數(shù)字往往保證是順序寫入的，可以減少排序時間。但是遞增的數(shù)字往往不具備業(yè)務語義，業(yè)務實際查詢時需要先查二級索引，然后進行主鍵查找。業(yè)務標識符往往是業(yè)務實際的身份區(qū)分符號，業(yè)務也往往通過業(yè)務標識符進行數(shù)據(jù)查詢。但是業(yè)務標識符往往是一個字符串，可能會比較長，這樣比較、排序、緩存效率方面不如數(shù)字。一般情況下，本人建議LSM Tree數(shù)據(jù)庫采用業(yè)務標識符作為主鍵。因為為業(yè)務標識符建立索引以及維護索引的成本是免不了的，與其建立二級索引，不如直接建立主鍵索引。
  4. 設計合理的二級索引，不建立不需要的二級索引。二級索引可以提升相應數(shù)據(jù)的查詢速度，每增加一個二級索引，就需要額外維護相應的二級索引文件，嚴重影響寫入數(shù)據(jù)性能。
  5. 根據(jù)具體場景使用合適的SSTable合并策略。單次寫，頻繁讀場景選擇leveled compaction策略。
  6. 在允許情況下關閉自動SSTable合并，在業(yè)務量低的時間段強制執(zhí)行SSTable合并。
  7. 數(shù)據(jù)更新時合理選擇全量更新（覆蓋寫）方式還是部分更新（增量寫）方式。全量更新方式增加了傳輸和寫入的數(shù)據(jù)量，但是可以提升數(shù)據(jù)查詢速度。部分更新方式會使數(shù)據(jù)分布在多個SSTable中，需要查詢和合并多個SSTable中的數(shù)據(jù)才能得到完整的數(shù)據(jù)，會降低數(shù)據(jù)查詢速度。如果數(shù)據(jù)修改比較頻繁，且需要較高查詢速度，建議采用全量更新方式。
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容