Skip to content

Merkle-Tree Divergence Scan

Divergence-detection method — instantiates Asynchronous Replica Convergence

Compares two replicas by exchanging a tree of range hashes, zeroing in on exactly which keys differ while transferring almost no data.

Merkle-Tree Divergence Scan answers one question cheaply: do these two replicas hold the same data, and if not, exactly where do they differ? It hashes the keyspace into a tree — each leaf a range of keys, each parent the hash of its children — so two replicas can compare a single root hash to prove equality, and, when the roots differ, descend only into the branches that mismatch. Its defining property is cost: localizing a difference takes work proportional to the size of the difference, not the size of the dataset. It is pure detection — it finds and pinpoints divergence but repairs nothing, handing a precise list of differing keys to whatever mechanism does the fixing.

Example

Two replicas of a 40-million-row user table drift apart during a network partition and now need reconciling. Streaming all 40 million keys across the wire to compare them would cost hours and saturate the link. Instead each replica builds a Merkle tree over sorted key ranges and they exchange just the root hash. The roots differ, so they descend: at each level they trade only the child hashes and prune every subtree whose hashes already match.

After a couple dozen small hash exchanges the scan has narrowed the disagreement to ≈1,200 keys in three leaf ranges — out of forty million. That short, exact list is what gets handed to the repair process. The whole detection cost a few kilobytes of hashes; almost no data moved until the system knew precisely what to move.

How it works

Its distinctive trick is hierarchical hashing with prune-on-match descent. Because a parent hash summarizes its whole subtree, a single matching hash certifies that an entire range is identical and can be skipped; only mismatching branches are explored, so comparison narrows logarithmically toward the actual diff. It emits two things: a root-level equality verdict (equal roots ⇒ the replicas are identical) and, on mismatch, a localized diff set plus a measure of how much and where the replicas have drifted. It is a detector feeding a repairer — it deliberately does not decide which side is right or move the data.

Tuning parameters

  • Leaf granularity / tree depth — how many keys per leaf. Finer leaves localize the diff to smaller ranges (cheaper repair) but cost more to compute and store; coarse leaves force re-transferring a whole bucket for one changed key.
  • Hash function and width — stronger, wider hashes shrink collision risk — two different ranges hashing equal and a real diff being missed — at the cost of size and CPU.
  • Range bucketing scheme — how keys map to leaves. The two replicas must bucket identically or their trees won't align and every branch looks different; this is the parameter that most often breaks a scan.
  • Scan trigger — on demand (before a repair, after a partition) versus on a schedule. On-demand avoids rebuilding trees over churny data needlessly.

When it helps, and when it misleads

Its strength is making "are these two big replicas in sync, and if not, where?" answerable for kilobytes instead of gigabytes — the detection step that makes background reconciliation affordable at scale. Its limits are honest ones: it tells you that and where replicas differ, never which side is correct. A root-hash match only proves the two agree, even if they agree on the same wrong value, and deciding a winner needs version metadata the scan doesn't carry.[1] It is also only as valid as its bucketing: trees built over mismatched range boundaries compare as all-different and send you chasing phantom divergence. The classic misuse is reading a matching root hash as a correctness certificate rather than an equality one, or comparing incomparably-bucketed trees. The discipline is to fix identical bucketing on both sides, pair the scan with causal metadata to pick the winner, and keep it firmly as detection feeding a separate repair.

How it implements the components

Merkle-Tree Divergence Scan fills the detection components — the ones a comparison method can fill:

  • state_equivalence_test — comparing root hashes is a direct, cheap test of whether two replicas hold equivalent state.
  • drift_detection_signal — descending the tree yields exactly where and how much the replicas have drifted, the signal that triggers and scopes repair.

It does not repair the differences it finds (that is Anti-Entropy Reconciliation Exchange, which consumes this scan) or decide which side is newer (that is Version-Vector or Dotted-Context Exchange). It proves equality and localizes drift; others act on it.

References

[1] A Merkle tree (hash tree, after Ralph Merkle) summarizes a large dataset as a tree of hashes so that any difference can be localized by comparing O(log n) hashes rather than the whole data. It certifies equality of content, not authority — which of two differing replicas should win is a separate question the tree cannot answer. ↩