Notesreplication🌱 seedling
Anti-Entropy
Also: Anti-Entropy Repair · Merkle Tree Repair · Merkle Tree
A background process that compares replicas and copies over whatever is missing. Merkle trees of hashes make the comparison cheap: descend only into subtrees whose hashes differ.
Why it exists
Read repair fixes only what's read, and hints are best effort. Something must guarantee that every replica eventually holds every write, including deletes.
How it works
- Each replica builds a Merkle tree over a key range: leaves hash sub-ranges of keys, parents hash their children.
- Two replicas compare roots. Equal: done. Different: compare children, and recurse only into mismatches.
- Only the leaf ranges that differ have their keys exchanged; each side keeps the newer versions.
- Unlike a leader's log, there's no order: missing writes are copied in any order.
Trade-offs
| Gains | Costs |
|---|---|
| finds differences with a few hash exchanges | building trees costs CPU and disk I/O |
| fixes cold data and missed deletes | must be scheduled and monitored |
In practice
- Cassandra
nodetool repairbuilds Merkle trees per token range. Incremental repair (default) only checks data since the last repair, so occasional full repairs are still needed. Repair each node at least every 7 days with the default 10-daygc_grace_seconds, or deleted data can resurrect.
Pitfalls
- Zombie data: if a replica missed a delete and repair doesn't run before the tombstone is purged, repair later copies the deleted value back everywhere.
Connections
- Part of
- Leaderless Replication
Recall
These cards are also in your review deck, scheduled with spaced repetition.