Rapid increase of storage and network bandwidth incurs higher CPU consumption in modern data systems. This phenomenon is particularly evident for log-structured merged key-value stores (LSM-KVS), which rely on resource-intensive background operations to flush and compact disk data. While extensive research has been conducted to reduce the CPU overhead of background compaction, less attention has been paid to background flushing, which can also consume a significant amount of valuable CPU cycles and disrupt CPU caches, ultimately impacting overall performance. In this paper, we propose DFlush, a novel solution that uses DPUs to offload background flush operations to reduce its CPU cost. DPUs are an appealing choice for this goal due to their cost-effectiveness, ease of programming, and widespread deployment. However, their complex hardware architecture requires careful design of both the data and control planes. To fully harness the DPU's capabilities, DFlush decomposes a flush job into fine-grained steps, mapped them to DPU hardware units, and accelerates them through pipeline, data, and channel parallelism, ensuring data-plane efficiency. It also introduces an adaptive control plane that dynamically schedules flush jobs from different LSM-KVS instances based on their priority, reducing write stall and tail latency. Our experiments on a real DPU platform with an industrial-grade LSM-KVS show that DFlush delivers higher throughput, significantly lower tail latency, and saves up to dozens of CPU cores per LSM-KVS server while reducing energy consumption.

Disaggregated memory separates compute and memory resources into independent pools connected by fast RDMA (Remote Direct Memory Access) networks, which can improve memory utilization, reduce cost, and enable elastic scaling of compute and memory resources. Hash indexes provide high-performance single-point operations and are widely used in distributed systems and databases. However, under disaggregated memory, existing hash indexes suffer from write performance degradation due to high resize overhead and concurrency control overhead. Traditional write-optimized hash indexes are not efficient for disaggregated memory and sacrifice read performance. In this paper, we propose SepHash, a write-optimized hash index for disaggregated memory. First, SepHash proposes a two-level separate segment structure that significantly reduces the bandwidth consumption of resize operations. Second, SepHash employs a low-latency concurrency control strategy to eliminate unnecessary mutual exclusion and check overhead during insert operations. Finally, SepHash designs an efficient cache and filter to accelerate read operations. The evaluation results show that, compared to state-of-the-art distributed hash indexes, SepHash achieves a 3.3X higher write performance while maintaining comparable read performance.

Disaggregated memory separates compute and memory resources into independent pools connected by RDMA (Remote Direct Memory Access) networks, which can improve memory utilization, reduce cost, and enable elastic scaling of compute and memory resources. However, existing RDMA-based distributed transactions on disaggregated memory suffer from severe long-tail latency under high-contention workloads. In this article, we propose Scythe, a novel low-latency RDMA-enabled distributed transaction system for disaggregated memory. Scythe optimizes the latency of high-contention transactions in three approaches: (1) Scythe proposes a hot-aware concurrency control policy that uses optimistic concurrency control (OCC) to improve transaction processing efficiency in low-conflict scenarios. Under high conflicts, Scythe designs a timestamp-ordered OCC (TOCC) strategy based on fair locking to reduce the number of retries and cross-node communication overhead. (2) Scythe presents an RDMA-friendly timestamp service for improved timestamp management. And, (3) Scythe designs an RDMA-optimized RPC framework to improve RDMA bandwidth utilization. The evaluation results show that, compared with state-of-the-art distributed transaction systems, Scythe achieves more than 2.5× lower latency with 1.8× higher throughput under high-contention workloads.

Memory disaggregation is a promising architecture for modern datacenters that separates compute and memory resources into independent pools connected by ultra-fast networks, which can improve memory utilization, reduce cost, and enable elastic scaling of compute and memory resources. However, existing memory disaggregation solutions based on remote direct memory access (RDMA) suffer from high latency and additional overheads including page faults and code refactoring. Emerging cache-coherent interconnects such as CXL offer opportunities to reconstruct high-performance memory disaggregation. However, existing CXL-based approaches have physical distance limitation and cannot be deployed across racks. In this article, we propose Rcmp, a novel low-latency and highly scalable memory disaggregation system based on RDMA and CXL. The significant feature is that Rcmp improves the performance of RDMA-based systems via CXL, and leverages RDMA to overcome CXL’s distance limitation. To address the challenges of the mismatch between RDMA and CXL in terms of granularity, communication, and performance, Rcmp (1) provides a global page-based memory space management and enables fine-grained data access, (2) designs an efficient communication mechanism to avoid communication blocking issues, (3) proposes a hot-page identification and swapping strategy to reduce RDMA communications, and (4) designs an RDMA-optimized RPC framework to accelerate RDMA transfers. We implement a prototype of Rcmp and evaluate its performance by using micro-benchmarks and running a key-value store with YCSB benchmarks. The results show that Rcmp can achieve 5.2× lower latency and 3.8× higher throughput than RDMA-based systems. We also demonstrate that Rcmp can scale well with the increasing number of nodes without compromising performance.

