Differentiated Key-Value Storage Management for Balanced IO Performance
本文使用 Zhihu On VSCode 創作併發布
ATC21 Differentiated Key-Value Storage Management for Balanced I/O Performance
Abstract
KV 儲存讀寫放大嚴峻，現有設計都是在做 trade-off，不能同時實現高效能的讀寫以及 scan。所以提出了 DiffKV，在 KV 分離的基礎上構建並仔細管理 Key Value 的順序。Key 沿用 LSM-Tree，保持全序，同時以協調的方式管理部分有序的 Value，以保持高掃描效能。進一步提出細粒度 KV 分離，以大小區分 KV 對，實現混合工作負載下的均衡效能。
Introduction
為了減小 compaction 開銷，現有方案大致有幾個方向。
放鬆全域性有序的要求來緩解 compaction 開銷。
但常伴隨著 scan 效能的下降
Dostoevsky
PebblesDB
SlimDB
基於 KV 分離，Key 有序，專門的儲存區管理 Value。
一是更適用於大 KV，二是還是有 scan 的效能損失（畢竟 Value 的順序不保證了就導致隨機讀），三是還引入了垃圾回收的開銷
WiscKey
HashKV
BadgerDB
Atlas
An Efficient Memory-Mapped Key-Value Store for Flash Storage
Titan
UniKV
簡而言之，現有的LSM-tree最佳化仍然受到讀寫和掃描之間緊密的效能緊張關係的限制，包括：
（i）
鍵和值的有序程度
（ii）
不同大小的KV對的管理
。
Background and Motivation
LSM-tree KV Store 基礎結構此處省略。
現有最佳化方案
主要還是分為兩類：
Relaxing fully-sorted ordering
KV separation
Relaxing fully-sorted ordering
以 PebblesDB 為例實現了分段 LSM。將一個 Level 分為了幾個不相交的 Guards，每個 Guard 裡的 SSTables 可以範圍重疊。那麼你會問了：
為啥這樣就能減小 compaction 開銷呢？
因為 PebblesDB 只是讀取了某一層中的 group 的 SSTables，然後進行了排序建立了新的 SSTables 寫到下一層，compaction 過程不需要讀取下一層的 SSTables 從而減小 compaction 開銷和寫放大。
但是因為每個 Group 裡的 SSTable 是重疊的，所以犧牲了一部分 scan 效能，雖然可以利用多執行緒來並行讀，但是就導致了更多的 CPU 開銷，所以提升也是有限的。
20210617231445
KV separation
KV 分離則是將 Key 和 Location 資訊儲存在 LSM-tree，Value 單獨地儲存在一個日誌裡，Titan 中以多個 blob 檔案形式來組織 Value。對於中大型 Value，因為 Key 和 Location 有著遠小於 Value 的大小，在 LSM-tree 裡儲存的資料量就比較小，compaction 開銷和寫放大也相應比較小。除此以外，小的 LSM-tree 也減小了讀放大，可以提升讀效能。
20210618103203
然而，由於 KV 分離將值寫入一個附加日誌，一個連續範圍的鍵值現在分散在日誌的不同位置。scan 操作也就會導致隨機讀取，因此導致比較差的 scan 效能，特別是小到中型 Value（OLTP 應用超過 90% 的 value 小於 1KB），除此以外，KV 分離還需要 GC 來回收空間，頻繁的 GC 操作會導致額外的 I/O 開銷。
Trade-off Analysis
效能測試之前，先大概講一下 Titan
Titan 基於 KV 分離實現，此外，採用了多個小的 Blob Files 來代替大的只追加寫的日誌對 Value 進行管理，使用多執行緒來減小 GC 開銷。
資料組織形式如下：
LSM-tree： Key - index（BlobFileID：offset：ValueSize）
BlobFile： Value （Value 的儲存類似於原本 SSTable 的結構）
每條 BlobRecord 冗餘儲存了 Value 對應的 Key 以便反向索引，但也引入了寫放大
KeyValue 有序存放，為了提升 scan 效能，甚至進行預取
支援 BlobRecord 粒度的 compression，支援多種演算法
GC：
監聽 LSM-tree 的 compaction 來統計每個 BlobFile 的 discardable 資料大小，觸發的 GC 則選擇對應 discardable 最大的 File 來作為 candidate
GC 選擇了一些 candidates，當 discardable size 達到一定比例之後再 GC。使用 Sample 演算法，隨機取 BlobFile 中的一段資料 A，計其大小為 a，然後遍歷 A 中的 key，累加過期的 key 所在的 blob record 的 size 計為 d，最後計算得出 d 佔 a 比值 為 r，如果 r >= discardable_ratio 則對該 BlobFile 進行 GC，否則不對其進行 GC。如果 discardable size 佔整個 BlobFile 資料大小的比值已經大於或等於 discardable_ratio 則不需要對其進行 Sample
20210618111817
Write performance
：載入 100GB 資料庫，不同 value 大小（128B - 16KB），兩種最佳化方案都能降低寫放大，隨著 value 大小的增加，寫放大降低的越多，相應的寫吞吐也就很大提升。證明以往的兩種最佳化方向都是可以改善寫放大並提升寫效能的，特別是對於大 Value。
20210618104027
Read and scan performance
：放鬆全域性有序的要求導致查詢效能出現了降級，而 KV 分離因為顯著減小了 LSM-tree 的大小，讀吞吐比 RocksDB 高很多。而對於 scan 兩種方案都比 RocksDB 差很多，做了延遲分解，發現大部分掃描時間花在了 iteratively reading values，隨著 value 的增大，scan 延遲的差距變小，因為訪問更大的 Value 對應了更小的隨機讀開銷。對於那些小 KV 為主的負載，兩種最佳化方案都會受到很大限制。
20210618140321
總結一下，現有的最佳化方案其實都是在做 reads/writes 的 trade-off，兩種最佳化方向的本質都是在降低 Value 的有序程度來減小寫放大並提升吞吐量，但相應地犧牲了 scan 的效能，特別是對於小到中型的 KV 對。
Design
System Overview
DiffKV 利用了一個類似於 LSM-tree 的結構 vTree 來組織 Value 保證 Value 的部分有序，也是由多個 Level 組成，每個 level 只能以追加的方式寫入，和 LSM-Tree 的不同在於，vTree 只儲存那些在每一層中不一定按鍵完全排序的 Value，即允許部分有序來保證 scan 效能。
為了實現部分有序，vTree 也需要類似 compaction 的操作，稱之為 merge，為了減小 merge 的開銷，DiffKV 讓 LSM-tree 的 compaction 和 vTree 的 merge 協調地執行來減少總體開銷。
為了讓 DiffKV 和現有設計相容，記憶體元件和 WAL 都和原生 LSM 一樣，流程是一樣的。
20210618144116
Data Orgaization
vTree 分層組織，每層由 sorted groups 組成，每個 group 由很多 vTables 組成。（
這裡彷彿就跟 PebblesDB 的設計是類似的了
）
vTable
大小固定，8MB 預設。一個 immutable Memtable 的 flush 可以生成很多個 vTables，取決於 value size 和 Memtable Size。
vTable 組成部分：
data area： 基於 Key 的順序儲存 values
metedata area： 記錄必要的元資料，比如 vTable 的資料大小，該 table 中最小最大 Value（
和 SSTable 不同的是不要求 BllomFilter
，因為直接查索引就能知道）。元資料較小，儲存開銷也較小。
Sorted Group
所有的 vTables 在 Group 中也是有序的。也就是無重疊範圍，LSM-tree 的 SSTables 組成的集合也相當於一個 Sorted Group。DiffKV 一次 flush 對應生成一個 Sorted Group，從而保留每個 immutable Memtable 裡順序性，對應 Groups 數量表示了 vTree 的有序程度，Groups 數量增加，有序性相應下降，在一個極端情況下，如果所有的 sstable/vtable組成一個 Group，那麼有序程度最大，因為所有的 KV 對都是完全排序的。
（埋個坑：這裡直接用 Groups 數量來表示有序程度會不會有些草率，其實有序與否更多是看重疊範圍大小，當然 Groups 越多重疊的機率可能越大，但不確定這個有序程度是不是會對後面造成影響，拭目以待）
vTree
vTree ——- 1：N ——- levels ——- 1：N ——- groups ——- 1：N ——- vTables ——- 1：N ——- values
全域性有序的最小單元是 group，level 就可能存在具有重疊鍵範圍的 groups 了，merge 操作不需要對 vTree 中連續兩層中的所有值進行排序；與 lsm-tree 中的 compaction 相比，這減輕了I/O開銷
Compaction-Triggered Merge
首先，為什麼要 merge？
其實就是為了保證部分有序，或者說維持有序性，這樣才可能加速 scan。
Merge 會讀取一定數量的 vTables，透過查詢 LSM-tree 中儲存的最新位置資訊來檢查哪些 value 是有效的，每個 merge 還要更新最新的 location 資訊到 LSM-tree 中
為了限制 vTree 中的合併開銷，vTree 中的合併操作不是獨立執行的，而是和 LSM-tree 中的壓縮操作以協調的方式觸發的。所以稱該操作為 compaction-triggered merge
舉例說明：
假設 LSM tree 的 level 和 vTree 的 level 是關聯的。
當 LSM-tree 發生 Level i -> i+1 的 compaction 的時候，相應地觸發 vTree 上相應的 value 從
到
的 merge。
Merge 有兩個主要問題：
選哪些 value 進行 merge
？選擇那些參加了 compaction 的 keys 對應的 value 進行 merge，稱之為 compaction-related value
如何把這些 value 寫回到 #FormatImgID_15#
？把這些 value 組織起來生成新的 vTables 並把這些 vTables 以追加寫的形式寫到下一層。如下圖所示的棕色就是這些需要 merge 的 values，
，
，
在排序後追加寫入到下一層。
20210618151924
生成的 vTables 中的所有資料都是有序的，也就是說 Merge 產生的 vTables 形成了一個單獨的 sorted group。但是，我們要指出的是，合併操作並不需要重新組織 vTree 中
和
兩級的所有vtable。追加寫的形式來表面重寫，從而減小寫放大，老的 vTables 也不會在 merge 過程中刪除，因為可能還是包含一些有效的 value，交給 GC 來判斷處理。
compaction-triggered merge 帶來的好處表現在兩個方面
：（
協同設計的核心
）
只合並與 compaction 相關的值可以非常有效地識別哪些值仍然有效，因為在 compaction 期間本身就需要從 lsm-tree 中讀出相應的鍵
。相反如果 vTree 的 merge 獨立執行，那就需要查詢 LSM-tree 並比較 location 資訊來判斷有效性了，增加了較大的查詢開銷。
merge 操作過程中新生成的 vTables 伴隨著有效 value 的位置資訊的變化，LSM-tree 需要被更新來維護對應的最新的 value location 資訊，因為
只有 compaction-related values 被合併，更新 LSM 樹中的值位置可以透過直接更新參與 compaction 的 KV 對來執行
。因此，更新值位置的開銷可以隱藏在 compaction 操作中，因為 compaction 本身需要重寫 lsm 樹中的 KV 對
Merge Optimizations
Compaction-triggered merge 引入了有限的合併開銷，該開銷又主要是檢查 value 的有效性並寫回 value location 資訊造成的。但是如果讓每一次 compaction 操作都觸發 merge 的話可能造成頻繁的 merge，比如 vTree 中的每個級別只與 LSM-tree 中的一個級別相關，那麼每個 compaction 操作都必須在 vTree 中觸發合併操作，為了減小 merge 開銷，提出了兩個最佳化方案。
Lazy merge
該策略用於限制 merge 頻率和開銷。核心思想是聚合多個 lower vTree levels 為單個 level，關聯地聚合 LSM-tree 的多個 levels，如下圖所示。聚合 vTree 的 0，。。。，n-2 為一個單獨的 level，相應地聚合 LSM Tree 的 0，。。。，n-2 levels，因此任何發生在 0，。。。，n-2 之間的 compaction 都不會觸發 merge，也就是說 vTree 的 0，。。。，n-2 Level Merge 操作被延遲到除非需要合併到
的時候才會執行。
該策略顯著減少合併次數和合並資料量，但是犧牲了較低層次的 value 的有序程度，然而，我們認為這種犧牲對掃描效能的影響是有限的。因為 LSM 中的大部分資料都是儲存在最後幾層，不同層次的資料分佈不均勻意味著大多數值實際上是從 vTree 的最後兩層進行掃描的，所以最後兩層的值的有序程度才會更多地影響 scan 效能。也就是說，low level 對 scan 效能影響很小，頻繁的在 low level 的合併操作不會對 scan 效能的提升有什麼幫助但卻引入了較大的 merge 開銷。
20210618155342
Scan-optimized merge
該策略用於調整 value 的有序程度，來保證較高的 scan 效能。原本的合併策略中，上層的 value 被重新組織寫入到下層，下層的 value 其實是沒有參與 merge 的。這種策略減小了寫放大，但是導致了太多的 sorted group，即可能重疊的現象更嚴峻。因此我們的核心思想是找到和其他 vTables 有重疊範圍的 vTables，讓這些 vTables 參與 merge 而不管其位於哪一層。這樣就能保證有序的程度較高。
下圖描述了核心思想，在普通的 compaction-triggered merge 之後，首先在下層檢查包含 compaction-related values 的 vTables，目標是找出滿足如下兩個條件的 vTables 集合：
集合中至少一個 vTable 有重疊的鍵範圍
vTables 的數量，也就是 set size，大於預先定義的閾值，max_sorted_run
如果存在上述的 SET，scan 效能勢必會降低，因為這些 vTable 沒有被排序。所以新增一個 scan optimization tag 給這些 tables，所以他們將能總是參與到下一次 Merge 並增加有序性。
為了找到這樣的一組 vTables，首先遍歷每個包含 compaction-related values 的 vTable 的起始和終止 Key，對於每個檢查的 vTable，統計有重疊鍵範圍的 vTables 的數量，可以透過掃描排序後的鍵字串來完成。如下圖所示，考慮一個檢查過的 vTable 【26-38】，掃描排序後的字串，可以統計出在 Key 38 之前起始 keys 的個數，本例中有五個，然後結束 Key 在 26 之前的只有一個，然後相減，得到和 【26-38】 重疊的 tables 有四個，也就是該集合的 size 為 4，如果超過了閾值，那麼就會給這些 tables 新增 tag，並在下一次合併中對他們進行合併。同時這個 tag 會被持久化到 mainfest file 中，持久化開銷可忽略不計。
20210618161027
Scan-optimized merge 該策略是一個原始策略上的 enhancement。原策略只是簡單做追加寫，而該策略進一步包含了下一層中確定的 tables 來進行合併，從而增加有序性。注意該策略引入了有限的合併開銷，有兩個原因：
允許每一層有多個 sorted groups（一整層不是全域性有序的）
（這裡有點奇怪）
不是標記了的 table 中的所有 values 都會參與 merge，而只是 compaction-related values 會參與。
GC
為了減小 GC 開銷，又提出了基於無效 value 數量的 state-aware lazy approach
State awareness
DiffKV 在一個雜湊表中記錄每個 vTable 的無效 KV 的數量，每次當 vTable 參與一個 Merge 的時候，DiffKV 記錄從 vTable 中檢索到的值的數量，並在雜湊表中更新舊 vTable中無效值的數量。它還為雜湊表中任何新的 vTable 插入一個條目。對雜湊表的更新是在合併操作期間執行的，因此開銷是有限的。另外，雜湊表中的每個條目只佔用幾個位元組，所以雜湊表的記憶體開銷是有限的。
Lazy GC
如果 vTable 有一定比例的無效 Values 且超過閾值 gc_threshold 的時候被選為 GC candidate，需要注意的是 DiffKV 不能立馬回收候選的 vTables，相反只是標記一個 GC tag，延遲 GC 到下一次合併。具體的，如果帶有 GC tag 的 vTable 被包含到一次合併中，那麼該 table 包含的 values 將總是被重寫到下一個 level。
該策略避免了查詢 LSM 檢查有效性的額外開銷，也避免了更新 LSM 新的地址資訊的開銷，被延遲到和合並一起執行，所以查詢和更新的開銷可以被合併操作給隱藏。
Discussion
Optimizing compaction at L0
：提出一個簡單的最佳化 selective compaction 來聚合 Level 0 中小的 SSTables，具體而言，我們會觸發內部 compaction，簡單地在 L0 處合併多個小 sstable 來生成一個新的大的，而不與 L1 處的 sstable 合併，這樣的話，L0 中的 SSTables 的大小將和 L1 中的相當，且沒有額外的 compaction 開銷引入。
Crash consistency
：DiffKV 基於 Titan 實現，一致性保證和 Titan 以及 RocskDB 一樣，使用了 WAL。同時 DiffKV 還未記錄無效資料的 HASHTable 提供了一致性保證，隨著 HashTable 在 compaction 之後被更新，DiffKV 將更新資訊追加到 manifest 檔案中。
Fine-grained KV Separation
對於大KV對，KV分離的好處是顯著的，但對於小KV對就不是這樣了。然而，不同值大小的混合工作負載也很常見；例如，在廣義帕累託分佈下，值的大小可能變化很大。在本節中，我們透過 value 大小來區分KV對，透過細粒度的KV分離來進一步增強DiffKV，從而實現混合工作負載下的均衡效能。
Differentiated Value Management
使用兩個引數分為三組，small medium large 。小 value 直接寫 LSM，中 Value 寫 vTree，大 value 寫 vLog。
大 value 的在寫 Memtable 之前就先分離了 KV，這樣做的好處有兩個方面：
直接將大 value 刷回到 vLog，並保留小的 Key 和地址資訊在 Memtable，可以節省記憶體消耗，同時因為大的順序 I/O 保證了較高的寫效能。
因為大 value 被寫回到了 disk，就不用再寫 WAL 了，減小了 I/O 的次數
需要注意的是，對於中小型KV對，以及大型KV對的鍵和值位置，仍然需要寫入WAL中，以保證一致性。
20210618170142
Hotness-aware vLogs
Structure of vLogs
就是一個簡單的環形只允許追加的日誌，由一組無序的 vTables 組成，vTable 和前面提到的 vTable 格式相同，唯一的不同是 value 是追加寫入到無序的 vTables 的，所以在每個 table 內也是無序的，我們這樣做的原因是因為 KV 分離對於大型 KV 對執行寫入MemTable 之前，大型 KV 被立即重新整理到磁碟，以免寫 WAL，所以沒有辦法排序每個 table 中的 values。事實上也不需要，因為他們本身就能從大 I/O 中獲益了而不用批次寫入。
GC for vLogs
為了減小 GC 開銷，使用了一個熱點感知的設計，採用一種簡單而有效的無引數冷熱分離方案。如下圖所示，使用兩個 vLogs，分別對應冷熱 vLogs，儲存了對應的冷熱資料，每個vLog 都有自己的寫邊界，我們分別稱它們為 寫頭 和 GC 頭。為了實現冷熱分離，使用者寫入的資料被追加到 hot vLog 的 write head，而來自於 GC 寫的資料（比如有效資料需要在 GC 過程中進行寫入）被追加寫到 cold vLog 的 GC head。其基本原理是，GC 回收的值通常比最近寫入的使用者資料訪問頻率更低，因此可以將它們視為冷資料，這種設計的一個好處是實現簡單，因為實現冷熱識別不需要引數。顯然，我們還可以應用其他的熱點感知分類方案。
DiffKV 使用了一個貪心的演算法來減小 GC 開銷，思想是回收有最大數量的無效值的無序的 vTables。具體的，DiffKV 在 compaction 中監控了每個無序 vTables 的無效資料比例，並維護了一個記憶體中的 GC 佇列來追蹤所有候選的 vTables，候選條件即為無效值比例大於閾值。需要注意的是 GC 佇列只維護每個無序 vTable 的元資料，它根據無效值的比率按降序進行維護。GC 觸發的時候，DiffKV 簡單地選擇佇列頭的無序 vTables，如圖 9 中的 t1 t2，然後將有效的 values 追加到 cold vLog 的 GC 頭。出於效能考慮，DiffKV 使用後臺程序多執行緒來實現 GC。
Evaluation
原文做了大量實驗，實驗很足，細節可以去看原文。
20210618205333
20210618211219
20210618213715
20210618213702
20210618213857
