cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject 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...
Date Wed, 16 Dec 2009 17:59:59 GMT
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;
 



Mime
View raw message