Replication — Topologies, CRAQ Read-Scaling, Failover Selection & True Multi-Master (Deep Dive)

What this page covers — and what it deliberately skips

The rest of this guide already answers the classic replication questions well: how a follower falls behind and what read-your-writes/monotonic-reads mean for it, how externally-orchestrated failover splits brains and how async failover loses data, and why a newly elected Raft leader is guaranteed to already hold every committed entry (see the Leader/Follower deep dive); how conflicting writes merge without central coordination via CRDTs, state-based and operation-based (see the CRDT pages); and how the log itself gets shipped to a follower — statement vs logical vs physical/WAL (see Replication Log Formats). This page picks up exactly where those leave off: the read-scaling trick chain replication is missing until CRAQ adds it, the topology choices hiding inside the word “multi-leader” and how each one specifically breaks, which follower a failover should actually promote, why “active-active for reads” and “true multi-master for writes” are not the same difficulty, and why you can’t just throw threads at replaying a log.

Chain replication: strict order, but the tail is a read bottleneck

Mechanism: nodes sit in a strict line, head → middle(s) → tail. Every write enters at the head and is applied node-by-node down the chain; it is considered committed only once the tail has applied it. Every read, regardless of which node a client asks, is routed to the tail — and because nothing in the chain sits after the tail, whatever the tail holds has, by construction, already been applied everywhere upstream of it. A read from the tail is therefore always linearizable: there is no fresher copy anywhere in the system. The cost is that every single read pays the cost of hitting one node, so read throughput is capped at what that one node can serve, no matter how many nodes sit in the chain ahead of it.

CRAQ: apportion the reads across the whole chain

CRAQ (Chain Replication with Apportioned Queries — van Renesse & Schneider) keeps the write path exactly as above — strictly head to tail — but lets every node in the chain answer reads, not only the tail, while keeping the same strong consistency. The trick is a per-object flag each node keeps alongside its stored value:

• Clean — this version has already been acknowledged all the way to the tail; it is committed. A node can serve a clean value directly, with zero coordination.
• Dirty — this version has been applied locally (the write passed through) but the tail has not yet acked it. It might still be in flight, so it is not yet guaranteed durable.

When a read lands on a node whose top version for that object is dirty, the node cannot safely hand it out as-is — instead it sends the tail one cheap question: “what version number is currently committed for this object?” If the answer matches the version the node is holding dirty, that value is already committed (the node just hasn’t heard the ack yet) and it serves it. If the tail reports an older committed version — because a newer write is still in flight behind the one the node is asking about — the node falls back to serving its last known clean value instead of the unconfirmed dirty one. Either way the node never has to ship the whole value to the tail and back, only a version number — which is what makes this cheap enough to do on every dirty read.

Traced: two writes racing a read, dirty and clean

Chain: Head H → Middle M → Tail T. Object X starts at v1, clean everywhere.

Notice what never happens: M never serves a value that could still be overwritten before it is durable. The one-number query to the tail is what buys that guarantee without shipping the whole read through the tail.

Multi-leader topologies: same goal, three different failure shapes

Mechanism: the moment more than one leader accepts writes, something has to move a write that landed on leader A over to leaders B and C. How that movement is wired — the topology — is a design decision with its own failure mode, independent of the conflict-resolution question itself (that part is the CRDT pages’ job).

All-to-all

Every leader ships its writes directly to every other leader. This gives the fastest convergence (no intermediate hop to wait on) and no single relay node whose failure blocks propagation. But because a write can take a different number of network hops to reach different leaders, writes can arrive out of the causal order they were created in — leader C might see leader B’s write before the write on leader A that causally preceded it. Detecting this needs version vectors (not physical timestamps, which cannot be trusted to agree across independent clocks) to tell “happened-before” from “genuinely concurrent” — see the CRDT pages for what happens once that ordering is known.

Circular / ring

Each leader forwards only to one neighbor, forming a loop. Cheap — one outbound link per node — and simple to reason about. Two problems follow directly from the shape: first, if any one node in the ring goes down, propagation breaks for every leader positioned after it — a single failure partitions the whole ring, not just one leader’s traffic. Second, a ring has no natural stopping signal: without a replica-id tag attached to every write identifying which node originated it, a node has no way to recognize “I already forwarded this once” and a write can circle the ring forever, consuming bandwidth on every lap.

