Bringing together the Apache Cassandra experts from the community and DataStax.

Want to learn? Have a question? Want to share your expertise? You are in the right place!

Not sure where to begin? Getting Started

 

question

bhupalreddy1992_162660 avatar image
bhupalreddy1992_162660 asked ·

Is the Merkle tree a hash of a row?

In merkele tree , on which data leaf hash is computed.

Is it on individual row (record) ?

Or group or records

If it's on individual record , depth of merkele tree will be very high right?

cassandrarepair
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

1 Answer

Erick Ramirez avatar image
Erick Ramirez answered ·

Repair is the process of comparing data between replicas and synchronising them so the replicas have the latest copies. In order to do the comparison, Cassandra builds a Merkle tree of each replica and compares them to determine differences between the replicas.

The root of the tree is a hash (digest) of the replica's data. This then branches into 2 halves of the data where each half gets hashed. Each branch repeatedly gets split and hashed until there are 15 "levels" (tree depth). Note that the depth of the Merkle tree differs depending on the version of Cassandra in use.

With a depth of 15, the tree ends up with 32,768 "leaves" (215). If a replica has 30 million partitions, the root is a hash of all the 30M partitions. In the next level where the are 2 branches, each branch is a hash of 15M partitions (30M / 2) and so on until it gets to the leaves.

Each leaf at the maximum depth of 15 is a hash of around 900 partitions (30M / 32K). This is the smallest unit of the Merkle tree so if there is a digest mismatch (hash values) of 2 leaves between 2 replicas, 900 partitions will get streamed by the repair (even if only 1 partition is out of sync).

To answer your question, it isn't a hash of just one partition. Cheers!

2 comments Share
10 |1000 characters needed characters left characters exceeded

Up to 8 attachments (including images) can be used with a maximum of 1.0 MiB each and 10.0 MiB total.

Thanks Erick.

It cleared my doubt.

1 Like 1 · ·
Erick Ramirez avatar image Erick Ramirez ♦♦ bhupalreddy1992_162660 ·

Good to hear. Cheers!

0 Likes 0 · ·