cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From xe...@apache.org
Subject git commit: Murmur3Partitioner improvements patch by Pavel Yaskevich; reviewed by Jonathan Ellis for CASSANDRA-3772
Date Thu, 23 Aug 2012 16:19:11 GMT
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 <xedin@apache.org>
Authored: Thu Aug 23 01:45:19 2012 +0300
Committer: Pavel Yaskevich <xedin@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);


Mime
View raw message