Concepts
Merkle trees for anti-entropy
Intuition
Imagine two people each keeping a copy of the same huge filing cabinet, and you want to check if the copies still match. You could compare every single page one by one, which takes forever — or you could first compare just a one-page summary of the whole cabinet. If the summaries match, you're done: everything underneath must match too. If they don't, you only open the drawers where the summaries disagree, and keep zooming in until you find the exact pages that differ. That shortcut — compare a summary first, only dig deeper where it disagrees — is the whole idea.
How it works
A Merkle tree turns that summary trick into a hash tree over a replica's key range: each leaf is the hash of a small slice of keys, and each parent node is the hash of its children's hashes, all the way up to a single root hash that summarizes the entire dataset a replica holds. Two replicas can compare just their root hashes first — if they match, the ranges are provably identical and no more work is needed. If the roots differ, each side recurses one level down and compares the child hashes, discarding any subtree whose hashes already match and only descending further into the branches that disagree, until the actual divergent keys are isolated. This is what Dynamo runs as its background anti-entropy process between replica pairs, separate from read repair, specifically to catch divergence in keys that aren't read often enough to self-heal through normal traffic (divergence that sloppy quorums and hinted handoff make possible in the first place). The key property is that the cost of detecting divergence — bandwidth and comparisons — scales with how much the replicas actually differ, not with the total size of the dataset, which is what makes it practical to run continuously in the background across a large cluster.
In practice
This is the standard anti-entropy technique in Dynamo-style eventually-consistent stores: it's how a replica repairs data nobody has read in a while, instead of relying purely on read-time repair. You'd reach for it whenever you have many replicas of large datasets that can silently drift apart (due to hinted handoff, temporary partitions, or failures) and comparing full datasets key-by-key would be too expensive to run regularly — Cassandra's repair tooling, descended from the same lineage, uses the same hash-tree comparison for exactly this reason.
Use it in a design
Practice the cases that rely on this concept in the System Design school.