Replication · 1 of 2

Leader-Based Replication

One node takes every write and the rest copy it. It's the simplest way to keep many copies of a database, and its failure modes have taken GitHub down twice.

≈ 25 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

Why replicate

Keeping a copy of the same data on several machines buys you three things:

  • Availability. If one machine dies, another has the data and can keep serving.
  • Read throughput. Many copies can answer many reads in parallel.
  • Latency. A copy in Frankfurt answers a European user faster than one in Virginia.

If the data never changed, replication would be trivial: copy it once, done. All of the difficulty is in changes. Every write has to reach every copy, in the right order, while machines crash and networks drop packets, and readers have to cope with copies that are a moment out of date.

This lesson covers the most common answer, used by PostgreSQL, MySQL, SQL Server, Oracle, MongoDB and Kafka among many others. The next lesson covers the alternatives, where several nodes accept writes.

Leaders and followers

One replica is the leader (also called primary or source). Every write goes to it. The others are followers (replicas, secondaries, standbys).

  1. A client sends a write to the leader, which writes it to its own storage.
  2. The leader appends the change to its replication log and streams the log to every follower.
  3. Each follower applies the changes in exactly the order the leader wrote them.
  4. Reads can go to the leader or to any follower. Writes go only to the leader.

Because one node decides the order of every write, there are no write conflicts to resolve: the leader’s log is the history. Each follower is just somewhere along that log.

The log, replica by replica

Leadertakes writes#1#2#3#4at #4Follower Asynchronous#1#2#3#4at #4Follower Basynchronous#1#2#3#4at #4committedpendinglost on promotionLeader takes writes#1#2#3#4at #4Follower A synchronous#1#2#3#4at #4Follower B asynchronous#1#2#3#4at #4committedpendinglost on promotion
Committed entries are solid; pending ones are dashed. Each follower is a position in the leader's log.

That last frame contains most of this lesson. Followers are always at some position in the log. How far behind they are is replication lag, and which follower you promote when the leader dies decides what you lose.

Synchronous vs asynchronous

When the leader accepts a write, does it wait for followers before telling the client “OK”?

  • Synchronous: the leader waits until a follower confirms it has the write. The client’s OK then means two machines have it.
  • Asynchronous: the leader replies as soon as its own disk has the write and ships it to followers in the background.

Who waits for whom

Synchronous buys durability with latency and availability. Asynchronous buys speed with the risk of losing acknowledged writes.

Making every follower synchronous is impractical: any one slow or dead follower halts all writes. So real systems mix. One follower is synchronous and the rest are asynchronous; if the synchronous one fails, an asynchronous one is promoted to take its place. That guarantees an up-to-date copy on at least two nodes without letting one sick machine stop the world. This is usually called semi-synchronous.

Many deployments go fully asynchronous, especially across regions. Writes are fast and never block on a follower, but a write that was acknowledged can still be lost if the leader dies before shipping it. That’s a real weakening of durability, accepted for latency and availability.

PostgreSQL makes the choice per transaction with synchronous_commit. With synchronous standbys configured, remote_write waits until the standby has written the commit record to its OS, on waits until the standby has flushed it to durable storage, and remote_apply waits until the standby has replayed it, so a query on that standby can see it. local and off don’t wait for standbys at all. You can run your payments transactions with remote_apply and your analytics inserts with local on the same cluster.

The replication log

What exactly does the leader send? There are four answers, and the choice leaks into everything from upgrades to data correctness.

Statement-based. Ship the SQL text: UPDATE accounts SET balance = balance - 10 WHERE id = 7. Compact, but anything nondeterministic breaks it. RAND() or UUID() produce different values on each replica, and an UPDATE ... LIMIT without an ORDER BY can touch different rows. MySQL marks such statements unsafe for statement-based logging.MySQL does replicate NOW() correctly in statement mode, because the binary log carries the source’s timestamp with each event. SYSDATE() doesn’t get that treatment.

Write-ahead log shipping. The storage engine already writes every change to a write-ahead log for crash recovery. Send that same byte stream to followers, which replay it. PostgreSQL’s streaming replication does this. It’s exact, but it describes disk blocks, so leader and followers must run the same major version. That makes zero-downtime major-version upgrades hard.

Logical (row-based). Ship a separate log that describes changes at the row level: insert this row, update row 7’s balance from 50 to 40, delete row 9. It’s decoupled from the storage format, so followers can run a different version, or not be the same database at all. MySQL’s row-based binary log and PostgreSQL’s logical replication work this way. It’s also the foundation of change data capture: other systems can consume the same stream. MySQL has defaulted to row format since 5.7 and now deprecates the binlog_format setting, so row-based is where it’s heading.

Trigger-based. Database triggers write changes into a side table that an external process ships. It’s flexible (replicate a subset, transform on the way) but slower and more fragile, and it’s mostly legacy now.

Adding a follower

