今天我們聊聊 LSM 樹(shù)?？赡苓@是你第一次聽(tīng)說(shuō) LSM 樹(shù)，但 LSM 樹(shù)其實(shí)已經(jīng)是我們的老朋友了，大多數(shù) NoSQL 如 HBase、LevelDB、Cassandra、RocksDB 等底層都有 LSM 樹(shù)的身影。今天我們聊聊 LSM 樹(shù)的理論、落地實(shí)踐以及它的缺陷。

LSM 樹(shù)的起源

LSM 樹(shù)的概念源自一篇論文《The Log-Structured Merge Tree》，其名稱直接反映了其核心特性：日志結(jié)構(gòu)化和合并操作。日志結(jié)構(gòu)化意味著數(shù)據(jù)以追加的方式寫(xiě)入，類似于應(yīng)用程序的日志輸出，這種方式的優(yōu)勢(shì)在于其高效性，因?yàn)樽芳硬僮魍ǔ１入S機(jī)寫(xiě)入要快得多。

在之前關(guān)于 Kafka 的討論中，我們已經(jīng)了解到日志追加方式的優(yōu)勢(shì)。LSM 樹(shù)的另一個(gè)關(guān)鍵特性是“合并”，即通過(guò)合并多個(gè)分散的日志片段來(lái)優(yōu)化存儲(chǔ)和訪問(wèn)效率。

LSM 樹(shù)是為 NoSQL 存儲(chǔ)系統(tǒng)而生的，NoSQL 基本都是 key-value 結(jié)構(gòu)，因此最主要的功能只有兩個(gè)：put 和 get。put：寫(xiě)入一個(gè) key-value；get：給定一個(gè) key 返回 Value。除此之外 LSM 還提供了排序能力，比如在 HBase 中，默認(rèn)就是按照字典順序排序的，因此 HBase 可以 scan 某一個(gè)區(qū)間段的數(shù)據(jù)，比如我要查詢某個(gè)用戶的訂單列表并按下單時(shí)間倒序排列，就很適合用 HBase 來(lái)存儲(chǔ)，這得益于 LSM 的支持。

LSM 樹(shù)的架構(gòu)與優(yōu)勢(shì)

LSM 樹(shù)的優(yōu)點(diǎn)就是寫(xiě)入速度快，寫(xiě)入快的秘密在于 LSM 樹(shù)利用了磁盤(pán)的順序?qū)懀@使得 NoSQL 的性能優(yōu)于關(guān)系型數(shù)據(jù)庫(kù)。

下圖是 LSM 樹(shù)的邏輯示意圖，LSM 樹(shù)是一個(gè)多層結(jié)構(gòu)，自上而下存儲(chǔ)的數(shù)據(jù)越來(lái)越多。最上層是位于內(nèi)存的 C0 層，里面存儲(chǔ)著最近寫(xiě)入的 key-value，默認(rèn)情況下這里的 key-value 是有序的，這個(gè)順序就是 key 的字典順序，并且由于數(shù)據(jù)在內(nèi)存里，所以可以方便我們?cè)鰟h改查。剩下的 C1 到 CN 層和 C0 是割裂的。因?yàn)槌?C0 層，其他層都在磁盤(pán)上，每一層都按照 key 的字典順序進(jìn)行排列。

圖片

下面我們聊聊寫(xiě)入的過(guò)程，假設(shè)一個(gè) put 操作過(guò)來(lái)了，第一步數(shù)據(jù)會(huì)進(jìn)入到最上方的 C0 層。然后 C0 層的數(shù)據(jù)越來(lái)越多，達(dá)到一定閾值后， C0 層的數(shù)據(jù)就會(huì)合并到 C1 層，這個(gè)合并過(guò)程就是大名鼎鼎的歸并排序，在這里稱作 Compaction。接下來(lái) C1 層的數(shù)據(jù)越來(lái)越多，多出來(lái)的數(shù)據(jù)會(huì) Compaction 到 C2 層，以此類推直到 CN 層。

假設(shè)有 2 個(gè)相同的 key 怎么辦呢？

比如 key “ABC”由于前面的合并已經(jīng)寫(xiě)入到 C2 層了，但是新的 put 請(qǐng)求又過(guò)來(lái)了，按這種設(shè)計(jì)，整個(gè) LSM 樹(shù)會(huì)出現(xiàn)多個(gè)“ABC”。實(shí)際上，你不用擔(dān)心這個(gè)問(wèn)題，LSM 會(huì)在 Compaction 過(guò)程中自動(dòng)刪除早期的 key。Compaction 是一個(gè)異步過(guò)程，不會(huì)影響寫(xiě)入性能。

講完了寫(xiě)入，我們?cè)僦v講查詢過(guò)程，在上面的寫(xiě)入流程中可以看到，從 C0 到 CN，數(shù)據(jù)越來(lái)越“舊”，所以查詢時(shí)也是先查 C0 層，如果沒(méi)有查到需要的數(shù)據(jù)，再查 C1 層，逐層查。這樣一來(lái)，即使 Compaction 還沒(méi)來(lái)得及刪除舊的“ABC”也沒(méi)關(guān)系，我們會(huì)先找最新的“ABC”。

你會(huì)發(fā)現(xiàn)，針對(duì) LSM 樹(shù)的一次查詢可能需要多層查詢，看上去稍慢。這種情況下 NoSQL 如何保證高性能查詢呢？這種情況下不同的 NoSQL 又針對(duì)查詢做了優(yōu)化，比如 HBase 把數(shù)據(jù)放在不同的 Region 里面，完成對(duì)數(shù)據(jù)的路由等等，針對(duì)讀的優(yōu)化和 LSM 樹(shù)無(wú)關(guān)，我在這兒就不贅述了。

