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.

Improving software-managed cache efficiency is an important issue for various modern applications. Although LRU (Least Recently Used) has been widely used as the default replacement policy in many key-value caches, it suffers from low concurrency performance caused by frequent list updates. However, existing concurrency-aware schemes like FIFO sacrifice the LRU’s temporal locality of data access, leading to a drop in the cache’s hit ratio. In this work, aiming to improve the concurrency performance of cache management while maintaining a high hit ratio as LRU, we propose a novel concurrency-aware cache replacement policy called SEMU (SEgment-based MUlti-version cache replacement) that outperforms state-of-the-art schemes. The novelty of SEMU lies in two aspects. First, it uses an appendonly segment-based FIFO list to avoid locking the list, yielding high concurrency performance. Second, it adopts a multi-version mechanism to make the cache aware of the temporal locality of data access, which can offer a high hit ratio as LRU. With such designs, SEMU can offer high concurrency performance and a high hit ratio for the cache.We conduct extensive experiments on both synthetic and real world workloads to compare SEMU with a few existing schemes, including LRU, FIFO, 2Q, and FrozenHot. We also implement SEMU into a real key-value store, RocksDB, and perform a system-to-system evaluation. The performance comparison under the YCSB workloads shows that SEMU can efficiently improve the performance of RocksDB with the consideration of data concurrency. Particularly, in the multi-thread concurrent environment, SEMU averagely outperforms LRU, 2Q, FIFO, and FrozenHot by up to 1.9×, 1.6×, 80%, and 102% under the synthetic workloads and improves the throughput of RocksDB configured with default settings by up to 59.67% under the system-to-system comparison.

Cache management is a critical concern for both key-value stores and relational DBMSs. The most significant challenge in cache management is the cache replacement strategy, which directly affects the throughput and latency of the cache manager. While the Least Recently Used (LRU) policy is widely adopted by many systems, it suffers from severe performance degradation in multi-threaded environments due to lock contention. This contention arises when multiple threads attempt to update the LRU list simultaneously. Motivated by this issue, we propose a new cache management scheme called twCache, designed to deliver high performance in concurrent environments. The novelty of twCache lies in two key aspects. First, it proposes to partition the replacement policy data structure into thread-wise sublists, each corresponding to one thread. Such a structure can enable thread isolation so that the requests from one thread will not introduce lock contention with other threads, yielding high concurrency performance. Second, we propose a low-cost technique to combine recency and hotness for victim selection during cache replacement. Each sublist is maintained as an LRU list, representing the recency of object requests. Each cached object's hot count is proposed to reflect its hotness, defined as the number of sublists visiting the object. We conducted extensive experiments to compare twCache with traditional algorithms (LRU, FIFO, and 2Q) and the state-of-the-art FrozenHot policy. Three types of trace are used, including 39 Twitter traces, 23 MSR traces, and 6 YCSB workloads. The results show that twCache achieves$12\times$and$7\times$higher throughputs than LRU on the Twitter and MSR traces, respectively. Meanwhile, twCache outperforms LRU by$4.8\times$in the average throughput under YCSB workloads.

Multi-tenancy is a crucial criterion for cloud service providers since it enables them to share resources among tenants, thus reducing costs. As all tenants share the same buffer space in the cloud server, a tenant’s overall performance will be affected by other tenants. Thus, developing an efficient buffering scheme to ensure tenant isolation becomes an urgent need. Aiming to solve this problem, this paper proposes a novel buffering scheme for managing the shared buffer in a multi-tenant cloud database. We first present an SLA (Service Level Agreement)-based model to quantify the buffering performance of each tenant. Then, we propose MTRP (Multi-Tenant Replacement Policy) for multi-tenant scenarios. The novelty of MTRP lies in three aspects: (1) it partitions the buffer into logical zones to implement tenant isolation. Each zone manages the pages one tenant uses, but the zone space can be dynamically adjusted by buffer replacements; (2) it proposes a two-step replacement algorithm, including global replacement and local replacement, which can improve space efficiency and reduce the SLA cost; (3) it adopts a reinforcement learning model to select the most appropriate zone for page replacement. The experimental results on various multi-tenant workloads show that MTRP achieves a higher hit ratio and lower SLA costs than LRU, LFU, LRU-2, and LeCaR.

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.

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.

Cloud services such as multi-tenant content delivery networks (CDN) have become a trend because they can offer personalized business support for users. However, as the business modes of different users are usually different, it is not appropriate to use a single cache strategy on cloud servers. First, a single cache cannot adapt to various access patterns of tenants. Second, a single cache will also affect the isolation among different users. In this paper, we propose MyCache, a new framework to deliver personalized cache management for multi-tenant cloud services. We first discuss the impact of access patterns, which motivates MyCache. Then, we briefly introduce the architecture of MyCache, and finally, we present preliminary experimental results to show the feasibility and superiority of our proposal.

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.