You can’t just copy the leader’s data files while it’s taking writes: you’d get a smear of different points in time. The standard procedure:

  1. Take a consistent snapshot of the leader, tied to an exact position in its log (an LSN in PostgreSQL, binlog coordinates or a GTID set in MySQL).
  2. Copy the snapshot to the new follower.
  3. The follower connects and requests every change after that position.
  4. When it has caught up, it streams like any other follower.

Step 3 only works if the leader still has those changes. If it has already recycled the log past that position, the follower can’t catch up and must be rebuilt from a new snapshot. PostgreSQL’s replication slots pin the log for a follower, at the risk of filling the leader’s disk if the follower disappears.

That exact situation began GitLab’s worst outage. On January 31, 2017, a load spike made the secondary lag, and then replication broke because the primary had already removed WAL segments the secondary still needed. While rebuilding the secondary late at night, an engineer ran the command to wipe its data directory on the primary instead. They stopped it a second or two after noticing, but about 300 GB were already gone. The regular backups turned out not to be working either, so GitLab restored from a snapshot taken six hours earlier and lost those six hours of database changes.

Failover

Followers dying is easy: one restarts and catches up from its last log position. The leader dying is the hard part. Someone has to promote a follower, every client has to start sending writes to it, and the other followers have to start following it. That’s failover. It can be manual, but usually it’s automatic:

  1. Detect that the leader has failed. There’s no reliable way to tell “crashed” from “slow” or “network blip”, so nodes use a timeout.
  2. Choose a new leader, ideally the follower with the most recent data, by election or by a controller.
  3. Reconfigure clients and followers to use it, and make sure the old leader, if it comes back, steps down.

Failover, and what it costs

With asynchronous replication, the new leader can only be as current as the best follower was.

Every step can go wrong:

  • Acknowledged writes get discarded. With asynchronous replication, the promoted follower may be missing the old leader’s last writes. When the old leader returns, its extra writes conflict with the new history, and the usual resolution is to throw them away.
  • Discarding is dangerous when other systems saw those writes. In September 2012, a GitHub MySQL cluster promoted a node its own operations team had already flagged as out of date. MySQL-generated IDs were also used as keys in Redis, so for records created in that window the two stores no longer agreed. Some events showed on the wrong users’ dashboards, and 16 private repositories were reachable by people outside their teams for seven minutes.
  • The timeout is a trade-off. Too long and writes are down for longer than they need to be. Too short and a load spike or a slow network triggers a failover that makes the overload worse. Patroni, the common PostgreSQL failover manager, defaults to a 30-second leader lock.
  • Two nodes can both believe they’re the leader. That one gets its own section.

Split brain

Split brain is two leaders at once, both accepting writes, with no way to merge their histories afterwards. It happens when the old leader is merely cut off rather than dead: the rest of the cluster promotes a replacement, and the old one keeps serving whoever can still reach it.

Two leaders

Data centre EastData centre West
A partition doesn't kill the old leader. Unless something forces it to stop, it keeps accepting writes.

GitHub lived this on October 21, 2018. During routine maintenance to replace failing 100G optical equipment, the link between its US East Coast network hub and its primary East Coast data centre went down for 43 seconds. GitHub’s failover tool, Orchestrator, runs its own Raft consensus across sites. The nodes in the West Coast and in a public cloud region formed a quorum and promoted the West Coast databases to primary.

When the link came back, both sides had writes the other lacked. The East Coast held a few seconds of writes never replicated West; the West Coast had taken nearly 40 minutes of writes from the application tier. Failing back would have discarded the West’s writes; staying put would have discarded the East’s.

43 snetwork partition between East Coast hub and data centre
954writes in the affected window on one of the busiest clusters
24 h 11 minof degraded service while GitHub reconciled by restoring from backup

GitHub chose to prioritise data integrity over site usability and time to recovery. It kept the West Coast as primary, restored the East Coast databases from backups, let them catch up, and only then failed back. The East’s unreplicated writes were captured from MySQL’s binary logs and reconciled afterwards, some automatically and some by contacting users.

The defences against split brain all share one idea: a leader must be able to prove it’s still the leader before it writes.

  • Majority leases. The leader holds a time-limited lease granted by a majority of nodes and stops writing the moment it can’t renew. Since only one side of any partition can hold a majority, only one leader can be writing. Patroni does this with a leader key in etcd, Consul or ZooKeeper: a primary that can’t renew the key demotes itself.
  • Fencing. Every new leader gets a higher epoch number, and storage rejects writes carrying an older one. The bluntest version is STONITH (“shoot the other node in the head”): power the old leader off before promoting.

Neither saves writes the old leader accepted before it noticed. With asynchronous cross-region replication, some loss on failover is part of the deal.

Replication lag

Asynchronous followers are the reason leader-based replication scales reads: add followers, spread reads across them. But every read from a follower can return slightly old data. Usually “slightly” means milliseconds; Amazon Aurora says its replicas typically lag much less than 100 ms behind the writer. Under load, during a large migration, or across regions, it can stretch to seconds or minutes.

