Merkle Trees and Anti-Entropy

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.

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

View full sizeOpen original

Merkle Trees and Anti-Entropy

Reset viewClose

Mechanism and decision flow for Merkle Trees and Anti-Entropy.