Designing an Efficient Tree Index on Disaggregated Memory

Memory disaggregation architecture physically separates CPU and memory into independent components, which are connected via high-speed networks (for example, RDMA), greatly improving resource utilization of datacenter systems. However, such an architecture poses unique challenges to data indexing due to limited memory access semantics and near-zero computation power at memory side. Existing indexes supporting disaggregated memory either suffer from low write performance or require hardware modification. We present Sherman , a write-optimized <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:msup> <mml:mi mathvariant="normal">B</mml:mi> <mml:mo>+</mml:mo> </mml:msup> <mml:mi>Tree</mml:mi> </mml:mrow> </mml:math> index on RDMA-enabled disaggregated memory. Sherman combines RDMA hardware features and RDMA-friendly software techniques to boost index write performance from three angles. First, to reduce round trips, Sherman coalesces dependent RDMA commands by leveraging in-order delivery property of RDMA. Second, to accelerate concurrent accesses, Sherman introduces a hierarchical lock that exploits on-chip memory of RDMA NICs. Finally, to mitigate write amplification, Sherman tailors the data structure layout of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:msup> <mml:mi mathvariant="normal">B</mml:mi> <mml:mo>+</mml:mo> </mml:msup> <mml:mi>Tree</mml:mi> </mml:mrow> </mml:math> with a two-level version mechanism. Our evaluation shows that Sherman is one order of magnitude faster compared with state-of-the-art designs in terms of both throughput and 99 th percentile latency on typical write-intensive workloads.