Replication Strategies
Imagine an airline booking system that keeps a single copy of every seat reservation on one machine. The moment that machine's disk fails, every gate agent, kiosk, and app worldwide freezes mid-transaction. Real systems cannot tolerate this. So they keep multiple copies of the same data on different machines — a technique called replication. The hard part is not making copies. The hard part is deciding when the copies must agree, who is allowed to write, and what a client sees while copies are catching up with each other. Replication sits at the center of nearly every large-scale data system. Examples include relational databases with read replicas, distributed key-value stores like Dynamo and Cassandra, and coordination services like ZooKeeper and etcd. Cloud storage systems must also survive an entire data center going dark. Once data is partitioned across many machines (see Data Partitioning and Sharding), each partition still needs its own replication strategy. Otherwise, losing one machine means losing that partition's data. This article develops the three central design axes of replication. First, synchronous versus asynchronous propagation of writes — a durability-versus-latency tradeoff. Second, primary-replica versus multi-primary designs — who is allowed to accept writes, and what happens when two writers disagree. Third, quorum-based reads and writes — a tunable middle ground. This lets a system trade consistency for availability on a per-operation basis, using simple arithmetic over replica counts. By the end, you will be able to design a replication scheme for a given workload. You will be able to predict its failure behavior. You will also be able to reason precisely about which anomalies (stale reads, lost writes, split-brain) each configuration permits. The ideas here are the direct on-ramp to The CAP Theorem and to Eventual Consistency and Consistency Models. Both of these formalize the tradeoffs introduced here.
- Replication keeps multiple copies of data on different machines to survive failures and to spread read load.
- Synchronous replication waits for replicas to acknowledge before committing; it gives strong durability but higher latency and lower availability during failures.
- Asynchronous replication commits locally and propagates later; it gives low latency and high availability but risks losing recently committed writes.
- Primary-replica designs route all writes through one node, avoiding write conflicts; multi-primary designs let several nodes accept writes concurrently, requiring conflict resolution.
- Quorum protocols (with read quorum R, write quorum W, and N replicas) let a system tune consistency and availability by requiring `R + W > N` for strong guarantees.
- These strategies are the concrete mechanisms behind the abstract tradeoffs in The CAP Theorem and Eventual Consistency and Consistency Models.
Replication strategies trade latency, availability, and consistency against each other, and the exact tradeoff is set by how many replicas must confirm a write before the system calls it done.
The idea
Replication is the maintenance of multiple copies (replicas) of the same logical data item across distinct physical machines (nodes), so that the failure of any single node does not make the data unavailable or lost. A replication strategy must answer two orthogonal questions. First, the propagation question: when a write occurs, does the system wait for other replicas to confirm it before telling the client "done" (synchronous), or does it acknowledge immediately and propagate in the background (asynchronous)? Second, the topology question: which nodes are permitted to accept writes at all — exactly one designated node (primary-replica, also called master-slave or leader-follower), or any node (multi-primary, also called multi-master)? A third technique, quorum replication, cuts across both questions. Instead of a fixed rule ("always wait for all replicas" or "never wait for any"), a quorum system requires only a subset of replicas to participate in each read or write. With `N` total replicas of an item, a write must be acknowledged by a write quorum of `W` replicas, and a read must consult a read quorum of `R` replicas. Choosing `W` and `R` lets the system dial its position on the latency/consistency spectrum continuously rather than picking one extreme. Three anomalies motivate all of the machinery below. A lost write occurs when a client is told a write succeeded, but a later failure causes that write to vanish from every surviving replica. A stale read occurs when a client reads a value older than one it (or another client) already observed as committed. Split-brain occurs when a network partition causes two nodes to simultaneously believe they are the sole primary, accepting conflicting writes that must later be reconciled or that are simply lost. Every strategy in this article is best understood as a specific set of guarantees against these three failure modes, purchased at a specific cost in latency and availability.
How it works
Synchronous vs. asynchronous replication
In synchronous replication, the node that receives a write does not acknowledge the client until some number of other replicas have durably applied that write and confirmed it. This guarantees that once a client is told "committed," the data survives the failure of any single replica (as long as at least one acknowledging replica survives). The cost is latency: every write pays for a round trip to the slowest confirming replica, and if that replica or the network to it is down, the write stalls or fails — hurting availability. In asynchronous replication, the receiving node applies the write locally, immediately acknowledges the client, and propagates the write to other replicas afterward, typically via a replication log shipped in the background. Writes are fast and available even if other replicas are slow or unreachable. The cost is a durability gap: if the accepting node crashes before propagating a write, that write is lost even though the client was told it succeeded — and other replicas may serve stale reads in the meantime. Most production systems use semi-synchronous replication as a practical middle ground: the primary waits for acknowledgment from some replicas (say, one out of several) before confirming to the client, then propagates to the rest asynchronously. ```pseudocode // Synchronous write on primary P with replica set {R1, ..., Rn} function SYNC_WRITE(key, value, requiredAcks): logEntry = APPEND_TO_LOCAL_LOG(key, value) send REPLICATE(logEntry) to all replicas acks = 0 wait until acks >= requiredAcks or TIMEOUT: on receiving ACK(logEntry) from some replica: acks += 1 if acks >= requiredAcks: COMMIT_LOCALLY(logEntry) return SUCCESS to client else: return FAILURE to client // do not commit; write is aborted // Asynchronous write on primary P function ASYNC_WRITE(key, value): logEntry = APPEND_TO_LOCAL_LOG(key, value) COMMIT_LOCALLY(logEntry) return SUCCESS to client // acknowledge immediately enqueue logEntry for BACKGROUND_REPLICATION_TASK ```
Primary-replica replication
In primary-replica replication, exactly one node — the primary (or leader) — accepts all writes for a given data item or partition. Every other replica is a read replica (or follower) that applies the primary's write log in order and may serve read-only requests. This design trivially avoids write-write conflicts, because there is only ever one writer. The central mechanism is leader election and failover: when the primary fails, the remaining replicas must agree on a new primary, typically using a consensus protocol so that at most one new primary is chosen even under network partitions. ```pseudocode // Follower applying the replication stream function FOLLOWER_APPLY_LOOP(replicationLog): lastApplied = 0 loop: entry = replicationLog.next(after = lastApplied) APPLY_TO_LOCAL_STATE(entry) lastApplied = entry.sequenceNumber // Simplified failover (assumes an underlying consensus/leader-election service) function ON_PRIMARY_TIMEOUT(replicaSet): candidate = ELECT_NEW_PRIMARY(replicaSet) // e.g., replica with highest applied LSN if I_AM(candidate): BECOME_PRIMARY() FENCE_OLD_PRIMARY() // prevent old primary from accepting writes ("fencing") else: REDIRECT_WRITES_TO(candidate) ``` The fencing step is essential: without it, a temporarily-partitioned old primary might resume accepting writes after a new primary has already been elected, producing split-brain. Common fencing mechanisms include epoch/term numbers (a write is only accepted if it carries the current term) and STONITH ("shoot the other node in the head") hardware fencing.
Multi-primary replication
In multi-primary replication, two or more nodes each accept writes independently, then exchange and merge updates with each other. This removes the single-writer bottleneck and lets each region or data center write locally with low latency, but it reintroduces the possibility of write-write conflicts: two primaries may each accept a different value for the same key before either learns of the other's write. A multi-primary system must therefore include a conflict resolution policy:
- Last-writer-wins (LWW): attach a timestamp (or hybrid logical clock) to every write; on conflict, keep the write with the larger timestamp. Simple, but silently discards one of the two writes.
- Version vectors / vector clocks: track causal history per replica so the system can distinguish a genuine conflict from one write causally following another, surfacing true conflicts to the application (as in early Amazon Dynamo).
- Conflict-free replicated data types (CRDTs): design the data type itself (counters, sets, sequences) so that concurrent updates always merge deterministically without loss, using algebraic properties (commutativity, associativity, idempotence).
```pseudocode // Multi-primary write with version vectors function MULTI_PRIMARY_WRITE(key, value, myReplicaId): localVersion = VERSION_VECTOR_STORE.get(key) newVersion = INCREMENT(localVersion, myReplicaId) STORE_LOCALLY(key, value, newVersion) ASYNC_BROADCAST(key, value, newVersion) to peer primaries return SUCCESS to client // On receiving a remote write function ON_REMOTE_WRITE(key, remoteValue, remoteVersion): localValue, localVersion = STORE.get(key) if DOMINATES(remoteVersion, localVersion): STORE.set(key, remoteValue, remoteVersion) // remote strictly newer elif DOMINATES(localVersion, remoteVersion): // local is strictly newer; ignore remote pass else: // concurrent, incomparable versions: true conflict STORE.set(key, RESOLVE_CONFLICT(localValue, remoteValue), MERGE(localVersion, remoteVersion)) ```
Quorum reads and writes
A quorum system generalizes both extremes. With `N` replicas per item, define a write quorum size `W` and a read quorum size `R`. A write must be acknowledged by `W` replicas; a read must query `R` replicas and reconcile their answers (e.g., return the value with the highest version/timestamp). The system is tuned by the classic inequality: ``` R + W > N ``` When this holds, every read quorum and every write quorum must overlap in at least one replica, guaranteeing that a read quorum always includes at least one replica holding the most recent committed write. ```pseudocode function QUORUM_WRITE(key, value, N, W): timestamp = NEW_TIMESTAMP() acked = 0 send WRITE(key, value, timestamp) to all N replicas wait until acked >= W or TIMEOUT: on ACK from a replica: acked += 1 if acked >= W: return SUCCESS else: return FAILURE // fewer than W replicas confirmed; write may be partially applied function QUORUM_READ(key, N, R): responses = [] send READ(key) to all N replicas wait until len(responses) >= R or TIMEOUT: on RESPONSE(value, timestamp) from a replica: responses.append((value, timestamp)) if len(responses) >= R: best = argmax(responses, key = lambda r: r.timestamp) // optional: read repair — push best.value to any stale responder for r in responses: if r.timestamp < best.timestamp: ASYNC_SEND(REPAIR(key, best.value, best.timestamp), r.replica) return best.value else: return FAILURE ``` Two named special cases: `W = N, R = 1` recovers synchronous, all-replica writes with cheap reads (read-heavy optimization); `W = 1, R = N` recovers fast writes with expensive, thorough reads (write-heavy optimization). Setting `R = W = ⌈(N+1)/2⌉` balances the two and tolerates `⌊(N-1)/2⌋` simultaneous replica failures while preserving overlap.
Complexity & correctness
Time cost per operation. Let `d` be the one-way network latency between a client-facing node and the slowest replica it must contact. A synchronous write with `W` required acknowledgments costs `Θ(d)` in the best case (all `W` replicas respond promptly in parallel) but is bounded below by the slowest of the `W` replicas contacted, so tail latency is governed by the maximum of `W` parallel round trips, not their sum — the requests are sent concurrently. An asynchronous write costs `Θ(1)` local disk write, decoupled from `d` entirely; replication happens off the critical path. A quorum read or write similarly costs one parallel round trip to `max(R, N)` or `max(W, N)` replicas respectively, i.e., `Θ(d)` with a constant factor depending on how many replicas are contacted, not how many exist.
Space cost. Each of the `N` replicas stores a full copy of the data item, so total space is `Θ(N)` times a single copy — this is the fundamental price of durability and read scaling; there is no way to tolerate `f` replica failures with less than `f+1` copies of the affected data (pigeonhole: if only `f` copies exist and all `f` machines holding a specific item fail, that item is gone).
Correctness of the quorum inequality. Claim: if `R + W > N`, then every write quorum and every read quorum share at least one common replica. Proof. Let `Q_w` be any set of `W` replicas and `Q_r` be any set of `R` replicas, both drawn from the same universe of `N` replicas. Suppose for contradiction they were disjoint: `|Q_w ∪ Q_r| = |Q_w| + |Q_r| = W + R`. But `Q_w ∪ Q_r` is a subset of the `N` replicas, so `|Q_w ∪ Q_r| ≤ N`. Combining, `W + R ≤ N`, contradicting `R + W > N`. Hence `Q_w` and `Q_r` must intersect. ∎ This intersection replica saw the most recent acknowledged write, so a correctly implemented read (taking the maximum-timestamp response among `R` contacted replicas) always returns a value at least as new as the last completed write — this is exactly what rules out stale reads under the assumption that no more than `N − W` replicas are simultaneously unreachable and clocks/versions are comparable.
Failure tolerance. A quorum-based system remains available for writes as long as at least `W` replicas are reachable, and available for reads as long as at least `R` are reachable. It tolerates up to `N − W` replica failures for writes and `N − R` for reads simultaneously. Choosing `W` and `R` both around `⌈(N+1)/2⌉` maximizes the minimum of these two tolerances, which is why majority quorums are the default choice in systems like Cassandra (`QUORUM` consistency level) and in consensus protocols underlying primary election.
Honest tradeoffs.
- Synchronous replication is safer but slower and less available: a network blip to any required replica stalls every write.
- Asynchronous replication is fast and available but can silently lose acknowledged writes on primary crash — the size of this loss window equals the replication lag.
- Primary-replica avoids conflicts entirely but makes the primary a bottleneck and a single point of contention during failover (there is a window, however brief, with no writable primary).
- Multi-primary removes that bottleneck but pushes conflict-resolution complexity into the application or into CRDT design, and can never guarantee no data is discarded unless the merge function is provably conflict-free.
- Quorums do not eliminate these tradeoffs; they let you choose a point on the curve per-operation, at the cost of needing to contact multiple replicas even for reads (more network messages than a single-replica read).
Worked example
Consider a key-value store with `N = 3` replicas (`A`, `B`, `C`) holding the value for key `x`, initially `x = 10` on all three, all at logical timestamp `t0`.
Scenario 1 — synchronous, primary-replica, `W = 3`. `A` is primary. A client writes `x = 20`.
| Step | Action | State |
|---|---|---|
| 1 | Client sends `write(x, 20)` to A | A: pending |
| 2 | A appends to local log, sends REPLICATE to B, C | A=10(pending), B=10, C=10 |
| 3 | B applies and ACKs; C is network-partitioned, times out | A=10(pending), B=20, C=10 |
| 4 | A has only 1 of 2 required ACKs (needs W=3, has 2 incl. itself) | write FAILS, client told failure |
Here the strict `W = N = 3` requirement correctly refuses to commit when a replica is unreachable — a safe but unavailable outcome. The client can retry once `C` recovers.
Scenario 2 — same setup, quorum with `N = 3, W = 2, R = 2`.
| Step | Action | State |
|---|---|---|
| 1 | Client writes `x = 20`, timestamp `t1` | — |
| 2 | A applies locally, sends to B and C | A=20@t1 |
| 3 | B ACKs; C is partitioned and times out | A=20@t1, B=20@t1, C=10@t0 |
| 4 | 2 of 3 ACKs received (W = 2 satisfied) | write SUCCEEDS |
| 5 | Later, client reads `x`, contacting A and C (R = 2) | responses: A→20@t1, C→10@t0 |
| 6 | Reader picks max timestamp: `20@t1` | correct value returned |
| 7 | Read-repair pushes `20@t1` to C in the background | C=20@t1 eventually |
Even though `C` was stale, the quorum overlap guarantee (`R + W = 4 > N = 3`) forced the read to include at least one of `{A, B}`, which held the fresh value — so the stale replica never fooled the client. Had the client instead queried `{B, C}` or `{A, C}`, at least one of `A` or `B` is still present in every 2-out-of-3 read set, by the pigeonhole argument proven above.
Scenario 3 — multi-primary conflict. Suppose instead both `A` and a second primary `D` (in a different data center) accept writes on `x` concurrently while partitioned from each other: `A` sets `x = 20`, `D` sets `x = 30`, neither aware of the other. Using last-writer-wins with wall-clock timestamps `20@14:00:01` and `30@14:00:00`, the earlier-timestamped `30` is discarded even though it was, from the client's perspective, a perfectly valid concurrent write — illustrating that LWW silently loses data to resolve conflicts, motivating vector clocks or CRDTs when silent loss is unacceptable.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Treating asynchronous replication as "just a bit behind" | Ignoring that the primary can crash before any propagation happens | Silent, permanent loss of acknowledged writes |
| Choosing `R + W ≤ N` while assuming strong consistency | Confusing "using a quorum" with "using a quorum that overlaps" | Reads can miss the latest write; stale data returned with no error |
| No fencing on primary failover | Assuming the old primary will "notice" it lost leadership and stop | Split-brain: two primaries accept conflicting writes simultaneously |
| Using wall-clock last-writer-wins across data centers | Clocks are not perfectly synchronized; skew silently reorders events | A causally later write can be discarded because its timestamp is smaller |
| Counting the write quorum from the coordinator's perspective only | Forgetting the coordinator itself counts as one of the `W` acks | Off-by-one: system requires one fewer remote ack than intended |
| Assuming quorum reads are as cheap as single-replica reads | Overlooking that `R` replicas must be contacted and reconciled every time | Higher read latency and network cost than a naive primary-only read |
Pioneers & history
Replication as a systematic discipline grew out of distributed systems research on fault tolerance and consensus, rather than from any single database vendor. The key conceptual leap was recognizing that agreement on "who writes next" is itself a consensus problem, and that read/write quorums could quantify the consistency-availability tradeoff with simple arithmetic rather than ad hoc rules.
Origins · 1 minLeslie Lamport and how this was discovered
Leslie Lamport formalized logical clocks, causal ordering of events, and the Paxos consensus protocol — the theoretical bedrock beneath every safe primary-election and fencing scheme used in modern replicated databases. His 1978 paper on ordering events in distributed systems introduced the "happens-before" relation that underlies vector clocks and version-vector conflict detection used in multi-primary replication today.
Where this matters
Relational databases (PostgreSQL streaming replication, MySQL semi-sync replication) use primary-replica designs with a configurable synchronous/asynchronous boundary, letting operators choose durability guarantees per deployment. Distributed key-value and wide-column stores — Amazon DynamoDB, Apache Cassandra, Riak — expose quorum consistency levels (`ONE`, `QUORUM`, `ALL`) directly to application developers as a per-query knob. Coordination services such as etcd and ZooKeeper use consensus-based primary election (Raft, ZAB) with fencing tokens to guarantee at most one active leader, forming the backbone of Kubernetes' control plane and countless distributed locks. Multi-region cloud databases (CockroachDB, Google Spanner, Azure Cosmos DB) combine quorum writes with either synchronized clocks or consensus logs to offer strong consistency across data centers at the cost of higher write latency, while collaborative editing systems and offline-first mobile apps lean on CRDT-based multi-primary replication to merge concurrent edits without a central coordinator at all.
Ask the tutor: How would you redesign the quorum parameters if reads are 100× more frequent than writes in my workload?
Is synchronous replication the same as strong consistency?
Not exactly, though they are closely related. Synchronous replication describes how a write propagates — waiting for acknowledgments before confirming to the client. Strong consistency describes an observable guarantee about what reads return relative to writes. A system can replicate synchronously to all replicas and still allow a stale read if reads are served from a follower without checking freshness. Conversely, a well-designed quorum system with `R + W > N` can achieve strong-consistency-like guarantees without every write reaching every replica synchronously. Synchronous replication is one common mechanism for achieving strong consistency, not a guarantee in itself; the read path must also be designed to respect it.
Why not just always use W = N for maximum safety?
Setting `W = N` means every single replica must acknowledge every write, so the loss or slowdown of any one replica blocks all writes — the system's write availability becomes as fragile as its least reliable machine. This defeats much of the purpose of having multiple replicas, since more replicas should mean more fault tolerance, not less. In practice, systems favor `W` around a majority (`⌈(N+1)/2⌉`) so that a minority of slow or failed replicas cannot halt writes, while still guaranteeing overlap with reasonably sized read quorums.
How does multi-primary replication relate to eventual consistency?
Multi-primary systems almost always propagate writes asynchronously between primaries, because waiting synchronously for a geographically distant primary would erase the low-latency benefit of writing locally in the first place. This means replicas temporarily diverge after concurrent writes and must be reconciled later — the defining behavior of eventual consistency, covered in depth in Eventual Consistency and Consistency Models. Multi-primary replication is essentially the topology choice that requires an eventual-consistency model (or CRDT-based merging) to make sense, since strict agreement among independent writers without coordination is not achievable.
What happens to a quorum system during a network partition?
If a partition splits `N` replicas into two groups, a write or read can only succeed in a group that still contains at least `W` (for writes) or `R` (for reads) reachable replicas. With majority quorums, only one side of any partition — the side with more than half the replicas — can make progress; the minority side must refuse operations rather than risk inconsistency. This refusal-on-minority-side behavior is precisely the availability sacrifice formalized by The CAP Theorem: under partition, a system must choose between remaining available on both sides (risking divergence) or refusing service on the minority side (preserving consistency).
Do quorum reads always return the correct value, or can they still fail?
Quorum reads return the correct value under two assumptions: fewer than `N − W` replicas are simultaneously unavailable at write time (so the write quorum was genuinely satisfiable), and version/timestamp comparison correctly identifies the most recent write. If clocks are unsynchronized and used as raw timestamps, "most recent" can be miscomputed, which is why systems favor logical clocks, hybrid logical clocks, or per-key version counters over wall-clock time. Even with correct versioning, a read quorum only guarantees seeing the latest completed write — a write still in flight (not yet reaching `W` acks) may be invisible or partially visible, which is expected and not a correctness violation.
How do primary-replica and quorum replication combine in real systems?
Many systems use a hybrid: a primary-replica structure for ordering writes (avoiding conflicts by funneling writes through one leader per partition), combined with a quorum-based commit protocol for durability (the leader waits for a majority of followers, not all, to acknowledge before committing). Raft-based systems like etcd and CockroachDB work exactly this way — one leader per Raft group proposes writes, and the write is committed once a majority of the group's replicas persist it to their logs. This gives the conflict-avoidance of primary-replica together with the failure tolerance and tunable overlap guarantees of quorums.
Why do multi-primary systems need CRDTs instead of just detecting conflicts?
Version vectors detect that two writes were concurrent, but detection alone does not tell the system what value to store — some policy must merge or choose between them, and ad hoc policies (like last-writer-wins) can silently discard data. CRDTs (conflict-free replicated data types) solve this by designing the data structure itself so that the merge operation is mathematically guaranteed to be commutative, associative, and idempotent — meaning any order or repetition of merges converges to the same final state without needing a coordinator to arbitrate. This shifts conflict resolution from an application-level guess into a provable property of the data type, at the cost of restricting which data types (counters, sets, sequences) are usable.