Chapter 12 of 33

Database Replication

What happens to your app if the one machine running your database dies at 2 a.m.? Without a copy of the data somewhere else, the answer is: everything stops, and some data may be gone forever. And even on a good day, a single database server can only answer so many reads per second.

Replication solves both problems by keeping copies of the same data on multiple machines. In SQL vs NoSQL Databases we saw that databases differ in how they scale; this chapter looks at the most common scaling and reliability technique of all, which nearly every production database uses.

Database replication means keeping a copy of the same data on multiple machines (replicas) connected by a network, and keeping those copies up to date as the data changes.


Why Replicate?

  • High availability: if one machine fails, another copy can take over (see Latency, Throughput & Availability).

  • Read scalability: spread read queries over many replicas.

  • Lower latency: keep a replica geographically close to users (a Mumbai replica for Indian users, a Frankfurt replica for European users).

  • Durability and backups: data survives disk or machine loss; a replica can be used to take backups without loading the main server.

If data never changed, replication would be trivial: copy it once. All the difficulty comes from handling changes. There are three main approaches: single-leader, multi-leader and leaderless.


Single-Leader (Primary–Replica) Replication

This is the most common setup, used by default in MySQL, PostgreSQL, MongoDB replica sets, SQL Server and many others.

  • One node is the leader (also called primary, or source in MySQL). All writes go to it.

  • The leader records every change in a replication log and sends it to the other nodes, called followers (replicas, secondaries, standbys).

  • Followers apply the changes in the same order and can serve reads.

               writes + reads
   App  ─────────────────────────►  +---------+
                                    | Leader  |
                                    +---------+
                                   /     |     \   replication log
                                  ▼      ▼      ▼  (changes in order)
                         +--------+ +--------+ +--------+
   App  ── reads only ─► |Replica1| |Replica2| |Replica3|
                         +--------+ +--------+ +--------+

Because only one node accepts writes, there are no write conflicts: the leader decides the order of all changes. This simplicity is why single-leader replication is the default choice.


Synchronous vs Asynchronous Replication

The key question: when does the leader tell the client "your write succeeded"?

Synchronous                          Asynchronous

Client   Leader   Replica            Client   Leader   Replica
  |--write->|        |                  |--write->|        |
  |         |--log-->|                  |<--ACK---|        |   ← fast reply
  |         |<--ok---|                  |         |--log-->|   ← sent later
  |<--ACK---|        |                  |         |        |
SynchronousAsynchronousSemi-synchronous
Leader replies afterReplica(s) confirm they have the changeWriting locally onlyAt least one replica confirms receipt
Write latencyHigher (includes a network round trip)LowestMedium
Data loss if leader diesNone for acknowledged writesRecent writes can be lostNone, as long as the confirming replica survives
If a replica is slow or downWrites stallNo effect on writesFalls back or waits, depending on settings

In practice, making every replica synchronous is rare, because one slow replica would block all writes. Common real-world settings:

  • MySQL: asynchronous by default; a semi-synchronous plugin and Group Replication are available.

  • PostgreSQL: streaming replication is asynchronous by default; listing standbys in synchronous_standby_names makes commits wait for them, and synchronous_commit (remote_write, on, remote_apply...) controls how far each standby must get before the commit returns.

  • MongoDB: the client chooses a write concern. Since MongoDB 5.0 the default is w: "majority" (for most deployments), meaning a write is acknowledged once a majority of voting replica-set members have it.

Seeing It in Code

Here is a tiny simulation: a leader with a replication log, two replicas, and both modes. It is a model of the idea, not a real database.

from itertools import combinations

class Node:
    def __init__(self, name):
        self.name, self.data, self.applied = name, {}, 0

class Primary(Node):
    def __init__(self, replicas):
        super().__init__("primary")
        self.log, self.replicas = [], replicas

    def write(self, key, value, sync=False):
        self.log.append((key, value))          # append to replication log
        self.data[key] = value
        self.applied = len(self.log)
        if sync:                               # wait for every replica
            for r in self.replicas:
                self.ship(r)
        return "ACK"

    def ship(self, replica):                   # send the missing log entries
        for key, value in self.log[replica.applied:]:
            replica.data[key] = value
        replica.applied = len(self.log)

r1, r2 = Node("replica-1"), Node("replica-2")
p = Primary([r1, r2])

