The question this answers
How do two replicas find which of a billion keys differ, without sending each other a billion keys?
If two roots are equal, the compared ranges are identical — with a probability of error equal to a 256-bit hash collision, which is not a practical concern. If they differ, the tree locates every differing *leaf range* in O(depth) round trips per divergent path, exchanging only hashes. It guarantees nothing below leaf granularity: you learn which range differs, never which key.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A replica knows the hashes of its own ranges and whatever hashes its peer has sent. Crucially, it never learns the peer’s data — only that some range disagrees. The comparison is an argument about equality conducted entirely in hashes, which is why it is cheap and why it can be run between mutually untrusting parties.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
The construction, and the one-round-trip case
Take a key range and split it into a fixed number of contiguous leaf ranges — say 2^15 = 32,768 of them. Hash the contents of each leaf: every key and value it contains, in a canonical order. Then hash each pair of sibling hashes to form their parent, and repeat upward until a single root hash remains.
Now the headline property. Two replicas exchange one root hash — 32 bytes. If they match, a terabyte of data on each side is identical, established in one round trip. That is the case that dominates in practice, because most ranges on most replicas are in fact in agreement, and it is why repair is affordable at all.
When the roots differ, you descend. Compare the two children; at least one differs; recurse into the differing ones only. A single divergent key means one path from root to leaf, so about 15 levels — roughly 30 hash exchanges to narrow a billion keys to a range of 30,000. Then, and only then, does any actual data move: you stream that leaf range and reconcile it.
The cost structure is worth stating precisely: O(1) when equal, O(k · log(L/k)) node visits for k differing leaves out of L. Divergence is cheap to find when it is rare, and the structure degrades gracefully to "compare everything" when it is not — which is the right shape, since widespread divergence means you were going to move most of the data anyway.
root
a3f9 | 7c21 <- differ, descend
/ \
8e10 | 8e10 b442 | 1d0c <- left matches, prune it
(identical, / \
skip entirely) 55ab|55ab 90fe|c317 <- descend right
/ \
... leaf 24178
90fe | c317
^ stream this range only
exchanged: ~30 hashes (about 1 KB)
transferred data: one leaf range, not the dataset
if the roots had matched: 32 bytes, and doneDepth is a trade between memory and how much you over-send
The tree can only narrow divergence to a leaf. Whatever a leaf covers, you transfer — so leaf granularity sets the floor on wasted transfer, and depth sets leaf granularity.
With a billion keys and depth 15, each leaf covers about 30,000 keys. One differing key costs you 30,000 keys of streaming: perhaps a few hundred megabytes to repair one row. Go to depth 20 and leaves cover ~1,000 keys, cutting the waste by 30× — but the tree now has 2^20 leaf hashes, and at 32 bytes each that is 32 MB of hashes *per range per replica*, held in memory during comparison and recomputed whenever the data changes.
That is the whole trade: deeper tree, less over-streaming, more memory and more hashing work. Real systems cap depth for exactly this reason and accept the over-streaming, which is why a repair can move gigabytes to fix a handful of rows. When an operator complains that repair streamed far more than the actual divergence, this is usually the honest explanation and not a bug.
The second-order effect: building a tree requires reading and hashing the whole range. If the tree is rebuilt from scratch for every repair, the *build* — not the comparison — is the dominant cost, and it competes with live traffic exactly like Rebalancing: A Load Spike You Schedule for Yourself does. Systems that maintain incremental hashes as data changes avoid this; systems that do not pay full-scan cost per repair cycle.
| Depth | Leaves | Keys per leaf | Hash memory per range | Over-streaming to fix one key |
|---|---|---|---|---|
| 10simplified | 1,024 | ~977,000 | 32 KB | about a million keys |
| 15simplified | 32,768 | ~30,500 | 1 MB | about 30,000 keys |
| 20simplified | 1,048,576 | ~950 | 32 MB | about 1,000 keys |
| 25simplified | 33,554,432 | ~30 | 1 GB | about 30 keys — and the tree no longer fits comfortably |
The two ways this goes wrong in production
Both are subtle, both are common, and both produce the same symptom: repair reports enormous divergence and streams huge volumes between replicas that hold identical data.
The trees must cover exactly the same ranges. A hash tree is defined over a specific key interval split at specific boundaries. If replica A builds its tree over [0, 1000) and replica B over [0, 1200), the roots differ for a reason that has nothing to do with the data. This is why repair is always scoped to a token range that both replicas agree on — and why a topology change invalidates every cached tree. Adding a node changes range boundaries, and any tree built before it is now incomparable. Systems that fail to invalidate on topology change repair the entire dataset for no reason.
The leaf hash must be over a canonical serialisation. The hash covers bytes, and identical logical data can produce different bytes: rows in a different order, different compaction state, a tombstone still present on one side and purged on the other, a value re-encoded by a newer writer, timestamps at different precisions. Every one of these makes the hashes differ while the data agrees, and the tree faithfully reports a difference that is not there.
The fix is discipline about what goes into the hash: a defined ordering, a defined encoding, an explicit decision about whether deletion markers are included, and a hash that covers logical content rather than physical layout. Getting this wrong is the single most common cause of "repair streams far more than it should", far more common than genuine divergence.
A third, smaller one: the tree is built over a moving dataset. Writes landing during the build mean the two sides hash slightly different snapshots and report differences at the margin. Systems accept a small false-positive rate here rather than freezing writes — the right call, provided the rate stays small.
The same structure, doing a different job: proofs
Everything above uses the tree for *diffing*. The same construction supports something else entirely, and seeing both is what makes the idea click.
A Merkle proof is the set of sibling hashes along the path from a leaf to the root — about log₂(n) hashes. Give someone the root and a proof, and they can verify that a specific leaf is part of the tree without holding any other part of it. Verification is O(log n) hashes and requires no trust in the party that supplied the proof: recompute the path and compare to a root you already trust.
Diffing asks "where do we differ?"; proving asks "can you show me this belongs?" Both work because a Merkle root is a compact, tamper-evident commitment to a whole dataset: changing any byte anywhere changes the root, and the path from that byte to the root is short.
That is why the structure appears everywhere once you recognise it. Git commits are a Merkle DAG — a commit hash commits to the entire tree beneath it, which is why git fetch can determine what you are missing by exchanging a few hashes. ZFS and Btrfs hash blocks into a tree so that corruption is detectable and localisable. Certificate Transparency uses inclusion and consistency proofs to show a log is append-only. Blockchains commit a block’s transactions to a single root so a light client can verify one transaction. IPFS addresses content by its hash tree. Dynamo, Cassandra and Riak use it for exactly the repair job in this lesson.
And there is a nice structural note for readers coming from data structures: a Merkle tree is a segment tree whose aggregate function is a hash. Both are trees over ranges with an aggregate per node; the segment tree aggregates sums or minima for querying, the Merkle tree aggregates hashes for comparison. Same shape, different monoid.
When something else is better
Merkle trees are not the only way to reconcile two sets, and for some shapes of problem they are not the best one.
Version or timestamp comparison. Keep a max-timestamp or a mutation counter per range. Comparing is one number. It tells you *that* a range changed, never *which* keys, and it is fragile under clock skew — but for "has anything happened here since we last synced?", it is far cheaper.
A change log. If you have an ordered log of mutations, reconciliation is "send me everything after offset X" — exact, incremental, and cheap. This is why leadered systems do not need Merkle trees (The Raft Log: Commit Index, Divergence and Reconciliation, The Log Is Not a Queue), and it is the strongest alternative when the architecture permits it.
Set-reconciliation sketches. Invertible Bloom lookup tables and related structures reconcile two sets in one round trip, with a message sized proportional to the *number of differences* rather than the log of the set size. When two peers differ by a handful of items out of millions, this is strictly better than descending a tree — Bitcoin’s Erlay uses Minisketch for exactly this. The catch is that the sketch must be sized above the actual difference count, and if it is undersized it fails to decode and you retry larger.
Bloom filters for the asymmetric case: send a filter of your keys and let the peer send back anything not in it. Cheap and one-directional, with a false-positive rate meaning a few genuinely missing keys go unnoticed per pass — fine when repair repeats, unacceptable when it does not.
The honest summary: Merkle trees win when the set is huge, differences may be anywhere, and you want the equal case to cost nothing. Sketches win when differences are few and one round trip matters. Logs win whenever you can have one.
Key points
- One 32-byte root exchange proves that two replicas hold identical data over a whole range.
- When roots differ, only the divergent paths are descended: about 15 levels to locate one bad key among a billion.
- No key or value is ever transferred during comparison — the whole argument is conducted in hashes.
- Leaf granularity is the resolution limit; whatever a leaf covers, you re-stream. Depth trades memory against over-streaming.
- Trees are comparable only over identical range boundaries and identical canonical serialisation — violating either reports divergence that does not exist.
- The same structure yields O(log n) inclusion proofs, which is why it underpins git, ZFS, Certificate Transparency and content-addressed storage.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • Agree with the peer on the exact key range to compare — usually a token range both replicas own.
- • Split the range into a fixed number of contiguous leaf ranges at deterministic boundaries.
- • For each leaf, hash its contents in a canonical order and encoding, including deletion markers by an explicit rule.
- • Hash sibling pairs upward to a single root.
- • Exchange roots. If equal, stop — the ranges are identical.
- • Otherwise exchange the children of each differing node, recursing only into subtrees whose hashes disagree.
- • For each differing leaf, stream that range’s data and reconcile with the merge rule.
- • Discard the trees; rebuild them next cycle, or maintain them incrementally as data changes.
- • The two sides build trees over different range boundaries and every comparison reports total divergence.
- • Serialisation differs — row order, compaction state, tombstone presence, timestamp precision — and identical data hashes differently.
- • Writes land during the build, so the two snapshots differ at the margin and repair chases phantom differences.
- • The tree does not fit in memory at the configured depth and building it destabilises the node.
- • Range boundaries change mid-repair due to a topology change, invalidating work in progress.
- • One replica is corrupt; the tree correctly reports a difference and the merge rule picks the corrupt side.
- • Massive over-streaming: repair moves gigabytes between replicas that are logically identical. The operator sees streamed bytes far exceeding any plausible divergence — almost always a serialisation or boundary mismatch, not real drift.
- • Repair reports full divergence after every topology change: every range differs immediately following a node addition, because the cached trees were built over the old boundaries and were not invalidated.
- • Memory pressure or OOM during tree build on a wide range: the node building the tree becomes slow or dies. The operator sees a node fail reliably at the same point in the repair cycle, with heap dominated by hash arrays.
- • Repair that fixes one row and moves a gigabyte: leaf granularity is coarse. The operator sees a wildly unfavourable ratio of repaired rows to transferred bytes, which is expected behaviour and is regularly misfiled as a bug.
- • Endless repair chasing live writes: on a range under constant write load, each pass finds new differences created during the previous pass. The operator sees repair never converging on a hot range while cold ranges complete normally.
- • The two replicas must agree on the range and the leaf boundaries before comparing. That agreement is small but essential, and it is where topology changes break things.
- • Nothing else needs coordination — the comparison is pairwise and independent of the rest of the cluster, so many pairs can compare concurrently.
- • Because only hashes cross the wire, the comparison reveals nothing about the data itself, which is what allows the same technique to work between parties that do not trust each other.
- • The merge that follows the comparison needs a deterministic rule, not a protocol (Anti-Entropy: Repairing Divergence Nobody Reported).
- • An aborted comparison loses only the work done; nothing is left inconsistent, since comparison has no side effects.
- • A comparison against a corrupt replica correctly identifies the difference — the tree is doing its job; the merge rule then has to decide, and a timestamp cannot distinguish corrupt from current.
- • Under concurrent writes the comparison reports a small number of false differences, which cost a little extra streaming and no correctness.
- • If one replica is far behind, the tree degenerates toward comparing everything — correct behaviour with no cliff, just a gradual loss of the shortcut.
- • Detect: track the ratio of bytes streamed to rows actually repaired. A ratio far above leaf granularity means the comparison is producing false differences.
- • Contain: cap tree depth and repair range size so a build cannot exhaust memory.
- • Recover: on a suspected serialisation mismatch, compare a single leaf by hand — hash the same rows on both sides with the same encoding and see whether they agree.
- • Reconcile: invalidate all cached trees after any topology change; treat this as mandatory rather than an optimisation.
- • Verify: re-run the comparison after repair and confirm the roots now match. A repair that does not end with matching roots has not finished.
- • Bytes streamed per repair versus rows repaired — the single diagnostic that separates real divergence from a broken comparison.
- • Tree build time and peak memory per range, which determine whether depth is set sanely.
- • Number of differing leaves per comparison, over time. A stable low number is healthy; a step change means something structural altered.
- • Comparisons that end in matching roots as a fraction of all comparisons. This should be high; if it is not, either divergence is rampant or the trees are not comparable.
- • Repairs abandoned or restarted due to topology change, which tells you whether repair scheduling and cluster operations are colliding.
- • Comparing large replicas where most data agrees — the equal case costs one round trip, which is what makes routine repair viable.
- • Leaderless replication, where there is no log to replay and set comparison is the only option (Leaderless Replication: Every Replica Accepts Writes).
- • Detecting silent corruption, since the hash covers content rather than metadata.
- • Synchronising over expensive or slow links, where avoiding transfer is worth substantial local computation.
- • Any setting where one party should learn *whether* data matches without learning the data.
- • When divergence is widespread — the descent visits most of the tree and you pay comparison cost on top of streaming everything anyway.
- • On ranges under constant heavy write load, where the dataset changes faster than a pass completes.
- • When an ordered change log is available, which makes reconciliation exact and incremental with no comparison at all.
- • When differences are few and one round trip matters — a set-reconciliation sketch does the same job in a single exchange.
- • When the data cannot be canonically serialised, in which case the tree reports noise rather than divergence.
- • Per-range version numbers or max timestamps: one number to compare, tells you that something changed but not what.
- • Change-log replay from an offset — exact and incremental, and the reason leadered systems need none of this (The Log Is Not a Queue).
- • Invertible Bloom lookup tables and similar sketches: one round trip, message size proportional to the number of differences rather than the size of the set.
- • Bloom filters for one-directional reconciliation: cheap, with a false-negative rate that repeated passes absorb.
- • Full comparison, when the range is small enough that the machinery costs more than it saves. Under a few thousand keys, just send the list.
- • Rebuilding the replica from a peer or a backup instead of comparing, when divergence is known to be large.
Finding the difference without reading the data
What people believe, and what is true
A Merkle tree tells you which keys differ.
It tells you which *leaf ranges* differ. Whatever a leaf covers must then be transferred and compared, which is why fixing one row can move a gigabyte.
Deeper trees are strictly better.
Depth cuts over-streaming and multiplies hash memory and build cost. Depth 25 over a billion keys needs a gigabyte of hashes per range per replica.
If the roots differ, the data has diverged.
It means the hashes differ. Different range boundaries, different row ordering, different tombstone state or a re-encoded value all produce differing roots over identical data — and this is more common in practice than genuine divergence.
Merkle trees are a blockchain thing.
They predate it by decades and are used for repair in Dynamo-lineage stores, for content addressing in git, for integrity in ZFS, and for inclusion proofs in Certificate Transparency.
Building the tree is cheap because it is only hashing.
It requires reading the entire range from disk. On a large range the build, not the comparison, dominates the cost of a repair cycle.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Hash each slice of a key range, hash the hashes upward to a root, and compare roots. Equal roots mean identical data, proven in 32 bytes.
Practical
Scope every comparison to a range both replicas own, invalidate cached trees on any topology change, and watch the ratio of bytes streamed to rows repaired. A high ratio means the trees are not comparable, not that the data has drifted.
Advanced
The leaf is the resolution limit and depth is the knob: 2^d hashes in memory buys you leaves of n/2^d keys, and whatever a leaf covers gets re-streamed for a single differing key. Real systems cap depth and accept over-streaming, because hash memory is per range per replica and repair runs many ranges at once.
Internals
Hash logical content under a canonical encoding, never physical layout. Row order, compaction state, tombstone presence, timestamp precision and value re-encoding all change the bytes without changing the meaning, and every one of them turns the comparison into noise. Decide explicitly whether deletion markers participate in the hash — if they do not, a purged tombstone on one side makes the ranges look different in exactly the case Anti-Entropy: Repairing Divergence Nobody Reported cares about most.
Apply it
- 🔧 Implement a depth-10 Merkle tree over a sorted map, then measure the number of hash comparisons required to locate 1, 10 and 1,000 differing keys.
- 🔧 Break your own implementation deliberately by hashing rows in insertion order rather than key order, and observe that identical datasets now report full divergence.
- ⚡ After adding a node, every repair reports that every range differs. Nothing else changed. What happened?
- ⚡ A team wants to sync two 500 GB datasets across a slow WAN link where roughly 200 records differ. Compare a Merkle tree against a set-reconciliation sketch for this case.
- 💬 Two replicas hold a billion keys. Design a protocol that finds the differing ones without transferring the data.
- 💬 Repair between two replicas streams 40 GB and repairs 12 rows. Give me three possible explanations, ranked.
- 💬 What does a Merkle proof let you verify, and what do you need to trust to verify it?