Replication and Consensus, In Depth

A replica is simply a full copy of your data kept on a separate machine. Running one database on one server is the simplest design, but it fails the moment that server does. Replication means holding the same data on several machines so the system survives loss, serves more traffic, and answers users faster.

There are four honest reasons to replicate, and it helps to name which one you are buying:

The tension running through the whole day: the moment you have more than one copy, the copies can disagree. Every technique below is a different answer to "how do we keep them close enough to agree, and what do we do when they don't?"

The most common setup has one leader (also called primary) and one or more followers (also called replicas or secondaries). All writes go to the leader. The leader records each change and streams it to the followers, which apply the same changes in the same order. Reads can be served by the leader or any follower.

This is the default in most relational databases (PostgreSQL, MySQL) and many others. It is easy to reason about because one machine decides the order of all writes, so there is never a write conflict: the leader is the single source of truth for "what happened first."

The key decision in a single-leader system is: when a client writes, does the leader wait for followers to confirm before telling the client "done"?

• Synchronous replication: the leader waits for at least one follower to acknowledge the change before reporting success. The follower is guaranteed to have the data.
• Asynchronous replication: the leader reports success immediately and forwards the change to followers in the background. The follower will have the data soon, but not yet.

The trade-off is durability versus latency:

In practice many systems use a middle path: replicate synchronously to one follower and asynchronously to the rest. That one synchronous follower guarantees a second copy exists, while the others catch up without slowing writes. This is sometimes called semi-synchronous replication.

Replication lag is the delay between a write landing on the leader and that same write appearing on a follower. With asynchronous replication the lag is usually milliseconds, but under load or a network hiccup it can grow to seconds or minutes. During that window a follower serves stale data — an old value that the leader has already changed.

Lag is invisible until a user reads from a lagging follower and sees something wrong. Three classic anomalies follow directly from lag.

Read-after-write (also called read-your-writes). A user updates their profile, the write hits the leader, then the page reloads and reads from a follower that has not received the change yet. The user sees their old profile and thinks the save failed. The guarantee we want is: a user always sees their own writes, even if not everyone else's yet.

The common fixes: read anything the user themselves might have just modified from the leader, or route that user's reads to the leader for a short window after a write, or track the write's position and only read from a follower that has caught up to it.

Monotonic reads. A user reads a value, then reads again and sees an older value — time appears to move backward. This happens when the first read hit an up-to-date follower and the second read hit a more-lagged follower. Monotonic reads is the guarantee that once you have seen a value, you never later see an older one. The usual fix is to pin each user to a single follower (for example by hashing the user id) so their reads always come from the same copy.

Consistent-prefix reads. A user sees an answer before the question it responds to, because two related writes replicated out of order across partitions. The fix is to make sure causally related writes are ordered together.

The unifying idea: asynchronous replication trades a small, temporary staleness for lower latency, and these anomalies are the concrete shapes that staleness takes. You either accept them where they are harmless or spend effort to hide them where they matter.

If the leader dies, someone has to promote a follower to be the new leader. Doing this automatically is called failover. It sounds simple and is famously full of traps.

The hard parts:

• How long to wait before declaring the leader dead. Too short and a brief pause triggers a needless failover; too long and the system is down longer than it needed to be. There is no perfect timeout.
• Lost writes. With asynchronous replication the old leader may have acknowledged writes that never reached the new leader. Those writes are simply gone. If those ids are reused elsewhere (say, in a cache or a downstream system), you get corruption.
• Split-brain. The old leader may not actually be dead — just briefly unreachable. If it comes back still believing it is leader while a new one has been promoted, you now have two leaders. That is the danger we handle further down.

Because these traps are real, many teams disable fully-automatic failover and require a human to confirm promotion, trading a little downtime for safety. The consensus systems described later exist largely to make leader election safe and automatic despite exactly these traps.

In a multi-leader setup there is more than one leader, and a client can write to any of them. Each leader accepts writes locally and then replicates them to every other leader. This is used when a single leader is too far away or too much of a bottleneck.

Where it fits:

• Multi-region deployments. Each region has its own leader so local writes are fast. Cross-region replication happens in the background.
• Offline-capable clients. A phone or laptop that keeps working without a network is effectively its own leader; it syncs its changes when it reconnects. Calendar and note apps work this way.

The price you pay is conflicts. Because two leaders accept writes independently, two users can change the same record at the same time in different places. When those writes meet, the system must decide which one wins — or how to combine them. A single-leader system never has this problem because one machine orders every write.

