Two replicas that should hold the same key range have drifted apart. This build finds out where they differ without shipping every key, then repairs them. Keys are hash-partitioned into token buckets. Each replica builds a Merkle tree over those buckets, the trees are compared top-down (descending only into mismatched subtrees), and only the mismatched ranges are streamed and resolved with last-write-wins. The same approach is behind Dynamo's anti-entropy and Cassandra's nodetool repair.
The problem
Replication with sloppy quorums, hinted handoff and read repair still leaves gaps. Hints expire, nodes get replaced, disks lose files, and keys that are never read never get read-repaired. Some background process has to guarantee that replicas eventually converge. Comparing replicas key by key means sending a digest for every one of millions of keys every time, even when only a handful differ. A Merkle tree summarises the whole range in one root hash, and a mismatch can be narrowed down in O(differences × depth) hashes.
Where it shows up: Amazon Dynamo (the 2007 paper), Apache Cassandra and ScyllaDB repair, Riak's Active Anti-Entropy, and more generally in content-addressed sync (Git, IPFS, ZFS scrubs, certificate-transparency logs).
Design
token = murmur3_32(key) in [0, 2^32) tree over [lo, hi) with 2^depth equal-width leaf buckets
entry digest = SHA-256(key, ts, value | tombstone)
leaf hash = XOR of digests of entries in the bucket (empty range = 32 zero bytes)
inner hash = XOR of its two children == XOR of every entry digest in its rangeDiff (diffTrees): send the root. For each mismatched node, send its two children in the next round. Stop at the shallower tree's leaf depth, or as soon as either side's node is empty (nothing left to narrow down, so the whole range is streamed). Adjacent mismatched ranges are coalesced. The result reports hashesExchanged, rounds and a per-level trace.
Repair (repair): both replicas stream their entries in each mismatched range. For every key the winner is chosen by timestamp, then tombstone beats value, then larger value. The winner is applied to whichever side lost. The rule is deterministic and symmetric, which makes LWW a join: the outcome doesn't depend on which replica starts the session.
Invariants
- Range hash is independent of depth. XOR is associative and commutative, so a node's hash depends only on the entries in its token range, not on how the range was subdivided. Trees of different depths therefore agree on every level they share (tested level by level), and diffing works at
min(depthA, depthB). Cassandra combines row hashes the same way, and so do Riak's tictac trees. - Single-key divergence costs
2·depth + 1hashes: the root, then two siblings per level (tested at depths 4, 10 and 15). - Incremental maintenance: one write XORs out the old digest and XORs in the new one along its leaf-to-root path, in O(depth). The test shows the result is identical to a full rebuild.
- Deletes are data. Tombstones take part in the hashes and win ties, so a stale replica can't resurrect a deleted key. Purging a tombstone before every replica has seen it does resurrect the key, and the demo shows it.
- Bucket/range arithmetic is shared:
bucketOfandrangeOfuse the same floor/ceil boundaries, so every token belongs to exactly one leaf in every tree over[lo, hi).
Complexity
| Cost | |
|---|---|
| Build tree | O(n) digests + O(2^depth) node combines; memory (2^(depth+1) − 1) × 32 B (depth 16 ≈ 4 MB) |
| Diff, k divergent leaves | ≤ 1 + 2·k·depth hashes (bounded by 2^(depth+1) − 1), depth + 1 round trips |
| Naive compare | one digest per key: n hashes, every session |
| Stream | about k × n / 2^depth entries per side (whole buckets) |
In node demo.js, with 50,000 keys and 33 divergent keys at depth 12, the diff exchanges 463 hashes compared with 50,003 for a naive per-key compare, and streams 815 entries.
Failure modes and trade-offs
- Overstreaming. The repair unit is a bucket, not a key. With 33 bad keys the demo streams 87,505 entries at depth 4 and 107 at depth 16. Deeper trees cost memory, more hashes and more round trips. Cassandra spent years fighting this: row-level repair in ScyllaDB and subrange repair in Cassandra both exist because of it.
- Hot or churning data. A tree is a snapshot. Writes that land during the session show up as false mismatches. Real systems build from a consistent snapshot (Cassandra's validation compaction) or accept that some writes get repaired next time.
- Topology changes. Trees are per token range. When ranges split or move (a node joins or leaves), the trees have to be rebuilt. The Dynamo paper names this as the main drawback.
- Tombstone GC vs repair cadence. If tombstones are purged before repair has reached every replica, deleted data comes back. Cassandra's rule: repair every node within
gc_grace_seconds(10 days by default). - XOR's weakness. XOR-combined hashes are only safe because each key appears once per range and the digests are cryptographic. A structured, adversarial set of entries could cancel out. Classic Merkle trees (
H(left‖right)) avoid this, but they lose the depth independence and O(depth) incremental updates. - Clock-based LWW can silently drop a concurrent write when clocks skew. Dynamo used vector clocks and sibling values for that reason.
How production systems do it
- Dynamo (2007): each node keeps a Merkle tree per key range it hosts and exchanges roots with the other replicas to detect divergence cheaply. This handles permanent failures, while hinted handoff covers transient ones.
- Cassandra:
nodetool repairtriggers a validation compaction on each replica that reads the range and builds a Merkle tree. Trees are compared by the coordinator, and mismatched ranges are streamed as SSTable sections. Tree depth is capped (historically 2^15 leaves per range, later sized by a memory budget), so large ranges overstream. Incremental repair (marking SSTables repaired), subrange repair, and schedulers such as Cassandra Reaper keep it tractable. - ScyllaDB row-level repair compares row hashes in small batches, which removes most overstreaming.
- Riak KV Active Anti-Entropy keeps persistent hash trees updated on every write. Its later tictac trees use XOR-combinable hashes for exactly the incremental-update property used here.
Extension exercises
- Run the diff as a real message exchange (JSON over a socket pair), batching one level per round, and measure bytes on the wire against the hash counts.
- Replace XOR with classic
H(left‖right)trees. How do you then compare trees of different depths? (Hint: one side must rebuild or resample its leaves.) - Add adaptive leaves: split a bucket only when it holds more than B entries, so skewed token distributions don't overstream.
- Implement three-replica repair: one coordinator diffs all pairs and streams each range once from the replica that holds the winning versions.
- Swap LWW for version vectors with siblings, and show a case where LWW silently loses a concurrent write that vectors keep.