cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r1163090 - in /cassandra/branches/cassandra-0.8: CHANGES.txt src/java/org/apache/cassandra/dht/Range.java test/unit/org/apache/cassandra/dht/RangeTest.java
Date Tue, 30 Aug 2011 05:50:31 GMT
Author: jbellis
Date: Tue Aug 30 05:50:30 2011
New Revision: 1163090

URL: http://svn.apache.org/viewvc?rev=1163090&view=rev
Log:
fix corner cases in Range.differenceToFetch
patch by Tyler Hobbs; reviewed by Stu Hood for CASSANDRA-3084

Modified:
    cassandra/branches/cassandra-0.8/CHANGES.txt
    cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/dht/Range.java
    cassandra/branches/cassandra-0.8/test/unit/org/apache/cassandra/dht/RangeTest.java

Modified: cassandra/branches/cassandra-0.8/CHANGES.txt
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.8/CHANGES.txt?rev=1163090&r1=1163089&r2=1163090&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.8/CHANGES.txt (original)
+++ cassandra/branches/cassandra-0.8/CHANGES.txt Tue Aug 30 05:50:30 2011
@@ -39,6 +39,7 @@
    and string representations in CLI (CASSANDRA-3075)
  * always hint counters (CASSANDRA-3099)
  * fix log4j initialization in EmbeddedCassandraService (CASSANDRA-2857)
+ * fix corner cases in Range.differenceToFetch (CASSANDRA-3084)
 
 
 0.8.4

Modified: cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/dht/Range.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/dht/Range.java?rev=1163090&r1=1163089&r2=1163090&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/dht/Range.java (original)
+++ cassandra/branches/cassandra-0.8/src/java/org/apache/cassandra/dht/Range.java Tue Aug
30 05:50:30 2011
@@ -261,6 +261,24 @@ public class Range extends AbstractBound
     }
 
     /**
+     * Subtracts a portion of this range.
+     * @param contained The range to subtract from this. It must be totally
+     * contained by this range.
+     * @return An ArrayList of the Ranges left after subtracting contained
+     * from this.
+     */
+    private ArrayList<Range> subtractContained(Range contained)
+    {
+        ArrayList<Range> difference = new ArrayList<Range>();
+
+        if (!left.equals(contained.left))
+            difference.add(new Range(left, contained.left));
+        if (!right.equals(contained.right))
+            difference.add(new Range(contained.right, right));
+        return difference;
+    }
+
+    /**
      * Calculate set of the difference ranges of given two ranges
      * (as current (A, B] and rhs is (C, D])
      * which node will need to fetch when moving to a given new token
@@ -270,33 +288,35 @@ public class Range extends AbstractBound
      */
     public Set<Range> differenceToFetch(Range rhs)
     {
-        Set<Range> difference = new HashSet<Range>();
-
-        int comparisonAC = Range.compare(left, rhs.left);
-
-        if (comparisonAC == 0) // (A, B] & (A, C]
+        Set<Range> result;
+        Set<Range> intersectionSet = this.intersectionWith(rhs);
+        if (intersectionSet.isEmpty())
         {
-            if (Range.compare(right, rhs.right) < 0) // B < C
-            {
-                difference.add(new Range(right, rhs.right));
-            }
+            result = new HashSet<Range>();
+            result.add(rhs);
         }
-        else if (comparisonAC > 0) // (A, B] & (C, D]  where C < A (A > C)
+        else
         {
-            difference.add(new Range(rhs.left, left)); // first interval will be (C, A]
-
-            if (Range.compare(rhs.right, right) > 0) // D > B
+            Range[] intersections = new Range[intersectionSet.size()];
+            intersectionSet.toArray(intersections);
+            if (intersections.length == 1)
             {
-                difference.add(new Range(rhs.right, right)); // (D, B]
+                result = new HashSet<Range>(rhs.subtractContained(intersections[0]));
+            }
+            else
+            {
+                // intersections.length must be 2
+                Range first = intersections[0];
+                Range second = intersections[1];
+                ArrayList<Range> temp = rhs.subtractContained(first);
+
+                // Because there are two intersections, subtracting only one of them
+                // will yield a single Range.
+                Range single = temp.get(0);
+                result = new HashSet<Range>(single.subtractContained(second));
             }
         }
-        else // (A, B] & (C, D] where C > A (mean that comparisonAC < 0)
-        {
-            Token newLeft = (Range.compare(rhs.left, right) > 0) ? rhs.left : right; //
C > B ? (C, D] : (B, D]
-            difference.add(new Range(newLeft, rhs.right));
-        }
-
-        return difference;
+        return result;
     }
 
     public static boolean isTokenInRanges(Token token, Iterable<Range> ranges)