When two leaders (or two offline clients) modify the same value concurrently, replication brings the two versions together and something must reconcile them. There are three common strategies, and the difference between them is who loses data.

Last-write-wins is the simplest: every write carries a clock reading, and on conflict the higher clock value survives. The trap is that "last" depends on clocks agreeing, and machine clocks drift. Two writes that a user considers simultaneous get an arbitrary winner, and the loser is thrown away with no trace. LWW is fine for data where losing an occasional write is acceptable (a cache, a presence flag) and dangerous for anything you must not lose.

Version vectors (a generalization of vector clocks) let the system distinguish "this write is genuinely newer and supersedes the old one" from "these two writes happened concurrently and neither knew about the other." That means it can auto-resolve the easy cases and only flag the genuinely conflicting ones. It does not by itself decide the winner of a true conflict — it just detects it honestly so you can merge deliberately.

Application-level merge keeps both versions and lets your own logic combine them. A shopping cart can union the two carts; a text document can merge non-overlapping edits. This is the only strategy that loses nothing, at the cost of writing the merge rules yourself. Data types designed to always merge cleanly (CRDTs) are a formal version of this idea.

The rule of thumb: match the conflict strategy to the cost of losing a write. Cheap-to-lose data can use LWW; valuable data wants detection plus a real merge.

