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.

Two parties with compatible trees compare root hashes and descend into subtrees that disagree to locate differing ranges. Matching roots are strong evidence of equal inputs when the hash resists collisions and both sides use the same range boundaries, encoding, and tree construction. This is not a mathematical proof that arbitrary inputs are identical. Comparing prepared trees can avoid transferring matching data; the amount of work depends on the tree shape and the distribution of differences.

Cassandra uses this approach during replica repair. A full repair first reads and hashes the participating data to build trees, even if the replicas turn out to match. Tree construction, tree comparison, and transfer of differing ranges are separate costs. A system that maintains hashes incrementally can reuse earlier work, but that requires a maintenance mechanism; a Merkle tree does not remove the initial scan by itself.

The pattern also helps reconcile datasets across systems: compare compatible summaries, then inspect or transfer the differing ranges. Budget the cost of producing and maintaining those summaries as well as comparing them. A small difference can save network transfer without making the entire reconciliation cheap.

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.

References

• Apache Cassandra, Dynamo architecture: data versioning and replica synchronization