System Design, Step by Step

Part 4 · Databases & Data at Scale

Database Replication: Leader, Follower and Beyond

One database server will eventually die, drown in reads, or be too far from your users. How leader-follower replication works, what replication lag does to real users, why failover is so hard, and how multi-leader and quorum systems handle conflicts.

Lesson 2412 min readintermediate#database#replication

On this page

  1. The Problem
  2. The Core Idea
  3. How It Works
  4. Trade-offs
  5. In the Real World
  6. Interview Questions
  7. Key Takeaways
  8. Further Reading

The Problem

Your whole app depends on one database server. Sooner or later, three things will go wrong:

  1. It dies. A disk fails or the machine crashes. The whole app is down until the database is restored.
  2. It is overloaded with reads. Product pages, feeds and searches are 95% reads. One machine cannot keep up.
  3. Users are far away. Users in Europe wait 150 ms for each query to reach your database in India.

The answer to all three is replication. Replication means keeping copies of the same data on several machines. But copies bring new problems:

  • Which copy accepts writes?
  • What happens when copies disagree?
  • Why does a user update their profile, refresh, and see the old data?

The Core Idea

Think about the notice boards in a school.

  • The principal's office has the main notice board. Only the office writes new notices. (This is the leader.)
  • Every classroom has a copy of the board. A student runner carries each new notice from the office to every classroom. Students read the notices in their own classroom. (These classrooms are the followers, also called replicas.)

This works well. Reading is spread across many classrooms. If one classroom's board falls down, the others still have the notices. But there are problems:

  • The runner takes time, so for a few minutes a classroom may show yesterday's notice. This delay is called replication lag.
  • If the principal's office burns down, one classroom must become the new office. This switch is called failover.
  • What if two rooms both think that they are the office, and they post different notices? This is called split brain.

How It Works

Why replicate?

  • High availability: the app stays up. If one machine dies, another one has the data.
  • Read scaling: spread the reads across the replicas, so each machine does less work.
  • Lower latency: put replicas close to users in other regions.
  • Backups and analytics: run heavy reports or backups on a replica. The main database stays fast.

Single-leader replication (primary–replica)

In single-leader replication, one machine (the leader, also called the primary) accepts all writes. The other machines (the followers, also called replicas) copy its changes. This is the most common setup: PostgreSQL, MySQL, SQL Server, MongoDB replica sets and many more.

  1. 1
    App writes
    every INSERT/UPDATE/DELETE
  2. 2
    Leader / primary
    records each change in its log (WAL or binlog)
  3. 3
    Replicas 1, 2, 3
    replay the same changes in the same order
  4. 4
    App reads
    spread across replicas and the leader
Single-leader replication. One writer, many readers, one ordered log. · flow
  1. All writes go to the leader.
  2. The leader records every change in its log. A log is a file where changes are written in order (the WAL in PostgreSQL, the binlog in MySQL).
  3. Replicas receive the log and replay the same changes, in the same order. Replaying means doing the same changes again on their own copy.
  4. Reads can go to the leader or to any replica.

Synchronous vs asynchronous replication

Asynchronous (the most common default). To commit means to save a change for good. In asynchronous replication, the leader commits and replies "OK" without waiting for the replicas.

  • ✅ Fast writes. Slow or broken replicas do not block the leader.
  • ❌ If the leader dies, the most recent writes may not have reached any replica. They are lost after failover.

Synchronous. The leader waits until at least one replica confirms that it has the change. Only then does it reply "OK".

  • ✅ No data loss if the leader dies (a replica has everything).
  • ❌ Slower writes. If that replica is slow or down, writes stop and wait.

Semi-synchronous (a common compromise). The leader waits for one replica to confirm. It copies to the other replicas asynchronously. If the synchronous replica fails, another one takes over that role.

Asynchronous
  • •Commit → “OK” → replicas catch up later
  • +Fast writes; slow replicas never block
  • −Latest writes lost if the leader dies
  • −Replicas can serve stale reads