If you stop writing and wait, every follower catches up. That’s eventual consistency, and “eventually” has no upper bound. Lag produces three specific anomalies, each with its own fix. The first two were named in a 1994 paper from Xerox PARC’s Bayou project, which defined guarantees per session rather than for the whole database.

Reading your own writes

Where did my comment go?

Your write went to the leader. Your next read went to a follower that hadn't seen it yet.

Read-your-writes consistency promises that a user always sees their own updates. It says nothing about other users’ updates. Ways to provide it:

  • Read what the user may have modified from the leader. Their own profile, say, while other profiles come from followers. If most things are editable, refine it: read from the leader for a minute after the user’s last write, or avoid followers that report more than a minute of lag.
  • Track a position. The client remembers the log position of its last write (in PostgreSQL, the LSN). A follower serves the read only once it has replayed past that position; otherwise wait or route elsewhere.
  • Make the write wait. PostgreSQL’s remote_apply doesn’t return until synchronous standbys have applied the write, so reads there see it.

The hard version is cross-device read-your-writes: write on your phone, read on your laptop. Any token has to live on the server, and the two devices may be routed to different data centres.

Monotonic reads

Time going backwards

Each read was individually plausible. Together, they told an impossible story.

Monotonic reads promise that once you’ve seen some data, you won’t later see an older version of it. Stale reads are allowed; going backwards isn’t. It’s weaker than strong consistency and stronger than plain eventual consistency.

The usual fix is to make each user read from the same replica every time, for example chosen by hashing the user ID. If that replica dies, reroute, and accept one possible step back (or carry a position token as above).

Consistent prefix reads

Answers before questions

Each partition's log is in order. There's no order *across* partitions unless you make one.

Consistent prefix reads promise that if writes happen in some order, anyone reading them sees them in that order: a prefix of history, never history with holes. Doug Terry’s “Replicated Data Consistency Explained Through Baseball” uses the same idea for a scoreboard: you may see an old score, but never runs that hadn’t been scored yet.

Inside one leader-based database this comes for free, because one log orders everything. It breaks in partitioned (sharded) databases, where each partition has its own leader and its own log, and they replicate independently. Fixes: put causally related writes in the same partition (a whole chat thread on one shard), or track causal dependencies explicitly.

Trade-offs

Mode OK means the write is on Writes block when If the leader dies
Fully synchronous every follower any follower is slow or down nothing acknowledged is lost
Semi-synchronous the leader and one follower no follower can acknowledge (MySQL then falls back to async) nothing lost, if the sync follower is promoted
Quorum commit k of a set of followers fewer than k can acknowledge nothing lost, if a follower that acknowledged is promoted
Asynchronous the leader’s disk only never recent acknowledged writes can be lost

In the real world

  • PostgreSQL ships its WAL to standbys (streaming replication) or decodes it into row changes (logical replication). synchronous_standby_names takes FIRST 2 (a, b, c) to wait on the two highest-priority standbys or ANY 2 (a, b, c) to wait on any two: quorum commit. PostgreSQL 17 (2024) added failover slots, so logical replication consumers can continue after a standby is promoted, and pg_createsubscriber to turn a physical standby into a logical one. Failover is left to external tools like Patroni.
  • MySQL replicates its binary log, row-based by default. Global transaction IDs (GTIDs) let a replica find its position on a new source after failover. Semisynchronous replication waits, by default, for one replica to acknowledge after the binlog is synced but before the storage engine commits (AFTER_SYNC). That ordering means a crash can’t leave a transaction visible on the source but missing from every replica.
  • Amazon Aurora separates compute from a replicated storage layer. Readers share the writer’s storage volume, so they only refresh cached pages instead of rebuilding their own copy, which is why replica lag is usually far below 100 ms.
  • Apache Kafka replicates each partition from a leader to followers. The in-sync replica set (ISR) is a dynamic version of semi-synchronous: with acks=all, a write is committed once every in-sync replica has it, and min.insync.replicas sets how small that set may shrink before writes are refused.

Pitfalls

  • “It’s replicated, so it’s durable.” With asynchronous replication, an acknowledged write lives on one disk until it ships. Know which mode you’re in, and whether semi-sync has silently fallen back.
  • Automatic failover without fencing. Promoting a replacement is easy. Making sure the old leader stops writing is the actual problem.
  • Promoting a stale follower. Pick the most up-to-date one, and remember that anything outside the database that saw the discarded writes (caches, search indexes, IDs handed to users) is now wrong.
  • Read replicas behind a load balancer, with no session guarantees. Users see their edits vanish and comments flicker. Decide which reads need read-your-writes or monotonic reads.
  • Treating lag as a constant. It’s milliseconds until a bulk import, a long-running query on a replica or a network event makes it minutes. Monitor it and decide what happens past a threshold.
  • Never testing failover. In GitHub’s 2018 incident, Orchestrator did exactly what it was configured to do. The application tier just couldn’t run against a primary on the other side of the country.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Multi-Leader & Leaderless Replication (what changes when more than one node takes writes) and Consensus (how to elect a leader that provably can’t be two).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in ReplicationMulti-Leader & Leaderless Replication