[[421749]]

LSM tree (log-structured merge-tree) 是一種對頻繁寫操作非常友好的數據結構，同時兼顧了查詢效率。LSM tree 是許多 key-value 型或日志型數據庫所依賴的核心數據結構，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB 等。

LSM tree 之所以有效是基于以下事實：磁盤或內存的連續讀寫性能遠高于隨機讀寫性能，有時候這種差距可以達到三個數量級之高。這種現象不僅對傳統的機械硬盤成立，對 SSD 硬盤也同樣成立。如下圖：

LSM tree 在工作過程中盡可能避免隨機讀寫，充分發揮了磁盤連續讀寫的性能優勢。

SSTable

LSM tree 持久化到硬盤上之后的結構稱為 Sorted Strings Table (SSTable)。顧名思義，SSTable 保存了排序后的數據(實際上是按照 key 排序的 key-value 對)。每個 SSTable 可以包含多個存儲數據的文件，稱為 segment，每個 segment 內部都是有序的，但不同 segment 之間沒有順序關系。一個 segment 一旦生成便不再修改(immutable)。一個 SSTable 的示例如下：

可以看到，每個 segment 內部的數據都是按照 key 排序的。下面我們來介紹每個 segment 是如何生成的。

寫入數據

LSM tree 的所有寫操作均為連續寫，因此效率非常高。但由于外部數據是無序到來的，如果無腦連續寫入到 segment，顯然是不能保證順序的。對此，LSM tree 會在內存中構造一個有序數據結構(稱為 memtable)，例如紅黑樹。每條新到達的數據都插入到該紅黑樹中，從而始終保持數據有序。當寫入的數據量達到一定閾值時，將觸發紅黑樹的 flush 操作，把所有排好序的數據一次性寫入到硬盤中(該過程為連續寫)，生成一個新的 segment。而之后紅黑樹便從零開始下一輪積攢數據的過程。

讀取/查詢數據

如何從 SSTable 中查詢一條特定的數據呢?一個最簡單直接的辦法是掃描所有的 segment，直到找到所查詢的 key 為止。通常應該從最新的 segment 掃描，依次到最老的 segment，這是因為越是最近的數據越可能被用戶查詢，把最近的數據優先掃描能夠提高平均查詢速度。

當掃描某個特定的 segment 時，由于該 segment 內部的數據是有序的，因此可以使用二分查找的方式，在O(logn)的時間內得到查詢結果。但對于二分查找來說，要么一次性把數據全部讀入內存，要么在每次二分時都消耗一次磁盤 IO，當 segment 非常大時(這種情況在大數據場景下司空見慣)，這兩種情況的代價都非常高。一個簡單的優化策略是，在內存中維護一個稀疏索引(sparse index)，其結構如下圖：

稀疏索引是指將有序數據切分成(固定大小的)塊，僅對各個塊開頭的一條數據做索引。與之相對的是全量索引(dense index)，即對全部數據編制索引，其中的任意一條數據發生增刪均需要更新索引。兩者相比，全量索引的查詢效率更高，達到了理論極限值O(logn)，但寫入和刪除效率更低，因為每次數據增刪時均需要因為更新索引而消耗一次 IO 操作。通常的關系型數據庫，例如 MySQL 等，其內部采用 B tree 作為索引結構，這便是一種全量索引。

有了稀疏索引之后，可以先在索引表中使用二分查找快速定位某個 key 位于哪一小塊數據中，然后僅從磁盤中讀取這一塊數據即可獲得最終查詢結果，此時加載的數據量僅僅是整個 segment 的一小部分，因此 IO 代價較小。以上圖為例，假設我們要查詢 dollar 所對應的 value。首先在稀疏索引表中進行二分查找，定位到 dollar 應該位于 dog 和 downgrade 之間，對應的 offset 為 17208~19504。之后去磁盤中讀取該范圍內的全部數據，然后再次進行二分查找即可找到結果，或確定結果不存在。

稀疏索引極大地提高了查詢性能，然而有一種極端情況卻會造成查詢性能驟降：當要查詢的結果在 SSTable 中不存在時，我們將不得不依次掃描完所有的 segment，這是最差的一種情況。有一種稱為**布隆過濾器(bloom filter)**的數據結構天然適合解決該問題。布隆過濾器是一種空間效率極高的算法，能夠快速地檢測一條數據是否在數據集中存在。我們只需要在寫入每條數據之前先在布隆過濾器中登記一下，在查詢時即可斷定某條數據是否缺失。

