論文解讀：Differentiated Key-Value Storage Management for Balanced IO Performance

導語

LSM-Tree 作為一種為寫最佳化的資料結構，近年來隨著 LevelDB 和 RocksDB 的廣泛使用逐漸走入大家的視線。在使用 LSM-Tree 時，較大的寫放大會對系統整體的寫入效能造成影響；而 KV 分離技術雖然能夠降低寫放大，但卻會影響查詢效能。

本文將介紹發表在 ATC 2021 上的 《Differentiated Key-Value Storage Management for Balanced I/O Performance》［1］，其在現有 LSM-Tree KV 分離技術做出一系列改進，透過對 Value 排序、細粒度 KV 分離等方式，使得其能夠在不同的工作負載下都能有一個良好的效能。

背景

下圖展示了 LSM-Tree 的基本結構。LSM-Tree 在磁碟上是一個分層儲存的結構，越往下層資料量越大。當我們將一個 KV 對寫入 LSM-Tree 時，我們的寫請求首先快取至記憶體的 MemTable，MemTable 寫滿後再 Flush 到 L0 的一個 SSTable 檔案中。而寫入 SSTable 後的 KV 對則透過 Compaction 操作逐層向下移動。由於 Flush 和 Compaction 都是順序訪問磁碟的，因此其有一個較好的寫效能。

在 LSM-Tree 中，寫放大指的是寫入一個 KV 對的引起的磁碟 I/O 大小和實際 KV 對的大小之比，那麼在磁碟頻寬有限的情況下，寫放大越大，實際資料寫入的吞吐量也就越小。在 LSM-Tree 中，影響寫放大的操作主要是 Compaction，因為一次 Compaction 需要將下層 SSTable 中的 KV 對讀取出，歸併排序後再寫回同一層。假設層間大小之比為 $T$ 的 LSM-Tree，一個 KV 對平均在一層中經歷 $T$ 次 Compaction 後才會移動到下一層，因此 KV 對每經過一層寫放大就會增加 $T$。

為了減少寫放大，目前學術界的最佳化方案可以大致分為兩類：

放鬆每一層 KV 對的順序約束。之所以 Comapaction 會產生寫放大，就是因為為了保證每一層的 KV 對都是有序的，每次將上層的 SSTable 向下層移動的時候都需要重新進行一次歸併排序。因此在第一種做法放鬆每一層 SSTable 都要有序的這一限制，允許每一層存在多個 Sorted Group，這樣就不會在每次 Compaction 的時候都觸發與下層檔案的歸併排序。這種做法的缺點是犧牲了查詢的效能，因為現在在查詢時每一層都要進行多次查詢。目前一些相關的文章有 PebblesDB［2］、Dostoevsky［3］ 等。

KV 分離。在一些使用場景下，Key 和 Value 的大小相差較大，於是我們將 Value 單獨儲存在一個追加寫的 vLog 中，只在 LSM-Tree 儲存 Key 和指向 Value 的指標，這樣進行 Compaction 的時候每次都需要重新讀取和寫入的資料量就會小很多。但這種做法同樣帶來了一些新的問題：

由於 Key 和 Value 是分開儲存的，所以每次讀取一個 KV 對的時候我們需要多進行一次 I/O 來獲得 Value，影響查詢效能。此外由於 Value 是按寫入順序而不是 Key 的順序進行儲存的，因此在範圍查詢時會導致大量的隨機 I/O，範圍查詢的效能較差。

由於在 LSM-Tree 中刪除一個 Key 時不能直接刪除 vLog 中的 Value ，因此我們需要一個額外的 GC 過程來定期回收被刪除的 vLog 中的無效 value 佔用的空間。我們以 WiscKey 為例，其做法是在 GC 的時候每次選擇最舊的一個 vLog 檔案，然後把裡面的無效 Value 丟掉，把依然有效的 Value 重新 Append 到 vLog 尾部。這一過程需要重新查詢 LSM-Tree 並更新相應的 Value 指標，相比於 LSM-Tree 的刪除代價更高。

目前一些相關的文章有 WiscKey［4］、HashKV［5］ 等。

出發點

為了說明這兩類最佳化方案的效果，論文中進行了一系列實驗，用 RocksDB 和放鬆每一層 KV 對的順序約束的 PebblesDB、KV 分離的 Titan 進行對比：

