S071 · Replication — Leader/Follower, Multi-Leader, Leaderless

Module M08: Distributed Systems · Session 71 of 130 · Track: SYS 🔁

What you'll be able to do after this session

• Explain Replication to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S070 — CAP & PACELC — the Actual Trade-Offs

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Database Replication Explained (Hussein Nasser) — 15-minute plain-English tour of leader/follower vs multi-leader vs leaderless.
• 🎥 Deep dive (30–60 min) · MIT 6.824 · Replicated State Machines (Robert Morris) — the MIT distributed-systems lecture on how replication really works.
• 🎥 Hands-on demo (10–20 min) · Postgres Streaming Replication Setup (Database Star) — configure a leader + follower live.
• 📖 Canonical article · PostgreSQL 16 Docs — High Availability, Load Balancing, and Replication — the canonical reference; skim the intro and §27.2.
• 📖 Book chapter / tutorial · DDIA Ch.5 — Replication (Kleppmann, O'Reilly) — the definitive treatment.
• 📖 Engineering blog · GitHub — MySQL High Availability at GitHub — how GitHub actually runs leader/follower MySQL at scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: How systems stay up when a node dies.

Imagine a small library that owns a single copy of a very popular book. Every reader walks to that one shelf; if the shelf collapses, nobody can read. Now imagine the librarian photocopies the book and puts one copy in every branch — readers get faster access, and if one branch burns down, the book still exists elsewhere. That is replication: keeping the same data on multiple machines so the system survives failures and serves reads faster.

Replication exists because disks fail, servers crash, and network cables get cut by backhoes — but users still expect their timeline, their bank balance, and their cart to be there. One copy = one bad day ends your product. Three copies across racks or regions = one machine dies at 3 AM and nobody notices.

The three patterns you'll see everywhere: leader/follower (one node accepts writes, the rest copy — Postgres, MySQL, Redis), multi-leader (several nodes accept writes and sync with each other — used for multi-datacenter and offline apps), and leaderless (any node accepts a write, clients read from many and pick the freshest — Dynamo, Cassandra).

Gotcha to carry forever: replication does not give you consistency for free. The moment a write is accepted on the leader but not yet on the follower, a reader hitting the follower sees stale data. Every replication design is a specific answer to "how stale is okay, and what happens when the leader dies mid-write?"

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Below is the leader/follower flow — the single most common shape in production databases.

Worked example — async vs sync. Alice books the last concert ticket at t=0 ms on the leader. Then:

At t=5 ms Bob refreshes and hits Follower 2, which hasn't yet applied Alice's insert — Bob sees the ticket as available and clicks buy. That is replication lag, root cause of half the "why does the UI show old data?" bugs you'll ever see.

Multi-leader vs leaderless in one picture.

Multi-leader: both continents accept local writes (fast), then reconcile async — you now need conflict resolution (LWW, CRDTs, human review). Leaderless: the client sends writes to W nodes and reads from R nodes; if R + W > N (N = total replicas) you always overlap at least one node with the freshest value — the Dynamo quorum trick.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Spin up a Postgres leader with a streaming replica in Docker, watch replication lag, then kill the leader.

#!/usr/bin/env bash
# save as repl-demo.sh · run: bash repl-demo.sh
set -euo pipefail
NET=repl-net
docker network create $NET 2>/dev/null || true
 
# 1. Leader
docker run -d --name pg-leader --network $NET \
  -e POSTGRES_PASSWORD=secret -e POSTGRES_DB=demo -p 5432:5432 \
  postgres:16 -c wal_level=replica -c max_wal_senders=5 -c hot_standby=on
sleep 5
 
# 2. Replication user + pg_hba
docker exec -u postgres pg-leader psql -d demo -c \
  "CREATE ROLE repl WITH REPLICATION LOGIN PASSWORD 'repl';"
docker exec -u postgres pg-leader bash -c \
  "echo 'host replication repl 0.0.0.0/0 md5' >> /var/lib/postgresql/data/pg_hba.conf"
docker exec -u postgres pg-leader psql -c 'SELECT pg_reload_conf();'
 
# 3. Follower via pg_basebackup
docker run -d --name pg-follower --network $NET \
  -e PGPASSWORD=repl -p 5433:5432 postgres:16 bash -c '
    rm -rf /var/lib/postgresql/data/*
    pg_basebackup -h pg-leader -U repl -D /var/lib/postgresql/data -Fp -Xs -P -R
    exec postgres -c hot_standby=on'
sleep 8
 
# 4. Write on leader, read from follower
docker exec -u postgres pg-leader psql -d demo -c \
  "CREATE TABLE t(id serial, ts timestamptz default now()); INSERT INTO t DEFAULT VALUES;"
sleep 1
docker exec -u postgres pg-follower psql -d demo -c 'SELECT * FROM t;'
 
# 5. Measure lag
docker exec -u postgres pg-leader psql -d demo -c \
  "SELECT client_addr, state, sent_lsn, replay_lsn,
          pg_wal_lsn_diff(sent_lsn, replay_lsn) AS lag_bytes
   FROM pg_stat_replication;"

Observe (checklist):

1. pg_stat_replication on the leader lists the follower in streaming state.
2. The row inserted on the leader appears on the follower within ~1 second.
3. lag_bytes is normally 0; run pgbench -c 20 -T 30 on the leader and watch it grow.
4. Kill the leader (docker stop pg-leader) — writes fail immediately, but reads on the follower still work.
5. Promotion requires an explicit pg_ctl promote; nothing happens automatically.

Try this modification: add a second follower and set synchronous_standby_names = 'ANY 1 (*)' on the leader. Stop one follower — writes still succeed because any one live follower satisfies the quorum. That's synchronous quorum replication in two lines of config.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

War stories almost never come from replication itself — they come from failover and replication lag under load.

GitHub, October 2018. A 43-second network partition triggered automated MySQL failover. The old primary came back and, because fencing was incomplete, both regions accepted writes for a short window. Reconciliation took 24 hours and required per-repository manual work. The public postmortem is a masterclass: the fix wasn't "better replication" but better fencing (STONITH) and human-in-the-loop promotion.

Common bugs top teams hit:

• Read-your-writes violations. User updates avatar (write to leader), gets redirected, read hits a lagging follower, sees the old avatar. Fix: route the user's own reads to the leader for a few seconds after their write, or stamp a read-consistency token.
• Replication lag death spiral. A giant UPDATE takes 10 min to replay on followers (single-threaded WAL apply in older MySQL/Postgres). Followers fall behind, get pulled from the read pool, remaining followers take more traffic and also fall behind — cascade failure. Fix: parallel apply (Postgres 14+, MySQL 8), and chunk large writes.
• Split-brain in multi-leader. Two DCs both accept writes to the same PK during a partition. LWW silently drops one write. Use tunable quorums and make conflict resolution explicit.
• Silent follower drift. A follower with a bad disk applies WAL but produces different bytes. You only find out at failover when customer balances shift. Tools: pg_checksums, periodic checksum jobs.

Netflix, Uber and Shopify treat replication as a first-class product concern: continuous failover drills ("game days"), P99 replication lag as an SLO, and read paths built to tolerate followers being seconds — not milliseconds — behind.

(e) Quiz + exercise · 10 min

1. What is the difference between synchronous and asynchronous replication, and what does each cost you?
2. In a leader/follower setup, what happens to writes when the leader dies before a follower has been promoted?
3. Explain the formula R + W > N in a leaderless (Dynamo-style) system in plain English.
4. Give one concrete example of a bug caused by replication lag that a user would notice.
5. Why is multi-leader replication almost always paired with a conflict-resolution strategy, but leader/follower usually isn't?

Stretch (connects to S070 · CAP & PACELC): A leaderless system with R=1, W=1, N=3 is extremely fast and highly available. In CAP/PACELC vocabulary from S070, describe exactly which guarantees you've given up, and sketch a scenario where a user sees a value they wrote disappear.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Replication? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S072): Consistency Models — Linearizable, Sequential, Eventual
• Previous (S070): CAP & PACELC — the Actual Trade-Offs
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.