Anti-Entropy Repair: Merkle Trees, Read Repair, and the Cost of Finding Divergence

A write accepted under a sloppy quorum lands on nodes that were not the preferred replicas. A node that was down during a partition misses every write in that interval. A repair that runs after the fact has to answer a hard question before it can fix anything: which of the two replicas is missing what? Comparing the full contents of two replicas is proportional to the size of the data, which for a large range is prohibitive to do regularly. The mechanism that makes repair affordable is a hash tree over the keys, because it turns “compare everything” into “compare a summary, then descend only where the summaries disagree”.

The comparison problem

Take two replicas of a range holding n keys. The naive repair reads every key from both and compares. The cost is O(n) reads per pair per run, and with a replication factor of three that is three pairwise comparisons, or a star topology with one replica as the reference. On a range with millions of keys, and with a repair cycle that must run often enough to bound the divergence window, the cost dominates the cluster’s read capacity.

The requirement is a summary that is cheap to compare and that changes when the underlying data changes. A single hash over all keys and values is cheap to compare but useless for locating the divergence: two replicas with one differing key out of a million produce completely different digests, and the digest says nothing about where.

The hierarchical structure fixes this. Build a tree whose leaves are the hashes of individual keys (or of small key blocks), and whose internal nodes are the hash of the concatenation of their children. Two replicas compare their root hashes. If they match, the subtrees are identical with high probability and nothing needs to be read. If they differ, compare the children. Only the subtrees whose hashes differ are descended, so a single differing key out of n requires reading one path of length log₂ n plus the differing leaves, rather than n.

import hashlib

def leaf(k, v):
    h = hashlib.sha256()
    h.update(k)
    h.update(b"\x00")          # separator: k||v must not collide with (k+1)||v'
    h.update(v)
    return h.digest()

def build(items):
    # items: sorted list of (key, value); returns root and per-level hashes
    level = [leaf(k, v) for k, v in items]
    levels = [level]
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level), 2):
            pair = level[i:i + 2]
            nxt.append(hashlib.sha256(b"".join(pair)).digest())
        levels.append(nxt)
        level = nxt
    return levels

Two details matter for correctness. The separator byte prevents a key-value pair from being reinterpreted as a different pair whose concatenation happens to match, which is the same length-extension-adjacent reasoning that motivates unambiguous encodings in hash-based structures generally. And the leaf set must be ordered identically on both replicas, because a tree over the same keys in a different order has a different root; the ordering is by key bytes, and it must be the same ordering the range’s storage uses.

The tree is a summary of a snapshot. If the replica’s contents change while the tree is being built, the tree describes a state that never existed. Repair therefore builds the tree over a consistent snapshot — a memtable plus a set of immutable files, or a database snapshot — and the repair protocol must know which snapshot each tree describes. A tree built at time T₁ compared against a tree built at T₂ reports differences that include every write between them, which is not a defect but does mean the repair cannot conclude that a key is corrupt; only that the replicas differ at those points.

Merkle trees do not say which side is right

The descent identifies the differing leaves. It does not identify the correct value, because both replicas are equally authoritative from the tree’s point of view. The tree is symmetric.

Resolution needs a third input, and the choices are the same ones that appear in conflict resolution generally.

Version comparison. Each value carries a version, and the higher version wins. This is correct when versions are assigned by a single writer or by a total order, and it silently discards data when two writers produced the same version. The per-key counter and the vector clock discussed in quorum intersection are the two schemes, with the same trade between size and expressiveness.

Timestamp comparison. Last write wins by wall clock. It is cheap, needs no per-key metadata beyond a timestamp, and it is wrong whenever clocks disagree — which is always, by some amount. A replica whose clock runs fast wins every conflict for the period of the skew, and the writes it overwrites are lost.

Application-defined merge. The differing values are returned to the application, which decides. This is the only option that can preserve both sides when the conflict is genuine, and it requires the application to know that a merge is possible, which most data models do not.

