In-memory learned index has been an efficient approach supporting in-memory fast data access. However, existing learned indexes are inefficient in supporting variable-length keys. To address this issue, we propose a new in-memory learned index called LIVAK that adopts a hybrid structure involving trie, learned index, and B+-tree. Each node indexes an 8-byte slice of keys, and we use learned indexes for large nodes but B+-trees for small nodes. Also, LIVAK presents a character re-encoding mechanism to avoid performance degradation. We compare LIVAK with B+-tree, Masstree, and SIndex on various datasets and workloads, and the results suggest the efficiency of LIVAK.

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.

Nonvolatile memory (NVM) suffers from more serious nonuniform memory access (NUMA) effects than DRAM because of the lower bandwidth and higher latency. While numerous works have aimed at optimizing NVM indexes, only a few of them tried to address the NUMA impact. Existing approaches mainly rely on local NVM write buffers or DRAM-based read buffers to mitigate the cost of remote NVM access, which introduces memory overhead and causes performance degradation for lookup and scan operations. In this article, we present NOBtree, a new NUMA-optimized persistent tree index. The novelty of NOBtree is two-fold. First, NOBtree presents per-NUMA replication and an efficient node-migration mechanism to reduce remote NVM access. Second, NOBtree proposes a NUMA-aware NVM allocator to improve the insert performance and scalability. We conducted experiments on six workloads to evaluate the performance of NOBtree. The results show that NOBtree can effectively reduce the number of remote NVM accesses. Moreover, NOBtree outperforms existing persistent indexes, including TLBtree, Fast&Fair, ROART, and PACtree, by up to$3.23\times $in throughput and$4.07\times $in latency.

Key-value stores (KVStores), such as LevelDB and Redis, have been widely used in real-world production environments. To guarantee data durability and availability, traditional KVStores suffer from high write latency, mainly caused by the long network and data-persisting time. To solve this problem, this article presents a novel data-persisting path for KVStores, allowing remote clients to persist data to the KVStore server with$\mu s$-level latency. The novelty of this study is threefold. First, we propose PMRDirect, which utilizes a persistent memory region (PMR) in the NVM express standard to construct a direct data-persisting path from the RDMA networking card (NIC) to the PMR region inside an SSD. Second, to showcase PMRDirect in KVStores, we developed a new accessing stack called PMRAccess, enabling remote clients to access existing KVStores and providing durability for each write request. Specifically, we present a low-latency RDMA-based messaging mode and a chunk-based PMR management in PMRAccess to reduce write latency and improve system throughput. Finally, we conducted extensive experiments to evaluate the performance of our proposals. We first compared PMRDirect with a few remote data-persisting paths to show its effectiveness. Then, we evaluated PMRAccess upon two KVStores, including LibCuckoo (an in-memory KVStore) and LevelDB (an in-storage KVStore). The results showed that PMRAccess outperformed the SSD-based accessing stack by up to$6.1\times $in write throughput and$36\times $in write tail latency, and it achieved$1.7\times $higher write throughput and$0.59\times $lower write tail latency over the PMEM-based accessing stack. Further, we conducted a system-to-system comparison between the PMRAccess-integrated LibCuckoo and Redis, and the results showed our proposal achieved up to$13\times $higher throughputs and$40\times $lower write latency than Redis.

In this paper, we propose a new space-efficient key-value store called ZoneKV for ZNS (Zoned Namespace) SSDs. We observe that existing work on adapting RocksDB to ZNS SSDs will cause fragmentation of zones and severe space amplification. Thus, we propose a lifetime-based zone storage model and a level-specific zone allocation algorithm to store SSTables with a similar lifetime in the same zone. We evaluate ZoneKV on a real ZNS SSD. The results show that ZoneKV can reduce up to 60% space amplification and maintain higher throughputs than two competitors, RocksDB and ZenFS.

So far, most LSM-tree-based storage engines adopt either leveling or tiering compaction. We note that while leveling compaction can deliver high search performance and low space amplification, it has a high rate of write amplification (therefore delivering poor write performance). On the other hand, tiering compaction has a low rate of write amplification (therefore delivering good write performance) but has poor search performance and high space amplification. Aiming to close the performance gap between leveling and tiering databases, this paper proposes a new storage engine called B+LSM. The novel ideas of B+LSM lie in two aspects: (1) B+LSM replaces the underlying level structure of LSM-tree with a B+-tree-like tree, and each tree node is defined as a Bundle Compaction Unit (BCU), whose size is allowed to be dynamically changed with workload statistics to balance read and write performance. (2) B+LSM proposes a new node-grained compaction scheme called Bundle Compaction. Bundle compaction is always triggered to merge all the data within a BCU node, partition them into bundles, and then send bundles to the children. Such a compaction scheme can take advantage of leveling and tiering compaction by auto-tuning the size of BCU nodes. We implemented B+LSM and compared it with LevelDB, RocksDB, PebblesDB, and L2SM on the YCSB workloads. The results show that B+LSM can achieve high time performance and reduce space amplification on both static and dynamic workloads.

