cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject svn commit: r1006105 - in /cassandra/trunk: 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/unit/org/apache/cassan...
Date Sat, 09 Oct 2010 02:32:16 GMT
Author: jbellis
Date: Sat Oct  9 02:32:16 2010
New Revision: 1006105

URL: http://svn.apache.org/viewvc?rev=1006105&view=rev
Log:
merge from 0.6

Added:
    cassandra/trunk/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
    cassandra/trunk/test/unit/org/apache/cassandra/service/StorageProxyTest.java
Removed:
    cassandra/trunk/test/unit/org/apache/cassandra/dht/BoundsTest.java
Modified:
    cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java
    cassandra/trunk/src/java/org/apache/cassandra/dht/Bounds.java
    cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java
    cassandra/trunk/src/java/org/apache/cassandra/locator/NetworkTopologyStrategy.java
    cassandra/trunk/src/java/org/apache/cassandra/locator/OldNetworkTopologyStrategy.java
    cassandra/trunk/src/java/org/apache/cassandra/locator/SimpleStrategy.java
    cassandra/trunk/src/java/org/apache/cassandra/locator/TokenMetadata.java
    cassandra/trunk/src/java/org/apache/cassandra/service/StorageProxy.java
    cassandra/trunk/test/unit/org/apache/cassandra/Util.java
    cassandra/trunk/test/unit/org/apache/cassandra/service/MoveTest.java

Modified: cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java Sat Oct  9 02:32:16
2010
@@ -28,6 +28,7 @@ import java.io.Serializable;
 import java.util.*;
 
 import org.apache.cassandra.io.ICompactSerializer2;
+import org.apache.cassandra.utils.Pair;
 
 public abstract class AbstractBounds implements Serializable
 {
@@ -56,6 +57,20 @@ 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()
     {
@@ -67,7 +82,8 @@ public abstract class AbstractBounds imp
 
     public abstract boolean contains(Token start);
 
-    public abstract Set<AbstractBounds> restrictTo(Range range);
+    /** @return A clone of this AbstractBounds with a new right Token. */
+    public abstract AbstractBounds createFrom(Token right);
 
     public abstract List<AbstractBounds> unwrap();
 

Modified: cassandra/trunk/src/java/org/apache/cassandra/dht/Bounds.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/dht/Bounds.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/dht/Bounds.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/dht/Bounds.java Sat Oct  9 02:32:16 2010
@@ -39,43 +39,20 @@ 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)
+    public AbstractBounds createFrom(Token token)
     {
-        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);
+        return new Bounds(left, token);
     }
 
     public List<AbstractBounds> unwrap()
     {
         // Bounds objects never wrap
-        return (List)Arrays.asList(this);
+        return Collections.<AbstractBounds>singletonList(this);
     }
 
     @Override

Modified: cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java Sat Oct  9 02:32:16 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,9 +187,9 @@ public class Range extends AbstractBound
         return Collections.unmodifiableSet(intersection);
     }
 
-    public Set<AbstractBounds> restrictTo(Range range)
+    public AbstractBounds createFrom(Token token)
     {
-        return (Set) intersectionWith(range);
+        return new Range(left, token);
     }
 
     public List<AbstractBounds> unwrap()
@@ -205,7 +204,7 @@ public class Range extends AbstractBound
 
     /**
      * Tells if the given range is a wrap around.
-         */
+     */
     public static boolean isWrapAround(Token left, Token right)
     {
         return left.compareTo(right) >= 0;
@@ -241,6 +240,7 @@ public class Range extends AbstractBound
         return false;
     }
 
