uKharon: A Membership Service for Microsecond Applications

Rachid Guerraoui, Antoine Murat, Javier Picorel, Athanasios Xygkis, Huabing Yan, Pengfei ZuoUSENIX ATC 2022 · OpenReview

TL;DR

Modern distributed applications demand microsecond-level responsiveness, especially when dealing with membership changes due to failures or reconfigurations. This paper introduces uKharon, a novel membership service designed for these ultra-low-latency scenarios, enabling applications to react to failures in as little as 50µs. uKharon achieves this by leveraging RDMA and a suite of specialized microsecond-aware components, significantly improving the tail latency of critical cloud services.

What Problem Does This Paper Address?

In today's data centers, applications are increasingly built on a microservices architecture, leading to complex request paths with many inter-service communications. This "fan-out" effect amplifies the impact of rare events like node failures or reconfigurations. Even small delays in detecting and reacting to these events can drastically increase the latency of the slowest requests (tail latency), negatively impacting user experience for services like online trading or analytics. Existing membership services, while robust, operate at millisecond scales, which is orders of magnitude too slow for microsecond-level applications. The challenge is to build a membership service that is not only fast in the common case but also incredibly quick to adapt to failures, all while minimizing overhead for the applications it serves.

Methods

uKharon tackles this challenge with three core, RDMA-optimized components:

  • Multi-level Failure Detector: Instead of a single, timeout-based detector, uKharon employs a hierarchy of specialized detectors. These target userspace failures (via kernel-level "deadbeats"), kernel failures, and catastrophic hardware failures, each with tailored detection mechanisms to achieve microsecond accuracy without false positives.
  • Microsecond Consensus Engine: This engine uses RDMA Compare-and-Swap (CAS) operations to achieve consensus on membership changes. It's designed to elect a new leader and decide on new memberships in just a few microseconds, making coordinator failures less impactful.
  • Microsecond Leases: To ensure real-time membership information for applications, uKharon uses short-lived leases (around 20µs). These leases allow applications to check membership status with minimal overhead, only requiring communication with coordinators when leases expire or need renewal.

Datasets

Not discussed in the paper. The paper focuses on system design and evaluation using custom benchmarks and existing systems for comparison.

Key Insights and Ideas

  • RDMA is Key for Microsecond Operations: The paper strongly emphasizes that achieving microsecond-level performance for membership services is only possible by deeply integrating with RDMA capabilities, particularly its one-sided verbs like CAS.
  • Specialized Failure Detection is Crucial: A one-size-fits-all failure detection approach doesn't work at microsecond scales. uKharon's multi-level approach, tailored to different failure types, is essential for fast and accurate detection.
  • Consensus Can Be Microsecond-Fast: By cleverly adapting Paxos to use RDMA CAS and optimizing for leader election and proposal phases, the authors demonstrate that consensus can indeed operate within the microsecond envelope.
  • Leases Balance Overhead and Responsiveness: Short, efficient leases are vital for providing real-time membership information to applications without introducing significant latency in the common case.
  • uKharon-KV as a Killer App: The development of uKharon-KV, a replicated key-value cache, serves as a compelling demonstration of uKharon's benefits, showing significant improvements in both latency and failover time compared to prior state-of-the-art.

Key Results

  • Failover Time: uKharon achieves end-to-end failover times as low as 53µs, a 10x improvement over previous systems like HERD+Mu (531µs).
  • Latency Overhead: The Active method, used by applications to check membership, adds a negligible 38ns latency in the 99th percentile when leases are renewed in time.
  • Throughput: Integrating uKharon into HERD (as Dynamic HERD) shows minimal throughput reduction (around 1.8% for batches of 6 requests), demonstrating good scalability.
  • Consensus Leader Election: uKharon's consensus engine can change leaders in under 10µs, significantly faster than comparable systems.
  • uKharon-KV Performance: uKharon-KV matches the PUT request latency of HERD+Mu in failure-free scenarios and offers 31.8% faster GET requests by eliminating the need for replication.

Limitations and Future Work

  • Byzantine Failures: uKharon does not address Byzantine failures, where nodes might exhibit malicious or arbitrary behavior.
  • Network Partitions: While uKharon assumes eventual resolution of network partitions by administrators, it doesn't actively handle them for liveness.
  • Adaptive Leases and Lease Caches: The paper discusses extensions like adaptive leases and lease caches to further improve scalability and handle network variations, but these were not fully implemented or evaluated in the presented work.
  • Durability: uKharon-KV, while demonstrating uKharon's capabilities, lacks the durability guarantees of systems like ZooKeeper.
  • Future Work: The authors suggest extending uKharon to support features like ZooKeeper's watches and locks, and further exploring the adaptive lease mechanisms for broader applicability.

Summary updated

BibTeX
@inproceedings{guerraoui2022ukharon,
  author = {Rachid Guerraoui and Antoine Murat and Javier Picorel and Athanasios Xygkis and Huabing Yan and Pengfei Zuo},
  title = {{uKharon: A Membership Service for Microsecond Applications}},
  booktitle = {USENIX ATC},
  year = {2022},
  url = {https://openreview.net/forum?id=gevriRGnmv},
}
Figure