Modified: cassandra/branches/cassandra-0.8/test/unit/org/apache/cassandra/dht/RangeTest.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.8/test/unit/org/apache/cassandra/dht/RangeTest.java?rev=1163090&r1=1163089&r2=1163090&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.8/test/unit/org/apache/cassandra/dht/RangeTest.java (original)
+++ cassandra/branches/cassandra-0.8/test/unit/org/apache/cassandra/dht/RangeTest.java Tue
Aug 30 05:50:30 2011
@@ -19,12 +19,10 @@
 package org.apache.cassandra.dht;
 
 import java.nio.ByteBuffer;
-import java.util.Arrays;
-import java.util.List;
+import java.util.HashSet;
 import java.util.Set;
 
 import org.apache.commons.lang.StringUtils;
-
 import org.junit.Test;
 
 public class RangeTest
@@ -314,4 +312,151 @@ public class RangeTest
         assert Range.compare(t5, t4) == 1;
         assert Range.compare(t1, t4) == 0;
     }
+
+    private Range makeRange(String token1, String token2)
+    {
+        return new Range(new BigIntegerToken(token1), new BigIntegerToken(token2));
+    }
+
+    private Set<Range> makeRanges(String[][] tokenPairs)
+    {
+        Set<Range> ranges = new HashSet<Range>();
+        for (int i = 0; i < tokenPairs.length; ++i)
+            ranges.add(makeRange(tokenPairs[i][0], tokenPairs[i][1]));
+        return ranges;
+    }
+
+    private void checkDifference(Range oldRange, String[][] newTokens, String[][] expected)
+    {
+        Set<Range> ranges = makeRanges(newTokens);
+        for (Range newRange : ranges)
+        {
+            Set<Range> diff = oldRange.differenceToFetch(newRange);
+            assert diff.equals(makeRanges(expected)) : "\n" +
+                                                       "Old range: " + oldRange.toString()
+ "\n" +
+                                                       "New range: " + newRange.toString()
+ "\n" +
+                                                       "Difference: (result) " + diff.toString()
+ " != " + makeRanges(expected) + " (expected)";
+        }
+    }
+
+    @Test
+    public void testDifferenceToFetchNoWrap()
+    {
+        Range oldRange = makeRange("10", "40");
+
+        // New range is entirely contained
+        String[][] newTokens1 = { { "20", "30" }, { "10", "20" }, { "10", "40" }, { "20",
"40" } };
+        String[][] expected1 = { };
+        checkDifference(oldRange, newTokens1, expected1);
+
+        // Right half of the new range is needed
+        String[][] newTokens2 = { { "10", "50" }, { "20", "50" }, { "40", "50" } };
+        String[][] expected2 = { { "40", "50" } };
+        checkDifference(oldRange, newTokens2, expected2);
+
+        // Left half of the new range is needed
+        String[][] newTokens3 = { { "0", "10" }, { "0", "20" }, { "0", "40" } };
+        String[][] expected3 = { { "0", "10" } };
+        checkDifference(oldRange, newTokens3, expected3);
+
+        // Parts on both ends of the new range are needed
+        String[][] newTokens4 = { { "0", "50" } };
+        String[][] expected4 = { { "0", "10" }, { "40", "50" } };
+        checkDifference(oldRange, newTokens4, expected4);
+    }
+
+    @Test
+    public void testDifferenceToFetchBothWrap()
+    {
+        Range oldRange = makeRange("1010", "40");
+
+        // New range is entirely contained
+        String[][] newTokens1 = { { "1020", "30" }, { "1010", "20" }, { "1010", "40" }, {
"1020", "40" } };
+        String[][] expected1 = { };
+        checkDifference(oldRange, newTokens1, expected1);
+
+        // Right half of the new range is needed
+        String[][] newTokens2 = { { "1010", "50" }, { "1020", "50" }, { "1040", "50" } };
+        String[][] expected2 = { { "40", "50" } };
+        checkDifference(oldRange, newTokens2, expected2);
+
+        // Left half of the new range is needed
+        String[][] newTokens3 = { { "1000", "10" }, { "1000", "20" }, { "1000", "40" } };
+        String[][] expected3 = { { "1000", "1010" } };
+        checkDifference(oldRange, newTokens3, expected3);
+
+        // Parts on both ends of the new range are needed
+        String[][] newTokens4 = { { "1000", "50" } };
+        String[][] expected4 = { { "1000", "1010" }, { "40", "50" } };
+        checkDifference(oldRange, newTokens4, expected4);
+    }
+
+    @Test
+    public void testDifferenceToFetchOldWraps()
+    {
+        Range oldRange = makeRange("1010", "40");
+
+        // New range is entirely contained
+        String[][] newTokens1 = { { "0", "30" }, { "0", "40" }, { "10", "40" } };
+        String[][] expected1 = { };
+        checkDifference(oldRange, newTokens1, expected1);
+
+        // Right half of the new range is needed
+        String[][] newTokens2 = { { "0", "50" }, { "10", "50" }, { "40", "50" } };
+        String[][] expected2 = { { "40", "50" } };
+        checkDifference(oldRange, newTokens2, expected2);
+
+        // Whole range is needed
+        String[][] newTokens3 = { { "50", "90" } };
+        String[][] expected3 = { { "50", "90" } };
+        checkDifference(oldRange, newTokens3, expected3);
+
+        // Both ends of the new range overlaps the old range
+        String[][] newTokens4 = { { "10", "1010" }, { "40", "1010" }, { "10", "1030" }, {
"40", "1030" } };
+        String[][] expected4 = { { "40", "1010" } };
+        checkDifference(oldRange, newTokens4, expected4);
+
+        // Only RHS of the new range overlaps the old range
+        String[][] newTokens5 = { { "60", "1010" }, { "60", "1030" } };
+        String[][] expected5 = { { "60", "1010" } };
+        checkDifference(oldRange, newTokens5, expected5);
+    }
+
+    @Test
+    public void testDifferenceToFetchNewWraps()
+    {
+        Range oldRange = makeRange("0", "40");
+
+        // Only the LHS of the new range is needed
+        String[][] newTokens1 = { { "1010", "0" }, { "1010", "10" }, { "1010", "40" } };
+        String[][] expected1 = { { "1010", "0" } };
+        checkDifference(oldRange, newTokens1, expected1);
+
+        // Both ends of the new range are needed
+        String[][] newTokens2 = { { "1010", "50" } };
+        String[][] expected2 = { { "1010", "0" }, { "40", "50" } };
+        checkDifference(oldRange, newTokens2, expected2);
+
+        oldRange = makeRange("20", "40");
+
+        // Whole new range is needed
+        String[][] newTokens3 = { { "1010", "0" } };
+        String[][] expected3 = { { "1010", "0" } };
+        checkDifference(oldRange, newTokens3, expected3);
+
+        // Whole new range is needed (matching endpoints)
+        String[][] newTokens4 = { { "1010", "20" } };
+        String[][] expected4 = { { "1010", "20" } };
+        checkDifference(oldRange, newTokens4, expected4);
+
+        // Only RHS of new range is needed
+        String[][] newTokens5 = { { "30", "0" }, { "40", "0" } };
+        String[][] expected5 = { { "40", "0" } };
+        checkDifference(oldRange, newTokens5, expected5);
+
+        // Only RHS of new range is needed (matching endpoints)
+        String[][] newTokens6 = { { "30", "20" }, { "40", "20" } };
+        String[][] expected6 = { { "40", "20" } };
+        checkDifference(oldRange, newTokens6, expected6);
+    }
 }



Mime
View raw message