Fix M3P ownership calculation; patch by yukim reviewed by Sylvain Lebresne for CASSANDRA-5076
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/e7ae7c90 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/e7ae7c90 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/e7ae7c90 Branch: refs/heads/cassandra-1.2.0 Commit: e7ae7c9040135b6ecae5204efd7e41ad2e6ba4ee Parents: 620a4b7 Author: Yuki Morishita <yu...@apache.org> Authored: Wed Dec 19 12:43:23 2012 -0600 Committer: Yuki Morishita <yu...@apache.org> Committed: Wed Dec 19 12:43:23 2012 -0600 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../apache/cassandra/dht/Murmur3Partitioner.java | 14 +++-- .../apache/cassandra/dht/PartitionerTestCase.java | 40 ++++++++++++++- 3 files changed, 48 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/e7ae7c90/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 6edf7bb..7786b09 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -11,6 +11,7 @@ Merged from 1.1: * Fix ALTER TABLE overriding compression options with defaults (CASSANDRA-4996, 5066) * fix specifying and altering crc_check_chance (CASSANDRA-5053) + * fix Murmur3Partitioner ownership% calculation (CASSANDRA-5076) 1.2-rc1 http://git-wip-us.apache.org/repos/asf/cassandra/blob/e7ae7c90/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 3e98e32..ad3579a 100644 --- a/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java +++ b/src/java/org/apache/cassandra/dht/Murmur3Partitioner.java @@ -17,6 +17,7 @@ */ package org.apache.cassandra.dht; +import java.math.BigDecimal; import java.math.BigInteger; import java.nio.ByteBuffer; import java.util.HashMap; @@ -125,20 +126,21 @@ public class Murmur3Partitioner extends AbstractPartitioner<LongToken> // 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) + final BigInteger ri = BigInteger.valueOf(MAXIMUM).subtract(BigInteger.valueOf(MINIMUM.token + 1)); // (used for addition later) + final BigDecimal r = new BigDecimal(ri); + Token start = (Token) i.next();BigInteger ti = BigInteger.valueOf(((LongToken)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 = ((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 + t = (Token) i.next(); ti = BigInteger.valueOf(((LongToken) t).token); // The next token and its value + float age = new BigDecimal(ti.subtract(tim1).add(ri).mod(ri)).divide(r, 6, BigDecimal.ROUND_HALF_EVEN).floatValue(); // %age = ((T(i) - T(i-1) + R) % R) / R ownerships.put(t, age); // 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 = ((((LongToken) start).token - ti + ri) % ri) / ri; + float x = new BigDecimal(BigInteger.valueOf(((LongToken)start).token).subtract(ti).add(ri).mod(ri)).divide(r, 6, BigDecimal.ROUND_HALF_EVEN).floatValue(); ownerships.put(start, x); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/e7ae7c90/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 720ba3e..79b0d78 100644 --- a/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java +++ b/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java @@ -19,11 +19,14 @@ package org.apache.cassandra.dht; import java.nio.ByteBuffer; -import java.util.Random; +import java.util.*; import org.junit.Before; import org.junit.Test; +import static junit.framework.Assert.assertEquals; +import static junit.framework.Assert.fail; + public abstract class PartitionerTestCase<T extends Token> { protected IPartitioner<T> partitioner; @@ -115,4 +118,39 @@ public abstract class PartitionerTestCase<T extends Token> Token.TokenFactory factory = partitioner.getTokenFactory(); assert tok("a").compareTo(factory.fromString(factory.toString(tok("a")))) == 0; } + + @Test + public void testDescribeOwnership() + { + try + { + testDescribeOwnershipWith(0); + fail(); + } + catch (RuntimeException e) + { + // success + } + testDescribeOwnershipWith(1); + testDescribeOwnershipWith(2); + testDescribeOwnershipWith(256); + } + + private void testDescribeOwnershipWith(int numTokens) + { + List<Token> tokens = new ArrayList<Token>(); + while (tokens.size() < numTokens) + { + Token randomToken = partitioner.getRandomToken(); + if (!tokens.contains(randomToken)) + tokens.add(randomToken); + } + Collections.sort(tokens); + Map<Token, Float> owns = partitioner.describeOwnership(tokens); + + float totalOwnership = 0; + for (float ownership : owns.values()) + totalOwnership += ownership; + assertEquals(1.0, totalOwnership, 0.001); + } }