聊聊 LSM Tree 強悍的設計

什麼是 LSM Tree ？

LSM Tree 全名：Log Structured Merge Tree ，是一種在機械盤時代大放異彩的存儲架構設計。LSM Tree 是一個把順序寫發揮到極致的設計架構。它的核心之一就是 log 文件。筆者以幾個問答來看下它的設計思想：

問題一：LSM Tree 存儲引擎到底是什麼？

不就是一個 key/value 存儲引擎嘛。

問題二：用戶寫是怎麼一個流程？

用戶遞交數據流程分爲兩步：寫 log 文件，修改內存。所以會看到，寫的流程是非常簡單的，用戶的時延正常情況下就只包含這兩步。

問題三：用戶的刪是怎麼一個流程？

LSM Tree 爲了極致的寫性能把所有的更新操作都化作順序寫。也就是說，刪除也是寫入。往存儲裏面寫一條帶刪除標記的記錄，而不是直接更新原來的數據。

問題四：這是一個持久化的存儲嗎？能保證掉電不丟數據嗎？

是持久化的，因爲 log 持久化了嘛。掉電不會丟數據，因爲可以從 log 文件中恢復出來。恢復很簡單，其實就是遍歷 log 文件，然後解析出來就好。

那既然說到解析 log 文件，那麼問題又來了，log 文件越大解析時間會越長，無限制增長這個是無法忍受的。

問題五：log 文件本身是不具備查找功能的，那怎麼辦？

log 文件其實是一種有時間順序的文件，新數據不斷的往後 append 寫入，這種結構利於實現順序寫。但是從用戶 key/value 來講是 log 的結構是一種無序的結構，它的查找效率非常低。所以，自然而然，LSM 的架構裏就需要引入一種新型的有序的數據結構，這個就是 sst 文件（ 全名：sorted string  table ）。

所以，看到了，持久化的 log 數據向有序的 sst 文件轉變是 LSM 的一個核心的流程。

劃重點：sst 爲有序的結構。

問題六：爲什麼 sst 文件經常很多個？

log 文件轉變到 sst 文件是持續不斷髮生的。所以，很自然的，所以，系統中不會只有一個不斷變大 sst 文件。因爲一個龐大的空間這種查找效率會很低，並且每次重建一個有序的 sst 文件的開銷會很大。

所以，在 LSM 的實踐中，是劃分了很多個有序的空間（sst 文件），每個文件內部又按照 block 劃分，block 內部又按照 restart point 劃分。

問題七：冗餘或被刪除的空間怎麼釋放？

把有效的數據從 sst 文件中讀出來（刪除或者被覆蓋的舊數據丟棄）寫到新的文件，然後修改指向關係，然後把舊的文件刪掉。這個過程叫做 compact ，compact 是 LSM 設計中另一個核心流程。

LSM Tree 的設計思想？

存儲的核心是讀寫，針對讀寫有不同的優化手段，比如預讀，緩存，批量，併發，聚合等等。但是優化讀和優化寫能採用的手段其實不同，在機械盤時代，機械盤一定是瓶頸，它的隨機性能極差，順序的性能還能將就。

如果要優化 IO 讀，有非常多的優化策略，比如使用多層緩存，CPU Cache，內存，SSD 等等，也可以採用豐富多彩的查詢組織結構，比如各種平衡樹型結構，提高讀的效率。

但是，對於寫，它一定是受限於磁盤的瓶頸。因爲寫的流程，數據落盤纔算完。所以，對於寫的優化手段非常有限，無論用什麼手段，一定繞不過一點：保持順序，因爲只有這樣才能壓榨出機械盤的性能。在寫保持順序的基礎上，纔去考慮加上其他的優化手段，比如批量，聚合等操作。

這正是 LSM Tree 的設計思想，考慮極致的提升寫的性能，讀的性能則靠其他的手段解決。

下面介紹一些具體的 LSM Tree 項目的優秀實現。

LSM Tree 的架構

先聲明一下，下面的架構設計就假定按照 leveldb 的實現介紹，雖然 rocksdb 也是 LSM 的實現但是加了很多複雜特性，介紹起來還挺麻煩的。

 1   整體架構

先看看 LSM 的架構裏有哪些東西吧，我們一個個說說：

  1. CURRENT 是個文本文件，裏面存的是一個文件名，記錄當前可用的 MANIFEST 文件；

  2. MANIFEST 是一個二進制文件，裏面存儲的是整個集羣的元數據；

  3. log 文件則是 wal 文件，是承接用戶寫 IO 的文件，這個文件的寫性能直接關聯用戶的寫性能；

  4. Memtable 和 Immutable Memtable 是內存結構，一般實現爲一個具備查詢效率的數據結構，比如跳錶結構；

  5. ssttable 文件是內部生成的文件，每個文件都是按照 key 排序的文件。sst 內容格式都是一樣的，但是大小不一定；

  6. Memtable（還有 Immutable Memtable）和 sstable 都是需要承接用戶讀 IO ，所以這兩個裏面都有大量的提升查詢效率的手段；

