我們將深入探討日志結構合并樹，也稱為LSM Tree：這是許多高度可擴展的NoSQL分布式鍵值型數據庫的基礎數據結構，例如Amazon的DynamoDB、Cassandra和ScyllaDB。這些數據庫的設計被認為支持比傳統關系數據庫更高的寫入速率。我們將看到LSM Tree如何使它們能夠實現宣稱的寫入速度，并以及如何促進讀取。

在開始之前

首先，我們需要一些背景信息。典型的數據庫管理系統(DBMS)由多個組件組成，每個組件負責處理數據存儲、檢索和管理的不同方面。

其中一個組件是存儲引擎，它負責提供可靠的接口，以從/向底層存儲設備高效讀寫數據。

存儲引擎的性能在選擇數據庫時非常重要，因為它是最接近正在使用的存儲設備的組件。

用于實現存儲引擎的兩種流行數據結構是B+樹和LSM樹。在本文中，我們將覆蓋LSM樹。

LSM Tree 深度解析

LSM Tree并不是一個完整的單一數據結構，而是結合了多個數據結構，利用存儲層次結構中不同存儲設備的響應時間。

由于是追加寫入，它提供了高寫入速率，同時通過在RAM中維護的索引仍然提供低成本的讀取。

與基于B+樹的存儲引擎相比，它執行原地更新，但在LSM Tree中沒有原地更新，這有助于避免隨機I/O。在我們深入研究之前，讓我們詳細討論在寫入密集工作負載中使用基于B+樹的數據庫存儲引擎的缺點。

大多數傳統的關系型/SQL數據庫使用基于B+樹的存儲引擎。在這些數據庫中，每次寫入都必須執行不僅是記錄的請求寫入，還必須執行對B+樹不變式的任何所需的元數據更新，這涉及在B+樹結構中移動/拆分/合并節點。

解剖LSM Tree

LSM Trees凸顯了磁盤上的隨機I/O存在大量寫入開銷的問題，而順序寫入則更快，因為磁盤寫入頭緊挨著上一個記錄的位置，且旋轉和尋道延遲最小。

“Log-structured”這個術語意味著數據結構像追加日志一樣被組織。

“merge”這個術語指的是用于管理結構中數據的算法。其名稱中的“tree”一詞來自于數據被組織成多個級別，類似于典型計算機中存儲層次結構中的設備，其中頂層設備包含較小的數據子集，訪問速度更快，而較低級別包含較大的數據段，訪問速度較慢。

在最基本的設置中，LSM Tree由兩個數據結構組成，充分利用RAM和持久磁盤的優勢：LSM樹被優化用于快速寫入。

1. Memtable

LSM樹的工作方式不同。寫入在內存中按到達的順序進行批處理，存儲在稱為Mem table的結構中。Mem table按對象-鍵對進行排序，通常實現為平衡二叉樹。

當Mem table達到一定大小時，它將被刷新到磁盤作為不可變的有序字符串表。一個SS table以有序序列存儲鍵值對。這些寫入都是順序I/O，在任何存儲介質上都很快。

2.SS Tables

新的SS表成為LSM樹的最新段。隨著更多數據的到來，越來越多的這些不可變SS表被創建并添加到LSM樹中，每個都代表傳入更改的小時間段。

由于SS表是不可變的，對現有對象鍵的更新不會覆蓋舊的SS表。相反，將在最新的SS表中添加新條目，這將取代舊的SS表中對象鍵的任何條目。

LSM Tree上的操作

1.刪除

刪除對象需要特殊處理，因為我們無法標記SS表中的任何內容為已刪除。

為執行刪除操作，它會在對象鍵的最新SS表上添加一個稱為墓碑的標記。當我們在讀取時遇到墓碑時，我們知道該對象已被刪除。是的，刪除會占用額外的空間。

2. 讀取

為了響應讀取請求，我們首先嘗試在Mem table中查找鍵，然后在LSM樹中的最新訪問表中查找，然后在下一個SS表中查找，依此類推。由于SS表是有序的，查找可以有效進行。

SS表的積累產生了兩個問題。隨著SS表數量的增加，查找鍵將需要越來越長的時間。隨著SS表的累積，隨著鍵的更新和墓碑的添加，舊條目變得越來越多。這些會占用寶貴的磁盤空間。

為了解決這些問題，后臺運行定期的合并和壓縮過程，以合并SS表并丟棄過時或已刪除的值。這可以回收磁盤空間并限制讀取時必須查找的SS表數量。由于SS表是有序的，因此這個合并和壓縮過程是簡單而高效的。該方法類似于歸并排序算法的合并階段。

3. 寫入

LSM樹會在內存中緩沖傳入的寫入。當緩沖區填滿時，我們對其進行排序并將其刷新到磁盤作為不可變的SS表。

隨著更多的緩沖區刷新到磁盤，這會為讀取創建問題，因為每個讀取都必須搜索這些SS表以執行查找。

為了限制每個讀取時必須搜索的SS表數量，LSM樹會在后臺合并SS表并進行壓縮。

4. 壓縮策略

讓我們更仔細地看看壓縮過程。當合并SS表時，它們會被組織成級別。這是LSM樹名稱中“樹”的部分發揮作用的地方。

有不同的策略來確定何時以及如何合并和壓縮SS表。有兩種廣泛的策略：大小分層壓縮和級別壓縮。大小分層壓縮針對寫入吞吐量進行了優化，而級別壓縮則更多地針對讀取進行了優化。

壓縮可以使SS表數量保持在可管理的水平。SS表被組織成級別，每個級別的SS表隨著來自上一級別的SS表的出現而呈指數增長。

壓縮會消耗大量I/O。錯誤調整的壓縮可能會使系統餓死，并減慢讀取和寫入速度。

LSM Tree 的增強

最后，讓我們了解一些生產系統中LSM樹的標準優化。

為了查找鍵，它會在每個級別的SS表上執行搜索。盡管在排序數據上搜索很快，但在所有這些SS表上進行搜索會消耗大量I/O。

許多系統在內存中保留一個摘要表，其中包含每個級別的每個磁盤塊的最小/最大范圍。這允許系統跳過那些鍵不在范圍內的磁盤塊上的搜索，從而節省大量隨機I/O。

另一個可能昂貴的問題是查找不存在的鍵。這將需要查找所有級別的所有合格塊。大多數系統在每個級別上保留了一個Bloom過濾器。

Bloom過濾器是一種空間高效的數據結構，如果鍵不存在，則返回確定的“不存在”，如果鍵可能存在，則返回“可能存在”。這允許系統跳過一個級別，如果鍵在那里不存在，從而大大減少了需要的隨機I/O數量。

LSM Tree 的缺點

• LSM樹的主要缺點是壓縮的成本，它影響讀取和寫入性能。由于涉及數據的壓縮/解壓縮、復制和比較，壓縮是LSM樹中資源占用最高的階段。
• 所選的壓縮策略必須試圖最小化讀取放大、寫入放大和空間放大。
• LSM樹的另一個缺點是執行讀取在最壞情況下會變慢。由于是追加方式，讀取必須在最低級別的SSTable中進行搜索。這涉及到尋找的文件I/O，這會導致讀取變慢。