OpenACID Blog

Adaptive Membership Changes in OpenRaft: Skip Joint Consensus When Quorums Overlap

· Zhang Yanpo (drdr.xp)

Article link: https://blog.openacid.com/distributed/raft-adaptive-config-change/

OpenRaft now skips joint consensus whenever the old and new configurations have quorum overlap: every old quorum shares at least one node with every new quorum.

For Raft::change_membership(), that means two possible paths:

  • With quorum overlap, write one entry containing the new configuration.
  • Without quorum overlap, write a joint configuration first, then the new configuration: two entries in total.

The idea follows from the purpose of joint consensus. A joint configuration lets us cross from the old configuration to the new one in two steps, each with the required quorum overlap. If the old and new quorums already overlap, we can make that transition directly.

For configurations that use majority quorums, OpenRaft can test this condition exactly in linear time. Raft’s familiar single-server change rule—adding or removing one node at a time—is a simpler way to guarantee the same property. The exact test also admits a few changes involving two nodes.

1. Joint consensus provides quorum overlap at each step

Let C0 be the old configuration, C1 the new one, and C01 = [C0,C1] their joint configuration. Write C0 ~ C1 when every quorum of C0 intersects every quorum of C1. A direct transition from C0 to C1 requires this property; Section 3 of Raft Membership Changes: When a Leader Must Commit a Current-Term Entry First explains why.

Joint consensus splits a configuration change into two transitions that each preserve quorum overlap. Every quorum of C01 contains a quorum of C0 and a quorum of C1. As a result, C0 ~ C01 and C01 ~ C1 always hold, even when C0 ~ C1 does not.

| Joint change, two entries:
|
|     C0 -----> C01 -----> C1
|        C0 ~ C01   C01 ~ C1
|
| When C0 ~ C1, one entry:
|
|     C0 ----------------> C1

When C0 ~ C1 already holds, we can go straight to C1. The joint step would add an entry and another wait for commitment without providing any additional overlap.

There is one other requirement: the leader must first commit an entry from its own term. Skipping that barrier allows the bug described in The Pitfalls of Raft Membership Change; the article on membership log barriers explains the failure in detail.

OpenRaft already enforces this barrier for every membership change. It returns UncommittedLeaderLog until the first entry the leader writes after its election has committed. With that requirement satisfied, the choice between a direct change and joint consensus comes down to C0 ~ C1.

2. Majority sizes give us an exact overlap test

For a configuration C that uses majority quorums, define its majority size as maj(C) = ⌊|C|/2⌋ + 1. Two such configurations have quorum overlap exactly when their majority sizes add up to more than the number of distinct nodes across both configurations:

C0 ~ C1 if and only if maj(C0) + maj(C1) > |C0 ∪ C1|.

We only need to compute one set union. The work is linear in the total number of nodes in the two configurations. Enumerating all possible quorums to check the definition directly would take exponential time.

To see why the test works, suppose we can pick an old quorum and a new quorum that share no nodes. Together, they occupy at least maj(C0) + maj(C1) distinct nodes, all within C0 ∪ C1. That requires maj(C0) + maj(C1) ≤ |C0 ∪ C1|.

The converse holds too. If maj(C0) + maj(C1) ≤ |C0 ∪ C1|, build each quorum from nodes unique to its configuration first. Then fill any remaining places with shared nodes, assigning each shared node to only one quorum. The inequality guarantees enough nodes to finish both quorums without overlap.

Adding or removing one node always passes the overlap test. When we add one node, C1 contains all of C0, so |C0 ∪ C1| = |C1| = |C0| + 1. The two majority sizes add up to:

maj(C0) + maj(C1) = ⌊|C0|/2⌋ + ⌊(|C0|+1)/2⌋ + 2 = |C0| + 2

That is one more than the size of the union, so quorum overlap is guaranteed. Removing one node gives the same result with C0 and C1 exchanged. The exact test also tells us when a change involving two nodes can skip joint consensus:

Change Exact test One-node-at-a-time rule
{a,b,c} → {a,b,c,d} Overlap Allowed
{a,b,c} → {b,c,d} No overlap: quorum {a,b} of C0 and quorum {c,d} of C1 share no nodes Not allowed
{a,b,c,d} → {a,b,c,e} Overlap Not allowed

The exact test admits three kinds of changes beyond the one-node-at-a-time rule. All three start and end with an even number of voters:

  • Replace one voter: {a,b,c,d} → {a,b,c,e}.
  • Add two voters: {a,b,c,d} → {a,b,c,d,e,f}.
  • Remove two voters: {a,b,c,d} → {a,b}.

Checking the even and odd cases in the formula shows that these are the only additional possibilities. Production clusters usually have an odd number of voters. Starting from an odd-sized configuration, the exact test permits the same changes as the one-node-at-a-time rule.

