The question this answers
My replicas have drifted apart and nobody noticed. What brings them back together?
Given a deterministic merge rule and a period without new writes, a completed anti-entropy pass leaves the compared replicas holding identical values for every key in the compared range. It says nothing about when a pass completes, and it cannot recover data that reached no replica at all.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A replica knows its own contents. It does not know whether it is missing anything, because a missing key is indistinguishable from a key that never existed. Divergence is undetectable from a single node by construction — which is why repair requires comparison, and why it must be scheduled rather than triggered.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
Where divergence comes from
Divergence is not exotic. In any system that acknowledges a write before every replica has it, it is the expected steady state.
Partial quorum writes. With N=3, W=2, the write is acknowledged when two replicas have it. The third is behind, by design, and nothing in the write path ever comes back for it.
A replica that was down. It missed everything written while it was away. On return it looks healthy and serves reads immediately, including reads for keys it never received.
Expired or dropped hints. Hinted handoff stores writes destined for a down replica and replays them on return. Hints have a TTL, and the hint store has a capacity; both are exceeded routinely during a long outage or a load spike, and the excess is discarded.
Dropped mutations under load. A node shedding load or timing out internally may drop a replica write that the coordinator already counted as one of its W.
Corruption. Bit rot, a bad disk, a bug during compaction. The replica has data — wrong data — and reports itself healthy.
None of these produces an error at the time. That is the defining property of this whole lesson: divergence is silent, and therefore must be looked for rather than waited for.
Three repair mechanisms, and what each one leaves behind
Systems typically run all three, and they are complementary rather than alternative. The instructive part is what each does *not* cover.
Read repair. When a read consults several replicas and they disagree, the coordinator returns the winner and writes it back to the laggards. It is nearly free — the replicas were already being read — and it repairs exactly the data that is being read. Its limitation is total: cold data is never read, so it is never repaired. In a typical access distribution, most keys are read rarely or never, so read repair covers a small fraction of the dataset while giving a strong impression of health.
Hinted handoff. The coordinator, unable to reach a replica, stores the write locally as a hint and replays it when the replica returns. Excellent for short outages — a restart, a brief network blip — and it keeps the replica count effectively whole. Its limitations are the TTL and the hint store’s capacity, and both are exceeded exactly when the outage is serious.
Anti-entropy repair. A background process that compares full key ranges between replicas and repairs every difference. It is the only mechanism that covers cold data, and the only one that fixes divergence after hints have expired or corruption has occurred. Its cost is that it must, in principle, compare everything — which is why Merkle Trees: Finding the Difference Without Reading the Data exist.
The framing to keep: read repair is opportunistic, hinted handoff is a short-term buffer, and anti-entropy is the only thing that guarantees anything.
| Mechanism | Triggered by | Covers | Does not cover | Cost |
|---|---|---|---|---|
| Read repairtypical | A read that sees disagreement | Data that is actually read | Cold data — permanently | Near zero; occasionally extra write latency |
| Hinted handofftypical | A replica being unreachable at write time | Writes during short outages | Outages longer than the hint TTL; hints lost when the store fills or the coordinator dies | Storage and replay traffic on the coordinator |
| Anti-entropy repairtypical | A schedule, or an operator | Everything in the compared range, including cold data and corruption | Data that reached no replica at all | A full comparison plus streaming of differences — a self-inflicted load spike |
The deletion problem: why repair has a deadline
This is the operational consequence people meet the hard way, and it is the strongest argument for running repair on a schedule you actually meet.
In a replicated store with no single ordering point, a delete cannot simply remove the row. If it did, a replica that missed the delete would still hold the value, and the next comparison would see "A has data, B has nothing" and helpfully copy the data *back*. A delete must therefore be recorded as a tombstone — an explicit marker that says "deleted at time T" — so that comparison resolves in favour of the deletion.
Tombstones cannot be kept forever; they accumulate and slow down reads. So they are garbage-collected after a grace period. And now the deadline is visible: if a replica missed both the delete and the tombstone, and the tombstone is purged before repair compares that range, the surviving replica’s live value wins and the deleted data comes back. Cassandra names this window gc_grace_seconds and the rule is blunt: complete a full repair within it, or accept resurrected deletes.
The failure is one of the nastiest in this domain because it is silent, delayed, and looks like an application bug. A user deletes something, it disappears, and weeks later it is back — with no error, no log line, and nothing to correlate against except a repair schedule nobody was watching.
The knock-on rule is equally blunt: as a dataset grows, full repair takes longer, and at some point it exceeds the grace window. Repair duration is a capacity metric with a correctness consequence, which is not how anyone instinctively treats a background job.
- replica A — delete applied; tombstone purged after grace period
- replica B — delete applied; tombstone purged after grace period
- replica C — was down during the delete; still holds the live value
- rcbelieves “this row exists and is current”✕ and it is false
- rabelieves “this row was deleted and the evidence is no longer needed”✕ and it is false
Every node above is acting on what it believes. Nothing in the cluster tells the mistaken one that it is mistaken.
Repair is a rebalance in disguise
Anti-entropy has the same cost profile as Rebalancing: A Load Spike You Schedule for Yourself and deserves the same operational respect. It reads large amounts of data on both sides, streams the differences over the network, and writes them at the destination with all the compaction amplification that implies. Running it during peak traffic is a self-inflicted load spike, and running several ranges concurrently multiplies it.
The standard mitigations mirror the rebalancing ones. Subrange repair: repair a slice of the token range at a time, so each pass is short, interruptible and schedulable. Incremental repair: track which data has already been repaired and compare only what is new — much cheaper, at the cost of extra bookkeeping and a class of bugs where the "already repaired" marking is wrong. Rate limiting on both comparison and streaming. Off-peak scheduling, which is nearly free and is skipped surprisingly often.
And the important asymmetry: repair is *urgent* in a way rebalancing is not, because of the grace-period deadline. The correct operational posture is a continuous, low-rate, always-running repair that completes a full cycle well inside the tombstone window — not an occasional large operation someone remembers to run.
When you do not need any of this
Anti-entropy is a consequence of a specific choice: replicas that accept writes independently, with no single ordering point. Change that choice and the problem changes shape entirely.
Under leader-based replication with an ordered log, replicas cannot diverge in the same way. A follower is behind, not different — it holds a prefix of the same sequence. Catching up is a log replay from an offset, not a set comparison, and it is cheap, incremental and exact. That is a strong argument for leadered replication whenever you can tolerate the leader’s availability characteristics (Leader-Based Replication: Buying Order With a Single Writer, The Raft Log: Commit Index, Divergence and Reconciliation).
Under CRDTs, divergence is not an error but an expected state with a defined resolution, so replicas can be merged at any time without deciding who is right (CRDTs: Deterministic Merge, Not Correct Merge, What "Eventually Converges" Actually Requires). You still need to exchange state — which is still anti-entropy — but the merge is total and the tombstone problem takes a different, better-behaved form.
The general point: anti-entropy is the tax on leaderless replication (Leaderless Replication: Every Replica Accepts Writes). It is a reasonable tax, and it should be a deliberate purchase rather than a surprise.
Key points
- Divergence is the normal state of any system that acknowledges writes before every replica has them.
- Read repair covers only data that is read, which is a small fraction of most datasets and gives a false impression of health.
- Hinted handoff covers short outages and fails exactly when outages are long.
- Anti-entropy is the only mechanism that covers cold data and corruption, and the only one that makes replication factor mean anything over time.
- If a tombstone is garbage-collected before repair reaches a replica that missed the delete, the deleted data comes back — silently, weeks later.
- Repair duration is therefore a correctness deadline, not just a background cost.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • Choose a replica pair (or set) and a key range to compare.
- • Build a compact summary of each side’s contents over that range — in practice a Merkle Trees: Finding the Difference Without Reading the Data hash tree.
- • Exchange summaries and identify the sub-ranges that differ.
- • Stream the differing data between replicas.
- • Merge with a deterministic rule — usually last-write-wins on timestamp, or a version-vector merge (Version Vectors: Making the Conflict Visible).
- • Record progress so the next pass can skip what has already been reconciled, and repeat on a schedule that completes inside the tombstone grace period.
- • Repair never completes within the grace window and deletes begin to resurrect.
- • The merge rule loses a write — last-write-wins with skewed clocks silently discards the newer value (Clock Skew: The Gap You Cannot Measure From Inside, Last Write Wins Is Data Loss You Chose by Default).
- • Repair streams enormous volumes between replicas whose data is actually identical, because the summaries were not comparable.
- • Incremental repair marks data as repaired that was not, and the gap is never revisited.
- • The repair itself overloads the cluster and is aborted, leaving ranges permanently unreconciled.
- • A corrupted replica wins the merge and the corruption is propagated to the healthy replicas.
- • Zombie data: a deleted record reappears weeks after deletion. The operator sees a customer complaint, no error in any log, and no way to correlate it with anything except a repair schedule that was not being watched.
- • Repair never finishes: on a growing dataset a full pass takes longer than the grace period, and passes begin to overlap. The operator sees repair sessions running continuously and cluster load permanently elevated, with the correctness deadline quietly missed.
- • Repair-induced latency spike: starting a repair during peak traffic doubles p99 for its duration. The operator sees a latency incident with no traffic change and no deployment.
- • Silent divergence between reads: the same key returns different values depending on which replicas the coordinator happened to consult. The operator sees flapping values reported by users, and read repair papers over each instance without ever fixing the underlying gap.
- • Propagated corruption: a replica with a bad disk wins the merge on timestamp and the corrupt value is written to the healthy replicas. The operator sees data that is wrong on every copy, with the original good value gone.
- • Hint store overflow: during a long node outage the coordinators fill their hint storage and begin discarding. The operator sees a "hints dropped" counter that nobody alerts on, and a silent divergence that only repair will ever fix.
- • None in the request path — anti-entropy is entirely background, which is precisely why it is affordable and why it is forgotten.
- • The merge rule is the coordination, compressed into a function. Because every replica applies the same deterministic rule, no agreement protocol is needed to converge — the same insight that makes CRDTs: Deterministic Merge, Not Correct Merge work.
- • Scheduling needs cluster-level coordination to avoid every node repairing at once. Uncoordinated repair schedules are a common cause of periodic cluster-wide load spikes.
- • The merge rule is where correctness is decided, and last-write-wins quietly delegates that decision to clock accuracy. If two replicas hold genuinely concurrent writes, LWW discards one of them permanently — an application decision being made by a timestamp comparison.
- • Repair failing does not affect serving; it affects how divergent the replicas will be tomorrow. That delay between cause and symptom is why it is under-prioritised.
- • While replicas are divergent, quorum reads still return a value satisfying R+W>N if the write reached W replicas — divergence weakens durability and consistency for the keys it touches, not the whole system (Quorums: What R + W > N Does and Does Not Buy).
- • A replica that missed a long window is a durability risk disguised as a healthy node: it reports up, serves reads, and holds fewer keys than it should.
- • If repair is aborted midway, the ranges already compared stay reconciled. Progress is durable, which is what makes subrange repair the right unit.
- • Detect: track full-repair completion time per range and compare it against the tombstone grace period. That comparison is the alert.
- • Contain: rate-limit and stagger repair so it never competes with peak traffic; abort rather than let it deepen an incident.
- • Recover: after a long node outage, repair that node’s ranges explicitly before trusting it — do not wait for the schedule.
- • Reconcile: for suspected corruption, compare against a backup or an external source of truth rather than letting replicas vote, because a timestamp comparison cannot tell corrupt from current.
- • Verify: after repair, re-run the comparison and confirm the differing-range count is zero. A repair that reports success without a verification pass has proven nothing.
- • Time since the last completed full repair, per range. The single most important metric in this lesson and rarely present.
- • Full-repair duration trend against dataset growth — the leading indicator of missing the correctness deadline.
- • Hints stored, hints replayed, and hints *dropped*. The third is the one that matters and the one nobody alerts on.
- • Read-repair rate: how often reads find disagreement. A rising rate means divergence is growing faster than repair is fixing it.
- • Bytes streamed per repair versus bytes actually differing. A large gap means the comparison is producing false differences (Merkle Trees: Finding the Difference Without Reading the Data).
- • Count of ranges never repaired since a given node joined — the durability blind spot.
- • Any leaderless or multi-master replicated store, where it is not optional but structural.
- • After a node has been down long enough for hints to expire, which is the routine case for hardware replacement.
- • When cold data matters — archives, audit records, anything read rarely but required to be correct when it is.
- • For detecting silent corruption, which no other mechanism in the stack will find.
- • When run during peak traffic, where it competes directly with serving.
- • On very large datasets where a full pass cannot complete inside the grace window — the honest response is to shrink the ranges or lengthen the window, not to skip repair.
- • When the merge rule is wrong for the data: last-write-wins on concurrent updates silently loses writes, and repair spreads that loss to every replica.
- • When it masks a real problem: constant high divergence means writes are being dropped somewhere, and repair is treating the symptom.
- • Leader-based replication with an ordered log, where a lagging replica replays from an offset instead of being compared (Leader-Based Replication: Buying Order With a Single Writer).
- • Read repair alone, accepted knowingly for datasets that are entirely hot and where cold divergence genuinely cannot exist.
- • CRDT-valued data, where replicas merge by definition and divergence is not an error state (CRDTs: Deterministic Merge, Not Correct Merge).
- • Rebuilding a suspect replica from scratch instead of repairing it — often faster than a comparison when divergence is large.
- • Reconciling against an external source of truth (an event log, an upstream system) rather than against peers, which additionally catches the case where all replicas are wrong (Reconciliation Is a Component, Not a Cleanup Script, Source of Truth: The Question Every Inconsistency Incident Is Really Asking).
What repairs the data nobody reads
What people believe, and what is true
Read repair is enough.
It repairs only what is read. Most keys in most datasets are read rarely or never, so read repair leaves the majority of divergence untouched while making the system look healthy.
Repair is optional maintenance.
In a system with tombstone expiry, skipping repair for longer than the grace period causes deleted data to return. It is a correctness deadline wearing the costume of a background job.
If replication factor is 3, there are three copies.
There are three replicas that were *supposed* to receive every write. Without repair, the actual number of copies of any given key drifts downward over time.
Anti-entropy fixes conflicts.
It makes replicas agree. Whether they agree on the *right* value depends entirely on the merge rule — last-write-wins converges by discarding a write, and calls that success.
Hinted handoff means a node coming back is fully caught up.
Only if the outage was shorter than the hint TTL and no hint store filled up. Otherwise the node returns permanently missing data and reports itself healthy.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Replicas drift apart silently. Anti-entropy compares them in the background and repairs the differences — the only mechanism that covers data nobody is reading.
Practical
Run repair continuously at a low rate in small subranges, and alert on time-since-last-complete-repair per range rather than on repair job success. Alert on hints dropped. Both metrics are usually absent and both predict silent data problems.
Advanced
Deletes need tombstones because comparison is symmetric — "present here, absent there" cannot distinguish an un-propagated insert from an un-propagated delete. Tombstones must expire, which turns full-repair duration into a hard correctness deadline: exceed it and deleted data resurrects.
Internals
The merge rule decides correctness and is usually chosen by default rather than deliberately. Last-write-wins delegates conflict resolution to clock comparison, so a replica with a fast clock wins every conflict and its data is propagated by repair to all the others. Where concurrent updates are genuinely possible, use version vectors so repair can detect concurrency instead of silently discarding one side (Version Vectors: Making the Conflict Visible, Only the Application Knows What the Merge Means).
Apply it
- 🔧 Find your system’s time-since-last-complete-repair per range. If the metric does not exist, that is the finding.
- 🔧 Take down a replica for longer than the hint TTL, bring it back, and measure how many keys it is missing before repair runs.
- ⚡ Users report that items they deleted last month have reappeared. Nothing was restored from backup and no code changed. Explain the mechanism precisely and name the metric that would have predicted it.
- ⚡ Read-repair rate has tripled over a month with no change in traffic. What does that tell you and what would you check?
- 💬 Why is read repair not sufficient on its own?
- 💬 Explain why a deleted row can come back in a leaderless replicated store, and what bounds the risk.
- 💬 Your full repair now takes 12 days and the tombstone grace period is 10. What are your options?