Replication: Leader-Follower & Multi-Leader
You'll learn to
- -Compare synchronous and asynchronous replication
Sharding splits data up for scale; replication copies data for safety and read throughput, and real systems do both at once (each shard is itself replicated). This chapter closes the loop on "how do multiple copies of the same data stay in sync."
Leader-follower replication: all writes go to the leader, which streams changes to followers that serve reads.
Copy your data to multiple servers to achieve fault tolerance, read scaling, and geographic distribution.
A newspaper company (Primary) prints the daily paper. It sends copies to hundreds of newsstands (Replicas) across the city. Readers can buy from any newsstand nearby - no need to travel to the print shop. If the print shop burns down, all the newsstands still have yesterday's paper.
Single-Leader (Master-Replica) Replication: One designated node accepts all writes (the leader/primary). It continuously ships write events to one or more follower nodes. Followers are read-only - they replicate and serve reads. This is PostgreSQL streaming replication, MySQL binlog replication, and Redis Sentinel.
This pattern dramatically improves read throughput: you can have 5 replicas and spread your read queries across all 6 nodes (1 primary + 5 replicas). Write throughput is unchanged because all writes still go through one node.
Synchronous vs Asynchronous replication: Synchronous means the primary waits for at least one replica to acknowledge every write before confirming success to the client. Zero data loss, but higher write latency. Asynchronous means the primary confirms immediately and replicates in the background - lower latency, but potential data loss if the primary crashes before the replica catches up.
Multi-Leader Replication: Multiple nodes accept writes. Used for multi-datacenter setups (one leader per data center). Each leader asynchronously replicates to the others. The trade-off: write conflicts can occur when the same row is modified simultaneously in two data centers.
Leaderless Replication (Dynamo-style): Used by Cassandra, Riak, DynamoDB. Any node can accept writes. The client writes to W nodes and reads from R nodes. If W + R > N (total nodes), you are guaranteed to read at least one up-to-date value. This enables extremely high availability - no single leader to fail.
- -Primary goal: fault tolerance - if the primary fails, promote a replica.
- -Secondary goal: read scaling - distribute reads across replicas.
- -Replication lag: replicas may be seconds behind the primary (problematic for "read your own writes").
- -Automatic failover (sentinel, orchestrator) needed in production.
- -RPO (Recovery Point Objective) = max data loss tolerable. Sync replication = RPO of 0.
How a New Leader Gets Chosen: Consensus
The diagram above begs an obvious question: when the leader crashes, who decides which follower becomes the new leader, and how do you guarantee the whole cluster agrees on the same one? Get this wrong and you get "split-brain": two nodes each believing they're the leader, both accepting writes, silently diverging. This is exactly the problem distributed consensus algorithms solve, and it's worth being able to name one, even at a high level.
Paxos (the original, from Leslie Lamport) and Raft (designed later specifically to be easier to reason about) both work on the same core idea: a node can only become leader if it wins votes from a strict majority of the cluster. Because any two majorities of the same set must overlap by at least one node, it's mathematically impossible for two different nodes to both win a majority in the same term, which is exactly what rules out split-brain. Google's Chubby lock service and Spanner are both built on Paxos-family consensus; etcd, Consul, and CockroachDB are built on Raft.
You will essentially never be asked to implement Paxos or Raft from scratch in an interview; they're notoriously subtle. The signal an interviewer is actually looking for is knowing that leader election in a real distributed system isn't "whichever server notices first," but a specific, majority-vote-based protocol, and being able to name that this is usually delegated to a battle-tested coordination service (like etcd or ZooKeeper) rather than hand-rolled.
Your database's leader crashes. Two remaining replicas both think the leader is gone and both try to promote themselves. What actually prevents both from succeeding?
"Whichever one notices the crash first becomes the new leader."
"A consensus protocol is exactly what prevents that. Each candidate has to win votes from a strict majority of the cluster to become leader: with an odd-sized cluster, two different candidates mathematically cannot both win a majority in the same election round, since their majorities would have to overlap. This is what Paxos and Raft guarantee, which is why production systems delegate leader election to one of them (often via etcd or ZooKeeper) instead of inventing an ad-hoc scheme."
Why do plain auto-increment IDs fail once data is sharded across multiple database instances?
Level 7 (Consistent Hashing & Load Balancing) and Level 9 (Unique ID Generator) put this whole module into practice.