Replication
Keep more than one copy of every byte. The copies buy you durability, read scale, and survival — and in return they are allowed to disagree. This lesson is about how writes reach the copies; lesson 09 is about what a reader then sees.
Partitioning (lesson 07) cut your data into disjoint slices so it would fit and so load would spread. Replication is the orthogonal move: take each slice and store it on several nodes. The two compose — a real system shards into P partitions and replicates each partition R-ways, giving P×R copies arranged on a cluster. Here we hold partitioning fixed and ask the single question replication actually answers: how does a write propagate to the N copies of one piece of state?
Why you pay for copies
There are exactly three first-principles reasons to store the same datum more than once. Every replication design is a different weighting of these three against the one cost they all incur — divergence.
| Reason | What a second copy buys | Quantified |
|---|---|---|
| Durability | A copy survives the death of a disk or a whole node. Without it, one disk failure = data loss. | Annualized disk failure ~1–2%. One copy → ~1.5% chance/yr of losing that data; three independent copies → ~3.4×10⁻⁶. |
| Read scaling | Reads served from any copy, so read throughput multiplies with replica count. | 1 leader + 5 read replicas ≈ 6× read capacity (writes still bottleneck on the leader). |
| Availability / geo-latency | If one copy is down, route to another (failover). A copy near the user cuts RTT. | Cross-continent RTT ~150 ms vs ~1 ms in-region — a local replica is a 100×+ latency win on reads. |
The cost is uniform: the instant you have two copies and a write lands on one, the other is briefly wrong. Closing that gap is either slow (wait for all copies) or leaves a window of staleness (don't wait). That tension is the entire subject below, and the reader-facing consequences are lesson 09.
Single-leader replication
The default. One replica is the leader (primary); all writes go there. The leader appends each change to a replication log (a WAL / binlog / oplog of ordered operations — this is the write-ahead log from lesson 04, the ordered record of every change; replication ships this log to the followers, which replay it) and streams that log to its followers, which apply the same operations in the same order. Reads may be served by the leader or by any follower. (B-tree engines like Postgres and LSM engines like Cassandra replicate this log differently — see 04.)
Synchronous vs asynchronous: where you put the durability/latency knob
The leader's only real decision is when do I acknowledge the client's write? Three positions:
| Mode | Leader acks after… | On leader crash | Write latency | Availability of writes |
|---|---|---|---|---|
| Synchronous | ≥1 follower confirms it has the write | No data loss — the synced follower has it | Leader RTT + slowest synced follower RTT | A slow/dead follower stalls all writes |
| Asynchronous | local commit only | Loses the un-replicated tail (your RPO) | Local commit only — fastest | Followers can lag or die freely |
| Semi-sync | at least one of N followers acks | No loss if that one survives | W=2 fastest of N | Tolerates the slowest N−1 followers |
Fully synchronous to all followers is rarely used: one slow disk anywhere freezes the cluster, and your write latency becomes the tail latency of your worst node. The common production choice is semi-sync (e.g. MySQL rpl_semi_sync, Postgres synchronous_standby_names with a quorum): wait for one ack so a single leader death can't lose data, but don't wait for everyone. Asynchronous is correct when a few seconds of lost writes is acceptable in exchange for the lowest latency and the highest write availability — many read-heavy systems run this way.
An async follower applies the log after receiving it. So at any instant it trails the leader by the replication lag — normally single-digit ms, but it balloons to seconds under write spikes, long transactions, or a saturated follower. Any read off an async follower may be stale by up to the current lag. This is not a bug to fix; it is the contract. Lesson 07 names the consistency models that tame it.
The lag problems and their session fixes (preview of 07)
- Read-your-own-writes: a user posts a comment (write → leader), immediately reloads (read → lagging follower), and their own comment is missing. Fix: for a short window after a user's write, route that user's reads to the leader, or to a replica known to be caught up past the write's log position.
- Monotonic reads: successive reads must not go backwards in time. Read 1 hits a fresh follower, read 2 hits a more-lagged one, and data the user already saw vanishes. Fix: pin a given user to a single replica (e.g. hash userID → replica) so they always read from one timeline.
- Consistent prefix: if writes are causally ordered (question then answer), a reader must never see the answer before the question. Fix: ensure causally related writes go through the same partition/order, or carry causal tokens.
Multi-leader replication
Run a leader in each region (or each datacenter). Local clients write to their local leader at LAN latency; leaders asynchronously replicate to each other. This survives the loss of an entire leader and gives every region fast local writes — the headline use cases are multi-datacenter deployments and offline-capable clients (a phone is its own leader until it syncs).
The tax is write conflicts: two leaders concurrently modify the same key and only learn of each other later. Now you must merge. Conflict resolution strategies, worst to best in fidelity:
| Strategy | Mechanism | Cost |
|---|---|---|
| Last-write-wins (LWW) | Highest timestamp wins | Silently discards the loser; clock skew picks the "winner" arbitrarily — real data loss |
| Version vectors | Per-replica counters detect concurrent vs causal updates | Detects conflicts reliably but still hands you two values to merge |
| CRDTs | Data types whose merge is commutative/associative/idempotent (counters, OR-sets) | Conflict-free by construction, but you must model state as a CRDT |
| Application merge | App-defined resolver (e.g. union shopping carts) | Correct for your domain; you write and test the merge logic |
Replicas A and B both accept a write to the same key during a partition. Each tags its new version with a per-replica counter: A produces {A:1}, B produces {B:1}. When the partition heals and they compare, neither version dominates the other — {A:1} has not seen B's write, {B:1} has not seen A's — so the system detects a concurrent write (a conflict to resolve) rather than silently overwriting one with the other. Contrast last-write-wins, which would compare timestamps and quietly discard the loser.
Rule of thumb: prefer single-leader unless you genuinely need writes in multiple regions or offline. The moment you accept multi-leader you have signed up to own conflict resolution forever.
Leaderless / quorum replication (Dynamo-style)
No leader at all. The client (or a coordinator on its behalf) writes to several replicas and reads from several. With N replicas, a write is acknowledged once W replicas confirm, and a read consults R replicas and returns the freshest version (by version stamp). The whole guarantee rides on one inequality:
W + R > N
If the write set (any W nodes) and the read set (any R nodes) must overlap, they share at least one node — by pigeonhole, W + R > N forces overlap, so every read set contains at least one node that saw the latest acked write. The read picks the highest version among the R responses and returns it. Pick the version stamp (vector clock / timestamp) so "freshest" is well defined.
The knobs are independent and tunable per query class:
- Large W → durable, conflict-resistant writes, but slower (wait for the W-th fastest ack) and less write-available (need W up).
- Large R → fresher reads, but slower and less read-available.
- W = N: maximum durability, but a single node down blocks all writes (zero write fault-tolerance).
- W = 1, R = N: fast lossy writes, expensive strong reads — used when writes vastly outnumber reads.
Stragglers are reconciled by read-repair (on a read, push the newest version to any replica found stale) and background anti-entropy (Merkle-tree diffing — replicas exchange a tree of hashes to find exactly which keys differ, without shipping all the data). During partitions, hinted handoff and sloppy quorums keep writes flowing by accepting them on substitute nodes — but a sloppy quorum's W nodes may not be the "home" nodes, so the W + R > N overlap no longer guarantees you read the latest. You trade strict consistency for write availability, exactly the CAP dial of lesson 09.
Target: tolerate one node failure on both the read and write path, with strong reads. Choose N = 3. Need N − W ≥ 1 ⇒ W ≤ 2, and N − R ≥ 1 ⇒ R ≤ 2, and W + R > 3. Take W = 2, R = 2: 2 + 2 = 4 > 3 ✓, fault tolerance N−W = 1 and N−R = 1 ✓. Write latency = the 2nd-fastest of 3 acks (one slow replica is masked). To tolerate two failures you'd need N = 5, W = 3, R = 3 (3 + 3 = 6 > 5), at the cost of higher per-op latency and 5× storage.
Failover hazards
When the leader dies, a follower must be promoted. This is where replication's quiet trade-offs become loud incidents (and forward-references lessons 10 and 11):
- Lost tail (RPO): with async replication the new leader is missing the writes the old leader hadn't shipped yet. Those writes are gone. If the old leader later rejoins, its extra writes are usually discarded — which can violate other systems that already acted on them (e.g. an autoincrement ID reused).
- Split-brain: a network partition makes two nodes each believe they are leader; both accept writes; the data diverges irreconcilably. Prevention requires fencing (a fencing token / STONITH) and ultimately a real consensus protocol to elect exactly one leader — lesson 10.
- Detection vs false failover: too-short a timeout causes needless failovers (and cascading load); too-long leaves you down. There is no safe default — it must be tuned and the whole failover path must be regularly tested, not assumed.
"We have replicas, so we're durable and highly available." Async replicas give you a non-zero RPO (you will lose the tail on failover) and an untested promotion path is a guaranteed outage. Replication is necessary for HA, not sufficient — it must be paired with consensus-backed leader election (10) and tested failover (13).
Quorum explorer
Set N, W, R and watch the overlap guarantee, the fault tolerance on each path, and the qualitative write latency. Confirm the math: strong reads require W + R > N.
Interview prompts you should be ready for
- Why replicate at all, and what does each copy cost you? (senior answer): three benefits — durability, read scaling, availability/geo-latency. The single cost is divergence: copies disagree until propagation completes, which forces a durability-vs-latency choice on every write and a consistency model on every read.)
- Sync vs async replication — pick one for a payments ledger and one for a social feed. (senior answer): payments → sync/semi-sync, RPO must be zero; a lost write is real money. Feed → async, a few seconds of lag is invisible to users and the latency/availability win is large. Semi-sync is the usual middle: one synchronous ack for durability, the rest async for speed.)
- A user posts then immediately can't see their post on refresh. Diagnose and fix without making everything strongly consistent. (senior answer): replication lag — the read hit a follower behind the write. Fix with read-your-own-writes: route that user's reads to the leader for a short window, or to a replica caught up past the write's log position. Don't promote the whole system to strong reads for one session guarantee.)
- Derive W + R > N from first principles and explain what breaks it in practice. (senior answer): any W-write set and any R-read set must share a node so the read sees the latest write; by pigeonhole that requires W + R > N. Sloppy quorums break it — writes land on substitute nodes, so the home read set may miss them; you've traded the overlap guarantee for write availability under partition.)
- When would you choose multi-leader, and what's the bill? (senior answer): multi-region low-latency writes or offline clients. The bill is conflict resolution — concurrent writes to the same key must be merged. LWW is lossy (clock-dependent); prefer version vectors to detect, then CRDTs or app-level merge to resolve. If you don't need multi-region writes, stay single-leader.)
- Leader dies. Walk me through promotion and everything that can go wrong. (senior answer): detect (timeout, beware false positives), elect a new leader (needs consensus to avoid two leaders), re-point clients. Hazards: async tail loss (non-zero RPO), split-brain without fencing, the old leader rejoining with extra writes. Failover must be fenced and tested, not assumed.)
- What's the difference between N=3,W=3,R=1 and N=3,W=1,R=3? (senior answer): both satisfy W+R>N so both give strong reads. W=3,R=1: durable writes but zero write fault-tolerance (any node down blocks writes) and cheap reads — good for read-heavy with rare writes. W=1,R=3: fast highly-available writes, expensive reads, and W=1 risks losing a write if its one node dies before replication — choose by read/write ratio and durability needs.)
- How do leaderless systems heal stragglers? (senior answer): read-repair pushes the freshest version to stale replicas seen during a read; anti-entropy runs in the background, diffing replicas via Merkle trees to converge data that's never read. Hinted handoff stores writes for a temporarily-down home node and replays them on recovery.)
Replication keeps multiple copies of each datum for durability, read scaling, and availability — and the unavoidable price is that the copies disagree. Single-leader is the default: pick sync (zero RPO, slower) vs async (fast, lossy tail) vs semi-sync (the usual compromise), and patch lag with session guarantees. Multi-leader buys multi-region/offline writes at the cost of conflict resolution. Leaderless quorums tune durability and freshness with W and R, where W + R > N is the overlap that makes reads see the latest write. Whatever you pick, an async tail and an untested failover are your real exposure — replication needs consensus (10) and tested fault handling (13) to actually deliver HA.