PinK: High-speed In-storage Key-value Store

該篇文章來自於 ATC2020 Best Paper PinK： High-speed In-storage Key-value Store with Bounded Tails

論文其實是基於一種新的 KV 儲存形式 KV-SSD 開展研究的，KV-SSD 近年來常被提及，未來可能作為一種新型儲存器件在鍵值儲存系統中使用。

本文的工作主要實現了基於 LSM-Tree 的 KV-SSD，和基於雜湊的 KV-SSD 進行了對比。

Abstract

KV 儲存的實現主要有 LSM-tree 和 HASH 兩種，但相關學術研究和工業應用中 LSM Tree 因為支援更多的操作以及更好的寫效能，相比於 HASH 更受歡迎。但是，在資源有限的 KV-SSD 環境下，LSM-tree 很難實現，故 KV-SSD 的環境下常常使用 HASH 實現。

我們提出了

PinK

，一種基於 LSM-tree 實現的 KV-SSD，相比於基於 HASH 實現的 KV-SSD，99th 尾延遲降低了 73%，平均讀延遲增加了 42% 但吞吐量提升了 37%。

在資源受限的環境下提升 LSM-tree 的效能的核心思想是

避免使用 BloomFilter，使用少量的 DRAM 來 keep/pin LSM-tree 的頂層資料。

Introduction & Background

NAND Flash-based SSD

SSD 的具體結構請參考其他博文。

eg.

一個比較關鍵的點，也是本文涉及到的點：FTL 中維護了由 LBA 索引的對映表，對應地指向響應的 flash page。對映表儲存在 SSD 控制器 DRAM 中，DRAM 大小通常為 SSD 容量的 0。1%。對映表需要持久化，所以會使用到 SSD 內建的電容來防止突然的斷電故障。

KV-SSD

近年來學術和工業界都在考慮將 KV 儲存的相關功能從軟體層面轉移到硬體儲存裝置層面。

為什麼要引入 KV-SSD

？傳統的 KV 儲存不能完全發揮新型儲存器件的效能，如很多支援 NVMe 的裝置，結合之前 SOSP19 的一篇論文

[2]

，發現 KV Store 的 bound 已經從磁碟轉移到了 CPU，故考慮引入 KV-SSD 來降低 KV 儲存對 host 側的 CPU 和 DRAM 的高佔用率，同時減小 I/O 延遲並提高吞吐量。

KV SSD 支援的介面對應的規範：

https：//www。

snia。org/tech_activitie

s/standards/curr_standards/kvsapi

工業界

Samsung KV-SSD

：直接處理 KV 請求，參考文獻

[1]

。透過簡化軟體儲存堆疊和合並冗餘，KV-SSD 提供了更好的可伸縮性和效能，從而降低了總體 CPU 使用量並將記憶體釋放給使用者應用程式。

學術界

ASPLOS19

LightStore: Software-defined Network-attached Key-value Drives

KAML： A Flexible， High-Performance Key-Value SSD

Towards Building a High-performance， Scale-in Keyvalue Storage System。

NVMKV： A Scalable and Lightweight Flash Aware Key-value Store

Bluecache： A Scalable Distributed Flash-based Key-value Store

HASH-Based KV-SSD

SSD DRAM 中維護一個 hashtable， hashtable 有很多個 buckets，每個 bucket 對應的儲存了元資料（key 和指向 value 的指標）。假設 Key 為 32B，Value 為 1KB，假設 4TB 的 SSD 中的 bucket 數量為

$2^{32}$

，即 4TB 全部用於存 1KB 的 Value，那麼實際對應需要 DRAM 大小為

$36B * 2^{32}=144 GB$

才能裝下對應的 HashTable，但是按照之前的 0。1% 的計算邏輯來看，最多提供 4GB DRAM。顯然是不夠的。

為了降低 DRAM 使用率，可以使用雜湊簽名來代替 KEY，實際的 KEY 和 Value 一起儲存在 flash 中，即便是使用 16bit 的簽名還是需要 24GB 的 DRAM，且可能產生簽名衝突。所以只能儲存部分熱資料索引到 DRAM 中，剩餘部分需要儲存在 flash 中，但是引入了額外的 flash 讀取開銷。

現在的 KV-SSD 存在的問題

從現如今的 KV-SSD 表現出來的效果來看，在尾延遲和吞吐量方面表現都是 inconsistent （

注：至於這個 incosistent 怎麼理解，可以看後文的具體描述，大膽猜測一下應該是類似於 unpredictable 的意思

）

