Read Repair, Hinted Handoff and Tombstones
Eventually consistent databases use repair mechanisms to converge replicas; repair correctness depends on versioning, tombstone retention and anti-entropy.
Read Repair, Hinted Handoff and Tombstones
Eventually consistent databases use repair mechanisms to converge replicas; repair correctness depends on versioning, tombstone retention and anti-entropy. Read repair compares versions observed during a read and may send newer state to stale replicas. Hinted handoff stores a temporary record for an unavailable replica and replays it when the node returns. Anti-entropy compares ranges, often with Merkle trees. Tombstones record deletions so stale replicas do not resurrect removed values.
Mechanism and worked example
A replica is unavailable while a write is accepted by the configured consistency policy. Another node retains a hint for the missing replica. When it returns, the hint is replayed; periodic anti-entropy checks remaining divergence. A deletion tombstone must remain long enough to outlive the maximum relevant replica outage and repair horizon.
| Mechanism | Purpose | Limit |
|---|---|---|
| Read repair | Fix divergence observed on read | Cold keys may never be repaired |
| Hinted handoff | Replay writes for temporarily absent replica | Hints expire and consume storage |
| Anti-entropy | Compare full ranges | Background bandwidth/CPU cost |
| Tombstone | Remember deletion | Too-early purge can resurrect stale data |
Failure modes and operations
Expired tombstones can allow old values to reappear. Long outages can exceed hint retention. Read repair only touches data that gets read. Clock-based last-write-wins can discard a logically newer value if clocks are skewed. Repair traffic can saturate disks and networks.
Trade-offs and design boundary
Read repair improves convergence on hot data but is not a complete repair strategy. Hinted handoff is temporary and bounded. Anti-entropy provides broader coverage but consumes background capacity. Tombstone retention trades storage for deletion safety.
Interview transfer exercise
Explain how a deleted user record can reappear after a replica outage. Include tombstone retention, hint expiry, anti-entropy and the required repair horizon.
Read the diagram
Replica misses an update during outage → Hint retains bounded replay record → Returning replica catches up → Merkle anti-entropy repairs remaining divergence