LSM-Tree & SSD

來自專欄長日將盡4 人贊了文章

近年來，以LevelDB和Rocksdb為代表的LSM（Log-Structured Merge-Tree）存儲引擎憑藉其優異的寫性能及不俗的讀性能成為眾多分散式組件的存儲基石。

1. LevelDB的架構設計

LSM-Tree全名：Log-Structured Merge-Tree。LevelDB採用LSM-Tree存儲引擎，整體架構如下：

當用戶向leveldb中插入一組key-value的時候，key-value首先被保存進LogFile，接下來這組key-value被插入到（有序的）MemTable中，MemTable中保存著最近的更新。當LogFile的大小達到一定容量(4M for example)的，這個MemTable就會被轉化為一個只讀的ImmutableMemTable。同時，新的MemTable和LogFile將會被創建，一個後台進程會把生成的ImmutableMemTable保存在磁碟上，成為一個有序的SSTable (Level-0)。key的刪除是一個特例，在刪除操作中，value會被寫入一個特殊的值，將該key標記為已刪除。

2. LevelDB的Compaction

leveldb compaction

Compactions

當level0中的文件(SSTable，默認大小1MB)到達了一定的數量後(默認4個), 每個level0中的文件都和level1中的所有有重疊(包含有相同的rowkey)的文件生成一系列新的SSTable文件.

在level0中的文件，可能會有重疊(指除了timestamp以外，有相同的key)，但是在其他層的文件之間是不會有重疊的(稱之為互斥),這是由compact的過程決定的。

對於任意的levelL(L>=1), 如果該層所有文件的大小的總和超過了10^L MB, 將會一個levelL中的文件(選擇的策略下面講)，將和所有Level(L+1)中的有重疊的sorted table進行compact, 生成一系列level(L+1)中的文件。這樣的操作將會產生這樣一種效果，就是用批量讀寫操作(input SSTable，output SSTable)將更新的數據從低level向高level轉移。因此對於一條記錄而言，這是一個逐漸下沉的過程。

從L層選擇一個文件與L+1層中所有重疊的文件進行compact的時候，涉及到一個選擇的策略問題。LevelDB採用的策略是這樣的，由於進行compact的SSTable都是有序的，所以很容易找到一個SSTable的最後一行數據。將L層中上次進行compact的SSTable的最後一個rowkey記錄下來，再此選擇的時候，將會選擇從上次rowkey以後開始的最近的那個SSTable文件進行compact(因為同層的文件之間是嚴格互斥的). 如果沒有這個文件就在key空間上循環重新來找。

Level(L+1)中的整個文件將會作為compaction的輸入，compaction完成以後，這個文件將會被刪除。Compaction過程將選擇的file的內容歸併在一起，然後產生一系列L+1層文件。(當歸併完後寫入磁碟的時候，如果文件大小超過2MB，就轉向下一個文件寫。如果當前寫的文件與L+2層的10個文件以上產生了重疊，同樣轉向下一個文件進行寫，這樣就保證了L+1層在與L+2層compact的時候，不會涉及過多的數據。)舊的文件將在歸併完成後被刪除。

Compaction的核心功能就是丟棄覆蓋數據，刪除標記為刪除的數據，以及清除過期數據。具體的compact的過程如下：

3. LevelDB的優缺點

LSM Tree是一種對寫優化的系統，將隨機寫轉化為順序寫，從而獲得非常優秀的寫性能，但一定的LSM也損失了一些東西作為交換，這個損失就是寫放大，即實際的磁碟寫跟用戶請求寫的比值，就是說：

LSM Tree 將隨機寫轉化為順序寫，而作為代價帶來了大量的重複寫入。

而在傳統的機械盤上順序寫的性能遠遠好於其隨機寫性能，這個性能差異接近一千倍。

通常Compaction涉及到三個放大因子，Compaction需要在三者之間做取捨。

  • 寫放大Write Amplification : 寫放大，假設每秒寫入10MB的數據，但觀察到硬碟的寫入是30MB/s，那麼寫放大就是3。寫分為立即寫和延遲寫，比如redo log是立即寫，傳統基於B-Tree資料庫刷臟頁和LSM Compaction是延遲寫。redo log使用direct IO寫時至少以512位元組對齊，假如log記錄為100位元組，磁碟需要寫入512位元組，寫放大為5。
  • 讀放大Read Amplification : 讀放大，對應於一個簡單query需要讀取硬碟的次數。比如一個簡單query讀取了5個頁面，發生了5次IO，那麼讀放大就是 5。假如B-Tree的非葉子節點都緩存在內存中，point read-amp 為1，一次磁碟讀取就可以獲取到Leaf Block；short range read-amp 為1~2，1~2次磁碟讀取可以獲取到所需的Leaf Block。
  • 空間放大Space Amplification : 空間放大，假設我需要存儲10MB數據，但實際硬碟佔用了30MB，那麼空間放大就是3。有比較多的因素會影響空間放大，比如在Compaction過程中需要臨時存儲空間，空間碎片，Block中有效數據的比例小，舊版本數據未及時刪除等等。

