Read Repair, Merkle Trees, Anti-Entropy, and Convergence After Missed Writes

Learning outcomes

Replication does not converge merely because the network becomes healthy again. AtlasMart needs explicit mechanisms to find replicas that missed updates and move the missing state. This lesson separates read repair from operator/background anti-entropy repair and uses a small Merkle tree to show why hash trees can localize divergent key ranges.

1. Three convergence paths solve different scopes

Hinted handoff remembers a write for a temporarily unavailable intended replica and tries to deliver it later. Read repair detects disagreement encountered while serving a read and may repair replicas involved in that read. Anti-entropy repair systematically compares broader ranges and transfers missing/different data. Each reduces divergence, but each has gaps.

Read repair is demand-driven: a cold key that nobody reads may remain divergent. Hints can expire, be lost with the hint holder, or cover only a bounded outage window. Range repair is therefore the mechanism that eventually inspects data even when user traffic does not.

2. Merkle trees turn “these replicas differ” into “which range differs?”

A Merkle tree is a hierarchy of hashes. Leaves summarize small key ranges; internal nodes hash their children. If two roots match under the same tree construction, the summarized content matches for that comparison. If roots differ, peers descend only into branches whose hashes differ. That can avoid transferring or hashing every item across the network.

The tree is an index for comparison, not a conflict resolver. Once a mismatching range is found, the system still needs version/timestamp/tombstone semantics to decide which records to stream or reconcile. Tree resolution, partition boundaries, compaction state, and topology changes can affect repair cost.

3. Tombstones make “absence” a replicated state

In eventually convergent stores, deleting a key often creates a tombstone or deletion marker instead of instantly erasing every historical copy. The marker must propagate far enough that a stale replica cannot later reintroduce the old live value. Compaction/garbage collection eventually discards tombstones, but only under assumptions about repair/replica absence.

A dangerous operational pattern is to keep a replica offline beyond the deletion-retention/repair horizon, discard tombstones on healthy replicas, then bring the stale node back and treat its old live value as new evidence. Product implementations have specific safeguards and rules; the generic lesson is that delete retention, repair cadence, restore procedures, and node replacement are one consistency design.

4. Deliberately wrong approach — rely on hints and popular-key reads as “automatic repair”

AtlasMart leaves replica C isolated for days. Hints are no longer available, and the divergent cart range receives little user traffic. A later node replacement copies from inconsistent peers. The team discovers that “eventual” had no deadline because no comprehensive anti-entropy job ever compared that range.

The repair is to define a maximum repair age, monitor successful repair coverage, test the repair process, coordinate repair with topology changes, and keep deletion retention safely aligned with the longest permitted unrepaired interval. Preview/validation tooling can reduce surprise, but repair remains an operational workload with disk/network cost.

5. AtlasMart lab — localize divergence with a hash tree

import hashlib

ranges = {
    "r0": ["cart:1=v4", "cart:2=v3"],
    "r1": ["cart:3=v9", "cart:4=v2"],
    "r2": ["cart:5=v7", "cart:6=v1"],
    "r3": ["cart:7=v5", "cart:8=v6"],
}
replica_a = {k:list(v) for k,v in ranges.items()}
replica_c = {k:list(v) for k,v in ranges.items()}
# C missed one write in r1 and one deletion in r3.
replica_c["r1"][0] = "cart:3=v8"
replica_a["r3"][1] = "cart:8=TOMBSTONE:v7"


def digest(items):
    payload = "|".join(sorted(items)).encode()
    return hashlib.sha256(payload).hexdigest()[:12]


def tree(replica):
    leaves = {r:digest(items) for r,items in replica.items()}
    left = digest([leaves["r0"], leaves["r1"]])
    right = digest([leaves["r2"], leaves["r3"]])
    root = digest([left, right])
    return leaves, {"left":left, "right":right}, root

la, ba, ra = tree(replica_a)
lc, bc, rc = tree(replica_c)
print("root A", ra, "root C", rc, "equal?", ra == rc)
for branch in ("left", "right"):
    if ba[branch] != bc[branch]:
        print("mismatching branch", branch)
for r in ranges:
    if la[r] != lc[r]:
        print("mismatching range", r, "A", replica_a[r], "C", replica_c[r])

print("\nSTREAM DIFFERENCES / REPAIR")
for r in ranges:
    if la[r] != lc[r]:
        replica_c[r] = list(replica_a[r])
_,_,rc2 = tree(replica_c)
print("root C after repair", rc2, "matches A?", rc2 == ra)

print("\nTOMBSTONE WARNING")
print("If the deletion marker is discarded before a stale replica is repaired,")
print("an old live value can be copied back and appear to resurrect deleted data.")
print("This simulator keeps the tombstone as state until convergence is proven.")

Verification checklist

• The roots differ before repair.
• The tree identifies both left and right branch mismatches because two distinct ranges diverged.
• Only ranges r1 and r3 are replaced in the toy repair.
• The roots match after repair.
• The deletion is represented as a tombstone rather than erased from comparison state.

6. Production judgment

Schedule repair based on data criticality, write/delete rate, topology, and the implementation’s documented retention semantics—not a universal interval copied from another cluster. Repair can create I/O and network pressure, so capacity headroom and rate limiting matter. Validate restored/replaced nodes before returning them to normal traffic. Treat repair metadata and administrative endpoints as privileged operational surfaces.

The next lesson combines quorum counts with partitions, slow replicas, coordinator loss, and client timeouts—the cases where request outcome itself becomes ambiguous.

Authoritative references

• Apache Cassandra 5.0 — Repair — current Merkle-tree comparison, streaming, incremental/full repair, and I/O guidance
• Apache Cassandra — Read repair — documented blocking read-repair behavior and monotonic-quorum-read rationale
• Apache Cassandra 5.0 — Hints — current statement that hints/read repair are best effort and not replacements for full repair
• Dynamo: Amazon’s Highly Available Key-value Store — primary Merkle-tree anti-entropy and hinted-handoff reference