Anti-Entropy and Merkle Trees

Imagine a 1 TB Cassandra table spread across three replicas. A network partition isolates one replica for two hours. Writes continue on the other two. When the partition heals, the isolated replica is behind — but only on the 0.1% of keys actually written during those two hours. That is 1 GB of divergence inside 1 TB. Where is that 1 GB?

You have no idea. The isolated replica does not know which writes it missed. The other two do not know which keys the isolated one failed to receive — the data is just "in the SSTables" mixed with everything else. There is no log of "these are the keys that changed during the partition." The only honest answer is: compare.

Naive comparison is arithmetic — for every key, fetch the value from both replicas, compare, overwrite if different. That is 2 TB of disk reads, up to 2 TB of network, hours of CPU, across every pair of replicas every repair cycle. A 30-node cluster with replication factor 3 has 30 such pairs — tens of terabytes of cross-cluster traffic to fix a gigabyte of actual divergence.

The Merkle-tree approach starts with 32 bytes. Each replica has a pre-computed root hash summarising its entire state. Roots match: replicas identical, done, zero data transferred. Roots differ: each sends its two children — 64 bytes. Children match: prune. Children differ: recurse. Localising the 1 GB of divergence costs about 100 KB on the wire. Only then does a targeted transfer move the actual gigabyte.

The asymmetry is dramatic. Naive comparison scales with dataset size; Merkle comparison scales with divergence size times a logarithmic factor. In a healthy cluster, the dominant case is "root hashes match, stop." That case is free.

Why "anti-entropy"

The term comes from Demers et al.'s 1987 PODC paper Epidemic Algorithms for Replicated Database Maintenance, written at Xerox PARC while they were building the Clearinghouse directory service. A distributed system has an entropy — the amount of disagreement between replicas. Every missed write, dropped message, or brief partition adds entropy. Mechanisms that reduce it — push writes that other replicas lack, pull writes from replicas with more — are anti-entropy.

The paper separates anti-entropy into three patterns: push (A sends B its recent updates), pull (A asks B "what do you have that I don't?"), and push-pull (they exchange summaries, then trade differences). Merkle-tree comparison is push-pull anti-entropy: the summary is a tree of hashes, the "trade" is the recursive descent. Dynamo borrowed the vocabulary directly. Cassandra's nodetool repair is push-pull anti-entropy.

Why the thermodynamic metaphor sticks: in a closed system with no input, entropy never decreases — the second law. Distributed replicas without a reconciliation mechanism drift forever; any noise (packet loss, clock skew, disk errors) increases divergence monotonically. You need an active process pumping order back in. Anti-entropy is that pump.

The Merkle-tree data structure

Ralph Merkle invented the tree that bears his name in his 1979 Stanford PhD thesis and again in his 1987 Crypto paper A Digital Signature Based on a Conventional Encryption Function. The motivation was cryptographic — efficient authentication of large datasets — but the data structure itself is simple enough to describe in a paragraph.

A Merkle tree is a binary tree with two invariants:

1. Leaves hash actual data. Each leaf corresponds to some piece of the underlying state — in a database context, usually a range of keys — and stores a cryptographic hash of that piece. For key range [000..., 3FF...), the leaf stores H(sorted list of all key-value pairs in that range).
2. Internal nodes hash their children. An internal node stores H(left_child.hash || right_child.hash) — literally hash the concatenation of its children's hashes. The root is an internal node whose value is a function of the entire tree below it.

The combination gives you the defining property: if any leaf's data changes, its hash changes, which changes the hash of its parent, which changes the hash of the grandparent, all the way to the root. Conversely, two trees with the same root hash must have — modulo cryptographic-hash collisions, which for SHA-256 have probability around 2⁻²⁵⁶ per comparison — identical contents at every leaf.

That single property is the entire leverage. 32 bytes at the root tell you, with overwhelming probability, whether two arbitrarily large datasets agree.

The comparison algorithm

The recursive comparison between two replicas is almost mechanical:

1. Both replicas send their root hash to each other.
2. If the root hashes are equal, the entire dataset is identical. Exchange terminates; zero further work.
3. If they differ, both replicas send the hashes of their root's two children. Each side compares the received hashes with its own children's hashes.
4. For each child-pair whose hashes match, the corresponding subtree is pruned — no data in it differs, so there is nothing to reconcile in that half.
5. For each child-pair whose hashes differ, recurse into that subtree: request and compare the grandchildren.
6. At the leaf level, when a leaf's hash differs from the other replica's leaf, record the leaf's key range as divergent.
7. After the recursion finishes, the union of divergent key ranges is the set of data that actually needs to be exchanged. A targeted sync step — "send me every key-value in ranges R1, R2, … Rk" — transfers only those keys.

