今天我們聊聊 LSM 樹。可能這是你第一次聽說 LSM 樹，但 LSM 樹其實已經是我們的老朋友了，大多數 NoSQL 如 HBase、LevelDB、Cassandra、RocksDB 等底層都有 LSM 樹的身影。今天我們聊聊 LSM 樹的理論、落地實踐以及它的缺陷。

LSM 樹的起源

LSM 樹的概念源自一篇論文《The Log-Structured Merge Tree》，其名稱直接反映了其核心特性：日志結構化和合并操作。日志結構化意味著數據以追加的方式寫入，類似于應用程序的日志輸出，這種方式的優勢在于其高效性，因為追加操作通常比隨機寫入要快得多。

在之前關于 Kafka 的討論中，我們已經了解到日志追加方式的優勢。LSM 樹的另一個關鍵特性是“合并”，即通過合并多個分散的日志片段來優化存儲和訪問效率。

LSM 樹是為 NoSQL 存儲系統而生的，NoSQL 基本都是 key-value 結構，因此最主要的功能只有兩個：put 和 get。put：寫入一個 key-value；get：給定一個 key 返回 Value。除此之外 LSM 還提供了排序能力，比如在 HBase 中，默認就是按照字典順序排序的，因此 HBase 可以 scan 某一個區間段的數據，比如我要查詢某個用戶的訂單列表并按下單時間倒序排列，就很適合用 HBase 來存儲，這得益于 LSM 的支持。

LSM 樹的架構與優勢

LSM 樹的優點就是寫入速度快，寫入快的秘密在于 LSM 樹利用了磁盤的順序寫，這使得 NoSQL 的性能優于關系型數據庫。

下圖是 LSM 樹的邏輯示意圖，LSM 樹是一個多層結構，自上而下存儲的數據越來越多。最上層是位于內存的 C0 層，里面存儲著最近寫入的 key-value，默認情況下這里的 key-value 是有序的，這個順序就是 key 的字典順序，并且由于數據在內存里，所以可以方便我們增刪改查。剩下的 C1 到 CN 層和 C0 是割裂的。因為除了 C0 層，其他層都在磁盤上，每一層都按照 key 的字典順序進行排列。

圖片

下面我們聊聊寫入的過程，假設一個 put 操作過來了，第一步數據會進入到最上方的 C0 層。然后 C0 層的數據越來越多，達到一定閾值后， C0 層的數據就會合并到 C1 層，這個合并過程就是大名鼎鼎的歸并排序，在這里稱作 Compaction。接下來 C1 層的數據越來越多，多出來的數據會 Compaction 到 C2 層，以此類推直到 CN 層。

假設有 2 個相同的 key 怎么辦呢？

比如 key “ABC”由于前面的合并已經寫入到 C2 層了，但是新的 put 請求又過來了，按這種設計，整個 LSM 樹會出現多個“ABC”。實際上，你不用擔心這個問題，LSM 會在 Compaction 過程中自動刪除早期的 key。Compaction 是一個異步過程，不會影響寫入性能。

講完了寫入，我們再講講查詢過程，在上面的寫入流程中可以看到，從 C0 到 CN，數據越來越“舊”，所以查詢時也是先查 C0 層，如果沒有查到需要的數據，再查 C1 層，逐層查。這樣一來，即使 Compaction 還沒來得及刪除舊的“ABC”也沒關系，我們會先找最新的“ABC”。

你會發現，針對 LSM 樹的一次查詢可能需要多層查詢，看上去稍慢。這種情況下 NoSQL 如何保證高性能查詢呢？這種情況下不同的 NoSQL 又針對查詢做了優化，比如 HBase 把數據放在不同的 Region 里面，完成對數據的路由等等，針對讀的優化和 LSM 樹無關，我在這兒就不贅述了。

總結一下，LSM 樹的結構其實就像是多層噴泉，上一層滿了就會溢出，到下一層。

LSM 樹實踐

上面的模型是論文中的表述，我們知道理論到實踐還是有點距離的。比如將 C0 跟 C1 合并的過程需要一個時間，這個時候新的 put 請求怎么辦，會被阻塞住嗎？另外，每次都要將這么多層合并，這個過程是怎樣進行的？這里我將以 LevelDB 為例，分享一下 LevelDB 是怎么落地 LSM 樹的。

我們先看看 LevelDB 中的 LSM 樹架構，這個和上面的理論 LSM 樹有些區別。要理解 LevelDB 中的 LSM 樹，我們需要關注兩種文件，第一種是內存中的 2 個 MemTable，MemTable 又分為 2 塊區域，一塊是普通內存 memtable，一塊是不可變的內存 Immutable MemTable。另一個文件叫 SSTable，中文翻譯是“有序的字符串表”，SSTable 是按照數據的 key 進行排序的，SSTable 位于磁盤上，一共有 7 層（L0 到 L6）。

圖片

我們來看看 put 的流程，首先將數據寫到普通內存 MemTable 中，當普通內存 MemTable 溢出，就將這個普通內存 MemTable 轉化成為不可變內存區域 Immutable MemTable，并再申請一個普通內存 MemTable 處理新的 put 消息。這樣一來，不可變內存區域 Immutable MemTable 就不會接收新的消息了，意味著 Immutable MemTable 可以同步磁盤了，同步的方式很簡單，Immutable MemTable 會直接放到 L0 層最后一個 SSTable 文件后面，并不奢求跟 L0 層的其他 SSTable 文件合并，也就是說 L0 的數據是無序的、可以冗余的。

從 L1 層開始，每往下一層空間都會比上一層大很多，通常是 10 倍左右。如果第 i 層的數據總大小超過第 i 層閾值限制了，會自動挑選一個文件和第 i+1 的文件合并，這里就和 LSM 樹理論一致了。合并完成之后，除了 L0 層，其他每層的數據都是有順序的，并且層與層之間也是有順序的，也就是數據完全有序。

查詢流程則很簡單，先查 MemTable 區域，然后查詢 Immutable MemTable 區域，接著從 L0 層的 SSTable 文件開始，逐層遍歷。

LSM 樹的挑戰與優化

盡管 LSM 樹在寫入性能上具有優勢，但它也面臨著讀寫放大的問題。讀寫放大是指實際的 IO 操作次數超過了用戶需求的次數，這會導致資源的浪費。例如，在查詢一個數據時，可能需要遍歷多個層級的 SSTable，增加了 IO 操作的次數。同樣，在寫入新數據時，也需要與其他 SSTable 進行合并排序，增加了寫入的開銷。

為了解決這個問題，LSM 樹采用了分層結構，通過分攤計算過程來減少每次壓縮操作的資源消耗，每次上一層溢出只需要將溢出的 SSTable 和下一層 SSTable 進行歸并計算。此外，每層都會構造布隆過濾器來進一步優化查詢性能，減少不必要的磁盤訪問。

總結

今天我們聊了 LSM 樹的相關知識，我們首先介紹了 LSM 樹的原理，其實 LSM 并不是樹，而是一個多層的讀寫流程，LSM 樹本身是為了解決快速寫入的問題而設計的，LSM 樹利用了磁盤的順序讀寫能力，通過多層噴泉一樣的方式寫入數據，層與層之間不斷歸并計算。

后面我們了解了 LSM 樹是如何在 LevelDB 中落地的， LevelDB 利用了 MemTable 和 ImmutableMemTable2 個內存空間來解決并發問題，而一層中的每個文件叫做 SSTable。 SSTable 內部是有序的，并且在同一層中 SSTable 彼此也是有序的。最后，我們討論了讀寫放大問題，并提出了一些可能的解決方案。