[Solution] Matchmaker Paxos: A Reconfigurable Consensus Protocol

Michael J. Whittaker, Neil Giridharan, Adriana Szekeres, Joseph M. Hellerstein, Heidi Howard, Faisal Nawab, Ion Stoica

Introduction

Distributed systems rely on consensus protocols like Paxos and Raft to maintain a consistent state across multiple machines. These protocols are essential for building reliable databases, coordination services, and distributed logs. However, a persistent challenge in these systems is reconfiguration—the process of changing the set of machines (the "configuration") that participate in the protocol. Whether due to hardware failure, maintenance, or the need to scale up or down, reconfiguration is a necessary but often disruptive event.

Matchmaker Paxos is a novel reconfigurable consensus protocol designed to make membership changes fast, frequent, and nearly invisible to the system's performance. By introducing a dedicated set of "matchmaker" nodes, the protocol decouples configuration management from the primary data processing path.

The Problem: The Cost of Change

In traditional consensus implementations, reconfiguration is often treated as an exceptional event. Two common approaches exist:

  1. Stop-the-World Reconfiguration: The entire system pauses processing requests while a new configuration is established. This leads to significant availability gaps.
  2. Horizontal Reconfiguration: Membership changes are treated as special entries in the data log. While this avoids a full pause, it ties reconfiguration to specific log indices, which can be slow and complex to manage in highly dynamic environments like the modern cloud.

In environments utilizing spot instances or serverless functions, nodes may join and leave the cluster frequently. Existing methods are often too heavy-handed for these "elastic" scenarios, leading to performance degradation or increased complexity.

Methods: The Matchmaker Innovation

The authors of Matchmaker Paxos introduce a new architecture centered around two key concepts: Matchmaker Nodes and Vertical Reconfiguration.

Matchmaker Nodes

Instead of requiring every node in the cluster to maintain an up-to-date view of the current membership, the protocol introduces a small, dedicated set of "matchmaker" machines. These nodes act as a source of truth for configuration history. When a leader (proposer) wants to initiate a new round of consensus, it first communicates with the matchmakers. The matchmakers provide the leader with the history of previous configurations and record the leader's intent to use a new configuration.

Vertical Reconfiguration

Unlike horizontal methods that reconfigure at specific log positions, Matchmaker Paxos reconfigures across rounds. This "vertical" approach allows every single round of consensus to potentially utilize a completely different set of acceptors. This flexibility is crucial for rapid scaling and fault tolerance.

Protocol Phases and Optimization

The protocol follows a structure similar to classic Paxos but with integrated matchmaking.

The two phases of the Paxos protocol. Matchmaker Paxos optimizes these interactions by decoupling configuration management from the data path.
  1. Phase 1 (Discovery): The leader contacts matchmakers to learn about previous configurations and then contacts a quorum of acceptors from those configurations to ensure no previous values were chosen.
  2. Phase 2 (Accept): Once the leader has "cleared" previous rounds, it proposes a value to a quorum of acceptors in the current configuration.

To ensure Matchmaker Paxos remains as fast as standard Paxos, the authors implement Phase 1 Bypassing. If the matchmakers can prove that no values were chosen in any previous rounds, the leader can skip the expensive discovery phase and move directly to proposing values. This makes the transition to a new configuration nearly instantaneous.

Key Insights

  • Decoupling is Key: By moving configuration metadata to matchmakers, the "data path" (the acceptors) is freed from the burden of tracking cluster membership. This removal of reconfiguration from the critical path is what enables high performance.
  • Broad Applicability: Because the protocol reconfigures based on rounds rather than log indices, it can be adapted to a variety of consensus protocols beyond standard MultiPaxos, such as EPaxos or CASPaxos.
  • Formal Safety: The authors provided a formal safety proof for the protocol, ensuring that even under frequent reconfigurations and node shutdowns, the system maintains data integrity and consistency.

Results and Evaluation

The protocol was evaluated using the frankenpaxos framework on AWS EC2 m5.xlarge instances. The researchers measured the overhead of the protocol under a "no-op" state machine benchmark.

The results were impressive:

  • Minimal Performance Impact: In stress tests where the cluster was reconfigured every single second, the impact on median throughput and latency was less than 4%.
  • Rapid Reconfiguration: Moving to a new set of machines typically takes only a few milliseconds, roughly equivalent to a single network round-trip.
  • Resilience: The system demonstrated the ability to handle leader and matchmaker failures gracefully, with recovery times under two seconds.

Conclusion

Matchmaker Paxos represents a significant step forward in making distributed systems more elastic and resilient. By transforming reconfiguration from a disruptive "event" into a routine, low-overhead operation, it allows systems to adapt to changing infrastructure and workloads with unprecedented agility. Future work aims to apply this "matchmaking" philosophy to even more complex distributed protocols, further hardening the foundations of modern cloud infrastructure.

Summary updated

Abstract

State machine replication protocols, like MultiPaxos and Raft, are at the heart of numerous distributed systems. To tolerate machine failures, these protocols must replace failed machines with new machines, a process known as reconfiguration. Reconfiguration has become increasingly important over time as the need for frequent reconfiguration has grown. Despite this, reconfiguration has largely been neglected in the literature. In this paper, we present Donut Paxos and Donut MultiPaxos, a reconfigurable consensus and state machine replication protocol respectively. Our protocols can perform a reconfiguration with little to no impact on the latency or throughput of command processing; they can perform a reconfiguration in a few milliseconds; and they present a framework that can be generalized to other replication protocols in a way that previous reconfiguration techniques can not. We provide proofs of correctness for the protocols and optimizations, and present empirical results from an open source implementation showing that throughput and latency do not change significantly during a reconfiguration.
BibTeX
@article{whittaker2021solution,
  author = {Michael J. Whittaker and Neil Giridharan and Adriana Szekeres and Joseph M. Hellerstein and Heidi Howard and Faisal Nawab and Ion Stoica},
  title = {{[Solution] Matchmaker Paxos: A Reconfigurable Consensus Protocol}},
  journal = {J. Syst. Res.},
  year = {2021},
  doi = {10.5070/sr31154842},
}
Figure