Skip to content

Anti-entropy and Merkle tree gossip#

2024-09-02

Anti-entropy is the process of periodically comparing state between replicas to detect and repair divergence. Merkle trees are the standard way to make this efficient.

The naive approach#

For each key, ship its value to peers and compare. Cost: O(N) network per sync. Unworkable.

Merkle trees#

Build a binary tree over your key space. Each leaf is the hash of a range of keys; each internal node is the hash of its two children. Root hash summarizes the entire keyspace.

To compare two replicas:

  1. Exchange root hashes. If equal, done — no divergence.
  2. If different, exchange child hashes. Recurse into subtrees where hashes differ.
  3. At the leaves, exchange actual keys and reconcile.

Cost: O(k log N) where k is the number of divergent keys. Much better than O(N) when divergence is small (typical case).

Cassandra's implementation#

Cassandra uses Merkle trees for nodetool repair. The tree has:

  • 2^15 = 32768 leaves by default (repair_session_max_tree_depth).
  • Each leaf covers a range of tokens.
  • Leaves store the hash of their range's SSTables.

Repair sessions:

  1. Coordinator computes Merkle trees on all replicas of a range.
  2. Compares trees pairwise to find divergent leaves.
  3. For each divergent leaf, streams the actual data between replicas.

For a 1 TB table with negligible divergence, a repair session might transfer only megabytes.

Riak's approach#

Riak uses active anti-entropy — Merkle trees are maintained continuously in the background rather than computed on-demand. Each vnode keeps an up-to-date Merkle tree of its data; when two vnodes gossip, they just exchange root hashes.

Practical notes#

  • Merkle tree computation is CPU-intensive. Cassandra's repair operation can spike CPU to 100% during the tree-build phase.
  • Divergence detection is only as good as your hash function. Cassandra uses MurmurHash3, which is fast but not cryptographic.
  • Tree granularity is a tradeoff: coarser trees are cheaper to compare but identify divergence to larger ranges.

Reference#

  • Merkle, A Digital Signature Based on a Conventional Encryption Function (CRYPTO 1987).
  • The Cassandra source at src/java/org/apache/cassandra/repair/.
  • Basho's Riak Handbook sections on AAE.