Source-linked AI summary
Decoupling Disaggregated Memory Optimizations from Indexing: A Compiler-Runtime Approach
Xinpeng Zhao, Zeling Long, Chaichon Wongkham, Srijan Srivastava, Jiayi Liu, Baotong Lu, Tianzheng Wang, Eric Lo
TL;DR
Disaggregated memory makes irregular index accesses costly, while tightly coupled optimizations are difficult to reuse across indexes and hardware platforms. Nox uses compiler rewrites and a centralized runtime to adapt unmodified concurrent indexes, and its generated indexes scale robustly while beating or matching several hand-crafted baselines.
Problem
Remote-memory latency complicates pointer-dependent index accesses, while hand-crafted optimizations impose substantial per-index and per-platform redesign costs.
Method
Nox rewrites an unmodified concurrent index so a centralized runtime can provide reusable caching, address translation, placement, and remote-object mechanisms.
Results
Nox-generated B+-trees, hash tables, and skip lists scale robustly across tested RDMA and CXL workloads, outperforming SepHash by 1.4–16× and reaching 82%–1.01× of DEX.
Takeaways & Limitations
Disaggregated-memory optimizations can be generalized across indexes while preserving existing index code and scalability.
Takeaways & Limitations
Nox sometimes underperforms hand-crafted counterparts on uniform workloads at low core counts, and its RDMA runtime does not support memory pooling.
Abstract
from arXiv · showhide
Disaggregated memory (DM) decouples compute and memory into independently scalable pools, connected over a slower interconnect rather than a local bus. This decoupling is exactly what makes DM attractive--but it also means that every index must now reason explicitly about remote-memory access and its associated optimizations.State-of-the-art index designs respond to this by embedding remote-memory logic and optimizations directly into their core data structures and concurrency control mechanisms. Consequently, an optimization tuned for one index cannot be lifted and reused in another, and even the same index cannot be ported to a different DM architecture without a fresh round of redesign. This escalating, per-index, per-platform engineering burden is unsustainable as hardware and index requirements evolve. In this paper, we present Nox, a compiler-runtime framework that breaks this coupling by taking an unmodified, concurrent index as input and automatically generating its disaggregated-memory counterpart, without touching the original index logic. A compiler layer rewrites the index's LLVM IR to expose allocation, address, and pointer-dependency information that a centralized runtime uses to drive caching and address translation. Empirically, Nox-generated B+-trees, hash tables, and skip lists scale robustly on real RDMA and CXL hardware across every workload tested. They can also outperform some specialized, hand-crafted indexes and match others, especially on workloads that are closer to real-world ones. These results show that today's fastest disaggregated-memory optimizations need not stay locked inside monolithic, hand-crafted code--a compiler-runtime stack can generalize them while preserving the scalability of proven index implementations, without sacrificing it for portability.
1 INTRODUCTION
Disaggregated memory makes irregular, pointer-dependent index accesses expensive, while hand-crafted optimizations create per-index and per-platform redesign costs. Nox addresses this coupling with compiler-runtime co-design and achieves robust performance across indexes, workloads, and hardware.
- Motivation: Remote-memory latency makes data-dependent, pointer-intensive index accesses difficult to optimize with hardware prefetching.B+-tree traversals may scatter nodes across memory, adding latency at each remote access.
- Motivation: Hand-crafted disaggregated-memory indexes tightly couple caching, layout, pointer representation, concurrency, allocation, and update logic.Porting optimizations across indexes or from RDMA to CXL can require substantial redesign.
- Alternative approaches: AI-based optimization can shift engineering effort toward writing complete specifications, preventing reward hacking, and verifying concurrent-code correctness.The paper reports an attempted optimization that consumed over 1.5 million tokens and ultimately returned a linked-list instead.
- Nox: Nox rewrites an unmodified concurrent index and centralizes reusable remote object management, address translation, placement, and caching in a runtime.Compiler transformations expose information that runtime optimizations need while preserving the input index’s original logic.
- Evaluation: Nox-generated B+-trees, hash tables, and skip lists scale robustly on RDMA and CXL across YCSB and a real Twitter workload.They beat or match specialized indexes, including 1.4–16× better performance than SepHash and 82%–1.01× DEX performance.
2 BACKGROUND AND RELATED WORK
The background distinguishes DM hardware and surveys index, kernel, user-space, and compiler-runtime approaches. Existing methods trade transparency, granularity, performance, application changes, or support for concurrent indexes.
- Disaggregated Memory Architecture: Disaggregated memory separates compute and memory into independent pools connected by RDMA or CXL.The architecture provides near local DRAM and far memory accessed through the interconnect.
- Disaggregated Memory Architecture: RDMA provides one-sided remote operations, whereas CXL provides cache-coherent, byte-addressable pooled memory with conventional load/store semantics.The cited latencies are around 2 μs for RDMA and 500–660 ns for CXL-switched memory.
- Index Optimizations: Specialized indexes use local DRAM as an index-managed acceleration tier but remain tightly coupled to particular indexes and hardware.Examples include Sherman, Deft, DEX, SepHash, Shard, and CHash.
- Kernel-Space Solutions: Kernel-space approaches provide transparency at coarse granularity, while page-level migration can waste local memory on cold data co-located with hot objects.LegoOS trades performance for transparency, and page-level pollution is problematic for fine-grained database-index workloads.
- User-Space and Compiler-Runtime Solutions: User-space runtimes provide finer-grained management but may require language or runtime changes, application integration, or metadata manipulation on pointer dereferences.Clove targets garbage-collected languages, AIFM requires remoteable allocations, and compiler-runtime systems may lack multithreading support or performance.
3 DESIGN PRINCIPLES
Nox’s design principles emphasize low developer effort and reusable, index-aware optimizations rather than extensive rewrites or independently rebuilt implementations.
- High Programming Efficiency: Nox should require developers to provide a monolithic index with minimal modification and verification effort.This principle distinguishes Nox from hand-crafted and AI-based approaches.
- Index-Specific Optimizations: Nox should exploit index design and workload specifics rather than relying only on general-purpose operating-system or runtime policies.The supplied passage identifies this as the requirement for index-specific optimizations.
4 NOX DESIGN
Nox combines compiler rewrites with a centralized runtime to adapt unmodified concurrent indexes to disaggregated memory. Its design preserves original index operations while exposing allocation, address, and dependency information for runtime-managed translation and caching.
- Compiler-runtime architecture: Nox rewrites LLVM IR from an unmodified concurrent index, then links the transformed binary with a runtime that manages disaggregated memory.The compiler performs allocation/free rewriting, address translation, dependency tracking, and pointer unswizzling before generating the executable.
- Compiler-runtime architecture: The runtime manages index objects across local DRAM and disaggregated memory through object management, address translation, dependency tracking, and cache management.These components use compiler-exposed information to coordinate object placement, execution locations, access relationships, and compute-side caching.
- Memory management rewriting: Allocation rewriting redirects standard heap allocations to disaggregated memory while returning values that continue through the original program unchanged.Nox replaces allocation and deallocation calls with disaggregated-memory manager operations, while preserving the allocation result’s flow through the index.
- Address translation: The compiler preserves original memory operations and transforms their address operands, retaining atomicity and memory-ordering semantics while delegating address resolution and cache state to the runtime.This avoids reimplementing locks, atomics, and lock-free protocols inside a generic runtime.
- Dependency discovery: Nox discovers address dependencies from runtime pointer accesses, such as reaching a child through its parent, rather than relying on index-specific field names or pointer types.The runtime records dependencies dynamically and uses them to accelerate address translation and guide cache management.
- Cache management and safety: Dependency-aware caching keeps terminal objects in a cached set, but copied swizzled pointers during index splits can escape tracking and become stale after eviction.The runtime maintains terminal objects for efficient victim selection, while unswizzling may miss copied references such as A′→B.
5 IMPLEMENTATION AND DISCUSSION
Nox uses separate RDMA and CXL runtimes to provide disaggregated-memory support while leaving index logic unchanged. The implementation supports caching, address management, coherence strategies, and platform-specific access paths, but leaves several engineering opportunities for future work.
- Runtime implementation: Nox includes separate runtimes for RDMA and CXL disaggregated memory.The implementation contains approximately 9K lines of C++ built on LLVM and Clang 18.1.3.
- Runtime implementation: The RDMA runtime uses one-sided operations, registered per-thread buffers, and batched work requests to reduce communication overhead.Only the final request is signaled during chained submissions, reducing posting and completion-polling overhead.
- Runtime limitations: Nox’s CXL runtime supports memory pooling, whereas its RDMA runtime currently does not support multiple memory nodes.The RDMA implementation primarily demonstrates backward compatibility, while object placement can use standard hashing, range partitioning, or load-aware policies.
- Runtime implementation: The runtime can maintain cache coherence with existing protocols or avoid compute-side coherence through DEX’s single-ownership model.Under single ownership, each compute node independently maintains its object cache, dependency graph, pointer-swizzling state, and eviction metadata.
- Future work: The current runtime leaves prefetching, compute pushdown, and near-data computing as future or orthogonal extensions.Address-dependency information could support prefetching, while PIM, SmartNICs, and programmable switches could add near-data processing.
6 CAN DECOUPLING YIELD COMPARABLE PERFORMANCE?
Nox is evaluated by compiling concurrent B+-trees, hash tables, and skip lists, then comparing them with specialized indexes across RDMA and CXL settings. The generated indexes scale across all tested workloads, compete strongly with hand-crafted designs, and show their main performance gap on uniform low-core-count workloads.
- Evaluation setup: Nox compiles a B+-tree, extensible hash table, and skip list, comparing them with corresponding manually optimized indexes.The inputs are open-source, multithreaded indexes using conventional optimistic locking or lock-free implementations.
- Evaluation setup: The evaluation covers RDMA and CXL hardware, Twitter-Storage, uniform and skewed YCSB workloads, and read- to write-intensive operation mixes.YCSB uses 100 million keys and includes read-only, 5%-update, and 50%-update mixes after 10 million warm-up operations.
- Scalability: Nox-generated indexes scale across every evaluated disaggregated-memory configuration and workload.Several hand-crafted baselines stop scaling as contention increases in hard-coded caching logic.
- Comparison with specialized indexes: 1.4–16× hash-table speedups over SepHash and approximately 1% higher B+-tree performance than DEX occur in some settings.Nox’s local object caching reduces remote accesses, while its terminal-set maintenance lowers cache-management overhead relative to DEX’s recursive cooling.
- Comparison with specialized indexes: At high core counts, Nox outperforms SIDLE, Shard, and CHash on Twitter-Storage and skewed YCSB workloads.These results indicate that decoupling index design from platform-specific optimizations need not sacrifice competitive performance.
- Performance boundaries: Nox sometimes underperforms hand-crafted indexes on uniform workloads at low core counts.The paper attributes this regime gap to fewer caching opportunities and leaves additional runtime optimizations for future work.
- Additional comparison: Nox’s index-specific optimizations improve performance over Mira in the single-threaded RDMA setting.Mira lacks CXL and multithreaded execution, so the comparison is limited to the comparable configuration.
7 NOX INTERNAL EVALUATION
Nox’s internal evaluation examines pointer swizzling, cache capacity, and address-dependency-graph overhead across representative indexes and memory fabrics. The results show lower runtime costs from swizzling, workload- and index-dependent cache sensitivity, and generally small ADG space overhead.
- Pointer Swizzling: 29%/13%/7% on CXL and 42%/12%/9% on RDMA: pointer swizzling reduces runtime cost for the B+-tree/hash table/skip list.Most savings come from address translation, with additional savings from dependency tracking; the unswizzling check adds negligible cost.
- Pointer Swizzling: 25%/5%/7% on CXL and 24%/16%/8% on RDMA: swizzling reduces CPU cycles per index operation for the B+-tree/hash table/skip list.Swizzling does not increase branch misses and can reduce them by bypassing metadata lookup.
- Cache Capacity: At a 30% cache ratio, the B+-tree retains ∼92%/83% of peak throughput on CXL/RDMA, while the skip list retains ∼80%/60%.Throughput is normalized to the 100%-cache configuration, and performance improves with cache capacity.
- Cache Capacity: At a 30% cache ratio, the hash table reaches only ∼42% of peak throughput on CXL and 28% on RDMA.This makes the hash table substantially more sensitive to cache capacity than the B+-tree and skip list.
- Address Dependency Graph Footprint: The ADG incurs 1.55%/0.4% space overhead for the B+-tree/hash table and 10.81% for the skip list.The skip-list overhead reflects its input implementation’s many nodes and resulting address dependencies.
8 WILL AI TAKE NOX’S JOB?
The study finds that AI-generated optimization can work for a narrow workload but remains unreliable across broader index and workload settings. Nox therefore complements, rather than is replaced by, AI-driven index research.
- SkyDiscover generated thread-safe B+-tree code for both YCSB workloads within a USD 30 budget per workload, but failed for the remaining cases.The study was limited to the RDMA platform and tested B+-trees, hash tables, and skip lists.
- AI-generated B+-tree performance matched DEX and Nox on YCSB uniform read-intensive workloads but fell short on skewed and real workloads.
- Manual inspection found apparently efficient and scalable hash-table and skip-list outputs unsafe, requiring their rejection.
- Using an AI coding agent shifted work rather than eliminating it, because developers still refined specifications, fixed validators, and verified concurrent code.
- Nox can separate AI-driven discovery of index semantics from recurring, architecture-specific optimization for disaggregated-memory deployment.