Replication: Leader-Follower, Multi-Leader, Leaderless

Why

Three reasons to replicate. Durability: if one machine dies, a copy still has the data. Read scaling: most apps read a hundred times more than they write, so spread the reads across copies. And latency: put a copy near users in each region. The hard part is the same in all three: keeping the copies identical while writes keep arriving.

Leader-follower

The common arrangement: leader-follower, also called primary-replica or master-slave in older docs. One node is the leader. Every write goes to it. The leader streams its changes to the followers, which apply them in the same order. Postgres, MySQL, MongoDB and Redis all work this way by default.

What's streamed is the write-ahead log from episode eighteen. Every committed change is already a record in that log, in order. The leader ships those records, and each follower replays them, so it ends up byte for byte in the same state. Durability and replication are literally the same log.

leader write-ahead log (ep 18)

LSN 1041  UPDATE accounts id=7 …
LSN 1042  INSERT posts …
LSN 1043  COMMIT

followers replay the same records
in the same order → same state

Read scaling

Now your service sends writes to the leader and reads to any follower. Need more read capacity? Add a follower. That's how a single Postgres handles a read-heavy site: one writer, five readers, a load balancer in front of the readers.

Sync vs async

Here's the first trade-off. A synchronous follower must acknowledge each write before the leader confirms the commit. No data loss if the leader dies, but every write is as slow as the slowest follower. An asynchronous follower gets the log whenever it arrives. Writes are fast, but the follower lags, and if the leader dies now, the last few writes may be gone. The usual setup: one synchronous follower for safety, the rest asynchronous.

Lag

Asynchronous followers create the bug every engineer hits once. You post a comment, the write goes to the leader. The page reloads and reads from a follower that is two hundred milliseconds behind. Your comment isn't there. You think it failed and post again. Replication lag is usually milliseconds, but under load it can be seconds or minutes.

The fix is called read-your-own-writes. After a user writes, send that user's reads to the leader for the next few seconds, or always when reading their own data. Or have the client remember the time of its last write, and only use a follower that has caught up to it. Mention this in an interview and you've shown you've run a real system.

t=0    write comment → leader
t=5ms  read comments → follower
       follower is 200 ms behind
       your comment is missing

lag: ms normally,
     seconds or minutes under load

Failover

What if the leader dies? Failover. The followers notice missed heartbeats, the most up-to-date follower is promoted, and clients are pointed at it. Managed databases do this for you in thirty seconds or so. The catch: if replication was asynchronous, the new leader may be missing the last writes, and they're gone.

Split brain

The nightmare version: the old leader wasn't dead, just cut off by the network. It comes back and keeps accepting writes while the new leader does too. Split brain. Two sets of data that disagree. The fix is fencing, which forcibly shuts the old leader out, and requiring a majority of nodes to agree before anyone is promoted. That's consensus, episode twenty-six.

Multi-leader

Second arrangement: multi-leader. One leader per region, each accepting local writes and syncing with the others. Writes are fast everywhere, and a whole region can go down. The cost: two people edit the same row in two regions at once, and now you have a conflict to resolve. Last write wins, merge the fields, or ask the user. It's how Google Docs style collaboration and multi-region setups work, and you only choose it when you need it.

Leaderless

Third: leaderless, from Amazon's Dynamo paper, used by Cassandra and DynamoDB. There is no leader. The client writes to all three replicas and counts it a success when two reply. Reads ask two replicas and take the newest version. Because two plus two is more than three, every read overlaps at least one replica that has the latest write. That's a quorum. No failover, no single writer, always available, and the price is that you handle versions and conflicts yourself.

N = 3 replicas
W = 2  write succeeds when 2 ack
R = 2  read asks 2, takes newest

W + R > N  → every read overlaps
            a successful write

no failover needed: any node
can be down and it still works

Choosing

Choosing: leader-follower by default. It's simple, it's what your database already does, and it gives you durability and read scaling. Multi-leader when you need writes in several regions or offline clients. Leaderless when you need always-on writes at huge volume and can live with eventual consistency, which is the next episode but one.

leader-follower   default; most SQL,
                  Mongo, Redis
multi-leader      multi-region writes,
                  offline clients
leaderless        always-on, huge write
                  volume, can tolerate
                  eventual consistency

In the interview

Say it like this. Postgres with one leader and two followers: writes to the leader, reads to the followers. One follower is synchronous so a committed write is never lost. After a user writes, their own reads go to the leader for a few seconds, so they see it. Failover is managed, about thirty seconds. Four sentences: topology, durability, lag, failure.