Use whenThe common default
Synchronous
  • •Commit → wait for replica ACK → “OK”
  • +No data loss on leader failure
  • −Every write pays the replica round trip
  • −A slow replica stalls writes
Use whenSemi-sync: one sync replica, the rest async
When does the leader say “OK”? · compare

Replication lag and the problems it causes

With async replication, replicas are usually behind the leader by only milliseconds. Under heavy load they can be behind by seconds or even minutes. This delay is the replication lag. It causes bugs that users can see:

1. Read-your-own-writes failure.

Leader
Asha
v1 · takes writes
Follower 1
Asha
v1 · in sync
Follower 2
Asha
v1 · in sync
write latency
~5 ms
Save a new name, then immediately read it back from a follower. Switch to synchronous replication and watch what you pay instead. · interactive

The user saves a change, but the next read goes to a replica that has not received it yet. The user thinks the update failed.

Fixes:

  • Read the user's own data (their profile, settings, recent posts) from the leader, at least for a short time after they write.
  • Remember the time (or log position) of the user's last write. Read only from replicas that have caught up to that point.
  • Update the screen at once in the browser (optimistic UI), so the user sees their change immediately.

2. Monotonic reads (going back in time). Monotonic means "never going backwards". Here, a user sees newer data and then older data.

Diagram
Refresh 1 ──► replica A (up to date)  → sees new comment
Refresh 2 ──► replica B (lagging)     → comment disappears!

The fix is to send each user to the same replica every time. For example, choose the replica by hashing the user ID (turning it into a number).

3. Consistent prefix (effects before causes). In systems where data is split into partitions, you might see an answer before the question it replies to. The two came from different copies with different lag. The fix is to keep writes that depend on each other together. Lesson 28 covers this more.

Monitor replication lag and set an alert for it. If a replica falls too far behind, remove it from the group of replicas that serve reads.

Failover: when the leader dies

  1. 1
    Detect
    heartbeats (regular "I am alive" signals) time out. Or was it just a short network problem?
  2. 2
    Choose
    pick the most up-to-date replica
  3. 3
    Promote
    it becomes the new leader
  4. 4
    Redirect
    apps and other replicas send writes to it
  5. 5
    Fence
    make sure the old leader can never accept writes again (for example, STONITH)
Failover, step by step. Each step has its own way to go wrong. · flow

It sounds simple, but it is one of the hardest jobs in databases:

  • Lost writes (with async replication). Writes that only the old leader had are lost. Or they cause conflicts when the old leader comes back.
  • False alarms. A short network problem can look like a dead leader. If you fail over too quickly, you cause trouble for no reason.
  • Split brain. The old leader was not really dead. It was only cut off. Now two leaders accept writes, and the data drifts apart.

Fencing prevents split brain. You make sure the old leader is really stopped, cut off from storage, or refused by the rest of the system. One fencing method has a dramatic name: "STONITH", which means Shoot The Other Node In The Head (switch the old machine off by force).

Consensus algorithms. Machines must decide "who is the leader?" in a safe way, even when messages are delayed or lost. Consensus algorithms like Raft and Paxos solve exactly this. The machines vote, and a leader needs a majority of the votes. So a cluster of 3 survives 1 failure, and a cluster of 5 survives 2. Tools like etcd, ZooKeeper and Consul give you this. Many databases (CockroachDB, TiDB, MongoDB and others) have it built in. For PostgreSQL, tools like Patroni handle automatic failover, using etcd or something similar.

Multi-leader replication

Here, several nodes accept writes. Often there is one leader per region. They copy their changes to each other. (A node is one machine in the cluster.)

Diagram
[Leader: India] ◄────────► [Leader: Europe] ◄────────► [Leader: US]
    ▲ writes                    ▲ writes                  ▲ writes
 local users                 local users               local users
  • ✅ Fast writes for users in every region. Each region keeps working if the links between regions fail.
  • ❌ Write conflicts. Two regions change the same record at the same time. Which change wins?