布隆過濾器的內部依賴于哈希算法，當檢測某一條數據是否見過時，有一定概率出現假陽性(False Positive)，但一定不會出現假陰性(False Negative)。也就是說，當布隆過濾器認為一條數據出現過，那么該條數據很可能出現過;但如果布隆過濾器認為一條數據沒出現過，那么該條數據一定沒出現過。這種特性剛好與此處的需求相契合，即檢驗某條數據是否缺失。

文件合并(Compaction)

隨著數據的不斷積累，SSTable 將會產生越來越多的 segment，導致查詢時掃描文件的 IO 次數增多，效率降低，因此需要有一種機制來控制 segment 的數量。對此，LSM tree 會定期執行文件合并(compaction)操作，將多個 segment 合并成一個較大的 segment，隨后將舊的 segment 清理掉。由于每個 segment 內部的數據都是有序的，合并過程類似于歸并排序，效率很高，只需要O(n)的時間復雜度。

在上圖的示例中，segment 1 和 2 中都存在 key 為 dog 的數據，這時應該以最新的 segment 為準，因此合并后的值取 84 而不是 52，這實現了類似于字典/HashMap 中“覆蓋寫”的語義。

刪除數據

現在你已經了解了 LSM tree 讀寫數據的方式，那么如何刪除數據呢?如果是在內存中，刪除某塊數據通常是將它的引用指向 NULL，那么這塊內存就會被回收。但現在的情況是，數據已經存儲在硬盤中，要從一個 segment 文件中間抹除一段數據必須要覆寫其之后的所有內容，這個成本非常高。LSM tree 所采用的做法是設計一個特殊的標志位，稱為 tombstone(墓碑)，刪除一條數據就是把它的 value 置為墓碑，如下圖所示：

這個例子展示了刪除 segment 2 中的 dog 之后的效果。注意，此時 segment 1 中仍然保留著 dog 的舊數據，如果我們查詢 dog，那么應該返回空，而不是 52。因此，刪除操作的本質是覆蓋寫，而不是清除一條數據，這一點初看起來不太符合常識。墓碑會在 compact 操作中被清理掉，于是置為墓碑的數據在新的 segment 中將不復存在。

LSM tree 與 B tree 的對比

主流的關系型數據庫均以 B/B+ tree 作為其構建索引的數據結構，這是因為 B tree 提供了理論上最高的查詢效率 O(log n)。但對查詢性能的追求也造成了 B tree 的相應缺點，即每次插入或刪除一條數據時，均需要更新索引，從而造成一次磁盤 IO。這種特性決定了 B tree 只適用于頻繁讀、較少寫的場景。如果在頻繁寫的場景下，將造成大量的磁盤 IO，從而導致性能驟降。這種應用場景在傳統的關系型數據庫中比較常見。

而 LSM tree 則避免了頻繁寫場景下的磁盤 IO 開銷，盡管其查詢效率無法達到理想的 O(log n)，但依然非常快，可以接受。所以從本質上來說，LSM tree 相當于犧牲了一部分查詢性能，換取了可觀的寫入性能。這對于 key-value 型或日志型數據庫是非常重要的。

總結

LSM tree 存儲引擎的工作原理包含以下幾個要點：

寫數據時，首先將數據緩存到內存中的一個有序樹結構中(稱為 memtable)。同時觸發相關結構的更新，例如布隆過濾器、稀疏索引。

當 memtable 積累到足夠大時，會一次性寫入磁盤中，生成一個內部有序的 segment 文件。該過程為連續寫，因此效率極高。

進行查詢時，首先檢查布隆過濾器。如果布隆過濾器報告數據不存在，則直接返回不存在。否則，按照從新到老的順序依次查詢每個 segment。

在查詢每個 segment 時，首先使用二分搜索檢索對應的稀疏索引，找到數據所在的 offset 范圍。然后讀取磁盤上該范圍內的數據，再次進行二分查找并獲得結果。

對于大量的 segment 文件，定期在后臺執行 compaction 操作，將多個文件合并為更大的文件，以保證查詢效率不衰減。