從數據的格式轉變來講：

  1. log 的數據和 memtable 的數據是對應起來的（同一份數據），log 的數據結構本質是無序的，所以必須依賴於 memtable 的查詢效率；

  2. log 和 memtable 的這份數據下一步的去路就是 sstable 文件嘍，這些個 sstable 文件屬於 Level 0 ；

  3. Level 0 的 sstable 文件的去路是更底層 Level 的 sstable 文件嘍，小的合併成大的，不斷的往下沉嘍；

思考一個小問題：log 存儲的數據和 memtable 存儲的數據量一般是一樣大的？爲什麼？

log 是時間上有序但是內容上無序的格式，它上面的數據就只能依賴於 memtable 來提高查詢效率。換句話說，它兩就是一份數據，自然一樣大。

 2   寫的流程

看了整體架構之後，簡單看一眼用戶的數據怎麼存到系統的。步驟只有兩步：

  1. 數據先寫 log 文件；

  2. 數據再插入 memtable 結構中；

就這樣，用戶的寫流程就算完了。由於 log 是持久化的，所以能確保數據不丟。這是對寫流程的極致優化，只有一個寫 log 的 io 消耗，並且是永遠的 append 寫入，簡直是最理想的寫流程。

 3   讀的流程

數據讀的流程就略顯複雜了，因爲數據的範圍太大了，那麼多 sst 文件，那麼多 key 的範圍，可得好好查一查。當然了，先從 memtable 開始，查不到就一步步往底層查，也就是到 Level 0，再到 Level 1，Level 2 等等。這裏耗費的 IO 次數就不好說了，讀的性能遠比寫要差多了。

既然聊到這裏，大家都知道 sst 的讀性能很差，那咋辦？

加 “索引” 嘍。 和數據庫的索引效果類似，都是爲了提高讀和查詢效率的方法。所以，你仔細看會發現，在 leveldb，rocksdb 的實現離，有大量的索引結構。比如：

  1. leveldb 把整個 sst 文件劃分成一個個 block 小段，然後在 sst 尾端都有一個 index block，用來索引數據塊。這樣就能快速定位到 key 在哪一個 block 裏；

  2. sst 文件中還有個 bloom filter 的小塊，布隆過濾器嘍，又給讀提升了一點性能；

  3. 每個 block 裏面呢，還有個 restart point 的數組，也能提高讀性能；

比如，sst 的圖示如下：

整體設計就是把 sst 切成一個個有序的小塊，極大的提高查詢的效率。每一個 block 裏面又有按照 restart point 數組劃分：

其實，還有很多講究哦，這就不提了，太多了，很多都是爲了查詢效率。

 4   compact 的流程

leveldb 的 compact 分爲兩種：

  1. minor compact ：這個是 memtable 到 Level 0 的轉變；

  2. major compact ：這個是 Level 0 到底層或者底下的 Level 的 sstable 的相互轉變；

這裏值得提一點的是，sstable 每個都是有序的。但是呢，Level 0 的文件之間可能是有範圍交叉的，但是 Level 0 之下的 sstable 文件則絕對沒有交叉。正因如此，Level 0 的文件個數就不能太多，不然會影響查詢效率（因爲相互覆蓋嘛，所以每一個都要查的）。

爲什麼會這樣呢？

因爲 Level 0 的文件是直接來源於 memtable，而沒有去做合併。

優秀的開源實現

 1   Leveldb

leveldb 是谷歌開源的一個 key/value 存儲引擎，github 地址：https://github.com/google/leveldb 。由大佬 Sanjay Ghemawat 和 Jeff Dean 開發並開源。整個項目 c++ 實現，代碼精緻優雅，值得學習。

 2   rocksdb

rocksdb 是 facebook 開源的一個 key/value 存儲引擎，github 地址：https://github.com/facebook/rocksdb 。是基於 leveldb 項目的優化實現，適配 facebook 數據庫團隊的實際場景，特性要比 leveldb 多。整個項目 c++ 實現，代碼實現也非常優秀，值得學習。

 3   goleveldb

考慮到奇伢的讀者很多都是 gopher ，那自然要推薦一個 golang 的版本，就是 goleveldb ，github 地址：https://github.com/syndtr/goleveldb ，這個項目實現的更小巧，值得學習推薦。

