Repository: cassandra Updated Branches: refs/heads/trunk 88b244a13 -> 4c80eeece
http://git-wip-us.apache.org/repos/asf/cassandra/blob/4c80eeec/test/unit/org/apache/cassandra/dht/SplitterTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/dht/SplitterTest.java b/test/unit/org/apache/cassandra/dht/SplitterTest.java index 751a7d7..409e333 100644 --- a/test/unit/org/apache/cassandra/dht/SplitterTest.java +++ b/test/unit/org/apache/cassandra/dht/SplitterTest.java @@ -24,9 +24,14 @@ import java.util.Collections; import java.util.List; import java.util.Random; import java.util.Set; +import java.util.stream.Collectors; import org.junit.Test; +import org.apache.cassandra.utils.Pair; + +import static com.google.common.collect.Sets.newHashSet; +import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; @@ -50,34 +55,35 @@ public class SplitterTest { randomSplitTestVNodes(new RandomPartitioner()); } + @Test public void randomSplitTestVNodesMurmur3Partitioner() { randomSplitTestVNodes(new Murmur3Partitioner()); } - public void randomSplitTestNoVNodes(IPartitioner partitioner) + private static void randomSplitTestNoVNodes(IPartitioner partitioner) { - Splitter splitter = partitioner.splitter().get(); + Splitter splitter = getSplitter(partitioner); Random r = new Random(); for (int i = 0; i < 10000; i++) { - List<Range<Token>> localRanges = generateLocalRanges(1, r.nextInt(4)+1, splitter, r, partitioner instanceof RandomPartitioner); + List<Range<Token>> localRanges = generateLocalRanges(1, r.nextInt(4) + 1, splitter, r, partitioner instanceof RandomPartitioner); List<Token> boundaries = splitter.splitOwnedRanges(r.nextInt(9) + 1, localRanges, false); - assertTrue("boundaries = "+boundaries+" ranges = "+localRanges, assertRangeSizeEqual(localRanges, boundaries, partitioner, splitter, true)); + assertTrue("boundaries = " + boundaries + " ranges = " + localRanges, assertRangeSizeEqual(localRanges, boundaries, partitioner, splitter, true)); } } - public void randomSplitTestVNodes(IPartitioner partitioner) + private static void randomSplitTestVNodes(IPartitioner partitioner) { - Splitter splitter = partitioner.splitter().get(); + Splitter splitter = getSplitter(partitioner); Random r = new Random(); for (int i = 0; i < 10000; i++) { // we need many tokens to be able to split evenly over the disks int numTokens = 172 + r.nextInt(128); int rf = r.nextInt(4) + 2; - int parts = r.nextInt(5)+1; + int parts = r.nextInt(5) + 1; List<Range<Token>> localRanges = generateLocalRanges(numTokens, rf, splitter, r, partitioner instanceof RandomPartitioner); List<Token> boundaries = splitter.splitOwnedRanges(parts, localRanges, true); if (!assertRangeSizeEqual(localRanges, boundaries, partitioner, splitter, false)) @@ -85,7 +91,7 @@ public class SplitterTest } } - private boolean assertRangeSizeEqual(List<Range<Token>> localRanges, List<Token> tokens, IPartitioner partitioner, Splitter splitter, boolean splitIndividualRanges) + private static boolean assertRangeSizeEqual(List<Range<Token>> localRanges, List<Token> tokens, IPartitioner partitioner, Splitter splitter, boolean splitIndividualRanges) { Token start = partitioner.getMinimumToken(); List<BigInteger> splits = new ArrayList<>(); @@ -113,7 +119,7 @@ public class SplitterTest return allBalanced; } - private BigInteger sumOwnedBetween(List<Range<Token>> localRanges, Token start, Token end, Splitter splitter, boolean splitIndividualRanges) + private static BigInteger sumOwnedBetween(List<Range<Token>> localRanges, Token start, Token end, Splitter splitter, boolean splitIndividualRanges) { BigInteger sum = BigInteger.ZERO; for (Range<Token> range : localRanges) @@ -133,7 +139,7 @@ public class SplitterTest return sum; } - private List<Range<Token>> generateLocalRanges(int numTokens, int rf, Splitter splitter, Random r, boolean randomPartitioner) + private static List<Range<Token>> generateLocalRanges(int numTokens, int rf, Splitter splitter, Random r, boolean randomPartitioner) { int localTokens = numTokens * rf; List<Token> randomTokens = new ArrayList<>(); @@ -149,10 +155,327 @@ public class SplitterTest List<Range<Token>> localRanges = new ArrayList<>(localTokens); for (int i = 0; i < randomTokens.size() - 1; i++) { - assert randomTokens.get(i).compareTo(randomTokens.get(i+1)) < 0; - localRanges.add(new Range<>(randomTokens.get(i), randomTokens.get(i+1))); + assert randomTokens.get(i).compareTo(randomTokens.get(i + 1)) < 0; + localRanges.add(new Range<>(randomTokens.get(i), randomTokens.get(i + 1))); i++; } return localRanges; } + + @Test + public void testSplitMurmur3Partitioner() + { + testSplit(new Murmur3Partitioner()); + } + + @Test + public void testSplitRandomPartitioner() + { + testSplit(new RandomPartitioner()); + } + + @SuppressWarnings("unchecked") + private static void testSplit(IPartitioner partitioner) + { + boolean isRandom = partitioner instanceof RandomPartitioner; + Splitter splitter = getSplitter(partitioner); + BigInteger min = splitter.valueForToken(partitioner.getMinimumToken()); + BigInteger max = splitter.valueForToken(partitioner.getMaximumToken()); + BigInteger first = isRandom ? RandomPartitioner.ZERO : min; + BigInteger last = isRandom ? max.subtract(BigInteger.valueOf(1)) : max; + BigInteger midpoint = last.add(first).divide(BigInteger.valueOf(2)); + + // regular single range + testSplit(partitioner, 1, newHashSet(Pair.create(1, 100)), newHashSet(Pair.create(1, 100))); + testSplit(partitioner, 2, + newHashSet(Pair.create(1, 100)), + newHashSet(Pair.create(1, 50), Pair.create(50, 100))); + testSplit(partitioner, 4, + newHashSet(Pair.create(1, 100)), + newHashSet(Pair.create(1, 25), Pair.create(25, 50), Pair.create(50, 75), Pair.create(75, 100))); + testSplit(partitioner, 5, + newHashSet(Pair.create(3, 79)), + newHashSet(Pair.create(3, 18), Pair.create(18, 33), Pair.create(33, 48), Pair.create(48, 63), + Pair.create(63, 79))); + testSplit(partitioner, 3, + newHashSet(Pair.create(3, 20)), + newHashSet(Pair.create(3, 8), Pair.create(8, 14), Pair.create(14, 20))); + testSplit(partitioner, 4, + newHashSet(Pair.create(3, 20)), + newHashSet(Pair.create(3, 7), Pair.create(7, 11), Pair.create(11, 15), Pair.create(15, 20))); + + // single range too small to be partitioned + testSplit(partitioner, 1, newHashSet(Pair.create(1, 2)), newHashSet(Pair.create(1, 2))); + testSplit(partitioner, 2, newHashSet(Pair.create(1, 2)), newHashSet(Pair.create(1, 2))); + testSplit(partitioner, 4, newHashSet(Pair.create(1, 4)), newHashSet(Pair.create(1, 4))); + testSplit(partitioner, 8, newHashSet(Pair.create(1, 2)), newHashSet(Pair.create(1, 2))); + + // single wrapping range + BigInteger cutpoint = isRandom ? midpoint.add(BigInteger.valueOf(7)) : min.add(BigInteger.valueOf(6)); + testSplit(partitioner, 2, + newHashSet(Pair.create(8, 4)), + newHashSet(Pair.create(8, cutpoint), Pair.create(cutpoint, 4))); + + // single range around partitioner min/max values + testSplit(partitioner, 2, + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(8)), min)), + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(8)), max.subtract(BigInteger.valueOf(4))), + Pair.create(max.subtract(BigInteger.valueOf(4)), isRandom ? first : max))); + testSplit(partitioner, 2, + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(8)), max)), + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(8)), max.subtract(BigInteger.valueOf(4))), + Pair.create(max.subtract(BigInteger.valueOf(4)), max))); + testSplit(partitioner, 2, + newHashSet(Pair.create(min, min.add(BigInteger.valueOf(8)))), + newHashSet(Pair.create(min, min.add(BigInteger.valueOf(4))), + Pair.create(min.add(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(8))))); + testSplit(partitioner, 2, + newHashSet(Pair.create(max, min.add(BigInteger.valueOf(8)))), + newHashSet(Pair.create(max, min.add(BigInteger.valueOf(4))), + Pair.create(min.add(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(8))))); + testSplit(partitioner, 2, + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(4)))), + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(4)), last), + Pair.create(last, min.add(BigInteger.valueOf(4))))); + testSplit(partitioner, 2, + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(8)))), + newHashSet(Pair.create(max.subtract(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(2))), + Pair.create(min.add(BigInteger.valueOf(2)), min.add(BigInteger.valueOf(8))))); + + // multiple ranges + testSplit(partitioner, 1, + newHashSet(Pair.create(1, 100), Pair.create(200, 300)), + newHashSet(Pair.create(1, 100), Pair.create(200, 300))); + testSplit(partitioner, 2, + newHashSet(Pair.create(1, 100), Pair.create(200, 300)), + newHashSet(Pair.create(1, 100), Pair.create(200, 300))); + testSplit(partitioner, 4, + newHashSet(Pair.create(1, 100), Pair.create(200, 300)), + newHashSet(Pair.create(1, 50), Pair.create(50, 100), Pair.create(200, 250), Pair.create(250, 300))); + testSplit(partitioner, 4, + newHashSet(Pair.create(1, 100), + Pair.create(200, 300), + Pair.create(max.subtract(BigInteger.valueOf(4)), min.add(BigInteger.valueOf(4)))), + newHashSet(Pair.create(1, 50), + Pair.create(50, 100), + Pair.create(200, 250), + Pair.create(250, 300), + Pair.create(last, min.add(BigInteger.valueOf(4))), + Pair.create(max.subtract(BigInteger.valueOf(4)), last))); + } + + private static void testSplit(IPartitioner partitioner, int parts, Set<Pair<Object, Object>> ranges, Set<Pair<Object, Object>> expected) + { + Splitter splitter = getSplitter(partitioner); + Set<Range<Token>> splittedRanges = splitter.split(ranges(partitioner, ranges), parts); + assertEquals(ranges(partitioner, expected), splittedRanges); + } + + private static Set<Range<Token>> ranges(IPartitioner partitioner, Set<Pair<Object, Object>> pairs) + { + return pairs.stream().map(pair -> range(partitioner, pair)).collect(Collectors.toSet()); + } + + private static Range<Token> range(IPartitioner partitioner, Pair<?, ?> pair) + { + return new Range<>(token(partitioner, pair.left), token(partitioner, pair.right)); + } + + private static Token token(IPartitioner partitioner, Object n) + { + return partitioner.getTokenFactory().fromString(n.toString()); + } + + @Test + public void testTokensInRangeRandomPartitioner() + { + testTokensInRange(new RandomPartitioner()); + } + + @Test + public void testTokensInRangeMurmur3Partitioner() + { + testTokensInRange(new Murmur3Partitioner()); + } + + private static void testTokensInRange(IPartitioner partitioner) + { + Splitter splitter = getSplitter(partitioner); + + // test full range + Range<Token> fullRange = new Range<>(partitioner.getMinimumToken(), partitioner.getMaximumToken()); + BigInteger fullRangeSize = splitter.valueForToken(partitioner.getMaximumToken()).subtract(splitter.valueForToken(partitioner.getMinimumToken())); + assertEquals(fullRangeSize, splitter.tokensInRange(fullRange)); + fullRange = new Range<>(splitter.tokenForValue(BigInteger.valueOf(-10)), splitter.tokenForValue(BigInteger.valueOf(-10))); + assertEquals(fullRangeSize, splitter.tokensInRange(fullRange)); + + // test small range + Range<Token> smallRange = new Range<>(splitter.tokenForValue(BigInteger.valueOf(-5)), splitter.tokenForValue(BigInteger.valueOf(5))); + assertEquals(BigInteger.valueOf(10), splitter.tokensInRange(smallRange)); + + // test wrap-around range + Range<Token> wrapAround = new Range<>(splitter.tokenForValue(BigInteger.valueOf(5)), splitter.tokenForValue(BigInteger.valueOf(-5))); + assertEquals(fullRangeSize.subtract(BigInteger.TEN), splitter.tokensInRange(wrapAround)); + } + + @Test + public void testElapsedTokensRandomPartitioner() + { + testElapsedMultiRange(new RandomPartitioner()); + } + + @Test + public void testElapsedTokensMurmur3Partitioner() + { + testElapsedMultiRange(new Murmur3Partitioner()); + } + + private static void testElapsedMultiRange(IPartitioner partitioner) + { + Splitter splitter = getSplitter(partitioner); + // small range + Range<Token> smallRange = new Range<>(splitter.tokenForValue(BigInteger.valueOf(-1)), splitter.tokenForValue(BigInteger.valueOf(1))); + testElapsedTokens(partitioner, smallRange, true); + + // medium range + Range<Token> mediumRange = new Range<>(splitter.tokenForValue(BigInteger.valueOf(0)), splitter.tokenForValue(BigInteger.valueOf(123456789))); + testElapsedTokens(partitioner, mediumRange, true); + + // wrapped range + BigInteger min = splitter.valueForToken(partitioner.getMinimumToken()); + BigInteger max = splitter.valueForToken(partitioner.getMaximumToken()); + Range<Token> wrappedRange = new Range<>(splitter.tokenForValue(max.subtract(BigInteger.valueOf(1350))), + splitter.tokenForValue(min.add(BigInteger.valueOf(20394)))); + testElapsedTokens(partitioner, wrappedRange, true); + + // full range + Range<Token> fullRange = new Range<>(partitioner.getMinimumToken(), partitioner.getMaximumToken()); + testElapsedTokens(partitioner, fullRange, false); + } + + private static void testElapsedTokens(IPartitioner partitioner, Range<Token> range, boolean partialRange) + { + Splitter splitter = getSplitter(partitioner); + + BigInteger left = splitter.valueForToken(range.left); + BigInteger right = splitter.valueForToken(range.right); + BigInteger tokensInRange = splitter.tokensInRange(range); + + // elapsedTokens(left, (left, right]) = 0 + assertEquals(BigInteger.ZERO, splitter.elapsedTokens(splitter.tokenForValue(left), range)); + + // elapsedTokens(right, (left, right]) = tokensInRange((left, right]) + assertEquals(tokensInRange, splitter.elapsedTokens(splitter.tokenForValue(right), range)); + + // elapsedTokens(left+1, (left, right]) = 1 + assertEquals(BigInteger.ONE, splitter.elapsedTokens(splitter.tokenForValue(left.add(BigInteger.ONE)), range)); + + // elapsedTokens(right-1, (left, right]) = tokensInRange((left, right]) - 1 + assertEquals(tokensInRange.subtract(BigInteger.ONE), splitter.elapsedTokens(splitter.tokenForValue(right.subtract(BigInteger.ONE)), range)); + + // elapsedTokens(midpoint, (left, right]) + tokensInRange((midpoint, right]) = tokensInRange + Token midpoint = partitioner.midpoint(range.left, range.right); + assertEquals(tokensInRange, splitter.elapsedTokens(midpoint, range).add(splitter.tokensInRange(new Range<>(midpoint, range.right)))); + + if (partialRange) + { + // elapsedTokens(right + 1, (left, right]) = 0 + assertEquals(BigInteger.ZERO, splitter.elapsedTokens(splitter.tokenForValue(right.add(BigInteger.ONE)), range)); + } + } + + @Test + public void testPositionInRangeRandomPartitioner() + { + testPositionInRangeMultiRange(new RandomPartitioner()); + } + + @Test + public void testPositionInRangeMurmur3Partitioner() + { + testPositionInRangeMultiRange(new Murmur3Partitioner()); + } + + private static void testPositionInRangeMultiRange(IPartitioner partitioner) + { + Splitter splitter = getSplitter(partitioner); + + // Test tiny range + Token start = splitter.tokenForValue(BigInteger.ZERO); + Token end = splitter.tokenForValue(BigInteger.valueOf(3)); + Range<Token> range = new Range<>(start, end); + assertEquals(0.0, splitter.positionInRange(start, range), 0.01); + assertEquals(0.33, splitter.positionInRange(splitter.tokenForValue(BigInteger.valueOf(1)), range), 0.01); + assertEquals(0.66, splitter.positionInRange(splitter.tokenForValue(BigInteger.valueOf(2)), range), 0.01); + assertEquals(1.0, splitter.positionInRange(end, range), 0.01); + // Token not in range should return -1.0 for position + Token notInRange = splitter.tokenForValue(BigInteger.valueOf(10)); + assertEquals(-1.0, splitter.positionInRange(notInRange, range), 0.0); + + + // Test medium range + start = splitter.tokenForValue(BigInteger.ZERO); + end = splitter.tokenForValue(BigInteger.valueOf(1000)); + range = new Range<>(start, end); + testPositionInRange(partitioner, splitter, range); + + // Test wrap-around range + start = splitter.tokenForValue(splitter.valueForToken(partitioner.getMaximumToken()).subtract(BigInteger.valueOf(123456789))); + end = splitter.tokenForValue(splitter.valueForToken(partitioner.getMinimumToken()).add(BigInteger.valueOf(123456789))); + range = new Range<>(start, end); + testPositionInRange(partitioner, splitter, range); + + // Test full range + testPositionInRange(partitioner, splitter, new Range<>(partitioner.getMinimumToken(), partitioner.getMaximumToken())); + testPositionInRange(partitioner, splitter, new Range<>(partitioner.getMinimumToken(), partitioner.getMinimumToken())); + testPositionInRange(partitioner, splitter, new Range<>(partitioner.getMaximumToken(), partitioner.getMaximumToken())); + testPositionInRange(partitioner, splitter, new Range<>(splitter.tokenForValue(BigInteger.ONE), splitter.tokenForValue(BigInteger.ONE))); + } + + private static void testPositionInRange(IPartitioner partitioner, Splitter splitter, Range<Token> range) + { + Range<Token> actualRange = range; + //full range case + if (range.left.equals(range.right)) + { + actualRange = new Range<>(partitioner.getMinimumToken(), partitioner.getMaximumToken()); + } + assertEquals(0.0, splitter.positionInRange(actualRange.left, range), 0.01); + assertEquals(0.25, splitter.positionInRange(getTokenInPosition(partitioner, actualRange, 0.25), range), 0.01); + assertEquals(0.37, splitter.positionInRange(getTokenInPosition(partitioner, actualRange, 0.373), range), 0.01); + assertEquals(0.5, splitter.positionInRange(getTokenInPosition(partitioner, actualRange, 0.5), range), 0.01); + assertEquals(0.75, splitter.positionInRange(getTokenInPosition(partitioner, actualRange, 0.75), range), 0.01); + assertEquals(0.99, splitter.positionInRange(getTokenInPosition(partitioner, actualRange, 0.999), range), 0.01); + assertEquals(1.0, splitter.positionInRange(actualRange.right, range), 0.01); + } + + private static Token getTokenInPosition(IPartitioner partitioner, Range<Token> range, double position) + { + if (range.left.equals(range.right)) + { + range = new Range<>(partitioner.getMinimumToken(), partitioner.getMaximumToken()); + } + Splitter splitter = getSplitter(partitioner); + BigInteger totalTokens = splitter.tokensInRange(range); + BigInteger elapsedTokens = BigDecimal.valueOf(position).multiply(new BigDecimal(totalTokens)).toBigInteger(); + BigInteger tokenInPosition = splitter.valueForToken(range.left).add(elapsedTokens); + return getWrappedToken(partitioner, tokenInPosition); + } + + private static Token getWrappedToken(IPartitioner partitioner, BigInteger position) + { + Splitter splitter = getSplitter(partitioner); + BigInteger maxTokenValue = splitter.valueForToken(partitioner.getMaximumToken()); + BigInteger minTokenValue = splitter.valueForToken(partitioner.getMinimumToken()); + if (position.compareTo(maxTokenValue) > 0) + { + position = minTokenValue.add(position.subtract(maxTokenValue)); + } + return splitter.tokenForValue(position); + } + + private static Splitter getSplitter(IPartitioner partitioner) + { + return partitioner.splitter().orElseThrow(() -> new AssertionError(partitioner.getClass() + " must have a splitter")); + } } --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
