數(shù)據(jù)結(jié)構LSM tree核心實現(xiàn)講解

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

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

LSM tree 在工作過程中盡可能避免隨機讀寫，充分發(fā)揮了磁盤連續(xù)讀寫的性能優(yōu)勢。

SSTable

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

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

寫入數(shù)據(jù)

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

讀取/查詢數(shù)據(jù)

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

當掃描某個特定的 segment 時，由于該 segment 內(nèi)部的數(shù)據(jù)是有序的，因此可以使用二分查找的方式，在

O（logn） 的時間內(nèi)得到查詢結(jié)果。但對于二分查找來說，要么一次性把數(shù)據(jù)全部讀入內(nèi)存，要么在每次二分時都消耗一次磁盤 IO，當 segment 非常大時（這種情況在大數(shù)據(jù)場景下司空見慣），這兩種情況的代價都非常高。一個簡單的優(yōu)化策略是，在內(nèi)存中維護一個稀疏索引（sparse index），其結(jié)構如下圖：

稀疏索引是指將有序數(shù)據(jù)切分成（固定大小的）塊，僅對各個塊開頭的一條數(shù)據(jù)做索引。與之相對的是全量索引（dense index），即對全部數(shù)據(jù)編制索引，其中的任意一條數(shù)據(jù)發(fā)生增刪均需要更新索引。兩者相比，全量索引的查詢效率更高，達到了理論極限值

O（logn），但寫入和刪除效率更低，因為每次數(shù)據(jù)增刪時均需要因為更新索引而消耗一次 IO 操作。通常的關系型數(shù)據(jù)庫，例如 MySQL 等，其內(nèi)部采用 B tree 作為索引結(jié)構，這便是一種全量索引。

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

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

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

文件合并（Compaction）

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

O（n）O（n）的時間復雜度。

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

刪除數(shù)據(jù)

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

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

LSM tree 與 B tree 的對比

主流的關系型數(shù)據(jù)庫均以 B/B+ tree 作為其構建索引的數(shù)據(jù)結(jié)構，這是因為 B tree 提供了理論上最高的查詢效率 O（log n）

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

而 LSM tree 則避免了頻繁寫場景下的磁盤 IO 開銷，盡管其查詢效率無法達到理想的 O（log n）

O（logn），但依然非?？欤梢越邮?。所以從本質(zhì)上來說，LSM tree 相當于犧牲了一部分查詢性能，換取了可觀的寫入性能。這對于 key-value 型或日志型數(shù)據(jù)庫是非常重要的。

總結(jié)

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

寫數(shù)據(jù)時，首先將數(shù)據(jù)緩存到內(nèi)存中的一個有序樹結(jié)構中（稱為 memtable）。同時觸發(fā)相關結(jié)構的更新，例如布隆過濾器、稀疏索引。

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

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

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

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

責任編輯：haq