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, traditional ART 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 <italic>Flat Inner Node Table</italic> to eliminate data dependencies among hierarchical ART nodes, enabling memory-level parallelism. Moreover, Sphinx introduces <italic>Succinct Filter Cache</italic>, which leverages a space-efficient cuckoo filter in the local cache of compute nodes to mitigate read amplification during index traversal. By further incorporating <italic>Semi Lock-free ART Nodes</italic>, Sphinx achieves high scalability with strong consistency guarantees. Experimental results show that Sphinx outperforms state-of-the-art counterparts by up to 7.3<inline-formula><tex-math notation="LaTeX">$\boldsymbol{\times}$</tex-math><alternatives><mml:math><mml:mo mathvariant="bold">×</mml:mo></mml:math><inline-graphic xlink:href="zheng-ieq1-3726609.gif"/></alternatives></inline-formula> in the YCSB benchmark.