You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2010/10/09 04:32:16 UTC
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...
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"));
+ }
+}