Replication and durability

01What are replication and durability?

Replication means maintaining copies of the same logical data on several machines. A replica is one of those copies; engineers also use the word for the database instance that holds it. Durability means a committed change survives the failures covered by the system's guarantee. A replica can exist and still be too far behind to preserve an acknowledged write.

In single-leader replication, one leader orders writes and followers copy its log. In multi-leader replication, multiple leaders accept writes, so concurrent changes need a conflict rule. In leaderless replication, clients or coordinators contact multiple replicas; versioning, quorums, and repair determine the result. This lesson first traces the single-leader case because it makes it easy to see when the service may safely tell the client that a write succeeded.

A single-copy database can acknowledge a write that later disappears with the only usable storage. For a bounded example, cart C17 changes from version 40 to version 41 with mugs = 2. The acknowledgment policy must specify whether that result survives a process crash, disk loss, or loss of a complete replica; merely adding machines does not establish the promise.

Redundancy means having additional resources: another database copy, application instance, or network path. Replication is the process that carries changes between copies. Adding an empty second database provides neither a current cart nor a useful recovery path. We need a protocol for moving updates and deciding which state is authoritative.

Assume three database participants, A, B, and C, in separate failure zones. A currently orders writes. Our chosen promise is that an acknowledged cart change survives one participant’s failure. All timestamps are illustrative rather than measurements of a product. The version-41 trace tests acknowledgment, read visibility, and recovery separately.

These describe who accepts and orders writes, not a universal consistency level. A last-writer-wins conflict rule may discard one concurrent cart edit; merging a set of product IDs cannot by itself preserve a quantity decrement. Choose conflict semantics from the operation, not merely from the desire to write locally.

02Replication logs: received, durable, applied, committed

A replication log is an ordered sequence of changes that replicas can receive, persist, and replay. Each entry identifies a change and its position in that history. Queryable data pages are a separate representation, so durable logging and visible application need not happen simultaneously. In the example, A records the C17 version-41 update before forwarding the log entry.

The protocol determines when an entry is committed: accepted into the authoritative history under its safety rules. Counting network receipts without those rules does not establish commitment.

03Synchronous versus asynchronous replication

The acknowledgment policy chooses how much replication must finish before the client hears “saved.” Synchronous replication waits for a configured stage at designated replicas; asynchronous replication allows that work to continue after the reply. In our three-participant example, a majority is two participants, including the leader. Their durable acknowledgments matter only within a protocol that preserves the resulting committed history.

For the one-replica-loss requirement, choose a protocol that commits after the required durable majority acknowledgment. A waits until B confirms durable receipt at .008, then returns version 41. A subsequent failure of A leaves the committed information on B, and the election/recovery rules must preserve it.

Waiting costs remote network and storage time. It can also prevent writes when the required participants are unreachable. Waiting for every replica often worsens tail latency compared with an appropriate majority protocol. Choose the acknowledgment rule from the failure promise, not from a claim that more copies are always better. PostgreSQL’s standby documentation illustrates configurable acknowledgment stages.

The example is a safe majority protocol, not a claim that any database becomes Raft by waiting for a standby. In PostgreSQL, configured synchronous standbys and synchronous_commit=on wait for remote durable logging; remote_write can stop at the standby operating-system buffer, and remote_apply additionally waits for replay. Promotion eligibility and prevention of competing primaries still require a failover design. An acknowledgment setting does not supply that design.

Our three failure zones protect the stated single-participant loss. If all three are within one region, their count does not establish region-loss durability. Cross-region copies add network delay and require a separate placement and acknowledgment decision.

04Replica lag and read-your-writes

Replica lag is the gap between a source’s progress and a follower’s received or applied state. A read can therefore be stale even after the write commits durably. In the example, a read at .010 seconds reaches C, which still serves v40 although v41 has committed elsewhere. Durability and read visibility require separate policies.

A commit-position token identifies the write’s location in a particular replication history. A follower’s applied position identifies how far it has replayed that same history into queryable state. Comparing those positions lets a read wait for its required write instead of guessing how many milliseconds replication needs.

After a write, send the read to the current leader. Alternatively, return the write’s log position and make a follower wait until it has applied that position before answering. Use the database’s supported mechanism; an application-assigned version number alone cannot prove a follower has caught up.

For the cart, we choose read-your-writes: the client should observe its own acknowledged change. Product browsing can use a different policy. A fixed sleep is only a guess because lag can grow under load or failure.

A current-state read needs more than a machine that once accepted writes. A linearizable read must fit an order that respects completed operations in real time, so it cannot return a version from before a write that completed before the read began. Checking current authority is part of establishing that guarantee after failover.

