High-Performance and Cache-Efficiency Adaptive Radix Tree for Disaggregated Memory

Abstract: Disaggregated memory (DM) architectures enhance resource utilization and architectural scalability by separating computing and memory resources into distinct pools connected via high-speed interconnects, such as RDMA and CXL. Adaptive radix tree (ART) is a widely used range index known for its efficient support of variable-sized keys. However, traditionalART structures incur substantial network overhead in DM architectures during index traversal. In this paper, we propose Sphinx, a high-performance and cache-efficient ART for DM architectures. To minimize network roundtrips during index traversal, Sphinx employs Flat Inner Node Table to eliminate data dependencies among hierarchical ART nodes, enabling memory-level parallelism. Moreover, Sphinx introduces Succinct Filter Cache, which leverages a space-efficient cuckoo filter in the local cache of compute nodes to mitigate read amplification during index traversal. By further incorporating Semi Lock-free ART Nodes, Sphinx achieves high scalability with strong consistency guarantees. Experimental results show that Sphinx outperforms state-of-the-art counterparts by up to 7.3× in the YCSB benchmark.