Two properties to notice. First, the comparison is symmetric. Both replicas run the recursion; both end up with the same list of divergent ranges. Either can push its missing data, or they can push simultaneously — whichever is more operationally convenient.

Second, the comparison is oblivious to which replica is newer. Merkle trees detect divergence; they do not resolve it. Once divergent leaves are identified, the sync step must transfer the full key-value pairs and apply the same conflict-resolution rules the database uses everywhere else — last-write-wins timestamps, vector-clock merge, CRDT merge, whatever the data model specifies. Merkle trees narrow the expensive "what should you exchange" question; they do not replace the "how should you reconcile" question. That question is what read repair and chapter 82 answer.

Python implementation

A skeletal Merkle tree with build and compare, kept under the 40-line budget:

# anti_entropy/merkle.py
import hashlib

def h(b): return hashlib.sha256(b).digest()

class MerkleNode:
    __slots__ = ("hash", "left", "right", "range")
    def __init__(self, hash=None, left=None, right=None, range=None):
        self.hash, self.left, self.right, self.range = hash, left, right, range

def build_merkle(kv_store, key_range, depth=0, max_depth=20, leaf_cap=100):
    items = kv_store.items_in(key_range)
    if depth >= max_depth or len(items) <= leaf_cap:
        payload = b"".join(k + b"\x00" + v for k, v in sorted(items))
        return MerkleNode(hash=h(payload), range=key_range)
    lo, hi = key_range.split()
    left = build_merkle(kv_store, lo, depth + 1, max_depth, leaf_cap)
    right = build_merkle(kv_store, hi, depth + 1, max_depth, leaf_cap)
    return MerkleNode(hash=h(left.hash + right.hash),
                      left=left, right=right, range=key_range)

def compare_trees(a, b, out):
    if a.hash == b.hash:
        return                       # subtree identical, skip
    if a.left is None or b.left is None:
        out.append(a.range)          # at a leaf and hashes differ
        return
    compare_trees(a.left, b.left, out)
    compare_trees(a.right, b.right, out)

Why items_in(key_range) sorted before hashing: the hash must be deterministic across replicas. If replica A stores keys in insertion order and replica B in a different order, H(iteration order of A) would differ from H(iteration order of B) even with identical contents. Sorting canonicalises the input so equal sets hash to equal digests.

Why leaf_cap — not every Merkle tree bottoms out at depth 20. If a key range contains only 3 keys, stop there; no benefit to subdividing an already-tiny range. This is a leaf-size threshold, not a tree-depth threshold. Cassandra uses a similar heuristic: leaves cover roughly 4096 to 65536 keys by default, chosen so each leaf's hash computation is a bounded cost.

The compare_trees function is where the cost savings live. The first line — if a.hash == b.hash: return — is the pruning step that lets whole subtrees be skipped. Without it, comparison is O(N); with it, comparison is O(divergent-leaves · tree-depth). That single equality check is why Merkle trees work.

Cost analysis

Three regimes dominate:

No divergence (common case). Root hashes match. Comparison terminates after one 32-byte exchange. Total: one round-trip, 64 bytes. This case must be cheap — you run anti-entropy continuously.

One leaf differs. At each of the tree's log₂ N levels, one child-pair matches (pruned) and one differs (recurse). Cost: O(log N) exchanges. A million-leaf tree takes ~20 levels — 640 bytes on the wire to pinpoint the single divergent leaf.

Fraction f of leaves differ. Divergent leaves typically scatter across the tree; each requires its own O(log N) descent, but descents share prefixes. Worst-case amortised cost is O(f · tree_size · log(1/f)); best case (clustered divergence) is better. In typical production, f ≈ 0.001 and tree depth ≈ 20, so comparison exchanges a few hundred hashes — well under 100 KB — to localise 0.1% of the dataset.

All leaves differ. Pathological — fresh replica joining empty, or total data loss. Every path descends to a leaf; cost is O(N), no better than naive. The database usually short-circuits Merkle exchange and streams the full dataset (Cassandra calls this bootstrap or rebuild, not repair).

The good news is that f is almost always small. With read repair running continuously and hinted handoff catching short outages, the residual divergence anti-entropy must clean up is tiny. f = 0.001 is realistic.

Building the tree is the cost

The comparison is cheap; building the tree is not.

To build a Merkle tree over a TB of data, you must hash every byte. That is TB-worth of disk reads plus TB-worth of SHA-256 CPU. SHA-256 runs at ~500 MB/s per core, so 1 TB takes 2000 core-seconds — 30 minutes single-core, 4 minutes on 8 cores. Disk reads at 500 MB/s on NVMe match the CPU; on spinning disks at 100 MB/s, disk dominates. Building a Merkle tree is measurable — not catastrophic, not free.

Two optimisations production systems use:

