You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2009/08/27 00:20:23 UTC
svn commit: r808206 - in /incubator/cassandra/trunk:
src/java/org/apache/cassandra/dht/ test/conf/
test/unit/org/apache/cassandra/dht/
Author: jbellis
Date: Wed Aug 26 22:20:23 2009
New Revision: 808206
URL: http://svn.apache.org/viewvc?rev=808206&view=rev
Log:
add midpoint method to IPartitioner. patch by Stu Hood; reviewed by jbellis for CASSANDRA-242
Modified:
incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java
incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java
incubator/cassandra/trunk/test/conf/storage-conf.xml
incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/CollatingOrderPreservingPartitioner.java Wed Aug 26 22:20:23 2009
@@ -71,6 +71,84 @@
return reverseComparator;
}
+ /**
+ * @return A new byte array that will compare (via compareByteArrays)
+ * approximately halfway between the parameters.
+ */
+ private static byte[] midpoint(byte[] lbytes, byte[] rbytes)
+ {
+ // pad the arrays to equal length, for convenience
+ int inlength;
+ int comparison = FBUtilities.compareByteArrays(lbytes, rbytes);
+ if (comparison < 0)
+ {
+ inlength = Math.max(lbytes.length, rbytes.length);
+ if (lbytes.length < inlength)
+ lbytes = Arrays.copyOf(lbytes, inlength);
+ else if (rbytes.length < inlength)
+ rbytes = Arrays.copyOf(rbytes, inlength);
+ }
+ else
+ {
+ // wrapping range must involve the minimum token
+ assert FBUtilities.isEqualBits(MINIMUM.token, rbytes);
+
+ inlength = Math.max(lbytes.length, 1);
+ if (lbytes.length < inlength)
+ lbytes = Arrays.copyOf(lbytes, inlength);
+ rbytes = new byte[inlength];
+ Arrays.fill(rbytes, (byte)0xFF);
+ }
+
+ // if the lsbits of the two inputs are not equal we have to extend
+ // the result array to make room for a carried bit during the right shift
+ int outlength = (((int)lbytes[inlength-1] & 0x01) == ((int)rbytes[inlength-1] & 0x01))
+ ? inlength
+ : inlength+1;
+ byte[] result = new byte[outlength];
+ boolean carrying = false;
+
+ // perform the addition
+ for (int i = inlength-1; i >= 0; i--)
+ {
+ // initialize the lsbit if we're carrying
+ int sum = carrying ? 1 : 0;
+
+ // remove the sign bit, and sum left and right
+ sum += (lbytes[i] & 0xFF) + (rbytes[i] & 0xFF);
+
+ // see if we'll need to carry
+ carrying = sum > 0xFF;
+
+ // set to the sum (truncating the msbit)
+ result[i] = (byte)sum;
+ }
+ // the carried bit from addition will be shifted in as the msbit
+
+ // perform the division (as a right shift)
+ for (int i = 0; i < inlength; i++)
+ {
+ // initialize the msbit if we're carrying
+ byte shifted = (byte)(carrying ? 0x80 : 0x00);
+
+ // check the lsbit to see if we'll need to continue carrying
+ carrying = (result[i] & 0x01) == 0x01;
+
+ // OR the right shifted value into the result byte
+ result[i] = (byte)(shifted | ((result[i] & 0xFF) >>> 1));
+ }
+
+ if (carrying)
+ // the last byte in the result array
+ result[inlength] |= 0x80;
+ return result;
+ }
+
+ public BytesToken midpoint(BytesToken ltoken, BytesToken rtoken)
+ {
+ return new BytesToken(midpoint(ltoken.token, rtoken.token));
+ }
+
public BytesToken getMinimumToken()
{
return MINIMUM;
Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/IPartitioner.java Wed Aug 26 22:20:23 2009
@@ -37,6 +37,18 @@
public Comparator<String> getReverseDecoratedKeyComparator();
+ /**
+ * Calculate a Token representing the approximate "middle" of the given
+ * range.
+ *
+ * The Tokens must have been generated by previous calls to midpoint,
+ * or be equal to this.getMinimumToken(). The range may not wrap unless it
+ * involves this.getMinimumToken().
+ *
+ * @return The approximate midpoint between left and right.
+ */
+ public T midpoint(T left, T right);
+
/**
* @return The minimum possible Token in the range that is being partitioned.
*/
Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/OrderPreservingPartitioner.java Wed Aug 26 22:20:23 2009
@@ -65,6 +65,104 @@
return reverseComparator;
}
+ /**
+ * Copies the given string into a char array, padding the end
+ * with empty chars up to length.
+ */
+ private static char[] getChars(String str, int length)
+ {
+ char[] chars;
+ if (str.length() < length)
+ {
+ chars = new char[length];
+ str.getChars(0, str.length(), chars, 0);
+ }
+ else if (str.length() == length)
+ {
+ chars = str.toCharArray();
+ }
+ else
+ throw new RuntimeException("Cannot truncate string of length " + str.length() + " to length " + length);
+ return chars;
+ }
+
+ /**
+ * @return A new String array that will compare
+ * approximately halfway between the parameters.
+ */
+ private static String midpoint(String left, String right)
+ {
+ int inlength;
+ char[] lchars;
+ char[] rchars;
+ int comparison = left.compareTo(right);
+ if (comparison < 0)
+ {
+ inlength = Math.max(left.length(), right.length());
+ lchars = getChars(left, inlength);
+ rchars = getChars(right, inlength);
+ }
+ else
+ {
+ // wrapping range must involve the minimum token
+ assert MINIMUM.token.equals(right);
+
+ inlength = Math.max(left.length(), 1);
+ lchars = getChars(left, inlength);
+ rchars = new char[inlength];
+ Arrays.fill(rchars, (char)0xFFFF);
+ }
+
+
+ // if the lsbits of the two inputs are not equal we have to extend
+ // the result array to make room for a carried bit during the right shift
+ int outlength = (((int)lchars[inlength-1] & 0x0001) == ((int)rchars[inlength-1] & 0x0001))
+ ? inlength
+ : inlength+1;
+ char[] result = new char[outlength];
+ boolean carrying = false;
+
+ // perform the addition
+ for (int i = inlength-1; i >= 0; i--)
+ {
+ // initialize the lsbit if we're carrying
+ int sum = carrying ? 0x0001 : 0x0000;
+
+ // remove the sign bit, and sum left and right
+ sum += (lchars[i] & 0xFFFF) + (rchars[i] & 0xFFFF);
+
+ // see if we'll need to carry
+ carrying = sum > 0xFFFF;
+
+ // set to the sum (truncating the msbit)
+ result[i] = (char)sum;
+ }
+ // the carried bit from addition will be shifted in as the msbit
+
+ // perform the division (as a right shift)
+ for (int i = 0; i < inlength; i++)
+ {
+ // initialize the msbit if we're carrying
+ char shifted = (char)(carrying ? 0x8000 : 0x0000);
+
+ // check the lsbit to see if we'll need to continue carrying
+ carrying = (result[i] & 0x0001) == 0x0001;
+
+ // OR the right shifted value into the result char
+ result[i] = (char)(shifted | ((result[i] & 0xFFFF) >>> 1));
+ }
+
+ if (carrying)
+ // the last char in the result array
+ result[inlength] |= 0x8000;
+ return new String(result);
+ }
+
+ public StringToken midpoint(StringToken ltoken, StringToken rtoken)
+ {
+ return new StringToken(midpoint(ltoken.token, rtoken.token));
+ }
+
public StringToken getMinimumToken()
{
return MINIMUM;
Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/RandomPartitioner.java Wed Aug 26 22:20:23 2009
@@ -31,6 +31,9 @@
*/
public class RandomPartitioner implements IPartitioner<BigIntegerToken>
{
+ public static final BigInteger TWO = new BigInteger("2");
+ public static final BigInteger MD5_MAX = TWO.pow(127);
+
public static final BigIntegerToken MINIMUM = new BigIntegerToken("0");
private static final Comparator<String> comparator = new Comparator<String>()
@@ -81,6 +84,26 @@
return rcomparator;
}
+ public BigIntegerToken midpoint(BigIntegerToken ltoken, BigIntegerToken rtoken)
+ {
+ BigInteger left = ltoken.token;
+ BigInteger right = rtoken.token;
+
+ BigInteger midpoint;
+ if (left.compareTo(right) < 0)
+ {
+ midpoint = left.add(right).divide(TWO);
+ }
+ else
+ {
+ // wrapping case
+ BigInteger distance = MD5_MAX.add(right).subtract(left);
+ BigInteger unchecked = distance.divide(TWO).add(left);
+ midpoint = (unchecked.compareTo(MD5_MAX) > 0) ? unchecked.subtract(MD5_MAX) : unchecked;
+ }
+ return new BigIntegerToken(midpoint);
+ }
+
public BigIntegerToken getMinimumToken()
{
return MINIMUM;
Modified: incubator/cassandra/trunk/test/conf/storage-conf.xml
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/conf/storage-conf.xml?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/conf/storage-conf.xml (original)
+++ incubator/cassandra/trunk/test/conf/storage-conf.xml Wed Aug 26 22:20:23 2009
@@ -22,7 +22,7 @@
<FlushIndexBufferSizeInMB>0.1</FlushIndexBufferSizeInMB>
<CommitLogSync>batch</CommitLogSync>
<CommitLogSyncBatchWindowInMS>1.0</CommitLogSyncBatchWindowInMS>
- <Partitioner>org.apache.cassandra.dht.OrderPreservingPartitioner</Partitioner>
+ <Partitioner>org.apache.cassandra.dht.CollatingOrderPreservingPartitioner</Partitioner>
<EndPointSnitch>org.apache.cassandra.locator.EndPointSnitch</EndPointSnitch>
<ReplicaPlacementStrategy>org.apache.cassandra.locator.RackUnawareStrategy</ReplicaPlacementStrategy>
<ReplicationFactor>1</ReplicationFactor>
Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java?rev=808206&r1=808205&r2=808206&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java (original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/PartitionerTestCase.java Wed Aug 26 22:20:23 2009
@@ -50,6 +50,38 @@
assert tok("asdz").compareTo(tok("asdf")) > 0;
}
+ public void assertMidpoint(T left, T right, int depth)
+ {
+ T mid = this.part.midpoint(left, right);
+ assert new Range(left, right).contains(mid)
+ : "For " + tos(left) + "," + tos(right) + ": range did not contain mid:" + tos(mid);
+ if (depth > 0)
+ assertMidpoint(left, mid, depth-1);
+ if (depth > 0)
+ assertMidpoint(mid, right, depth-1);
+ }
+
+ @Test
+ public void testMidpoint()
+ {
+ assertMidpoint(tok("a"), tok("b"), 16);
+ assertMidpoint(tok("a"), tok("bbb"), 16);
+ }
+
+ @Test
+ public void testMidpointMinimum()
+ {
+ assertMidpoint(tok(""), tok("a"), 16);
+ assertMidpoint(tok(""), tok("aaa"), 16);
+ }
+
+ @Test
+ public void testMidpointWrapping()
+ {
+ assertMidpoint(tok(""), tok(""), 16);
+ assertMidpoint(tok("a"), tok(""), 16);
+ }
+
@Test
public void testTokenFactoryBytes()
{