Merkle Tree Anti-Entropy: Finding Divergence Without Comparing Everything

Two replicas hold overlapping key ranges and have been accepting writes independently. Comparing them key by key requires transferring one side’s dataset, which for a large store is the whole dataset per repair cycle. The alternative is to compare summaries: hash each range of keys, compare the range hashes, and descend only into ranges whose hashes disagree. That is a Merkle tree, and the reason it works is that a hash mismatch localises the divergence to a subtree instead of forcing a scan.

The tree over the key space

Partition the key space into ranges. In a consistent-hashing ring the ranges are the token intervals between partition boundaries; in a range-partitioned store they are the partitions themselves. Each range gets a leaf whose value is a hash over the records it contains, computed over key, value, and version so that a differing version at the same key produces a differing leaf.

Internal nodes hash the concatenation of their children’s hashes. The root hash therefore depends on every record in the dataset, and two replicas with identical data have identical roots. Two replicas with any difference have different roots, with overwhelming probability.

import hashlib

def build(leaves, fanout=16):
    """leaves: list of (range_start, digest_bytes), sorted by range."""
    level = [digest for _, digest in leaves]
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level), fanout):
            h = hashlib.sha256()
            for child in level[i:i + fanout]:
                h.update(child)
            nxt.append(h.digest())
        level = nxt
    return level[0]

With a fan-out of 16 and a million leaves, the tree is about five levels deep. Comparing roots costs one hash per side. Comparing level by level costs at most fanout hashes per differing node.

The descent

Repair proceeds by exchanging the root hashes. If they match, the replicas agree and the process stops after a single exchange. If they differ, each side sends the hashes of its root’s children, and the pair identifies which child subtrees differ. The walk continues into those subtrees only.

The cost is proportional to the number of differing leaves times the tree depth, not to the dataset size. Two replicas that differ in k records out of n exchange on the order of k · log_fanout(n) hashes instead of n records. For a large store with a small divergence — the normal case after a brief node outage — the saving is enormous, and it is the entire justification for maintaining the tree.

The degenerate case is a replica that is missing half the dataset or has diverged everywhere. Then every subtree differs, the walk visits every node, and the cost approaches a full comparison plus the tree overhead. Merkle trees optimise the common case and do nothing for the catastrophic one, which is why a node that has been down for a long time is usually bootstrapped from a snapshot rather than repaired by this mechanism.

The unit of comparison must match the unit of repair

A leaf covers a range. If the range holds many keys, the leaf mismatch says “something in here differs” and the repair must then exchange the range’s contents or its per-key hashes. The choice of leaf granularity is therefore a trade:

Leaf size	Tree size	Work per differing leaf	Best for
One key per leaf	large; one hash per key	one record	sparse divergence, small records
Many keys per leaf	small	whole range or a sub-scan	dense records, few differences
Fixed byte budget	bounded	variable	heterogeneous record sizes

Dynamo’s design used a tree per replica over the key ranges that replica hosts, with each leaf covering a range rather than a single key, and the granularity chosen so that the tree fits comfortably in memory. Cassandra’s repair similarly builds trees per table and per token range, with the range split controlled by configuration because the split determines both the tree’s memory footprint and how much data a single mismatch forces through.

The mismatch is not a correctness problem, only a cost one. But a leaf granularity that is too coarse converts a Merkle walk into a series of range transfers, and a granularity that is too fine makes the tree itself the dominant memory consumer.

Hash stability is the hidden requirement

The tree is only useful if both replicas compute the same hash for the same data. That requires a canonical serialisation: the same field order, the same encoding for nulls, the same treatment of absent columns, and the same hash over the version metadata. A mismatch in serialisation produces different hashes for identical logical data, which makes every leaf differ and turns the walk into a full comparison while appearing to be a genuine divergence.

The same hazard applies to the version metadata. If one replica stores a version vector in a different key order or with zero entries elided and another does not, the leaf hashes disagree even though the causal information is identical. Repair then overwrites data that was already correct, and the process repeats at the next cycle. This is a real class of bug in systems that hash serialised records without pinning the encoding, and it presents as “repair never converges”.

The hash function also has to be collision-resistant enough that an adversary cannot construct two different records with the same leaf hash. SHA-256 is the conservative choice; a 128-bit hash is adequate against accident but not against a deliberate collision.

Maintaining the tree against write churn

A tree over a live dataset must be updated as writes arrive. Recomputing the root requires hashing every leaf, which is O(n) per write and unacceptable.

The standard solution is to compute the tree lazily over an immutable snapshot of the data, or to maintain per-leaf dirty flags and recompute only the path from a modified leaf to the root. The path recomputation costs log_fanout(n) hashes per write, which is small. The difficulty is that the tree must be consistent with a single point in the data’s history. If a write lands while the tree is being built, the root does not correspond to any state the replica ever had, and the comparison with another replica is meaningless.

Practical implementations either build the tree over an immutable file set — each flush produces a file, and the tree is built over the files present at a given generation — or hold a read snapshot for the duration of the build. The first approach makes the tree cheap to rebuild and ties its validity to the file generation; the second requires the storage engine to support consistent snapshots, which not every engine does. The cost of a rebuild is proportional to the data hashed, so the interval between rebuilds determines the amortised overhead.

There is a second-order effect: churn invalidates the tree’s value. If a replica receives a steady stream of writes, its tree is stale as soon as it is built, and a repair run against it compares against a moving target. Systems handle this by repairing against a snapshot at a known point and replaying the log from that point afterwards, which is the same structure used for bootstrapping a new replica.

Where the walk is not enough

The Merkle walk finds differing ranges. It does not decide what the correct value is. If both sides have a value for a key, the repair must compare versions and choose; if the versions are concurrent, the repair must not overwrite either. A repair process that blindly copies from one side to the other destroys the sibling that a merge function needed to see. The version comparison rules from version vectors and conflict detection apply here exactly as they do on the read path.

Deletes create a parallel problem. A key present on one side and absent on the other is either a missed delete or a missed insert, and only a tombstone distinguishes them. Without tombstones, repair must guess, and guessing wrong resurrects deleted data. This is why tombstone retention must exceed the repair interval, as noted in read repair and hinted handoff.

Finally, the walk assumes both replicas can enumerate the same range boundaries. When the ring is being resized or partitions are migrating, the two sides may cover different ranges, and a leaf-by-leaf comparison is not defined. Repair during migration has to be suspended or restricted to ranges both sides own, which is why topology changes and anti-entropy are usually scheduled against each other rather than run concurrently. Placement decisions that keep repair traffic local are covered in failure-domain placement.