Replication strategies — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 5: Correctness across machines

Prerequisites: Lesson 26 and the preceding foundations.

Learning outcomes

Trace leader/follower and leaderless read/write acknowledgment paths.
Explain the additional ordering, membership, and failure assumptions needed beyond quorum intersection.
Follow lag, failover, repair, and divergent versions through an explicit example.

Copies do not decide when success is safe

A primary acknowledges a write and immediately fails. A follower is promoted, but it never received the acknowledged write. The cluster has several copies of older data and no surviving copy of the accepted result. Replication existed; the acknowledgment and promotion rules did not preserve the desired durability contract.

Replication is the propagation and maintenance of state across failure domains. A design must define authoritative order, acknowledgment conditions, read paths, divergence handling, and reconfiguration. More copies can improve resilience, read capacity, or geographic access, but those benefits come from specific protocols.

Leader and follower paths

In a leader/follower model, a leader orders or accepts writes and sends changes to followers. Followers may apply a log or receive another state representation. The write response can wait for local durability, remote receipt, remote durability, remote application, or some combination.

These are different guarantees and costs. A follower can have received bytes without making them durable. It can have durable log records without applying them to its queryable state. A read from that follower may therefore lag despite a durable copy existing.

leader append -> follower receive -> follower durable -> follower apply
       |                  |                 |                 |
 possible acknowledgment boundaries under different contracts

The schematic is not a recommendation to acknowledge at every boundary. It shows why a configuration needs precise semantics. A failover policy must choose a replacement compatible with whatever boundary the service promised to clients.

Synchronous and asynchronous replication

Synchronous replication waits for specified remote progress before returning success. It can protect against losing the leader’s failure domain while adding communication and waiting for required replicas. The exact required set determines both resilience and latency.

Asynchronous replication returns before selected followers reach that progress. It reduces waiting and can keep writes available during some follower problems, while exposing a loss or staleness window under relevant failures. A bounded lag policy can reject writes when the window becomes too large, trading availability for a tighter limit.

A slow synchronous follower can affect the primary’s tail latency. Waiting for any one of several suitable replicas differs from waiting for all. Placement matters because independent failure domains may be farther apart. The architecture should state which failures the acknowledgment survives rather than simply saying replicated.

Read routing and stale observations

Followers can serve reads under a freshness contract. A local follower may provide low latency but lag the latest leader state. Read-your-writes can require routing to the leader or waiting until a follower reaches a recorded position. A strong read may need additional authority or quorum evidence.

A read replica does not automatically increase write-processing capacity. It can move read work away from the leader, indirectly freeing resources. Every accepted write still needs ordering and replication under the chosen design. Adding replicas can increase total write-distribution work.

Failover complicates session observations. A client that read a recent value from one replica can later reach another with older state. Monotonic-read or causal tokens can prevent regression if the system supports them. Without such a contract, eventual convergence alone does not prevent backward-looking user experiences.

Quorum reasoning

For a fixed set of N replicas, read set size R and write set size W intersect when R + W > N. With illustrative N=5, R=3, W=3, any read set and write set overlap in at least one replica. The combinatorial intersection is useful, but it is not a complete linearizability proof.

The protocol must also define version ordering, concurrent writes, incomplete writes, durable acknowledgment, and configuration changes. A read can contact an overlapping replica yet select the wrong version if resolution rules are inadequate. Sloppy quorums that temporarily use different replica sets require additional analysis.

Quorum intersection is therefore one ingredient. An engineer should explain which information the overlapping participant carries and how the reader uses it safely. A formula without the surrounding protocol can create false confidence.

Leaderless writes and conflict resolution

A leaderless model can accept writes through several coordinators or replicas. It needs a way to reconcile concurrent versions and repair missing data. Historical Dynamo is a primary case of this design family, with assumptions and application responsibilities specific to that system.

Version vectors can represent causal relationships and concurrent versions. Timestamp-based last-write-wins chooses a winner under a timestamp order, potentially discarding another update. Neither mechanism automatically preserves an invariant such as one exclusive owner or a nonnegative global balance.

Cassandra’s documented architecture uses Dynamo-influenced distribution and its own timestamp-based reconciliation behavior. Its lightweight transaction facilities and other special paths must be distinguished from ordinary writes. The course does not classify all operations in a product under one simplistic consistency label.

