Skip to content

Joint consensus vs single-server changes in Raft#

2024-07-22

The original Raft paper (Ongaro & Ousterhout, 2014) proposes joint consensus for membership changes: transition through an intermediate configuration C_old,new that requires a majority in both C_old and C_new to commit anything. This is provably safe but complicated to implement.

Ongaro's dissertation later proposes single-server changes: add or remove one server at a time, relying on the observation that any two configurations that differ by a single server necessarily overlap in a majority. Much simpler to implement — you can treat membership changes as ordinary log entries.

The subtle correctness bug#

Single-server changes were widely deployed (etcd, Consul, most Raft libs) before Bug #10 was found: if you do multiple single-server changes rapidly, you can end up with a split-brain scenario during a specific failure pattern. Ongaro published a patch that requires each server to reject configuration changes until the previous change has committed under the new config.

Details: the leader that proposes change 2 must have committed change 1 in change 1's configuration, not just in the leader's local log. Otherwise change 1 can be lost and change 2 can succeed under an inconsistent view.

What real systems do#

  • etcd: single-server changes with the fix; sequential membership changes.
  • TiKV/braft: joint consensus, always.
  • Redis Raft: single-server changes.
  • CockroachDB: joint consensus for atomic multi-server changes (adding and removing at once to rebalance).

When to prefer which#

Single-server is fine for slowly-changing cluster membership (add/remove one machine at a time). Joint consensus is better if you routinely need to swap out multiple servers atomically (e.g., cross-datacenter migrations).

Reference#

  • Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC 2014).
  • Ongaro, Consensus: Bridging Theory and Practice (Stanford dissertation, 2014).
  • The etcd #10166 issue thread has a lot of detail on the safety bug.