Star / hub-and-spoke

One central node relays between all the spoke leaders. Simple topology, O(n) links — but the hub is a single point of failure for the entire multi-leader system: if it goes down, no leader can propagate to any other, even though every individual leader is still healthy and perfectly capable of serving writes locally.

Failover: promote the most-caught-up follower, not the most-recently-healthy one

Mechanism: when a leader dies and a follower must be promoted, which follower matters as much as the decision to fail over at all. The correct policy promotes whichever surviving follower has the highest applied log position — its LSN (log sequence number) — not whichever one has the most recent heartbeat. Two followers can both have “looked healthy two seconds ago” while one is three writes behind the dead leader and the other is thirty writes behind, purely from network jitter or a slow disk — time-since-last-heartbeat says nothing about how much log a follower actually holds. LSN is a precise count of exactly how much acked history that follower has.

Promoting a less-caught-up replica instead of the most-caught-up one does not merely accept the unavoidable loss of writes that never reached any follower under async replication — it additionally, and needlessly, throws away the tail of writes that did safely reach the most-caught-up replica but not the one that got promoted. That is a self-inflicted wound: data that was durably replicated somewhere in the cluster becomes unrecoverable because the orchestrator picked the wrong promotion target, not because replication itself failed. (What happens next — the promoted follower’s divergence from the old leader’s un-replayed tail — is covered by the truncation mechanism in the Leader/Follower deep dive; this section is about correctly picking who gets promoted before that truncation logic ever runs.)

Active-active-for-reads is easy; true multi-master writes pay upfront

Mechanism: “active-active” gets used loosely, so it is worth separating the two axes it actually names. Serving reads from multiple nodes is close to free — reads do not mutate state, so any sufficiently caught-up replica can answer one without coordinating with anyone else (modulo the staleness anomalies the Replication Lag & Failover page already covers). True multi-master writes are a different problem: the instant two leaders can each accept a write to the same record independently, every write is a potential conflict, not a rare edge case — because neither leader knows what the other just did until propagation catches up. That forces conflict resolution to become a mandatory, always-on cost paid on every write path, not an occasional cleanup job: either engineered away with CRDTs (data types whose merges are conflict-free by construction — see the CRDT pages) or handled with application-level merge logic (last-write-wins, per-field merge, a manual “which value wins” resolution flow) that the team must design, test, and maintain itself.

Contrast this with a single-leader system that simply serves active-active reads: it pays zero design cost for conflicts, because conflicts cannot happen — there is exactly one place writes are serialized. That gap is the real reason “let’s go multi-master” is a materially bigger project than “let’s let our replicas serve reads.”

Why not just parallelize replaying the log?

Mechanism: a replication log is ordered for a reason — later entries can depend on earlier ones. An UPDATE orders SET qty = qty - 1 WHERE id = 42 applied at position 51 depends on every prior write to that row having already been applied in order; a row updated at position 50 might not even exist yet if the insert that created it sits at position 12 and hasn’t been replayed. Naively splitting the raw log into chunks and replaying them on separate threads breaks this: a worker assigned position 51 can run before the worker assigned position 12 finishes, applying an update to a row that, from its point of view, does not exist yet — silently corrupting state with no error raised anywhere.

The real escape hatch is narrower than “just add threads”: parallelism is safe exactly where the ordering dependency the log encodes does not cross the parallel boundary. If two writes provably never touch the same key or partition, they have no ordering dependency on each other and can be replayed concurrently. This is why practical replication systems parallelize replay per-key or per-partition — each key/partition gets its own single-threaded, strictly-ordered replay stream — rather than chunking the raw log by byte offset. Global order across partitions is not preserved, but it usually is not needed; order within a partition, which is where the real dependencies live, is preserved exactly.

One-line PACELC framing: every mechanism on this page — CRAQ’s dirty-read query, chain replication’s tail bottleneck, ring/star propagation delay, multi-master’s conflict window — is a different point on the same dial. Even with no partition (PACELC’s “else” branch), you still trade Latency against Consistency: pay the coordination cost now (synchronous replication, a single global order, upfront conflict resolution) or pay it later as staleness or conflicts (async, multi-master, parallel-by-partition). See the CAP/PACELC replication page for the base framework this page’s trade-offs all sit inside.

