Learned index has emerged as a new indexing technique that leverages machine learning to accelerate in-memory data processing. However, current learned indexes are primarily designed to index numeric keys and lack robust support for variable-length string keys. In this paper, we propose a novel in-memory learned index called LISK (LearnedIndex forStringKeys) to support string keys. The novelty of LISK is two-fold. First, we propose a trie-like structure to address the limitations of linear models in fitting string keys. Each trie node indexes 8-byte key slices, which are organized as learned sub-indexes or B+-trees. Second, we present a new structure for learned sub-indexes, namely TLS (Two-layerLearnedSubindex), which is tailored to handle the complex distribution of string keys. TLS utilizes three key designs to improve the overall performance: (1) a two-phase hybrid index construction, (2) a second-derivative-based data partitioning, and (3) a cachefriendly overflow node design. We conduct extensive experiments on five datasets and six workloads to compare LISK with seven existing indexes, including five trie-based indexes and the state-of-the-art learned index LITS. The experimental results show that LISK achieves an average 1.99× (up to 7.87×) higher throughput across the six workloads on real-world datasets. Specifically, compared with LITS, LISK achieves an average 1.42× (up to 1.91× ) higher throughput. The source code of LISK is available athttps://github.com/suibianll/LISK/tree/master.

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.

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.

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.

Buffer management is an essential technology for database management systems.Traditional buffer management employs an empirical approach based on access recency or frequency which fails to adapt to access-pattern changes in various database applications.In this paper, we present a new access-pattern-aware buffer manager called PBM (Personalized Buffer Manager), which can detect the access patterns for each database file and use a specific buffering policy for each database file.In particular, we propose a workload classifier to detect the access pattern of a database file.Then, we partition the buffer into various zones, set different sizes for each zone, and select the most suitable buffering scheme for each zone.With such a mechanism, each zone is responsible for caching a specific database file, and we can realize a personalized buffer manager for different database files, which can improve the buffer efficiency and reduce the page I/Os of the buffer manager.We compare PBM with three existing buffering algorithms, including LRU, LFU, and LeCaR, on two workloads, namely a regular workload and a shifting workload, which are composed of different access patterns.The results show that PBM outperforms the three competitors in terms of hit ratio and page I/Os.As a consequence, PBM achieves 1.66x, 2.03x, and 1.39x hit-ratio improvements compared to LRU, LFU, and LeCaR, respectively, on the regular workload.While on the shifting workload, PBM achieves 1.90x, 1.55x, and 1.49x higher hit ratios than LRU, LFU, and LeCaR, respectively.

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.

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.