20 Merkle Trees
Two replicas hold copies of the same data range. They've drifted apart -- some records differ. You need to find exactly which records are different so you can sync only those. But the data range contains millions of records. You can't compare them one by one (too much network traffic) or compare a single hash of the entire range (tells you something differs, but not what).
Background
Read repair fixes stale data lazily during reads. Hinted handoff handles short-term failures. But what about data that's rarely read (so read repair doesn't trigger) or divergence that accumulated over a long outage (beyond the hint window)?
You need a way to proactively detect and repair divergence between replicas -- efficiently, in the background, without transferring entire datasets.
The naive approach: have both replicas send all their data to a coordinator for comparison. This works but transfers an enormous amount of data, most of which is identical.
The efficient approach: use a data structure that lets you narrow down exactly which records differ with minimal data exchange.
Definition
A Merkle tree (also called a hash tree) is a binary tree where:
- Each leaf node contains the hash of a portion of the data (e.g., one record or one block)
- Each internal node contains the hash of its two children
- The root contains a hash that represents the entire dataset
How it works for replica synchronization
- Both replicas independently build a Merkle tree over their data
- Compare the root hashes
- If they match → the entire dataset is identical, stop
- If they don't match → recurse into the children
- Compare child hashes to narrow down which subtree contains differences
- Continue recursing until you reach the leaf nodes that differ
- Transfer only the differing records
Why this is efficient
With N records:
- Naive comparison: Transfer all N records → O(N) data
- Single hash: Compare 1 hash, but if different, you must transfer everything → O(N) worst case
- Merkle tree: Compare O(log N) hashes to find the exact differences → transfer only the differing records
For two replicas with millions of records where only a handful differ, a Merkle tree lets you find those handful by exchanging just a few kilobytes of hashes.
Merkle trees are a binary search over data integrity. Just as binary search efficiently finds a value in a sorted list by halving the search space, a Merkle tree efficiently finds data differences by halving the data range at each level of the tree.
Trade-offs
| Advantage | Disadvantage |
|---|---|
| Minimal data transfer for synchronization | Trees must be recalculated when data changes |
| Each subtree can be verified independently | When nodes join/leave, key ranges change and trees need full rebuilding |
| Efficient background anti-entropy | Building the tree requires reading all data (CPU and I/O cost) |
The recalculation cost is the main drawback. In systems where data changes frequently or the cluster topology changes often, Merkle trees can be expensive to maintain. This is why they're typically rebuilt periodically (not in real-time) and used for background repair, not real-time consistency.
The complete anti-entropy stack
| Layer | Mechanism | Handles |
|---|---|---|
| 1 (immediate) | Hinted Handoff | Short-term node failures during writes |
| 2 (on access) | Read Repair | Stale data detected during reads |
| 3 (background) | Merkle Trees | All remaining divergence, including cold data |
Together, these three mechanisms ensure that replicas converge -- hinted handoff catches most problems immediately, read repair fixes hot data on access, and Merkle trees sweep up everything else in the background.
Examples
Dynamo
Dynamo uses Merkle trees for background anti-entropy. Each node maintains a separate Merkle tree for each key range it hosts. Nodes periodically compare their Merkle trees and synchronize any divergent data. See Anti-entropy Through Merkle Trees for the full details.
Cassandra
Cassandra uses Merkle trees during its nodetool repair process. When repair is triggered, nodes exchange Merkle trees over their shared data ranges to identify and sync differences. Cassandra's repair is typically run manually or on a schedule, rather than continuously.
Git and blockchain
Outside of distributed databases, Merkle trees are used in Git (to efficiently detect which files changed between commits) and in blockchain (to verify transaction integrity without downloading the entire chain).
Merkle trees are the answer to "How do you efficiently sync replicas that have drifted apart?" The key phrase: "Build a hash tree over the data, compare root hashes, and recurse into subtrees that differ -- this finds exactly which records need syncing with O(log N) comparisons instead of comparing all N records." Always present it as the third layer alongside hinted handoff and read repair.