Disaggregated Persistent Memory (DPM) is a promising technology offering elasticity, high resource utilization, persistent data storage, and lower power consumption. While building KV stores on the DPM benefits from these merits, achieving efficient writes also faces two primary challenges: 1) limited scalability caused by the underused PM bandwidth, and 2) limited CPU resources the persistent memory server (PMS) can provide. Integrating the SmartNIC such as the Data Processing Unit (DPU) into the DPM gives developers the chance to optimize writing to KV stores by utilizing both the memory and processor of DPU. However, simple offloading cannot make full use of the DPU’s potential capacity. To address these challenges, we propose DoW-KV, a persistent hash KV store on DPM. DoW-KV employs a two-tier hash index consisting of a DPU cache table in DPU memory and multiple PM persistent tables on the PM. It relocates small random writes to the DPU memory and consolidates them to the PM at a coarse granularity. Furthermore, DoW-KV uses DPU-offloaded step merge and a coroutine-based asynchronous processing framework to efficiently manage the PM persistent tables. DoW-KV also introduces a client-mixed read strategy to boost key searching on the two-tier hash index. Experimental results show that DoW-KV outperforms the state-of-the-art DINOMO by 2.1× and 1.3× in the Put and Get operations, respectively.

Previous works proposed building file systems and organizing the metadata with KV stores because KV stores handle entries of various sizes efficiently and have excellent scalability. The emergence of the byte-addressable persistent memory (PM) enables metadata service to be faster than before by tailoring the KV store for the PM. However, existing PM-based KV stores cannot handle the workloads of file systems’ metadata well because simply depending on hash tables or trees cannot simultaneously provide fast file accessing and efficient directory traversing. In this paper, we exploit the insight of the metadata operations and propose the PetaKV, a KV store tailored for the metadata management of file systems on PM. PetaKV leverages dual hash indexing to achieve fast file put and get operations. Moreover, it cooperates with PM-tailored peta logs to collocate KV entries for each directory, thus supporting efficient directory scans. Our evaluation indicates PetaKV outperforms state-of-art tree-based KV stores on put, get and scan$2.5\times$,$3.2\times$, and$2.8\times$on average, respectively. Moreover, the file system built with PetaKV achieves$1.2\times$to$6.4\times$speedup compared to those built with tree-based KV stores on the metadata operations.

Host-managed shingled magnetic recording drives (HM-SMR) are advantageous in capacity to harness the explosive growth of data. For key-value (KV) stores based on log-structured merge trees (LSM-trees), the HM-SMR drive is an ideal solution owning to its capacity, predictable performance, and economical cost. However, building an LSM-tree-based KV store on HM-SMR drives presents severe challenges in maintaining the performance and space utilization efficiency due to the redundant cleaning processes for applications and storage devices (i.e., compaction and garbage collection). To eliminate the overhead of on-disk garbage collection (GC) and improve compaction efficiency, this article presents GearDB , a GC-free KV store tailored for HM-SMR drives. GearDB improves the write performance and space efficiency through three new techniques: a new on-disk data layout, compaction windows, and a novel gear compaction algorithm. We further augment the read performance of GearDB with a new SSTable layout and read ahead mechanism. We implement GearDB with LevelDB, and use zonefs to access a real HM-SMR drive. Our extensive experiments confirm that GearDB achieves both high performance and space efficiency, i.e., on average 1.7× and 1.5× better than LevelDB in random write and read, respectively, with up to 86.9% space efficiency.

