You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by xe...@apache.org on 2012/08/23 18:19:11 UTC
git commit: Murmur3Partitioner improvements patch by Pavel Yaskevich;
reviewed by Jonathan Ellis for CASSANDRA-3772
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);