A Lock-free RDMA-friendly Index in CPU-parsimonious Environments

In CPU-parsimonious environments, such as disaggregated memory systems, the limited CPU power on the memory side constrains the ability to perform more operations. Thus, reducing CPU usage and enhancing concurrency performance are critical for indexing key-value storage in these scenarios. Current hash indexes support one-sided RDMA access and lock-free concurrency control with good performance but lack range query support. In contrast, existing tree indexes support range query but only implement expensive locks for concurrency control. Therefore, designing a tree index that supports lock-free concurrent access and one-sided RDMA is a significant challenge. To address these issues, this paper proposes a lock-free tree index based on the van Emde Boas (vEB) tree, called vBoost. vBoost inherits the vEB tree’s characteristics of index nodes without splitting or merging, and simplifies concurrency control by managing changes at a single node. It redesigns tree nodes with an 8-byte compact data structure, allowing each key-value pair to support RDMA_CAS atomic operations for lock-free concurrency. Additionally, vBoost leverages the RDMA Doorbell technique to reduce RTTs, enhancing range query and write performance. Evaluation results show that, vBoost achieves up to 3.85× higher throughput and better scalability under YCSB workloads compared to state-of-the-art tree indexes.