Merkle Trees, Range Digests, and Finding Divergence Without Reading Everything

Two replicas hold the same key range and disagree about some of it. The direct way to find out which parts differ is to read every key from both and compare, which costs two full scans of the range and transfers a volume of data proportional to the range’s size regardless of how little of it differs. A digest tree changes the cost from “proportional to the data” to “proportional to the differences”, by summarising sub-ranges into hashes and comparing the summaries first.

The tree over a key range

Partition the key range into fixed-size leaf intervals. Hash each interval’s contents, key and value for every key in the interval, in a defined order, and combine the hashes pairwise upward: a parent’s hash is the hash of its two children’s hashes concatenated. The root hash summarises the entire range in a fixed number of bytes. Two replicas that agree on the root agree on every leaf, with the collision resistance of the hash function as the only assumption.

Comparison descends. The two roots are compared; if equal, the ranges agree and the comparison stops, having transferred 32 bytes for a range of any size. If unequal, the two children’s hashes are compared, then the differing child’s children, and so on until the differing leaves are identified. The number of hash comparisons is proportional to the number of differing leaves times the depth of the tree, and the number of leaf comparisons is exactly the number of differing leaves. A range with one differing key in a million costs a handful of hash comparisons rather than a scan of a million keys.

import hashlib

def leaf_hash(pairs):
    h = hashlib.sha256()
    for k, v in pairs:                      # order must be identical on both replicas
        h.update(k)
        h.update(b"\x00")                   # separator: prevents (ab, c) colliding with (a, bc)
        h.update(v)
        h.update(b"\x00")
    return h.digest()

def node_hash(left, right):
    return hashlib.sha256(left + right).digest()

def build(pairs, fanout=1024):
    """Return the levels of a digest tree, leaves first."""
    leaves = [leaf_hash(pairs[i:i + fanout]) for i in range(0, len(pairs), fanout)]
    levels = [leaves]
    while len(levels[-1]) > 1:
        cur = levels[-1]
        nxt = [node_hash(cur[i], cur[i + 1]) for i in range(0, len(cur) - 1, 2)]
        if len(cur) % 2:                       # odd child is promoted, not dropped
            nxt.append(cur[-1])
        levels.append(nxt)
    return levels

The separator byte in the leaf hash is not decoration. Without a delimiter, the concatenation of key ab and value c is the same byte string as key a and value bc, so two different leaf contents produce the same digest. Length-prefixing or a separator that cannot appear in either field removes the ambiguity. This is the same class of error as the length-extension problem in naive hash(secret || message) constructions, and it appears in real digest implementations often enough to be worth stating.

The alignment requirement

The comparison only works if both replicas partition the range identically. If one uses 1024-key leaves and the other 512, the trees have different shapes and no node’s hash corresponds to any other node’s hash; the comparison degenerates to comparing the roots and then nothing. The partition must be a deterministic function of the key space, not of the data: boundaries at fixed token values, or at fixed key prefixes, or at ranges assigned by the placement function.

This is why digest trees are usually built over the same ranges the placement scheme assigns. In a ring-based store the natural leaf is the token range a node owns, and the tree is built over that range in a canonical order. In a store with fixed partitions the leaf is the partition. The tree’s shape becomes part of the cluster’s metadata, and a change to the partition scheme invalidates every digest, which is one reason partition counts are chosen once and kept.

Ordering within a leaf is the second alignment requirement. Two replicas holding the same key-value pairs in different iteration orders produce different leaf hashes. The fix is a canonical order, by key bytes usually, or a commutative combination such as XOR of per-key hashes, which makes the leaf digest independent of order. XOR has the drawback that a key present twice cancels; a sum modulo a large integer does not, and either way the digest must include a count so that duplicate and missing keys are distinguishable.

Choosing the leaf size

