cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r1006095 - in /cassandra/branches/cassandra-0.6: ./ src/java/org/apache/cassandra/dht/ src/java/org/apache/cassandra/locator/ src/java/org/apache/cassandra/service/ test/unit/org/apache/cassandra/ test/unit/org/apache/cassandra/dht/ test/un...
Date Sat, 09 Oct 2010 01:26:48 GMT
Author: jbellis
Date: Sat Oct  9 01:26:47 2010
New Revision: 1006095

URL: http://svn.apache.org/viewvc?rev=1006095&view=rev
Log:
Rewrote StorageProxy.getRestrictedRanges to use a more robust algorithm for range scans spanning
multiple nodes.
patch by Stu Hood; reviewed by jbellis for CASSANDRA-1442

Added:
    cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
    cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/service/StorageProxyTest.java
Removed:
    cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/dht/BoundsTest.java
Modified:
    cassandra/branches/cassandra-0.6/CHANGES.txt
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/AbstractBounds.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Bounds.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Range.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackAwareStrategy.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/TokenMetadata.java
    cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/service/StorageProxy.java
    cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/Util.java

Modified: cassandra/branches/cassandra-0.6/CHANGES.txt
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/CHANGES.txt?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/CHANGES.txt (original)
+++ cassandra/branches/cassandra-0.6/CHANGES.txt Sat Oct  9 01:26:47 2010
@@ -45,6 +45,8 @@
  * add cache save/load ability (CASSANDRA-1417)
  * Ignore stray files in the commit log directory (CASSANDRA-1547)
  * Disallow bootstrap to an in-use token (CASSANDRA-1561)