在寫入效能方面，實驗中 Load 100GB 隨機資料，然後觀察寫放大和寫吞吐。可以看出，使用 KV 分離的 Titan 寫放大最小，寫吞吐最高；而 RocksDB 的寫放大最大，寫吞吐最低。可以看出，這兩類最佳化均在一定程度上提升了 LSM-Tree 的寫效能。

在查詢效能方面，左圖展示的是點查詢的吞吐，可以看到比較有意思的一點是 Titan 雖然用了 KV 分離，需要多一次 I/O 來讀取 Value，但是其點查詢效能反而是最好的，其原因是 KV 分離之後 LSM-Tree 本身較小。

右圖展示的則是範圍查詢的延遲，從圖中可以看出 RocksDB 的表現是最好的，特別是在 Value 大小較小的時候。另一方面，透過對延遲的分解，可以發現範圍查詢時主要的時間開銷在於迭代器的迭代部分。特別是對於 KV 分離的 Titan，其迭代的時候會產生大量的隨機 I/O，並且雖然每次都讀取 4K 的內容至記憶體，但是隻有一部分是有用的；而其它兩種做法，由於是按 Key 的順序進行儲存的，所以可能一次 I/O 就讀取了多個需要的 KV 對至記憶體中。

這兩組實驗說明了現有的寫放大最佳化技術雖然確實優化了寫效能，但在一定程度上犧牲了查詢效能，特別是範圍查詢，因此論文中提出了一種新設計，即 DiffKV，其透過對 Value 排序、細粒度 KV 分離等方式，能夠在無論是寫入，還是點查詢、範圍查詢時都能取得一個較好的效能。

設計

DiffKV 依然採用了 KV 分離的設計，其核心思想是 Value 將其儲存 vTree 中，vTree 採用了放鬆順序約束的方法進行管理。具體來說，vTree 的每一層由若干個 Sorted Group 組成，一個 Sorted Group 中的 Value 是按 Key 的順序儲存在 vTable 中。一開始在 Flush 的時候，生成一個 SSTable 的時候也會生成一個相應的 vTable；之後上層 vTable 中 Value 會透過 Merge 的方式往下層移動。

Compaction-triggered Merge

接下來我們看一下 Merge 操作是怎麼進行的。首先，一個 SSTable 中的 Key 所對應的 Value 可能在不同的 vTable 中，因此如果 Merge 操作是獨立進行的話，我們依然需要讀取 LSM-Tree 來判斷哪些 Value 是有效的，並且更新這些 Value 在 LSM-Tree 中的指標，代價較高。因此 DiffKV 採用了 Compaction-triggered Merge，其基本思想是在 LSM-Tree 進行 Compaction 的時候順便進行 vTree 的 Merge 操作。具體做法是，在 Compaction 的時候，將這次 Compaction 所涉及到的 Value 全部讀取出來，並 Append 到下一層，形成一個新的 Sorted Group。由於 Compaction 操作本來就要在 LSM-Tree 中重新讀取和寫入 KV 對，所以 Merge 操作就不需要額外的查詢，代價較低。由於 Merge 之後的 vTable 可能仍然含有有效的 Value ，所以這些 vTable 的空間之後由 GC 進行回收，而不是直接刪除。

但這樣做也有兩個問題：

如果每次 Compaction 都觸發一次 Merge 的話，那麼 Merge 的次數依然很高，總體代價依然較大；

其次由於 Merge 是 Append Only 的，那麼在執行一段時間後 vTree 的每一層存在很多的 Sorted Group，影響查詢效能。

針對第一個問題，文中提出了 Lazy Merge。因為 LSM 中的大部分資料都是儲存在最後幾層，這也就意味著範圍查詢的時候大多數值實際上是從 vTree 的最後兩層進行掃描得到的，所以主要是最後兩層的 Value 的有序程度決定了範圍查詢的效能，而上層 Value 的有序程度對範圍查詢的效能影響很小。因此我們選擇只在最後兩層進行 vTree 的 Merge 操作。

針對第二個問題，文中提出了 Scan-optimized Merge。DiffKV 在 Merge 的時候會檢查同一層中範圍重疊的 vTable 數量，過多時進行將這些 vTable 打上標記，以供之後 GC 時進行回收。

GC

