Replication¶

Prerequisites: Consistency Models, CAP Theorem

← Consistency Models | Next: Consensus & Raft →

Why This Exists¶

Every distributed database keeps multiple copies of the same data — for durability (a disk dies, you don't lose data), for availability (a node dies, you still serve traffic), and for latency (serve reads from the datacenter closest to the user). The moment you have more than one copy, you have to answer: who is allowed to write, and how do the other copies find out?

Every answer to that question is a replication topology, and every topology trades off latency, durability, and availability differently. Pick the wrong one and you either lose acknowledged writes on failover, silently serve stale reads, or build a system that can't tell two conflicting writes apart.

Abstraction Levels¶

The Three Topologies¶

graph TD
    subgraph "Leader-Follower"
        L1[Leader] -->|replicate| F1[Follower]
        L1 -->|replicate| F2[Follower]
    end
    subgraph "Multi-Leader"
        M1[Leader A] <-->|replicate| M2[Leader B]
        M2 <-->|replicate| M3[Leader C]
        M1 <-->|replicate| M3
    end
    subgraph "Leaderless / Quorum"
        Q1[Node 1] <--> Q2[Node 2]
        Q2 <--> Q3[Node 3]
        Client((Client)) -->|write to W of N| Q1
        Client -->|write to W of N| Q2
    end
    style L1 fill:#1565c0,color:#fff
    style M1 fill:#f57f17,color:#fff
    style M2 fill:#f57f17,color:#fff
    style M3 fill:#f57f17,color:#fff
    style Q1 fill:#00838f,color:#fff
    style Q2 fill:#00838f,color:#fff
    style Q3 fill:#00838f,color:#fff

Leader-Follower (Primary-Replica)¶

One node (the leader) accepts all writes. It streams a change log to followers, which apply it and can serve reads. Simple mental model: one writer, many readers.

• Used by: PostgreSQL streaming replication, MySQL replication, MongoDB replica sets, Kafka partitions.
• Failure mode: if the leader dies, someone must be promoted — see Failover below.

Multi-Leader¶

Multiple nodes (often one per datacenter) each accept writes and replicate to each other. Good for multi-region write locality — a European user writes to the EU leader, an Asian user writes to the APAC leader — but two leaders can accept conflicting writes to the same record before either replicates to the other.

• Used by: multi-datacenter MySQL/Postgres setups, CouchDB, some CDN edge configs.
• Failure mode: conflicting writes require resolution — see Conflict Resolution below.

Leaderless / Quorum-Based (Dynamo-style)¶

No node is special. Clients (or a coordinator) write to W of N replicas and read from R of N replicas directly, relying on R + W > N overlap (see Consistency Models — Quorums) to surface the latest write. Replicas gossip and repair themselves (read repair, anti-entropy, hinted handoff) rather than relying on a single replication stream.

• Used by: original Amazon Dynamo (the paper), Apache Cassandra, Riak. DynamoDB the service is not leaderless — each partition has a leader replica that takes writes, then replicates to followers in other AZs. Do not conflate Dynamo with DynamoDB in an interview.
• Failure mode: concurrent writes to the same key from different clients — resolved via LWW, version vectors, or CRDTs.

Interactive Simulation¶

Dial replication factor and read/write quorum, then kill nodes and inject latency. Watch successful writes collapse before availability does — quorum failures show up as write errors long before the cluster looks "down."

Kill enough nodes that up < W and writes start failing outright — that's the quorum, not the cluster, running out of room. With R + W > N (strict quorum), stale reads stay near zero even under latency spikes; drop to R=1 (weak quorum) and the same node kills produce many more stale reads instead of failed ones — the trade-off is failure mode, not just a number going up or down.

How It Works Internally¶

Synchronous vs Asynchronous Replication¶

The leader has a choice for every write: wait for followers to confirm before acknowledging the client (synchronous), or acknowledge immediately and replicate in the background (asynchronous).

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F as Follower
    Note over C,F: Synchronous
    C->>L: Write x=5
    L->>F: Replicate x=5
    F-->>L: ACK (persisted)
    L-->>C: OK (durable on 2 nodes)
    Note over C,F: Asynchronous
    C->>L: Write x=5
    L-->>C: OK (durable on 1 node only)
    L->>F: Replicate x=5 (in background)

Most production systems use a middle ground: semi-synchronous — wait for acknowledgment from at least one follower (not all), so durability improves without fully coupling availability to every follower's health.

Replication Lag¶

Asynchronous followers apply the log some delay behind the leader — replication lag. This is the mechanism, not an edge case; it's the direct cost of choosing lower write latency.

Production symptoms: - Stale reads: a user writes, then reads from a lagging follower and doesn't see their own write (a read-your-writes violation — see Consistency Models). - Monotonic-read violations: a user refreshes and sees older data than they did a moment ago, because their read was load-balanced to a more lagged replica than last time. - Split-brain risk: if lag detection is broken or the leader/follower roles are ambiguous during a network hiccup, two nodes can both believe they're the leader and accept writes independently — the most dangerous replication failure, because it silently creates two divergent histories.

Failover Mechanics¶

When the leader dies (crash, network partition, disk failure), something has to pick a new one:

1. Detect the leader is gone — usually a missed-heartbeat timeout.
2. Elect a new leader — the follower with the most up-to-date log (or, in consensus-based systems, a majority vote; see Raft for exactly how term-based election and log-completeness voting works).
3. Reconfigure clients and other followers to point at the new leader.
4. Reconcile any writes the old leader accepted but never replicated — these are typically lost if the old leader used async replication, or discarded/re-applied depending on the system's rules.

Naive (human-operated) failover takes minutes and risks promoting a follower that's missing the last few writes. Consensus-based failover (Raft, Paxos) automates steps 1–2 safely: a candidate can only win an election if its log is at least as complete as a majority of voters, which is exactly the mechanism that prevents promoting a follower that would silently drop committed writes. See Consensus & Raft for the full mechanics of terms, elections, and commit index.

Conflict Resolution¶

In multi-leader and leaderless topologies, two writes to the same key can happen concurrently on different nodes before either has heard about the other. Something must decide the outcome when they meet:

Worked Example: Global E-Commerce Checkout¶

A checkout service replicates order data across 3 regions.

Leader-follower, async, single US leader: EU customers write across the Atlantic (100ms+ RTT) to the leader — slow checkout, but no conflicts. A US region outage means the leader is gone; failover takes a manual runbook or a consensus layer, and any order acknowledged in the last replication window may vanish.

Multi-leader, one leader per region: EU customers write locally (low latency). But if the same customer opens two tabs and one checkout hits the EU leader while a duplicate-click retry hits the US leader before they've synced, you get two "orders" for one cart — needs LWW (risky — could silently drop a real order) or, better, idempotency keys generated client-side so duplicate writes are detected as the same write rather than a conflict to resolve.

Leaderless, N=3, W=2, R=2 quorum: Any node accepts the write; R+W > N guarantees a read overlaps a write. Handles regional outages gracefully (any 2 of 3 nodes suffice), but concurrent duplicate submissions still need idempotency keys or version vectors at the application layer — quorum consistency doesn't remove the need for conflict-aware design, it just changes where the seams are.

In all three, the actual fix for "duplicate order" is the same: an idempotency key on the client request, independent of the replication topology. The topology determines latency and failover behavior; correctness under concurrent client mistakes is usually an application-layer concern layered on top.

Failure Modes¶

Production Debugging¶

Symptom: users report stale or missing data intermittently

1. Check replication lag per replica
   → seconds behind leader; is one replica consistently worse?
2. Check which replica served the read
   → load balancer / router logs; is read routing sticky or random?
3. Check leader election history
   → how many failovers in the last 24h? Flapping leader = deeper problem (disk, GC, network)
4. Check for split-brain indicators
   → two nodes both claiming leadership in logs/metrics at the same timestamp
5. Check write acknowledgment mode
   → was this write sync or async? Does durability expectation match reality?
6. Check for conflict resolution activity (multi-leader/leaderless)
   → sibling/version counts, LWW discard rate — is conflict volume higher than expected?

Key metrics to monitor: - Replication lag (p50/p99, per follower) - Leader election / failover count and duration - Write acknowledgment latency (sync vs async paths, separately) - Conflict/merge rate in multi-leader or leaderless systems - Fsync and disk I/O latency on the leader (root cause of most lag spikes)

Scaling Limits¶

• Leader-follower scales reads horizontally (add followers) but write throughput is capped by a single leader's disk and CPU — this is the same ceiling discussed in Raft's scaling limits.
• Multi-leader scales writes across regions but conflict-resolution cost grows with concurrent write rate to the same keys — fine for mostly-partitioned key spaces (each region owns its own users), painful for shared hot keys.
• Leaderless/quorum scales writes best of the three (no single write bottleneck) but pays a tunable latency cost per operation (R/W round trips) and pushes correctness work into the application via conflict resolution.
• All three are ultimately bounded by network RTT between replicas for any synchronous guarantee — physics, not configuration, sets the floor.

Trade-offs¶

Interview Questions¶

Reasoning Exercises¶

1. Multi-region social feed: posts should appear near-instantly to the author's region, but eventually everywhere. Which topology, and what happens to a post if two regions partition from each other for 10 minutes?

2. Inventory counter under multi-leader replication: two regions both decrement the same item's stock concurrently, dropping it below zero when merged with LWW. Redesign the conflict resolution to make this impossible — what data structure or protocol would you reach for, and why?

3. Failover blast radius: a leader-follower cluster promotes a follower that was 30 seconds behind. What's the actual impact on clients mid-request, and how would synchronous replication, consensus-based election (Raft), and idempotency keys each independently reduce the damage?

Key Takeaways¶

Previous: Consistency Models | Next: Consensus & Raft