Matchmaker Paxos: A Reconfigurable Consensus Protocol

Michael Whittaker, Joe Hellerstein's PhD pupil at UC Berkeley, has late defended his PhD thesis on Compartmentalized Paxos. The thesis deconstructs Paxos together with shows ways to reconstruct it to survive to a greater extent than scalable past times individually focusing on each component/role inwards Paxos. It is a unproblematic but effective trick. Even after you lot acquire the trick, you lot yet expire on getting surprised past times how effective it is.

When I say Michael defended his thesis, I am speaking loosely. Michael was non defensive near anything. He didn't receive got to be, his run spoke for him. Just lookout adult man his PhD presentation together with you lot volition sympathize what I mean. Michael has a peachy talent for explaining things simply. Unfortunately this is an underappreciated talent, peculiarly inwards academia. This may acquire into hold back also slow together with effortless, together with similar you lot didn't do sophisticated work. This dude did non fifty-fifty laid upwardly presentation slides for his PhD thesis (the heresy!), together with winged it on the wing past times drawing his protocols on an iPad. He drew effortlessly (which comes from hundreds of hours of practice) together with boiled downward everything to their simplest essence. This beingness inwards Berkeley, his thesis commission was sophisticated plenty to appreciate the simplicity of Michael's work. 

Michael was really generous inwards giving credit to collaborators. He did a long acknowledgment department at the goal of his presentation, unopen to other rare occurrence inwards PhD defenses. I had the pleasance of collaborating amongst Michael on Scaling Replicated State Machines amongst Compartmentalization newspaper (VLDB 2021). It was peachy collaborating amongst him together with Michael instantly comes across equally really overnice together with sort soul.

OK, dorsum to business. I am non going to speak near the whole thesis, but volition focus on i newspaper that came out of it. This paper is near reconfiguration inwards Paxos together with introduces Matchmaker (MM) sentiment for reconfiguring of Paxos. The sentiment is this: In add-on to Paxos proposers together with acceptors, MM employs an extra 2f+1 matchmaker nodes to concord the configurations used inwards electrical flow circular together with previous rounds. Notice the compartmentalization trick? 

How does MM compare amongst previous reconfiguration ideas?

Similar to Vertical Paxos, MM Paxos allows every round, non exactly every consensus instance/slot, to receive got a unlike configuration of acceptors. Round 0 of a consensus instance may job unopen to configuration C0, land circular 1 of the same consensus instance may job unopen to completely unlike configuration C1. MM is a realization/implementation of Vertical Paxos amongst a to a greater extent than integrated deployment to the Paxos protocol. Vertical Paxos requires an external master, which is itself implemented using state auto replication. The matchmakers inwards MM are analogous to that external master/Paxos-box together with demo that such a reconfiguration does non require a nested invocation of state auto replication.

Vanilla MultiPaxos together with Raft job log-based approach to reconfiguration. Pipelining of Paxos commands becomes a challenge for this approach. Paxos solves this past times limiting the length of the pipeline window to α > 0 together with alone activating the novel config Cnew chosen at slot i after slot i + α. Depending on the value of α, this approach either limits throughput or latency of the system. On the other hand, Raft does non impose whatsoever limitation of concurrency together with proposes 2 solutions. The commencement solution is to confine the reconfiguration operation, i.e. what tin survive reconfigured. For example, if each functioning alone adds i node or removes i node, a sequence of these operations tin survive scheduled to ambit arbitrary changes. The minute solution is to alter configuration inwards 2 phases: a spousal human relationship of both onetime together with novel configuration C+Cnew is proposed inwards the log first, together with committed past times the quorums combined. Only after the commit, the leader may suggest the novel config Cnew. During the 2 phases, whatsoever election or ascendancy proposal should survive committed past times quorum inwards both C together with Cnew. To ensure security during reconfiguration, all these solutions essentially forestall 2 configurations C together with Cnew to brand determination at the same fourth dimension that leads to divergent organisation states. (This paragraph explaining Paxos/Raft reconfiguration is requoted from our WPaxos paper.)

