Replication Strategies & the CAP Theorem

A single database running on a single machine is easy to reason about and impossible to trust. The disk fails, the process crashes, the data center loses power, or a datacenter's worth of users on the other side of the planet wait 200ms for every query to cross the ocean and back. Replication — keeping copies of the same data on multiple machines — is how distributed systems solve all four of those problems at once, but it introduces a problem of its own: what happens when the copies disagree?

Why replicate at all

There are four independent reasons to replicate, and it's worth separating them because they push toward different designs. Availability comes first — if a node holding the only copy of a row dies, that row is gone until the node comes back; with replicas, another node just takes over. Read scalability follows naturally — a hundred followers can each serve a slice of read traffic that a single leader never could. Geographic locality matters once your users aren't all next to your database — a replica in Singapore answers a Singapore user's query without a round trip to Virginia. And durability is the quiet one: a write acknowledged by three machines in three different failure domains survives a lot more than a write sitting on one disk.

Single-leader replication

The simplest design elects one node as the leader (or primary) and routes every write through it. The leader applies the write locally and streams it to its followers as a replication log, which they replay in order. Reads can go to the leader or, if you're willing to tolerate slightly stale data, to any follower.

The replication itself can be synchronous — the leader waits for at least one follower to confirm before acknowledging the write, guaranteeing the data survives a leader crash — or asynchronous, where the leader acknowledges immediately and ships the log in the background. Most production systems use a hybrid: one synchronous follower for safety, the rest asynchronous for throughput. The appeal of single-leader replication is that it sidesteps write conflicts entirely — there's only ever one place a write can happen, so there's nothing to reconcile. The cost is that the leader is both a throughput ceiling and a single point of failure: lose it, and someone (a human, or a consensus protocol like Raft) has to promote a follower before writes can resume.

Multi-leader replication

Multi-leader replication removes that bottleneck by letting more than one node accept writes — typically one leader per data center, so a write in Europe doesn't have to cross the Atlantic before it's acknowledged. Each leader replicates its writes to every other leader, and each applies the others' writes locally.

The problem this creates is unavoidable: two leaders can accept conflicting writes to the same record within milliseconds of each other, and by the time either notices, both have already told their client the write succeeded. Something has to decide which write wins, and there's no single right answer. Last-write-wins (usually by timestamp) is simple but silently discards data. Version vectors detect that a conflict happened and surface both versions instead of picking one blindly. CRDTs (conflict-free replicated data types) sidestep the question by choosing data structures — counters, sets, sequences — whose merge operation is mathematically guaranteed to converge no matter what order updates arrive in. And sometimes the honest answer is an application-level merge, the way a shared document merges two people's edits to the same paragraph.

Leaderless replication

Dynamo-style systems (Cassandra, Riak, and DynamoDB's own ancestor) drop the concept of a leader entirely. A client writes directly to several replicas at once, and reads from several replicas at once, resolving any disagreement — usually by version number or timestamp — at read time instead of write time.

Consistency here is a knob, not a guarantee, tuned through quorums. With N replicas holding each piece of data, a write is considered successful once W of them acknowledge it, and a read queries R of them and returns the newest version seen. Choosing W + R > N guarantees the read set and the write set overlap by at least one node, so a read is mathematically guaranteed to see the latest write. It doesn't eliminate conflicts — two writes can still race each other to different quorums — but it lets you dial consistency up or down per operation instead of fixing it for the whole system.

The CAP theorem, precisely stated

CAP is one of the most cited and most misquoted ideas in distributed systems. The precise claim: when a network partition occurs — some nodes can't talk to others — a replicated system must choose between Consistency (every read sees the most recent write, or an error) and Availability (every request gets a non-error response). It cannot have both during the partition, because the only way to guarantee a consistent answer from a node that can't reach the rest of the cluster is to refuse to answer at all.

The common misreading treats CAP as a permanent architectural choice — "we're a CP system" or "we're an AP system" — as if you pick two of three forever. That's not what the theorem says. Outside of a partition, a well-built system can be both consistent and available; CAP only forces the trade-off during the partition, and only for the operations actually affected by it. Partitions are also rare and temporary compared to the system's total uptime, so CAP describes a narrow, specific failure mode — not the system's everyday character.

PACELC: the more useful extension

CAP's biggest gap is that it only talks about behavior during a partition, and partitions are the exception, not the rule. PACELC fills that gap: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Even on a perfectly healthy network, a system that wants strong consistency has to wait for enough replicas to confirm a write or agree on a read, and that waiting costs latency. A system that wants low latency has to answer from whatever replica is closest, before it can be sure that replica has the newest data. This is the trade-off engineers actually live with day to day — long after the last network partition healed.