+ * Rewrote StorageProxy.getRestrictedRanges to use a more robust
+   algorithm for range scans spanning multiple nodes (CASSANDRA-1442)
 
 
 0.6.5

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/AbstractBounds.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/AbstractBounds.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/AbstractBounds.java
(original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/AbstractBounds.java
Sat Oct  9 01:26:47 2010
@@ -25,10 +25,9 @@ import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
 import java.io.Serializable;
-import java.util.List;
-import java.util.Set;
 
 import org.apache.cassandra.io.ICompactSerializer2;
+import org.apache.cassandra.utils.Pair;
 
 public abstract class AbstractBounds implements Serializable
 {
@@ -57,6 +56,19 @@ public abstract class AbstractBounds imp
         this.partitioner = partitioner;
     }
 
+    /**
+     * Given token T and AbstractBounds ?L,R], returns Pair(?L,T], ?T,R])
+     * (where ? means that the same type of Bounds is returned -- Range or Bounds -- as the
original.)
+     * The original AbstractBounds must contain the token T.
+     * If R==T, null is returned as the right element of the Pair.
+     */
+    public Pair<AbstractBounds,AbstractBounds> split(Token token)
+    {
+        assert contains(token);
+        Range remainder = token.equals(right) ? null : new Range(token, right);
+        return new Pair<AbstractBounds,AbstractBounds>(createFrom(token), remainder);
+    }
+
     @Override
     public int hashCode()
     {
@@ -68,9 +80,8 @@ public abstract class AbstractBounds imp
 
     public abstract boolean contains(Token start);
 
-    public abstract Set<AbstractBounds> restrictTo(Range range);
-
-    public abstract List<AbstractBounds> unwrap();
+    /** @return A clone of this AbstractBounds with a new right Token. */
+    public abstract AbstractBounds createFrom(Token right);
 
     private static class AbstractBoundsSerializer implements ICompactSerializer2<AbstractBounds>
     {

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Bounds.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Bounds.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Bounds.java (original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Bounds.java Sat Oct
 9 01:26:47 2010
@@ -39,43 +39,14 @@ public class Bounds extends AbstractBoun
         assert left.compareTo(right) <= 0 || right.equals(partitioner.getMinimumToken())
: "[" + left + "," + right + "]";
     }
 
-    @Override
     public boolean contains(Token token)
     {
         return Range.contains(left, right, token) || left.equals(token);
     }
 
-    public Set<AbstractBounds> restrictTo(Range range)
-    {
-        Token min = partitioner.getMinimumToken();
-
-        // special case Bounds where left=right (single Token)
-        if (this.left.equals(this.right) && !this.right.equals(min))
-            return range.contains(this.left)
-                   ? Collections.unmodifiableSet(new HashSet<AbstractBounds>(Arrays.asList(this)))
-                   : Collections.<AbstractBounds>emptySet();
-
-        // get the intersection of a Range w/ same left & right
-        Set<Range> ranges = range.intersectionWith(new Range(this.left, this.right));
-        // if range doesn't contain left token anyway, that's the correct answer
-        if (!range.contains(this.left))
-            return (Set) ranges;
-        // otherwise, add back in the left token
-        Set<AbstractBounds> S = new HashSet<AbstractBounds>(ranges.size());
-        for (Range restricted : ranges)
-        {
-            if (restricted.left.equals(this.left))
-                S.add(new Bounds(restricted.left, restricted.right));
-            else
-                S.add(restricted);
-        }
-        return Collections.unmodifiableSet(S);
-    }
-
-    public List<AbstractBounds> unwrap()
+    public AbstractBounds createFrom(Token token)
     {
-        // Bounds objects never wrap
-        return (List)Arrays.asList(this);
+        return new Bounds(left, token);
     }
 
     @Override

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Range.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Range.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Range.java (original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/dht/Range.java Sat Oct
 9 01:26:47 2010
@@ -25,7 +25,6 @@ import org.apache.commons.lang.ObjectUti
 
 import org.apache.cassandra.service.StorageService;
 
-
 /**
  * A representation of the range that a node is responsible for on the DHT ring.
  *
@@ -188,24 +187,14 @@ public class Range extends AbstractBound
         return Collections.unmodifiableSet(intersection);
     }
 
-    public Set<AbstractBounds> restrictTo(Range range)
-    {
-        return (Set) intersectionWith(range);
-    }
-
-    public List<AbstractBounds> unwrap()
+    public AbstractBounds createFrom(Token token)
     {
-        if (!isWrapAround() || right.equals(partitioner.getMinimumToken()))
-            return (List)Arrays.asList(this);
-        List<AbstractBounds> unwrapped = new ArrayList<AbstractBounds>(2);
-        unwrapped.add(new Range(left, partitioner.getMinimumToken()));
-        unwrapped.add(new Range(partitioner.getMinimumToken(), right));
-        return unwrapped;
+        return new Range(left, token);
     }
 
     /**
      * Tells if the given range is a wrap around.
-         */
+     */
     public static boolean isWrapAround(Token left, Token right)
     {
         return left.compareTo(right) >= 0;
@@ -241,6 +230,7 @@ public class Range extends AbstractBound
         return false;
     }
 
+    @Override
     public boolean equals(Object o)
     {
         if (!(o instanceof Range))
@@ -248,7 +238,8 @@ public class Range extends AbstractBound
         Range rhs = (Range)o;
         return left.equals(rhs.left) && right.equals(rhs.right);
     }
-    
+
+    @Override
     public String toString()
     {
         return "(" + left + "," + right + "]";

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackAwareStrategy.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackAwareStrategy.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackAwareStrategy.java
(original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackAwareStrategy.java
Sat Oct  9 01:26:47 2010
@@ -52,7 +52,7 @@ public class RackAwareStrategy extends A
         if (tokens.isEmpty())
             return endpoints;
 
-        Iterator<Token> iter = TokenMetadata.ringIterator(tokens, token);
+        Iterator<Token> iter = TokenMetadata.ringIterator(tokens, token, false);
         Token primaryToken = iter.next();
         endpoints.add(metadata.getEndPoint(primaryToken));
 
@@ -97,7 +97,7 @@ public class RackAwareStrategy extends A
         // loop through the list and add until we have N nodes.
         if (endpoints.size() < replicas)
         {
-            iter = TokenMetadata.ringIterator(tokens, token);
+            iter = TokenMetadata.ringIterator(tokens, token, false);
             while (endpoints.size() < replicas && iter.hasNext())
             {
                 Token t = iter.next();

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java
(original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/RackUnawareStrategy.java
Sat Oct  9 01:26:47 2010
@@ -50,7 +50,7 @@ public class RackUnawareStrategy extends
             return endpoints;
 
         // Add the token at the index by default
-        Iterator<Token> iter = TokenMetadata.ringIterator(tokens, token);
+        Iterator<Token> iter = TokenMetadata.ringIterator(tokens, token, false);
         while (endpoints.size() < replicas && iter.hasNext())
         {
             endpoints.add(metadata.getEndPoint(iter.next()));

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/TokenMetadata.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/TokenMetadata.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/TokenMetadata.java
(original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/locator/TokenMetadata.java
Sat Oct  9 01:26:47 2010
@@ -27,6 +27,7 @@ import java.util.concurrent.locks.Reentr
 import com.google.common.collect.*;
 import org.apache.cassandra.dht.Token;
 import org.apache.cassandra.dht.Range;
+import org.apache.cassandra.service.StorageService;
 
 import java.net.InetAddress;
 
@@ -390,36 +391,46 @@ public class TokenMetadata
     /**
      * iterator over the Tokens in the given ring, starting with the token for the node owning
start
      * (which does not have to be a Token in the ring)
+     * @param includeMin True if the minimum token should be returned in the ring even if
it has no owner.
      */
-    public static Iterator<Token> ringIterator(final List ring, Token start)
+    public static Iterator<Token> ringIterator(final List ring, Token start, boolean
includeMin)
     {
         assert ring.size() > 0;
+        // insert the minimum token (at index == -1) if we were asked to include it and it
isn't a member of the ring
+        final boolean insertMin = (includeMin && !ring.get(0).equals(StorageService.getPartitioner().getMinimumToken()))
? true : false;
+
         int i = Collections.binarySearch(ring, start);
         if (i < 0)
         {
             i = (i + 1) * (-1);
             if (i >= ring.size())
-            {
-                i = 0;
-            }
+                i = insertMin ? -1 : 0;
         }
+
         final int startIndex = i;
         return new AbstractIterator<Token>()
         {
             int j = startIndex;
             protected Token computeNext()
             {
-                if (j < 0)
+                if (j < -1)
                     return endOfData();
                 try
                 {
+                    // return minimum for index == -1
+                    if (j == -1)
+                        return StorageService.getPartitioner().getMinimumToken();
+                    // return ring token for other indexes
                     return (Token) ring.get(j);
                 }
                 finally
                 {
-                    j = (j + 1) % ring.size();
+                    j++;
+                    if (j == ring.size())
+                        j = insertMin ? -1 : 0;
                     if (j == startIndex)
-                        j = -1;
+                        // end iteration
+                        j = -2;
                 }
             }
         };

Modified: cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/service/StorageProxy.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/service/StorageProxy.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/service/StorageProxy.java
(original)
+++ cassandra/branches/cassandra-0.6/src/java/org/apache/cassandra/service/StorageProxy.java
Sat Oct  9 01:26:47 2010
@@ -32,15 +32,11 @@ import javax.management.ObjectName;
 
 import com.google.common.collect.Multimap;
 import org.apache.commons.lang.ArrayUtils;
-import org.apache.commons.lang.StringUtils;
 
 import org.apache.cassandra.concurrent.StageManager;
 import org.apache.cassandra.config.DatabaseDescriptor;
 import org.apache.cassandra.db.*;
-import org.apache.cassandra.dht.AbstractBounds;
-import org.apache.cassandra.dht.IPartitioner;
-import org.apache.cassandra.dht.Range;
-import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.dht.*;
 import org.apache.cassandra.locator.AbstractReplicationStrategy;
 import org.apache.cassandra.locator.TokenMetadata;
 import org.apache.cassandra.net.IAsyncResult;
@@ -51,6 +47,7 @@ import org.apache.cassandra.thrift.Inval
 import org.apache.cassandra.thrift.UnavailableException;
 import org.apache.cassandra.utils.FBUtilities;
 import org.apache.cassandra.utils.LatencyTracker;
+import org.apache.cassandra.utils.Pair;
 import org.apache.cassandra.utils.WrappedRunnable;
 import org.apache.log4j.Logger;
 
@@ -600,71 +597,39 @@ public class StorageProxy implements Sto
     }
 
     /**
-     * compute all ranges we're going to query, in sorted order, so that we get the correct
results back.
-     *  1) computing range intersections is necessary because nodes can be replica destinations
for many ranges,
-     *     so if we do not restrict each scan to the specific range we want we will get duplicate
results.
-     *  2) sorting the intersection ranges is necessary because wraparound node ranges can
be discontiguous.
-     *     Consider a 2-node ring, (D, T] and (T, D]. A query for [A, Z] will intersect the
2nd node twice,
-     *     at [A, D] and (T, Z]. We need to scan the (D, T] range in between those, or we
will skip those
-     *     results entirely if the limit is low enough.
-     *  3) we unwrap the intersection ranges because otherwise we get results in the wrong
order.
-     *     Consider a 2-node ring, (D, T] and (T, D].  A query for [D, Z] will get results
in the wrong
-     *     order if we use (T, D] directly -- we need to start with that range, because our
query starts with
-     *     D, but we don't want any other results from it until after the (D, T] range. 
Unwrapping so that
-     *     the ranges we consider are (D, T], (T, MIN], (MIN, D] fixes this.
+     * Compute all ranges we're going to query, in sorted order. Nodes can be replica destinations
for many ranges,
+     * so we need to restrict each scan to the specific range we want, or else we'd get duplicate
results.
      */
-    private static List<AbstractBounds> getRestrictedRanges(final AbstractBounds queryRange)
+    static List<AbstractBounds> getRestrictedRanges(final AbstractBounds queryRange)
     {
-        TokenMetadata tokenMetadata = StorageService.instance.getTokenMetadata();
+        // special case for bounds containing exactly 1 token
+        if (queryRange instanceof Bounds && queryRange.left.equals(queryRange.right))
+        {
+            if (logger.isDebugEnabled())
+                logger.debug("restricted single token match for query " + queryRange);
+            return Collections.singletonList(queryRange);
+        }
 
-        if (logger.isDebugEnabled())
-            logger.debug("computing restricted ranges for query " + queryRange);
+        TokenMetadata tokenMetadata = StorageService.instance.getTokenMetadata();
 
         List<AbstractBounds> ranges = new ArrayList<AbstractBounds>();
-        // for each node, compute its intersection with the query range, and add its unwrapped
components to our list
-        for (Token nodeToken : tokenMetadata.sortedTokens())
-        {
-            Range nodeRange = new Range(tokenMetadata.getPredecessor(nodeToken), nodeToken);
-            for (AbstractBounds range : queryRange.restrictTo(nodeRange))
-            {
-                for (AbstractBounds unwrapped : range.unwrap())
-                {
-                    if (logger.isDebugEnabled())
-                        logger.debug("Adding to restricted ranges " + unwrapped + " for "
+ nodeRange);
-                    ranges.add(unwrapped);
-                }
-            }
+        // divide the queryRange into pieces delimited by the ring and minimum tokens
+        Iterator<Token> ringIter = TokenMetadata.ringIterator(tokenMetadata.sortedTokens(),
queryRange.left, true);
+        AbstractBounds remainder = queryRange;
+        while (ringIter.hasNext())
+        {
+            Token token = ringIter.next();
+            if (remainder == null || !remainder.contains(token))
+                // no more splits
+                break;
+            Pair<AbstractBounds,AbstractBounds> splits = remainder.split(token);
+            ranges.add(splits.left);
+            remainder = splits.right;
         }
-
-        // re-sort ranges in ring order, post-unwrapping
-        Comparator<AbstractBounds> comparator = new Comparator<AbstractBounds>()
-        {
-            // no restricted ranges will overlap so we don't need to worry about inclusive
vs exclusive left,
-            // just sort by raw token position.
-            public int compare(AbstractBounds o1, AbstractBounds o2)
-            {
-                // sort in order that the original query range would see them.
-                int queryOrder1 = queryRange.left.compareTo(o1.left);
-                int queryOrder2 = queryRange.left.compareTo(o2.left);
-
-                // check for exact match with query start
-                assert !(queryOrder1 == 0 && queryOrder2 == 0);
-                if (queryOrder1 == 0)
-                    return -1;
-                if (queryOrder2 == 0)
-                    return 1;
-
-                // order segments in order they should be traversed
-                if (queryOrder1 < queryOrder2)
-                    return -1; // o1 comes after query start, o2 wraps to after
-                if (queryOrder1 > queryOrder2)
-                    return 1; // o2 comes after query start, o1 wraps to after
-                return o1.left.compareTo(o2.left); // o1 and o2 are on the same side of query
start
-            }
-        };
-        Collections.sort(ranges, comparator);
+        if (remainder != null)
+            ranges.add(remainder);
         if (logger.isDebugEnabled())
-            logger.debug("Sorted ranges are [" + StringUtils.join(ranges, ", ") + "]");
+            logger.debug("restricted ranges for query " + queryRange + " are " + ranges);
 
         return ranges;
     }

Modified: cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/Util.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/Util.java?rev=1006095&r1=1006094&r2=1006095&view=diff
==============================================================================
--- cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/Util.java (original)
+++ cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/Util.java Sat Oct  9 01:26:47
2010
@@ -31,9 +31,7 @@ import org.apache.commons.lang.ArrayUtil
 
 import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.filter.QueryPath;
-import org.apache.cassandra.dht.Bounds;
-import org.apache.cassandra.dht.Range;
-import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.dht.*;
 import org.apache.cassandra.service.StorageService;
 import org.apache.cassandra.thrift.SliceRange;
 
@@ -44,6 +42,21 @@ public class Util
         return new Column(name.getBytes(), value.getBytes(), timestamp);
     }
 
+    public static Token token(String key)
+    {
+        return StorageService.getPartitioner().getToken(key);
+    }
+
+    public static Range range(String left, String right)
+    {
+        return new Range(token(left), token(right));
+    }
+
+    public static Bounds bounds(String left, String right)
+    {
+        return new Bounds(token(left), token(right));
+    }
+
     public static void addMutation(RowMutation rm, String columnFamilyName, String superColumnName,
long columnName, String value, long timestamp)
     {
         rm.add(new QueryPath(columnFamilyName, superColumnName.getBytes(), getBytes(columnName)),
value.getBytes(), timestamp);

Added: cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java?rev=1006095&view=auto
==============================================================================
--- cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
(added)
+++ cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
Sat Oct  9 01:26:47 2010
@@ -0,0 +1,80 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements.  See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership.  The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License.  You may obtain a copy of the License at
+*
+*    http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied.  See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package org.apache.cassandra.locator;
+
+import java.net.InetAddress;
+import java.util.ArrayList;
+import java.util.List;
+
+import com.google.common.collect.Iterators;
+
+import org.junit.BeforeClass;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+import org.apache.cassandra.CleanupHelper;
+import static org.apache.cassandra.Util.token;
+
+import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.locator.TokenMetadata;
+import org.apache.cassandra.service.StorageService;
+
+public class TokenMetadataTest
+{
+    public final static String ONE = "1";
+    public final static String SIX = "6";
+
+    public static List<Token> RING;
+
+    @BeforeClass
+    public static void beforeClass() throws Throwable
+    {
+        TokenMetadata tmd = StorageService.instance.getTokenMetadata();
+        tmd.updateNormalToken(token(ONE), InetAddress.getByName("127.0.0.1"));
+        tmd.updateNormalToken(token(SIX), InetAddress.getByName("127.0.0.6"));
+        RING = tmd.sortedTokens();
+    }
+
+    private void testRingIterator(String start, boolean includeMin, String... expected)
+    {
+        ArrayList<Token> actual = new ArrayList<Token>();
+        Iterators.addAll(actual, TokenMetadata.ringIterator(RING, token(start), includeMin));
+        assertEquals(actual.toString(), expected.length, actual.size());
+        for (int i = 0; i < expected.length; i++)
+            assertEquals("Mismatch at index " + i + ": " + actual, token(expected[i]), actual.get(i));
+    }
+
+    @Test
+    public void testRingIterator()
+    {
+        testRingIterator("2", false, "6", "1");
+        testRingIterator("7", false, "1", "6");
+        testRingIterator("0", false, "1", "6");
+        testRingIterator("", false, "1", "6");
+    }
+
+    @Test
+    public void testRingIteratorIncludeMin()
+    {
+        testRingIterator("2", true, "6", "", "1");
+        testRingIterator("7", true, "", "1", "6");
+        testRingIterator("0", true, "1", "6", "");
+        testRingIterator("", true, "1", "6", "");
+    }
+}

Added: cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/service/StorageProxyTest.java
URL: http://svn.apache.org/viewvc/cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/service/StorageProxyTest.java?rev=1006095&view=auto
==============================================================================
--- cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/service/StorageProxyTest.java
(added)
+++ cassandra/branches/cassandra-0.6/test/unit/org/apache/cassandra/service/StorageProxyTest.java
Sat Oct  9 01:26:47 2010
@@ -0,0 +1,108 @@
+/*
+* Licensed to the Apache Software Foundation (ASF) under one
+* or more contributor license agreements.  See the NOTICE file
+* distributed with this work for additional information
+* regarding copyright ownership.  The ASF licenses this file
+* to you under the Apache License, Version 2.0 (the
+* "License"); you may not use this file except in compliance
+* with the License.  You may obtain a copy of the License at
+*
+*    http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing,
+* software distributed under the License is distributed on an
+* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+* KIND, either express or implied.  See the License for the
+* specific language governing permissions and limitations
+* under the License.
+*/
+package org.apache.cassandra.service;
+
+import java.net.InetAddress;
+import java.util.List;
+
+import org.junit.BeforeClass;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+import org.apache.cassandra.CleanupHelper;
+import static org.apache.cassandra.Util.range;
+import static org.apache.cassandra.Util.bounds;
+
+import org.apache.cassandra.dht.AbstractBounds;
+import org.apache.cassandra.locator.TokenMetadata;
+
+public class StorageProxyTest extends CleanupHelper
+{
+    @BeforeClass
+    public static void beforeClass() throws Throwable
+    {
+        TokenMetadata tmd = StorageService.instance.getTokenMetadata();
+        tmd.updateNormalToken(StorageService.getPartitioner().getToken("1"), InetAddress.getByName("127.0.0.1"));
+        tmd.updateNormalToken(StorageService.getPartitioner().getToken("6"), InetAddress.getByName("127.0.0.6"));
+    }
+
+    private void testGRR(AbstractBounds queryRange, AbstractBounds... expected)
+    {
+        List<AbstractBounds> restricted = StorageProxy.getRestrictedRanges(queryRange);
+        assertEquals(restricted.toString(), expected.length, restricted.size());
+        for (int i = 0; i < expected.length; i++)
+            assertEquals("Mismatch for index " + i + ": " + restricted, expected[i], restricted.get(i));
+    }
+
+    @Test
+    public void testGRR() throws Throwable
+    {
+        // no splits
+        testGRR(range("2", "5"), range("2", "5"));
+        testGRR(bounds("2", "5"), bounds("2", "5"));
+        // single split
+        testGRR(range("2", "7"), range("2", "6"), range("6", "7"));
+        testGRR(bounds("2", "7"), bounds("2", "6"), range("6", "7"));
+        // single split starting from min
+        testGRR(range("", "2"), range("", "1"), range("1", "2"));
+        testGRR(bounds("", "2"), bounds("", "1"), range("1", "2"));
+        // single split ending with max
+        testGRR(range("5", ""), range("5", "6"), range("6", ""));
+        testGRR(bounds("5", ""), bounds("5", "6"), range("6", ""));
+        // two splits
+        testGRR(range("0", "7"), range("0", "1"), range("1", "6"), range("6", "7"));
+        testGRR(bounds("0", "7"), bounds("0", "1"), range("1", "6"), range("6", "7"));
+    }
+
+    @Test
+    public void testGRRExact() throws Throwable
+    {
+        // min
+        testGRR(range("1", "5"), range("1", "5"));
+        testGRR(bounds("1", "5"), bounds("1", "1"), range("1", "5"));
+        // max
+        testGRR(range("2", "6"), range("2", "6"));
+        testGRR(bounds("2", "6"), bounds("2", "6"));
+        // both
+        testGRR(range("1", "6"), range("1", "6"));
+        testGRR(bounds("1", "6"), bounds("1", "1"), range("1", "6"));
+    }
+
+    @Test
+    public void testGRRWrapped() throws Throwable
+    {
+        // one token in wrapped range
+        testGRR(range("7", "0"), range("7", ""), range("", "0"));
+        // two tokens in wrapped range
+        testGRR(range("5", "0"), range("5", "6"), range("6", ""), range("", "0"));
+        testGRR(range("7", "2"), range("7", ""), range("", "1"), range("1", "2"));
+        // full wraps
+        testGRR(range("0", "0"), range("0", "1"), range("1", "6"), range("6", ""), range("",
"0"));
+        testGRR(range("", ""), range("", "1"), range("1", "6"), range("6", ""));
+        // end wrapped
+        testGRR(range("5", ""), range("5", "6"), range("6", ""));
+    }
+
+    @Test
+    public void testGRRExactBounds() throws Throwable
+    {
+        // equal tokens are special cased as non-wrapping for bounds
+        testGRR(bounds("0", "0"), bounds("0", "0"));
+    }
+}



Mime
View raw message