Popular LSM-tree based key-value stores suffer from suboptimal and unpredictable performance due to write amplification and write stalls that cause application performance to periodically drop to nearly zero. Our preliminary experimental studies reveal that (1) write stalls mainly stem from the significantly large amount of data involved in each compaction between$L_{0}$-$L_{1}$(i.e., the first two levels of LSM-tree), and (2) write amplification increases with the depth of LSM-trees. Existing work mainly focus on reducing write amplification, while only a couple of them target mitigating write stalls. In this paper, we exploit unique features of non-volatile memory (NVM) to address these two limitations and propose TriangleKV, a new LSM-tree based persistent KV store with multi-tier DRAM-NVM-SSD storage. TriangleKV's design principles include performing smaller and cheaper$L_{0}$-$L_{1}$compaction to reduce write stalls while reducing the depth of LSM-trees to mitigate write amplification. To this end, four novel techniques are proposed. First, we relocate and manage the$L_{0}$level in NVM with our proposedtriangle container. Second, the newright-angle side compactionis devised to compact$L_{0}$to$L_{1}$at fine-grained key ranges, thus substantially reducing the amount of compaction data. Third, TriangleKV increases the width of each level to decrease the depth of LSM-trees thus mitigating write amplification. Finally, thecross-row hint searchis introduced for the triangle container to keep adequate read performance. We implement TriangleKV based on MatrixKV and evaluate it on a hybrid DRAM/NVM/SSD system using Intel's latest 3D Xpoint NVM device Optane DC PMM. Evaluation results show that, with the same amount of NVM, TriangleKV outperforms RocksDB, NoveLSM and MatrixKV in 99th-percentile latencies by$5.5\times$,$2.1\times$and$1.1\times$, and random write throughput by$4.9\times$,$3.5\times$and$1.4\times$respectively.

To leverage the larger-than-DRAM capacity and close-to-DRAM performance of persistent memory (PM) to build future memory systems, more scalable and efficient indexing structures are of paramount importance. However, as we evaluate existing PM indexing structures, we find that (1) both ordered and unordered indexing structures cannot support efficiently all KV operation types, i.e., Put, Get, Delete and Scan, and (2) the majority of indexes scale poorly as the PM capacity and dataset increases, i.e., the decreasing throughput of ordered indexes with the growth of dataset and the blocking of foreground requests by costly hash resizing of unordered indexes. To provide better operational efficiency on both point accesses and range queries for persistent memory in the ever-increasing volume of data, this article proposes ComboTree, a three-tiered indexing structure with a sorted key space. In ComboTree, we break the global B+Tree into multiple low height B+Trees (Tier C) and arrange them with a sorted array (Tier B). Further, we accelerate the lookup of the sorted array by cumulative distribution function (Tier A). Last but not least, a background resizing policy is proposed to avoid performance degradation when the capacity of the ComboTree grows. We implement and evaluate ComboTree on Intel’s Optane DCPMM. Test results show that ComboTree delivers$2.1\times -3.6\times$put throughput and$1.5\times -2.1\times$get throughput of the state-of-art sorted indexes. Furthermore, ComboTree is$1.27\times$faster than the efficient B+Tree variant in various scan granularities, and it is open-sourced1.

Key-value (KV) stores play an increasingly critical role in supporting diverse large-scale applications in modern data centers hosting terabytes of KV items which even might reside on a single server due to virtualization purposes. The combination of the ever-growing volume of KV items and storage/application consolidation is driving a trend of high storage density for KV stores. Shingled Magnetic Recording (SMR) represents a promising technology for increasing disk capacity, which however comes with the increased complexity of handling random writes. To take the best advantages of SMR drives, applications are expected to work in an SMR-friendly way. In this work, we present SEALDB, a Log-Structured Merge tree (LSM-tree) based key-value store that is specifically optimized for SMR drives via avoiding random writes and the corresponding write amplification on SMR drives. First, for LSM-trees, SEALDB collects and groups participating data of each compaction into sets. Using a set as the basic unit for compactions, SEALDB improves compaction efficiency by reducing random I/Os. Second, SEALDB creates variable sized bands on original HM-SMR drives, named dynamic bands. Dynamic bands store sets in an SMR-friendly way to eliminate the auxiliary write amplification from SMR drives. Third, SEALDB employs two light-weight garbage collection (GC) policies to further improve the space efficiency. We demonstrate the advantages of SEALDB via extensive experiments with various workloads. Overall, SEALDB delivers impressive performance compared with LevelDB, e.g., 3.42×/2.65× faster for random writes (without or with GCs), and 3.96× faster for sequential reads.