總結(jié)一下，LSM 樹(shù)的結(jié)構(gòu)其實(shí)就像是多層噴泉，上一層滿了就會(huì)溢出，到下一層。

LSM 樹(shù)實(shí)踐

上面的模型是論文中的表述，我們知道理論到實(shí)踐還是有點(diǎn)距離的。比如將 C0 跟 C1 合并的過(guò)程需要一個(gè)時(shí)間，這個(gè)時(shí)候新的 put 請(qǐng)求怎么辦，會(huì)被阻塞住嗎？另外，每次都要將這么多層合并，這個(gè)過(guò)程是怎樣進(jìn)行的？這里我將以 LevelDB 為例，分享一下 LevelDB 是怎么落地 LSM 樹(shù)的。

我們先看看 LevelDB 中的 LSM 樹(shù)架構(gòu)，這個(gè)和上面的理論 LSM 樹(shù)有些區(qū)別。要理解 LevelDB 中的 LSM 樹(shù)，我們需要關(guān)注兩種文件，第一種是內(nèi)存中的 2 個(gè) MemTable，MemTable 又分為 2 塊區(qū)域，一塊是普通內(nèi)存 memtable，一塊是不可變的內(nèi)存 Immutable MemTable。另一個(gè)文件叫 SSTable，中文翻譯是“有序的字符串表”，SSTable 是按照數(shù)據(jù)的 key 進(jìn)行排序的，SSTable 位于磁盤(pán)上，一共有 7 層（L0 到 L6）。

圖片

我們來(lái)看看 put 的流程，首先將數(shù)據(jù)寫(xiě)到普通內(nèi)存 MemTable 中，當(dāng)普通內(nèi)存 MemTable 溢出，就將這個(gè)普通內(nèi)存 MemTable 轉(zhuǎn)化成為不可變內(nèi)存區(qū)域 Immutable MemTable，并再申請(qǐng)一個(gè)普通內(nèi)存 MemTable 處理新的 put 消息。這樣一來(lái)，不可變內(nèi)存區(qū)域 Immutable MemTable 就不會(huì)接收新的消息了，意味著 Immutable MemTable 可以同步磁盤(pán)了，同步的方式很簡(jiǎn)單，Immutable MemTable 會(huì)直接放到 L0 層最后一個(gè) SSTable 文件后面，并不奢求跟 L0 層的其他 SSTable 文件合并，也就是說(shuō) L0 的數(shù)據(jù)是無(wú)序的、可以冗余的。

從 L1 層開(kāi)始，每往下一層空間都會(huì)比上一層大很多，通常是 10 倍左右。如果第 i 層的數(shù)據(jù)總大小超過(guò)第 i 層閾值限制了，會(huì)自動(dòng)挑選一個(gè)文件和第 i+1 的文件合并，這里就和 LSM 樹(shù)理論一致了。合并完成之后，除了 L0 層，其他每層的數(shù)據(jù)都是有順序的，并且層與層之間也是有順序的，也就是數(shù)據(jù)完全有序。

查詢流程則很簡(jiǎn)單，先查 MemTable 區(qū)域，然后查詢 Immutable MemTable 區(qū)域，接著從 L0 層的 SSTable 文件開(kāi)始，逐層遍歷。

LSM 樹(shù)的挑戰(zhàn)與優(yōu)化

盡管 LSM 樹(shù)在寫(xiě)入性能上具有優(yōu)勢(shì)，但它也面臨著讀寫(xiě)放大的問(wèn)題。讀寫(xiě)放大是指實(shí)際的 IO 操作次數(shù)超過(guò)了用戶需求的次數(shù)，這會(huì)導(dǎo)致資源的浪費(fèi)。例如，在查詢一個(gè)數(shù)據(jù)時(shí)，可能需要遍歷多個(gè)層級(jí)的 SSTable，增加了 IO 操作的次數(shù)。同樣，在寫(xiě)入新數(shù)據(jù)時(shí)，也需要與其他 SSTable 進(jìn)行合并排序，增加了寫(xiě)入的開(kāi)銷。

為了解決這個(gè)問(wèn)題，LSM 樹(shù)采用了分層結(jié)構(gòu)，通過(guò)分?jǐn)傆?jì)算過(guò)程來(lái)減少每次壓縮操作的資源消耗，每次上一層溢出只需要將溢出的 SSTable 和下一層 SSTable 進(jìn)行歸并計(jì)算。此外，每層都會(huì)構(gòu)造布隆過(guò)濾器來(lái)進(jìn)一步優(yōu)化查詢性能，減少不必要的磁盤(pán)訪問(wèn)。

總結(jié)

今天我們聊了 LSM 樹(shù)的相關(guān)知識(shí)，我們首先介紹了 LSM 樹(shù)的原理，其實(shí) LSM 并不是樹(shù)，而是一個(gè)多層的讀寫(xiě)流程，LSM 樹(shù)本身是為了解決快速寫(xiě)入的問(wèn)題而設(shè)計(jì)的，LSM 樹(shù)利用了磁盤(pán)的順序讀寫(xiě)能力，通過(guò)多層噴泉一樣的方式寫(xiě)入數(shù)據(jù)，層與層之間不斷歸并計(jì)算。

后面我們了解了 LSM 樹(shù)是如何在 LevelDB 中落地的， LevelDB 利用了 MemTable 和 ImmutableMemTable2 個(gè)內(nèi)存空間來(lái)解決并發(fā)問(wèn)題，而一層中的每個(gè)文件叫做 SSTable。 SSTable 內(nèi)部是有序的，并且在同一層中 SSTable 彼此也是有序的。最后，我們討論了讀寫(xiě)放大問(wèn)題，并提出了一些可能的解決方案。