A server calling itself “leader” may be an isolated former leader with old data. For linearizable reads, a consensus-based database must confirm its current leadership and apply the required committed entries before answering. A read-your-writes token must also refer to the correct history after failover. A number from another shard or a discarded history does not prove this replica includes the write.

05Leader failover and split-brain prevention

Leader failover lets another replica accept writes when the leader becomes unusable. Missing replies cannot tell us whether A crashed or lost its network connection. If B takes over while A keeps accepting independent writes, their data can diverge: this is split brain. The election and storage protocol must prevent it. Consider A becoming unreachable after the version-41 commit.

Safe failover has four obligations:

In this example, B and C form the required majority and the protocol establishes B as leader. A’s later return does not automatically restore its authority.

Response loss requires operation deduplication independently of replication. If v41 committed but its reply was lost, retry with the same operation identifier and recover its durable outcome. Applying “add two mugs” twice would turn uncertainty into four mugs. Routing clients away from A changes discovery; it does not itself fence obsolete writes.

06Replication versus sharding versus backups

Three copies of C17 are replicas. Three servers each holding different customers are shards. Replication helps survive loss and may add read capacity; sharding divides data and work. Adding followers does not automatically multiply a single leader’s write capacity, because every follower still processes the write stream.

Copies must occupy appropriate failure domains. Three processes on one laptop do not survive laptop loss. Three zones still share risks such as a bad application release or administrator action.

07Replica repair: anti-entropy, Merkle trees, read repair, and hinted handoff

Replica repair detects and reconciles differences between copies that missed updates. The repair must follow the store's version and conflict rules; it cannot simply trust whichever machine responds first. A leader/follower log normally catches up by replaying missing committed entries or installing a snapshot. The following mechanisms are common in Dynamo-style replicated stores and must not be confused with electing a new leader.

Why repair must cover cold data

Anti-entropy means systematically reducing divergence, including records that receive no foreground reads. Suppose A and B contain cart C17 at version 41 while C still has version 40. A surviving hint may deliver the missed update to C. A read comparing B and C may repair that particular cart. Scheduled range repair also discovers the difference when nobody reads C17. Hints and read repair therefore reduce inconsistency but do not replace full repair coverage.

How a Merkle tree locates differences

To compare replicas without first transferring every record, compute compact hash summaries of the same data ranges. A hash is derived from encoded bytes, so the replicas need a canonical encoding: the same record must produce the same byte representation on both machines. The tree then organizes those summaries so a mismatch can be narrowed to a smaller range.

A Merkle tree summarizes data from the bottom up: leaves hash canonical records or small ranges, and each parent hashes its children. Compare roots for the same range and comparable repair snapshot. If they differ, descend only into mismatching branches. For four leaf ranges, matching left-half summaries let replicas focus on the right half containing C17 instead of transferring every record. After locating differences, exchange the actual versioned data and reconcile it. Matching hashes are equality evidence under the chosen collision assumptions, not a mathematical guarantee of uniqueness. Building the summaries still costs work, even when little data needs streaming.

Why deletion evidence must survive

Deletes require repair too. A tombstone is a versioned deletion marker that tells another replica its older value must remain deleted. If A and B delete C17 while C is offline, immediately erasing both the value and its tombstone removes that evidence. When C returns with version 40, repair could resurrect the deleted cart. Retain deletion evidence long enough for every relevant replica to be repaired, or exclude and rebuild a replica that missed the safe recovery horizon. In Cassandra, plan and verify repair completion before the applicable gc_grace_seconds horizon; actual tombstone removal also depends on compaction and table settings. Time passing alone does not prove that every replica learned the delete.

Repair promotes convergence under its delivery, retention, and conflict-resolution assumptions. It does not undo a stale response already returned, recover a write absent from every surviving copy, or establish linearizability by itself. Cassandra's blocking read repair supports a specific monotonic-quorum-read behavior; it is not a general transaction guarantee. Monitor completed range coverage, repair age, hint backlog, and repair resource use instead of treating a started repair job as proof of recovery.

08Interview answer: defend the acknowledgment and read policy

Interviewer: “Why not just put a read replica behind the load balancer?”

Candidate: “That can improve reads, but I first need to define what an acknowledged cart update survives. With asynchronous replication, A could acknowledge v41 and fail before B receives it. For our one-node-loss promise, I would choose the necessary durable acknowledgments and a safe election protocol.

“I would also avoid sending a read-after-write request to an arbitrary lagging follower. An authoritative read or verified replication position preserves the session’s read-your-writes contract. Finally, if a buggy job deletes the cart, every live replica may copy that deletion. I need retained history and a restore procedure for that failure.”

This answer separates keeping an acknowledged change, showing the right version, and recovering an earlier valid state. It explains why the extra components exist and what each costs. A diagram of repeated databases becomes useful once those behaviors are explicit.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.