Database Replication Explained: Leader, Follower and Lag

Replication keeps copies of the same data on several servers. It gives you three things: more read capacity, survival when a server dies, and data closer to users.

Primary and replicas#

The most common setup has one primary (or leader) that takes all writes, and several replicas (or followers) that copy it:

Writes --> Primary --copies changes--> Replica 1 <-- Reads
                  \------------------> Replica 2 <-- Reads

Since most apps read far more than they write, replicas add a lot of capacity:

read_share = 0.9
reads_per_node = 10_000
for replicas in (0, 2, 5):
    if replicas:
        max_total = reads_per_node * replicas / read_share
    else:
        max_total = reads_per_node
    print(f"{replicas} replicas: about {max_total:>8,.0f} requests/s before reads saturate")

0 replicas: about   10,000 requests/s before reads saturate
2 replicas: about   22,222 requests/s before reads saturate
5 replicas: about   55,556 requests/s before reads saturate

This does not help writes, as each replica must apply every write too. For more write capacity, see sharding.

Synchronous or asynchronous#

A common compromise is semi-synchronous: wait for one replica, and let the others follow asynchronously.

Replication lag#

With asynchronous replication, replicas fall a little behind. This lag is usually milliseconds, but it can grow under load, and it causes odd effects:

class Database:
    def __init__(self):
        self.primary = {}
        self.replica = {}
        self.pending = []

    def write(self, key, value):
        self.primary[key] = value
        self.pending.append((key, value))

    def replicate(self):
        for key, value in self.pending:
            self.replica[key] = value
        self.pending.clear()


db = Database()
db.write("name", "Asha Rao")
print("Read from replica:", db.replica.get("name"))
db.replicate()
print("After replication:", db.replica.get("name"))

Read from replica: None
After replication: Asha Rao

A user changes their name, reloads, and sees the old one. Common fixes are:

• Read your own writes: after a user writes, read their data from the primary for a short time.
• Sticky reads: send a user to the same replica, so that time never appears to go backwards.
• Track versions: only read from a replica that has caught up.

Failover#

If the primary dies, a replica must take over:

1. Detect the failure, usually through missed heartbeats.
2. Choose the replica that is most up to date.
3. Point writes at it.
4. Bring the old primary back as a replica.

The danger is split brain: a network problem makes two nodes both think they are the primary. Systems avoid this by requiring a majority vote, using algorithms such as Raft, and tools such as Patroni, etcd or managed cloud databases. An odd number of voters prevents ties:

for nodes in (2, 3, 4, 5):
    majority = nodes // 2 + 1
    print(f"{nodes} nodes: majority {majority}, survives {nodes - majority} failure(s)")

2 nodes: majority 2, survives 0 failure(s)
3 nodes: majority 2, survives 1 failure(s)
4 nodes: majority 3, survives 1 failure(s)
5 nodes: majority 3, survives 2 failure(s)

Note that 4 nodes survive no more failures than 3 do.

Multi-leader and leaderless#

Cassandra and DynamoDB-style systems are leaderless.

Replication is not a backup#

If someone runs DELETE by mistake, that is copied to the replicas too. You still need backups.

Common mistakes#

Practice#

import math

reads = 40_000 * 0.95
needed = math.ceil(reads / 8_000)
print(f"{needed} for the load, {needed + 1} with a spare")

5 for the load, 6 with a spare

Key takeaway#

Next: Sharding and Consistent Hashing.