LSM-tree has been widely used in key-value stores to offer high write throughputs. However, LSM-tree suffers from the block-cache invalidation problem caused by periodical compaction operations, which lowers the efficiency of the block cache and leads to poor read performance, especially for range queries. To address this problem, we propose a novel cache component named Range Cache to accelerate range queries on LSM-based key-value stores. The differences between Range Cache and the traditional block cache lie in two aspects. First, Range Cache caches the query results, i.e., key-value pairs, rather than data blocks. Second, in contrast to the traditional block cache that utilizes a hash table to index data, Range Cache incorporates an ordered index, which is more efficient for range queries. Further, we integrate Range Cache into LSM-based key-value stores without disturbing other components. With Range Cache, we can eliminate the impact of compaction operations on the block cache, avoiding the block-cache invalidation problem and reducing disk I/Os for point/range queries. We implement Range Cache on top of RocksDB and conduct system-to-system comparisons to compare Range Cache with LevelDB, RocksDB, LSbM-tree, and RemixDB under various settings. The experimental results show that Range Cache can significantly improve the cache efficiency and increase the throughput, especially for range queries.

Non-Volatile Memory (NVM) has emerged as an alternative to next-generation main memories. Although many tree indices have been proposed for NVM, they generally use B+-tree-like structures. To further improve the performance of NVM-aware indices, we consider integrating learned indexes into NVM. The challenges of such an integration are two fold: (1) existing NVM indices rely on small nodes to accelerate insertions with crash consistency, but learned indices use huge nodes to obtain a flat structure. (2) the node structure of learned indices is not NVM friendly, meaning that accessing a learned node will cause multiple NVM block misses. Thus, in this paper, we propose a new persistent learned index called PLIN. The novelty of PLIN lies in four aspects: an NVM-aware data placement strategy, locally unordered and globally ordered leaf nodes, a model copy mechanism, and a hierarchical insertion strategy. In addition, PLIN is proposed for the NVM-only architecture, which can support instant recovery. We also present optimistic concurrency control and fine-grained locking mechanisms to make PLIN scalable to concurrent requests. We conduct experiments on real persistent memory with various workloads and compare PLIN with APEX, PACtree, ROART, TLBtree, and Fast&Fair. The results show that PLIN achieves 2.08x higher insertion performance and 4.42x higher query performance than its competitors on average. Meanwhile, PLIN only needs ~30 μs to recover from a system crash.

Recently, Zoned Namespaces (ZNS) SSDs have emerged as a hot topic in both academics and industries. Compared to conventional SSDs, ZNS SSDs have the advantages of less overhead of garbage collection and lower over-provisioning cost. However, ZNS SSDs only accept sequential writes, and the zones inside ZNS SSDs need to be carefully managed to maximize the advantages of ZNS SSDs. Therefore, how to make data management systems adapt to ZNS SSDs is becoming a challenging issue. Current database systems, either SQL databases or NoSQL data stores, are mainly designed toward magnetic disks or traditional SSDs (without zoned namespaces). In this paper, we explore the challenges and research opportunities of revising index structures for ZNS SSDs and focus on the B+-tree and LSM-tree, which represent the index structures for SQL databases and key-value stores. After summarizing the features of ZNS SSDs, we discuss the key issues of adapting the B+-tree to ZNS SSDs and the challenges of revising the LSM-tree (Log-Structured Merge tree) for ZNS SSDs. Finally, we suggest some future research work on this topic.

With the rapid advance of Non-Volatile Memory (NVM), it has been a hot topic to improve traditional tree indices like B+-tree for NVM. However, due to the high cost of the writing operations on NVM, few existing tree indices can offer high performance for both read and write operations. For example, the WB-tree with unsorted leaf nodes is write-optimized but has poor search performance. To address this problem, in this paper, we propose a read/write-optimized tree index called TLBtree (Two-Layer B+-tree) for NVM. TLBtree consists of a read-optimized top layer and a write-optimized bottom layer. We notice that the top levels of a B+-tree are read frequently, while the bottom levels are written frequently. Motivated by such an observation, we propose to design a read-optimized top layer and a write-optimized layer for the TLBtree index. We offer several read optimizations to implement the top layer and employ write-optimized structures to organize the bottom layer. With this mechanism, we can alleviate the read and write tradeoff of the index on NVM. We conduct extensive experiments on a server with Intel Optane DC Persistent Memory and compare TLBtree with state-of-the-art NVM-based tree indices, including WB-tree, Fast&fair, and FPtree. The results show that TLBtree outperforms other indices in write-intensive workloads by up to 1.7x throughput and achieves comparable read-only performance with read-optimized indices.

Non-Volatile Memory (NVM) has emerged as an alternative to next-generation memories. Compared to the traditional DRAM, NVM offers data persistency and higher density. However, so far, NVM has higher accessing latency than DRAM. Therefore, to ensure the high performance of data accessing, we still need to consider using DRAM in memory architecture. This leads to the hybrid memory architecture involving DRAM and NVM. Some previous benchmark works have shown that such hybrid memory architecture is more efficient than NVM-only architecture. Due to NVM's unique properties, the traditional memory B+-tree becomes unsuitable for NVM because of its high cost of maintaining node orderliness and high space-filling feature. In this paper, we propose to optimize the Adaptive Radix Tree (ART) for the hybrid memory architecture and offer a new index called HART (Hybrid Adaptive Radix Tree). HART takes advantage of ART's deterministic structure to get good query performance. Meanwhile, we only selectively persist linked list to reduce NVM access cost. In particular, we exploit the compression path to improve the leaf node's space utilization, making the subtree shorter. We run a preliminary experiment on a server with Intel Optane DC Persistent Memory and compare HART with several NVM-aware indexes. The results suggest the efficiency of our proposal.

Non-volatile memory (NVM) as a new kind of future memory has several special properties such as non-volatility, read/write asymmetry, and byte address-ability. This makes it difficult to directly replace DRAM with NVM in the current memory hierarchy. Thus, a practical way is to construct a hybrid memory composed of both NVM and DRAM. Such hybrid memory architecture introduces many new challenges for existing algorithms. In this paper, we focus on the data placement issue in NVM-based hybrid memory systems, i.e., how to place the data on DRAM and NVM for a data-centric algorithm so that it can achieve high performance on hybrid memory. Particularly, we propose an optimal data placement model (ODP) to properly store data structures on DRAM and NVM during the execution of an algorithm. We present the theoretical proof to ODP to ensure the correctness of the model. To demonstrate the efficiency of ODP, we apply the ODP to two kinds of data-centric algorithms, namely sorting and database join. For sorting algorithms, we implement four ODP-based sorting algorithms, including Insertion Sort, Selection Sort, Heapsort, and Merge Sort. For join algorithms, we implement four ODP-based join strategies, including Nested Loops Join, Sort Join, Hash Join, and Virtual Partitioning Join. We conduct comparative experiments to evaluate the performance of the sorting/join algorithms. The results show that the ODP-based sorting/join strategies are much faster than the classical sorting/join algorithms that are not NVM-aware. In addition, the ODP-based implementation can reduce more NVM writes, showing that it is more NVM-friendly.