DepFast: Orchestrating Code of Quorum Systems

Xuhao Luo, Weihai Shen, Shuai Mu, Tianyin XuUSENIX ATC 2022 · OpenReview

TL;DR

Building reliable and high-performance distributed quorum systems is notoriously difficult due to complex state transitions and asynchronous event handling, often leading to "callback hell." This paper introduces DepFast, a novel framework that enables developers to write these complex systems using a synchronous, coroutine-based style, significantly simplifying development and maintenance without sacrificing performance.

What Problem Does This Paper Address?

Distributed systems like replicated state machines (e.g., Raft, Paxos) are critical for modern infrastructure, but their implementation is a significant challenge. The core difficulty lies in managing complex state transitions triggered by various asynchronous events (like network messages and timeouts). Traditional approaches use an event-driven, callback-based style, which, while potentially performant, quickly becomes unmanageable, leading to code that is hard to read, debug, and maintain – often referred to as "callback hell." While synchronous programming with coroutines can simplify code, existing solutions struggle to handle the intricate, multi-event branching logic inherent in quorum systems. This paper aims to bridge this gap by providing a framework that combines the expressiveness of synchronous programming with the necessary abstractions for complex distributed systems.

Methods

The core of DepFast is its QuorumEvent abstraction, which allows developers to express complex waiting conditions involving multiple events (like RPC replies and timeouts) in a unified, synchronous manner. Instead of managing individual callbacks, developers can define a QuorumEvent that waits for a specific quorum of sub-events to complete. This abstraction is integrated into a coroutine-based framework that provides cooperative scheduling. This means that tasks run within a single thread, avoiding the overhead of OS threads while allowing for efficient context switching between coroutines when they encounter waiting points. DepFast also offers other event types (ValueEvent, IOEvent) and compound events (AndEvent, OrEvent) to further enhance expressiveness.

Datasets

Not discussed in the paper. The evaluation uses custom workloads and fault injection rather than pre-existing datasets.

Key Insights and Ideas

  • Synchronous Style for Complex Systems: The paper demonstrates that complex quorum system logic, which was previously only manageable with asynchronous callbacks, can be elegantly expressed using a synchronous, coroutine-based approach with the right abstractions.
  • QuorumEvent as a Game Changer: The QuorumEvent abstraction is the key innovation, allowing developers to naturally express waiting for a "majority of replies" or similar conditions, which is fundamental to quorum systems but notoriously difficult with traditional callback patterns.
  • Fail-Slow Tolerance by Design: DepFast's design encourages waiting on quorums of events rather than individual events, inherently making systems more resilient to fail-slow nodes. This is because a single slow node won't block the entire coroutine indefinitely.
  • Simplified Debugging: By maintaining a single, un-ripped stack for the main control flow, DepFast significantly simplifies debugging, especially for complex issues like fail-slow behavior.

Key Results

  • Code Reduction: Implementations of Raft and Copilot using DepFast required 25%-35% fewer lines of code compared to their state-of-the-art counterparts.
  • Comparable Performance: DepFast-based implementations achieved performance comparable to highly optimized systems like etcd and the original Copilot implementation, demonstrating that the ease of development does not come at a performance cost.
  • Improved Fail-Slow Tolerance: DepFast-based systems showed better resilience to fail-slow faults, with throughput and latency differences within acceptable ranges (e.g., <15% for Raft, <30% for Copilot) even under fault injection.
  • Expressiveness Showcase: The paper provides compelling examples, particularly with the Copilot implementation, illustrating how DepFast allows for a more direct and readable translation of complex protocol algorithms into code.

Limitations and Future Work

  • Limited Scope of Evaluation: The artifact evaluation includes experiments for Raft and Copilot but does not include comparisons with etcd or experiments from Appendix B.
  • Potential for CPU Contention: While DepFast's coroutine model minimizes thread-related issues, it relies on a single worker thread, which could become a bottleneck under extremely high CPU load. The paper suggests that sharding the system into different threads is a viable strategy for scaling.
  • Future Work: The authors plan to explore using DepFast for other distributed systems, such as sharded datastores with distributed transactions, and investigate integrating DepFast's abstractions with C++20 coroutines and actor models in languages like Erlang/Scala. They also aim to further develop DepFast's fail-slow analysis capabilities.

Summary updated

BibTeX
@inproceedings{luo2022depfast,
  author = {Xuhao Luo and Weihai Shen and Shuai Mu and Tianyin Xu},
  title = {{DepFast: Orchestrating Code of Quorum Systems}},
  booktitle = {USENIX ATC},
  year = {2022},
  url = {https://openreview.net/forum?id=r8S4loDnRN},
}

Loading related content...

Figure