Anti-Entropy and Data Repair

Replication propagates new writes to replicas, while repair identifies and eliminates discrepancies that have already occurred. Nodes being offline for extended periods, expired hint records, interrupted migrations, or media corruption can all leave issues unaddressed by normal request paths.

Read repair in the read-write path only covers accessed data and the replicas participating in the read. Anti-entropy proactively compares data ranges co-responsible by replicas, bringing cold data into the inspection scope. It is not a specific command, but a class of mechanisms that bring replicas back into consistency.

Conditions Required for Convergence

Assume both replicas eventually receive the same set of updates. If they use the same and appropriate conflict resolution rules, they should produce the same state. To achieve this, at least the following are required: updates must eventually become reachable, discrepancies must be detectable, repairs must have resources to execute, and deletion and version information must not be discarded prematurely.

Therefore, eventual consistency does not mean "it will fix itself if left alone." Permanent network partitions, repairs being perpetually starved of resources, or differing version comparison rules can all prevent convergence. Operational guarantees for these prerequisites are themselves part of the consistency design.

Merkle Tree: Excluding Identical Ranges Using Digests

Exchanging entire datasets item by item can identify discrepancies, but the transmission cost is high. A Merkle tree maps data ranges under the same partitioning to leaf digests, then recursively hashes child digests to form parent digests. If the root digests match, assuming negligible hash collisions and consistent encoding, the entire range can be skipped; otherwise, the process descends into different subtrees.

Both sides of the comparison must use the same key ranges, ordering, encoding, and version semantics. If one side includes tombstones in the hash while the other only hashes current values, digest differences may stem from comparison rules rather than replica faults.

The role of the tree is to reduce unnecessary exchanges, not to turn all repair costs into O(log n). Building digests for n records typically requires scanning the corresponding data at least once; locating a single local discrepancy can descend along the tree height, but numerous discrepancies will touch many nodes, ultimately requiring the transmission of actual records. If the tree is maintained persistently, updates also incur additional costs.

Locating One Discrepancy Using Eight Fixed Ranges

Below, both parties pre-agree on eight ranges, each storing records sorted by key, with the record format being (key, version, value). The model uses only strings, integers, and null; both parties share a JSON encoding convention, with type prefixes added to leaf and internal nodes respectively. This way, what is compared is not just the current value, but also version and deletion information.

from hashlib import sha256
import json

def tree(ranges):
    n = len(ranges)
    if n == 0 or n & (n - 1):
        raise ValueError("This example requires the number of ranges to be a power of 2")
    nodes = [b""] * (2 * n)
    for i, records in enumerate(ranges):
        data = json.dumps(sorted(records, key=lambda r: r[0]),
                          ensure_ascii=True, separators=(",", ":")).encode("ascii")
        nodes[n + i] = sha256(b"leaf:" + data).digest()
    for i in range(n - 1, 0, -1):
        nodes[i] = sha256(b"node:" + nodes[2*i] + nodes[2*i+1]).digest()
    return nodes

def differences(left, right):
    if len(left) != len(right):
        raise ValueError("Tree range partitioning must be consistent")
    n, compared, changed = len(left) // 2, 0, []
    def visit(i):
        nonlocal compared
        compared += 1
        if left[i] == right[i]:
            return
        if i >= n:
            changed.append(i - n)
        else:
            visit(2*i)
            visit(2*i+1)
    visit(1)
    return changed, compared

A = [[(f"k{i}", 1, "old")] for i in range(8)]
B = [list(records) for records in A]
B[6] = [("k6", 2, "new")]
assert differences(tree(A), tree(B)) == ([6], 7)
assert differences(tree(A), tree(A)) == ([], 1)
C = [[(f"k{i}", 2, "new")] for i in range(8)]
assert differences(tree(A), tree(C)) == (list(range(8)), 15)
assert tree([[("k", 1, "same")]]) != tree([[("k", 2, "same")]])
assert tree([[("k", 2, None)]]) != tree([[]])  # Tombstone is not equivalent to no record
assert tree([[('b', 1, 'v'), ('a', 1, 'v')]]) == tree([[('a', 1, 'v'), ('b', 1, 'v')]])

With one discrepancy, 7 pairs of digests are compared: once at the root, comparing two children at each level, for a total of three levels. Matching subtrees in ranges 0–3 and 4–5 are no longer expanded, ultimately locating only range 6. When all eight ranges differ, all 15 nodes must be compared; "tree height is only 3" does not mean all discrepancies cost only 3 comparisons.

The count includes only digest comparisons between two already built trees, excluding the scanning, sorting, hashing of each range, and the transmission of discrepancy records. A single leaf range may contain millions of records; even after locating the leaf, further comparison is still required. Range boundaries must be fixed by identical metadata; they cannot be split equally by count if the number of records on both sides differs, otherwise leaves at the same position would no longer represent the same set of keys.

How much can a tree skip as differences grow?

Matching digests permit pruning; a mismatch only justifies further comparison and does not identify the newer replica. Both trees below use SHA-256. One changed leaf exposes its search path; all changed leaves touch all 15 nodes. Short hashes are display-only, equality uses full digests, and counts cover comparison of already-built trees.

From Detecting Differences to Deciding How to Repair

Assume in a certain range, A has key=X, version=7, and B has version=5. Only when the version rules prove that 7 supersedes 5 can 7 be treated as the new state. When two vector clocks conflict, digests only tell us that differences exist; they cannot choose the winner for the application.

