Anti-Entropy and Merkle Trees

Define the problem

Replicas drift apart in ordinary operation. A write misses a replica that was restarting, and a copy promised for later delivery never arrives.

Repairs that happen during reads only fix values that somebody reads. A cold value, one nobody asks for, can stay wrong on one replica for months.

The store needs a repair that runs whether or not anyone reads. It also needs that repair to be cheap, because comparing two full datasets is far too much data to move.

Checksums and the Merkle tree

A checksum is a short number computed from a block of data. Change any part of the data, and the number changes with it.

A Merkle tree organises checksums over a replica's keys. The keys are split into ranges, and each leaf of the tree holds the checksum of one range's data.

Each parent in the tree holds a checksum computed from its children's checksums. The root, at the top, is one number that summarises the entire dataset.

Two replicas with the same data build the same tree. Two replicas that differ anywhere build different roots.

Comparing two trees

The comparison starts at the root. Equal roots end the conversation, because everything below them already agrees.

Different roots send the comparison one level down. The replicas compare the children, keep the branches that match, and descend only into the branches that differ.

At the leaves, the replicas know exactly which key ranges disagree. They copy the missing or newer versions for those ranges only, in both directions.

Take a demo tree with 16 children per node and 5 levels. It has 16 × 16 × 16 × 16 × 16 = 1,048,576 leaves, about a million key ranges.

Finding one differing range costs 16 comparisons per level × 5 levels = 80 checksum comparisons.

Sending the data itself instead would move 1,000,000 records × 1 KB = 1,000,000,000 bytes, about 1 GB, to learn the same thing.

The repair run

Anti-entropy runs on a schedule in the background. Pairs of replicas are chosen in turn, often using the gossip protocol to spread the pairing fairly.

Each pair exchanges trees, finds its differing ranges, and streams the missing versions across. Both replicas end the run holding the union of what either one had.

The run is throttled on purpose. It takes spare bandwidth and spare disk time, and it yields whenever real reads and writes need the machine.

Deleted values take part like any other data. A delete leaves a marker behind, and the marker is compared and copied too, or a deleted value would quietly return from a replica that missed the delete.

Where it breaks

The tree is a snapshot. Data that changes while two replicas compare can make a range look different when it is only newer, so runs compare versions, not just presence.

Rebuilding a tree over fast-changing data is itself work. Stores update the tree as writes land, and rebuild it rarely, to keep the cost steady.

Repair is eventual, never instant. Between runs, replicas can disagree, and a read in that window can still meet a stale copy.

A checksum collision, two different blocks with the same number, is possible in theory. Wide checksums make it so unlikely that stores treat equal checksums as equal data.

Trade-offs and wrap-up

Anti-entropy is the repair of last resort. It covers the cold data and the lost hints that no read will ever trigger a fix for.

Its cost is a steady background tax. Trees must be built, comparisons must run, and differing ranges must stream, forever, even when nothing is wrong.

The tuning knob is frequency. Frequent runs close the disagreement window quickly and tax the cluster more. Rare runs are cheap and let drift live longer.

Replicas will drift, so the store schedules the comparison that finds the drift, and the Merkle tree makes that comparison cheap enough to run forever.

Finding one difference