Replication: Leader-Follower & Multi-Leader

Sharding splits data up for scale. Replication does the opposite: it keeps copies of the same data on several machines, for two reasons. Reads can be spread across the copies, and if one machine dies, another has the data. Real systems do both at once: each shard is itself replicated. The interesting question is how several copies stay in step with each other, and what you give up when they briefly do not.

A restaurant chain keeps its master recipe book at head office. Whenever the head chef changes a recipe, a copy of the change is sent to every branch kitchen, and cooks at the branches read from their own copy instead of phoning head office. If head office burns down, the branches still have the recipes. The questions are how quickly a change reaches the branches, and what happens if a branch cook reads the book just before the update arrives.

• -The master book at head office is the leader (also called the primary): the one place that accepts changes.
• -The branch copies are the followers (replicas): they receive the stream of changes and serve reads.
• -Sending the changes out is replication.
• -A branch that has not yet received the latest change is lagging, which is replication lag.

In the most common design, all writes go to the leader, which records each change and streams it to its followers. Reads can go to any follower. Because most applications read far more than they write, adding followers multiplies read capacity without touching the write path, and a follower can be promoted if the leader fails.

The leader has to decide when to tell the client the write succeeded. In synchronous replication it waits until the followers confirm they have it. In asynchronous replication it answers straight away and sends the change along afterwards. The trade is speed against safety:

• -Synchronous: the data is on more than one machine before the client is told. But the write is as slow as the slowest follower, and a follower that is down can block all writes.
• -Asynchronous: writes are fast, and a slow follower does not matter. But if the leader dies before a change has been sent, that change is lost. At 500 writes a second and a two-second delay, that could be around 1,000 writes.
• -Semi-synchronous: wait for one follower, send to the rest asynchronously. At least two copies exist when the client hears back, without waiting for every follower. Many systems choose this middle path.

With asynchronous followers, a read can arrive before the change does. The classic symptom: a user updates their profile photo, the write goes to the leader, the page refreshes and its read is served by a follower that has not yet received the change, so the old photo appears. The user thinks the save failed. This is the read-your-writes problem. The usual fix is to send a user's reads to the leader for a short time after they write, or to remember the position of their last write and only read from a follower that has caught up to it.

• -Multi-leader: several nodes accept writes, often one per region, so writes are fast everywhere. The price is conflicts: two people edit the same record in different regions at the same moment, and the system needs a rule to resolve it (last write wins, a merge, or special data types designed to merge cleanly).
• -Leaderless: any node can accept a write. A write goes to W of N copies and a read asks R of them, and if W plus R is more than N, the reads and writes always overlap. With N = 3, W = 2 and R = 2, any two copies you read must include at least one that has the latest write. This is the idea behind Dynamo-style stores such as Cassandra.

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.