Repair must use the same merge rules as normal writes. If the business retains concurrent siblings, repair should propagate necessary versions; if Last-Writer-Wins (LWW) is adopted, one must accept its timestamp ordering and semantics of discarding concurrent values. See Conflict Resolution for details.

Gossip can propagate membership or scheduling information, while anti-entropy handles data discrepancies; the two can be combined, but not all Merkle repairs are driven by gossip. The idealized number of rounds for message diffusion cannot be directly equated to the database repair time including scanning, transmission, and merging.

Why Deletions Must Also Be Replicated: Tombstones

If a deletion only removes the record locally, it cannot tell a replica still holding the old value "this record has been deleted." Tombstone retention preserves the fact of deletion, allowing merge rules to determine that the old value should be overwritten.

Consider A and B having recorded the deletion, while C remains offline holding the old value. If A and B clear the unique deletion evidence before C returns, subsequent repairs might propagate C's old value back. This is the tombstone resurrection problem.

Tombstone retention period, maximum offline time, repair coverage cycle, and node rejoining strategy must work in coordination. Simply setting an expiration parameter very large is not a panacea: one must prove that relevant replicas have received the deletion, or force a full rebuild upon rejoining. See Repair for Cassandra's repair and tombstone constraints.

Tombstone Retention is a Versioned Fact

For simplicity, consider strictly increasing versions for the same key: version 5 is the old value, version 6 is the deletion. None indicates that the replica has no record; (6, None) represents the deletion fact of version 6.

def merge(a, b):
    candidates = [record for record in (a, b) if record is not None]
    return max(candidates, key=lambda record: record[0]) if candidates else None

old = (5, "value")
deleted = (6, None)
assert merge(deleted, old) == deleted
assert merge(None, old) == old  # Prematurely losing deletion evidence lets the old value win again
assert merge(deleted, (7, "recreated")) == (7, "recreated")

The third assertion is also critical: a tombstone does not mean "this key is permanently forbidden in the future." When the business allows recreation, a new valid version can overwrite the deletion; what is prevented is the resurrection of the old value. If actual systems allow different content for the same version, they must also define deterministic conflict rules and cannot directly apply this function that only compares version numbers.

Safe cleanup requires covering the evidence: relevant old replicas have received the deletion, or are excluded and fully rebuilt upon rejoining. Seeing that the digests of two online replicas match does not mean the long-offline third replica is safe. Therefore, repair completion records must include the replica set and range, not just a cluster-level "last successful time."

Full, Incremental, and Node Rebuild

These names have different implementations across products. Cassandra's repair and rebuild are not interchangeable, and incremental repair is not equivalent to reading a generic change log. Consult deployment version documentation for operation scopes and version constraints.

Performing digest comparisons under continuous writes also requires a consistent data view or version snapshot. Otherwise, just after comparing root digests, data may change again; repeated scanning might mistake active writes for unrecoverable discrepancies. Snapshots, phased protocols, or re-validation are used to define the coverage boundaries of this round.

Strong Consistency Replication Also Requires Recovery and Integrity Checks

Consensus protocols maintain log order and commit safety under their own failure models; lagging followers can catch up on logs or install snapshots. However, silent disk corruption, incorrect software apply, or backup corruption may exceed protocol assumptions.

Therefore, one cannot write "with Raft, data verification is unnecessary." Log catching up, state snapshots, checksums, and replica consistency checks solve problems at different levels. Repair success should also verify logical state, not just that network transmission returned success.

Estimating Repair Budgets

Assume a round requires transmitting 600 GB of discrepancy data. Allocating a sustained bandwidth of 50 MB/s for repair, transmission alone theoretically takes about 12,000 seconds, i.e., 3.3 hours, not including digest construction, disk reads, and merging. If completion is required within two hours, the current budget is clearly insufficient.

If discrepancies are generated at 10 MB/s during repair, the net elimination rate is only 40 MB/s. Calculating all quantities in decimal GB and MB:

from fractions import Fraction
backlog = 600 * 10**9
repair_rate, new_difference_rate = 50 * 10**6, 10 * 10**6
assert Fraction(backlog, repair_rate) == 12000
assert Fraction(backlog, repair_rate - new_difference_rate) == 15000
hours = Fraction(15000, 3600)
assert hours == Fraction(25, 6)  # Approximately 4.17 hours
required_rate = Fraction(backlog, 2 * 3600) + new_difference_rate
assert required_rate == Fraction(280_000_000, 3)  # Approximately 93.33 MB/s

Therefore, clearing the backlog within two hours requires an effective repair throughput of approximately 93.33 MB/s, not accounting for additional I/O bottlenecks. If the discrepancy generation rate reaches or exceeds the repair rate, this steady-state model has no finite catch-up time. The "new discrepancies" here refer to bytes that have not yet reached the target replica and truly require repair; one cannot directly substitute the entire business write throughput; compaction and update coverage may also change the actual bytes to be transmitted.

Such estimates are used to reverse-engineer parallelism, run windows, and resource margins. Repair throttling that is too low may never catch up with new discrepancies, while being too high competes with online reads and writes for disk and network resources. One must monitor scanning, streaming, merging, and uncovered ranges separately; simply seeing "task started" is insufficient.

Complete acceptance should answer: which token/key ranges were compared and when; which replicas participated; were there any skips or failures; could coverage be completed before the tombstone retention period expired; did post-repair digest or version checks pass?

References

• Dynamo: Replica Synchronization using Gossiping Merkle Trees
• Cassandra: Repair
• Cassandra: Read Repair
• Cassandra: Hints

Keywords: anti-entropy, Merkle tree, convergence, tombstone, tombstone resurrection, full repair, incremental repair, rebuild