Anti-entropy with Merkle trees

Anti-entropy compares replicas and repairs divergent ranges without scanning and transferring every record. Merkle trees make equality checks hierarchical; they do not decide which value wins.

Comparable snapshots

A root comparison is meaningful only when both sides pin the same:

• token/key range and partition ownership generation;
• snapshot or consistent-cut rule;
• canonical serialization, sort order, and leaf bucket boundaries;
• hash algorithm and tree construction;
• schema and treatment of tombstones/expiry.

Concurrent writes after the cut belong to a later generation. Repair applies versioned or conditional mutations so an older repair value cannot overwrite newer state.

Repair protocol

1. Freeze or identify comparable range snapshots.
2. Build trees from canonical records.
3. Compare roots.
4. Descend only mismatching subtrees.
5. Fetch the actual versioned records for mismatching leaves.
6. Reconcile with the database's conflict/version policy.
7. Verify or schedule another pass.

Hash mismatch identifies a region, not the correct value. Equal roots rely on collision resistance and the shared input contract.

Hinted handoff is not anti-entropy

Hints are a best-effort optimization for temporarily unavailable replicas. Hints can expire, be lost, or become irrelevant after topology changes. Periodic repair is still required.

Deletes and tombstones

A delete marker must participate in tree comparison until every replica that could hold the old value has been repaired or the system's retention assumptions make resurrection impossible. Garbage-collecting tombstones before the maximum safe repair interval can resurrect deleted data.

Capacity and concurrency

Merkle rebuilding, range reads, and streaming compete with foreground traffic. Bound work per range, throttle streams, preserve checksums, and make record application idempotent. Membership changes may invalidate tree/range mappings and require rebuild.

Diagram scenarios

The animation covers equal roots, subtree descent, a concurrent post-snapshot write, best-effort hints, and tombstone repair before garbage collection.

Related concept

Interactive scenarios