System Design Cases
Anti-Entropy with Merkle Trees
Anti-entropy reconciliation between two replicas using Merkle trees: full repair (root match), partial diff (recurse into mismatched subtree), hinted handoff (short outage), and tombstone resurrection anti-pattern (skipped repair past gc_grace_seconds).
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
- Freeze or identify comparable range snapshots.
- Build trees from canonical records.
- Compare roots.
- Descend only mismatching subtrees.
- Fetch the actual versioned records for mismatching leaves.
- Reconcile with the database's conflict/version policy.
- 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.