Merkle Tree Anti-Entropy
TechniqueDistributed SystemsSeniorStaffUpdated
Replicas build a tree of hashes over their key ranges; comparing root then children lets them find divergent ranges in O(log n) hops instead of full scans.
When to Use Merkle Tree Anti-Entropy
Background repair between leaderless replicas after partitions, dropped writes, or hinted-handoff misses. Cheap when divergence is rare.
In Practice
Cassandra's nodetool repair, DynamoDB's anti-entropy, and Riak active anti-entropy all use Merkle trees. Git's object store uses the same idea for packfile transfer.
How Merkle Tree Anti-Entropy Comes Up in Interviews
Scenario
Two Cassandra replicas of a 1TB range may have drifted. You want to find the small set of differing keys without streaming the whole range.
Each replica builds a Merkle tree of hashes over sub-ranges. Compare roots; if equal you're done. If different, descend only into mismatched children. Finds a single divergence in O(log n) comparisons.
Cassandra's nodetool repair does exactly this. AWS DynamoDB's internal anti-entropy and Git's wire protocol use the same tree-of-hashes idea.