print("--- asynchronous ---")
p.write("profile:42:name", "Ravi Kumar")
print("primary  :", p.data.get("profile:42:name"))
print("replica-1:", r1.data.get("profile:42:name"), "(lag =", len(p.log) - r1.applied, "entries)")
p.ship(r1); p.ship(r2)
print("after shipping, replica-1:", r1.data.get("profile:42:name"))

print("--- synchronous ---")
p.write("profile:42:name", "Ravi K.", sync=True)
print("replica-2:", r2.data.get("profile:42:name"), "(lag =", len(p.log) - r2.applied, "entries)")

print("--- quorum overlap check (N = 3) ---")
N = 3
nodes = range(N)
for W in range(1, N + 1):
    for R in range(1, N + 1):
        always = all(set(w) & set(r)
                     for w in combinations(nodes, W)
                     for r in combinations(nodes, R))
        print(f"W={W} R={R} R+W={R+W} overlap_always={always}")

Output:

--- asynchronous ---
primary  : Ravi Kumar
replica-1: None (lag = 1 entries)
after shipping, replica-1: Ravi Kumar
--- synchronous ---
replica-2: Ravi K. (lag = 0 entries)
--- quorum overlap check (N = 3) ---
W=1 R=1 R+W=2 overlap_always=False
W=1 R=2 R+W=3 overlap_always=False
W=1 R=3 R+W=4 overlap_always=True
W=2 R=1 R+W=3 overlap_always=False
W=2 R=2 R+W=4 overlap_always=True
W=2 R=3 R+W=5 overlap_always=True
W=3 R=1 R+W=4 overlap_always=True
W=3 R=2 R+W=5 overlap_always=True
W=3 R=3 R+W=6 overlap_always=True

In asynchronous mode, the client got "ACK" while replica-1 still had nothing: a reader hitting replica-1 at that moment would see no name at all. That gap is replication lag. The quorum part of the output is used later in this chapter.


Problems Caused by Replication Lag

With asynchronous replicas, lag is usually milliseconds, but under heavy load or network trouble it can grow to seconds or minutes. Example: a leader receives 2,000 writes/s, but a replica can apply only 1,800/s. After one minute the replica is (2,000 − 1,800) × 60 = 12,000 changes behind, and the gap keeps growing until load drops.

Lag causes three classic anomalies (we study the formal guarantees in Consistency Models):

1. Reading Your Own Writes

Ravi updates his name  ──► Leader      (write OK)
Ravi refreshes profile ──► Replica 2   (not updated yet)
Ravi sees his OLD name and thinks the update failed!

Fixes: read data the user can edit (their own profile) from the leader; or for a short time after a write (say 10 seconds), route that user's reads to the leader; or remember the log position of the user's last write and only read from a replica that has reached it.

2. Monotonic Reads

A user refreshes twice. The first read goes to a fresh replica and shows a new comment; the second goes to a lagging replica and the comment disappears. Time seems to move backwards. Fix: route each user consistently to the same replica (for example, choose the replica by hashing the user id).

3. Consistent Prefix Reads

If related writes are applied in a different order on different partitions, a reader might see an answer before its question. Fix: write causally related data to the same partition, or track causal dependencies.


Handling Failures

Follower Failure: Catch-Up Recovery

Each follower remembers the last log position it applied. After a restart it asks the leader for everything after that position and catches up. Simple and safe.

Leader Failure: Failover

Much harder. Failover means promoting a follower to become the new leader:

  1. Detect that the leader is dead, usually by missed heartbeats over a timeout (say 10–30 seconds).

  2. Choose a new leader, ideally the replica with the most up-to-date data, through an election (MongoDB replica sets and Raft-based systems do this automatically) or a cluster manager (Patroni for PostgreSQL; MySQL InnoDB Cluster, built on Group Replication, or Orchestrator for MySQL).

  3. Reconfigure clients to send writes to the new leader, and make sure the old leader becomes a follower if it comes back.

What can go wrong:

  • Lost writes: with asynchronous replication, writes the old leader acknowledged but never shipped are gone. If the old leader returns, those writes usually have to be discarded.

  • Split brain: two nodes both believe they are the leader and both accept writes, so data diverges. Systems prevent this with majority voting (a leader needs votes from more than half the nodes) and fencing (the old leader is blocked from writing, using an epoch/term number or by cutting off its access).

  • Wrong timeout: too short, and a brief network hiccup triggers needless failovers; too long, and the outage lasts longer.

