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:
- Stop-the-World Reconfiguration: The entire system pauses processing requests while a new configuration is established. This leads to significant availability gaps.
- 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.
- 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.
- 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