Repair and anti-entropy

Replication streams can miss updates because nodes were unavailable or state was lost. Repair compares replicas and transfers differences. Merkle-tree-style summaries can help locate mismatching ranges without sending every byte first. Hinted delivery and read repair address related but distinct gaps.

Repair consumes CPU, disk, and network resources. Delaying it indefinitely can make divergence and deletion retention unsafe. Running it without resource control can harm foreground latency. The operational schedule must fit the retention and failure model.

Tombstones deserve particular care. Removing a deletion marker while another replica still holds an old value can permit resurrection during later repair. Safe collection depends on the database’s protocol and maintenance assumptions. An embedded LSM compaction rule alone cannot establish that all distributed replicas have forgotten the old value.

Promotion, fencing, and catch-up

A replacement leader must have an appropriate history and must exclude obsolete leaders. Catch-up can replay a log or install a snapshot. Snapshot installation needs a consistent state plus the correct subsequent log boundary, not a mixture assembled from arbitrary files.

A node far behind can create a large recovery workload. Streaming a snapshot competes with foreground bandwidth and storage. If several replicas restart together, the primary can become overloaded while trying to restore redundancy. Capacity planning should include the cost of failure recovery, not only the fully healthy state.

Membership changes alter which sets protect acknowledged data. A safe protocol coordinates configuration transitions so two disjoint groups do not each act as the authority. Lesson 28 develops consensus and leadership rules that make such transitions more precise.

Write acknowledgment is a vector of progress

A replication status should distinguish at least the leader’s appended position, the leader’s durable position, each follower’s received position, each follower’s durable position, and each follower’s applied position. For one transaction those values can advance at different times. A follower can protect against leader disk loss without yet serving a read containing the transaction.

Suppose a transaction ends at log position 900. Follower F1 has received through 920, persisted through 880, and applied through 870. F2 has received and persisted through 905 but applied only through 850. If acknowledgment requires remote durability through 900, F2 satisfies it and F1 does not. If the subsequent read requires visible state through 900, neither follower is ready yet.

These are constructed positions, not product metrics. They demonstrate why a dashboard showing one generic “replication lag” can be misleading. Byte lag, time lag, durable lag, and apply lag answer different questions. Time-based lag may also be hard to interpret when no writes occur, so progress markers and heartbeat semantics matter.

Promotion rules must preserve the evidence promised at acknowledgment. If success waited only for F2 and F2 is unreachable during failover, promoting F1 may discard acknowledged work. The service can wait for a sufficiently up-to-date candidate, recover F2, or follow a documented weaker emergency procedure. “Choose the fastest reachable follower” is not a durability protocol.

Replication placement sets a latency floor

Assume a local leader writes its log in 0.7 milliseconds and a required remote replica has a 30-millisecond round-trip path plus 0.8 milliseconds of flush time. Depending on overlap and protocol structure, the remote durability stage can dominate the acknowledgment path at roughly thirty-plus milliseconds. Reducing local validation from 0.5 to 0.1 milliseconds cannot remove that remote evidence requirement.

Waiting for every replica differs from waiting for a sufficient subset. If three candidate remote replicas have response times of 5, 8, and 200 milliseconds, waiting for any two is governed by the second-fastest adequate response rather than the slowest. The actual rule also depends on failure-domain placement: two fast replicas in the same zone may not provide the intended zone-failure resilience.

The acknowledgment set is therefore chosen for both timing and failure independence. An algorithm can achieve excellent latency by keeping all voters nearby, while a deployment intended to survive a regional outage may require a distant participant. Comparing the resulting latencies without placement information confuses topology with software efficiency.

A replica receiving every write consumes network, CPU, and storage work even if it serves no reads. Three replicas increase total write-application work substantially, although different stages can overlap. Replication can free leader resources by offloading reads, but it does not divide the logical mutation of one hot key into three independent mutations.

Quorum intersection is necessary evidence, not a complete algorithm

For N=5, W=3, R=3, every successful read set intersects every successful write set because two sets of three cannot fit disjointly within five. The minimum intersection size is one. If W=2 and R=3, disjoint sets are possible because the sum equals N rather than exceeding it.