This is why replica sets usually have an odd number of voting members (3 or 5): a clear majority is always possible, and a 3-node set survives 1 failure while a 5-node set survives 2.


How Changes Are Shipped: Replication Log Formats

MethodWhat is sentProsCons
Statement-basedThe SQL statement itself (UPDATE ... SET ...)CompactNon-deterministic functions like NOW() or RAND() can give different results on replicas
Physical / WAL shippingLow-level storage changes (which bytes changed in which disk block)Exact copy; used by PostgreSQL streaming replicationReplicas must run a compatible version of the same engine
Logical (row-based)Row-level changes: "row with id 42 now has name = 'Ravi K.'"Deterministic, version-independent, can feed other systems (change data capture)Larger for statements that change many rows

MySQL's binary log uses row-based format by default (since 5.7.7). PostgreSQL offers both physical streaming replication and logical replication (publications and subscriptions). Logical change streams are also what tools like Debezium read to push database changes into Kafka, which connects to Message Queues & Pub/Sub.


Multi-Leader Replication

Here more than one node accepts writes, and each leader forwards its changes to the others.

   Users in India                Users in Europe
        |                              |
   +-----------+   async both ways  +-----------+
   | Leader    | <----------------> | Leader    |
   | (Mumbai)  |                    | (Frankfurt)|
   +-----------+                    +-----------+
     |      |                          |      |
  replica replica                   replica replica

When it is useful:

  • Multiple data centres: each region writes locally with low latency and keeps working if the inter-region link fails.

  • Offline clients: a notes or calendar app on your phone acts as a "leader" while offline and syncs later.

  • Collaborative editing: several users editing the same document at once.

The big problem: write conflicts. If a user in Mumbai sets a product's price to ₹500 while an admin in Frankfurt sets it to ₹550 at the same moment, both leaders accept the change, and then each receives the other's. Which wins?

  • Last write wins (LWW): attach a timestamp and keep the latest. Simple, but it silently throws away one write, and clocks on different machines are never perfectly in sync.

  • Merge the values using data types designed to merge automatically, called CRDTs (Conflict-free Replicated Data Types), for example counters or sets where concurrent additions can always be combined.

  • Keep both versions and let the application or the user resolve the conflict (as Git does with merge conflicts).

  • Avoid conflicts: route all writes for a given record to the same "home" leader.


Leaderless Replication

Popularised by Amazon's Dynamo paper (2007) and used by Apache Cassandra, ScyllaDB and Riak. There is no leader: the client (or a coordinator node acting for it) sends each write to several replicas in parallel, and reads from several replicas in parallel.

Quorums

With N replicas of each item, a write must be confirmed by W replicas and a read must hear from R replicas.

If R + W > N, the set of replicas you read from always overlaps the set that acknowledged the latest write, so at least one response contains the latest value.

The quorum section of the program above checked every possible choice of replicas for N = 3, and it confirms the rule: overlap is guaranteed exactly when R + W ≥ 4, that is, R + W > 3. The common setting is N = 3, W = 2, R = 2: it tolerates one unavailable replica for both reads and writes.

N = 3, W = 2, R = 2

Write v2:   [A: v2 ✓]  [B: v2 ✓]  [C: v1 (missed it)]
Read:       ask A and C  →  A says v2, C says v1  →  return newer: v2

Note the quorum rule guarantees overlap, but edge cases (concurrent writes, sloppy quorums, failed writes that partly succeeded) mean leaderless systems are still usually described as eventually consistent rather than strongly consistent.

Keeping Replicas in Sync

  • Read repair: when a read notices a stale replica (C above), it writes the newer value back to it.

  • Anti-entropy: a background process compares replicas (Cassandra uses Merkle trees, hash trees that let two nodes find differing ranges quickly) and copies missing data.

  • Hinted handoff: if a replica is down, another node temporarily stores the write with a "hint" and delivers it when the replica returns.

In Cassandra, R and W are chosen per query through consistency levels such as ONE, QUORUM, LOCAL_QUORUM and ALL.


Comparing the Three Approaches

