How it works
Start with replicated data: key K belongs on replicas A, B, and C. If C is unavailable, a write may succeed on A and B while C keeps an older value. Each stored value needs version metadata so replicas can distinguish an older value from a newer one or detect concurrent updates.
Read repair discovers divergence while serving a read. A coordinator compares values or digests from multiple replicas, fetches full values when necessary, applies the conflict-resolution rule, and sends the resolved state to stale replicas. For example, if A has version 8 and C has version 7, C can be updated to version 8. Repair may happen before the response or asynchronously, depending on the design.
Background anti-entropy compares replica state independently of user reads. Replicas check corresponding key ranges, identify differences, and exchange missing or conflicting data. Merkle trees can reduce comparison traffic: compare range hashes, descend into mismatching branches, and transfer only the affected records. Building and maintaining those trees still costs resources.
Hinted handoff records a missed write for an unavailable replica. A coordinator or temporary holder stores the mutation and its intended destination, then retries delivery when that replica returns. Hints need bounded retention, storage limits, and retry control; if hints expire or their holder fails, background repair must still recover the missing data from surviving replicas.
All repair paths must use compatible version and conflict-resolution rules. They cannot infer user intent from two concurrent values: the system needs a policy such as preserving siblings, merging a CRDT, or choosing a timestamp winner. Deletions also need versioned markers, called tombstones, so an old live value is not mistaken for missing data and copied back.
A worked example
Repairing a replica after a two-hour outage
A key-value store keeps three replicas per key and acknowledges writes after two replicas persist them. Replica C is offline for two hours. During that time, A and B accept version 12 of a profile, and A retains a hint for C. When C returns, replaying the hint brings its profile copy forward. A read comparing A and C can also detect and repair the difference. Separately, a background range comparison finds a cold key that C missed and that nobody has read. If that key was deleted, repair must send its tombstone rather than copy C's old value back. The team rate-limits recovery traffic and retains tombstones until its repair or rebuild policy makes their removal safe.
Trade-offs to say out loud
- Read latency versus repair completion
- Blocking read repair adds work to the request path, while asynchronous repair can leave stale replicas available for subsequent reads.
- Hot-data repair versus full coverage
- Read repair follows access patterns, so background anti-entropy is needed to repair cold keys as well.
- Recovery speed versus foreground capacity
- Repair consumes disk I/O, CPU, and network bandwidth, so aggressive recovery can increase application latency.
- Efficient comparisons versus bookkeeping
- Merkle trees reduce data comparison traffic but require consistent range boundaries, compatible hashing, and tree construction or maintenance.
- Fast outage recovery versus bounded hint storage
- Hinted handoff efficiently covers short outages, but long outages can exhaust hint capacity or outlast retention.
- Deletion safety versus retained metadata
- Tombstones consume space, but removing them before stale replicas are repaired or rebuilt can resurrect deleted values.
When to reach for it
- You choose leaderless or asynchronously replicated storage and must explain how replicas recover from missed writes.
- The service accepts writes during a replica outage or network partition and needs a concrete convergence plan afterward.
- Cold data must remain consistent even when it receives no reads for weeks.
- The interviewer asks what happens when a node returns after a long outage, especially after deletions.
- Offline clients or peers reconcile versioned state and need both conflict detection and a way to discover missed changes.
How to bring it up in the interview
- Start with one missed-write scenario and trace it through acknowledgment, replica recovery, and repair; do not stop at saying the database is eventually consistent.
- Separate the jobs: hinted handoff retries known missed writes, read repair fixes observed divergence, and background anti-entropy checks the wider dataset.
- Name the conflict policy separately from the repair mechanism; expect questions about concurrent writes and clock skew if you propose last-write-wins.
- Explain tombstone safety using the maximum supported offline period and actual repair coverage, not just a scheduled repair interval; a replica outside that safety window may need rebuilding.
- Describe repair throttling and metrics such as oldest unrepaired range, hint backlog, failed repair sessions, and repair bandwidth; expect a follow-up about recovery competing with live traffic.
Common mistakes
- Claiming read repair guarantees convergence for keys that are never read, or assuming every read compares all replicas.
- Treating hinted handoff as a permanent delivery guarantee despite hint expiration, storage limits, and holder failures.
- Assuming a Merkle tree resolves concurrent writes; it detects differences, while a separate policy decides how to reconcile them.
- Deleting tombstones on a timer without proving that stale replicas can no longer reintroduce old values.
- Claiming repair or overlapping read/write quorums alone makes an asynchronously replicated store linearizable.
Where it comes up
Interview questions where read repair and anti-entropy is part of a strong answer, and why.
- Design a distributed key-value storeReplica convergence after available writes, repair scheduling, and preventing deleted data from returning are core parts of the design.
- Design a distributed cacheReplica failover requires deciding how stale copies recover without reviving expired values or treating the cache as durable storage.
- Design Dropbox or Google DriveReconnecting clients must discover missed changes and reconcile versioned files and deletions after working offline.
Questions people ask
What is the difference between read repair and anti-entropy?
Read repair is triggered by reads that discover inconsistent replica state. Background anti-entropy checks replica state without waiting for user reads, so it can repair cold data too. In a broader sense, read repair is also an anti-entropy technique, but interview discussions usually distinguish read-triggered repair from background repair.
What is hinted handoff, and does it replace repair?
Hinted handoff temporarily stores a missed mutation for its intended replica and retries delivery later. It speeds recovery from short outages but cannot cover every divergence: hints can expire, be lost with their holder, or never be recorded. Background repair provides coverage beyond those retained hints.
Do read repair and anti-entropy guarantee eventual consistency?
They support convergence when communication resumes, repair reaches all relevant data, and replicas use compatible conflict-resolution rules. Permanent partitions, lost copies of acknowledged data, or unsafe tombstone removal can prevent correct convergence. They also do not guarantee that an individual read sees the latest write.