Replication
Replication means keeping the same data on multiple nodes. The reasons are straightforward:
- Availability — if one node dies, others serve reads/writes
- Latency — serve users from a geographically closer replica
- Read throughput — spread read load across replicas
The hard part is keeping replicas in sync when data changes. Every replication scheme makes trade-offs about what happens when the network partitions, a replica falls behind, or two nodes accept conflicting writes.
If the data never changed, replication would be a file copy. All of the difficulty comes from change: a write lands on one machine first, and for some window of time the copies disagree. Every design on this page is a different answer to two questions about that window. Who may accept a write? And how long does the writer wait before telling the client "done"?
The Two Decisions Every Scheme Makes
| Decision | Options | What it controls |
|---|---|---|
| Who accepts writes? | One leader · several leaders · any replica | Whether concurrent writes to the same key can conflict |
| When is a write acknowledged? | After the leader alone (async) · after some followers (semi-sync, quorum) · after all (sync) | How much acknowledged data can be lost, and how slow writes are |
Crossing the two gives the design space. Single-leader with async acknowledgement is the classic MySQL or PostgreSQL read-replica setup. Single-leader with majority acknowledgement is what Raft and Multi-Paxos do. Multi-leader with async cross-site replication is the multi-datacenter active-active setup. Leaderless with quorum acknowledgement is Dynamo-style storage.
quadrantChart
title Replication design space
x-axis Fewer writers --> More writers
y-axis Ack early --> Ack late
quadrant-1 Leaderless quorums
quadrant-2 Consensus logs
quadrant-3 Async read replicas
quadrant-4 Many writers acking early
Postgres async standby: [0.15, 0.2]
Raft and etcd: [0.2, 0.75]
Cassandra QUORUM: [0.85, 0.7]
Cassandra ONE: [0.85, 0.25]
Multi-leader MySQL: [0.6, 0.15]
Where This Page Fits
This page is the distributed-systems view: the models, the anomalies they produce, and the reasoning behind each fix. For production configuration (PostgreSQL streaming replication, replication slots, MySQL GTIDs, Patroni and lag monitoring), see the database-focused Replication deep dive. Closely related pages:
- Quorums and Leaderless Replication: the quorum maths and its edge cases
- Replicated State Machines: replication when every replica must apply the same sequence of commands
- Leases and Fencing: how to stop a deposed leader from doing damage
- Causality and Version Vectors: how multi-leader and leaderless systems detect concurrent writes
Single-Leader Replication
The most common approach. One node is designated the leader (also called primary or master). All writes go to the leader. Followers replicate from the leader.
How Replication Works
The leader writes changes to a replication log (WAL in PostgreSQL, binlog in MySQL). Followers consume this log and apply changes in order.
Synchronous replication:
- Leader waits for follower to confirm before acknowledging the write to the client
- Follower is guaranteed to be up-to-date
- Write latency = leader latency + round-trip to follower
- If the synchronous follower is slow or down, writes block
Asynchronous replication:
- Leader acknowledges the write immediately after writing locally
- Followers replicate in the background
- Low write latency
- Replication lag — followers may be seconds or minutes behind
- If the leader crashes before replication completes, writes are lost
Semi-synchronous (most practical):
- One follower is synchronous; the rest are async
- Guarantees at least two copies of every write
- PostgreSQL's
synchronous_standby_namesworks this way
The three modes look like this on the wire. The only thing that changes is where the client's acknowledgement sits relative to the follower's reply.
sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower 1
participant F2 as Follower 2
Note over C,F2: Asynchronous
C->>L: write x=5
L->>L: append to log, fsync
L-->>C: OK
L->>F1: log entry
L->>F2: log entry
Note over C,F2: Synchronous to all
C->>L: write x=6
L->>F1: log entry
L->>F2: log entry
F1-->>L: ack
F2-->>L: ack
L-->>C: OK
Note over C,F2: Semi-synchronous, one sync follower
C->>L: write x=7
L->>F1: log entry
L->>F2: log entry
F1-->>L: ack
L-->>C: OK
F2-->>L: ack, later
What "acknowledged" really means
"The follower acknowledged" hides a choice about how far the follower got. Received into memory? Written to its disk? Applied, so that a read on the follower sees it? Each step costs latency and buys a different guarantee. PostgreSQL exposes this directly through synchronous_commit:
synchronous_commit | Leader waits until the sync standby has... | Survives |
|---|---|---|
off | nothing, and the leader does not even wait for its own WAL flush | Nothing beyond the last flush. A leader crash can lose recent commits |
local | nothing (leader flushes locally) | Leader crash with disk intact |
remote_write | received the WAL and handed it to its OS | Leader loss, unless the standby's OS also crashes |
on (default) | flushed the WAL to durable storage | Leader loss plus standby crash |
remote_apply | replayed the WAL, so queries on the standby see the write | Same as on, plus read-your-writes on that standby |
MySQL's semi-synchronous plugin has a related knob, rpl_semi_sync_master_wait_point (renamed rpl_semi_sync_source_wait_point in newer releases). With AFTER_SYNC, the default since 5.7, the leader waits for a replica to receive the transaction before committing it in the storage engine, so no other client can see a transaction that only exists on the leader. With the older AFTER_COMMIT, other clients could read a commit that is then lost in a failover, which is a phantom read of data that later vanishes. MySQL semi-sync also falls back to async after rpl_semi_sync_master_timeout (10 seconds by default) when no replica answers, which silently weakens the guarantee during exactly the incidents you bought it for. Alert on that fallback.
Quorum acknowledgement
Waiting for one named follower makes that follower a single point of failure for writes. Waiting for any k of n followers avoids it. PostgreSQL supports this with synchronous_standby_names = 'ANY 1 (s1, s2, s3)'. Raft and Multi-Paxos generalise the idea: an entry is committed once a majority of the group (leader included) has it on disk. A five-node group commits after the two fastest followers respond, and the slowest two can be arbitrarily slow or dead. This is why consensus-based replication has better tail latency than "sync to one specific standby": the leader only waits for the median follower, not a particular one.
The durability window, quantified
With async replication, the data you can lose on leader failure is everything written during the replication lag:
At 2,000 writes per second and 300 ms of lag, an unclean failover throws away about 600 acknowledged writes. At 5 seconds of lag, during a burst or a long-running transaction on the replica, it is 10,000. Semi-sync and quorum commit shrink that window to zero for the failure cases they cover, at the price of one extra round trip on every write:
| Placement of the synchronous copy | Typical extra write latency |
|---|---|
| Same availability zone | well under 1 ms |
| Another zone in the same region | about 1–2 ms |
| Another region on the same continent | tens of ms |
| Another continent | 100 ms or more |
These are order-of-magnitude figures. Measure your own network, but the shape never changes: synchronous replication across a continent means every commit pays a transcontinental round trip.
Replication Log Formats
"Followers apply the leader's log" glosses over what the log contains. There are four common designs:
| Format | What is shipped | Example | Strengths | Weaknesses |
|---|---|---|---|---|
| Statement-based | The SQL text (UPDATE ... SET n = n + 1) | MySQL binlog_format=STATEMENT | Compact | Non-deterministic statements (NOW(), RAND(), UUID(), LIMIT without ORDER BY) diverge across replicas |
| Physical / WAL shipping | Byte-level page changes | PostgreSQL streaming replication | Exact copy, cheap to produce | Tied to the storage format, so leader and follower usually need the same major version |
| Logical (row-based) | "Row with key K now has these column values" | MySQL ROW binlog, PostgreSQL logical replication | Version-independent, consumable by other systems (change data capture) | Larger for bulk updates |
| Trigger-based | Application-defined change records | Older tools such as Slony, Bucardo | Flexible (filtering, transformation) | Slow, more moving parts |
The choice matters for distributed-systems reasoning because determinism is the foundation of replication. Two replicas that apply the same input in the same order must end in the same state. Statement-based replication breaks that whenever a statement depends on local time, randomness or physical row order, which is why MySQL moved its default to row-based logging in 5.7.7. The same principle shows up again in replicated state machines, where the commands in the log must be deterministic.
Adding a New Follower
You cannot copy the leader's data files while writes are flowing and expect a consistent result. The standard procedure:
- Take a consistent snapshot of the leader, tied to an exact log position (an LSN in PostgreSQL, a GTID set or binlog coordinate in MySQL).
- Copy the snapshot to the new node and restore it.
- Have the follower request every log entry after that position.
- When it has caught up to the head of the log, it is a live follower.
The snapshot-plus-position pairing is the important idea. Without the position, the follower cannot know which changes are already in its snapshot. Leaderless systems such as Cassandra do something analogous when bootstrapping a node: stream the token ranges it will own from existing replicas, then rely on anti-entropy and hints for writes that raced with the stream.
Replication Lag Problems
When followers are behind the leader, you get consistency anomalies:
Read-your-own-writes violation:
1. User writes a post
2. Read is routed to a lagging follower
3. User sees their post hasn't appeared yet
Fix: Route reads to the leader for a short window after a write from the same user.
Monotonic reads violation:
1. User reads comment from follower A (up to date)
2. User refreshes, routed to follower B (30s behind)
3. Comment appears to vanish
Fix: Route a user's reads to the same replica consistently (e.g., hash user ID to replica).
Causal consistency violation:
1. User A asks a question
2. User B answers
3. User C sees the answer but not the question (follower lag)
Fix: Track causality via vector clocks or only replicate causally ordered writes.
This third anomaly is usually called a consistent prefix violation: the reader sees a set of writes that is not a prefix of any order in which they could have happened. Within a single-leader log it cannot happen, because every follower applies the same total order and is always at some prefix of it. It shows up when data is partitioned and each partition has its own independently lagging log. The question lives on partition 1, the answer on partition 7, and partition 1's follower is further behind.
The three guarantees, stated precisely
These are the session guarantees, introduced by Terry and colleagues for the Bayou system in 1994. They are weaker than linearizability and much cheaper, because each one only constrains what a single client (or a single causal chain) sees.
| Guarantee | Promise | Violated when | Standard fix |
|---|---|---|---|
| Read-your-writes | After you write, your reads reflect that write | Your read goes to a replica that has not applied your write | Remember the log position of your write, and only read from replicas at or past it |
| Monotonic reads | Once you have seen a value, you never see an older one | Successive reads go to replicas with different lag | Sticky routing, or remember the highest position you have read |
| Consistent prefix | You see writes in an order that respects causality | Causally related writes live in partitions that lag differently | Put related writes in one partition, or carry causal dependencies with each write |
| Writes-follow-reads | A write you make after reading X is ordered after X everywhere | Your write replicates to a site that has not yet seen X | Attach the read's version to the write |
Notice that all of them are about one client's view. Two different users can still see different things at the same instant. If that is unacceptable, you need linearizability, and linearizable reads from followers require the follower to check with the leader or wait out a lease.
Read-your-writes, step by step
The time-window fix ("read from the leader for 60 seconds after a write") is popular and crude. It sends a lot of traffic to the leader, and it is still wrong when lag exceeds the window. The precise fix uses log positions as a causality token.
sequenceDiagram
participant U as User
participant App as App server
participant L as Leader
participant F as Follower
U->>App: POST /comment
App->>L: INSERT comment
L-->>App: committed at LSN 0/5A3F10
App-->>U: 201, cookie min_lsn=0/5A3F10
U->>App: GET /thread
App->>F: what LSN have you replayed?
F-->>App: 0/5A3E00, behind
App->>L: SELECT comments
L-->>App: rows including the new comment
App-->>U: thread with comment
Note over App,F: later requests go to F once its replay LSN passes 0/5A3F10
In PostgreSQL, the leader's position is pg_current_wal_lsn() (or the commit LSN you capture after your transaction) and a standby reports how far it has replayed with pg_last_wal_replay_lsn(). The app keeps the user's high-water mark and routes accordingly:
type Lsn = bigint;
// PostgreSQL prints LSNs as "XXXXXXXX/YYYYYYYY": high and low 32 bits in hex.
function parseLsn(s: string): Lsn {
const [hi, lo] = s.split("/");
return (BigInt("0x" + hi) << 32n) | BigInt("0x" + lo);
}
interface Replica {
name: string;
replayedLsn(): Promise<Lsn>; // SELECT pg_last_wal_replay_lsn()
query<T>(sql: string, params: unknown[]): Promise<T[]>;
}
export class SessionRouter {
constructor(private leader: Replica, private followers: Replica[]) {}
// Call after every write. Store the result in the user's session or cookie.
async afterWrite(currentMin: Lsn | undefined, commitLsn: string): Promise<Lsn> {
const lsn = parseLsn(commitLsn);
return currentMin !== undefined && currentMin > lsn ? currentMin : lsn;
}
// Read from any follower that has caught up to the session's minimum LSN,
// otherwise fall back to the leader. Covers read-your-writes AND monotonic
// reads, as long as the session's minimum also advances after each read.
async read<T>(minLsn: Lsn | undefined, sql: string, params: unknown[]): Promise<T[]> {
if (minLsn === undefined) return this.pick().query(sql, params);
for (const f of this.shuffled()) {
if ((await f.replayedLsn()) >= minLsn) return f.query(sql, params);
}
return this.leader.query(sql, params);
}
private pick(): Replica {
return this.followers[Math.floor(Math.random() * this.followers.length)] ?? this.leader;
}
private shuffled(): Replica[] {
return [...this.followers].sort(() => Math.random() - 0.5);
}
}
In production you would cache each follower's replay position for a few milliseconds rather than asking on every read, but the logic is the same. Other systems ship this idea as a feature:
- MongoDB causally consistent sessions attach an
afterClusterTimeto reads, and a secondary waits until it has applied that cluster time before answering. - Amazon Aurora replicas share the storage volume but have their own page caches, so they too lag by a small amount (typically tens of milliseconds). Reads that must see a write should go to the writer endpoint.
- Cosmos DB offers "session" consistency as a named level, implemented with a session token that the SDK carries between requests.
Monotonic reads without sticky routing
Hashing a user to one replica works until that replica dies, and then the user is rerouted to a replica that may be further behind, which is exactly the violation you were preventing. The token approach above handles it gracefully: if the user has read at position P, every subsequent read requires a replica at P or later. After each read, the session's minimum moves up to the position of the replica that served it. Failover of a follower becomes invisible to the session guarantee.
Consistent prefix in practice
Three practical tools, in increasing order of cost:
- Co-locate causally related data. Put a question and its answers under the same partition key (
thread_id), so one log orders them. - Carry dependencies. Each write records the versions it depends on, and a replica delays making a write visible until its dependencies are visible. This is the core of causal-consistency systems such as COPS, and it is what version vectors are for.
- Read at a snapshot timestamp. Systems with globally meaningful timestamps (Spanner, CockroachDB) can serve a read "as of time T" from any replica that has applied everything up to T, which gives a consistent prefix across partitions.
War Story (illustrative)
A marketplace moved its order-history page to read replicas to take load off the primary. Within an hour support tickets arrived: "I paid and my order disappeared." Checkout wrote the order to the primary, then redirected to the history page, which read from a replica about 400 ms behind. The first fix, "read from the primary for 5 seconds after checkout," held until a nightly batch job pushed replica lag to 40 seconds. The durable fix stored the commit LSN in the session and routed reads to any replica that had replayed past it. Primary read traffic stayed low because most replicas caught up within milliseconds of the redirect.
Failover
When the leader fails:
- Detect failure via heartbeat timeout
- Elect a new leader (the most up-to-date follower)
- Redirect clients to the new leader
Problems that can arise:
- Split brain — old leader comes back thinking it's still leader; two leaders accept writes simultaneously
- Lost writes — async-replicated writes on old leader that weren't yet replicated are lost when new leader takes over
- Wrong failover — promoting a follower that's far behind can lose more data
Failover is the most dangerous routine operation in a replicated system. Each of the three steps above hides a hard problem.
Hazard 1: Detection is a guess
There is no reliable way to tell a dead leader from a slow one or an unreachable one. A failure detector can only say "I have not heard from it for T seconds." The choice of T is a trade-off with no free option:
| Timeout | Benefit | Cost |
|---|---|---|
| Short (1–5 s) | Little write downtime after a real crash | False failovers during GC pauses, load spikes and network blips, each of which risks data loss and split brain |
| Long (30 s or more) | Rarely fires by mistake | Every real crash means half a minute or more of write unavailability |
A false failover is often worse than the outage it was meant to fix: it adds a second leader, discards the old leader's unreplicated writes, and frequently happens under load, which is when lag is highest. Many teams run automatic failover only with a quorum of independent observers (Patroni uses a consensus store, Orchestrator can be deployed with raft-based consensus between its own nodes) and some insist on a human confirming promotion of a replica that is known to be behind. See Timeouts, Retries and Backoff for how to pick timeouts from measured latency distributions.
Hazard 2: Choosing the new leader
The new leader should be the follower with the most of the old leader's log. With async replication, every candidate may be missing something, and whatever is missing is gone: the new leader's log becomes the truth, and the old leader's extra entries must be discarded when it rejoins. Consensus protocols make this precise. Raft only grants votes to a candidate whose log is at least as up to date as the voter's, which guarantees the winner holds every committed entry (see Leader Election and the Raft walkthrough). Ad hoc failover scripts often skip that check.
The discarded writes can do damage beyond their own loss. If the old leader handed out auto-increment IDs that the new leader then hands out again, and some other system (a cache, a search index, an external partner) already recorded the old IDs, two different records now share one identity. Kleppmann's Designing Data-Intensive Applications describes a GitHub incident in 2012 with this exact shape: an out-of-date MySQL follower was promoted, primary keys were reused, and because those keys were also used in Redis, some private data was shown to the wrong users.
Hazard 3: The old leader does not know it was replaced
A leader that was paused or partitioned, not dead, wakes up and keeps accepting writes. This is split brain. Turning it off ("STONITH", shoot the other node in the head) is fragile because the node you want to shoot may be unreachable for the same reason you failed over. The robust fix is fencing: every leadership term carries a monotonically increasing number, and the storage layer, replicas and downstream services reject anything stamped with an old number. A leader can also hold a time-bounded lease and stop serving once it cannot renew it. Both are covered in depth in Leases and Fencing.
A worked failover timeline
Three-node PostgreSQL cluster, async replication, write rate 1,000/s, failover manager with a 10-second leader timeout.
| Time | Event | State |
|---|---|---|
| t=0 s | Leader A at LSN 1000. Follower B at 990, follower C at 970 | Normal, 10–30 entries of lag |
| t=0.5 s | A's network switch port fails. A is up, but nobody can reach it | Clients near A keep writing to A |
| t=0.5–10.5 s | A accepts about 10,000 writes it cannot replicate | Divergence grows |
| t=10.5 s | Manager declares A dead and checks B and C. B is ahead at 990 | — |
| t=11 s | B promoted, starts a new timeline. C re-points to B | Writes 991–1000 and everything after are lost from the cluster's point of view |
| t=11–60 s | Clients that can reach B write there | Two leaders if A is still reachable by some clients |
| t=60 s | Switch port repaired. A sees it is no longer leader | A's 10,010 unreplicated writes conflict with B's history |
| t=60 s+ | A must be rewound (pg_rewind) or rebuilt, and its extra writes reconciled by hand or discarded | Data loss is now a business decision |
Three changes would have shrunk the damage. Semi-sync or quorum commit means B would have had every acknowledged write. A lease would have made A stop accepting writes once it could not reach the manager. And fencing tokens on downstream writes would have rejected A's late side effects.
War Story
GitHub's October 2018 incident is a well-documented real example. A roughly 43-second loss of connectivity between its US East Coast network hub and its primary East Coast data center caused its MySQL topology manager, Orchestrator, to promote primaries in the West Coast data center. Writes accepted on the East Coast in the short window before the promotion had not yet replicated west, and the West Coast primaries had then taken new writes. The two sides could not simply be merged, and cross-country latency to the new primaries hurt application performance. GitHub chose to prioritise data integrity and ran with degraded service for about 24 hours while restoring from backups and replaying and reconciling the stranded writes. GitHub's public post-incident analysis describes the timeline in detail.
Multi-Leader Replication
Multiple nodes accept writes. Each leader replicates to the others. Common for multi-datacenter setups.
graph LR
subgraph DC1[Datacenter 1]
L1[Leader 1] --> F1[Follower] & F2[Follower]
end
subgraph DC2[Datacenter 2]
L2[Leader 2] --> F3[Follower] & F4[Follower]
end
L1 <-->|async cross-DC replication| L2
Benefits:
- Writes served locally in each datacenter → low latency
- Works even if inter-DC network partitions (each DC keeps accepting writes)
The problem: write conflicts
1. User on DC1 sets title = "Hello"
2. Concurrently, user on DC2 sets title = "World"
3. Both leaders replicate to each other
4. What is the final value?
Conflict Resolution Strategies
Last-write-wins (LWW): Use timestamps — the write with the highest timestamp wins. Simple but loses data (the "Hello" write is silently discarded).
Merge: Keep both values and let the application merge them. Works for commutative operations (sets, counters). Used by Riak, CRDTs.
Custom conflict resolution: On write: reject the conflicting write (require explicit conflict resolution). On read: return all conflicting values and let the application decide. CouchDB uses this.
Operational Transformation / CRDTs: Design data structures that are inherently conflict-free. Every concurrent edit can be merged deterministically. Google Docs uses OT; collaborative text editors increasingly use CRDTs. See CRDT Fundamentals.
Multi-Leader Is More Common Than It Looks
You may never configure "multi-leader replication" in a database and still build one:
- Offline-capable clients. A mobile app that lets you edit notes on a plane has a local database that accepts writes and syncs later. Every device is a leader. Calendar sync, note apps and field-service tools all face multi-leader conflicts.
- Collaborative editing. Each open editor applies keystrokes locally and immediately, then exchanges them with others.
- Multi-region active-active. Each region accepts writes for low latency and survives losing the link to the others.
The common thread is that the system accepts a write before it can know about concurrent writes elsewhere. Conflicts are therefore not a bug to be prevented but a normal event to be designed for.
Conflict Avoidance: The Best Conflict Resolution
The simplest strategy is to make conflicts impossible for most data. Give every record a home leader (for instance, the region where the user signed up) and route all writes for that record there. Reads can still be served anywhere. You keep the latency win for most users and the conflict problem shrinks to the rare case where a record's home changes, such as a user moving or a region failing over. During that change, writes for the record may briefly land in two places, so you still need a resolution rule, but it fires rarely.
Detecting Concurrency
Before you can resolve a conflict you must recognise one. Two writes conflict if neither happened before the other. A wall-clock timestamp cannot tell you that: write B may carry a later timestamp than write A without B's author ever having seen A. Detection requires tracking causality, typically with a version vector of one counter per replica:
Write at DC1: title="Hello" version {DC1: 4, DC2: 7}
Write at DC2: title="World" version {DC1: 3, DC2: 8}
Neither vector dominates the other (4 > 3 but 7 < 8), so the writes are concurrent.
If DC2's write had carried {DC1: 4, DC2: 8}, it would dominate DC1's write, and
"World" would safely replace "Hello".
The full machinery, including dotted version vectors and sibling handling, is in Causality and Version Vectors.
Topologies and Their Ordering Problems
flowchart LR
subgraph Ring["Circular"]
A1["A"] --> B1["B"] --> C1["C"] --> A1
end
subgraph Star["Star"]
H["Hub"] <--> S1["S1"]
H <--> S2["S2"]
H <--> S3["S3"]
end
subgraph Mesh["All-to-all"]
A3["A"] <--> B3["B"]
B3 <--> C3["C"]
A3 <--> C3
end
| Topology | Failure tolerance | Ordering hazard |
|---|---|---|
| Circular | One node failure breaks propagation until reconfigured | Each write must carry the IDs of nodes it has passed through, or it loops forever |
| Star | Hub failure partitions all spokes | Same as circular, through the hub |
| All-to-all | Survives any single link failure | Messages take different paths, so they can overtake each other. An update can arrive before the insert it modifies |
The all-to-all overtaking problem is a causality problem. Node C receives "update row 42" from B before receiving "insert row 42" from A. Timestamps do not fix it, because clocks are not synchronised precisely enough to order events that happen milliseconds apart (see Clock Synchronization). Version vectors do: C can see that the update depends on a version it has not received yet, and buffer it.
Leaderless Replication
No designated leader. Any replica accepts writes. The client (or a coordinator) sends writes to multiple replicas simultaneously.
Made famous by Amazon Dynamo (2007). Used by Cassandra, Riak, Voldemort and ScyllaDB.
Correction
An earlier version of this page listed DynamoDB as leaderless. The 2007 Dynamo paper describes a leaderless system, but the AWS DynamoDB service is a different design: each partition is replicated across three availability zones in a group with a single leader elected by Multi-Paxos, and the leader handles writes and strongly consistent reads (Elhemali et al., "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service", USENIX ATC 2022). Eventually consistent reads may be served by any replica in the group.
graph TD
Client -->|write to all| R1[Replica 1]
Client -->|write to all| R2[Replica 2]
Client -->|write to all| R3[Replica 3]
Client2[Client] -->|read from multiple| R1
Client2 -->|read from multiple| R2
Quorum Reads and Writes
With N replicas, write to W replicas, read from R replicas:
The read will always hit at least one replica that has the latest write.
Common configurations:
| N | W | R | Trade-off |
|---|---|---|---|
| 3 | 2 | 2 | Balanced — tolerates 1 failure |
| 3 | 3 | 1 | Strong write consistency, fast reads |
| 3 | 1 | 3 | Fast writes, strong reads |
| 3 | 1 | 1 | Maximum availability, no consistency guarantee |
Cassandra defaults: N=3, W=1, R=1 (eventual consistency). Tunable per query.
Correction: Cassandra has no default replication factor. You set it per keyspace, and 3 is the usual production choice. What does default to one replica is the consistency level: ONE in older drivers and cqlsh, LOCAL_ONE in current DataStax drivers. So the common out-of-the-box combination is RF=3 with W=1 and R=1, as stated, but the RF comes from you.
A quorum write followed by a quorum read, in a three-replica group where one replica is slow:
sequenceDiagram
participant W as Writer
participant R1 as Replica 1
participant R2 as Replica 2
participant R3 as Replica 3
participant Rd as Reader
W->>R1: put k=v2, ts=20
W->>R2: put k=v2, ts=20
W->>R3: put k=v2, ts=20
R1-->>W: ack
R2-->>W: ack
Note over W: W=2 reached, write succeeds
Note over R3: message delayed, still holds v1 at ts=10
Rd->>R2: get k
Rd->>R3: get k
R2-->>Rd: v2, ts=20
R3-->>Rd: v1, ts=10
Note over Rd: R=2, newest wins, return v2
Rd->>R3: read repair, put k=v2, ts=20
Quorums Are Not Linearizability
guarantees that a read set overlaps the latest successful write set. It does not, by itself, give linearizable behaviour. The common gaps:
- Concurrent read and write. While a write is in flight, one reader may see the new value and a later reader may see the old one, depending on which replicas each contacts. Dynamo-style systems allow this. Making it linearizable requires readers to write back (synchronous read repair) before returning, as in the ABD algorithm.
- Failed writes are not rolled back. If a write reaches only one replica and reports failure, that replica still holds it, and later reads may or may not return it.
- Sloppy quorums break the overlap. Writes stored on stand-in nodes are not in the "home" N, so a strict read quorum can miss them.
- Last-write-wins on skewed clocks can discard a write that really came later.
- Replica replacement. If a replica holding the new value fails and is rebuilt from a stale one, the number of copies of the new value can drop below W.
These are covered in depth, with the probabilistic view of staleness, in Quorums and Leaderless Replication. The practical takeaway: treat Dynamo-style quorums as "very likely fresh," and use a consensus-based store when you need a guarantee, for instance for uniqueness constraints or compare-and-set. Cassandra offers lightweight transactions (Paxos-based) for exactly those operations.
Handling Stale Reads
Even with W+R > N, you can get stale reads if:
- A write failed on some replicas (partial write)
- A replica was down during the write and just came back
Read repair: When a read detects stale data on a replica, it writes the fresh value back. Happens in the read path.
Anti-entropy: A background process constantly compares replicas and syncs differences. Uses Merkle trees to efficiently find diverged data.
Hinted handoff: If a target replica is down, a different replica temporarily holds the write and forwards it when the target recovers.
Sloppy Quorums
During a network partition, strict quorum (W+R > N) might fail because not enough replicas are reachable. A sloppy quorum allows writing to any W reachable replicas, even if they're not in the usual N.
Trade-off: higher availability, but reads from the original N replicas might not see the latest write until handoff completes.
Chain Replication
Chain replication, introduced by van Renesse and Schneider at OSDI 2004, arranges the replicas in a line instead of a star. Writes enter at the head, flow node to node, and are acknowledged by the tail. Reads go to the tail.
flowchart LR
C1["Client write"] --> H["Head"]
H --> M["Middle"]
M --> T["Tail"]
T -->|"ack"| C1
C2["Client read"] --> T
Master["Configuration master<br/>(Paxos-replicated)"] -.-> H
Master -.-> M
Master -.-> T
sequenceDiagram
participant C as Client
participant H as Head
participant M as Middle
participant T as Tail
C->>H: write x=9
H->>H: apply, add to pending
H->>M: forward x=9
M->>M: apply, add to pending
M->>T: forward x=9
T->>T: apply, now committed
T-->>C: OK
T-->>M: ack x=9
M-->>H: ack x=9
Note over H,T: ack travels back so nodes can clear pending entries
C->>T: read x
T-->>C: 9
Why it is attractive
- Strong consistency is simple. The tail only holds writes that every node has applied, so reading from the tail is linearizable without any extra round trip or quorum.
- Load is spread. In star-shaped primary-backup replication, the leader sends every write to every follower, so its outbound bandwidth grows with N. In a chain each node sends each write once, to its successor.
- Recovery rules are local. Because the chain is ordered, each node's history is a prefix of its predecessor's, which makes failures easy to reason about.
Handling failures
The protocol relies on an external configuration master, itself replicated with Paxos in the original design, that detects failures and tells nodes about the new chain.
| Failed node | Repair |
|---|---|
| Head | Its successor becomes head. Writes the old head had accepted but not forwarded are lost, but they were never acknowledged, so clients retry |
| Tail | Its predecessor becomes tail. It holds every write the old tail had, and possibly more, so committed state only grows |
| Middle | Predecessor links to successor, then resends any pending writes the successor may not have received |
| Adding a node | New nodes join at the tail after copying the current tail's state |
Costs and the CRAQ variant
Write latency grows linearly with chain length, since a write must traverse every node, and all reads hit one node. CRAQ (Chain Replication with Apportioned Queries, Terrace and Freedman, USENIX ATC 2009) fixes the read bottleneck. Every node keeps a version per object marked clean or dirty. A node with a clean version serves the read locally. A node with a dirty version (a write is still propagating) asks the tail which version is committed and returns that. Read throughput then scales with chain length for read-mostly workloads while staying linearizable.
Chain replication shows up in research and specialised storage, for example the FAWN-KV store from Carnegie Mellon, and in systems whose authors cite it as a design inspiration. Most mainstream databases chose majority quorums instead, because a majority-quorum write can complete despite one slow node, while a chain is only as fast as its slowest link.
Replication Through Consensus
Single-leader replication with a majority acknowledgement rule and a safe election rule is no longer ad hoc. It is a consensus protocol. Raft, Multi-Paxos, ZAB and Viewstamped Replication all have this shape:
- One leader per term orders all writes into a log.
- An entry is committed once a majority of replicas have stored it.
- A new leader can only be elected by a majority, and only if its log contains every committed entry.
- Each replica applies committed entries in log order to a deterministic state machine.
Rules 2 and 3 together close the failover hazards above. Any two majorities overlap, so a new leader always overlaps with the majority that stored each committed entry, and the log-comparison rule guarantees it has those entries. A deposed leader cannot commit anything, because it cannot gather a majority in a term that has moved on.
| Concern | Classic async primary-backup | Consensus-based replication |
|---|---|---|
| Acknowledged write lost on failover | Possible | Not possible while a majority survives |
| Split brain | Prevented only by external fencing | Prevented by terms and majorities, though clients and side effects still need fencing |
| Nodes needed to tolerate f failures | f + 1 | 2f + 1 |
| Write latency | Leader's local commit | Leader plus the median follower's round trip |
| Behaviour without a majority | Keeps serving, possibly diverging | Stops accepting writes |
Systems built this way include etcd and Consul (Raft), ZooKeeper (ZAB), Spanner (Paxos per split), CockroachDB and TiKV (Raft per range), and MongoDB, whose replica-set protocol since 3.2 is Raft-inspired. The general model is covered in Replicated State Machines, and the protocols in Paxos and Raft in Plain English.
Replication Comparison
| Single-Leader | Multi-Leader | Leaderless | |
|---|---|---|---|
| Write conflicts | None (one writer) | Possible | Possible |
| Write latency | Leader RTT | Local DC | Tunable |
| Read latency | Low (follower) | Low (local DC) | Tunable |
| Failover complexity | High | Medium | Low |
| Consistency | Strong (sync) / Eventual (async) | Eventual | Tunable |
| Used by | PostgreSQL, MySQL, MongoDB, DynamoDB (per partition) | MySQL (cross-DC), CouchDB | Cassandra, Riak, ScyllaDB |
Replication Factor and Durability
Higher replication factor = more durability, more storage cost, higher write latency.
N=1: No redundancy. Any failure loses data. N=2: Survives 1 failure. No quorum possible (split-brain on partition). N=3: Survives 1 failure. Quorum = 2/3. Most common production default. N=5: Survives 2 failures. Used for critical data (financial records, auth tokens).
Rule of thumb: For OLTP data, N=3 with synchronous replication to at least one follower. For object storage (S3-style), N=3+ with erasure coding.
Practical Patterns
Read replicas (PostgreSQL):
Primary accepts writes, replicates via streaming WAL to standby nodes.
Application routes reads to standby, writes to primary.
Replication lag: typically <1s for same-region replicas.
Cassandra with LOCAL_QUORUM:
W=QUORUM within local DC, replicated async to remote DC.
Strong consistency within a DC, eventual across DCs.
MySQL GTID-based replication:
Global Transaction IDs track exactly which transactions each replica has applied.
Enables safe, automatic failover without manual binlog position tracking.
What Can Go Wrong in Production
- Replication lag spike under write burst → stale reads increase
- Circular replication in multi-leader without loop detection → infinite replication
- Ghost rows after failover — rows written to old leader that weren't replicated
- Schema changes on leader before replica has applied them → replication stops on type mismatch
- Clock skew in LWW — two writes a millisecond apart on different machines; NTP drift decides the winner
The safest default: synchronous replication to one follower + async to the rest, with automatic failover that requires manual confirmation before promoting a stale replica.
More failure modes worth knowing by name:
- Long-running queries on a replica block replay. PostgreSQL must choose between cancelling the query and delaying WAL replay when the query needs rows that replay would remove.
hot_standby_feedbackavoids cancellations but makes the leader keep dead rows, which bloats tables. - A replica's single apply thread falls behind a multi-threaded leader. The leader commits on many cores in parallel, while the follower applies the stream in order. Parallel apply (MySQL's multi-threaded replica, for example) helps only when transactions do not conflict.
- Retained log fills the disk. A replication slot or a binlog retention rule that waits for a dead replica keeps every log segment on the leader until the disk is full, and then the leader goes down.
- Cascading lag. A replica that feeds other replicas (cascading replication) adds its own lag to everything below it.
- Silent divergence. A manual write on a replica, a non-deterministic statement or a bug can make a replica differ from the leader without stopping replication. Periodic checksums (for example, Percona's
pt-table-checksumfor MySQL) are the only way to find it.
Choosing a Replication Strategy
flowchart TD
Q1{"Must every acknowledged<br/>write survive a node loss?"} -->|"Yes"| Q2{"Can writes wait for<br/>a majority round trip?"}
Q1 -->|"No, a few seconds of loss is OK"| A1["Single leader,<br/>async followers"]
Q2 -->|"Yes"| A2["Consensus log<br/>(Raft, Multi-Paxos)"]
Q2 -->|"No, too far apart"| Q3{"Can each record<br/>have a home region?"}
Q3 -->|"Yes"| A3["Multi-leader with<br/>conflict avoidance"]
Q3 -->|"No"| A4["Multi-leader or leaderless<br/>with CRDTs or version vectors"]
A1 --> Q4{"Read-heavy,<br/>users read own writes?"}
Q4 -->|"Yes"| A5["Add LSN-based<br/>session routing"]
| Requirement | Good fit | Avoid |
|---|---|---|
| Money, inventory, uniqueness constraints | Consensus-based or single leader with quorum commit | Async failover, LWW |
| Read scaling for a web app | Single leader plus async read replicas with session routing | Reading replicas blindly after writes |
| Writes from several continents with low latency | Multi-leader with home regions, or CRDTs | Synchronous cross-continent commit |
| Always-writable shopping cart, counters, presence | Leaderless with merge functions or CRDTs | Single leader in one region |
| Offline-first mobile app | Multi-leader (each device), CRDT document model | Anything that needs the server to accept the write first |
| Very high read throughput with linearizable reads | Chain replication with CRAQ, or consensus with follower reads under leases | Leaderless quorums |
Real numbers to keep in mind
| Quantity | Typical value |
|---|---|
| Same-region async replica lag, healthy | single-digit to tens of milliseconds |
| Lag during a bulk load or large transaction | seconds to minutes |
| Round trip, same zone | under 0.5 ms |
| Round trip, US East to US West | about 60–80 ms |
| Round trip, US East to Europe | about 70–90 ms |
| Failure-detection timeout in automatic failover tools | often 10–30 s |
| Replicas needed to tolerate 1 failure with majority quorums | 3 |
| Replicas needed to tolerate 2 failures with majority quorums | 5 |
These are rough planning numbers. Real values depend on the provider, the route and the load.
War Story (illustrative)
A team ran a single-leader PostgreSQL cluster with one synchronous standby in another zone, believing "synchronous" meant they could never lose data. During a zone outage, the standby went first. With synchronous_standby_names naming only that standby, every commit on the leader hung, and the on-call engineer "fixed" the outage by clearing the setting, turning the cluster async. Twenty minutes later the leader's zone failed too, and the async replica that was promoted was missing the last 90 seconds of orders. Two lessons: name several candidates with ANY 1 (...) so one standby's failure does not stall writes, and treat a drop to async as an alert, not a fix.
Interview Questions
1. What is the difference between synchronous, asynchronous and semi-synchronous replication, and what does each lose on leader failure?
Async acknowledges after the leader's local commit, so writes within the replication lag window are lost if the leader dies. Synchronous to all followers loses nothing but blocks writes if any follower is slow or down. Semi-sync (or quorum commit) waits for one follower or a majority, which keeps every acknowledged write on at least two nodes while tolerating some follower failures. Also mention what "ack" means: received, flushed or applied.
2. A user posts a comment and immediately reloads the page, but the comment is missing. Explain and fix it.
The reload read from a lagging replica, which is a read-your-writes violation. Capture the commit's log position (LSN or GTID) on write, store it in the session, and only read from replicas that have replayed past it, falling back to the leader. Time-window routing is a weaker alternative.
3. Why does a consistent-prefix violation require partitioning in a single-leader system?
With one log, every follower holds a prefix of the same total order, so causality is preserved. With several partitions, each with its own log and its own lag, related writes on different partitions can become visible out of order.
4. Walk through what can go wrong in an automatic failover.
False detection (a slow leader declared dead), promoting a stale follower (acknowledged writes lost, IDs reused), split brain (the old leader keeps accepting writes), clients and caches still pointing at the old leader, and the old leader's divergent history needing a rewind. Mitigations: quorum-based detection, safe election rules, fencing tokens and leases, and semi-sync or quorum commit.
5. If W + R > N, are reads in a Dynamo-style store linearizable?
No. Concurrent reads and writes can see values flip, failed writes linger on some replicas, sloppy quorums break overlap, LWW with clock skew discards writes, and replica rebuilds can reduce the copies. Linearizability needs synchronous read repair (ABD) or a consensus protocol.
6. How does chain replication provide strong consistency, and what are its costs?
Writes enter at the head and commit only at the tail, so the tail holds exactly the committed writes and reads from it are linearizable. Costs: write latency grows with chain length, the slowest node slows every write, and reads concentrate on the tail unless you use CRAQ. It also needs an external configuration service for membership.
7. When would you choose multi-leader replication, and how would you limit conflicts?
For multi-region writes with local latency, offline clients, or collaborative editing. Limit conflicts by giving each record a home leader, detect true concurrency with version vectors rather than timestamps, and resolve with CRDTs or application merge logic rather than LWW where data loss matters.
8. Why does consensus-based replication need 2f + 1 nodes when primary-backup needs only f + 1?
Primary-backup relies on an external oracle (an operator, or a coordination service) to decide who is primary, so any surviving copy can carry on. Consensus decides leadership internally by majority vote, and two majorities must always overlap to prevent two leaders, which needs 2f + 1 nodes to tolerate f failures.
9. Your async replica lag jumped from 50 ms to 3 minutes. What do you investigate?
A large or long-running transaction on the leader, a bulk load, a long query on the replica blocking replay, I/O or CPU saturation on the replica, a single-threaded apply bottleneck, network throughput between the nodes, and whether a cascading parent replica is itself lagging. Then decide whether reads should be routed away from that replica until it recovers.
10. How does DynamoDB's replication differ from the Dynamo paper's?
The paper describes a leaderless ring with sloppy quorums, hinted handoff and vector clocks. The DynamoDB service replicates each partition across three availability zones in a Multi-Paxos group with a leader that serves writes and strongly consistent reads, while eventually consistent reads can go to any replica.
Further Reading
- Kleppmann, Designing Data-Intensive Applications, chapter 5 (Replication)
- van Renesse and Schneider, "Chain Replication for Supporting High Throughput and Availability", OSDI 2004
- Terrace and Freedman, "Object Storage on CRAQ", USENIX ATC 2009
- Terry et al., "Session Guarantees for Weakly Consistent Replicated Data", PDIS 1994
- DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP 2007
- Elhemali et al., "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service", USENIX ATC 2022
- GitHub, "October 21 post-incident analysis" (2018)
- Operational detail: Replication deep dive (databases)