Stackbook Logo
data-consistencyestablished · medium operational burden

Anti-Entropy with Merkle Trees

Also known as: merkle-tree-repair, replica-repair, anti-entropy

Intent

Detect and repair divergence between replicas efficiently by comparing hash trees instead of full datasets.

Problem

Replicas drift apart because of missed writes, dropped hints and bit rot. Comparing entire datasets to find differences wastes bandwidth and time. A background process must find only the differing ranges.

Forces

  • •Datasets are huge and mostly identical
  • •Comparison traffic must be small
  • •Repair must not disrupt foreground traffic
  • •Updates continue during comparison

Solution

Overview

Anti-entropy is a background process that makes replicas converge by actively comparing their contents. Merkle trees make the comparison cheap: matching hashes at the top prove entire ranges equal. Cassandra, Riak and DynamoDB-style stores use it as a safety net behind read repair and hints.

How it works

        root = H(h1 + h2)
        /               \
   h1 = H(a+b)      h2 = H(c+d)
   /      \          /      \
  a        b        c        d      (hash of key buckets)

Replica X and Y compare roots -> differ
compare h1: same ; compare h2: differ
compare c: same ; d: differ -> stream keys in bucket d

Each replica builds its tree for a token range, usually via a validation scan. Trees have fixed depth, such as 15 levels, so each leaf covers a range of keys. After diffing, the replicas exchange the keys in mismatched leaves and keep the version with the newest timestamp or merged value.

Pitfalls

  • Run full repair within the tombstone grace period, otherwise deleted data can return from replicas that never saw the delete.
  • Building trees scans data and consumes IO; schedule off-peak and repair ranges incrementally.
  • Coarse leaves over-stream; very fine trees cost memory.
  • Trees reflect a snapshot; data written during the scan appears as spurious difference next round.
  • Repairing one node at a time is slow; use token-range parallelism with limits.

Key takeaways

  • Merkle trees find differences in logarithmic comparison cost.
  • Anti-entropy complements, not replaces, read repair and hinted handoff.
  • Schedule regular repairs within the delete grace period.

✓ When to Use

  • •Leaderless replicated stores needing eventual convergence
  • •After node outages longer than hint windows
  • •Detecting silent data corruption between replicas

✗ When Not to Use

  • •Small datasets where full comparison is cheap
  • •Systems with strongly consistent replication logs
  • •Highly write-hot ranges that change faster than trees rebuild

Pros

  • +Transfers only differing data
  • +Logarithmic comparison cost
  • +Guarantees eventual convergence even for cold data

Cons

  • −Tree building costs CPU and IO
  • −Trees go stale as data changes
  • −Repair traffic competes with production load

Cost Profile

Infrastructure

Extra IO and CPU during repair windows

Operational

Medium: schedule and monitor repairs

Cognitive

Medium: tree granularity tuning

Failure Modes

  • Repairs skipped beyond tombstone grace period resurrect deleted data

  • Tree resolution too coarse streams excess data

  • Concurrent writes make trees stale and cause repeat repair

Real-World Examples

Alternatives

    Related Patterns

    • replication
    • hinted-handoff
    • quorum-reads-writes
    • consistent-hashing

    Competency Domains

    data statereliability ops