Remote direct memory access (RDMA) supports zero-copy networking by transferring data from clients directly to host memory, eliminating the need to copy data between clients' memory and the data buffers in the hosting server. However, the hosting server must design efficient memory management schemes to handle incoming clients' data. In this paper, we propose a high-performance host memory management scheme called HM2 for RDMA-enabled distributed systems. We present a new buffer structure for incoming data from clients. In addition, we propose efficient data processing methods to reduce network transfers between clients and servers. We conducted a preliminary experiment to evaluate HM2, and the results showed HM2 achieved higher throughput than existing schemes, including L5 and FaRM.

Learned Indexes aim to use machine-learning models to predict the target addresses of requested data, which have been demonstrated efficient for in-memory data accesses. However, modern database systems mainly use flash-memory-based solid-state drives (SSDs) as storage devices, and current learned indexes fail to work on SSD-based databases. In this paper, we propose LIFM (Learned Index for Flash Memory), a new persistent and updatable learned index for flash-memory-based SSDs. Unlike existing learned indexes that aim to reduce memory access, LIFM is designed to reduce I/O costs. The novelty of LIFM lies in three aspects. First, LIFM proposes a hierarchical tree structure that combines the advantages of traditional B+-tree and in-memory learned indexes. Second, LIFM employs a model-based data placement scheme to reduce the page reads or writes. Third, LIFM uses a flash-memory-friendly storage layout to reduce additional access to flash memory. We conduct experiments on a real SSD and compare LIFM with B+-tree and two recently proposed learned indexes, ALEX and FITing-tree. The results suggest the efficiency of LIFM.

OLAP applications often perform aggregation queries, such as sum, avg, count, max, and min, to process a large dataset for getting a small result, and the key challenge for optimizing aggregation queries is to reduce the data volume needed to be read from disks. To address this problem, this paper presents an efficient caching component called FGCache (Fine-Grained Cache) for aggregation queries. FGCache is a query-driven caching policy, which aims to maintain the results of aggregation queries in the memory according to the predicates of user queries. The query results are divided into sets with fine-grained querying intervals, which are maintained via an in-memory tree index. We experimentally evaluate the performance of FGCache on various datasets and settings. The results suggest the efficiency and effectiveness of our proposal.

This paper proposes a novel learned index called DTtree that can optimize both read and write performance. DTtree adopts two novel designs. (1) To improve write performance, DTtree uses a dynamic filling rate and overflow buffers for each leaf node. The filling rate of a leaf node is dynamically determined according to the read/write tendency of the leaf node so as to improve space efficiency and reduce structure modification operations. In addition, DTtree uses an overflow buffer for a line in each leaf node. The overflow buffer is also dynamically allocated, and only write-intensive leaf nodes may have overflow buffers, reducing unnecessary space costs. (2) To improve read performance, we propose an in-node hot cache to cache hot records within a line of a leaf node, reducing additional memory access to the overflow buffer. As skewed access is common in real-world applications, using in-node hot caches can efficiently improve the read performance of DTtree. We experimentally evaluate DTtree on three datasets. The results on various workloads show that DTtree can reduce SMO operations effectively and achieve higher read/write performance than B+-tree and two representative learned indexes, PGM-Index and ALEX.

Hybrid memory composed of DRAM and persistent memory (PM) offers a promising way to realize large-capacity main memory supporting in-memory data storage and computing. However, traditional buffer management schemes focus on improving the hit ratio but lack awareness of the limitations of PM, e.g., slower write time and lower write endurance than DRAM. Therefore, developing new buffer management policies that can reduce costly write-backs of PM blocks while maintaining high performance for the hybrid buffer, is of paramount importance. Existing approaches mainly use a page-grained buffering policy, which will cause unnecessary data migrations between DRAM and PM, leading to a high number of disk I/Os and PM writes. Aiming to reduce I/O costs and PM writes, we propose a new buffer manager named HiBuffer for DRAM/PM-based hybrid memory systems. HiBuffer presents several novel ideas. First, it adopts multigrained data layouts to manage the hybrid buffer cooperatively. In addition to the page granularity, we introduce Lines for the DRAM buffer and Sectors to the PM buffer, forming a buffer with three granularities, including Line, Sector, and Page. We prove that the multigrained cooperative buffer management can deliver higher performance than existing page-grained schemes. Second, we propose a sector-grained method to migrate data from DRAM to PM, which can avoid unnecessary data movements and reduce PM writes. Third, we use an out-of-place updating mechanism to absorb updates in DRAM, which can further reduce the writes to PM. We compare HiBuffer with three existing schemes, including LRU, CLOCK-DWF, and MiniPage, on five synthetic workloads and the YCSB benchmark using real Intel Optane DC PM. The results in terms of various metrics, including running time, PM writes, hit ratio, and disk I/Os, suggest the efficiency of HiBuffer. In particular, HiBuffer reduces the running time by up to 37.8% and the writes to PM by up to 83% compared to the competitors when evaluated on the YCSB benchmark.