現在的 KV-SSD 主要都是基於 HASH 實現的，因為 HASH 實現起來相對容易，但是也就帶來了一些侷限。基於 HASH 實現的 KV-SSD 主要是在對應的磁碟控制器（DRAM）中維護了一個 HashTable，相應的操作本質就是查表以及對錶的管理，但是由於 KV-SSD 的 DRAM 容量有限，資料量大的時候肯定會有部分資料需要放在 Flash 上，簡單快速的 DRAM 內查表工作就可能退化成開銷較大的訪問 FLASH 的查表，同時還需要實現比較複雜的空間管理機制（何時訪問 FLASH 進行空間置換，諸如此類）。如果產生了 HASH 衝突，可能就需要訪問很多次 FLASH，導致長尾延遲以及吞吐量的下降。

光紙上談兵不行，做個實驗：4TB KV-SSD prototype （KV-PM983），KV pools 從 1GB 到 3TB，平均大小 Key-32B，Value-1KB，3TB 的池對應就可以有 30 億個 KV。負載 KVBench 10 分鐘隨機 GET（期間無 GC）。對比測試，對照了使用 4TB Block SSD 和 FIO 測試。

實驗結論：在基於雜湊的 KV-SSD 實現中，隨著儲存的 KV 對總數的增加，效能和尾延遲會變得更差，還不如 Block SSD 穩定。

incosistent 的效能表現可能是因為低效的 HASH 衝突解決策略引起的。可以考慮使用最壞情況下常數級的查詢的雜湊衝突解決策略，如 Cuckoo Hash， Hopscotch 等，來避免長尾延遲，但是這種好處是以降低寫入速度和/或頻繁重複雜湊為代價的。且 HASH 不支援 range query。

解決方案

從 DRAM 資源有限的角度來考慮，LSM-tree 提供了更好的效能。

在 KV-SSD 中比較常用的 LSM-tree 實現為 LightStore ［［3］］和 iLSM-SSD

[4]

考慮使用 LSM-tree 替代 HASH，因為 LSM-tree 需要使用的 DRAM 更小，對範圍查詢的支援也較好。但是實驗顯示，使用了常見的 LSM-Tree 實現的 KV-SSD 並沒有表現出預期的效果，在有些場景下甚至比 HASH 效能還差。

測試結果，如圖所示。

沒有 BloomFilter，LSM-tree KV-SSD 顯示出了比 BlockSSD 更高的延遲。

使用 BloomFilter 會顯著降低讀的層級數，平均進行一次 flash 上的 page read 就可以讀取到資料，讀延遲比不帶 BloomFilter 更好，但是尾延遲更嚴重（因為機率性的資料結構導致大約有 1。4% 的讀操作會需要超過一次的 flash lookup）。

YCSB-C 的負載下，吞吐量的表現上，帶 BloomFilter 的 LSM-tree KV-SSD 不到 Block-SSD 的一半（因為為了獲取KV索引來為GET（）服務， Monkey 需要兩次 flash 讀取）。

YCSB-Load 負載下，吞吐量嚴重下降，主要是因為 GC 產生了影響。我們發現為 GC 移動有效頁面涉及到 LSM 樹維護的 KV 索引的級聯更新。

CPU 的開銷，重建 BloomFilter 的開銷佔據了很大的比重。

通用的 LSM-tree 方案存在的問題

尾延遲：

雖然很多 LSM-tree 實現都使用了 BloomFilter 來改善平均讀延遲，但因為 BloomFilter 是機率型資料結構，對於最差的情況下的尾延遲還是沒有辦法改善，就會出現和 HASH KV-SSD 一樣的長尾延遲的情況。

嚴峻的寫放大：

LSM-tree 本身的問題（壓縮會導致 GC，GC 導致更多的 I/O，加劇寫放大），應用在 KV-SSD 中可能還會加劇 FTL 的 GC 開銷。

CPU 佔用率高：

這個也是 LSM-tree 本身存在的問題，現在用於 KV-SSD，本身儲存裝置的處理效能就有限，LSM-Tree 的 filter rebuild 以及 KV 對的壓縮排序都需要花費大量的時鐘週期，很容易導致 KV-SSD 的控制器處理單元過載，從而顯著影響 I/O 效能

本文的方案

Pink

：核心思想為

level pinning

，即透過將 top levels 的鍵值索引 pin 到 DRAM 中來代替 BloomFilter （

注：看著是不是很懵，可能直接看設計部分好點，但就暫時理解為 DRAM 裡放了個索引來代替了布隆過濾器吧

）

因為沒了 BloomFilter，使用了 DRAM 內的索引，帶來了兩個直接的好處：延遲變得 predictable；減少了資源佔用。

其他優點主要體現在：

壓縮過程減小了對 flash 的 I/O，因為 DRAM 索引排序不需要 I/O 操作，且該索引由內建的電容來保證永續性；

