The Problem of Drift
Even in a healthy cluster with no partitions, data can drift out of sync over time. A node might have been briefly slow during a write, causing it to miss an update. A disk might have silently corrupted a value. Over weeks and months, small inconsistencies accumulate. Distributed databases use two complementary mechanisms to detect and fix this drift: Read Repair and Anti-Entropy Repair.
Read Repair: Fix It When You See It
When a read operation consults multiple nodes (R > 1), the coordinator compares the responses. If Node A returns X=5 with timestamp T=100 and Node B returns X=3 with timestamp T=80, the coordinator knows Node B is stale. It returns X=5 to the client (the most recent value) and simultaneously sends a background write to Node B to update it to X=5.
This is Read Repair — the act of healing inconsistencies opportunistically during normal read operations. It is free in the sense that you are already doing the reads; the repair is a side effect.
The limitation: Read Repair only fixes data that is actually read. Data that is never queried can remain inconsistent indefinitely.
Anti-Entropy Repair: Systematic Reconciliation
For data that is rarely or never read, databases use Anti-Entropy Repair — a scheduled background process that systematically compares data across all replicas and synchronizes any differences.
The naive approach (compare every row on every node) would be prohibitively expensive. Instead, Cassandra and similar systems use Merkle Trees — a cryptographic data structure where each leaf node is a hash of a data partition, and each parent node is a hash of its children. To compare two nodes, you only need to compare the root hashes. If they match, the entire subtree is identical. If they differ, you traverse the tree to find exactly which partitions differ, minimizing the data transferred.
Merkle Tree comparison between Node A and Node B:
[Root Hash]
/ \
[Hash AB] [Hash CD] ← Hashes match? Skip this subtree.
/ \ / \
[A] [B] [C] [D] ← Only compare leaves where parent hashes differ.
In production, anti-entropy repair should be run regularly — Cassandra's documentation recommends running nodetool repair on every node at least once per gc_grace_seconds (default: 10 days) to prevent deleted data (tombstones) from reappearing.
A common interview question is: "How does Cassandra handle deleted data in a distributed system?" The answer involves tombstones — special markers written to indicate a deletion — and gc_grace_seconds, the window during which tombstones are preserved. If a node is offline during a delete and comes back after gc_grace_seconds has elapsed without a repair, the tombstone is garbage-collected and the deleted row can reappear on that node. This is why regular anti-entropy repair is not optional in production Cassandra clusters.