如果說，你是個 gopher，並且對 LSM Tree 感興趣，那麼完全可以去擼一擼 goleveldb 的源碼。只要擼懂一個，那以後再深入就得心應手了。

 4   更好的學習選擇？用 Python 解析 LSM ？

其實，還有一個好選擇，奇伢 fork 了 goleveldb ，會不定期更新一些代碼註釋，感興趣的也可以看下，Github 地址：https://github.com/liqingqiya/readcode-goleveldb-master。

筆者在理解了 LSM 的結構之後，用 Python 腳本解析了一把 manifest 和 sst 文件，獲益匪淺。貼上幾個 python 解析 leveldb 的實例：

當你從不同的角度去看到存儲，可以獲得更深入的理解。比如，從 python、golang 兩個角度來看數據。

比如，在 go 裏面寫入一個 uint64 的整型到文件，如下：

binary.BigEndian.PutUint64(buf, 0x123456789)

這個編碼出來就是：[0x00, 0x00, 0x00, 0x01, 0x23, 0x45, 0x67, 0x89] 這 8 個字節，然後把這個 []byte 數組寫到文件即可。文件裏是這樣的：

0x00, 0x00, 0x00, 0x01, 0x23, 0x45, 0x67, 0x89

那怎麼用 python 讀出來呢？

讀出來也是一個字節數組，怎麼轉化成 uint64 的類型呢？是這樣的：

struct.unpack(">Q", buf)

劃重點：只要是涉及到數據傳輸的場景，字節數組的形式纔是通用的形式。比如內存到磁盤，內存到網絡等等，都是轉成字節數組的形式，然後在別的地方按照特定規則構建出來就是無損的。

這裏舉這個例子，也只是想說明一點，LSM Tree 是一種有存儲思想的架構設計，而不是跟具體的語言綁定的，一通百通。

爲什麼越來越多 “唱衰” LSM 的聲音呢？

歸根結底還是硬件發展起來了。在原先的機械盤（ HDD ）時代，leveldb/rocksdb 的最佳實踐就是一個磁盤只有一個寫入源（ wal ），所有的寫請求都由這一個線程遞交。這個是合理的，因爲 HDD 最好的優化就是順序化，並且一個線程串行遞交請求也足以把 HDD 跑滿。

但是自從 SSD 這種介質普及之後，一切都變了，單線程串行遞交請求已經跑不滿硬件了，比如 pcie 盤的通道就非常多，要併發全力壓才能壓的滿。還有就是 SSD 盤隨機性能太好了，單就性能數據來講和順序的差不多。那這個時候 LSM Tree 爲了順序化而做的複雜的東西可能就顯得優先多餘了，反倒讓系統變得複雜。

劃重點：SSD 多通道併發、超高的隨機性能是變革的核心因素。

那存儲引擎的架構會怎麼演進呢？

演進方向筆者也不確定。不過有一篇很出名的 FAST 上的論文 ：《WiscKey: Separating Keys from Values in SSD-Conscious Storage》就討論了在 SSD 時代，LSM 架構的優化思路。並且立馬就有開源的實現跟進了這個思路，比如 go 的 badger ，rocksdb 本身也有個集成了 BlobDB 的實驗版本。

但實話說，LSM Tree 的架構會持續的優化，但會長時間持續存在，因爲並不是所有場景都要用 SSD ，並且它不便宜。

總結

  1. LSM Tree 是把寫性能優化到極致的結構，當然了，這個極致的考慮就在於：順序 IO、批量操作；

  2. 當順序並不是性能的關鍵因素的時候，LSM Tree 的架構就有點冗餘。這個想想最近不斷出現的針對 SSD 盤的優化思路就知道了；

  3. LSM Tree 的架構中沒有覆蓋寫，log 永遠 append，sst 也是讀舊的寫新的。CURRENT，MANIFEST 也是先寫臨時文件，最後 rename 一下。所以 LSM Tree 的安全、一致性就得到了保證；

  4. LSM 犧牲了的讀性能就靠各種 “索引” 結構、各種 cache 來解決；

  5. compact 有兩種：minor，major compact 。minor compact 是有序的 mem 數據（對應無序的 log 文件）到 sst 的轉變。major compact 是 sst 內部之間的轉變；

  6. 在 SSD 沒出來之前，寫的有效優化手段只有順序 + 批量，讀的優化手段千奇百怪，從 LSM 的實現就可以窺見一二；

後記

今天聊聊 LSM Tree 的架構，分享一些設計思考，希望能幫到大家。點贊、在看 是對奇伢最大的支持。

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

猜你喜歡