可以批次延遲更新 DRAM 中的 LSM-tree 索引，從而減小 GC I/O 次數；

新增硬體比較器來參與 sort 操作，而無需 CPU 介入，減小 CPU 開銷。

注：這兒可能看著還比較抽象，等著看下文的詳細設計部分吧

Design

Data Structure

DRAM

：a skiplist 和 level lists （由 SSD 電容保護）

skiplist：類似於 write buffer，通常配置的很大以便充分利用 NAND channels 的並行性來向 Flash 刷入資料。對應包含資料

level lists：每一層被組織成為了具有確定大小指標對組成的陣列，第一個指標指向 meta segment 在 flash 中的物理位置，第二個指標指向對應 meta segment 的開始 key。所以 meta segment 的起始 key 被單獨儲存在了 DRAM 中，

FLASH

：meta segments 和 data segments

skiplists 滿了之後，元資料和資料分離，刷入到 Flash，元資料包含指向對應資料的指標，資料段中儲存了 KEY 以及 Key Size 便於 GC。元資料段大小被固定為 flash page size，但資料段可以是任意大小

meta segment：由一組組成，按 key 排序，加上一個 header，key 大小可變 16B-128B，，為了利用二分查詢，所以維護了的起始位置在 header 中。

和 HASH 相比，PinK 需要使用的 DRAM 更少

Improving I/O Speed with Level Pinning

緩解讀延遲

：最差的情況下，PinK 需要

的 flash 查詢，為了防止這種情況， PinK 採用了

Level pinning

來代替布隆過濾器，簡單粗暴地可以理解如果 LSM-tree 有 h 層，PinK 直接把 top-k 層對應的 meta segments 給放在 DRAM 中。對於讀操作，首先看 DRAM 中的 top-k 層有沒有該 Key，沒有再訪問 flash。此時最糟糕的情況下的複雜度降低為

Level-pinning 記憶體需求

：假設 4TB SSD，共 5 層，可以根據 SSD 中 DRAM 的大小來考慮實際需要快取多少層 meta segement。

減少壓縮 I/O

：因為 meta segment 被快取在記憶體中，所以可以直接更新，且不用刷回，因為有電容保護。

Optimizing Search Path

假設

$L_{1}$

層有 N 個 entries，層級之間容量比為 T，因此

$L_{h-1}$

有

$N * T ^{h-2}$

。計算最壞的時間複雜度為

。帶 BloomFilter 的 LSM-tree 實現對應的複雜度可能更小，因為能夠跳過一些不必要的二分查詢。

為了減小查詢的開銷，PinK 使用了兩個技術：

一個是減少字串比較的開銷，透過使用 key 的字首，level list 的每個條目都有兩個指標，每個指標指向一個 meta segment 和一個 start key string，我們還包含了字首（即 start key 的前四個位元組）。二分查詢時，首先比較字首，只有匹配了才會匹配整個字串。

透過借用分級級聯技術來減少 level list 的搜尋範圍。level list 的每一個 entry 都會再有一個 4-byte 指標，稱之為範圍指標，該指標指向下一層的最大的起始 key 但是小於或等於當前 entry 的 key 的位置。例如，在

中找到了一個 entry

$e_{L_1}^i$

，如果該 entry 指向的 meta segment 不包含匹配的 KV index，那麼將會尋找下一層，

$e_{L_1}^i$

將成為

層搜尋的下界，而

$e_{L_1}^{i+1}$

對應的 range pointer 將成為搜尋的上界，從而縮小搜尋的範圍。複雜度變為

，因此平均時間複雜度降低為

Speeding up Compaction

雖然減少了壓縮對應的 I/O 次數，但是在壓縮過程中的排序操作仍然需要計算資源的開銷。考慮使用

HW accelerator

（硬體加速）來緩解主機端的壓力。HW 加速器放置在快閃記憶體和主機資料匯流排之間，可以很容易地合併兩個位於快閃記憶體的 level，因為兩個 level 的 meta segment 能夠從 flash 中以速度較快的流的形式進行傳輸。該加速器寫合併後的 meta segments 時不需要 CPU 的介入。硬體加速器的引入不僅減小了計算的開銷，同時提高了 I/O 匯流排的利用率，因為不再需要以前那樣的等待合併的以及合併後的資料傳輸。