Key-value (KY) stores play an increasingly critical role in supporting diverse large-scale applications in modern data centers hosting terabytes of KY items which even might reside on a single server due to virtualization purpose. The combination of ever growing volume of KY items and storage/application consolidation is driving a trend of high storage density for KY stores. Shingled Magnetic Recording (SMR) represents a promising technology for increasing disk capacity, but it comes at a cost of poor random write performance and severe I/O amplification. Applications/software working with SMR devices need to be designed and optimized in an SMR-friendly manner. In this work, we present SEALDB, a Log-Structured Merge tree (LSM-tree) based key-value store that is specifically optimized for and works well with SMR drives via adequately addressing the poor random writes and severe I/O amplification issues. First, for LSM-trees, SEALDB concatenates SSTables of each compaction, and groups them into sets. Taking sets as the basic unit for compactions, SEALDB improves compaction efficiency by mitigating random I/Os. Second, SEALDB creates varying size bands on HM-SMR drives, named dynamic bands. Dynamic bands not only accommodate the storage of sets, but also eliminate the auxiliary write amplification from SMR drives. We demonstrate the advantages of SEALDB via extensive experiments in various workloads. Overall, SEALDB delivers impressive performance improvement. Compared with LevelDB, SEALDB is 3.42× faster on random load due to improved compaction efficiency and eliminated auxiliary write amplification on SMR drives.

Log-Structure Merge tree (LSM-tree) has been one of the mainstream indexes in key-value systems supporting a variety of write-intensive Internet applications in today’s data centers. However, the performance of LSM-tree is seriously hampered by constantly occurring compaction procedures, which incur significant write amplification and degrade the write throughput. To alleviate the performance degradation caused by compactions, we introduce a lightweight compaction tree (LWC-tree), a variant of LSM-tree index optimized for minimizing the write amplification and maximizing the system throughput. The lightweight compaction drastically decreases write amplification by appending data in a table and only merging the metadata that have much smaller size. Using our proposed LWC-tree, we have implemented three key-value LWC-stores on different storage mediums including Shingled Magnetic Recording (SMR) drives, Solid State Drives (SSD), and conventional Hard Disk Drives (HDDs). The LWC-store is particularly optimized for SMR drives, as it eliminates the multiplicative I/O amplification from both LSM-trees and SMR drives. Due to the lightweight compaction procedure, LWC-store reduces the write amplification by a factor of up to 5× compared to the popular LevelDB key-value store. Moreover, the random write throughput of the LWC-tree on SMR drives is significantly improved by up to 467% even compared with LevelDB on conventional HDDs. Furthermore, LWC-tree has wide applicability and delivers impressive performance improvement in various conditions, including different storage mediums (i.e., SMR, HDD, SSD) and various value sizes and access patterns (i.e., uniform and Zipfian).

Disk data density improvement will eventually be limited by the super-paramagnetic effect for perpendicular magnetic recording. Of the various new technologies being explored, Shingled Magnetic Recording (SMR) exposes as the most promising one to achieve high areal density and only make little changes to the manufacturing process. At present, high-capacity SMR drives are available from Seagate and HGST. Since SMR is leading next generation disk technology and increasing SMR drives will be used in storage systems, there is a great need to look over the current RAID storage techniques based on HDDs again. In this paper, we proposed a dynamic variable-width striping RAID (DVS-RAID) for SMR drives to reduce the parity updating cost. DVS-RAID never overwrites the old data, but always constructs a new full or partial stripe (variable-width stripe), and writes to the SMR drives through appending. In addition, taking the access characteristics of SMR drives into consideration, we present a new write cache management that exploits both spatial and temporal localities. The experiment with six real-world traces demonstrates that DVS- RAID exhibits a slightly lower performance than HDD- based RAID on update intensive workloads. However the performance of DVS-RAID is better than HDD-based RAID with sequential access, read-dominated workloads or workloads with rarely update.