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/55ab10ee Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/55ab10ee Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/55ab10ee Branch: refs/heads/ignite-4929 Commit: 55ab10eee485ef47a1c0794cbc90da0376ecd738 Parents: c9d08d3 Author: Yakov Zhdanov <[email protected]> Authored: Tue Apr 11 19:47:10 2017 +0300 Committer: Yakov Zhdanov <[email protected]> Committed: Tue Apr 11 19:47:10 2017 +0300 ---------------------------------------------------------------------- .../rendezvous/RendezvousAffinityFunction.java | 26 ++++++++-- .../GridCachePartitionExchangeManager.java | 2 +- ...inityFunctionFastPowerOfTwoHashSelfTest.java | 50 ++++++++++++++++++++ ...ousAffinityFunctionStandardHashSelfTest.java | 50 ++++++++++++++++++++ .../testsuites/IgniteCacheTestSuite2.java | 8 +++- 5 files changed, 129 insertions(+), 7 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/55ab10ee/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..dcac7d4 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 @@ -101,6 +101,9 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza /** Number of partitions. */ private int parts; + /** Mask to use in calculation when partitions count is power of 2. */ + private transient int mask = -1; + /** Exclude neighbors flag. */ private boolean exclNeighbors; @@ -188,7 +191,9 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza A.ensure(parts > 0, "parts > 0"); this.exclNeighbors = exclNeighbors; - this.parts = parts; + + setPartitions(parts); + this.backupFilter = backupFilter; try { @@ -216,16 +221,22 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza } /** - * Sets total number of partitions. + * Sets total number of partitions.If the number of partitions is a power of two, + * the PowerOfTwo hashing method will be used. Otherwise the Standard hashing + * method will be applied. * * @param parts Total number of partitions. * @return {@code this} for chaining. */ public RendezvousAffinityFunction setPartitions(int parts) { - A.ensure(parts <= CacheConfiguration.MAX_PARTITIONS_COUNT, "parts <= " + CacheConfiguration.MAX_PARTITIONS_COUNT); + A.ensure(parts <= CacheConfiguration.MAX_PARTITIONS_COUNT, + "parts <= " + CacheConfiguration.MAX_PARTITIONS_COUNT); + A.ensure(parts > 0, "parts > 0"); this.parts = parts; + mask = (parts & (parts - 1)) == 0 ? parts - 1 : -1; + return this; } @@ -507,6 +518,12 @@ 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."); + if (mask >= 0) { + int h; + + return ((h = key.hashCode()) ^ (h >>> 16)) & mask; + } + return U.safeAbs(key.hashCode() % parts); } @@ -553,7 +570,8 @@ public class RendezvousAffinityFunction implements AffinityFunction, Externaliza /** {@inheritDoc} */ @SuppressWarnings("unchecked") @Override public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { - parts = in.readInt(); + setPartitions(in.readInt()); + exclNeighbors = in.readBoolean(); hashIdRslvr = (AffinityNodeHashResolver)in.readObject(); backupFilter = (IgniteBiPredicate<ClusterNode, ClusterNode>)in.readObject(); http://git-wip-us.apache.org/repos/asf/ignite/blob/55ab10ee/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCachePartitionExchangeManager.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCachePartitionExchangeManager.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCachePartitionExchangeManager.java index 885106d..1297c38 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCachePartitionExchangeManager.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCachePartitionExchangeManager.java @@ -42,7 +42,6 @@ import java.util.concurrent.atomic.AtomicReference; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; import org.apache.ignite.IgniteCheckedException; -import org.apache.ignite.internal.IgniteNeedReconnectException; import org.apache.ignite.IgniteSystemProperties; import org.apache.ignite.cache.affinity.AffinityFunction; import org.apache.ignite.cluster.ClusterNode; @@ -52,6 +51,7 @@ import org.apache.ignite.internal.IgniteClientDisconnectedCheckedException; import org.apache.ignite.internal.IgniteFutureTimeoutCheckedException; import org.apache.ignite.internal.IgniteInternalFuture; import org.apache.ignite.internal.IgniteInterruptedCheckedException; +import org.apache.ignite.internal.IgniteNeedReconnectException; import org.apache.ignite.internal.cluster.ClusterTopologyCheckedException; import org.apache.ignite.internal.events.DiscoveryCustomEvent; import org.apache.ignite.internal.managers.discovery.DiscoCache; http://git-wip-us.apache.org/repos/asf/ignite/blob/55ab10ee/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/55ab10ee/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/55ab10ee/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..0db7d06 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; @@ -114,11 +116,11 @@ import org.apache.ignite.internal.processors.cache.distributed.near.GridCachePar import org.apache.ignite.internal.processors.cache.distributed.near.GridCachePartitionedTxSingleThreadedSelfTest; import org.apache.ignite.internal.processors.cache.distributed.near.GridCachePartitionedTxTimeoutSelfTest; import org.apache.ignite.internal.processors.cache.distributed.near.GridCacheRendezvousAffinityClientSelfTest; -import org.apache.ignite.internal.processors.cache.distributed.near.GridPartitionedBackupLoadSelfTest; import org.apache.ignite.internal.processors.cache.distributed.near.GridNearCacheStoreUpdateTest; +import org.apache.ignite.internal.processors.cache.distributed.near.GridNearOffheapCacheStoreUpdateTest; +import org.apache.ignite.internal.processors.cache.distributed.near.GridPartitionedBackupLoadSelfTest; import org.apache.ignite.internal.processors.cache.distributed.near.NearCacheSyncUpdateTest; import org.apache.ignite.internal.processors.cache.distributed.near.NoneRebalanceModeSelfTest; -import org.apache.ignite.internal.processors.cache.distributed.near.GridNearOffheapCacheStoreUpdateTest; import org.apache.ignite.internal.processors.cache.distributed.replicated.GridCacheReplicatedEvictionSelfTest; import org.apache.ignite.internal.processors.cache.distributed.replicated.GridCacheReplicatedJobExecutionTest; import org.apache.ignite.internal.processors.cache.local.GridCacheLocalAtomicBasicStoreSelfTest; @@ -181,6 +183,8 @@ public class IgniteCacheTestSuite2 extends TestSuite { suite.addTest(new TestSuite(GridCacheAtomicNearReadersSelfTest.class)); suite.addTest(new TestSuite(GridCachePartitionedAffinitySelfTest.class)); suite.addTest(new TestSuite(RendezvousAffinityFunctionExcludeNeighborsSelfTest.class)); + suite.addTest(new TestSuite(RendezvousAffinityFunctionFastPowerOfTwoHashSelfTest.class)); + suite.addTest(new TestSuite(RendezvousAffinityFunctionStandardHashSelfTest.class)); suite.addTest(new TestSuite(FairAffinityFunctionExcludeNeighborsSelfTest.class)); suite.addTest(new TestSuite(GridCacheRendezvousAffinityClientSelfTest.class)); suite.addTest(new TestSuite(GridCachePartitionedProjectionAffinitySelfTest.class));