如圖所示工作流程，PinK 軟體首先請求加速器來執行壓縮，並提供兩個 level 的 meta segments 地址以及合併後寫回的 mete segements 地址。flash request generator 會進行排程等待多個讀請求以便充分利用 flash 頻寬，由於不同 flash 通道的資料包是交錯的，我們需要為每個 level 使用每個通道的 reorder buffer 來序列化 meta segment。序列化之後送入 compaction engine，本質是個比較器進行歸併排序，將比較後的更小的資料以輸出流的形式，使用了小的 write buffer，最終輸出到寫回地址中，當兩個 key 相等的時候，上層對應的資料因為最新將取代另外的資料。操作完成後，將使用了的 meta segments 頁號返回，從而由上層決定回收哪些未使用的空間。

對於 pinned levels 的合併是有一個類似的機制，只是使用了 DMA 代替 flash request generator，以及互動的不是 flash 而是 DRAM。

Optimizing Garbage Collection

壓縮會產生兩種垃圾資料：

一種是老舊的 meta segment，當執行壓縮時，PinK 寫新的 meta segments 資料來替代老舊的資料，如下圖所示的 pages 0，1，2。

另一種是過期的 KV 物件，該物件被更新了或者被客戶端刪除了都變成過期物件，過期物件的索引在壓縮過程中會被直接丟棄，所以將沒有 meta segments 指向。但是資料部分仍然儲存在 data segments 中。

為了擦除老舊的資料，PinK 將在空間接近枯竭的時候觸發 GC，選擇一個 flash block，將其中的有效資料複製到空閒空間，然後擦除整個塊。因為冷熱分離的原因，meta segment 通常和 data segment 位於不同的塊，PinK 通常針對不同塊型別採用不同的 GC 策略。

GC for Meta Segment

讀取頁對應的起始鍵，然後查詢 level list 中是否有 entry 指向該鍵，如果沒有則說明是老舊的 segment，直接跳過，如果有則需要將該頁遷移到空閒頁，然後對該 entry 的更新也將定位到新的頁。清理 meta segment 的開銷較小，因為只涉及到有效頁的複製以及 DRAM 中對 level list 的更新。

GC for Data Segment

從選出來的塊中掃描一個 data segments，需要將 value 對應的鍵提取出來，利用 key 才能查詢到 level lists 並找到 meta segments，才能檢查該 value 的有效性，如果一個 meta segment 沒有被 pin 到 DRAM 中，就必須從 flash 中去讀，從而可以收集到很多的有效 values。

最簡單的方法就是 WiscKey 的垃圾回收思想，收集有效的然後複製，然後整塊擦除，對應 value 的 meta segment 也需要更新並刷回，從而指向新的位置。如果被 pin 到 DRAM 裡了，則不需要寫 flash。這種方法會造成會多對 flash 上的元資料更新，其次就是對於一些很久以前寫的資料，壓縮之後，很有可能一個 meta segment 中包含的物件不在同一個 value segement 或者 block 中，即可能只有很少的 value 被複製，但是卻要更新對應的 meta segment。

所以 PinK 採用了延遲寫的方式，把有效的 KV 再寫到 L0，然後擦除整塊。垃圾資料靜待回收，但是對原有有效資料的訪問將被更高 level 處理，即不進行元資料的更新，全部交給 GC，雖然增加了 compaction 開銷，但是減少了 mete segment 的更新，因為有效的 KV 對應的元資料被重新整合到了一個 meta segment 中。

GC 過程中會把有的資料放在 L0 層會一定程度上地影響讀延遲。

Durability and Scalability Issues

Durability with Limited Capacitor

前面我們默認了使用 SSD 裡的電容來保證 SSD DRAM 裡的資料不丟，但其實很多 SSD 沒有足夠的電容來保證 DRAM 裡的所有元資料，此時就會有永續性的問題。可以透過將 DRAM 中的資料結構寫入 flash 中來解決。L0 的資料可以在處理請求之前寫入日誌，即寫前日誌；在執行壓縮之後，level list 和 pinned levels 會變成髒資料，需要被持久化到 flash。

無論是寫前日誌還是髒資料刷回，在 HASH-KV-SSD 中一樣需要處理，但是在 LSM-tree-KV-SSD 中可能刷回操作的開銷更小，因為寫效能 LSM-tree 更好。

DRAM Scalability

我們一開始就假設了 SSD 的 DRAM 容量會隨著 flash 的容量的增加而增加，但是 DRAM 的容量增長速度比 flash 要慢，所以可能就沒把所有的 levels 給 pin 在 DRAM 中，即只能 pin 部分 levels，相應地也就會增加最壞情況下的查詢開銷，但即便是最壞情況下，也比使用 HASH 的 KV-SSD 或者使用通用 LSM-tree 的 KV-SSD 表現要好。

另外可以考慮減小樹的高度，即讓除了最後一層以外的上層結構都放在 DRAM 中，雖然會因為壓縮開銷的增大一定程度上犧牲寫效能，但是能在最壞的情況下將查詢複雜度限制在