10 — Replication and consistency

Replication keeps copies of the same data on several machines. It has three purposes: surviving failures, scaling reads, and placing data close to users. The whole difficulty is that the copies change, and a network sits between them.

Single-leader replication

The most common design has one leader. All writes go to it, and it streams changes to followers, which serve reads.

Writes --> [Leader] --> [Follower 1] <-- Reads
               \------> [Follower 2] <-- Reads

This is simple, and it avoids write conflicts, since one node decides the order.

Synchronous and asynchronous

Replication lag

With asynchronous replication, followers run behind, usually by milliseconds, but sometimes by minutes under load. Lag produces odd behaviour.

Failover

When a leader dies, a follower has to take over. This is harder than it sounds.

Detecting failure. A slow leader and a dead leader look the same from outside. Timeouts have to be chosen: too short causes needless failovers, and too long means a longer outage.

Choosing a new leader. It should be the most up-to-date follower, but with async replication, even that may lack the latest writes, and those writes are lost.

Split brain. If an old leader comes back believing it’s still in charge, two nodes accept writes, and data diverges. Systems prevent this with fencing, which stops the old leader acting, and with terms or epochs that identify the current leader (chapter 11).

Multi-leader replication

Several nodes accept writes, usually one per region. Writes are fast for local users, and each region can survive alone. The problem is conflicts, when two regions change the same record at once.

Leaderless replication

In leaderless systems such as Dynamo and Cassandra, a client writes to several replicas directly, and reads from several.

With $N$ replicas, a write to $W$ nodes and a read from $R$ nodes are guaranteed to overlap if:

$R + W > N$

Checking every combination for $N = 3$:

$R = 2, W = 2$ is the common choice: it survives one node failure, for both reads and writes. Lower values trade consistency for speed.

Quorums don’t give the strongest guarantee, though. Concurrent writes can still conflict, and sloppy quorums, which write to other healthy nodes during an outage, break the overlap. Read repair and background anti-entropy bring stale replicas back up to date.

The CAP theorem

A network partition is when machines are working, but can’t reach each other. The CAP theorem, as proved by Gilbert and Lynch, says that during a partition, a replicated store can’t be both:

• Consistent: every read sees the latest write, or fails.
• Available: every working node answers.

If two sides can’t talk, then either one side refuses requests, or both answer and may disagree.

CAP is often summarized as “pick two of three”, which is misleading. Partitions aren’t optional, so the real choice applies only when one occurs. CAP’s “consistency” also means something specific, linearizability, which isn’t the C in ACID.

PACELC

Partitions are rare, but replication has a cost all the time. Daniel Abadi’s PACELC adds that case: if there’s a Partition, choose Availability or Consistency, Else choose Latency or Consistency.

Many systems are configurable per request, so a label describes a setting more than a product.

Consistency models

“Consistent” covers several guarantees. From strong to weak:

Stronger models need more coordination, which costs latency and availability. A useful design habit is to ask, per kind of data, what actually goes wrong if it’s stale. A like count can lag. An account balance mustn’t. Most systems mix several levels.

Spanner shows how far strong consistency can go. It offers external consistency across datacenters, using Paxos and tightly bounded clock uncertainty, at the price of commit latency that includes that uncertainty.

Conflict resolution

When two replicas accept conflicting writes, the system has to resolve them.

Last write wins keeps the write with the latest timestamp. It’s simple, but it silently loses data, and it depends on clocks that can’t be fully trusted.

Version vectors track which writes each replica has seen. They can detect that two writes were truly concurrent, and hand the conflict to the application.

Application merge lets domain logic decide. A shopping cart can take the union of two versions, which is what the Dynamo paper describes. That’s why a deleted item can occasionally reappear.

CRDTs

Conflict-free replicated data types are data structures designed so that replicas can update independently and always converge. Their merge function is commutative, associative and idempotent, so the order and repetition of merges don’t matter (overview).

A simple example is a counter that keeps one number per replica. Each replica increments only its own entry, and merging takes the maximum of each entry:

Replica A: {A: 5, B: 0}
Replica B: {A: 2, B: 3}
Merged:    {A: 5, B: 3}   total = 8

CRDTs power collaborative editors and some distributed databases. They work well for counters and sets. Text is harder, and not every rule can be expressed: “balance can’t go below zero” needs coordination.

Multi-region designs

Running in several regions is mostly a replication problem. Light in fibre sets a floor on latency, so strong consistency across continents costs real time on each write.

The third is a good compromise: each user’s data lives in one region, so most writes never conflict.

The takeaway

Replication trades simplicity for durability, read scale and latency. Replication lag affects users in concrete ways, and failover has to deal with split brain. CAP matters only during a partition, and the everyday trade-off is latency against consistency. Different data can have different guarantees.