Merkle Tree

A Merkle tree is a hierarchy of hashes. Each leaf hashes a block of data, each internal node hashes its children, and a single root hash summarizes everything beneath it.

The property that makes it useful is comparison by descent. Two parties exchange root hashes; if they match, the data underneath is identical and nothing more needs to be sent. If they differ, each compares the children, descends only into subtrees that disagree, and arrives at the specific ranges that differ. The work is proportional to the amount of divergence rather than to the size of the dataset.

That is exactly the requirement in a replicated store that allows replicas to diverge temporarily. Cassandra’s repair has replicas compute these hierarchical hash trees over their data and compare them to identify which ranges differ, so that only the mismatched ranges are transferred rather than the whole dataset.

The generalizable idea is worth keeping separate from the implementation. Where two datasets are expected to agree and are too large to compare row by row, a hierarchy of checksums turns an expensive full comparison into a cheap check plus a targeted one. That pattern applies to any reconciliation between systems, not only to database repair.

One limit to state clearly: a matching root hash is evidence that the compared blocks are identical as hashed. It says nothing about data outside the tree’s range, and it depends on both sides having built the tree over the same partitioning — a mismatch in how the ranges were divided produces differences that are not real.

Why replicas need this at all, and what else a reconciliation should check, is worked through in Replication, Consistency, and Time.