作者：京東物流 劉家存

隨著數據量的增大，傳統關係型資料庫越來越不能滿足對於海量數據存儲的需求。對於分散式關係型資料庫，我們瞭解其底層存儲結構是非常重要的。本文將介紹下分散式關係型資料庫 TiDB 所採用的底層存儲結構 LSM 樹的原理。

1 LSM 樹介紹

LSM 樹（Log-Structured-Merge-Tree) 日誌結構合併樹由 Patrick O’Neil 等人在論文《The Log-Structured Merge Tree》(https://www.cs.umb.edu/~poneil/lsmtree.pdf)中提出，它實際上不是一棵樹，而是2個或者多個不同層次的樹或類似樹的結構的集合。

LSM 樹的核心特點是利用順序寫來提高寫性能，代價就是會稍微降低讀性能（讀放大），寫入量增大（寫放大）和占用空間增大（空間放大）。

LSM 樹主要被用於 NoSql 資料庫中，如 HBase、RocksDB、LevelDB 等，知名的分散式關係型資料庫 TiDB 的 kv 存儲引擎 TiKV 底層存儲就是用的上面所說的 RocksDB，也就是用的 LSM 樹。

2 LSM 樹演算法大概思路

LSM 樹由兩個或多個樹狀的結構組成。
這一節我們以兩個樹狀的結構構成的簡單的雙層 LSM 樹舉例，來簡單說下 LSM 樹大概思路，讓大家對 LSM 樹實現有個整體的認識。

原論文中的圖

2.1 數據結構

雙層 LSM 樹有一個較小的層，該層完全駐留在記憶體中，作為 C0 樹（或 C0 層），以及駐留在磁碟上的較大層，稱為 C1 樹。
儘管 C1 層駐留在磁碟上，但 C1 中經常引用的節點將保留在記憶體緩衝區中，因此C1經常引用的節點也可以被視為記憶體駐留節點。

2.2 寫入

寫入時，首先將記錄行寫入順序日誌文件 WAL 中，然後再將此記錄行的索引項插入到記憶體駐留的 C0 樹中，然後通過非同步任務及時遷移到磁碟上的 C1 樹中。

2.3 讀取

任何搜索索引項將首先在 C0 中查找，在 C0 中未找到，然後再在 C1 中查找。
如果存在崩潰恢復，還需要讀取恢復崩潰前未從磁碟中取出的索引項。

2.4 Compact 過程

將索引條目插入駐留在記憶體中的 C0 樹的操作沒有 I/O 成本，然而，與磁碟相比，容納 C0 組件的記憶體容量成本較高，這對其大小施加了限制。達到一定大小後，我們就需要將數據遷移到下一層。
我們需要一種有效的方法將記錄項遷移到駐留在成本較低的磁碟介質上的 C1 樹中。為了實現這一點，當插入達到或接近每一層分配的最大值的閾值大小，將進行一個滾動合併（Compact）過程，用於從 C0 樹中刪除一些連續的記錄項，並將其合併到 C1 中。
Compact 目前有兩種策略，size-tiered 策略，leveled策略，我們將在下麵的內容里詳細介紹這兩種策略。

2.5 崩潰恢復

在 C0 樹中的項遷移到駐留在磁碟上的C1樹之前，存在一定的延遲（延遲），為了保證機器崩潰後C0樹中的數據不丟失，在生成每個新的歷史記錄行時，首先將用於恢復此插入的日誌記錄寫入以常規方式創建的順序日誌文件 WAL 中，然後再寫入 C0 中。

3 LSM 樹的組成

LSM樹有三個重要組成部分，MemTable，Immutable MemTable，SSTable(Sorted String Table)，如下圖。

這張經典圖片來自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演講的PPT

這幾個組成部分分別對應 LSM 樹的不同層次，不同層級間數據轉移見下圖。這節就是介紹 LSM 樹抽象的不同層的樹狀數據結構的某個具體實現方式。

3.1 MemTable

MemTable 是在記憶體中的數據結構，用於保存最近更新的數據，會按照 Key 有序地組織這些數據。LSM 樹對於具體如何組織有序地組織數據並沒有明確的數據結構定義，例如你可以任意選擇紅黑樹、跳錶等數據結構來保證記憶體中 key 的有序。

3.2 Immutable MemTable

為了使記憶體數據持久化到磁碟時不阻塞數據的更新操作，在 MemTable 變為 SSTable 中間加了一個 Immutable MemTable。
當 MemTable 達到一定大小後，會轉化成 Immutable MemTable，並加入到 Immutable MemTable 隊列尾部，然後會有任務從 Immutable MemTable 隊列頭部取出 Immutable MemTable 並持久化磁碟里。

3.3 SSTable(Sorted String Table)

有序鍵值對集合，是 LSM 樹組在磁碟中的數據結構。
其文件結構基本思路就是先劃分為數據塊(類似於 mysql 中的頁)，然後再為數據塊建立索引，索引項放在文件末尾，並用布隆過濾器優化查找。

4 LSM 樹的 Compact 策略

當某層數據量大小達到我們預設的閾值後，我們就會通過 Compact 策略將其轉化到下一層。

在介紹 Compact 策略前，我們先想想如果讓我們自己設計 Compact 策略，對於以下幾個問題，我們該如何選擇。

1. 對於某一層的樹，我們用單個文件還是多個文件進行實現？
2. 如果是多個文件，那同一層 SSTable 的 key 範圍是有序還是重合？有序方便讀，重合方便寫。
3. 每層 SSTable 的大小以及不同層之間文件大小是否相等。
4. 每層 SSTable 的數量。如果同一層 key 範圍是重合的，則數量越多，讀的效率越低。

不同的選擇會造成不同的讀寫策略，基於以上 3 個問題，又帶來了 3 個概念：

1. 讀放大：讀取數據時實際讀取的數據量大於真正的數據量。例如在 LSM 樹中可能需要在所有層次的樹中查看當前 key 是否存在。
2. 寫放大：寫入數據時實際寫入的數據量大於真正的數據量。例如在 LSM 樹中寫入時可能觸發Compact 操作，導致實際寫入的數據量遠大於數據的大小。
3. 空間放大：數據實際占用的磁碟空間比數據的真正大小更多。LSM 樹中同一 key 在不同層次里或者同一層次的不同 SSTable 里可能會重覆。

不同的策略實際就是圍繞這三個概念之間做出權衡和取捨，我們主要介紹兩種基本策略：size-tiered 策略和 leveled 策略，這兩個策略對於以上 3 個概念做了不同的取捨。

4.1 size-tiered 策略

4.1.1 演算法

1. size-tiered 策略每層 SSTable 的大小相近。
2. 當每一層 SSTable 的數量達到 N 後，則觸發 Compact 操作合併這些 SSTable，並將合併後的結果寫入到一個更大的 SStable。
3. 新的更大的 SStable 將直接放到下一層 SStable 的隊尾。所以同一層不同 SStable key 範圍重合，查找時要從後向前掃描，且最壞情況下可能會掃描同一層所有 SStable ，這增大了讀放大的問題(之所以說增大，是因為 LSM 樹不同層之間也有讀放大問題)。

4.1.2 總結

由此可以看出 size-tiered 策略幾個特點：

1. 每層 SSTable 的數量相近。
2. 當層數達到一定數量時，最底層的單個 SSTable 的大小會變得非常大。
3. 不但不同層之間，哪怕同一層不同 SSTable 之間，key 也可能會出現重覆。空間放大比較嚴重。只有當該層的 SSTable 執行 compact 操作才會消除這些 key 的冗餘記錄。
4. 讀操作時，需要同時讀取同一層所有 SSTable ，讀放大嚴重。

4.2 leveled 策略

4.2.1 演算法

1. leveled 策略和 size-tiered 策略不同的是，它限制 SSTable 文件的大小，每一層不同 SSTable 文件 key 範圍不重疊且後面的最小 key 大於前一個文件的最大 key
2. 當每一層 SSTable 的總大小達到閾值 N 後，則觸發 Compact 操作。
3. 首先會隨機選擇一個 SSTable 合併到下層，由於下一層 key 是全局有序的，這就要求 leveled 策略 Compact 操作時需要當前 SSTable 和下一層里和當前 SSTable key 存在範圍重疊的所有 SSTable 進行合併。最壞情況下可能下一層所有 SSTable 都參與合併，這就增大了寫放大問題(之所以說增大，是因為 LSM 樹不同層之間 Compact 也有寫放大問題)。

4.2.2 總結

由此可以看出 leveled 策略幾個特點：

1. 不會出現非常大的 SSTable 文件。
2. 每一層不同 SSTable 文件 key 範圍不重疊。相對於 size-tiered 策略讀放大更小。
3. Compact 操作時，需要同時和下一層 SSTable 一起合併，寫放大嚴重。

5 LSM 樹的插入、修改、刪除

從 LSM 樹的名字，Log-Structured-Merge-Tree 日誌結構合併樹中我們大概就能知道 LSM 樹的插入、修改、刪除的方法了——順序追加而非修改(對磁碟操作而言)。

1. LSM 樹的插入、修改、刪除都是在 L0 層的樹里插入、修改、刪除一條記錄，並記錄記錄項的時間戳，由於只需要取最新的內容即可，所以不需要操作後面層次的樹。
2. 歷史的插入、修改、刪除的記錄會在每次 Compact 操作時被後面的記錄覆蓋。

6 LSM 樹的查找

1. 由於後面的操作會覆蓋前面的操作，所以查找只需從 L0 層往下查，直到查到某個 key 的記錄就可以了，之前的記錄不需要再查了。
2. 對於 size-tiered 策略，同一層 SSTable 需要從後向前遍歷，直到找到符合的索引項。
3. 在查找過程中也會使用其他一些手段進行優化，例如增加緩存、布隆過濾器等。

7 LSM 樹和 B+ 樹的比較

1. 不考慮寫日誌等操作，插入、修改、刪除一條記錄 B+ 樹需要先找到數據位置，可能需要多次磁碟 IO；LSM 樹不需要磁碟 IO，單次插入耗時短，所以其寫入的最大吞吐量是高於 B+ 樹的。
2. LSM 樹後面的 Compact 操作也會操作這條數據幾次，總的寫入量是大於 B+ 樹的，但可以通過將 Compact 操作放到業務低峰時來降低這個劣勢的影響。
3. 查找時， LSM 樹需要遍歷所有層次的樹，查找效率上要低於 B+ 樹，但 LSM 樹寫入時節省的磁碟資源占用，可以一定程度上彌補讀效率上的差距。

8 總結

LSM 樹特點：順序寫入、Compact 操作、讀、寫和空間放大。
LSM 樹適用場景：對於寫操作吞吐量要求很高、讀操作吞吐量要就較高的場景，目前主要在 NoSql 資料庫中用的比較多。