CODEWITHSUNDEEP
algorithmdata-structurescassandramerkle-tree
snowmantw
snowmantw

Reputation: 1621

Merkle tree for difference comparison, in Cassandra

I'm reading an document about repair in Cassandra, it says

The comparison begins with the top node of the Merkle tree. If no difference is detected, the process proceeds to the left child node and compares and then the right child node.

However, Merkle tree's non-leaf nodes represents:

Each Parent node higher in the tree is a hash of its respective children. Because higher nodes in the Merkle tree represent data further down the tree, Casandra can check each branch independently without requiring the coordinator node to download the entire data set.

According to this, and other data structure articles I have found, they all indicates a following comparison deeper than the root only be proceed if two Merkle trees has the root that differs. I'm not sure if the document describes it correctly that I may understood something wrong, or it actually has an error?

Upvotes: 6

Views: 4331

Answers (1)

nevsv
nevsv

Reputation: 2466

There is a mistake in Datastax docs.

There's is a good explanation of Merkle tree's comparison:

http://distributeddatastore.blogspot.co.il/2013/07/cassandra-using-merkle-trees-to-detect.html

Many eventual consistency databases using Merkle tree for anti-entropy. You can review the documentation and explanation of it in Riak/DynamoDB documentation.

Upvotes: 7

Related Questions