RocksDB放大係數高達42倍，LevelDB也高達27倍。寫放大意味著更多的讀寫，會造成系統性能波動，比如對SSD來說會加速壽命衰減，從成本角度說也更加耗電，採用更優的避免寫放大的演算法可以使用成本更低廉的SSD，寫放大還影響資料庫系統的持續寫入的帶寬，假如磁碟帶寬為500M/s，寫放大為10，那麼資料庫持續寫入的的最大帶寬為50M/s，所以解決寫放大就成了一個很重要的問題。

4. LevelDB & SSD - WiscKey: Separating Keys from Values in SSD-conscious Storage

近些年來，新興的SSD磁碟相對具有較高的隨機寫能力，與順序寫的差距本身只有十倍左右，並且還可以通過並行IO進一步提升，因此這種交換就顯得有些得不償失。同時，由於反覆的寫入會帶來SSD的磨損從而降低壽命。

設計思路：

  • First, WiscKey separates keys from values, keeping only keys in theLSM-tree and the values in a separate log file.
  • Second,to deal with unsorted values (which necessitate random access during range queries), WiscKey uses the parallel random-read characteristic of SSD devices.
  • Third, WiscKey utilizes unique crash-consistency and garbage-collection techniques to efficiently manage the value log.
  • Finally, WiscKey optimizes performance by removing the LSM-tree log without sacrificing consistency, thusreducing system-call overhead from small writes.

優點：

  • 數據只寫日誌Value Log，避免了數據日誌和sstable的雙寫，提高IO效率；
  • 只將元數據寫入LSM-tree，雖然也會存在IO放大，但是由於數據量很小，總體的放大效果明顯降低。
  • 假設對象的元數據為16B，對象數據大小為1KB，按照LSM的放大係數為10來計算，採用WiscKey設計，寫入的總體放大率約為： (16 * 10 + 1024)/(1024 + 16) = 1.14
  • 對於讀操作，由於LSM-tree的數據量已經顯著減少，總的sstable文件數量也相應減少，元數據的查找過程也會加快，只是不太好評估這個效率。而且，LSM-tree數據量的減少還能帶來另外一個好處：可以盡量多的緩存元數據，進一步提高元數據檢索的效率。

WiscKey的幾個問題：

  • 垃圾回收

LevelDB等之類LSM-tree的存儲系統對於對象的刪除只是追加刪除標記，延期至sstable compaction的時候回收那些無效數據。

對於WiscKey的設計，由於元數據和數據分離，回收涉及兩個方面：元數據的回收和數據回收。

元數據回收與LevelDB類似，無需贅言。對象的數據位於Value Log區，如何回收Value Log區的無效對象呢？

如上圖所示，WiscKey設計了一種比較巧妙的思路：log區有兩個指針 head和tail。head指向當前新數據待寫入的位置，而tail則指向當前待回收的位置。

當觸發垃圾回收時，從tail位置讀取一條記錄，並從元數據判斷其是否已經被刪除：

  • 如果是，則tail向前移動至下一條記錄；
  • 如果不是，則將該記錄寫入至head位置，接下來再將tail移動至下一條記錄。

當然，為了避免垃圾回收過程不會因為異常導致數據丟失，會將head和tail信息持久化，當然，最好的地方便是LSM-tree內了。

當然，由於垃圾回收涉及IO（先讀後寫），因此不建議太頻繁，只有在刪除操作頻率比較高時才觸發該操作。

  • 數據一致性

因為數據和元數據分離存儲，因此，勢必存在數據不一致性，如數據寫入成功但元數據寫入失敗，或者相反。

如果數據存在，但是元數據不存在，那在後續的垃圾回收時數據會被清理。

如果元數據存在，那麼接下來還需要驗證數據有效性。驗證的方法也比較多，如checksum、magic等。如果驗證失敗，那麼會將元數據清除。

  • 數據讀優化

由於數據和元數據分離，數據的讀取先是從LSM-tree讀取元數據，然後再根據位置從Value Log中讀取數據。這樣做的劣勢是會產生隨機IO。

雖然SSD對隨機IO性能有較大的提升，但是較小的隨機IO依然會對性能產生較大影響。但是SSD也有個特性就是可並行的隨機IO也會充分發揮其性能，如下圖：

可以看到，在32個線程並發時，16KB的隨機IO就基本快達到了SSD的帶寬上線。

考慮到SSD的這種特性，WiscKey對range query進行了並發讀的優化，具體的做法是：

  1. 對於range query，同時取出多個key的元數據信息<key, address>
  2. 將這些<key,address>信息放入隊列，並喚醒預讀線程（默認32個）
  3. 預讀線程開始讀數據。

參考鏈接：

google/leveldb?

github.com圖標https://github.com/facebook/rocksdb/wiki/Leveled-Compaction?

github.com圖標一文帶你了解 LSM Compaction?

juejin.im

LSM upon SSD?

catkang.github.io圖標https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf?

www.usenix.org


推薦閱讀：

查看原文 >>
相关文章