Now consider a partially completed write. A new value reaches one replica, but the writer times out before collecting W acknowledgments. A read might encounter that value and return it. Another read could contact replicas without it and return the old value. Whether this is permitted depends on how the protocol orders writes, completes uncertain operations, and performs read repair or write-back.

For an atomic register, read protocols can need an additional propagation step to ensure a value observed by one completed read cannot disappear from a later nonoverlapping read. Version tags must also totally order competing writes in a way consistent with the desired guarantee. The overlap formula alone does not supply either property.

Membership changes can invalidate the fixed-set argument. An old configuration’s write set and a new configuration’s read set may not overlap at all unless the transition protocol preserves their relationship. Similarly, a sloppy quorum that uses temporary substitute nodes is not automatically the same set of N logical replicas assumed in the equation. These details are why a consistency level label should be read with its complete protocol.

Concurrent writes need domain-aware interpretation

Suppose two clients independently update a shopping cart from {book} to {book, pen} and {book, mug}. A last-write-wins policy can retain only one addition. A merge policy can preserve both additions, but deletion creates ambiguity: was an omitted book intentionally removed or merely absent from a stale base version? An application-aware data type needs operation identity and causal context to answer that question.

For a bank balance, merging two replacement numbers is generally not equivalent to preserving two transfers. Modeling operations or separate ledger entries may be more appropriate, while enforcing overdraft limits still needs coordination or preallocated rights. Data modeling and replication conflict semantics interact; no generic winner rule preserves every invariant.

Wall-clock last-write-wins can be sensitive to skew. A node whose timestamp is far ahead can cause later real-world updates to lose until clocks catch up. The timestamp order can still be a deterministic resolution policy, but it should not be described as a proof of real-time correctness. Operational clock discipline and application tolerance belong in its evaluation.

Historical Dynamo exposed sibling versions and application reconciliation for some conflicts. Cassandra documents its own timestamp-based reconciliation and additional paths for conditional operations. Their architectures share lineage without being identical interfaces or consistency contracts. Case-study analysis should preserve that distinction rather than assign one label to all their operations.

Repair has its own consistency window

An unavailable replica misses writes. When it returns, streaming logs, hinted delivery, read repair, or anti-entropy can restore missing data, depending on the engine. None is a universal substitute for all the others. A hint can expire, a cold key may never be read, and full repair can require substantial scanning.

Merkle-style summaries compare ranges recursively. Matching hashes can avoid transferring every row, while differing subranges are narrowed and reconciled. Hash equality is evidence under the chosen hash assumptions and representation, not a magical guarantee against every corruption class. The system must also compare compatible snapshots or account for concurrent changes during repair.

Suppose a replica is absent for six hours while the service receives 20 MB/s of logical writes. A full retained stream contains an illustrative 432 GB of changes before compression and protocol overhead. Catch-up at a net surplus of 100 MB/s takes 4,320 seconds, or seventy-two minutes. If ongoing writes consume most available bandwidth, the surplus may be much smaller and catch-up may never finish.

Repair debt therefore needs monitoring and resource reservations. Running repair without bounds can harm foreground latency; postponing it indefinitely can violate deletion-retention assumptions and reduce resilience. A sustainable design keeps convergence work below a known backlog envelope and defines when a replica must be rebuilt instead of incrementally repaired.

Tombstones encode knowledge, not just absence

A replica holding a deletion marker knows that an older value should not be resurrected. If the marker is discarded while another replica remains offline with the old value, later reconciliation can reintroduce it. Safe collection requires the engine’s stated grace, repair, and membership assumptions to hold.

The same problem appears when restoring an old backup into a live cluster. Its stale values can conflict with more recent deletions if introduced without a controlled bootstrap protocol. Rejoining should establish the node’s history and valid starting point rather than advertise arbitrary old data as current.

Space reclamation can therefore depend on distributed knowledge. Local compaction may see no newer local reader and still be unable to remove a tombstone safely. An LSM engine’s local rules and a distributed database’s repair rules belong to different layers and must be connected explicitly.

Retention policies should specify the longest supported disconnection, required repair cadence, and node replacement procedure. A “delete after seven days” setting is meaningful only with those operational constraints. Capacity planning must include markers and historical data retained to preserve that knowledge.