Unlike those MM (as good equally inwards Vertical Paxos) does non require a log together with is applicable to CASPaxos together with ePaxos.

MM reconfiguration

The newspaper emphasizes that MM reconfigures across rounds, non commands. Replication protocols based on classical MultiPaxos assume a totally ordered log of chosen commands, together with reconfigure across log entries: each log entry is handled past times a unmarried configuration. MM Paxos instead plant across rounds of consensus, equally proposed past times Vertical Paxos. Different Paxos rounds--even for the same command-- tin job unlike configurations. Every circular is statically assigned to a unmarried proposer together with that proposer selects a unmarried configuration for that round. A higher proposer overrides a lower proposer. (You tin recognize these ideas from Heidi's generalized consensus work.)

Since every circular uses a unlike configuration of acceptors, a Matchmaker Paxos proposer in the unoptimized case has to contact all of the configurations used inwards rounds less than i. (We volition speak over garbage collection later.) When a proposer begins executing circular i, it selects a configuration Ci. It sends the configuration Ci to the matchmakers, together with the matchmakers respond amongst the configurations used inwards previous rounds. This is called the Matchmaking phase. The proposer therefore executes Phase 1 of Paxos amongst the acceptors inwards these prior configurations, together with therefore executes Phase 2 amongst the acceptors inwards configuration Ci, equally illustrated inwards Figure 2.

Matchmaking MultiPaxos

Matchmaker MultiPaxos runs the Matchmaking stage together with Phase 1 alone during a leader change. The stable leader alone records configuration without doing phase1 clearing, together with tin yet safely alter configurations. A stable leader doesn't require matchmaking for learning the previous configurations, it exactly needs to shop the novel configuration to the matchmakers.

The stable leader tin easily alter configurations past times exactly writing to quorum of matchmakers (as inwards vertical paxos). There is no require to do phase1 clearing amongst the acceptors from onetime configurations because you lot are the same stable leader all along.

Retiring onetime configurations

If nosotros prematurely unopen downward the acceptors inwards Cj, therefore proposer p volition acquire stuck inwards Phase 1, waiting for Phase1B messages from a quorum of nodes that receive got been unopen down. Therefore, nosotros cannot unopen downward the acceptors inwards a configuration Cj until nosotros are certain that the matchmakers volition never in i trial again furnish Cj during the Matchmaking phase.

There are 3 situations inwards which it is rubber for a proposer pi inwards circular i to number a GarbageA⟨i⟩ command.

1. If the proposer pi gets a value x chosen inwards circular i,
2. If the proposer pi executes Phase 1 inwards circular i together with finds that no value has been or volition survive chosen inwards whatsoever circular less than i, 
3. If the proposer pi learns that a value x has already been chosen together with has been stored on f + 1 other machines ---then the proposer tin safely number a GarbageA⟨i⟩ ascendancy after it informs a Phase 2 quorum of acceptors inwards Ci of this fact.

Reconfiguring matchmakers

Ok, that is cool. Thanks to the matchmaker, nosotros brand configuration changes together with garbage collection onetime configurations super easy. But perhaps you lot are wondering: nosotros exactly punted the reconfiguration job past times introducing these matchmakers equally a score of indirection (which is itself a contribution), but what near the reconfiguration of the matchmaker nodes themselves?  

We tin unopen downward the onetime matchmakers together with supplant them amongst novel ones past times making certain that the novel matchmakers’ initial state is the same equally the onetime matchmakers’ in conclusion state. This is non efficient, but it is OK, because this happens rare together with tin survive pipelined amongst normal execution. The newspaper discusses how to do this.

Evaluation 

The evaluation shows trivial performance degradation. Reconfiguration has less than a 2% termination on median together with criterion divergence latency measurements (Section 8). This is because reconfiguration is pipelined/parallelized.

Share this post