The choice is per-dataset, and it is a data-modelling decision rather than a storage one. A counter can be merged by summing per-replica counts; a set can be merged by union; a register cannot be merged without discarding one side unless the application supplies a rule.

Read repair closes the fast path, not the slow one

Merkle-tree repair is expensive per run and therefore runs infrequently, on the order of hours to days. Between runs, a read that contacts R replicas can notice divergence for free: the responses disagree, and the coordinator can push the winning value to the replicas that returned the stale one. This is read repair, and it costs one extra write per detected divergence.

Read repair’s coverage is exactly the set of keys that were read. A key that is never read is never repaired by this path, which is why the background tree comparison exists: it covers the cold keys. The two mechanisms are complementary and neither replaces the other.

There is a subtlety in when the repair write happens. If the coordinator waits for all R responses and then writes back before returning to the client, the read latency includes the repair write, which is a cost paid by the reader for the benefit of future readers. If it writes back asynchronously, the read returns faster and the repair may fail without anyone noticing. Dynamo’s design writes back synchronously as part of the read, on the argument that a read that has already paid the round trip can afford one more write, and that the guarantee is worth the latency.

Read repair also has a race with concurrent writes. A coordinator that repairs based on responses from replicas at different positions can push an older value over a newer one if the newer write lands on a replica after that replica’s response was generated. The fix is the same as everywhere else: the repair write carries the version it believes is current, and the receiving replica rejects it if it already holds a higher version. Without that check, read repair can undo a successful write, which is a data-loss bug rather than a performance issue.

Hinted handoff and the window before repair

A sloppy quorum write that lands on a non-preferred node is parked with a hint: the intended destination and the write’s version. When the intended node returns, the hint is delivered. This is cheaper than anti-entropy because it is targeted — the parked write knows exactly where it belongs — and it closes the divergence window in minutes rather than in a repair cycle.

Hints are bounded by time and by volume. A node that is down longer than the hint retention window loses its hints, and the writes they carried are recoverable only by full repair. A cluster that accumulates hints faster than it can deliver them fills disk on the nodes that are holding them, which is the availability mechanism turning into a capacity problem. Both bounds are configuration, and both are the kind of setting whose default is chosen for a normal outage and is wrong for a long one.

The ordering of hint delivery matters as much as the delivery itself. Delivering hint for version 5 after the destination has already received version 7 from a client is a regression unless the destination checks versions. Delivering hints out of order for two different keys is harmless, since they are independent. The per-key version check is therefore the same requirement as in read repair, and it is the single invariant that makes every asynchronous repair path safe.

What repair cannot fix

Repair reconciles replicas. It does not reconcile a replica with reality.

A logical corruption — a value deleted by a buggy application, a row overwritten with the wrong data — is present on every replica, and every tree agrees. Anti-entropy compares replicas to each other, so it is blind to errors they share. Detecting this class of error requires an external reference: a checksum computed at write time and verified at read time, an audit log, or a backup taken before the corruption. The checksums in modern storage formats serve the physical variant of this purpose, and they detect bit rot but not a wrong value that was correctly written.

Repair also cannot fix a divergence that the version scheme cannot express. Two replicas holding different values with the same version are a permanent conflict that the tree will report on every run, and every run will resolve it the same arbitrary way. The tree is doing its job — it is telling the truth — and the data model has no answer. That is a signal to change the data model, not to run repair more often.

Finally, repair’s cost scales with the data, so its frequency scales inversely with the size of the cluster. A large cluster repairs less often per byte, which means a longer divergence window, which means a larger set of differences to reconcile when the run happens. The system is stable as long as the write rate during the window is small relative to the repair throughput, and it degrades sharply when that stops being true. The relationship is the practical reason replication factor is kept small and ranges are kept to a size that a repair can complete in a bounded time, which ties the repair design back to the partitioning decisions in hash and range partitioning.