Anti-Entropy

Hinted handoff handles writes when a node is briefly down. Read repair fixes stale data when someone reads it. But what about the data nobody reads? What about the replica that was down for three days and missed thousands of writes that will never be read again?

That's where anti-entropy comes in. It's the background process that periodically compares every piece of data across replicas, finds differences, and repairs them. If hinted handoff is the first responder and read repair is the opportunistic fixer, anti-entropy is the deep cleaning crew that comes through on weekends and catches everything the others missed.

The challenge is efficiency. You might have billions of keys across your replicas. Comparing them one by one would take forever and consume massive bandwidth. This is where Merkle trees (hash trees) come in, they let two nodes compare their entire datasets by exchanging just a handful of hashes. If the root hashes match, the datasets are identical. If they differ, the nodes can drill down the tree to find exactly which keys are out of sync, transferring only the data that's actually different.

Cassandra calls this "nodetool repair." DynamoDB runs it automatically in the background. It's the mechanism that guarantees eventually consistent systems actually converge, without it, stale data could persist indefinitely.

A Merkle tree is a binary tree where every leaf node contains the hash of a data block, and every non-leaf node contains the hash of its children's hashes. The root hash is a fingerprint of the entire dataset.

To compare two replicas:

1. Exchange root hashes. If they match, the replicas are identical. Done.
2. If root hashes differ, exchange the hashes of the root's children (left and right).
3. Whichever child hashes differ, drill down into those subtrees.
4. Continue until you reach the leaf nodes that differ, those are the specific keys that need repair.

For a dataset with 1 billion keys and a tree depth of 30, you might exchange only 60-100 hashes to find 5 differing keys. That's the power of Merkle trees, logarithmic comparison complexity.

Cassandra's approach: Each node builds a Merkle tree per token range per table. During repair, nodes exchange trees for their shared token ranges. Only the keys identified as different are streamed across the network.