3. OpenRaft chooses the next configuration with bridge_to()

Commit c90c6b53 brings this test to Raft::change_membership(). It uses bridge_to() from quorum-set 0.3.0, the library OpenRaft uses for quorum calculations, to choose the next configuration.

When the current configuration is not joint, bridge_to() applies the exact test from Section 2. If the quorums overlap, it returns the target configuration, completing the change with one entry. Otherwise, it returns the joint configuration C01. change_membership() waits for that entry to commit before appending the target configuration.

Adding or removing one voter therefore takes a single entry. So do the three additional cases involving even-sized configurations. Replacing all three voters in {a,b,c} → {d,e,f} still goes through joint consensus: the old and new quorums have no overlap.

Before this change, change_membership() wrote a joint configuration whenever the voters changed. It now takes the direct path whenever the overlap test permits it.

4. How 21 other Raft implementations choose the transition

The 21 implementations below fall into three groups. Each code link is pinned to the commit examined.

Six implementations use the number of changes to decide whether to skip joint consensus:

Implementation Condition for skipping joint consensus Code
etcd-io/raft The request uses ConfChangeTransitionAuto and contains exactly one change raftpb/confchange.go:85-91
tikv/raft-rs The same conditions as etcd-io/raft proto/src/confchange.rs:134
TiKV The request contains at most one change, in which case TiKV sends ConfChangeTransitionAuto util.rs:982
CockroachDB The request contains exactly one change, and that change does not demote a voter replica_command.go:1978
braft The total number of nodes added and removed is at most one node.cpp:3296
Redpanda Each learner is promoted to voter individually, skipping joint consensus. Removing a voter always uses joint consensus consensus.cc:550, group_configuration.cc:1391

Six implementations use joint consensus whenever the voters change: SOFAJRaft, Apache Ratis, LogCabin, ScyllaDB, Zeebe (Camunda’s Atomix Raft), and RethinkDB.

Nine implementations support only one-node-at-a-time changes, with no joint consensus: hashicorp/raft, Dragonboat, NuRaft, canonical/raft, RabbitMQ Ra, Kafka KRaft, Kudu, YugabyteDB, and MongoDB.

etcd’s choice to count changes is deliberate. The comment above the check in raftpb/confchange.go explains why it uses joint consensus even when a simpler transition might be safe:

NB: in theory, more config changes could qualify for the “simple” protocol but it depends on the config on top of which the changes apply. For example, adding two learners is not OK if both nodes are part of the base config (i.e. two voters are turned into learners in the process of applying the conf change). In practice, these distinctions should not matter, so we keep it simple and use Joint Consensus liberally.

MongoDB explicitly connects the one-node-at-a-time rule to quorum overlap. Its validateSingleNodeChange rejects reconfigurations that add or remove more than one node (repl_set_config_checks.cpp:115). The comment at the call site gives the reason (lines 544–546):

For non-force reconfigs, verify that the reconfig only adds or removes a single node. This ensures that all quorums of the new config overlap with all quorums of the old config.

William Schultz, first author of the paper on MongoDB’s reconfiguration protocol, proposed using the more general QuorumsOverlap condition in a 2024 note. This is exactly C0 ~ C1. His TLA+ model, MongoLoglessDynamicRaft.tla, already uses QuorumsOverlap as a precondition for reconfiguration. MongoDB’s implementation still enforces the one-node-at-a-time restriction.

Reference:

Article link: https://blog.openacid.com/distributed/raft-adaptive-config-change/

openacid

Leave a comment

Raft Membership Changes: When a Leader Must Commit a Current-Term Entry First

· Zhang Yanpo (drdr.xp)

Standard joint consensus provides its own log barrier through config entries. Single-step changes and joint consensus extended with rollback require a committed current-term entry before a new config. Two failure scenarios show why the difference comes down to quorum overlap.

Flexible Raft: Read and Write Quorums

· Zhang Yanpo (drdr.xp)

A Raft leader usually waits for a majority before committing a write. We can reduce that wait, but the election rules and leader identities must still protect the log. Through a few small clusters, we explore two ways to do this, then follow the consequences for reads, failures, and membership changes.

The Pitfalls of Raft Membership Change

· Zhang Yanpo (drdr.xp)

Raft’s single-server membership change carries two problems: its middle state can turn one datacenter into a single point of failure, and the original algorithm could lose a committed entry. Let us look at membership change through quorum sets, and see why joint consensus is the answer.

Build a Distributed Timestamp Oracle with EzRaft

· Zhang Yanpo (drdr.xp)

timestamp_oracle is a 200-line timestamp service on EzRaft. A background task reserves ranges through Raft; next_timestamp allocates from memory. Leader leases and term-scoped caches keep the sequence strictly increasing across failovers, with no Raft write on the request path.