為了進行 GC，DiffKV 在記憶體中儲存了所有 vTable 中無效 Value 的數量，如果一個 vTable 中的無效 Value 數量超過閾值，我們對 vTable 進行標記。那麼在之後的 Compaction 的過程中，如果發現一個如果 Value 處於被標記的 vTable 中，我們就會將其寫入新生成的 vTable 中，而原來的 vTable 中的 Value 就會標記為無效。如果一個 vTable 中所有的 Value 都是無效的，系統就可以安全地將其刪除。簡單來說，當一次 Merge 時，在最簡單的情況下只有上層 vTable 的 Value 會寫入新生成的 vTable 中，而標記使得處於下層的 Value 也可能會被重寫，Append 至一個新的 Sorted Group 中。

Fine-grained KV Separation

在提出了 vTree 之後，文中進一步提出了細粒度的 KV 分離，其基本思想是在 SSD 環境下，當 Value 大小足夠大時，使用最簡單的 vLog 也能有較好的範圍查詢效能，並且還能減少寫一次 WAL。因此本文將 Value 大小分為大、中、小三種，大 Value 寫入 vLog 中，中 Value 寫入 vTree 中，而小 Value 直接和 Key 一起寫入 LSM-Tree 中。

vLog 同樣需要進行 GC，因此 DiffKV 在記憶體中監控了每個 vLog 檔案的無效資料比例。GC 觸發的時候，DiffKV 選擇無效 KV 佔比最大的檔案進行回收空間。並且 DiffKV 還實現了一個簡單的冷熱分離策略，其把 MemTable Flush 時得到的 Value 寫入 Hot vLog 中，而 GC 後需要重新寫回的 Value 都寫入 Cold vLog，因為這部分 Value 都是未被新版本覆蓋的，可以認為是寫入頻次較低。

實驗

實驗在一臺記憶體大小為 16GB 的伺服器上進行，記憶體一半用於 Block Cache，其它作為系統的 Page Cache 使用。磁碟使用的是一塊 480GB 的 SATA III SSD。

LSM-Tree 的配置如下，MemTable 大小為 64MB，第一層大小為 64MB，SSTable 大小為 16MB，vTable 大小為 8MB，然後小、中、大 Value 的閾值分別為 128B 和 8KB。此外 Titan 的配置有幾種，NO-GC 表示完全不進行 GC，效能最好，但是空間浪費最嚴重；BG-GC 表示由後臺執行緒進行 GC；FG-GC 同樣由後臺執行緒進行 GC，只不過當空間浪費過大時 FG-GC 會阻塞前臺的寫入操作。

文中測試使用的 Workload 中，Key 的大小是 24B，Value 的平均大小是 1KB，符合 Pareto 分佈；讀寫熱點的分佈是 Zipf 分佈。測試時先載入 100GB 的資料，然後分別執行 Insert、Update、Read 和 Scan 操作。

結果如圖所示，分別展示了其不同操作的吞吐、延遲。可以看出，DiffKV 在所有不同的操作型別中都有較好的效能。而透過最後一張圖可以看出，DiffKV 也保持了較小的空間放大。

此外，論文還進行了在 YCSB 下的實驗，具體結果可以閱讀論文相關章節。

結語：

我們知道，目前的硬體下基本上都是順序訪問的效能要優於隨機訪問。因此對於一個數據結構來說，追求寫入效能可以認為是在追求時間有序性（比如 Append-Only Log）；而追求查詢效能（特別是範圍查詢），就是追求空間有序性（比如 Sorted Group），而這兩者在很多時候是矛盾的。最早 Wisckey 中，vLog 就是一個 Append-Only Log，其寫入效能最好，但是從空間上來看完全不具有有序性，因此查詢效能最差；而最初的 LSM-Tree 中，KV 儲存在一起，Value 在每一層在空間上都是有序的，查詢效能最好的同時，Compaction 引起的寫放大也是最大的。DiffKV 透過將 Value 儲存在部分有序的 vTree 中的方式，在時間有序性和空間有序性中取得一個平衡，因此能夠同時擁有較好的讀寫效能。

參考文獻

Differentiated Key-Value Storage Management for Balanced I/O Performance

PebblesDB： Building Key-Value Stores using Fragmented Log-Structured Merge Trees

Dostoevsky： Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging

WiscKey： Separating Keys from Values in SSD-conscious Storage

HashKV： Enabling Efficient Updates in KV Storage via Hashing