The emergence of new storage like persistent memory (PM) and zoned namespaces SSDs (ZNS-SSDs) introduces new challenges and opportunities for distributed key-value stores. Since LSM-tree has been widely adopted in distributed key-value stores, such as RocksDB and HBase, it is necessary to revisit the LSM-tree to make it adapt to new storage. In this paper, we first analyze the challenges of adapting the LSM-tree for new storage. Then, we propose a high-level architecture for a new-storage-aware LSM-tree-based key-value store called Hybrid-LSM. We explain the key structural issues of different storage layers in Hybrid-LSM and present some preliminary design ideas.

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) as a new type of storage technology has many advantages such as non-volatility, byte addressability, high storage-density, and low energy consumption.Meanwhile, NVM has some limitations, e.g., asymmetric read and write latency, limited write endurance, and high price.Therefore, at present, it is not realistic to completely replace DRAM with NVM in computer systems.A more feasible scheme is to adopt the hybrid memory architecture composed of NVM and DRAM.Following the assumption of hybrid memory architecture, this paper proposes an NVM-friendly sorting algorithm called NVMSorting.Particularly, we introduce a new concept called natural runs to improve the existing MONTRES algorithm and present the cost analysis of the algorithm in the hybrid memory architecture.In order to verify the performance of our proposal, we implement six existing sorting algorithms as baselines, including the MONTRES algorithm, and conduct comparative experiments on an unsorted dataset and a partially sorted dataset.The experimental results suggest the efficiency of NVMsorting in terms of execution time and NVM writes.Especially, on the partially sorted dataset, NVMSorting has 6.2% improvement on time performance and 5.7% reduction on NVM writes compared to MONTRES, and 13.0% performance improvement and 27.1% NVM-write reduction compared to the traditional merge sorting algorithm.

Non-volatile memory (NVM) has emerged as an alternative of the next-generation memory due to its non-volatility, byte addressability, high storage-density, and low-energy consumption. However, NVM also has some limitations, e.g. asymmetric read and write latency. Therefore, at present, it is not realistic to completely replace DRAM with NVM in computer systems. A more feasible scheme is to adopt the hybrid memory architecture composed of NVM and DRAM. Following the assumption of hybrid memory architecture, in this paper, we propose an NVM-friendly sorting algorithm called NVMSorting. Particularly, we introduce a new concept called Natural Run to improve the existing MONTRES algorithm. Further, we apply the proposed NVMSorting to database join algorithms to improve the performance of the existing sort-merge join. To verify the performance of our proposal, we implement six existing sorting algorithms as baselines, including the MONTRES algorithm, and conduct comparative experiments on real Intel Optane DC persistent memory. The results show that NVMSorting outperforms other sorting algorithms in terms of execution time and NVM writes. In addition, the results of the join experiment show that the NVMSorting algorithm achieves the highest performance among all schemes. Especially, in the partially ordered data, the execution time of NVMSorting is 2.9%, 2.7%, and 4.2% less than MONTRES, external sort, and quick sort, respectively. Also, the amount of NVM writes of the NVMSorting is 26.1%, 43.6%, 96.2% less than MONTRES, external sort, and quick sort, respectively.

The advance of byte-addressable persistent memory (PM) makes it a hot topic to revisit traditional tree indices such as B+-tree and radix tree, and a few new persistent memory-friendly tree indices have been proposed. However, due to the special features of persistent memory compared to DRAM and the limitations of B+-tree-like indices, it is much harder to optimize both search and write performance for tree indices on persistent memory. As a result, most existing indices for persistent memory, e.g., WB-tree, proposed to improve write performance while sacrificing search performance. Aiming to optimize both write and search performance for tree indices on persistent memory, in this paper, we first propose a novel Two-Layer Architecture (TLA) for constructing tree indices on persistent memory. The key idea, of TLA is to organize the index with a search-optimized top layer and a write-optimized bottom layer, letting the top layer optimize search performance and the bottom layer improve write performance. By adopting efficient structures for the two layers, TLA can boost both write and search performance for tree indices on persistent memory. Following the TLA architecture, we present a new index called TLBtree (Two-Layer B+-tree) offering high search and write performance for persistent memory. Moreover, we develop a concurrent TLBtree to support non-blocking read operations in multi-core environment. We evaluate our proposals under a server equipped with real Intel Optane persistent memory. The results show that TLBtree outperforms the state-of-the-art tree indices, including WB-tree, Fast&Fair, and FPTree, in both search and write performance. Also, the concurrent TLBtree can achieve up to 3.7x speedup than its competitors under the multi-core environment.

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.