[
https://issues.apache.org/jira/browse/CASSANDRA-193?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12777137#action_12777137
]
Stu Hood commented on CASSANDRA-193:
------------------------------------
> a. Why do you want to use an n-ary tree to represent a binary tree?
The main reason was due to memory concerns... for 256 subranges, an order 256
B-Tree only needs 1 inner node (total 257), while a binary tree would need 127
inner nodes (total 383). Also, in order to get reasonable performance out of a
binary tree over its lifetime, you would probably want to implement a self
balancing tree, which isn't much simpler than a B-Tree. Finally, B-Trees are
arguably faster than binary tree implementations:
http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
> b. Suppose + is the bit-wise AND [...] you can compute the hash of a range
> directly (since now + is commutative and transitive),
> without a bottom-up traversal from the leaves of the complete binary tree.
Ack, this was more of me glossing over details: we don't use AND or any other
commutative operations in the tree, since it would be more likely to cause hash
collisions (switched subtrees might compare equally).
All hashing is accomplished by a single method: Hashable.hash(byte[], byte[]),
which is currently implemented using MD5.
> Proactive repair
> ----------------
>
> Key: CASSANDRA-193
> URL: https://issues.apache.org/jira/browse/CASSANDRA-193
> Project: Cassandra
> Issue Type: New Feature
> Components: Core
> Reporter: Jonathan Ellis
> Assignee: Stu Hood
> Fix For: 0.5
>
> Attachments: 193-1-tree-preparation.diff, 193-2-tree.diff,
> 193-3-aes-preparation.diff, 193-4-aes.diff, mktree-and-binary-tree.png
>
>
> Currently cassandra supports "read repair," i.e., lazy repair when a read is
> done. This is better than nothing but is not sufficient for some cases (e.g.
> catastrophic node failure where you need to rebuild all of a node's data on a
> new machine).
> Dynamo uses merkle trees here. This is harder for Cassandra given the CF
> data model but I suppose we could just hash the serialized CF value.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
