LSM 核心實現講解

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)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)O(logn)。但對查詢性能的追求也造成了 B tree 的相應缺點，即每次插入或刪除一條數據時，均需要更新索引，從而造成一次磁盤 IO。這種特性決定了 B tree 只適用於頻繁讀、較少寫的場景。如果在頻繁寫的場景下，將造成大量的磁盤 IO，從而導致性能驟降。這種應用場景在傳統的關係型數據庫中比較常見。

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

總結

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

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

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

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

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

  5. 對於大量的 segment 文件，定期在後臺執行 compaction 操作，將多個文件合併爲更大的文件，以保證查詢效率不衰減。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/GsnBpZPzizX9ODuQLT-uAg

猜你喜歡