The Replica Sync Problem
In a distributed database, replicas can drift out of sync due to network partitions, node failures, or write conflicts. Anti-entropy is the background process that detects and repairs these inconsistencies. The naive approach — send all data from Replica A to Replica B and compare — is O(N) bandwidth. Merkle Trees reduce this to O(log N) in the common case.
How Cassandra Uses Merkle Trees
Cassandra's anti-entropy repair works as follows:
-
Build: Each replica independently builds a Merkle Tree over its token range (the partition of data it owns). Leaf nodes represent ranges of partition keys; each leaf hash covers all rows in that key range.
-
Exchange Roots: Replica A sends its Merkle Root to Replica B (and vice versa).
-
Root Match → Done: If the roots are identical, the replicas are in sync. Zero additional bandwidth consumed. This is the common case in a healthy cluster.
-
Root Mismatch → Descend: If roots differ, the replicas exchange the hashes of their root's two children. They identify which child subtree differs and ignore the matching subtree entirely — eliminating half the data space from consideration.
-
Recurse: They continue descending into only the differing subtrees, halving the search space at each level, until they reach the specific leaf nodes that differ.
-
Repair: Only the actual data rows corresponding to the differing leaf nodes are exchanged and reconciled.
Replica A Root: 0xABCD... ≠ Replica B Root: 0x1234...
↓
Exchange children:
Left Child: A=0xFF11 = B=0xFF11 → SKIP (in sync)
Right Child: A=0x8822 ≠ B=0x9933 → DESCEND
↓
Exchange grandchildren of Right:
Left Grandchild: A=0xAA = B=0xAA → SKIP
Right Grandchild: A=0xBB ≠ B=0xCC → DESCEND
↓
Found differing leaf → exchange only those rows
The Cost Model
In a tree with N leaf ranges, finding K differing ranges costs O(K × log N) hash comparisons — far better than O(N) for small K. In practice, replicas in a healthy Cassandra cluster are almost always in sync, so the root comparison terminates immediately with zero repair work.
A common interview question: "How does Cassandra repair work, and why is it expensive?" The answer has two parts. First, the Merkle Tree construction itself is expensive — Cassandra must read and hash every row in the token range to build the tree, which causes significant I/O. This is why nodetool repair is run during off-peak hours. Second, the tree comparison and data exchange are efficient (O(log N)). The bottleneck is tree construction, not tree comparison. Interviewers who expect only "it uses Merkle Trees" are looking for this nuance.
Key Point: Anti-entropy with Merkle Trees reduces synchronization bandwidth from O(N) to O(K × log N), where K is the number of differing ranges. The expensive part is building the tree (reading all data), not comparing it. This is why Cassandra repair is I/O-intensive even when replicas are mostly in sync.