Amortise tree construction. Build once at the start of a repair session; reuse for comparisons with multiple replicas in the same session. A replica with N=3 participates in 2 pairwise comparisons per cycle; tree built once, reused twice.

Incremental Merkle trees. Instead of rebuilding every cycle, update the tree in place as writes arrive. A write to key K rehashes the containing leaf, then its parent, up to the root — O(log N) per write instead of O(N) per repair cycle. Cassandra 4.0's Incremental Repair uses this approach; the first build is expensive but steady-state repairs only re-process data written since the last successful repair.

Why not always incremental: incremental trees require write-path bookkeeping. Every write must find and update its leaf; every update must cascade to the root. In an LSM engine where writes first land in the memtable and are later flushed and compacted into SSTables, the "leaf" that contains a given key changes over time — compaction rewrites SSTables, which changes which leaves hash which keys. Keeping the Merkle tree consistent with an LSM under compaction is tricky enough that Cassandra only enabled incremental repair by default in 4.0, more than a decade after 1.0.

Scheduling anti-entropy

How often should you run anti-entropy? The trade-offs are straightforward:

• More frequent → faster convergence, less chance of divergence becoming large or old, but more CPU and network spent on repair.
• Less frequent → cheaper steady state, but longer windows during which replicas can silently disagree, and any one run has more work to do.

Cassandra's default guidance is that every replica should participate in a full repair at least once every gc_grace_seconds — by default 10 days. The reason is tombstones: Cassandra's deletes are tombstones that must propagate to every replica before being garbage-collected, or else a replica that never saw the tombstone will "resurrect" the deleted row during the next read repair. Anti-entropy is how the tombstones propagate to cold-key replicas; gc_grace_seconds is the budget anti-entropy has to complete that propagation before GC runs. Miss the budget and you get zombie rows.

In practice, operators run full repair weekly on production clusters and incremental repair every few hours or overnight. Tools like Reaper (originally from Spotify, now a Cassandra project) handle the scheduling and rate-limiting — a full repair of a 50 TB cluster can take days of wall-clock time if not parallelised carefully, and flooding the network with repair traffic during peak hours is a classic operational mistake.

DynamoDB the managed service runs a continuous background anti-entropy loop that operators never touch. The Dynamo paper's section on anti-entropy describes roughly the same loop: every replica, every few hours, picks a peer and compares. The beauty of running it as a managed service is that the customer never schedules a repair window — it is just always running, bounded to a small fraction of cluster resources.

Merkle trees in the wild (beyond databases)

The "cheap cryptographic summary of large state" idea shows up everywhere you need to authenticate or synchronise content without scanning it:

• Git — every commit is ultimately a Merkle root over tree objects over file blobs. Two Git repositories verify they hold the same state by comparing one commit hash. git fetch uses Merkle-like exchange to transfer only the objects the receiver lacks.
• Bitcoin — each block header contains a Merkle root summarising all transactions. SPV wallets verify a transaction's inclusion by downloading the header plus O(log N) hashes — the same O(log N) proof path.
• IPFS and content-addressed storage — files are chunked, chunks are hashed, and the file's identity is the Merkle root over its chunks. Syncing is inherently deduplicated and integrity-checked.
• AWS S3 multipart upload — the final ETag is a hash-of-hashes over part hashes, letting the client verify whole-upload integrity with one comparison.
• Certificate Transparency — Google's CT logs use Merkle trees to prove a certificate is included without downloading the whole log.
• ZFS and Btrfs — filesystem checksums form a Merkle tree up the directory hierarchy, so zfs scrub detects silent corruption cheaply.

The common pattern: large state that many parties need to verify or synchronise, and cryptographic hashes that compress that state into a short digest to check against. Anti-entropy in databases is one instance; Ralph Merkle's 1979 thesis turns out to have covered much more ground than he could have imagined.

Common confusions

• "Merkle comparison IS the sync." No. Comparison localises the divergence to a set of leaf key-ranges. A separate targeted data-transfer step then actually moves the keys. Merkle exchange is the "which keys?" question; the sync is the "send them over" answer. They are different phases with different costs — the comparison scales with divergence, the sync scales with the divergent data size.

• "Running anti-entropy is free." It is absolutely not. Building the tree costs full-dataset disk reads and full-dataset hashing every cycle (amortised somewhat by incremental trees). Running anti-entropy during peak hours will compete with real queries for disk I/O and CPU; Cassandra operators religiously schedule repairs for off-peak windows and rate-limit them with compaction_throughput_mb_per_sec-style knobs.

• "Anti-entropy replaces hinted handoff." No. They complement each other at different timescales. Hinted handoff catches writes during outages up to a few hours — fast, narrow, targeted. Anti-entropy catches everything hinted handoff missed — slow, broad, systematic. Real deployments run both, plus read repair for a third layer of defence.