Pitfalls

• Assuming any chain node can safely answer a read the moment it has the value — without the clean/dirty bookkeeping, that is just plain (weaker) eventually-consistent chain replication, not CRAQ’s linearizable guarantee.
• Picking a ring topology for its low link cost and forgetting the replica-id tag — the first time a write outruns its own removal condition, it loops the ring forever, doubling load with every additional lap.
• Failing over on heartbeat freshness instead of LSN — “last seen one second ago” says nothing about how much log a replica is actually missing, and can promote the wrong follower.
• Treating “go multi-master” as a topology decision only, budgeting no time for conflict-resolution design — the conflict-handling cost is paid on every write, not occasionally.
• Parallelizing log replay by chunking raw file offsets instead of partitioning by key — a fast way to corrupt derived state with no error raised to catch it.

Judgment layer

Which topology, when

Chain + CRAQ: choose when reads must be both linearizable and horizontally scalable, and the operational complexity of a strictly ordered chain with version bookkeeping is acceptable — strongly-consistent metadata/config stores are the classic fit. Plain chain replication is enough if read volume never exceeds what the tail alone can serve, or a simpler mental model is worth more than the extra read throughput. Multi-leader all-to-all when writes must be accepted concurrently at multiple locations, conflicts are tolerable/mergeable, and fastest convergence matters more than O(n²) link cost. Ring only at small, stable node counts — it scales badly in both link-cost-per-failure and blast radius as n grows. Star only when the hub genuinely runs on infrastructure reliable enough that its SPOF risk is acceptable — otherwise it quietly re-introduces the single point of failure multi-leader was supposed to avoid.

Active-active reads vs true multi-master writes

Turn on active-active reads whenever the workload is read-heavy and healthy replicas already sit mostly idle — the added design cost is close to zero. Reach for true multi-master writes only when a concrete requirement makes a single write path insufficient — multi-region write availability through a regional outage, or offline-first clients that must write locally and reconcile later — and budget conflict resolution (CRDTs or an explicit merge policy) as a permanent, first-class part of the design from day one, not a patch added after the first conflict bug ships.

Takeaways

• CRAQ’s entire trick is a per-object clean/dirty flag plus one cheap “what’s committed?” query to the tail — it turns chain replication’s single-node read bottleneck into a scale-out read path without losing linearizability.
• The three multi-leader topologies trade convergence speed and link cost against three genuinely different failure shapes — out-of-order conflicts, ring breakage/infinite loops, and a hub SPOF — pick on which failure you can tolerate, not which is simplest to draw.
• Failover must promote the highest-LSN follower, not the most-recently-healthy one; picking wrong discards safely-replicated data a correct choice would have kept.
• Active-active reads cost almost nothing extra; true multi-master writes make conflict resolution a permanent, always-on tax on every write — budget for it up front, and remember naive parallel log replay has the same ordering trap unless it is scoped per-key/partition.

Related pages

• Replication Lag & Failover — Read-Your-Writes, Split-Brain & Fencing — System Design — the replica-lag and failover anomalies this page builds past
• Leader/Follower — Replica-Lag Anomalies, Failover Data Loss, Log-Shipping & Raft Leader Completeness (Deep Dive) — System Design — the log-shipping and truncation mechanics behind failover promotion
• Consensus with Raft — Leader Election & Log Replication — System Design — why a newly elected leader already holds every committed entry
• CRDTs: State-Based vs Operation-Based — System Design — the conflict-resolution mechanism multi-master writes require
• CAP/PACELC for Replication & Reads — System Design — the base latency/consistency framework this page's trade-offs sit inside

Re-authored/Deepened for this guide, drawing on Robbert van Renesse & Fred B. Schneider, “Chain Replication for Supporting High Throughput and Availability” (OSDI 2004), Jeff Terrace & Michael J. Freedman, “Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads” (USENIX ATC 2009), and Martin Kleppmann, Designing Data-Intensive Applications (Ch. 5, “Replication”); diagrams hand-authored (SVG) for this guide.