cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stu Hood (JIRA)" <>
Subject [jira] Commented: (CASSANDRA-193) Proactive repair
Date Mon, 23 Nov 2009 21:47:39 GMT


Stu Hood commented on CASSANDRA-193:

> see whether we lose any precision by simply using bitwise XOR to combine row hashes
Doing the math on this one was simpler than actually testing it: using a commutative hash
function like XOR means that the number of possible inputs goes from being a Permutation of
the leaves to being a Combination of the leaves (since a set of leaves in any order are equal).

For XOR you have:
(2^127)! / (2^127 - 2^16)! == number of possible permutations of 2^16 hashes of length 127
And for MD5:
(2^127)! / (2^16)! * (2^127 - 2^16)! == number of possible combinations of 2^16 hashes of
length 127

I wouldn't think it would be possible to notice such a small difference. Nonetheless, I think
it is a moot point:

> Using XOR further simplifies how hash values for internal nodes are computed.
I don't think that using XOR is significantly more efficient. Because XOR is associative,
it is possible to hash arbitrary sequential leaves together, which is impossible with MD5,
but we never do this: all of our comparison happens on the boundaries defined by IPartitioner.midpoint(),
so the tree structure containing predefined/precomputed values can contain any value required
for comparison.

> Proactive repair
> ----------------
>                 Key: CASSANDRA-193
>                 URL:
>             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-1-tree-preparation.diff, 193-2-tree.diff,
193-2-tree.diff, 193-3-aes-preparation.diff, 193-3-aes-preparation.diff, 193-4-aes.diff, 193-4-aes.diff,
193-5-manual-repair.diff, 193-6-inverted-filter.diff, 193-6-inverted-filter.diff, 193-7-disable-caching-and-fix-minimum-token.diff,
193-breakdown.txt, 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.

View raw message