• "Merkle trees prevent divergence." Merkle trees detect and localise divergence; they do not prevent it. The prevention is in the write path (quorum acks, hinted handoff). The detection is the safety net — when prevention fails, you want to find out before users do.

• "You only need anti-entropy if replicas fail." No. Even with perfect network and zero failures, silent data corruption on disk (bit rot, filesystem bugs, cosmic rays) causes divergence. Anti-entropy is a defence against the whole class of "the bytes on disk are not what we expect" problems, not just partition recovery.

• "The tree should be balanced over keys." Not necessarily — it should be balanced over data volume. If your key distribution is skewed (one hot shard has 10× the keys of a cold one), a tree with fixed-size leaf key-ranges will have wildly different leaf hash-costs. Cassandra's repair subdivides key ranges adaptively so each leaf covers roughly equal data volume, keeping build cost even across leaves.

Going deeper

Range trees and variable leaf sizes

A naive Merkle tree uses fixed-boundary leaves — e.g. "split the key range in half at each level." For skewed data this wastes tree depth on empty regions. Range trees adapt the tree shape to the data distribution, placing leaves only where data exists. Cassandra calls the resulting structure its repair tree and builds it lazily as it scans the underlying SSTables. The leaves cover unequal key-count ranges but roughly equal data-size ranges, which keeps the comparison's information-per-exchange constant.

Set reconciliation with IBFs

Eppstein, Goodrich, Uyeda, and Varghese's 2011 SIGCOMM paper What's the Difference? Efficient Set Reconciliation without Prior Context introduces Invertible Bloom Filters (IBFs) for set reconciliation. An IBF is a compact summary from which the symmetric difference of two sets can be decoded, without exchanging the whole sets. If the symmetric difference has size d, the IBF size is O(d) — independent of set size.

IBFs strictly dominate Merkle trees when d is small, because Merkle has a log factor that IBF does not. They are used in practice for things like BitTorrent's peer exchange and Ethereum's mempool sync. Cassandra has experimented with IBF-based repair but has not shipped it as the default — the Merkle tree is simpler, the cryptographic-hash-tree abstraction reusable for more than just reconciliation, and "good enough" beats "optimal but tricky" for a 15-year-old codebase.

Rsync's algorithm

Rsync (Andrew Tridgell, 1996) solves a conceptually related problem: synchronise two copies of a file with minimal data transfer. It splits the file into fixed-size blocks, computes a rolling checksum per block on one side, and lets the other side find matching blocks and send only the bytes in between. The structure differs from a Merkle tree — flat block list rather than hash tree — but the spirit is identical: exchange compact summaries, transfer only the differing content. Every modern database's anti-entropy path is a descendant of these ideas.

Where this leads next

Anti-entropy gets divergent replicas back in sync — but what happens when the divergence is not a replica catching up, but two replicas that accepted genuinely conflicting writes during a partition? The Merkle tree tells you where they disagree; it does not tell you what the right answer is. Chapter 82 covers conflict resolution — last-write-wins timestamps, vector-clock-based sibling merges, the shopping-cart union. Chapter 83 covers CRDTs, the algebraic data structures that make conflict resolution automatic — sets that merge by union, counters that merge by addition, maps whose merges are composed pointwise. The Dynamo story has been: replicate without a leader (ch.75), place replicas sensibly (ch.76-78), gossip about membership, hint missing writes, repair on read, anti-entropy on the cold tail (this chapter). What remains is telling the database what correct merge means for your data.

References

1. Merkle, A Digital Signature Based on a Conventional Encryption Function, Crypto 1987 — the original Merkle-tree paper, framed as a one-time signature scheme but introducing the tree-of-hashes data structure that is reused in every distributed system since.
2. Demers et al., Epidemic Algorithms for Replicated Database Maintenance, PODC 1987 — the Xerox PARC paper that introduced "anti-entropy" as a term of art for gossip-style reconciliation, with the push/pull/push-pull taxonomy still in use today.
3. DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007 — Section 4.7 on replica synchronisation describes Dynamo's use of Merkle trees for anti-entropy, with the explicit cost analysis that makes the leaderless design viable.
4. Apache Cassandra, nodetool repair and Incremental Repair documentation — the operational reference for running anti-entropy in production Cassandra, including full versus incremental repair, gc_grace_seconds, and scheduling guidance.
5. Amazon Web Services, Amazon DynamoDB Developer Guide — How It Works — reference for the managed DynamoDB architecture, including the continuous background anti-entropy loop that the service runs transparently to customers.
6. Eppstein, Goodrich, Uyeda, Varghese, What's the Difference? Efficient Set Reconciliation without Prior Context, SIGCOMM 2011 — the Invertible Bloom Filter paper, an O(d) alternative to O(d log N) Merkle-based set reconciliation, and a glimpse of where anti-entropy algorithms may go next.