LESSON 27.2
Anti-entropy and content addressing
How databases repair diverged replicas with Merkle trees, how sync tools transfer only what changed, and why naming data by its hash makes storage, caching and deduplication simpler.
7 min read
Merkle trees and hashes show up in two big families of system design: repairing replicas that drift apart, and naming data by its content. Both turn hard questions ("what changed?", "is this the right data?", "have we stored this already?") into cheap hash comparisons.
Anti-entropy repair
Leaderless databases accept writes on several replicas, so replicas drift: a node was down, a hint was lost, a write reached only some replicas. Three mechanisms bring them back together:
Hinted handoff
- Quick fix for short outages
- Hints are temporary and can be lost
Pick it when: Node down for minutes.
Read repair
- Fixes hot data as a side effect of reads
- Data never read is never fixed
Pick it when: Every quorum read that sees a mismatch.
Anti-entropy (Merkle repair)
- Covers everything, read or not
- Costs I/O to build trees
- Must run regularly
Pick it when: Scheduled background repair, such as weekly per node.
- Each replica builds a Merkle tree over a token range, with leaves covering small sub-ranges of keys.
- Replicas exchange trees and walk down to the leaves that differ.
- Only the rows in differing leaves are streamed, and the newest version wins.
This is the repair described in Amazon's Dynamo paper and used by Cassandra and Riak. Cassandra operators must run repair within the tombstone grace period, or deleted data can come back from a replica that missed the delete.
Syncing files
File sync and backup tools use the same idea for files:
- Chunk files into blocks, often with content-defined chunking (boundaries chosen by a rolling hash of the content), so inserting a byte near the start doesn't shift every later block.
- Hash each chunk and describe a file version as its list of chunk hashes.
- Upload only chunks the server doesn't have. Editing one paragraph of a 1 GB file uploads a few MB.
- rsync uses rolling checksums to find matching blocks between two versions without a shared index.
- File size
- 1 GB
- Chunk size~256 chunks
- 4 MB
- Edit touching 2 chunks
- ~8 MB uploaded instead of 1 GB
- Same file uploaded by 1,000 users
- stored once
Content addressing
Content-addressed storage names each object by the hash of its bytes: sha256:9f86d0….
- To store, hash the content and write it under that key. If the key exists, there's nothing to do: deduplication is free.
- To read, fetch by hash and verify the bytes match, so corruption or tampering is detected.
- Mutable names (a branch, a tag,
latest) are small pointers to hashes, updated atomically.
Examples are everywhere:
- Git: files are blobs, directories are trees of hashes, commits point to a tree and parents. A commit hash is the root of a Merkle structure over the whole history.
- Container registries and artifact stores keep layers and builds by digest.
- IPFS addresses files by hashes of Merkle DAGs.
- Build caches key outputs by the hash of all inputs, so identical builds are reused.
Because addressed content never changes, it can be cached forever at CDNs and clients, and replicated without conflicts. The hard parts move to the pointers (updating tags safely) and to garbage collection, finding objects no pointer reaches anymore.
Diverge three nearby rows in a million-row replica and compare the hash walk with a full scan.
Try it
Multi-device File Sync HLD
Sync files across devices, sending only what changed.