Anti-Entropy
A background process that compares data between replicas and fixes differences. Uses Merkle trees to efficiently identify which data ranges are out of sync.
What is Anti-Entropy?
In short
Anti-entropy is a background repair process in distributed databases that periodically compares the data stored on different replicas and copies over whatever is missing or stale so all copies converge to the same state. It typically uses Merkle trees to find the exact ranges that differ without comparing every record one by one.
What anti-entropy actually is
In a system that keeps several copies of your data on different machines, those copies drift apart over time. A write might reach two replicas but not the third because a node was rebooting, a network link dropped, or a message was lost. Read repair fixes some of this on the fly, but only for keys someone actually reads. Anti-entropy is the background job that fixes the rest, including data nobody has touched in months.
The name comes from physics. Entropy is the tendency of a system to fall into disorder. Replicas naturally diverge, which is the disorder. Anti-entropy is the counter-force that keeps pulling them back into agreement.
It is the safety net that lets a database promise eventual consistency. Even if every other repair mechanism misses an update, the anti-entropy sweep will eventually find the difference and heal it, so given no new writes all replicas converge to the same value.
How it works under the hood with Merkle trees
The naive approach is to ship every key and value from one replica to another and diff them. For a node holding hundreds of gigabytes that is far too much network traffic to run often. Merkle trees solve this.
Each replica hashes its keys in a range, then hashes those hashes upward into a tree where every parent node is the hash of its children, ending in one root hash. Two replicas first compare just the root. If the roots match, the entire range is identical and nothing needs to move. If they differ, they walk down the tree comparing child hashes, descending only into the branches that disagree. This turns a full data scan into a logarithmic search, so two terabytes of mostly-identical data can be reconciled by exchanging a few kilobytes of hashes plus only the records that genuinely differ.
Once the differing leaf ranges are found, the replicas exchange the actual rows for just those keys and resolve conflicts using whatever rule the database has, such as last-write-wins by timestamp or version vectors. The repaired data is then written back so the next comparison finds the trees in agreement.
When to use it and the trade-offs
Anti-entropy is the right tool whenever you run multiple replicas and need a guarantee that they converge even for cold data that is rarely read. It is essential in leaderless and multi-master systems where no single node is the authority and writes can land anywhere.
The cost is real. Building Merkle trees burns CPU and memory, and the comparison and row transfer use disk and network bandwidth that competes with live traffic. Run it too aggressively and you slow down user requests. Run it too rarely and divergence lingers, which means stale reads persist longer. Most systems schedule it as a slow continuous sweep or a periodic job during quieter hours, with throttling so it yields to foreground work.
It also does not give you strong consistency. Anti-entropy heals differences after the fact, so there is always a window where replicas disagree. If you need every read to reflect the latest write immediately, you want synchronous replication or quorum reads, not anti-entropy alone. The two are complementary: quorums catch most staleness at request time, anti-entropy catches the long tail in the background.
A concrete example
Apache Cassandra runs anti-entropy through a process called repair, triggered by the nodetool repair command or scheduled automatically. Each node builds a Merkle tree over its token ranges, neighbors compare trees, and only the mismatched ranges are streamed between nodes. A common operational rule is to run repair on every node at least once within the gc_grace_seconds window, which defaults to ten days, to prevent deleted data from resurrecting as zombies.
Picture a three-node cluster with replication factor 3. A user updates their email, but node C is briefly partitioned and misses the write. Reads from A and B return the new email; a read served by C alone could return the old one. When the next repair runs, A and C build Merkle trees, the root hashes disagree, they descend to the one leaf range holding that user, exchange just that record, and C adopts the newer version by timestamp. Now all three nodes agree and the divergence is gone without anyone having to read that key again.
Where it is used in production
Apache Cassandra
nodetool repair builds Merkle trees per token range and streams only mismatched ranges between replicas to converge them.
Amazon DynamoDB
The original Dynamo paper specified anti-entropy with Merkle trees as the background mechanism that keeps leaderless replicas in sync.
Riak
Ships Active Anti-Entropy, which keeps persistent Merkle-style hash trees so background repair can run continuously with low overhead.
ScyllaDB
Cassandra-compatible store that runs the same repair-based anti-entropy, with a row-level scheme to reduce overstreaming of unchanged data.
Frequently asked questions
- What is the difference between anti-entropy and read repair?
- Read repair fixes inconsistencies only for keys that are actively being read, and it happens during the request. Anti-entropy is a separate background sweep that compares whole ranges of data and fixes everything, including cold keys nobody has read. You usually want both: read repair for the hot path, anti-entropy for the long tail.
- Why use Merkle trees instead of comparing all the data?
- Comparing every key and value between replicas would move enormous amounts of data over the network. A Merkle tree lets two nodes compare a single root hash first and then descend only into the branches that differ, so identical data is confirmed by exchanging a few hashes instead of gigabytes of records.
- Does anti-entropy give me strong consistency?
- No. It repairs differences after the fact, so there is always a window where replicas disagree. It is what makes eventual consistency actually eventual. If you need a read to always reflect the latest write, combine it with quorum reads and writes or use synchronous replication.
- How often should anti-entropy run?
- It is a trade-off. Running it often keeps replicas tightly in sync but competes with live traffic for CPU, disk, and bandwidth. Running it rarely is cheaper but leaves divergence around longer. In Cassandra a common rule is to repair every node at least once inside the gc_grace_seconds window, ten days by default, to avoid deleted data resurrecting.
- What is a zombie or resurrected record, and how does repair relate to it?
- In systems that mark deletions with tombstones, a delete that does not reach every replica can be undone if the tombstone is garbage-collected before all nodes learn about it. The old value then reappears as a zombie. Running anti-entropy repair before tombstones expire propagates the deletion everywhere and prevents this.
Learn Anti-Entropy hands-on
This page explains the idea. The full lesson lets you step through the ring as servers join and leave, read the implementation, and check yourself with a quiz. It is one of 760+ lessons in the System Design Masterclass, from your first API call to distributed consensus. Eleven Foundation lessons are free, no signup. Lifetime access is ₹499 in India or $7.99 worldwide, one payment, no subscription.
Related lessons
Lessons that touch on Anti-Entropy as part of a larger topic.
See also
Related glossary terms you might want to look up next.
Read Repair
A technique where a read operation detects stale data on a replica and triggers a background update to bring it in sync. Used by Cassandra and DynamoDB to heal inconsistencies lazily.
Gossip Protocol
A peer-to-peer communication protocol where nodes share information with random neighbors, spreading it like gossip. Used for cluster membership and failure detection.
Eventual Consistency
A consistency model where updates propagate asynchronously and all replicas will eventually converge to the same value. Trades immediacy for availability.
Strong Consistency
A guarantee that after a write completes, all subsequent reads will return the updated value. Safer but slower than eventual consistency.
Linearizability
The strongest consistency guarantee: every operation appears to take effect atomically at some point between its invocation and completion. As if there's a single copy of the data.
Serializability
A guarantee that concurrent transactions produce the same result as if they were executed one at a time in some serial order. The gold standard for database transaction isolation.