Conflict resolution strategies:

  • Last-write-wins (LWW): keep the change with the latest timestamp. It is simple. But it silently loses the other write. Also, the clocks of different machines are never perfectly in sync.
  • Merge the values: for example, join two sets of cart items into one.
  • CRDTs (Conflict-free Replicated Data Types): special data structures (counters, sets, text) that are built so that copies always merge automatically and correctly (Lesson 28).
  • Ask the user or the app: keep both versions and let the application (or the user) decide.

The best strategy is to avoid conflicts. Send all writes for one record (for example, one user) to the same "home" region.

Collaborative apps like Google Docs, and mobile apps that work offline, are really multi-leader systems. Every device accepts edits and syncs them later.

Leaderless replication (Dynamo-style)

There is no leader at all. The client (or a coordinator node) sends each write to several replicas at once. It also reads from several replicas at once. Cassandra, ScyllaDB, Riak and the original Amazon Dynamo (the system in the 2007 paper) work this way.

Quorums. A quorum is the minimum number of replicas that must agree. Say there are N copies of each piece of data:

  • a write succeeds when W replicas confirm,
  • a read asks R replicas and takes the newest value that it gets.

If W + R > N, every read meets at least one replica that has the latest write. The reason: the replicas that took the write and the replicas that answer the read must share at least one machine.

W=2, R=2
2 + 2 > 3
reads always see the latest write
W=1, R=1
1 + 1 ≤ 3
fastest, but reads may be stale
W=3, R=1
fast reads
but writes fail if any replica is down
Quorums with N = 3 copies. If W + R > N, every read overlaps the latest write. · numbers

You can tune W and R for each query. In Cassandra, for example, consistency levels like ONE, QUORUM and ALL let you trade speed against freshness of data.

How to keep replicas in sync without a leader:

  • Read repair: during a read, if one replica returns an old value, the reader updates that replica with the newer value.
  • Anti-entropy: background jobs compare the replicas and fix the differences. They often use Merkle trees. A Merkle tree is a tree of hashes (short fingerprints of data) that quickly shows which ranges of data differ.
  • Hinted handoff: if a replica is down, another node keeps its writes for a while. It hands them over when the replica comes back.
  • Sloppy quorums: during failures, accept writes on "stand-in" nodes to stay available. This improves availability. But it weakens the W + R > N guarantee.

How changes are shipped

  • Statement-based: send the SQL statements themselves. This is risky. Functions like NOW() or RAND() can give a different result on each replica.
  • Physical / WAL shipping: send the low-level changes to the disk files. This is exact. But it only works between the same database versions.
  • Logical (row-based) replication: send "row X changed from A to B". It is flexible and works across versions. It is also the basis of Change Data Capture (CDC), which streams database changes to other systems (Lessons 19 and 23, Part 6).

Comparison

Single-leaderMulti-leaderLeaderless
Who accepts writesOne leaderSeveral leadersAny replica (quorum)
Write conflictsNone (one writer)Yes, must resolveYes, must resolve (versions, LWW)
Write availability during failuresDepends on failoverHighHigh
ComplexityLowestHighMedium–high
ExamplesPostgreSQL, MySQL, MongoDBMulti-region setups, offline/collab appsCassandra, ScyllaDB, Riak, the original Amazon Dynamo

Trade-offs

  • Replicas scale reads, not writes. In single-leader setups, all writes still go to one leader. To scale writes, you shard, which means you split the data across machines (Lesson 25).
  • Async replication gives fast writes. The costs are a possible loss of the latest writes on failover, and stale reads (reads that return old data).
  • Sync replication loses no data. But writes are slower, and they depend on the health of the replica.
  • Automatic failover means less downtime. But there is a risk of false failovers and split brain. Test it regularly.
  • Multi-leader and leaderless give high availability and local writes. But you get conflicts, and the system is harder to understand.
  • Replication is not a backup. A DELETE by mistake is copied to every replica within milliseconds. You still need backups (Part 7).

In the Real World

