Leader-based vs Leaderless Replication Visualization

The idea: who may take a write?

A replicated database keeps a copy of every key on several nodes, here three: A, B and C. The big design choice is who may accept a write. In leader-based (single-leader, primary/replica) replication only one node, the leader, takes writes; it puts them in order in its log and streams the log to the followers. In leaderless replication (Amazon Dynamo, Cassandra, Riak, ScyllaDB) every replica takes writes: the client sends each write to all of them and calls it done when W of the N replicas have acknowledged it.

Left: the client sends PUT to leader A, A streams REPL to followers B and C, they ACK, A answers OK: 4 message delays. Right: the client sends PUT straight to replicas A, B and C and is done after 2 ACKs: 2 message delays — A leader puts every write in one order but adds a hop; a leaderless client talks to the replicas itself and waits for W of N answers.

The page sends the same operations to both clusters on one clock. Every message takes one tick. The scoreboard counts how long the last write and read took, the messages sent, the ticks in which no write could be accepted, and stale reads: reads that returned an older value than one the client was already told was written.

Leader-based replication

One order. The leader appends each write to its log (MySQL binlog, PostgreSQL WAL) and every follower applies the log in the same order, so all copies go through the same states. Conflicts between two writers cannot happen: the leader decides which came first.
Semi-synchronous. The page's leader answers OK after one follower has acknowledged (MySQL rpl_semi_sync_source_wait_for_replica_count = 1, PostgreSQL synchronous_standby_names = 'ANY 1 (…)'), so an acknowledged write is on two nodes. That costs four message delays: client → leader → follower → leader → client (Demo: normal write and read).
Reads from the leader are never stale, because the leader has every acknowledged write. Reads from followers scale better but can lag (see Database Replication).
A follower that misses a message simply fetches it later: it asks the leader for the log from the entry it lacks. A lost copy is resent; a follower that was down catches up when it is back (Demo: C down).

Leaderless replication

No hop, no single point. The client (or any node it talks to, the coordinator in Cassandra) sends the write to all N replicas and is done after W acknowledgments: two message delays. Each write carries a version (a timestamp); the highest version wins (last write wins).
Quorums. A read asks R replicas and keeps the highest version. If R + W > N every read set overlaps every write set, so a read sees the last successful write. With N = 3, W = 2, R = 1 a read can ask exactly the replica that missed it (Demo: lost message, stale read, read repair). The quorum arithmetic has its own page: Quorum Reads and Writes.
Replicas drift and are repaired. Nothing orders the copies, so a replica can miss a write and nobody notices until a read compares answers. Read repair sends the newest version to the replicas that answered with an older one. Hinted handoff: when a replica is down, a live node keeps a hint with the write and hands it over when the replica is back. Background anti-entropy (Merkle-tree comparison) catches the rest.

Failover pause vs quorum

When a follower or a leaderless replica dies, both clusters carry on. When the leader dies, the leader-based cluster cannot take a single write until a new leader exists. The followers first have to be sure it is dead (no heartbeat for a timeout: here 3 ticks, in real systems seconds), then elect the follower with the longest log, which needs a majority (2 of 3). The leaderless cluster has nothing to replace: with A down, B and C still make W = 2 (Demo: leader down vs one node down).

Two timelines, ticks 1 to 10. Leader-based: A crashes at tick 1, ticks 2 to 4 no heartbeat, ticks 5 and 6 election, B is leader, then a 4-tick write: 5 ticks with no writes. Leaderless: A crashes, the next write goes to B and C and is OK after 2 ticks: 0 ticks with no writes — Losing the leader costs detection plus election time with no writes at all; losing one of three leaderless replicas costs nothing while W = 2 nodes are up.

The timeout is a real trade-off: a short one fails over fast but may depose a leader that was only slow, and two nodes that both believe they lead (split brain) can accept conflicting writes. Raft and Paxos avoid that with terms and majorities; see Raft and Leader Election.

When two nodes are down

Demo: two nodes down crashes B and C, then writes. The semi-sync leader waits for a follower, times out and falls back to asynchronous replication (what MySQL does after rpl_semi_sync_source_timeout): it answers OK with only one copy. Then A dies too. When B and C come back they elect B, which never saw the write: the client was told OK, yet the read returns the old value. The leaderless cluster refused the same write (1 ACK < W = 2), so it never promised anything. Turning the fallback off makes the leader refuse writes too: it is a choice between availability and durability, not something either design gets for free.

Which one?

	Leader-based	Leaderless
write path	client → leader → followers: 4 delays with semi-sync, 2 with async	client → W replicas: 2 delays
order of writes	one total order (the leader's log)	none; last write wins, or version vectors and siblings
leader / node failure	writes stop for detection + election	nothing to replace while W nodes are up
stale reads	none from the leader; followers lag	possible when R + W ≤ N, or during sloppy quorums
repairing copies	followers fetch the log	read repair, hinted handoff, anti-entropy
good for	transactions, constraints, read-your-writes (MySQL, PostgreSQL, MongoDB, Kafka partitions)	high write availability across data centres, simple key-value data (Cassandra, DynamoDB-style stores, Riak)

See also Database Replication for synchronous vs asynchronous followers and replication lag, Quorum Reads and Writes for every W and R, Raft for a leader elected safely by majority, and Consistent Hashing for how a leaderless store picks the N replicas of a key.

What the page leaves out

Concurrent writes to the same key from two clients (the leader orders them; a leaderless store keeps the one with the higher timestamp and silently drops the other, or keeps both as siblings with version vectors), multi-leader replication, follower reads and replication lag, sloppy quorums with a node outside the preference list, anti-entropy with Merkle trees, clock skew under last-write-wins, fencing tokens against a deposed leader, and timeouts measured in real time instead of ticks.