Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store

Christopher Mitchell, Yifeng Geng, Jinyang LiUSENIX ATC 2013 · OpenReview

TL;DR

This paper introduces Pilaf, a novel key-value store that uses Remote Direct Memory Access (RDMA) for client-side reads, significantly reducing CPU overhead and boosting performance. By restricting RDMA to read operations and employing self-verifying data structures to handle potential races, Pilaf achieves over 1.3 million operations per second on a single CPU core, outperforming traditional systems by an order of magnitude.

What Problem Does This Paper Address?

Modern datacenters are increasingly adopting High-Performance Computing (HPC) networking features like ultra-low latency and CPU bypassing. However, effectively leveraging these features in general-purpose applications, particularly distributed systems, presents a significant challenge. Traditional distributed systems rely on servers to manage all requests, creating a CPU bottleneck. While RDMA offers a way to bypass the server's CPU for direct memory access, it introduces complex synchronization issues, especially when clients and servers concurrently access the same memory. This paper tackles the problem of how to build a fast and CPU-efficient distributed key-value store by strategically exploiting RDMA while mitigating its inherent complexities.

Methods

Pilaf's core innovation lies in its hybrid approach to handling operations:

  • RDMA for Reads (Gets): Clients directly use RDMA to read data from the server's memory. This bypasses the server's CPU entirely for read operations, drastically reducing latency and CPU load.
  • Server-Managed Writes (Puts): Write operations are still handled by the server using traditional verb messages. This simplifies synchronization, as the server can manage memory allocations and consistency for writes.
  • Self-Verifying Data Structures: To address the read-write races that can occur when clients perform RDMA reads while the server is modifying data, Pilaf employs self-verifying data structures. These structures include checksums on data objects and pointers, allowing clients to detect inconsistencies and retry operations if a race is detected.
  • Cuckoo Hashing: To improve memory efficiency and reduce the number of probes required for lookups, Pilaf utilizes n-way Cuckoo hashing, specifically 3-way Cuckoo hashing.

Datasets

Not discussed in the paper. The paper uses the YCSB (Yahoo! Cloud Serving Benchmark) to generate workloads with variable key and value lengths, mimicking real-world distributions.

Key Insights and Ideas

  • Strategic RDMA Use is Key: Not all operations need RDMA. By limiting RDMA to read-only operations (gets), Pilaf captures most of RDMA's benefits while significantly simplifying the design and avoiding complex write synchronization.
  • Self-Verifying Data Structures are Crucial for RDMA: The ability to detect and recover from read-write races without expensive locking protocols is essential for enabling client-side RDMA reads in a shared memory environment.
  • CPU Efficiency is a Major Win: The ability to saturate network hardware with a single CPU core is a game-changer for datacenter economics, allowing for denser packing of applications and reduced infrastructure costs.
  • HPC Networking is Entering the Datacenter: The paper highlights the trend of HPC networking features becoming more affordable and accessible, making it imperative to explore their application in mainstream systems.

Key Results

  • High Throughput: Pilaf achieves a peak throughput of 1.3 million operations per second (90% gets) using a single CPU core.
  • CPU Efficiency: Pilaf saturates the network hardware on a single core, whereas Memcached and Redis require significantly more CPU resources (estimated 17x more) to achieve comparable performance.
  • Low Latency: Pilaf offers very low end-to-end operation latency, with a 90-percentile latency of approximately 30µs.
  • Effective Race Detection: Self-verifying data structures effectively detect read-write races, with race detection rates dropping below 0.01% for tables with over 20,000 keys, even under peak load.
  • Performance Advantage: Pilaf outperforms Memcached and Redis (running over IPoIB) by over an order of magnitude in throughput for small operations.

Limitations and Future Work

  • RDMA for Writes Complexity: The paper acknowledges that using RDMA for writes would introduce significant complexity in terms of client synchronization and memory management, which they deliberately avoided.
  • Connection Reset for Resizing: While infrequent, resizing the hash table or the extent region requires resetting client connections, which can incur a small performance penalty.
  • Future Work: The authors suggest that as future datacenter networks increasingly adopt RDMA, it will be crucial to rethink the design of distributed systems to fully exploit these capabilities. They believe their work provides a blueprint for building high-performance, CPU-efficient systems.

Summary updated

BibTeX
@inproceedings{mitchell2013using,
  author = {Christopher Mitchell and Yifeng Geng and Jinyang Li},
  title = {{Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store}},
  booktitle = {USENIX ATC},
  year = {2013},
  url = {https://openreview.net/forum?id=fPdgC4WrMv},
}
Figure