Merkle anti-entropy and read repair

Hinted handoff misses cases. A hint can be lost in a crash, or a node can be down for weeks. Some replicas stay wrong until something repairs them. The Dynamo design uses two repairs. Read repair fixes keys that get read. Anti-entropy finds the keys nobody reads.

The big idea

Think of comparing two thick ledgers. You do not read every page. You compare a checksum for the whole ledger. If it matches, you are done. If it does not, you compare checksums for each chapter, then each section. You copy only the pages that differ.

The picture simplifies the tree. Real systems use it over key ranges, which can be large.

Walking through it

Four key ranges, held by replicas A and C. Only range 3 differs.

Compare root hashes          -> differ
Compare left-half hashes     -> same, skip the whole left half
Compare right-half hashes    -> differ, descend
Compare range 3 and range 4  -> range 3 differs, range 4 is the same
Stream only range 3 from A to C

Read repair works differently. On a quorum read, the coordinator sees replicas that disagree. It writes the reconciled value back to the stale ones, often in the background. Read repair is quick for hot keys, but a cold key that is never read stays wrong.

Here is the failure that anti-entropy covers. A cart was written with W = 2 while node C was down. Its hint was lost in a crash. Weeks later, a Merkle comparison between A and C finds the range differs. It streams the missing version to C. A later read with R = 2 no longer depends on luck.

Common mistakes

• Relying on read repair alone. Cold keys stay wrong until something reads them.
• Deleting tombstones too early. A replica that missed the delete can bring the deleted key back. Keep tombstones until every replica has seen the delete.
• Assuming hints survive crashes. They are a best effort, and anti-entropy is the safety net.

Check yourself

1. Why compare Merkle trees instead of full datasets? Matching subtrees are skipped. Only the ranges that differ are sent over the network.
2. Which repair fixes a key that nobody reads? Anti-entropy, because it scans the ranges in the background and does not wait for a read.

Key takeaways

• Read repair fixes keys during reads. Anti-entropy fixes cold keys in the background.
• A Merkle tree finds the differing ranges with few comparisons.
• Repairs send only the data that differs.
• Tombstones must outlive any replica that might still need them.

Further learning

Next, see how the system tells an overwrite from a conflict, in Dynamo vector clocks.

Werner Vogels reflects on a decade of the Dynamo design in this post.

A Decade of Dynamo (Werner Vogels)Today marks the 10-year anniversary of AmazonAll Things Distributed