You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by dm...@apache.org on 2017/03/31 17:06:25 UTC
ignite git commit: IGNITE-4828: Improve the distribution of keys
within partitions
Repository: ignite
Updated Branches:
refs/heads/ignite-4828 b43dd2bbf -> ff82f7ca8
IGNITE-4828: Improve the distribution of keys within partitions
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo
Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/ff82f7ca
Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/ff82f7ca
Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/ff82f7ca
Branch: refs/heads/ignite-4828
Commit: ff82f7ca86079a4c2919dc8684104ba49cfecaad
Parents: b43dd2b
Author: Denis Magda <dm...@gridgain.com>
Authored: Fri Mar 31 13:06:20 2017 -0400
Committer: Denis Magda <dm...@gridgain.com>
Committed: Fri Mar 31 13:06:20 2017 -0400
----------------------------------------------------------------------
.../rendezvous/RendezvousAffinityFunction.java | 28 ++++++++++-
...inityFunctionFastPowerOfTwoHashSelfTest.java | 50 ++++++++++++++++++++
...ousAffinityFunctionStandardHashSelfTest.java | 50 ++++++++++++++++++++
.../testsuites/IgniteCacheTestSuite2.java | 4 ++
4 files changed, 130 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/ignite/blob/ff82f7ca/modules/core/src/main/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunction.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunction.java b/modules/core/src/main/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunction.java
index 0fee1af..b9af1ff 100644
--- a/modules/core/src/main/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunction.java
+++ b/modules/core/src/main/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunction.java
@@ -107,6 +107,9 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza
/** Exclude neighbors warning. */
private transient boolean exclNeighborsWarn;
+ /** Enables advanced partitioning algorithm with better distribution for partitions of power of 2. */
+ private boolean powerOfTwoHashing;
+
/** Optional backup filter. First node is primary, second node is a node being tested. */
private IgniteBiPredicate<ClusterNode, ClusterNode> backupFilter;
@@ -188,7 +191,10 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza
A.ensure(parts > 0, "parts > 0");
this.exclNeighbors = exclNeighbors;
- this.parts = parts;
+
+ // ensure that hashType is calculated
+ setPartitions(parts);
+
this.backupFilter = backupFilter;
try {
@@ -226,6 +232,8 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza
this.parts = parts;
+ powerOfTwoHashing = isPartitionsPowerOfTwo();
+
return this;
}
@@ -507,7 +515,23 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza
throw new IllegalArgumentException("Null key is passed for a partition calculation. " +
"Make sure that an affinity key that is used is initialized properly.");
- return U.safeAbs(key.hashCode() % parts);
+ if (powerOfTwoHashing) {
+ int h;
+
+ int i = U.safeAbs((h = key.hashCode()) ^ (h >>> 16));
+
+ return i & (parts - 1);
+ } else
+ return U.safeAbs(key.hashCode() % parts);
+ }
+
+ /**
+ * Determines if the partitions number is power of 2.
+ *
+ * @return true of the partitions number is power of 2.
+ */
+ private boolean isPartitionsPowerOfTwo() {
+ return (parts & (parts - 1)) == 0;
}
/** {@inheritDoc} */
http://git-wip-us.apache.org/repos/asf/ignite/blob/ff82f7ca/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.java
----------------------------------------------------------------------
diff --git a/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.java b/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.java
new file mode 100644
index 0000000..683ffa2
--- /dev/null
+++ b/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.java
@@ -0,0 +1,50 @@
+/*
+ * 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.ignite.cache.affinity.rendezvous;
+
+import org.apache.ignite.Ignite;
+import org.apache.ignite.cache.affinity.AbstractAffinityFunctionSelfTest;
+import org.apache.ignite.cache.affinity.AffinityFunction;
+import org.apache.ignite.testframework.GridTestUtils;
+
+/**
+ * Tests for {@link RendezvousAffinityFunction}.
+ */
+public class RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest extends AbstractAffinityFunctionSelfTest {
+ /** Ignite. */
+ private static Ignite ignite;
+
+ /** {@inheritDoc} */
+ @Override protected void beforeTestsStarted() throws Exception {
+ ignite = startGrid();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected void afterTestsStopped() throws Exception {
+ stopAllGrids();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected AffinityFunction affinityFunction() {
+ AffinityFunction aff = new RendezvousAffinityFunction(512, null);
+
+ GridTestUtils.setFieldValue(aff, "ignite", ignite);
+
+ return aff;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/ff82f7ca/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionStandardHashSelfTest.java
----------------------------------------------------------------------
diff --git a/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionStandardHashSelfTest.java b/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionStandardHashSelfTest.java
new file mode 100644
index 0000000..ed47c57
--- /dev/null
+++ b/modules/core/src/test/java/org/apache/ignite/cache/affinity/rendezvous/RendezvousAffinityFunctionStandardHashSelfTest.java
@@ -0,0 +1,50 @@
+/*
+ * 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.ignite.cache.affinity.rendezvous;
+
+import org.apache.ignite.Ignite;
+import org.apache.ignite.cache.affinity.AbstractAffinityFunctionSelfTest;
+import org.apache.ignite.cache.affinity.AffinityFunction;
+import org.apache.ignite.testframework.GridTestUtils;
+
+/**
+ * Tests for {@link RendezvousAffinityFunction}.
+ */
+public class RendezvousAffinityFunctionStandardHashSelfTest extends AbstractAffinityFunctionSelfTest {
+ /** Ignite. */
+ private static Ignite ignite;
+
+ /** {@inheritDoc} */
+ @Override protected void beforeTestsStarted() throws Exception {
+ ignite = startGrid();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected void afterTestsStopped() throws Exception {
+ stopAllGrids();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected AffinityFunction affinityFunction() {
+ AffinityFunction aff = new RendezvousAffinityFunction(513, null);
+
+ GridTestUtils.setFieldValue(aff, "ignite", ignite);
+
+ return aff;
+ }
+}
http://git-wip-us.apache.org/repos/asf/ignite/blob/ff82f7ca/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheTestSuite2.java
----------------------------------------------------------------------
diff --git a/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheTestSuite2.java b/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheTestSuite2.java
index e37a8a1..f6b1cdb 100644
--- a/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheTestSuite2.java
+++ b/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheTestSuite2.java
@@ -22,6 +22,8 @@ import org.apache.ignite.cache.affinity.fair.FairAffinityFunctionBackupFilterSel
import org.apache.ignite.cache.affinity.fair.FairAffinityFunctionExcludeNeighborsSelfTest;
import org.apache.ignite.cache.affinity.rendezvous.RendezvousAffinityFunctionBackupFilterSelfTest;
import org.apache.ignite.cache.affinity.rendezvous.RendezvousAffinityFunctionExcludeNeighborsSelfTest;
+import org.apache.ignite.cache.affinity.rendezvous.RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest;
+import org.apache.ignite.cache.affinity.rendezvous.RendezvousAffinityFunctionStandardHashSelfTest;
import org.apache.ignite.internal.processors.cache.CacheConcurrentReadThroughTest;
import org.apache.ignite.internal.processors.cache.CacheConfigurationLeakTest;
import org.apache.ignite.internal.processors.cache.CacheDhtLocalPartitionAfterRemoveSelfTest;
@@ -219,6 +221,8 @@ public class IgniteCacheTestSuite2 extends TestSuite {
suite.addTest(new TestSuite(GridCacheDhtPreloadUnloadSelfTest.class));
suite.addTest(new TestSuite(RendezvousAffinityFunctionBackupFilterSelfTest.class));
suite.addTest(new TestSuite(FairAffinityFunctionBackupFilterSelfTest.class));
+ suite.addTest(new TestSuite(RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.class));
+ suite.addTest(new TestSuite(RendezvousAffinityFunctionStandardHashSelfTest.class));
suite.addTest(new TestSuite(GridCachePartitionedPreloadLifecycleSelfTest.class));
suite.addTest(new TestSuite(CacheLoadingConcurrentGridStartSelfTest.class));
suite.addTest(new TestSuite(CacheLoadingConcurrentGridStartSelfTestAllowOverwrite.class));