We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningAdvanced · Consistency Models
A background process that compares data between replicas and fixes differences. Uses Merkle trees to efficiently identify which data ranges are out of sync.
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.
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.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Anti-Entropy across a run of lessons, not one page. These 4 alone are about 124 minutes of step-by-step reading, 1 of them with code you run in the browser, all with a quiz.
Background repair using Merkle trees, the last line of defense against data divergence.
Hash trees that verify data integrity and enable efficient synchronization, powering Git, blockchains, and distributed databases.
How read repair fixes stale replicas during a quorum read in Dynamo-style databases. Compares blocking and background repair, and other repair tools.
Partitioning by contiguous value ranges, the go-to strategy for time-series data, logs, and anything with a natural ordering.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Anti-Entropypay once,
yours for life
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
This page explains the idea. The "Anti-Entropy" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Anti-Entropy lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Anti-Entropy in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