Bootstrap requires a snapshot plus an ordered suffix

A new follower cannot safely copy changing files independently and then begin receiving arbitrary new log records. It needs a consistent base state through a known position and every required subsequent change. If the snapshot covers position S, replay starts at the correct successor boundary and applies in the proper order.

A live snapshot may be created through MVCC, copy-on-write storage, a backup protocol, or a controlled pause. Each has costs. A snapshot retaining old versions can increase memory or disk usage on the source; a full copy consumes network and storage throughput. Throttling protects users but extends the interval of reduced redundancy.

Bootstrap must also preserve format, configuration, and authority metadata. A state image without the consensus group’s identity or compatible log position can be dangerous even if its rows look correct. Partial snapshot installation should remain invisible until a valid complete state can be selected atomically according to the engine’s recovery protocol.

Read scaling is conditional on freshness and workload

If most reads tolerate lag, followers can add useful serving capacity. If every read requires the latest authoritative state and leader verification, the read path retains coordination costs. A follower can still execute heavy queries after obtaining a safe read boundary, but freshness establishment and apply progress must be accounted for.

Followers share the write workload because they apply accepted changes. A write-heavy service may leave limited CPU or I/O for extra reads. A long analytical query can also retain versions or interfere with apply work according to the implementation. More replicas do not imply a perfectly independent read tier.

The correct replication specification finally names its acknowledgment boundary, accepted failure domains, promotion restrictions, read freshness modes, repair policy, and membership transition. With those choices explicit, replica count becomes one parameter in a coherent system rather than a substitute for its correctness argument.

Draw the sets before applying the quorum formula

replica universe: {A, B, C, D, E}
accepted write:   {A, B, C}
possible read:         {C, D, E}
intersection:          {C}

The overlap at C proves that the sets share a participant. It does not prove C returns the accepted value, that its copy survived a crash, that the read chooses the right tag, or that an incomplete later write cannot cause read regression. Each missing fact belongs to the protocol surrounding the set arithmetic.

For a new configuration {D,E,F,G,H}, a read set {F,G,H} need not intersect the old write set at all. A safe membership transition must transfer or preserve the necessary history and quorum relationships. Recomputing R and W within the new universe cannot retroactively protect old acknowledgments. This is why reconfiguration is part of replication correctness rather than an administrative afterthought.

A failover decision should expose its contract

Suppose the leader and its only up-to-date synchronous follower are unreachable, while an older follower remains available. The service has a real choice: wait and preserve the prior durability promise, or force promotion and potentially lose acknowledged work. A user-facing availability claim should not pretend the second option preserves the first contract.

An emergency mode can be valid when explicitly authorized by the product’s recovery policy. It should identify the last confirmed durable position and potential loss interval, fence old authorities before accepting new writes, and retain evidence needed for later reconciliation. Recovering old nodes afterward may require comparing divergent histories rather than simply streaming a suffix.

The UX consequence can be severe even when the lost window is short. A player may have seen a rare item acquisition, a merchant may have received an order confirmation, or a user may have spent a balance that reappears inconsistently. Describing the risk in terms of acknowledged outcomes is more useful than saying the database is “eventually durable.”

Read replicas can improve write latency indirectly

Offloading a heavy read can reduce contention for CPU, buffers, or I/O on the leader. That can shorten the leader’s write path even though replicas do not directly parallelize its logical write ordering. The benefit depends on the original resource bottleneck and the cost of applying the same writes on followers.

A fair comparison therefore measures leader resource use before and after offload, replica freshness, and total cluster work. Adding replicas may improve the application SLO while increasing total resource consumption. That can be a good trade, provided the architecture states which cost moved and which guarantee the reader receives.

Replication preserves a stated contract only when acknowledgment, promotion, read routing, and repair rules agree on which history is authoritative.

Case connection and design conclusion

PostgreSQL documents streaming-replication behavior and different synchronization options. Dynamo’s original paper and Cassandra’s architecture document different distribution and reconciliation choices. These are evidence-backed examples; the scenario calculations are constructed analyses of their general mechanism families.

A replication design states what is copied, who orders it, when success is acknowledged, what readers may observe, and how failures and membership changes preserve the contract. Counting replicas is only the beginning of that specification.

Sources and further reading

Course index · Lesson plan