KVSSD：深度整合日誌結構合併樹與快閃記憶體轉換層的高寫入效率鍵值儲存系統

Abstract

日誌結構合併樹(LSM tree)是一種針對寫入最佳化的資料結構，用於輕量、高效能的鍵值儲存系統。SSD則是一種可以有效加速LSM tree的鍵值操作的儲存媒體。然而，多層軟體架構的設計將會造成「多重寫入放大率(cascading write amplification)」的問題，這些軟體層包含LSM tree本身、檔案系統與SSD內的快閃記憶體轉換層(FTL)。我們提出的KVSSD是藉由深度整合LSM tree和FTL來管理來自不同軟體層的寫入放大率。KVSSD利用FTL的映射機制實作了不需要複製資料就可以達成LSM tree的資料壓縮(Compaction)動作，並且可以直接分配空間讓垃圾回收(Garbage Collection)更加有效率。在我們的實驗中，與原本的多層軟體架構設計作比較，KVSSD減少約80%的寫入放大率並提升產出接近290%。

Log-Structured-Merge (LSM) trees are a write-optimized data structure for lightweight, high-performance Key-Value (KV) store. Solid State Disks (SSDs) provide acceleration of KV operations of LSM trees. However, this hierarchical design involves multiple software layers, including the LSM tree, host file system, and Flash Translation Layer (FTL) inside of SSDs, causing cascading write amplifications. We propose KVSSD, a close integration of LSM trees and the FTL, to manage write amplifications from different layers. It exploits the FTL mapping to implement copy-free compaction of LSM trees, and it enables direct data allocation in flash memory for efficient garbage collection. In our experiments, compared to the hierarchical design, our KVSSD reduced the write amplification by 80% and improved the throughput by 290%.