The idea: find the few keys that differ without sending all of them
Replicas of the same data drift apart. A write reaches two of three replicas because the third was down, a hint for it is lost, a disk is replaced. Anti-entropy repair is the background job that finds such differences and copies the missing data. The naive way, sending every key (or a hash of every key) to the other replica, costs as much as the data set, even when nothing differs, which is the usual case.
A Merkle tree (hash tree) makes the check cheap. Split the keys into ranges; a leaf is the hash of one range, and every parent is the hash of its two children's hashes. The root then summarises everything: if two replicas have the same root, they hold the same data. If not, compare the two children, and go down only where the hashes differ. On the page, replicas A and B each hold 16 keys in 8 ranges of 2 keys, and each value is a version (cat=v2 is newer than cat=v1).
Why replicas drift
Leaderless stores such as Dynamo, Cassandra and Riak write to N replicas and are happy when W of them answer (see Quorum Reads and Writes). A replica that was down misses writes. Hinted handoff covers short outages but hints can be dropped; read repair fixes a key when a read notices the replicas disagree, but keys that are never read are never fixed. Disks fail and are replaced empty. Anti-entropy is the safety net that catches what the other mechanisms miss (Demo: A lost a whole range: nobody reads kiwi or lynx, so only repair notices).
Building the tree
Each leaf covers a fixed range of keys (in Cassandra, a range of tokens on the hash ring), so both replicas cut the key space at the same places and their leaves can be compared one to one. The page hashes a leaf as H("cat=v1;dog=v1") and a parent as H(left + right). H is FNV-1a folded to 16 bits and shown as 4 hex digits, so you can read every value; a real tree uses MD5, SHA-256 or another wide hash, where an accidental match is out of the question. A write changes one leaf and the hashes on its path to the root, nothing else (Demo: one missed write: B re-hashes 4 nodes).
| System | When the tree is built | Leaves |
|---|---|---|
| Amazon Dynamo | kept per key range a node holds | key ranges of the ring |
Cassandra (nodetool repair) | at repair time, by a read of the data (validation compaction) | token ranges, depth up to 20 (about a million leaves) |
| Riak KV (active anti-entropy) | kept on disk and updated on every write | segments of the key space |
Descending: one round trip per level
Repair starts at the root. If A's and B's roots are equal, it is over after one hash (Demo: in sync). If not, A asks for the two children's hashes, keeps the ones that differ, and asks for their children, and so on down to the leaves. A subtree whose hash matches is never opened. For one differing range in a tree of depth d, that is 1 + 2·d hashes in d + 1 round trips: 7 hashes and 4 round trips on the page.
Differences in several places cost more, because every differing subtree is followed: with bee newer on B and mole newer on A, both halves differ and A follows two paths, 11 hashes (Demo: two keys in different halves). The worst case, every range different, sends every hash in the tree, which is about as much as the keys themselves; repair then degrades to a full copy, which is fine because that is what is needed.
Syncing the ranges
At the leaves A knows which ranges differ, but not which keys inside them. So the replicas exchange the whole range: A sends its copy to B, then B sends its copy to A, and each keeps the newer version of every key (last write wins, by version or timestamp). Both re-hash, and their roots are equal again (Demo: repair, then repair again: the second repair costs 1 hash). A leaf range is the unit of transfer, so a coarse tree streams more keys than strictly needed; Cassandra calls this overstreaming.
What it costs
| Situation | Hashes exchanged | Key/value pairs sent | Full compare |
|---|---|---|---|
| In sync (demo 1) | 1 | 0 | 16 keys |
| One missed write (demo 2) | 7 | 4 (2 each way) | 16 keys |
| Two keys in different halves (demo 3) | 11 | 8 | 16 keys |
| A lost a whole range (demo 4) | 7 | 2 (A has none to send) | 16 keys |
| 1 million keys, 220 leaves, one key differs | 41 | a few | 1 million keys |
The same idea, one hash standing for a whole subtree, is behind Git's object store, ZFS and Btrfs checksums, certificate transparency logs and blockchains. Merkle trees are hash functions put to work; for what a hash does and does not promise, see Encryption vs Hashing.
Git uses the same idea: every commit hash covers its parent's hash, which is why a rebase gives every replayed commit a new ID — see Git Merge vs Rebase.
Git names commits by hash the same way; Git branches and HEAD shows the small ref files that point at those hashes.
For how Bitcoin puts a Merkle root in its block header and proves one transaction with log n hashes, see Bitcoin Merkle Trees and SPV Proofs.
See also Object Storage, where missing erasure-coded shards are what a repair job has to find and rebuild.
A blockchain chains block hashes the same way; see Proof of Work.
What the page leaves out
Real trees are much deeper and use wide cryptographic hashes; Cassandra builds them per token range by reading all the data (expensive, so repairs are scheduled and can be incremental), and both replicas send their whole trees to a repair coordinator instead of descending interactively. More than two replicas (each pair is compared), deletions (tombstones must survive until repair runs, or deleted data comes back), clock-based timestamps and their skew, version vectors and siblings, streaming whole SSTable files, and the cost of keeping the tree current on every write are all skipped. How replicas find each other and agree on membership is on Gossip and SWIM; what readers see while replicas differ is on Consistency Patterns and Database Replication.