Merkle Trees and Anti-Entropy Repair
Merkle trees explained: hash trees that compare large datasets cheaply, anti-entropy repair between replicas, and their use in Cassandra, Git and blockchains.
A Merkle tree (hash tree) summarises a large dataset in a tree of hashes: each leaf is the hash of a block of data, and each parent is the hash of its children, up to a single root hash. Two copies of the data are identical if and only if their root hashes match, and if they differ, comparing hashes level by level finds exactly which blocks differ while exchanging very little data. That makes Merkle trees the standard tool for anti-entropy repair between replicas, and for verifying data in Git, file systems and blockchains.
How the tree is built
Finding differences between replicas
- Two replicas each build a Merkle tree over the same key ranges.
- They exchange root hashes. If they match, the data is identical and they're done, having sent one hash.
- If not, they compare the children and descend only into subtrees whose hashes differ.
- At the leaves, they sync just the key ranges that differ.
For a dataset split into a million leaf ranges with one range out of sync, the replicas exchange about 20 levels × 2 hashes instead of comparing every key. The work is proportional to the number of differences times the depth of the tree, not to the size of the data.
Anti-entropy in distributed databases
Replicas in leaderless stores drift apart: a write misses a replica that was down, a hint is lost, or a disk is replaced. Read repair only fixes data that's read. Anti-entropy is the background process that compares all data. Dynamo-style systems such as Cassandra build Merkle trees per token range during a repair, exchange them between replicas, and stream only the mismatched ranges. See Dynamo-style stores.
- Granularity trade-off: deeper trees find differences more precisely but cost more memory and CPU to build.
- Building cost: hashing all data is expensive, so repairs are scheduled, throttled, or done incrementally on recently changed ranges.
- Moving data: trees are tied to key ranges; when ownership changes, affected trees must be rebuilt.
Other uses
| System | What the Merkle structure provides |
|---|---|
| Git | Commits, trees and blobs are content-addressed by hash, so a commit hash identifies the whole project state and history |
| Blockchains | A block header holds the Merkle root of its transactions, so a light client can verify one transaction with a short proof |
| File systems and backups | Content-addressed chunks and hash trees detect corruption and deduplicate unchanged data |
| Certificate Transparency logs | Append-only Merkle logs let anyone verify that a certificate was logged and the log wasn't rewritten |
| File sync | Comparing hash trees of directories finds changed files quickly |
A Merkle proof shows that one leaf belongs to a tree with a given root by supplying the sibling hashes along its path. Its size grows with the logarithm of the number of leaves.
Where it’s used
Replicas exchange Merkle trees per range to find and fix divergent data.
Content-addressed hash trees make history tamper-evident and comparisons fast.
Hash trees of chunks find what changed in large files and folders.
In an interview
- Explain building leaves from data ranges and parents from child hashes.
- Walk through descending only into mismatched subtrees.
- Use Merkle trees for anti-entropy in a replicated store.
- Mention the cost of building trees and tree granularity.
Further reading
- Apache Cassandra: RepairApache Cassandra documentation
- Certificate Transparency: How CT workscertificate.transparency.dev