Database Replication

By the end of this lesson you will be able to explain how databases keep copies of data on several machines, predict the strange bugs that replication lag causes, fix them with read-your-writes routing, and reason about quorums in leaderless databases.

Why keep copies?

Replication means keeping a copy of the same data on more than one machine. Each copy is a replica. There are three reasons to do it:

• Availability: if one machine dies, another copy can take over.
• Read scaling: many replicas can answer read queries in parallel.
• Locality: a copy near users in another region answers them faster.

Think of a school's attendance register. The class teacher writes in the main register. Every evening, the office copies it into the principal's register and the exam cell's register. Anyone can read any copy, but only one person writes. If the main register is lost, a copy can become the new main one. And if you check the exam cell's copy at 2 pm, it will not show today's absences yet. That delay is the heart of this lesson.

Leader-follower replication

The most common setup is leader-follower (also called primary-replica). One node, the leader, accepts all writes. It records every change in a log and sends the log to followers, which apply the same changes in the same order. Reads can go to the leader or to any follower.

             writes                 change log
app  ----------------->  Leader  ===============+==============+
  \                     (primary)               |              |
   \  reads                                     v              v
    +----------------------------------->  Follower 1     Follower 2
                                          (read replica)  (read replica)

MySQL and PostgreSQL both support this pattern, and the SQL course shows the configuration side.

Synchronous or asynchronous?

When the leader receives a write, when does it tell the client "done"?

Most production setups are asynchronous or semi-synchronous. That means followers are usually a little behind. This gap is replication lag, normally milliseconds, but it can grow to seconds or minutes under heavy load.

Replication lag in action

Lag causes bugs that confuse users. The classic one: Ananya changes her delivery address, the page reloads, and the old address appears. Her write went to the leader, but her read went to a follower that had not caught up.

Step 1: run the simulation. Writes reach the follower after a lag of 2 seconds.

class ReplicatedDB:
    def __init__(self, lag):
        self.lag = lag
        self.leader = {}
        self.follower = {}
        self.in_transit = []                      # (arrives_at, key, value)
        self.last_write = {}                      # user -> time of their last write

    def write(self, user, key, value, now):
        self.leader[key] = value
        self.in_transit.append((now + self.lag, key, value))
        self.last_write[user] = now

    def _apply(self, now):
        for change in [c for c in self.in_transit if c[0] <= now]:
            self.follower[change[1]] = change[2]
            self.in_transit.remove(change)

    def read(self, user, key, now, read_your_writes=False):
        self._apply(now)
        recent = now - self.last_write.get(user, -999) < 10    # wrote in last 10 s?
        if read_your_writes and recent:
            return self.leader.get(key), "leader"
        return self.follower.get(key), "follower"

db = ReplicatedDB(lag=2)
db.write("ananya", "addr:ananya", "Old flat, Aliganj", now=0)
db.write("ananya", "addr:ananya", "New flat, Gomti Nagar", now=100)

for policy in [False, True]:
    print("read-your-writes" if policy else "always read follower")
    for t in [100.5, 101.5, 103]:
        value, source = db.read("ananya", "addr:ananya", t, read_your_writes=policy)
        print(f"  t={t:5}: {value:22} (from {source})")

always read follower
  t=100.5: Old flat, Aliganj      (from follower)
  t=101.5: Old flat, Aliganj      (from follower)
  t=  103: New flat, Gomti Nagar  (from follower)
read-your-writes
  t=100.5: New flat, Gomti Nagar  (from leader)
  t=101.5: New flat, Gomti Nagar  (from leader)
  t=  103: New flat, Gomti Nagar  (from leader)

Step 2: compare the two policies. With read-your-writes consistency, a user who wrote recently reads from the leader, so they always see their own change. Everyone else still reads from followers, so the leader is not overloaded. Other ways to get the same effect: send the write's log position with the next read and only use a follower that has reached it, or keep the fresh value in the user's session briefly.

A related anomaly is going "back in time": a user refreshes twice, hits a fresh follower then a lagging one, and sees a comment appear and vanish. Monotonic reads, achieved by sending each user to the same follower, prevents this.

Failover: when the leader dies

