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.