Updated Branches: refs/heads/trunk 3925aba84 -> a89ef1ffd
Murmur3Partitioner improvements patch by Pavel Yaskevich; reviewed by Jonathan Ellis for CASSANDRA-3772 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/a89ef1ff Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/a89ef1ff Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/a89ef1ff Branch: refs/heads/trunk Commit: a89ef1ffd4cd2ee39a2751f37044dba3015d72f1 Parents: 3925aba Author: Pavel Yaskevich <xe...@apache.org> Authored: Thu Aug 23 01:45:19 2012 +0300 Committer: Pavel Yaskevich <xe...@apache.org> Committed: Thu Aug 23 19:18:33 2012 +0300 ---------------------------------------------------------------------- NEWS.txt | 3 + .../cassandra/dht/AbstractHashedPartitioner.java | 194 --------------- src/java/org/apache/cassandra/dht/LongToken.java | 33 +++ .../apache/cassandra/dht/Murmur3Partitioner.java | 158 +++++++++++-- .../apache/cassandra/dht/RandomPartitioner.java | 160 ++++++++++++- .../cassandra/dht/Murmur3PartitionerTest.java | 41 +++ .../apache/cassandra/dht/PartitionerTestCase.java | 5 + 7 files changed, 378 insertions(+), 216 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/NEWS.txt ---------------------------------------------------------------------- diff --git a/NEWS.txt b/NEWS.txt index fe0b93d..199dd8a 100644 --- a/NEWS.txt +++ b/NEWS.txt @@ -38,6 +38,9 @@ Upgrading - The default bloom filter fp chance has been increased to 1%. This will save about 30% of the memory used by the old default. Existing columnfamilies will retain their old setting. + - The default partitioner was changed from RandomPartitioner to + Murmur3Partitioner which provides faster hashing as well as + improved performance with secondary indexes. Features -------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/src/java/org/apache/cassandra/dht/AbstractHashedPartitioner.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/dht/AbstractHashedPartitioner.java b/src/java/org/apache/cassandra/dht/AbstractHashedPartitioner.java deleted file mode 100644 index 55dfb97..0000000 --- a/src/java/org/apache/cassandra/dht/AbstractHashedPartitioner.java +++ /dev/null @@ -1,194 +0,0 @@ -/** - * 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.dht; - -import java.math.BigDecimal; -import java.math.BigInteger; -import java.nio.ByteBuffer; -import java.nio.charset.CharacterCodingException; -import java.util.*; - -import org.apache.cassandra.config.ConfigurationException; -import org.apache.cassandra.db.DecoratedKey; -import org.apache.cassandra.utils.ByteBufferUtil; -import org.apache.cassandra.utils.FBUtilities; -import org.apache.cassandra.utils.GuidGenerator; -import org.apache.cassandra.utils.Pair; - -/** - * This class is the super class of classes that generate a BigIntegerToken using hash function. - */ -public abstract class AbstractHashedPartitioner extends AbstractPartitioner<BigIntegerToken> -{ - public static final BigInteger ZERO = new BigInteger("0"); - public static final BigIntegerToken MINIMUM = new BigIntegerToken("-1"); - public static final BigInteger MAXIMUM = new BigInteger("2").pow(127); - - private static final byte DELIMITER_BYTE = ":".getBytes()[0]; - - /** - * returns a hash of the byte buffer in the range of 0 - 2**127 as a BigInteger - * - * @param buffer the buffer to hash - * @return the BigInteger hash value - */ - protected abstract BigInteger hash(ByteBuffer buffer); - - public DecoratedKey decorateKey(ByteBuffer key) - { - return new DecoratedKey(getToken(key), key); - } - - public DecoratedKey convertFromDiskFormat(ByteBuffer fromdisk) - { - // find the delimiter position - int splitPoint = -1; - for (int i = fromdisk.position(); i < fromdisk.limit(); i++) - { - if (fromdisk.get(i) == DELIMITER_BYTE) - { - splitPoint = i; - break; - } - } - assert splitPoint != -1; - - // and decode the token and key - String token = null; - try - { - token = ByteBufferUtil.string(fromdisk, fromdisk.position(), splitPoint - fromdisk.position()); - } - catch (CharacterCodingException e) - { - throw new RuntimeException(e); - } - ByteBuffer key = fromdisk.duplicate(); - key.position(splitPoint + 1); - return new DecoratedKey(new BigIntegerToken(token), key); - } - - public Token midpoint(Token ltoken, Token rtoken) - { - // the symbolic MINIMUM token should act as ZERO: the empty bit array - BigInteger left = ltoken.equals(MINIMUM) ? ZERO : ((BigIntegerToken)ltoken).token; - BigInteger right = rtoken.equals(MINIMUM) ? ZERO : ((BigIntegerToken)rtoken).token; - Pair<BigInteger,Boolean> midpair = FBUtilities.midpoint(left, right, 127); - // discard the remainder - return new BigIntegerToken(midpair.left); - } - - public BigIntegerToken getMinimumToken() - { - return MINIMUM; - } - - public BigIntegerToken getRandomToken() - { - BigInteger token = hash(GuidGenerator.guidAsBytes()); - if ( token.signum() == -1 ) - token = token.multiply(BigInteger.valueOf(-1L)); - return new BigIntegerToken(token); - } - - private final Token.TokenFactory<BigInteger> tokenFactory = new Token.TokenFactory<BigInteger>() { - public ByteBuffer toByteArray(Token<BigInteger> bigIntegerToken) - { - return ByteBuffer.wrap(bigIntegerToken.token.toByteArray()); - } - - public Token<BigInteger> fromByteArray(ByteBuffer bytes) - { - return new BigIntegerToken(new BigInteger(ByteBufferUtil.getArray(bytes))); - } - - public String toString(Token<BigInteger> bigIntegerToken) - { - return bigIntegerToken.token.toString(); - } - - public void validate(String token) throws ConfigurationException - { - try - { - BigInteger i = new BigInteger(token); - if (i.compareTo(ZERO) < 0) - throw new ConfigurationException("Token must be >= 0"); - if (i.compareTo(MAXIMUM) > 0) - throw new ConfigurationException("Token must be <= 2**127"); - } - catch (NumberFormatException e) - { - throw new ConfigurationException(e.getMessage()); - } - } - - public Token<BigInteger> fromString(String string) - { - return new BigIntegerToken(new BigInteger(string)); - } - }; - - public Token.TokenFactory<BigInteger> getTokenFactory() - { - return tokenFactory; - } - - public boolean preservesOrder() - { - return false; - } - - public BigIntegerToken getToken(ByteBuffer key) - { - if (key.remaining() == 0) - return MINIMUM; - return new BigIntegerToken(hash(key)); - } - - public Map<Token, Float> describeOwnership(List<Token> sortedTokens) - { - Map<Token, Float> ownerships = new HashMap<Token, Float>(); - Iterator i = sortedTokens.iterator(); - - // 0-case - if (!i.hasNext()) { throw new RuntimeException("No nodes present in the cluster. How did you call this?"); } - // 1-case - if (sortedTokens.size() == 1) { - ownerships.put((Token)i.next(), new Float(1.0)); - } - // n-case - else { - // NOTE: All divisions must take place in BigDecimals, and all modulo operators must take place in BigIntegers. - final BigInteger ri = MAXIMUM; // (used for addition later) - final BigDecimal r = new BigDecimal(ri); // The entire range, 2**127 - Token start = (Token)i.next(); BigInteger ti = ((BigIntegerToken)start).token; // The first token and its value - Token t; BigInteger tim1 = ti; // The last token and its value (after loop) - while (i.hasNext()) { - t = (Token)i.next(); ti = ((BigIntegerToken)t).token; // The next token and its value - float x = new BigDecimal(ti.subtract(tim1).add(ri).mod(ri)).divide(r).floatValue(); // %age = ((T(i) - T(i-1) + R) % R) / R - ownerships.put(t, x); // save (T(i) -> %age) - tim1 = ti; // -> advance loop - } - // The start token's range extends backward to the last token, which is why both were saved above. - float x = new BigDecimal(((BigIntegerToken)start).token.subtract(ti).add(ri).mod(ri)).divide(r).floatValue(); - ownerships.put(start, x); - } - return ownerships; - } -} http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/src/java/org/apache/cassandra/dht/LongToken.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/dht/LongToken.java b/src/java/org/apache/cassandra/dht/LongToken.java new file mode 100644 index 0000000..56799b6 --- /dev/null +++ b/src/java/org/apache/cassandra/dht/LongToken.java @@ -0,0 +1,33 @@ +/** + * 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.dht; + +public class LongToken extends Token<Long> +{ + static final long serialVersionUID = -5833580143318243006L; + + public LongToken(Long token) + { + super(token); + } + + public int compareTo(Token<Long> o) + { + return token.compareTo(o.token); + } +} http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java b/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java index 775cef9..fb8d721 100644 --- a/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java +++ b/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java @@ -19,35 +19,157 @@ package org.apache.cassandra.dht; import java.math.BigInteger; import java.nio.ByteBuffer; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import org.apache.cassandra.config.ConfigurationException; +import org.apache.cassandra.db.DecoratedKey; +import org.apache.cassandra.utils.ByteBufferUtil; +import org.apache.cassandra.utils.FBUtilities; import org.apache.cassandra.utils.MurmurHash; /** * This class generates a BigIntegerToken using a Murmur3 hash. */ -public class Murmur3Partitioner extends AbstractHashedPartitioner +public class Murmur3Partitioner extends AbstractPartitioner<LongToken> { - protected BigInteger hash(ByteBuffer buffer) + public static final LongToken MINIMUM = new LongToken(0L); + public static final long MAXIMUM = Long.MAX_VALUE; + + public DecoratedKey convertFromDiskFormat(ByteBuffer key) + { + throw new UnsupportedOperationException(); + } + + public DecoratedKey decorateKey(ByteBuffer key) + { + return new DecoratedKey(getToken(key), key); + } + + public Token midpoint(Token lToken, Token rToken) + { + // using BigInteger to avoid long overflow in intermediate operations + BigInteger l = BigInteger.valueOf(((LongToken) lToken).token), + r = BigInteger.valueOf(((LongToken) rToken).token), + midpoint; + + if (l.compareTo(r) < 0) + { + BigInteger sum = l.add(r); + midpoint = sum.shiftRight(1); + } + else // wrapping case + { + BigInteger max = BigInteger.valueOf(MAXIMUM); + midpoint = max.add(r).subtract(l).shiftRight(1).add(l).mod(max); + } + + return new LongToken(midpoint.longValue()); + } + + public LongToken getMinimumToken() + { + return MINIMUM; + } + + public LongToken getToken(ByteBuffer key) + { + if (key.remaining() == 0) + return MINIMUM; + + long hash = MurmurHash.hash3_x64_128(key, key.position(), key.remaining(), 0)[0]; + return new LongToken((hash < 0) ? -hash : hash); + } + + public LongToken getRandomToken() { - long[] bufferHash = MurmurHash.hash3_x64_128(buffer, buffer.position(), buffer.remaining(), 0); - byte[] hashBytes = new byte[16]; + return new LongToken(FBUtilities.threadLocalRandom().nextLong()); + } + + public boolean preservesOrder() + { + return false; + } + + public Map<Token, Float> describeOwnership(List<Token> sortedTokens) + { + Map<Token, Float> ownerships = new HashMap<Token, Float>(); + Iterator i = sortedTokens.iterator(); + + // 0-case + if (!i.hasNext()) + throw new RuntimeException("No nodes present in the cluster. How did you call this?"); + // 1-case + if (sortedTokens.size() == 1) + ownerships.put((Token) i.next(), new Float(1.0)); + // n-case + else + { + final float ri = MAXIMUM; // (used for addition later) + Token start = (Token) i.next(); Long ti = ((LongToken)start).token; // The first token and its value + Token t; Long tim1 = ti; // The last token and its value (after loop) + + while (i.hasNext()) + { + t = (Token) i.next(); ti = ((LongToken) t).token; // The next token and its value + float age = ((ti - tim1 + ri) % ri) / ri; // %age = ((T(i) - T(i-1) + R) % R) / R + ownerships.put(t, age); // save (T(i) -> %age) + tim1 = ti; // -> advance loop + } - writeLong(bufferHash[0], hashBytes, 0); - writeLong(bufferHash[1], hashBytes, 8); - // make sure it's positive, this isn't the same as abs() but doesn't effect distribution - hashBytes[0] = (byte) (hashBytes[0] & 0x7F); - return new BigInteger(hashBytes); + // The start token's range extends backward to the last token, which is why both were saved above. + float x = ((((LongToken) start).token - ti + ri) % ri) / ri; + ownerships.put(start, x); + } + + return ownerships; } - public static void writeLong(long src, byte[] dest, int offset) + public Token.TokenFactory<Long> getTokenFactory() { - dest[offset] = (byte) (src >> 56); - dest[offset + 1] = (byte) (src >> 48); - dest[offset + 2] = (byte) (src >> 40); - dest[offset + 3] = (byte) (src >> 32); - dest[offset + 4] = (byte) (src >> 24); - dest[offset + 5] = (byte) (src >> 16); - dest[offset + 6] = (byte) (src >> 8); - dest[offset + 7] = (byte) (src); + return tokenFactory; } + + private final Token.TokenFactory<Long> tokenFactory = new Token.TokenFactory<Long>() + { + public ByteBuffer toByteArray(Token<Long> longToken) + { + return ByteBufferUtil.bytes(longToken.token); + } + + public Token<Long> fromByteArray(ByteBuffer bytes) + { + return new LongToken(bytes.getLong()); + } + + public String toString(Token<Long> longToken) + { + return longToken.token.toString(); + } + + public void validate(String token) throws ConfigurationException + { + try + { + Long i = Long.valueOf(token); + + if (i.compareTo(MINIMUM.token) < 0) + throw new ConfigurationException("Token must be >= 0"); + + if (i.compareTo(MAXIMUM) > 0) + throw new ConfigurationException("Token must be <= " + Long.MAX_VALUE); + } + catch (NumberFormatException e) + { + throw new ConfigurationException(e.getMessage()); + } + } + + public Token<Long> fromString(String string) + { + return new LongToken(Long.valueOf(string)); + } + }; } http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/src/java/org/apache/cassandra/dht/RandomPartitioner.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/dht/RandomPartitioner.java b/src/java/org/apache/cassandra/dht/RandomPartitioner.java index 5b95454..cf3855b 100644 --- a/src/java/org/apache/cassandra/dht/RandomPartitioner.java +++ b/src/java/org/apache/cassandra/dht/RandomPartitioner.java @@ -17,18 +17,170 @@ */ package org.apache.cassandra.dht; +import java.math.BigDecimal; import java.math.BigInteger; import java.nio.ByteBuffer; +import java.nio.charset.CharacterCodingException; +import java.util.*; +import org.apache.cassandra.config.ConfigurationException; +import org.apache.cassandra.db.DecoratedKey; +import org.apache.cassandra.utils.ByteBufferUtil; import org.apache.cassandra.utils.FBUtilities; +import org.apache.cassandra.utils.GuidGenerator; +import org.apache.cassandra.utils.Pair; /** - * This class generates a BigIntegerToken using a MD5 hash. + * This class generates a BigIntegerToken using MD5 hash. */ -public class RandomPartitioner extends AbstractHashedPartitioner +public class RandomPartitioner extends AbstractPartitioner<BigIntegerToken> { - protected BigInteger hash(ByteBuffer buffer) + public static final BigInteger ZERO = new BigInteger("0"); + public static final BigIntegerToken MINIMUM = new BigIntegerToken("-1"); + public static final BigInteger MAXIMUM = new BigInteger("2").pow(127); + + private static final byte DELIMITER_BYTE = ":".getBytes()[0]; + + public DecoratedKey decorateKey(ByteBuffer key) + { + return new DecoratedKey(getToken(key), key); + } + + public DecoratedKey convertFromDiskFormat(ByteBuffer fromdisk) + { + // find the delimiter position + int splitPoint = -1; + for (int i = fromdisk.position(); i < fromdisk.limit(); i++) + { + if (fromdisk.get(i) == DELIMITER_BYTE) + { + splitPoint = i; + break; + } + } + assert splitPoint != -1; + + // and decode the token and key + String token = null; + try + { + token = ByteBufferUtil.string(fromdisk, fromdisk.position(), splitPoint - fromdisk.position()); + } + catch (CharacterCodingException e) + { + throw new RuntimeException(e); + } + ByteBuffer key = fromdisk.duplicate(); + key.position(splitPoint + 1); + return new DecoratedKey(new BigIntegerToken(token), key); + } + + public Token midpoint(Token ltoken, Token rtoken) { - return FBUtilities.hashToBigInteger(buffer); + // the symbolic MINIMUM token should act as ZERO: the empty bit array + BigInteger left = ltoken.equals(MINIMUM) ? ZERO : ((BigIntegerToken)ltoken).token; + BigInteger right = rtoken.equals(MINIMUM) ? ZERO : ((BigIntegerToken)rtoken).token; + Pair<BigInteger,Boolean> midpair = FBUtilities.midpoint(left, right, 127); + // discard the remainder + return new BigIntegerToken(midpair.left); + } + + public BigIntegerToken getMinimumToken() + { + return MINIMUM; + } + + public BigIntegerToken getRandomToken() + { + BigInteger token = FBUtilities.hashToBigInteger(GuidGenerator.guidAsBytes()); + if ( token.signum() == -1 ) + token = token.multiply(BigInteger.valueOf(-1L)); + return new BigIntegerToken(token); + } + + private final Token.TokenFactory<BigInteger> tokenFactory = new Token.TokenFactory<BigInteger>() { + public ByteBuffer toByteArray(Token<BigInteger> bigIntegerToken) + { + return ByteBuffer.wrap(bigIntegerToken.token.toByteArray()); + } + + public Token<BigInteger> fromByteArray(ByteBuffer bytes) + { + return new BigIntegerToken(new BigInteger(ByteBufferUtil.getArray(bytes))); + } + + public String toString(Token<BigInteger> bigIntegerToken) + { + return bigIntegerToken.token.toString(); + } + + public void validate(String token) throws ConfigurationException + { + try + { + BigInteger i = new BigInteger(token); + if (i.compareTo(ZERO) < 0) + throw new ConfigurationException("Token must be >= 0"); + if (i.compareTo(MAXIMUM) > 0) + throw new ConfigurationException("Token must be <= 2**127"); + } + catch (NumberFormatException e) + { + throw new ConfigurationException(e.getMessage()); + } + } + + public Token<BigInteger> fromString(String string) + { + return new BigIntegerToken(new BigInteger(string)); + } + }; + + public Token.TokenFactory<BigInteger> getTokenFactory() + { + return tokenFactory; + } + + public boolean preservesOrder() + { + return false; + } + + public BigIntegerToken getToken(ByteBuffer key) + { + if (key.remaining() == 0) + return MINIMUM; + return new BigIntegerToken(FBUtilities.hashToBigInteger(key)); + } + + public Map<Token, Float> describeOwnership(List<Token> sortedTokens) + { + Map<Token, Float> ownerships = new HashMap<Token, Float>(); + Iterator i = sortedTokens.iterator(); + + // 0-case + if (!i.hasNext()) { throw new RuntimeException("No nodes present in the cluster. How did you call this?"); } + // 1-case + if (sortedTokens.size() == 1) { + ownerships.put((Token)i.next(), new Float(1.0)); + } + // n-case + else { + // NOTE: All divisions must take place in BigDecimals, and all modulo operators must take place in BigIntegers. + final BigInteger ri = MAXIMUM; // (used for addition later) + final BigDecimal r = new BigDecimal(ri); // The entire range, 2**127 + Token start = (Token)i.next(); BigInteger ti = ((BigIntegerToken)start).token; // The first token and its value + Token t; BigInteger tim1 = ti; // The last token and its value (after loop) + while (i.hasNext()) { + t = (Token)i.next(); ti = ((BigIntegerToken)t).token; // The next token and its value + float x = new BigDecimal(ti.subtract(tim1).add(ri).mod(ri)).divide(r).floatValue(); // %age = ((T(i) - T(i-1) + R) % R) / R + ownerships.put(t, x); // save (T(i) -> %age) + tim1 = ti; // -> advance loop + } + // The start token's range extends backward to the last token, which is why both were saved above. + float x = new BigDecimal(((BigIntegerToken)start).token.subtract(ti).add(ri).mod(ri)).divide(r).floatValue(); + ownerships.put(start, x); + } + return ownerships; } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/test/unit/org/apache/cassandra/dht/Murmur3PartitionerTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/dht/Murmur3PartitionerTest.java b/test/unit/org/apache/cassandra/dht/Murmur3PartitionerTest.java new file mode 100644 index 0000000..7db91c1 --- /dev/null +++ b/test/unit/org/apache/cassandra/dht/Murmur3PartitionerTest.java @@ -0,0 +1,41 @@ +/* + * + * 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.dht; + +public class Murmur3PartitionerTest extends PartitionerTestCase<LongToken> +{ + public void initPartitioner() + { + partitioner = new Murmur3Partitioner(); + } + + @Override + protected void midpointMinimumTestCase() + { + LongToken mintoken = partitioner.getMinimumToken(); + assert mintoken.compareTo(partitioner.midpoint(mintoken, mintoken)) != 0; + assertMidpoint(mintoken, tok("a"), 16); + assertMidpoint(mintoken, tok("aaa"), 16); + assertMidpoint(mintoken, mintoken, 62); + assertMidpoint(tok("a"), mintoken, 16); + } +} + http://git-wip-us.apache.org/repos/asf/cassandra/blob/a89ef1ff/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java b/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java index 623b26c..720ba3e 100644 --- a/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java +++ b/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java @@ -82,6 +82,11 @@ public abstract class PartitionerTestCase<T extends Token> @Test public void testMidpointMinimum() { + midpointMinimumTestCase(); + } + + protected void midpointMinimumTestCase() + { T mintoken = partitioner.getMinimumToken(); assert mintoken.compareTo(partitioner.midpoint(mintoken, mintoken)) != 0; assertMidpoint(mintoken, tok("a"), 16);