You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2009/12/16 18:59:59 UTC
svn commit: r891352 - in /incubator/cassandra/branches/cassandra-0.5: ./
interface/gen-java/org/apache/cassandra/service/ src/java/org/
src/java/org/apache/cassandra/service/ src/java/org/apache/cassandra/utils/
test/unit/org/ test/unit/org/apache/cass...
Author: jbellis
Date: Wed Dec 16 17:59:58 2009
New Revision: 891352
URL: http://svn.apache.org/viewvc?rev=891352&view=rev
Log:
merge 891038, 891040, 891043 from trunk for CASSANDRA-629
Modified:
incubator/cassandra/branches/cassandra-0.5/ (props changed)
incubator/cassandra/branches/cassandra-0.5/CHANGES.txt
incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/Cassandra.java (props changed)
incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/Column.java (props changed)
incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java (props changed)
incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/NotFoundException.java (props changed)
incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/SuperColumn.java (props changed)
incubator/cassandra/branches/cassandra-0.5/src/java/org/ (props changed)
incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/service/AntiEntropyService.java
incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/FBUtilities.java
incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/MerkleTree.java
incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/Pair.java
incubator/cassandra/branches/cassandra-0.5/test/unit/org/ (props changed)
incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
Propchange: incubator/cassandra/branches/cassandra-0.5/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3:774578-796573
/incubator/cassandra/branches/cassandra-0.4:810145-834239,834349-834350
-/incubator/cassandra/trunk:889435,889834,889937
+/incubator/cassandra/trunk:889435,889834,889937,891038,891040,891043
Modified: incubator/cassandra/branches/cassandra-0.5/CHANGES.txt
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/CHANGES.txt?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/CHANGES.txt (original)
+++ incubator/cassandra/branches/cassandra-0.5/CHANGES.txt Wed Dec 16 17:59:58 2009
@@ -3,6 +3,7 @@
* add CRC32 to commitlog entries (CASSANDRA-605)
* fix data streaming on windows (CASSANDRA-630)
* GC compacted sstables after cleanup and compaction (CASSANDRA-621)
+ * Speed up anti-entropy validation (CASSANDRA-629)
0.5.0 beta 2
Propchange: incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/Cassandra.java
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3/interface/gen-java/org/apache/cassandra/service/Cassandra.java:774578-796573
/incubator/cassandra/branches/cassandra-0.4/interface/gen-java/org/apache/cassandra/service/Cassandra.java:810145-834239,834349-834350
-/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/Cassandra.java:749219-768588,889435,889834,889937
+/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/Cassandra.java:749219-768588,889435,889834,889937,891038,891040,891043
Propchange: incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/Column.java
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,4 +1,4 @@
/incubator/cassandra/branches/cassandra-0.3/interface/gen-java/org/apache/cassandra/service/column_t.java:774578-792198
/incubator/cassandra/branches/cassandra-0.4/interface/gen-java/org/apache/cassandra/service/Column.java:810145-834239,834349-834350
-/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/Column.java:749219-794428,889435,889834,889937
+/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/Column.java:749219-794428,889435,889834,889937,891038,891040,891043
/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/column_t.java:749219-768588
Propchange: incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java:774578-796573
/incubator/cassandra/branches/cassandra-0.4/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java:810145-834239,834349-834350
-/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java:749219-768588,889435,889834,889937
+/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/InvalidRequestException.java:749219-768588,889435,889834,889937,891038,891040,891043
Propchange: incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/NotFoundException.java
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3/interface/gen-java/org/apache/cassandra/service/NotFoundException.java:774578-796573
/incubator/cassandra/branches/cassandra-0.4/interface/gen-java/org/apache/cassandra/service/NotFoundException.java:810145-834239,834349-834350
-/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/NotFoundException.java:749219-768588,889435,889834,889937
+/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/NotFoundException.java:749219-768588,889435,889834,889937,891038,891040,891043
Propchange: incubator/cassandra/branches/cassandra-0.5/interface/gen-java/org/apache/cassandra/service/SuperColumn.java
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,4 +1,4 @@
/incubator/cassandra/branches/cassandra-0.3/interface/gen-java/org/apache/cassandra/service/superColumn_t.java:774578-792198
/incubator/cassandra/branches/cassandra-0.4/interface/gen-java/org/apache/cassandra/service/SuperColumn.java:810145-834239,834349-834350
-/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/SuperColumn.java:749219-794428,889435,889834,889937
+/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/SuperColumn.java:749219-794428,889435,889834,889937,891038,891040,891043
/incubator/cassandra/trunk/interface/gen-java/org/apache/cassandra/service/superColumn_t.java:749219-768588
Propchange: incubator/cassandra/branches/cassandra-0.5/src/java/org/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3/src/java/org:774578-796573
/incubator/cassandra/branches/cassandra-0.4/src/java/org:810145-834239,834349-834350
-/incubator/cassandra/trunk/src/java/org:749219-769885,889435,889834,889937
+/incubator/cassandra/trunk/src/java/org:749219-769885,889435,889834,889937,891038,891040,891043
Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/service/AntiEntropyService.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/service/AntiEntropyService.java?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/service/AntiEntropyService.java (original)
+++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/service/AntiEntropyService.java Wed Dec 16 17:59:58 2009
@@ -312,15 +312,16 @@
public final InetAddress initiator;
public final MerkleTree tree;
- private transient final List<MerkleTree.RowHash> rows;
// the minimum token sorts first, but falls into the last range
private transient List<MerkleTree.RowHash> minrows;
// null when all rows with the min token have been consumed
private transient Token mintoken;
private transient long validated;
+ private transient MerkleTree.TreeRange range;
private transient MerkleTree.TreeRangeIterator ranges;
public final static Predicate<DecoratedKey> DKPRED = Predicates.alwaysTrue();
+ public final static MerkleTree.RowHash EMPTY_ROW = new MerkleTree.RowHash(null, new byte[0]);
Validator(CFTuple cf, InetAddress initiator)
{
@@ -337,10 +338,10 @@
this.cf = cf;
this.initiator = initiator;
this.tree = tree;
- rows = new ArrayList<MerkleTree.RowHash>();
minrows = new ArrayList<MerkleTree.RowHash>();
mintoken = null;
validated = 0;
+ range = null;
ranges = null;
}
@@ -381,10 +382,14 @@
* Called (in order) for every row present in the CF.
* Hashes the row, and adds it to the tree being built.
*
- * There are three possible cases:
+ * There are four possible cases:
* 1. Token is greater than range.right (we haven't generated a range for it yet),
* 2. Token is less than/equal to range.left (the range was valid),
- * 3. Token is contained in the range (the range is in progress).
+ * 3. Token is contained in the range (the range is in progress),
+ * 4. No more invalid ranges exist.
+ *
+ * TODO: Because we only validate completely empty trees at the moment, we
+ * do not bother dealing with case 2 and case 4 should result in an error.
*
* Additionally, there is a special case for the minimum token, because
* although it sorts first, it is contained in the last possible range.
@@ -402,42 +407,31 @@
{
// and store it to be appended when we complete
minrows.add(rowHash(row));
- validated++;
return;
}
mintoken = null;
}
- if (!ranges.hasNext())
- return;
+ if (range == null)
+ range = ranges.next();
- MerkleTree.TreeRange range = ranges.peek();
// generate new ranges as long as case 1 is true
- while (range.right().compareTo(row.key.token) < 0)
+ while (!range.contains(row.key.token))
{
- // token is past the current range: finalize
- range.validate(rows);
- rows.clear();
-
- // and generate a new range
- ranges.next();
- if (!ranges.hasNext())
- return;
- range = ranges.peek();
+ // add the empty hash, and move to the next range
+ range.addHash(EMPTY_ROW);
+ range = ranges.next();
}
- // if case 2 is true, ignore the token
- if (row.key.token.compareTo(range.left()) <= 0)
- return;
-
- // case 3 must be true: buffer the hashed row
- rows.add(rowHash(row));
- validated++;
+ // case 3 must be true: mix in the hashed row
+ range.addHash(rowHash(row));
}
private MerkleTree.RowHash rowHash(CompactedRow row)
{
- byte[] rowhash = FBUtilities.hash("MD5", row.key.key.getBytes(), row.buffer.getData());
+ validated++;
+ // MerkleTree uses XOR internally, so we want lots of output bits here
+ byte[] rowhash = FBUtilities.hash("SHA-256", row.key.key.getBytes(), row.buffer.getData());
return new MerkleTree.RowHash(row.key.token, rowhash);
}
@@ -449,20 +443,17 @@
{
assert ranges != null : "Validator was not prepared()";
- // finish validating remaining rows
+ if (range != null)
+ range.addHash(EMPTY_ROW);
while (ranges.hasNext())
{
- MerkleTree.TreeRange range = ranges.next();
- if (!ranges.hasNext() && !minrows.isEmpty() && range.contains(tree.partitioner().getMinimumToken()))
- {
- // append rows with the minimum token into the last range
- rows.addAll(minrows);
- minrows.clear();
- }
- range.validate(rows);
- rows.clear();
+ range = ranges.next();
+ range.addHash(EMPTY_ROW);
}
- assert rows.isEmpty() && minrows.isEmpty();
+ // add rows with the minimum token to the final range
+ if (!minrows.isEmpty())
+ for (MerkleTree.RowHash minrow : minrows)
+ range.addHash(minrow);
StageManager.getStage(AE_SERVICE_STAGE).execute(this);
logger.debug("Validated " + validated + " rows into AEService tree for " + cf);
@@ -484,15 +475,9 @@
Collection<InetAddress> neighbors = Collections2.filter(ss.getNaturalEndpoints(ss.getLocalToken()),
Predicates.not(Predicates.equalTo(local)));
- // cache the local tree
+ // cache the local tree and then broadcast it to our neighbors
aes.register(cf, local, tree);
-
- if (!local.equals(initiator))
- {
- // one of our neighbors initiated: broadcast the tree to all of them
- aes.notifyNeighbors(this, local, neighbors);
- }
- // else: we initiated this validation session: wait for responses
+ aes.notifyNeighbors(this, local, neighbors);
// return any old object
return AntiEntropyService.class;
@@ -801,6 +786,7 @@
/**
* A tuple of table and cf.
+ * TODO: Use utils.Pair once it implements hashCode/equals.
*/
static final class CFTuple
{
Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/FBUtilities.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/FBUtilities.java?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/FBUtilities.java (original)
+++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/FBUtilities.java Wed Dec 16 17:59:58 2009
@@ -135,24 +135,40 @@
}
if(null == bytes2) return 1;
- for(int i = 0; i < bytes1.length && i < bytes2.length; i++){
- int cmp = compareBytes(bytes1[i], bytes2[i]);
- if(0 != cmp) return cmp;
+ int minLength = Math.min(bytes1.length, bytes2.length);
+ for(int i = 0; i < minLength; i++)
+ {
+ if(bytes1[i] == bytes2[i])
+ continue;
+ // compare non-equal bytes as unsigned
+ return (bytes1[i] & 0xFF) < (bytes2[i] & 0xFF) ? -1 : 1;
}
if(bytes1.length == bytes2.length) return 0;
else return (bytes1.length < bytes2.length)? -1 : 1;
}
- public static int compareBytes(byte b1, byte b2){
- return compareBytes((int)b1, (int)b2);
- }
+ /**
+ * @return The bitwise XOR of the inputs. The output will be the same length as the
+ * longer input, but if either input is null, the output will be null.
+ */
+ public static byte[] xor(byte[] left, byte[] right)
+ {
+ if (left == null || right == null)
+ return null;
+ if (left.length > right.length)
+ {
+ byte[] swap = left;
+ left = right;
+ right = swap;
+ }
- public static int compareBytes(int b1, int b2){
- int i1 = b1 & 0xFF;
- int i2 = b2 & 0xFF;
- if(i1 < i2) return -1;
- else if(i1 == i2) return 0;
- else return 1;
+ // left.length is now <= right.length
+ byte[] out = Arrays.copyOf(right, right.length);
+ for (int i = 0; i < left.length; i++)
+ {
+ out[i] = (byte)((left[i] & 0xFF) ^ (right[i] & 0xFF));
+ }
+ return out;
}
public static BigInteger hash(String data)
Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/MerkleTree.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/MerkleTree.java?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/MerkleTree.java (original)
+++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/MerkleTree.java Wed Dec 16 17:59:58 2009
@@ -30,47 +30,39 @@
/**
* A MerkleTree implemented as a binary tree.
*
- * A MerkleTree is a full binary that represents a perfect binary tree of
+ * A MerkleTree is a full binary tree that represents a perfect binary tree of
* depth 'hashdepth'. In a perfect binary tree, each leaf contains a
* sequentially hashed range, and each inner node contains the binary hash of
* its two children. In the MerkleTree, many ranges will not be split to the
* full depth of the perfect binary tree: the leaves of this tree are Leaf objects,
* which contain the computed values of the nodes that would be below them if
* the tree were perfect.
+ *
+ * The hash values of the inner nodes of the MerkleTree are calculated lazily based
+ * on their children when the hash of a range is requested with hash(range).
*
- * All nodes of the perfect tree are calculated using a MD5 hash: leaves are
- * sequential hashes of the rows that fall into the range they represent, and
- * inner nodes are a binary hash of their children.
+ * Inputs passed to TreeRange.validate should be calculated using a very secure hash,
+ * because all hashing internal to the tree is accomplished using XOR.
*
* If two MerkleTrees have the same hashdepth, they represent a perfect tree
* of the same depth, and can always be compared, regardless of size or splits.
*/
public class MerkleTree implements Serializable
{
- private static final long serialVersionUID = 1L;
+ private static final long serialVersionUID = 2L;
- public static final byte RECOMMENDED_DEPTH = (byte)64;
+ public static final byte RECOMMENDED_DEPTH = Byte.MAX_VALUE;
public static final int CONSISTENT = 0;
public static final int FULLY_INCONSISTENT = 1;
public static final int PARTIALLY_INCONSISTENT = 2;
- // cache of empty hash trees up to the maximum depth (0 to 127)
- public static final byte[][] EMPTIES = new byte[Byte.MAX_VALUE][];
- static {
- EMPTIES[0] = new byte[0];
- for (int i = 1; i < EMPTIES.length; i++)
- {
- EMPTIES[i] = Hashable.binaryHash(EMPTIES[i-1], EMPTIES[i-1]);
- }
- }
-
public final byte hashdepth;
private transient IPartitioner partitioner;
- private int maxsize;
- private int size;
+ private long maxsize;
+ private long size;
private Hashable root;
/**
@@ -79,7 +71,7 @@
* of the key space covered by each subrange of a fully populated tree.
* @param maxsize The maximum number of subranges in the tree.
*/
- public MerkleTree(IPartitioner partitioner, byte hashdepth, int maxsize)
+ public MerkleTree(IPartitioner partitioner, byte hashdepth, long maxsize)
{
this.partitioner = partitioner;
this.hashdepth = hashdepth;
@@ -96,32 +88,31 @@
}
/**
- * Initializes this tree by splitting it into maxsize ranges, or
- * until hashdepth is reached.
- *
- * TODO: could be optimized as breadth first generation of nodes.
+ * Initializes this tree by splitting it until hashdepth is reached,
+ * or until an additional level of splits would violate maxsize.
*
- * NB: asserts that the tree is of size 1.
+ * NB: Replaces all nodes in the tree.
*/
public void init()
{
- assert size() == 1;
+ // determine the depth to which we can safely split the tree
+ byte sizedepth = (byte)(Math.log10(maxsize) / Math.log10(2));
+ byte depth = (byte)Math.min(sizedepth, hashdepth);
- Queue<Range> ranges = new ArrayDeque<Range>();
- ranges.add(new Range(partitioner.getMinimumToken(),
- partitioner.getMinimumToken()));
- while (true)
- {
- Range range = ranges.remove();
- Token mid = partitioner.midpoint(range.left(),
- range.right());
- if (!split(mid))
- // we've reached maxsize or hashdepth
- return;
+ Token mintoken = partitioner.getMinimumToken();
+ root = initHelper(mintoken, mintoken, (byte)0, depth);
+ size = (long)Math.pow(2, depth);
+ }
- ranges.add(new Range(range.left(), mid));
- ranges.add(new Range(mid, range.right()));
- }
+ private Hashable initHelper(Token left, Token right, byte depth, byte max)
+ {
+ if (depth == max)
+ // we've reached the leaves
+ return new Leaf();
+ Token midpoint = partitioner.midpoint(left, right);
+ Hashable lchild = initHelper(left, midpoint, inc(depth), max);
+ Hashable rchild = initHelper(midpoint, right, inc(depth), max);
+ return new Inner(midpoint, lchild, rchild);
}
Hashable root()
@@ -138,17 +129,17 @@
* The number of distinct ranges contained in this tree. This is a reasonable
* measure of the memory usage of the tree (assuming 'this.order' is significant).
*/
- public int size()
+ public long size()
{
return size;
}
- public int maxsize()
+ public long maxsize()
{
return maxsize;
}
- public void maxsize(int maxsize)
+ public void maxsize(long maxsize)
{
this.maxsize = maxsize;
}
@@ -475,7 +466,7 @@
public static final long serialVersionUID = 1L;
private final MerkleTree tree;
public final byte depth;
- public final Hashable hashable;
+ private final Hashable hashable;
TreeRange(MerkleTree tree, Token left, Token right, byte depth, Hashable hashable)
{
@@ -497,89 +488,20 @@
}
/**
- * Consumes a collection of entries within this range.
- */
- public void validate(Collection<RowHash> entries)
- {
- PeekingIterator<RowHash> iter = Iterators.peekingIterator(entries.iterator());
- validate(iter);
- }
-
- /**
- * Consumes an iterator over entries within this range, setting the
- * value of this range's Leaf to the computed value.
+ * @param entry Row to mix into the hash for this range.
*/
- public void validate(PeekingIterator<RowHash> entries)
+ public void addHash(RowHash entry)
{
assert tree != null : "Not intended for modification!";
assert hashable instanceof Leaf;
- byte[] roothash;
- try
- {
- roothash = validateHelper(left(), right(), depth, entries);
- }
- catch (StopRecursion e)
- {
- throw new RuntimeException("Iterator contained invalid entry!");
- }
-
- // check that all values were consumed from the iterator, and that
- // a valid hash could be generated
- if (entries.hasNext() || roothash == null)
- throw new RuntimeException("Bad iterator for " + this + "!");
- hashable.hash(roothash);
- }
- /**
- * Collects values from the given iterator that fall into the
- * range represented by left and right. Recurses until we reach
- * hashdepth, where hashes are added sequentially, and then binary
- * hashes the results back to the root.
- *
- * @param left The left token of the active range.
- * @param right The right token of the active range.
- * @param depth The depth of the active range.
- * @param entries A peek()able iterator.
- */
- private byte[] validateHelper(Token left, Token right, byte depth, PeekingIterator<RowHash> entries) throws StopRecursion.InvalidHash
- {
- if (entries.hasNext() && Range.contains(left, right, entries.peek().token))
- {
- // see if we can recurse deeper
- if (depth < tree.hashdepth)
- {
- Token midpoint = tree.partitioner().midpoint(left, right);
- if (left.compareTo(midpoint) < 0 && midpoint.compareTo(right) < 0)
- {
- // we can recurse deeper
- byte[] lhash = validateHelper(left, midpoint, inc(depth), entries);
- byte[] rhash = validateHelper(midpoint, right, inc(depth), entries);
- return Hashable.binaryHash(lhash, rhash);
- }
- // else: the Token impl. cannot provide more resolution for this range
- }
-
- // hash relevant values from the iterator, and add to the context
- return consume(left, right, entries);
- }
- else
- {
- // this range is empty: return static hash value:
- // the hash is the one generated by a binary tree of depth (tree.hashdepth-depth)
- return EMPTIES[tree.hashdepth-depth];
- }
+ hashable.addHash(entry.hash);
}
- /**
- * Consumes and sequentially hashes values from the iterator that fall into the active
- * range. Should be called with an iterator that contains at least one matching entry.
- */
- private byte[] consume(Token left, Token right, PeekingIterator<RowHash> entries)
+ public void addAll(Iterator<RowHash> entries)
{
- byte[] sequentialHash = entries.next().hash;
- while (entries.hasNext() && Range.contains(left, right, entries.peek().token))
- sequentialHash = Hashable.binaryHash(sequentialHash, entries.next().hash);
- return sequentialHash;
+ while (entries.hasNext())
+ addHash(entries.next());
}
@Override
@@ -777,7 +699,8 @@
/**
* Hash value representing a row, to be used to pass hashes to the MerkleTree.
- * The byte[] hash value should contain a digest of the key and value of the row.
+ * The byte[] hash value should contain a digest of the key and value of the row
+ * created using a very strong hash function.
*/
public static class RowHash
{
@@ -831,15 +754,24 @@
}
/**
+ * Mixes the given value into our hash. If our hash is null,
+ * our hash will become the given value.
+ */
+ void addHash(byte[] righthash)
+ {
+ if (hash == null)
+ hash = righthash;
+ else
+ hash = binaryHash(hash, righthash);
+ }
+
+ /**
* The primitive with which all hashing should be accomplished: hashes
* a left and right value together.
*/
static byte[] binaryHash(final byte[] left, final byte[] right)
{
- if (left == null || right == null)
- return null;
- else
- return FBUtilities.hash("MD5", left, right);
+ return FBUtilities.xor(left, right);
}
public abstract void toString(StringBuilder buff, int maxdepth);
Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/Pair.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/Pair.java?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/Pair.java (original)
+++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/utils/Pair.java Wed Dec 16 17:59:58 2009
@@ -18,7 +18,7 @@
package org.apache.cassandra.utils;
-public class Pair<T1, T2>
+public final class Pair<T1, T2>
{
public final T1 left;
public final T2 right;
Propchange: incubator/cassandra/branches/cassandra-0.5/test/unit/org/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Dec 16 17:59:58 2009
@@ -1,3 +1,3 @@
/incubator/cassandra/branches/cassandra-0.3/test/unit/org:774578-796573
/incubator/cassandra/branches/cassandra-0.4/test/unit/org:810145-834239,834349-834350
-/incubator/cassandra/trunk/test/unit/org:749219-768583,889435,889834,889937
+/incubator/cassandra/trunk/test/unit/org:749219-768583,889435,889834,889937,891038,891040,891043
Modified: incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java?rev=891352&r1=891351&r2=891352&view=diff
==============================================================================
--- incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java (original)
+++ incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java Wed Dec 16 17:59:58 2009
@@ -405,7 +405,7 @@
// validate the tree
TreeRangeIterator ranges = mt.invalids(new Range(tok(0), tok(0)));
for (TreeRange range : ranges)
- range.validate(new HIterator(/*empty*/ new int[0]));
+ range.addHash(new RowHash(range.right(), new byte[0]));
assert null != mt.hash(new Range(tok(0), tok(0))) :
"Could not hash tree " + mt;
@@ -433,12 +433,12 @@
mt.split(tok(10));
ranges = mt.invalids(full);
- ranges.next().validate(new HIterator(2, 4)); // (0,4]: depth 2
- ranges.next().validate(new HIterator(6)); // (4,6]
- ranges.next().validate(new HIterator(8)); // (6,8]
- ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (8,10]
- ranges.next().validate(new HIterator(12)); // (10,12]
- ranges.next().validate(new HIterator(14, 0)); // (12,0]: depth 2
+ ranges.next().addAll(new HIterator(2, 4)); // (0,4]: depth 2
+ ranges.next().addAll(new HIterator(6)); // (4,6]
+ ranges.next().addAll(new HIterator(8)); // (6,8]
+ ranges.next().addAll(new HIterator(/*empty*/ new int[0])); // (8,10]
+ ranges.next().addAll(new HIterator(12)); // (10,12]
+ ranges.next().addAll(new HIterator(14, 0)); // (12,0]: depth 2
mt2.split(tok(8));
@@ -450,14 +450,14 @@
mt2.split(tok(11));
ranges = mt2.invalids(full);
- ranges.next().validate(new HIterator(2)); // (0,2]
- ranges.next().validate(new HIterator(4)); // (2,4]
- ranges.next().validate(new HIterator(6, 8)); // (4,8]: depth 2
- ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (8,9]
- ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (9,10]
- ranges.next().validate(new HIterator(/*empty*/ new int[0])); // (10,11]: depth 4
- ranges.next().validate(new HIterator(12)); // (11,12]: depth 4
- ranges.next().validate(new HIterator(14, 0)); // (12,0]: depth 2
+ ranges.next().addAll(new HIterator(2)); // (0,2]
+ ranges.next().addAll(new HIterator(4)); // (2,4]
+ ranges.next().addAll(new HIterator(6, 8)); // (4,8]: depth 2
+ ranges.next().addAll(new HIterator(/*empty*/ new int[0])); // (8,9]
+ ranges.next().addAll(new HIterator(/*empty*/ new int[0])); // (9,10]
+ ranges.next().addAll(new HIterator(/*empty*/ new int[0])); // (10,11]: depth 4
+ ranges.next().addAll(new HIterator(12)); // (11,12]: depth 4
+ ranges.next().addAll(new HIterator(14, 0)); // (12,0]: depth 2
byte[] mthash = mt.hash(full);
byte[] mt2hash = mt2.hash(full);
@@ -475,7 +475,7 @@
mt.maxsize(256);
mt.init();
for (TreeRange range : mt.invalids(full))
- range.validate(new HIterator(range.right()));
+ range.addAll(new HIterator(range.right()));
byte[] initialhash = mt.hash(full);
oout.writeObject(mt);
@@ -522,9 +522,9 @@
// add dummy hashes to the rest of both trees
for (TreeRange range : mt.invalids(full))
- range.validate(new HIterator(range.right()));
+ range.addAll(new HIterator(range.right()));
for (TreeRange range : mt2.invalids(full))
- range.validate(new HIterator(range.right()));
+ range.addAll(new HIterator(range.right()));
// trees should disagree for leftmost, (middle.left, rightmost.right]
List<TreeRange> diffs = MerkleTree.difference(mt, mt2);
@@ -564,7 +564,7 @@
return hstack.pop();
}
- static class HIterator extends AbstractIterator<RowHash> implements PeekingIterator<RowHash>
+ static class HIterator extends AbstractIterator<RowHash>
{
private Iterator<Token> tokens;