Leader/Follower Replication#

Problem statement (interviewer prompt)

Design the replication layer of a relational database for high availability + read scale. Cover synchronous vs asynchronous vs semi-synchronous modes, failover semantics, replica lag handling, and how to provide read-your-writes within a session.

flowchart LR
  C([Clients])
  L[(Leader<br/>writes)]
  F1[(Follower 1)]
  F2[(Follower 2)]
  C -->|writes| L
  L -. replicate log .-> F1
  L -. replicate log .-> F2
  C -->|reads| F1
  C -->|reads| F2

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C client;
    class L,F1,F2 datastore;

flowchart TB
  subgraph App[Application]
    W[Write traffic]
    R[Read traffic]
  end

  subgraph Primary[Primary / Leader]
    PRI[(Primary DB)]
    WAL[WAL / Binlog]
    POS[LSN / GTID position]
  end

  subgraph Sync[Sync Replicas - same DC]
    SR1[(Sync Replica 1)]
    SR2[(Sync Replica 2)]
  end

  subgraph Async[Async Replicas - cross-region/read scaling]
    AR1[(Async Replica<br/>read-only)]
    AR2[(Async Replica<br/>analytics)]
    AR3[(Cascading Replica)]
  end

  subgraph Failover[Failover & HA]
    SENT([Sentinel / Orchestrator])
    VIP[Virtual IP / DNS swap]
    FENCE[Fencing / STONITH]
    LAG[Replica lag monitor]
  end

  subgraph Modes
    SYNC[Synchronous: ack on N replicas]
    SEMI[Semi-sync: ack 1 replica]
    ASYNC[Async: ack from leader only]
  end

  W --> PRI
  PRI --> WAL
  WAL -. ship .-> SR1
  WAL -. ship .-> SR2
  WAL -. ship .-> AR1
  AR1 -. cascade .-> AR3
  WAL -. ship .-> AR2
  R -->|read-your-write| PRI
  R -->|eventually consistent| AR1
  R -->|eventually consistent| AR2
  SENT -.health.-> PRI
  SENT -.health.-> SR1
  SENT -. promote .-> SR1
  SENT --> VIP
  SENT --> FENCE
  LAG -.alert.-> SENT

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class VIP edge;
    class W,R,WAL,POS,FENCE,LAG,SYNC,SEMI,ASYNC service;
    class PRI,SR1,SR2,AR1,AR2,AR3 datastore;
    class SENT compute;

Replication mechanics#

Statement-based: SQL replayed. Cheap but non-deterministic (NOW(), RAND()).
Row-based: serialized row diff. Deterministic, larger volume.
WAL/redo shipping (Postgres physical, Oracle redo): byte-level.
Logical/CDC (Postgres logical, Debezium): row events for downstream consumers.

Replication topologies#

Single leader (most common).
Multi-leader (geo, conflict resolution needed: LWW, CRDT, app-defined).
Leaderless (Dynamo): clients write to N, read from N, R+W>N.

Failover steps#

Detect leader down (heartbeat, quorum check).
Pick most-up-to-date replica.
Fence old leader (STONITH).
Promote new leader, repoint app/VIP.
Re-attach stale replicas (rebuild if diverged).

Replication lag#

Causes: long-running tx, single-threaded apply (older MySQL), network.
Symptoms: read-after-write stale, broken pagination.
Mitigation: read from primary for critical paths, monotonic-read session, parallel applier.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Load balancer / GSLB	L4/L7 traffic distribution and failover	load-balancer
`HLD`	Raft / Paxos consensus	replicated state machine via majority quorum	consensus-raft-paxos
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`HLD`	LSM vs B-Tree engines	WAL, memtable, SSTables, compaction	storage-engines-lsm-btree
`HLD`	CRDTs	commutative replicated data types	crdts
`HLD`	Change Data Capture	WAL/binlog tailing, outbox publishing	change-data-capture
`HLD`	Multi-region & DR	RTO / RPO, active-active, failover	multi-region-dr

Quick reference#

Why#

HA: survive primary loss.
Read scale: serve reads off followers.
Analytics isolation: dedicated replica for OLAP.
Geo: place followers near readers.

Sync vs async vs semi-sync#

Mode	Durability on primary loss	Write latency
Async	last txs may be lost	low (1 fsync)
Semi-sync	1 replica safe	+1 RTT
Sync	N replicas safe	bounded by slowest

Many production systems use one sync replica + many async (Postgres, MySQL group repl, Aurora).

Lag management#

Monitor seconds_behind_master / pg_stat_replication.
Backpressure writes if lag > threshold.
Session-bound routing: read_after_write → primary for next K seconds.

Failover patterns#

Manual (safest), automated (Patroni, Orchestrator, Sentinel).
Split-brain prevention: fencing tokens, etcd lease, STONITH.
VIP swap vs DNS swap vs proxy (PgBouncer/ProxySQL).

Refs#

Designing Data-Intensive Applications, ch. 5.
Postgres streaming replication docs, MySQL replication doc, Aurora paper (SIGMOD '17).
Orchestrator (GitHub MySQL HA), Patroni (Zalando).

FAQ#

What is the difference between synchronous and asynchronous replication?#

Synchronous replication waits for replicas to confirm before acking writes, protecting data on primary loss but adding latency. Asynchronous replication acks immediately and risks losing the last few transactions on failover.

How do you handle replication lag?#

Monitor seconds behind master or pg_stat_replication, route read-after-write traffic to the primary for a short window, and use a parallel applier to speed up replay on busy followers.

What causes split-brain during database failover?#

Split-brain happens when the old primary keeps accepting writes after a new one is promoted. Fencing tokens, STONITH, or an etcd lease ensure only one node holds write authority at a time.

When should I use semi-synchronous replication?#

Choose semi-sync when you want stronger durability than async but cannot afford the tail latency of full sync. One replica acks each write, costing roughly one extra round trip.

Can read replicas serve all reads safely?#

Only for eventually consistent paths. For read-your-writes flows like checkout confirmation, route the next reads to the primary or use session-bound routing for a few seconds after the write.

Consistent Hashing: consistent hashing determines which replica set owns a given partition in distributed databases
CAP and PACELC Theorems: synchronous vs. asynchronous replication choices define a system's position in the CAP/PACELC space
Database Sharding: each shard in a sharded database uses leader-follower replication for fault tolerance