Anti-Entropy
Anti-entropy is background reconciliation that compares replicas and repairs differences, catching writes missed during failures, partitions, or dropped hints.
Definition
Anti-entropy is a set of background processes that detect and repair divergence between replicas. It typically compares digests or Merkle trees of data ranges, identifies mismatched keys, and exchanges the missing or newer values. It complements write-time replication and hinted handoff, which cannot cover long outages or lost hints.
Context and scope
Eventually consistent stores accept that replicas can diverge. Anti-entropy is how they converge without waiting for every write to reach every node. It is also relevant to backups, caches, and search indexes that must be reconciled with a source of truth.
Common misconceptions
- Anti-entropy runs continuously and repairs every write immediately.
- If hinted handoff is enabled, periodic repair is unnecessary.
Anti-patterns
- Never running repair and assuming replication factor alone guarantees durability.
- Running full repairs during peak traffic with no throttling or time bounds.
Related concepts
Authoritative source
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
How it works
Two replicas need to find differences without transferring the entire dataset. They build a Merkle tree: leaves hash individual keys or ranges, and parents hash their children. Comparing root hashes is cheap; if they match, the replicas agree. If not, the comparison descends only into differing branches, and the replicas exchange the affected rows. The result is a bounded transfer proportional to the divergence, not the data size.
Repair can be full or incremental. A full repair scans all ranges, which is expensive but thorough. Incremental repair tracks repaired ranges and focuses on recent writes, but it depends on metadata accuracy and tombstone handling. Some systems stream a snapshot and compare it with the live replica, then apply missing mutations.
Deletes and tombstones
Deletes complicate reconciliation. If a replica removes a key and later receives an old value from a peer, the value can resurrect. Stores therefore write tombstones with a grace period longer than the maximum expected repair interval. Running repair less often than the tombstone grace period can resurrect deleted data.
When to use it
Use anti-entropy for any eventually consistent store where durability and convergence matter: Cassandra, Riak, Dynamo-style systems, and multi-region caches. Also use reconciliation jobs for derived stores such as search indexes or materialized views, where the source may have changed while the index was unavailable.
Trade-offs and example
Repair consumes disk I/O, network bandwidth, and CPU, and can affect latency. Scheduling it off-peak and throttling helps. Merkle trees reduce transfer but require stable range boundaries and consistent hashing. Full repair is simpler and more trustworthy; incremental repair is faster but easier to get wrong.
Example: a node is offline for two days, beyond the hint window. A repair compares Merkle trees per token range, finds 40,000 mismatched keys, and streams only those rows. Without repair, those writes would remain missing indefinitely even though the cluster appears healthy.