+    @Override
     public boolean equals(Object o)
     {
         if (!(o instanceof Range))

Modified: cassandra/trunk/src/java/org/apache/cassandra/locator/NetworkTopologyStrategy.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/locator/NetworkTopologyStrategy.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/locator/NetworkTopologyStrategy.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/locator/NetworkTopologyStrategy.java Sat
Oct  9 02:32:16 2010
@@ -87,7 +87,7 @@ public class NetworkTopologyStrategy ext
             List<InetAddress> dcEndpoints = new ArrayList<InetAddress>(dcReplicas);
             Set<String> racks = new HashSet<String>();
             // first pass: only collect replicas on unique racks
-            for (Iterator<Token> iter = TokenMetadata.ringIterator(dcTokens.sortedTokens(),
searchToken);
+            for (Iterator<Token> iter = TokenMetadata.ringIterator(dcTokens.sortedTokens(),
searchToken, false);
                  dcEndpoints.size() < dcReplicas && iter.hasNext(); )
             {
                 Token token = iter.next();
@@ -101,7 +101,7 @@ public class NetworkTopologyStrategy ext
             }
 
             // second pass: if replica count has not been achieved from unique racks, add
nodes from duplicate racks
-            for (Iterator<Token> iter = TokenMetadata.ringIterator(dcTokens.sortedTokens(),
searchToken);
+            for (Iterator<Token> iter = TokenMetadata.ringIterator(dcTokens.sortedTokens(),
searchToken, false);
                  dcEndpoints.size() < dcReplicas && iter.hasNext(); )
             {
                 Token token = iter.next();

Modified: cassandra/trunk/src/java/org/apache/cassandra/locator/OldNetworkTopologyStrategy.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/locator/OldNetworkTopologyStrategy.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/locator/OldNetworkTopologyStrategy.java
(original)
+++ cassandra/trunk/src/java/org/apache/cassandra/locator/OldNetworkTopologyStrategy.java
Sat Oct  9 02:32:16 2010
@@ -47,7 +47,7 @@ public class OldNetworkTopologyStrategy 
         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));
 
@@ -85,7 +85,7 @@ public class OldNetworkTopologyStrategy 
         // 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/trunk/src/java/org/apache/cassandra/locator/SimpleStrategy.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/locator/SimpleStrategy.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/locator/SimpleStrategy.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/locator/SimpleStrategy.java Sat Oct  9 02:32:16
2010
@@ -47,7 +47,7 @@ public class SimpleStrategy extends Abst
             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/trunk/src/java/org/apache/cassandra/locator/TokenMetadata.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/locator/TokenMetadata.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/locator/TokenMetadata.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/locator/TokenMetadata.java Sat Oct  9 02:32:16
2010
@@ -34,6 +34,7 @@ import org.slf4j.LoggerFactory;
 import com.google.common.collect.*;
 import org.apache.cassandra.dht.Range;
 import org.apache.cassandra.dht.Token;
+import org.apache.cassandra.service.StorageService;
 
 public class TokenMetadata
 {
@@ -386,49 +387,57 @@ public class TokenMetadata
         return leavingEndpoints;
     }
 
-    public static int firstTokenIndex(final ArrayList ring, Token start)
+    public static int firstTokenIndex(final ArrayList ring, Token start, boolean insertMin)
     {
         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
         int i = Collections.binarySearch(ring, start);
         if (i < 0)
         {
             i = (i + 1) * (-1);
             if (i >= ring.size())
-            {
-                i = 0;
-            }
+                i = insertMin ? -1 : 0;
         }
         return i;
     }
 
     public static Token firstToken(final ArrayList<Token> ring, Token start)
     {
-        return ring.get(firstTokenIndex(ring, start));
+        return ring.get(firstTokenIndex(ring, start, false));
     }
 
     /**
-     * <tt>Iterator</tt> over the <tt>Token</tt>s in the given ring,
starting with the token for the node owning start
-     * (which does not have to be a <tt>Token</tt> in the ring)
+     * 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 ArrayList<Token> ring, Token
start)
+    public static Iterator<Token> ringIterator(final ArrayList<Token> ring, Token
start, boolean includeMin)
     {
-        final int startIndex = firstTokenIndex(ring, start);
+        final boolean insertMin = (includeMin && !ring.get(0).equals(StorageService.getPartitioner().getMinimumToken()))
? true : false;
+        final int startIndex = firstTokenIndex(ring, start, insertMin);
         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 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/trunk/src/java/org/apache/cassandra/service/StorageProxy.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/service/StorageProxy.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/service/StorageProxy.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/service/StorageProxy.java Sat Oct  9 02:32:16
2010
@@ -53,6 +53,7 @@ import org.apache.cassandra.net.Messagin
 import org.apache.cassandra.thrift.*;
 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.cassandra.db.filter.QueryFilter;
 
@@ -550,71 +551,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/trunk/test/unit/org/apache/cassandra/Util.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/Util.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/Util.java (original)
+++ cassandra/trunk/test/unit/org/apache/cassandra/Util.java Sat Oct  9 02:32:16 2010
@@ -36,11 +36,7 @@ import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.columniterator.IdentityQueryFilter;
 import org.apache.cassandra.db.filter.QueryFilter;
 import org.apache.cassandra.db.filter.QueryPath;
-import org.apache.cassandra.dht.BigIntegerToken;
-import org.apache.cassandra.dht.Bounds;
-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.gms.ApplicationState;
 import org.apache.cassandra.gms.VersionedValue;
 import org.apache.cassandra.locator.AbstractReplicationStrategy;
@@ -60,11 +56,26 @@ public class Util
         return new Column(name.getBytes(), value.getBytes(), clock);
     }
 
+    public static Token token(String key)
+    {
+        return StorageService.getPartitioner().getToken(key.getBytes());
+    }
+
+    public static Range range(String left, String right)
+    {
+        return new Range(token(left), token(right));
+    }
+
     public static Range range(IPartitioner p, String left, String right)
     {
         return new Range(p.getToken(left.getBytes()), p.getToken(right.getBytes()));
     }
 
+    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, IClock clock)
     {
         rm.add(new QueryPath(columnFamilyName, superColumnName.getBytes(), getBytes(columnName)),
value.getBytes(), clock);

Added: cassandra/trunk/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java?rev=1006105&view=auto
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java (added)
+++ cassandra/trunk/test/unit/org/apache/cassandra/locator/TokenMetadataTest.java Sat Oct
 9 02:32:16 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 ArrayList<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", "");
+    }
+}

Modified: cassandra/trunk/test/unit/org/apache/cassandra/service/MoveTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/service/MoveTest.java?rev=1006105&r1=1006104&r2=1006105&view=diff
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/service/MoveTest.java (original)
+++ cassandra/trunk/test/unit/org/apache/cassandra/service/MoveTest.java Sat Oct  9 02:32:16
2010
@@ -71,7 +71,7 @@ public class MoveTest extends CleanupHel
             for (Token token : keyTokens)
             {
                 List<InetAddress> endpoints = new ArrayList<InetAddress>();
-                Iterator<Token> tokenIter = TokenMetadata.ringIterator(tmd.sortedTokens(),
token);
+                Iterator<Token> tokenIter = TokenMetadata.ringIterator(tmd.sortedTokens(),
token, false);
                 while (tokenIter.hasNext())
                 {
                     endpoints.add(tmd.getEndpoint(tokenIter.next()));

Added: cassandra/trunk/test/unit/org/apache/cassandra/service/StorageProxyTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/service/StorageProxyTest.java?rev=1006105&view=auto
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/service/StorageProxyTest.java (added)
+++ cassandra/trunk/test/unit/org/apache/cassandra/service/StorageProxyTest.java Sat Oct 
9 02:32:16 2010
@@ -0,0 +1,109 @@
+/*
+* 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 static org.apache.cassandra.Util.token;
+
+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(token("1"), InetAddress.getByName("127.0.0.1"));
+        tmd.updateNormalToken(token("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