Leaf size sets the resolution of the comparison, and it trades three quantities against each other. Smaller leaves localise divergence more precisely, so the repair reads less; they also make the tree larger, which costs memory and update work, and they increase the number of hash comparisons needed to descend. A leaf of a thousand keys with a fanout of a thousand gives a tree of roughly three levels for a million keys, which is small enough to keep in memory and coarse enough that a single repair reads at most a thousand keys.

The degenerate case is worth naming. A leaf of one key reduces the tree to a sorted list of per-key hashes; comparison is a merge of two sorted lists, which is exactly the “read everything and compare” approach with a hash in front of it, and the tree structure has bought nothing. A single leaf covering the whole range reduces the tree to one root hash, which finds that divergence exists but not where, so the repair still scans everything. Useful leaf sizes sit between, chosen so that the expected divergence per leaf is well under one key.

What the tree costs under writes

A digest tree is cheap to build once and expensive to maintain. A single key update changes one leaf, which changes every ancestor up to the root: with a fanout of 1024 and a million keys, that is two internal nodes for a 1024-way tree, or about 20 for a binary tree. Recomputing an internal node requires the hashes of its children, which are in memory or on disk; the update cost is bounded by the tree’s depth, so a 1024-way tree is cheaper to maintain than a binary one for the same number of leaves.

The real cost is not the arithmetic but the invalidation. An incremental tree that is updated on every write is correct but adds a hash computation and an update to the write path. A tree rebuilt on demand is cheaper on the write path but requires a full scan when anti-entropy runs, which defeats the purpose for large ranges. Practical stores compromise: they maintain the tree lazily, invalidating subtrees on write and recomputing them when a comparison reaches them, so the cost is paid only for the parts of the range that are actually compared.

There is a third cost that is easy to overlook: the tree is only as fresh as its last update, so a comparison between two trees reports divergence as of the time each was built. A key written after replica A’s tree was built but before replica B’s is missing from A’s tree and present in B’s, so the comparison finds a difference that is a timing artefact rather than a real inconsistency. Repairing it is harmless, since the values converge, but the repair work is wasted, and a range that is written continuously can produce a stream of such artefacts. The mitigation is to build the two trees from comparable snapshots, or to accept the waste and let the next pass converge.

Failure modes

The first is a hash collision. A 256-bit digest makes a random collision astronomically unlikely, but the threat model for a digest tree is not an adversary, it is a bug: two different leaf contents that the digest function maps to the same value because of a delimiter bug, a truncation, or a non-canonical encoding. The digest is only as good as the encoding it hashes, and the encoding is where the bugs live.

The second is a false agreement caused by a stale tree. If replica A’s tree was built before a write and replica B’s after, the roots differ and the comparison proceeds; if both were built before the write, the roots agree and the write’s divergence is invisible. This is not a defect of the tree, it is a statement about when the tree is valid, and a repair pass that does not record the tree’s build point cannot distinguish the two cases.

The third is the boundary between leaves. A key exactly at a leaf boundary belongs to one leaf by convention, and the convention must be identical on both sides. Off-by-one at boundaries produces a comparison that finds a difference in the wrong leaf, then repairs the wrong key, and the actual difference persists. The symptom is a repair pass that reports success and a subsequent pass that reports the same divergence.

Relation to the rest of the repair path

Digest comparison identifies where divergence is; it does not fix it. The repair that follows reads the differing keys from both sides, orders them by version, and writes the winner to the loser, which is the same read-repair mechanism applied in bulk. For erasure-coded data the comparison is over fragments rather than replicas, and a differing leaf means one or more fragments need reconstruction from the surviving fragments rather than a simple copy, which changes the cost of the repair phase but not the cost of the comparison phase.

The comparison phase’s cost is what makes anti-entropy schedulable at all. Without a digest, a repair pass over a terabyte range transfers a terabyte in each direction; with one, it transfers a few kilobytes of hashes plus the divergent data. The saving is the ratio of range size to divergence, which for a healthy cluster is enormous, and that ratio is the entire justification for maintaining a tree whose updates cost more than the writes they shadow.