Single-leaderMulti-leaderLeaderless
Who accepts writesOne leaderSeveral leadersAny replica (W of N)
Write conflictsNoneYes, must be resolvedYes, must be resolved
Write availability if a node failsPaused until failoverOther leaders continueContinues while W replicas respond
ConsistencyStrong on leader; replicas may lagEventualTunable with R and W; usually eventual
ExamplesMySQL, PostgreSQL, MongoDB replica setsMulti-region setups, DynamoDB global tables (multi-Region eventual consistency mode), CouchDB syncCassandra, ScyllaDB, Riak

One recent development worth knowing: DynamoDB global tables can now be created in multi-Region strong consistency (MRSC) mode (generally available since mid-2025), where a write acknowledged in one Region is immediately visible to strongly consistent reads in the other Regions, at the cost of higher write latency. The default mode, MREC, replicates asynchronously and resolves conflicts with last-writer-wins.


Estimating How Many Replicas You Need

Suppose your app does 60,000 reads/s at peak and one replica can comfortably handle 8,000 reads/s. Running servers at 100% is risky, so target 70% utilisation:

capacity per replica at 70%  = 8,000 × 0.7 = 5,600 reads/s
replicas needed              = 60,000 / 5,600 = 10.7  →  11 replicas

Without the headroom you would compute 60,000 / 8,000 = 7.5 → 8, and any single failure or traffic spike would overload the rest. Remember: replicas scale reads, not writes. Every replica still has to apply every write, so if writes are the bottleneck you need Database Sharding & Partitioning instead.


Common Mistakes

  • "Adding replicas increases write throughput." It does not; each replica repeats all writes.

  • Treating replication as a backup. An accidental DELETE is replicated to every copy within milliseconds. You still need point-in-time backups.

  • Ignoring replication lag and reading a user's just-written data from a replica.

  • Using an even number of voting nodes (2 or 4). A 4-node set tolerates only 1 failure, the same as 3, while costing more and risking ties.

  • Assuming automatic failover is free. With asynchronous replication it can lose acknowledged writes, and without fencing it can cause split brain.

  • Saying R + W ≥ N is enough. It must be strictly greater.


Interview Questions

1. What is the difference between synchronous and asynchronous replication?

Synchronous: the leader acknowledges a write only after replicas confirm it, so acknowledged data is not lost on failover, but writes are slower and can stall. Asynchronous: the leader acknowledges immediately and ships changes later, so writes are fast but replicas lag and recent writes can be lost if the leader fails.

2. A user updates their profile but sees the old value on refresh. Why, and how do you fix it?

The read went to an asynchronous replica that had not yet applied the write (replication lag). Fix with read-your-writes: read the user's own data from the leader, route the user to the leader for a short time after writing, or read only from replicas that have reached the user's last write position.

3. What is split brain and how is it prevented?

Two nodes both act as leader and accept conflicting writes. It is prevented by requiring a majority vote to become leader (so at most one side of a partition can elect one) and by fencing the old leader using term/epoch numbers or by revoking its access.

4. With N = 5, which (R, W) pairs guarantee reading the latest write?

Any pair with R + W > 5, for example W = 3, R = 3 (majority both ways), W = 5, R = 1 (fast reads, but any failure blocks writes), or W = 1, R = 5 (fast writes, any failure blocks reads).

5. When would you choose multi-leader replication?

When writes must be accepted with low latency in several regions or while disconnected (multi-datacenter apps, offline-capable mobile apps, collaborative editing), and you can handle write conflicts through LWW, CRDTs, custom merge logic or by routing each record to a home leader.

6. Why are replica sets usually 3 or 5 nodes?

An odd number gives a clear majority. A majority of 3 is 2 (tolerates 1 failure); a majority of 5 is 3 (tolerates 2 failures). Adding a 4th node raises the majority to 3, so it still tolerates only 1 failure.


Summary

  • Replication keeps copies of data on several machines for availability, read scaling, lower latency and durability.

  • Single-leader is the default: simple, no write conflicts, but failover is tricky.

  • Synchronous replication avoids losing acknowledged writes; asynchronous is faster but causes replication lag and possible data loss.

  • Lag causes read-your-writes, monotonic-read and consistent-prefix anomalies; route reads carefully.

  • Multi-leader and leaderless designs accept writes in many places but must resolve conflicts; quorums need R + W > N.

  • Replicas scale reads, not writes, and are not a substitute for backups.

Replication answers "what if a machine dies?" and "how do we serve more reads?". For "how do we handle more writes and more data than one machine can hold?", we need sharding, the topic of the next chapter.