ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems

Pengfei Li, Yu Hua, Pengfei Zuo, Zhangyu Chen, Jiajie ShengFAST 2023 · OpenReview

TL;DR

This paper introduces ROLEX, a novel key-value store designed for disaggregated memory systems that leverages RDMA for high performance. ROLEX achieves significant speedups, especially in dynamic workloads, by decoupling model retraining from data modifications and processing requests directly on compute nodes.

What Problem Does This Paper Address?

Modern datacenters are increasingly adopting disaggregated memory systems, which separate compute and memory resources into independent pools. This architecture offers benefits like improved resource utilization and scalability. However, efficiently managing data, especially for ordered key-value (KV) stores that support range queries, presents challenges. Existing solutions struggle with either high network latency due to multiple roundtrips or insufficient processing power on memory nodes for frequent data updates. Learned indexes, while promising for fast lookups, traditionally require retraining upon data modifications, which can be a bottleneck in disaggregated environments. This paper aims to bridge this gap by proposing a KV store that efficiently handles both static and dynamic workloads in disaggregated memory systems.

Methods

ROLEX introduces several key innovations:

  • RDMA-oriented Design: It fully leverages RDMA (Remote Direct Memory Access) for direct, low-latency access between compute and memory nodes, bypassing remote CPUs.
  • Retraining-Decoupled Learned Indexes: This is the core idea. ROLEX separates the process of updating data from the process of retraining the learned index model. This is achieved by adding a "bias" to the learned models and implementing data-movement constraints. This allows compute nodes to directly modify data in memory nodes without waiting for model retraining.
  • Leaf-Atomic Shift Scheme: To handle concurrent data insertions and avoid collisions, ROLEX uses a novel scheme for atomically allocating new memory "leaves" (fixed-size arrays) and managing synonym leaves.
  • Asynchronous Retraining: Model retraining is performed asynchronously on memory nodes, utilizing their dedicated computing resources (like FPGAs or ARM cores), rather than blocking critical data modification paths.
  • Shadow Redirection Scheme: Compute nodes use a shadow redirection scheme to identify updated models from memory nodes during subsequent reads.

Datasets

The paper evaluates ROLEX using:

  • YCSB (Yahoo! Cloud Serving Benchmark): A standard benchmark suite with various workloads (uniform and Zipfian distributions, read-heavy, write-heavy, mixed, and range queries).
  • Real-world datasets: Weblogs and DocID.
  • Synthetic datasets: Normal and Lognormal distributions.

No new datasets were introduced; the focus was on evaluating existing KV store designs on disaggregated systems.

Key Insights and Ideas

  • Decoupling is Key: The most significant insight is that separating data modification from model retraining is crucial for achieving high performance in disaggregated memory systems, especially for dynamic workloads.
  • Learned Indexes Can Be Dynamic: Contrary to traditional assumptions, learned indexes can be adapted for dynamic workloads in disaggregated environments by carefully managing data movement and retraining.
  • Compute Nodes are the Right Place for Operations: For disaggregated systems, performing data operations directly on compute nodes using RDMA is more efficient than relying on the limited resources of memory nodes for complex tasks.
  • Asynchronous Operations Pay Off: Offloading non-critical operations like model retraining to an asynchronous background process significantly improves the responsiveness of the main data path.

Key Results

  • Static Workloads: ROLEX achieves competitive performance with XStore-D on static (read-only) workloads.
  • Dynamic Workloads: ROLEX significantly outperforms state-of-the-art schemes by up to 2.2x on dynamic (read-write) workloads.
  • Write-Intensive Workloads: ROLEX shows substantial improvements in insert throughput (up to 2.1x, 1.8x, 4.5x, and 4.3x over FG, Sherman, EMT-D, and XStore-D, respectively).
  • Range Query Workloads: ROLEX improves performance by 67% over other schemes.
  • Scalability: ROLEX's performance scales well with the number of CPU cores on compute nodes.
  • Memory Footprint: ROLEX has a significantly lower memory footprint for metadata compared to tree-based structures, with models and leaf tables being cacheable on compute nodes.

Limitations and Future Work

  • Lock Contention: The paper acknowledges that lock contention among compute nodes can be an issue, especially when many compute nodes contend for the same leaf lock. They mention that sharing leaf locks among threads of the same compute node helps, but a more robust fallback mechanism for lock contention is identified as future work.
  • Emerging Heterogeneous Technology: While ROLEX benefits from emerging accelerators, the paper suggests exploring how to better integrate these technologies and address lock contention in such environments.
  • Network Bandwidth for Retraining Data: Although asynchronous retraining is efficient, transferring large amounts of data for retraining can still consume significant network bandwidth. The paper implies that further optimizations in data movement for retraining could be beneficial.

Summary updated

BibTeX
@inproceedings{li2023rolex,
  author = {Pengfei Li and Yu Hua and Pengfei Zuo and Zhangyu Chen and Jiajie Sheng},
  title = {{ROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems}},
  booktitle = {FAST},
  year = {2023},
  url = {https://openreview.net/forum?id=DBseBuytqM},
}
Figure