Anti-entropy Through Merkle Trees

This lesson covers anti-entropy: the background process Dynamo uses to catch replicas that have quietly drifted out of sync. It repairs them using a structure called a Merkle tree.

Vector clocks catch a conflict the moment a client reads the data. But a replica nobody reads can drift for a long time before that happens, and vector clocks never get a chance to run on it.

What we want is a way to catch that drift and repair it in the background, without waiting for a read. That means comparing two copies of the same range of data, and finding exactly where they differ.

What are Merkle trees?

A replica can hold a lot of data. Comparing it byte by byte would send far more data across the network than the actual difference could justify.

Dynamo solves this with a Merkle tree: a binary tree of hashes. Each leaf node hashes a small portion of the data, and each internal node hashes its two children.

Comparing two Merkle trees follows a simple recursive rule:

1. Compare the root hashes of both trees.
2. If they match, stop. The two ranges are already identical.
3. If they do not match, recurse into the left and right children.

That rule is why replicas never need to send a whole range just to find a difference. They walk down only the branches that differ, so the data exchanged is limited to the actual gap between the two copies.

Merits and demerits of Merkle trees

The advantage is that each branch can be checked on its own, without either side downloading the whole tree or the whole dataset. That keeps both the data transferred and the disk reads during anti-entropy small.

The disadvantage shows up when the cluster changes. Adding or removing a node moves many key ranges at once, and each move forces the trees covering those ranges to be recalculated.