# Merkle Trees: Comparing Huge Datasets Cheaply How do two replicas holding millions of keys find the few that differ without sending everything? Merkle trees, a favourite detail in replication and storage interviews. ## Structure Split the key space into ranges. Hash each range's data to get the **leaves**. Each parent node stores the hash of its children's hashes, up to a single **root hash** that summarizes the whole dataset. ## Comparing two replicas 1. Exchange root hashes. Equal means the data is identical: done in one round trip. 2. If different, compare the children and descend only into subtrees whose hashes differ. 3. At the leaves, sync just the mismatched ranges. Cost is proportional to the number of differences times the tree depth, not the dataset size. ## Where they appear - **Anti-entropy repair** in Dynamo-style databases (Cassandra, Riak) to fix replicas that missed writes. - **Git**: every commit points to a tree of hashes, so identical files and directories are shared and changes are detected instantly. - **Blockchains**: transactions in a block form a Merkle tree, so a light client can verify one transaction with a short proof path. - **Content-addressed storage and sync tools** (IPFS, backup deduplication). - **Certificate Transparency logs** use them to prove entries were appended, not altered. ## Design trade-offs - Rebuilding the tree costs CPU and I/O; systems often rebuild periodically rather than on every write. - Leaf granularity: small ranges mean precise syncs but a bigger tree. - Use a strong hash (SHA-256) when adversaries matter; a fast hash is fine for internal repair. ## Interview tip If your design replicates data, mention Merkle-tree anti-entropy as the background safety net behind read repair and hinted handoff. Disclosure: I work on Linkjob AI (https://www.linkjob.ai/), an AI interview assistant.