What is the role of Merkle trees in Cassandra's repair process?

Comparing every row between two replicas byte-by-byte to find differences would be prohibitively slow at scale. Merkle trees let Cassandra compare huge token ranges efficiently by comparing hashes instead of raw data.

1. For a given token range, a replica divides the data into smaller sub-ranges and computes a hash for each one.
2. Those hashes become the leaves of a binary tree; each parent node's hash is computed from its children, all the way up to a single root hash.
3. Two replicas exchange their tree's root hash first — if the roots match, that whole range is confirmed identical with a single comparison.
4. If roots differ, the comparison recurses down the tree, only following branches whose hashes disagree, until it isolates the specific sub-ranges that actually differ.

Only the data underlying the mismatched leaves gets streamed between replicas, not the whole range. This is what makes nodetool repair scale reasonably well even on very large datasets: the cost of the comparison itself is proportional to the size of the divergence, not the size of the whole dataset.