Leaderless replication (popularized by Amazon's Dynamo, and used by Cassandra and Riak) drops the leader entirely. The client — or a coordinator acting for it — sends every write to several replicas at once, and reads from several replicas at once. There is no single machine that must be up for writes to proceed.

The core notation:

• N — the number of replicas that hold each piece of data.
• W — the number of replicas that must confirm a write for it to count as successful.
• R — the number of replicas the client reads from and compares.

The magic rule is R + W > N. If the set of replicas you write to and the set you read from must together exceed N, then those two sets are guaranteed to overlap by at least one replica — so every read touches at least one replica that has the latest write. A group of replicas that is large enough to make this guarantee hold is called a quorum.

With N=3, W=2, R=2, you have 2 + 2 > 3, so any write set and any read set share at least one replica (replica 2 above). That shared replica carries the newest value, so the reader can find it. Tuning the numbers shifts the trade-off: a larger W makes writes safer but slower and less available; a larger R does the same for reads. Setting W=N gives the strongest writes; setting W=1 gives the fastest, least durable ones.

Two mechanisms keep the lagging replicas honest:

• Read repair. When a read touches several replicas and notices one has a stale value, the client writes the fresh value back to the stale replica on the spot. Frequently-read data heals itself.
• Hinted handoff. If a replica that should receive a write is temporarily down, another node accepts the write on its behalf and holds a "hint." When the intended replica returns, the holder hands the write off to it. This keeps writes flowing during short outages without abandoning the down replica's copy.

Quorums give you tunable consistency without a leader, which is why leaderless stores are popular for always-writable, high-availability workloads. The catch is that quorum reads are not as strict as a true leader-ordered system — edge cases around concurrent writes still need the conflict resolution from the previous section.

Split-brain is the failure where two nodes both believe they are the leader at the same time. It happens when a leader is briefly unreachable, a new one is promoted, and then the old one comes back still convinced it is in charge. Now two machines accept writes and issue conflicting orders — the worst outcome, because state gets corrupted rather than merely stale.

You cannot always prevent an old leader from thinking it is leader (it may have been network-isolated and missed the news). What you can do is stop it from acting on that belief. The tool is a fencing token: a number that strictly increases every time a new leader is elected. Every request the leader sends to shared storage carries its token, and the storage rejects any token older than the highest one it has already seen.

Even if the stale old leader wakes up and tries to write, its token 33 is now below the storage's remembered 34, so the write is fenced off and refused. The old leader can shout all it wants; the shared resource simply stops listening. Fencing turns "two leaders exist" from a corruption event into a harmless rejected request.

Every problem so far — electing exactly one leader, agreeing on the newest configuration, deciding whether a write committed — reduces to the same question: how do a group of machines agree on one value when any of them can crash or be cut off, and messages can be lost or delayed? That agreement problem is consensus.

Consensus gives you a single decision that a majority of nodes commit to, such that once decided it never silently changes and everyone eventually learns the same outcome. It is what makes automatic leader election safe (only one winner), what prevents split-brain at the source, and what lets a cluster agree on membership and configuration despite failures.

The load-bearing idea in every practical consensus algorithm is the majority (more than half of N nodes). Any two majorities of the same group must share at least one node — the same overlap trick as quorums. That shared node cannot hold two contradictory decisions, so two conflicting majorities can never both form. This is why consensus clusters are sized at odd numbers like 3 or 5: a majority of 3 is 2, a majority of 5 is 3, and the cluster keeps working as long as a majority is alive.

Raft is a consensus algorithm designed to be understandable. It runs a cluster of an odd number of nodes and always keeps exactly one leader that all writes flow through — turning the messy agreement problem into ordinary single-leader replication, plus a safe way to pick the leader.

A term is Raft's notion of time: a numbered period during which there is at most one leader. Every new election starts a new, higher-numbered term. Terms are how nodes tell a current leader from a stale one — a message stamped with an old term is ignored, much like a fencing token.

Leader election. Each node is a follower, a candidate, or the leader. Followers expect regular heartbeats from the leader. If a follower hears nothing for a randomized timeout, it assumes the leader is gone, increments the term, becomes a candidate, votes for itself, and asks every other node for a vote. Each node grants only one vote per term. A candidate that collects votes from a majority becomes the leader. The randomized timeouts make it unlikely two candidates tie; if they do, the term ends with no winner and a fresh election starts.

Log replication. The leader appends each client command to its own log (an ordered list of entries) and sends the entry to every follower. A follower that receives it appends it and acknowledges. Here is the crucial rule: an entry is committed — treated as permanent and safe to apply — only once a majority of nodes have stored it. Until a majority holds it, the entry is tentative and could still be overwritten.

Because commit requires a majority, and any two majorities overlap, a newly elected leader is guaranteed to already have every committed entry — so committed data is never lost across an election. That single property is what makes Raft trustworthy: once the client is told "committed," no failure and no future leader can erase it.

The majority rule is worth making mechanical, because it explains how big to make a cluster and how many failures it tolerates.

The pattern: a cluster of N survives the loss of ⌊(N−1)/2⌋ nodes and needs ⌊N/2⌋+1 to make progress. Even numbers waste a node — a 4-node cluster still needs 3 for a majority and still tolerates only 1 failure, exactly like a 3-node cluster but with more machines to keep in sync. That is why consensus clusters are almost always 3 or 5 nodes. Three is enough to survive one failure (a routine event); five survives two and is used where the cluster itself must be highly reliable.

Running a full consensus protocol is expensive: every decision needs a majority round trip, so throughput is limited and latency is bounded by your slowest majority. This shapes what you should store in one.

Systems like etcd, ZooKeeper, and Consul are purpose-built consensus stores. They are excellent for coordination and small, critical metadata:

• Which node is the current leader (leader election for other services).
• Cluster membership and service discovery — who is alive and where.
• Configuration that must be consistent everywhere at once (feature flags, routing rules).
• Distributed locks and the fencing tokens that make them safe.

They are the wrong home for bulk application data. Storing user rows, images, or event streams in etcd would drown it — every write pays the majority-agreement tax, and the data volume swamps a system tuned for kilobytes of critical state, not terabytes of records.

The division of labor: a consensus store holds the small facts everyone must agree on, and your regular replicated databases (single-leader, multi-leader, or leaderless as the workload demands) hold the large data that can tolerate the looser guarantees those models give.

• Replication buys read scale, availability, durability, and lower latency — but the instant you have two copies, they can disagree, and every technique here manages that disagreement.
• Single-leader is the simplest model: one machine orders all writes, so there are no conflicts, but a slow or dead leader hurts. Async replication is fast but loses recent writes on failover; sync is safe but slow.
• Replication lag is temporary staleness. It shows up as read-your-writes and monotonic-read anomalies, which you hide only where they matter.
• Multi-leader and leaderless models trade the leader's simplicity for availability and locality, and pay for it with write conflicts you must resolve — LWW loses data, version vectors detect it, application merge preserves it.
• Quorums (R + W > N) give tunable consistency by forcing read and write sets to overlap.
• Split-brain corrupts state; fencing tokens neutralize a stale leader by rejecting its outdated writes.
• Consensus is agreement on one value despite failures, and it always rests on a majority, because two majorities must overlap. Raft makes this understandable: one leader per term, and an entry commits once a majority holds it.
• Consensus stores like etcd, ZooKeeper, and Consul are for small critical metadata and coordination, not bulk data — they pay a majority round trip per decision.