If the leader fails, a follower must be promoted to leader. Steps, whether done by a tool or a person:

1. Detect the failure, usually by missed heartbeats over some seconds. Too short a timeout causes needless failovers; too long means longer downtime.
2. Choose the new leader, normally the follower with the most up-to-date log.
3. Redirect writes to the new leader (update a config service, DNS or a proxy).
4. Fence the old leader so that, if it comes back, it cannot accept writes.

Step 4 prevents split brain: two nodes both believe they are the leader and accept conflicting writes. Fencing can mean cutting the old leader's network access or using a number called an epoch or term, which increases on each election, so writes from an old leader are rejected.

With asynchronous replication, any writes the old leader had not yet sent are lost on failover. For payments this is unacceptable, which is why such systems use synchronous or semi-synchronous replication or consensus-based databases.

Leaderless replication and quorums

Some databases, such as Apache Cassandra and others inspired by Amazon's Dynamo paper, have no leader. A client writes to several replicas and reads from several replicas. Three numbers describe the setup:

• N: how many replicas hold each key.
• W: how many must confirm a write.
• R: how many must answer a read.

If R + W > N, every read set overlaps every write set in at least one replica, so a read always reaches at least one node with the latest write. This is called a quorum.

from itertools import combinations

def always_overlaps(n, w, r):
    nodes = range(n)
    return all(set(ws) & set(rs)
               for ws in combinations(nodes, w)
               for rs in combinations(nodes, r))

for n, w, r in [(3, 2, 2), (3, 1, 1), (3, 3, 1), (5, 3, 3), (5, 2, 3)]:
    rule = "R+W>N" if r + w > n else "R+W<=N"
    print(f"N={n} W={w} R={r} ({rule}): every read sees the latest write? {always_overlaps(n, w, r)}")

N=3 W=2 R=2 (R+W>N): every read sees the latest write? True
N=3 W=1 R=1 (R+W<=N): every read sees the latest write? False
N=3 W=3 R=1 (R+W>N): every read sees the latest write? True
N=5 W=3 R=3 (R+W>N): every read sees the latest write? True
N=5 W=2 R=3 (R+W<=N): every read sees the latest write? False

The common choice N=3, W=2, R=2 survives one replica being down for both reads and writes. W=1, R=1 is fastest but may read stale data. You tune these numbers per use case. Even with a quorum, edge cases such as concurrent writes need conflict rules, which the next lessons touch on in Consistency Models, CAP & PACELC.

Multi-leader replication

Multi-leader setups allow writes in several places, for example one leader per region. Writes are fast locally, but two regions can change the same record at the same time, creating a conflict. Resolving conflicts (last write wins, merging, asking the user) is hard, so avoid multi-leader unless you truly need local writes in several regions.

Common mistakes

• Sending all reads to replicas without thinking about lag, so users miss their own updates.
• Assuming replicas are backups. A bad DELETE is replicated instantly. You still need real backups.
• Failover without fencing, leading to split brain and conflicting writes.
• Asynchronous replication for money, losing confirmed payments on failover.
• Ignoring lag monitoring. Alert when replica lag grows beyond a few seconds.

Key points

• Replication keeps copies for availability, read scaling and locality.
• Leader-follower is the common pattern: one writer, many readers.
• Asynchronous replication is fast but lags and can lose recent writes on failover.
• Read-your-writes and monotonic reads hide lag from users.
• Failover needs detection, promotion, redirection and fencing to avoid split brain.
• In leaderless systems, R + W > N makes read and write sets overlap.

from itertools import combinations

def always_overlaps(n, w, r):
    nodes = range(n)
    return all(set(ws) & set(rs) for ws in combinations(nodes, w) for rs in combinations(nodes, r))

def min_read_quorum(n, w):
    for r in range(1, n + 1):
        if always_overlaps(n, w, r):
            return r

for n, w in [(3, 1), (3, 2), (5, 2), (5, 4)]:
    print(f"N={n} W={w}: smallest R = {min_read_quorum(n, w)}")

N=3 W=1: smallest R = 3
N=3 W=2: smallest R = 2
N=5 W=2: smallest R = 4
N=5 W=4: smallest R = 2