Permanent Failures: Anti-Entropy with Merkle Trees

In one line: hinted handoff covers a node that comes back quickly. This covers a node that comes back a week later, or gets replaced entirely — and it does so without shipping the whole dataset across the network to find out what changed.

The structure

A Merkle tree (or hash tree) organizes data hashes hierarchically:

• Leaves contain hashes of individual key values.
• Parent nodes contain hashes of their children.

Each leaf H1..H8 is the hash of a key's value (K1..K8); each parent hashes its two children; the root summarizes everything below it.

The essential property: a Merkle tree allows nodes to verify subtrees independently. If the root hashes match, the datasets are identical. If they differ, the nodes recursively compare child hashes to identify the specific key ranges that diverge — without transferring the entire dataset to make the comparison.

Anti-entropy in practice

Each node maintains a Merkle tree for the key ranges it hosts. Because of virtual nodes, that means several trees — one per range:

Node A owns virtual nodes: [N1, N3, N5]
  N1 -> range [r+1, s]
  N3 -> range [m+1, n]
  N5 -> range [o+1, p]

Node B owns virtual nodes: [N2, N4, N6, N7]
  N2 -> range [0, m]
  N4 -> range [n+1, o]
  ...

To synchronize, two nodes exchange the root hashes of their trees:

1. Compare root hashes. If they match, the data is consistent and no further action is needed.
2. Traverse the tree. If the hashes differ, recurse down the left and right children.
3. Synchronize. Identify the specific leaves that differ and transfer only the missing or inconsistent data.

Why this is such a good idea

Step 1 is the payoff. A single hash comparison — a few dozen bytes — proves that two replicas holding gigabytes are identical. In the common case, where nothing has diverged, anti-entropy costs almost nothing.

And when something has diverged, the cost of finding it is logarithmic rather than linear: each level of recursion halves the search space, so locating one bad key among a million takes about twenty hash comparisons rather than a million value comparisons.

That combination — free when equal, cheap when not — is why Merkle trees appear in Dynamo, Cassandra, Git, and blockchains alike.

The trade-off

The disadvantage interacts badly with virtual nodes

Recall that virtual nodes mean each physical machine owns many small ranges. So a single node joining changes the boundaries of several ranges across several machines — and every affected tree must be rebuilt from its leaves up.

That is real work, and it is the reason the next lesson insists the system should not rebalance immediately when a node appears to fail. Recomputing trees for a node that was merely rebooting is expensive and pointless.

The mechanisms in this chapter are coupled: the cost of anti-entropy is part of why membership changes are deliberately conservative.

Deleting is a write, and it has to be

Anti-entropy repairs divergence by copying what one replica has and another lacks. That works beautifully for creates and updates, and it breaks catastrophically on deletes — unless the delete is stored.

Consider deleting a key while one replica is unreachable.

The mechanism has no way to tell "this key was deleted" from "this key never arrived". Absence carries no information, and repair is built to eliminate absence. So a genuine delete looks exactly like a replica that fell behind, and the system helpfully undoes it.

The fix is that a delete does not remove anything. It writes a marker — a tombstone — that says this key was deleted, at this version. Now the delete is a value like any other: it replicates, it participates in conflict resolution, and it wins over the older live value because it is newer.

Tombstones cannot live forever, and cannot be removed early

That creates the second problem, and it is a genuinely awkward one.

The resolution is a grace period: tombstones are retained for longer than the maximum time a replica can be absent and still rejoin, then collected during compaction. The number is an operational commitment, not a tuning knob — it says "a node offline longer than this must be rebuilt from scratch rather than repaired", because after that window its data cannot be trusted to be missing rather than deleted.

Two consequences worth volunteering, because they surprise people:

A delete-heavy workload gets slower, not faster. Deleting a million keys writes a million tombstones, and until compaction clears them reads still have to traverse them. Freeing space costs space first.

Deletion is not immediate at the storage layer, which matters for a compliance requirement to erase data. The key becomes unreadable at once, but the bytes persist until compaction — the same distinction the blob store drew between inaccessible and reclaimed, arrived at from a different direction.

Interview signal by level

Next: knowing which nodes are actually there.