Merkle Trees and Anti-Entropy
A Merkle tree summarizes data ranges with hashes so replicas can locate divergent portions without transferring every record.
Merkle Trees and Anti-Entropy
A Merkle tree summarizes data ranges with hashes so replicas can locate divergent portions without transferring every record. Hash each leaf record in a canonical representation. Parent hashes combine child hashes; the root summarizes tree contents. If roots differ, compare child hashes recursively until mismatching leaves or ranges are isolated. Tree shape, key ordering, hash algorithm and serialization must be deterministic.
Mechanism and worked example
Two replicas each hold one million records. Matching roots for a range avoid sending every record. A mismatch narrows repair to a smaller subtree; exact keys and versions are then compared and transferred under a safe repair policy.
| Technique | Purpose | Boundary |
|---|---|---|
| Record checksum | Detect changed record | No range localization |
| Merkle root | Summarize dataset | Requires canonical encoding |
| Recursive compare | Find divergent ranges | Concurrent writes need snapshot |
| Repair | Restore convergence | Conflict policy decides winner |
Failure modes and operations
Different canonicalization, schema versions or tree shapes create false mismatches. Concurrent writes during comparison require snapshots or versioning. A matching cryptographic hash is strong evidence, not mathematical proof against collisions. Repair can overwrite newer data if conflict policy is unspecified.
Trade-offs and design boundary
Merkle trees reduce comparison bandwidth but add index/build/maintenance cost. A full scan is simpler for small datasets. Checksums detect corruption but do not localize missing ranges. Anti-entropy must retain versions and tombstones long enough to repair.
Interview transfer exercise
How should replicas repair a mismatching subtree? Compare a stable snapshot, identify exact records, then reconcile by the database's version/conflict rule; do not blindly copy one replica over another.
Read the diagram
Build deterministic leaf hashes by key range → Compare replica roots → Descend into mismatching branches → Reconcile exact records under version policy