What is the role of Merkle trees in Cassandra's repair process?

Comparing every row between two replicas byte-by-byte to find differences would be prohibitively slow at scale. Merkle trees let Cassandra compare huge token ranges efficiently by comparing hashes instead of raw data.

1. For a given token range, a replica divides the data into smaller sub-ranges and computes a hash for each one.
2. Those hashes become the leaves of a binary tree; each parent node's hash is computed from its children, all the way up to a single root hash.
3. Two replicas exchange their tree's root hash first — if the roots match, that whole range is confirmed identical with a single comparison.
4. If roots differ, the comparison recurses down the tree, only following branches whose hashes disagree, until it isolates the specific sub-ranges that actually differ.

Only the data underlying the mismatched leaves gets streamed between replicas, not the whole range. This is what makes nodetool repair scale reasonably well even on very large datasets: the cost of the comparison itself is proportional to the size of the divergence, not the size of the whole dataset.

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.