Database Replication: Leader-Follower, Multi-Leader and Leaderless

Replication keeps copies of the same data on several machines. It serves three goals: availability (if one copy dies, others serve), read scaling (spread reads over copies) and latency (keep a copy near users). The hard part is keeping copies in sync while data changes, and the main designs differ in who accepts writes.

Each machine holding a copy is a replica (or node). If data never changed, replication would be trivial: copy it once and you're done. The difficulty is mutable data: every change must reach every replica while you keep the consistency, availability and performance you need. Terminology: leader = primary, follower = secondary = replica.

Which replication does my database use?

• Most relational databases default to single-leader replication. One source of truth makes conflict resolution far simpler. The weak point is the leader failing: a new leader must be elected, and if a network partition splits the remaining nodes, two leaders could be elected (split brain). Most systems therefore use consensus algorithms for leader election.
• Dynamo-style databases (Amazon's original Dynamo, Cassandra, Riak) use leaderless replication.
• Multi-region cloud databases differ in how they take writes. DynamoDB global tables are genuinely multi-leader: every region accepts writes. Google Spanner multi-region keeps a single Paxos leader per data split, replicated to synchronous voting replicas, and Azure SQL active geo-replication has one primary with asynchronous readable secondaries; neither accepts writes in more than one region at once, so neither is multi-leader. See geo-replication.
• Managed services handle much of it for you: Amazon RDS includes automated backups and replication, and Cloud SQL replicates managed MySQL and PostgreSQL across zones. It's still worth knowing what happens underneath.

Leader-follower (primary-replica)

One node, the leader, accepts all writes and streams changes (its write-ahead log or a change log) to followers, which serve reads. This is the default for PostgreSQL, MySQL, MongoDB replica sets, Redis and Kafka partitions.

Replication logs

The leader tells followers what changed through a replication log. There are three kinds:

• Statement-based logs record the exact SQL that changed data, e.g. INSERT INTO students (name, age) VALUES ('John', 15);, UPDATE students SET age = 16 WHERE name = 'John';. Simple, but non-deterministic statements (NOW(), RAND(), auto-increments) can produce different results on each replica.
• Write-ahead logs (physical) record changes at the byte level, in a form only the storage engine understands; other applications can't easily read them. PostgreSQL ships its WAL to replicas. MySQL's equivalent physical log is the redo log, used for crash recovery, but MySQL replication doesn't ship it; it uses the binlog. Physical logs are fast and compact but tie leader and followers to the same engine version. See write-ahead logging.
• Logical (row-based) logs describe each change in terms of rows: all new column values for an insert, enough to identify the row (usually the primary key) for a delete, and the row's identity plus new values for an update. Examples: MySQL's binlog (row format) and PostgreSQL's logical decoding. They're independent of the storage engine, so other applications can parse them, which is why change data capture uses them.

# A PostgreSQL WAL record (pg_waldump): byte-level, engine-specific
rmgr: Heap  len (rec/tot): 24/24, tx: 5828, lsn: 0/016F4130, prev 0/016F410C,
desc: INSERT+INIT off 3, xmax 0, xmin 5828, cmin 0, cmax 0, blkref #0: rel 1663/16384/1259 blk 0

# The same kind of change in a logical log: readable by any consumer
{"op": "insert", "table": "students", "after": {"id": 7, "name": "John", "age": 15}}

Synchronous vs asynchronous

With asynchronous replication the leader sends the log without waiting for acknowledgment: fast, but if the leader dies before any follower has the change, that write is lost. With synchronous replication the leader waits for followers to confirm before treating the write as done: followers match the leader, but one slow or crashed follower blocks every new write, so fully synchronous replication is rarely practical. Most setups are configured async for performance.

A common compromise is semi-synchronous: wait for one follower, replicate to the rest asynchronously.

MySQL is asynchronous by default and has no fully synchronous mode out of the box, but its semi-synchronous plugin waits for at least one replica to receive and log each transaction before the commit completes, so at least one replica always matches the primary. It costs some write latency; choose it by how much data loss you can tolerate. Enable it in my.cnf and restart each server:

# Primary: my.cnf
[mysqld]
plugin-load-add = semisync_source.so
rpl_semi_sync_source_enabled = 1
rpl_semi_sync_source_timeout = 1000      # ms; falls back to async if no replica acks

# Each replica: my.cnf
[mysqld]
plugin-load-add = semisync_replica.so
rpl_semi_sync_replica_enabled = 1

# (MySQL before 8.0.26 names these semisync_master.so / rpl_semi_sync_master_* and
#  semisync_slave.so / rpl_semi_sync_slave_*)

Replication lag and its anomalies

Async followers can be milliseconds or, under load, seconds behind. Reading from them causes the anomalies described in consistency models: a user not seeing their own update, or data appearing and disappearing. Fixes include reading your own recent writes from the leader and routing a session to one follower.

Failover

When the leader dies, a follower is promoted. The hard parts: detecting real failure versus a slow network, choosing the most up-to-date follower, making clients write to the new leader, and preventing the old leader from accepting writes if it comes back (split brain). Robust systems use a consensus service or leader election with fencing for this.

Nodes go down for hardware failures or just routine updates. The two cases differ:

• A follower goes down: it keeps its position in its local log, so when it returns it asks the leader for every change since that point, applies them, and carries on once caught up.
• The leader goes down: a follower must be promoted and every follower must switch to it (failover). Manual failover is simpler because a human decides. Automatic failover has three steps: confirm the leader is dead (say, unreachable for 30 seconds), elect a new leader (a consensus problem; see leader election), and reconfigure clients and followers to use it.
• What goes wrong: the old leader comes back still believing it's the leader and must learn it isn't; or two nodes both believe they lead (split brain), both accept writes, and followers receive conflicting updates. Consensus algorithms and fencing tokens exist to prevent this.

Try it: leader-follower replication with Redis

Start a primary on the default port and a replica that follows it (or run both with docker run redis:7):

redis-server                                           # primary on 6379
redis-server --port 6380 --replicaof 127.0.0.1 6379    # replica following it

import redis

primary = redis.Redis(host="localhost", port=6379, decode_responses=True)
replica = redis.Redis(host="localhost", port=6380, decode_responses=True)

primary.set("key", "value")                        # write only to the primary
print("Primary node value:", primary.get("key"))   # value
print("Replica node value:", replica.get("key"))   # value: it was replicated

try:
    replica.set("key", "other")                    # replicas are read-only
except redis.exceptions.ReadOnlyError as err:
    print(err)        # You can't write against a read only replica.

The replica's log shows it syncing on start (PRIMARY <-> REPLICA sync started … Successful partial resynchronization with primary). Stop the primary briefly, as a network partition would, and the replica logs PRIMARY timeout: no data nor PING received, Connection with primary lost, then keeps reconnecting and resynchronizes from where it left off as soon as the primary is reachable. Plain replication doesn't promote the replica; that's what Redis Sentinel or Redis Cluster add (see cache high availability).

Multi-leader replication

Several nodes accept writes, typically one leader per region, and replicate to each other. Users write locally with low latency, and each region keeps working if another is cut off.

The cost is write conflicts: two regions can change the same record concurrently. Resolution strategies include last-write-wins (simple, silently loses data), merging (for example with CRDTs), or routing all writes for a given record to one "home" region to avoid conflicts entirely.

Leaderless replication and quorums

In Dynamo-style systems (Cassandra, Riak, DynamoDB internally), clients or a coordinator write to N replicas and wait for W acknowledgements; reads query R replicas and take the newest version. If R + W > N, every read set overlaps every write set, so a read sees the latest acknowledged write.

Stale replicas are repaired by read repair (fix replicas found stale during a read), hinted handoff (another node holds writes for a down replica and delivers them later) and anti-entropy (background comparison using Merkle trees).

Comparison