Multi-Leader Replication Topologies

In the previous post we established that write conflicts are the price of multi-leader replication. But we haven’t yet asked a more basic question: how do the leaders actually talk to each other?

In a two-leader system the answer is obvious — each leader sends its writes to the other. With three or more leaders there are choices, and those choices have real consequences for fault tolerance and consistency.

The Three Topologies

A replication topology describes the communication paths between leaders: which nodes send replication data to which other nodes.

Circular topology. Each leader receives writes from one predecessor and forwards them (along with its own writes) to one successor, forming a ring. MySQL supports this by default in multi-leader configurations.

Star topology. One leader is designated the root. Every other leader sends its writes to the root, and the root forwards all writes to all other leaders. This is a hub-and-spoke model.

All-to-all topology. Every leader sends its writes directly to every other leader. No intermediaries.

Multi-leader replication topologies

Circular, Star, and All-to-all topologies — each showing how a write propagates through the network.

The difference matters most when a node fails.

In a circular topology, a single failed node breaks the ring. Writes originating on the far side of the failure can’t reach leaders on the near side. The ring has to be reconfigured to route around the failed node.

In a star topology, the root is a single point of failure for all write propagation. If the root goes down, other leaders can still accept writes, but nothing replicates until the root comes back or is replaced.

In an all-to-all topology, no single node is required for replication to proceed. If one leader fails, the others continue replicating directly to each other. This makes all-to-all significantly more fault-tolerant — but it introduces a consistency problem that the other two topologies don’t have.

The Causality Problem in All-to-All

In circular and star topologies, writes flow through a single path. A write from Leader 1 that depends on an earlier write always travels the same route, so it always arrives after its predecessor.

In all-to-all, every leader sends directly to every other. This means two causally related writes can travel on completely different network paths — and the network doesn’t guarantee that the faster path carries the earlier write.

Consider this sequence:

Leader 1 inserts a new row: INSERT INTO records VALUES (id=42, title='A')
Leader 2 updates that row: UPDATE records SET title='B' WHERE id=42

Leader 2 sees the INSERT, then applies the UPDATE. When these replicate to Leader 3:

The INSERT travels from Leader 1 → Leader 3
The UPDATE travels from Leader 2 → Leader 3

If the Leader 2 → Leader 3 link is faster, Leader 3 sees the UPDATE before the INSERT. It tries to update a row that doesn’t exist yet. The causality is violated: the effect arrives before its cause.

Causality violation in all-to-all replication

UPDATE races ahead of the INSERT it depends on — Leader 3 gets the effect before its cause.

This problem doesn’t occur in circular or star topologies because all writes pass through the same ordered path. All-to-all’s direct links are what create the risk.

Version Vectors

The solution is to track causality explicitly using version vectors (sometimes called vector clocks).

Each write carries a version vector — a map from each leader’s ID to the sequence number of the most recent write from that leader that this write depends on. When a node receives a write, it checks whether all the writes in the version vector have already been applied. If not, it buffers the incoming write and waits.

For the example above:

Leader 1’s INSERT gets version vector {L1: 1}
Leader 2’s UPDATE gets version vector {L1: 1, L2: 1} — it depends on L1’s first write

When Leader 3 receives the UPDATE with {L1: 1, L2: 1}, it checks: have I applied L1’s write number 1? If not, buffer the UPDATE and wait for it.

Traced out at Leader 3, where the UPDATE arrives first:

state: applied = {}          buffer = []

recv UPDATE  vv={L1:1, L2:1}
  needs L1:1 — applied has no L1  ->  BUFFER, do not apply
state: applied = {}          buffer = [UPDATE]

recv INSERT  vv={L1:1}
  needs nothing  ->  APPLY
state: applied = {L1:1}      buffer = [UPDATE]

  re-check buffer: UPDATE needs L1:1 — satisfied  ->  APPLY
state: applied = {L1:1, L2:1}  buffer = []

The buffering is what makes the order the network happened to deliver irrelevant. Both leaders converge on the same final state whether the INSERT or the UPDATE arrives first — the version vector carries enough information to reconstruct the dependency the topology lost.

Version vectors in action

How Leader 3 uses version vectors to buffer an out-of-order write and apply both in causal order.

This lets the receiving node detect out-of-order arrivals and hold writes in a pending queue until their dependencies arrive. Once the INSERT lands, the UPDATE can be applied in the correct order.

Version vectors add overhead: every write carries the vector, and nodes maintain pending queues for out-of-order arrivals. But they’re a necessary cost for correctness in all-to-all topologies. Without them, a database silently applies writes in the wrong order and produces corrupted state.

The Practical Tradeoff

Circular and star topologies are simpler to reason about. Causality is preserved automatically because all writes travel a single path. The cost is fault tolerance: one failed node disrupts all replication.

All-to-all is more resilient. No single node is a bottleneck. But it requires explicit causality tracking — either via version vectors in the replication protocol, or by the application ensuring that causally related writes go through the same leader.

Most production multi-leader systems prefer all-to-all for its fault tolerance, and implement version vectors in the replication layer rather than requiring applications to handle ordering. But the causality problem is easy to underestimate — and a database that silently drops or misorders writes is worse than one that fails loudly.

Key Takeaways

Multi-leader systems with three or more leaders must choose a replication topology: circular, star, or all-to-all.
Circular and star topologies preserve write ordering naturally — all writes travel a single path — but have single points of failure that can halt replication.
All-to-all is the most fault-tolerant topology: no single failure blocks replication. But direct paths between every pair of leaders mean causally related writes can arrive out of order.
Version vectors solve the causality problem by attaching dependency metadata to each write. A receiving node buffers writes whose dependencies haven’t arrived yet, and applies them in causal order once they do.
Without causality tracking in all-to-all, a database can silently apply writes in the wrong order — producing corrupted state with no obvious error.

References

Martin Kleppmann, Designing Data-Intensive Applications, chapter 5 — the canonical treatment of replication this series works through.
Version vectors — how replicas track causality between concurrent updates.