GitHub's October 2018 incident. A short network problem (about 43 seconds) cut the link between GitHub's East Coast data centre and the rest of its network. Its automated failover system promoted database primaries on the West Coast. When the link came back, some writes existed only in the East and others only in the West. The databases could not simply be merged. GitHub ran in a degraded state for about 24 hours while engineers carefully fixed the data. It is one of the best public examples of how hard failover and split brain are.

Read replicas in everyday apps. Managed services like Amazon RDS, Google Cloud SQL and Azure Database let you add read replicas with a few clicks. Many teams then meet the "I updated my profile but I see old data" bug. They fix it by reading the user's own data from the primary.

Cassandra at Netflix and Apple. Leaderless Cassandra clusters that span several data centres hold huge amounts of data, such as viewing history and service data. Tunable consistency lets teams choose, for each query, between speed and freshness.

Amazon's shopping cart. The Dynamo paper describes how the cart stays writable during failures by using leaderless replication, and how conflicting versions are merged. The paper also admits a side effect: deleted items could sometimes reappear after a merge. Amazon accepted this as a fair price for never refusing "add to cart".

Interview Questions

Q1What does replication give you, and what doesn't it?

It gives you availability (another copy survives a crash), read scaling, lower latency for distant users, and a safe place to run backups and reports. It does not scale writes in a single-leader setup. It is also not a backup, because a bad DELETE is copied everywhere within milliseconds.

Q2A user updates their profile and sees the old version on refresh. Why, and how do you fix it?

The cause is asynchronous replication lag. The write went to the leader, but the read hit a replica that had not caught up. To fix it, serve a user's own data from the leader for a while after they write. Or send reads only to replicas that have reached the user's last write position. Or show the change in the UI at once (optimistic UI).

Q3What is split brain, and how do you prevent it?

Two nodes both believe that they are the leader, and they accept conflicting writes. This usually happens after a network partition (a break in the network) triggers a failover while the old leader is still alive. To prevent it, use leader election based on consensus that needs a majority (Raft, etcd). Also use fencing, which stops the old leader from writing.

Q4Explain W + R > N.

With N replicas, a write waits for W acknowledgements and a read asks R replicas. If W + R > N, every group of read replicas overlaps every group of write replicas. So at least one replica in each read has the latest value. Changing W and R trades write latency, read latency and availability against each other.

Q5How do multi-leader systems resolve conflicts?

You can use last-write-wins by timestamp. It is simple, but it silently drops writes and it trusts clocks. You can merge the values. You can use CRDTs, which merge automatically. Or you can keep both versions for the app or the user to resolve. The best way is to avoid conflicts by sending each record's writes to one home region.

Q6Why should a cluster have an odd number of voting nodes?

A leader needs a majority. Three nodes survive one failure and five survive two. A fourth node adds cost but still survives only one failure (a majority of 4 is 3). Even counts also make ties possible.

Key Takeaways

  • Replication keeps copies of data on many machines, for availability, read scaling, lower latency and safe reporting.
  • Single-leader is the default: writes go to the leader, and replicas replay its log. Async is fast but risks lost writes and stale reads. Sync is safe but slower.
  • Replication lag causes real bugs. Handle read-your-writes (read your own data from the leader) and monotonic reads (stick users to one replica).
  • Failover is hard: watch for lost writes and split brain. Use fencing and consensus (Raft, etcd) to pick leaders safely.
  • Multi-leader and leaderless (quorum) designs improve write availability but need conflict resolution. Remember that replication is not a backup.

Further Reading

  • Designing Data-Intensive Applications by Martin Kleppmann (chapter 5, "Replication")
  • The PostgreSQL documentation chapter "High Availability, Load Balancing, and Replication"
  • The Raft paper "In Search of an Understandable Consensus Algorithm" by Ongaro and Ousterhout, and the interactive Raft visualisation on its official website
  • The Amazon Dynamo paper (SOSP 2007), for quorums, hinted handoff and read repair
  • GitHub's post-incident analysis of the October 21, 2018 outage
  • The System Design Primer on GitHub (section "Replication")

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series