Repository: incubator-ignite Updated Branches: refs/heads/ignite-396 [created] 658e7aa1a
ignite-396 Batch eviction support added to CacheFifoEvictionPolicy Project: http://git-wip-us.apache.org/repos/asf/incubator-ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-ignite/commit/658e7aa1 Tree: http://git-wip-us.apache.org/repos/asf/incubator-ignite/tree/658e7aa1 Diff: http://git-wip-us.apache.org/repos/asf/incubator-ignite/diff/658e7aa1 Branch: refs/heads/ignite-396 Commit: 658e7aa1a73427f831c60f81bf6f3fdcb48f0347 Parents: 2126914 Author: Andrey Gura <ag...@gridgain.com> Authored: Fri Mar 20 18:19:11 2015 +0300 Committer: Andrey Gura <ag...@gridgain.com> Committed: Wed Mar 25 12:34:23 2015 +0300 ---------------------------------------------------------------------- .../cache/eviction/fifo/FifoEvictionPolicy.java | 52 ++- .../eviction/fifo/FifoEvictionPolicyMBean.java | 16 + ...ridCacheFifoBatchEvictionPolicySelfTest.java | 373 +++++++++++++++++++ 3 files changed, 432 insertions(+), 9 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/658e7aa1/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicy.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicy.java b/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicy.java index d32c746..a938bf7 100644 --- a/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicy.java +++ b/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicy.java @@ -27,8 +27,8 @@ import java.io.*; import java.util.*; /** - * Eviction policy based on {@code First In First Out (FIFO)} algorithm. This - * implementation is very efficient since it does not create any additional + * Eviction policy based on {@code First In First Out (FIFO)} algorithm and supports batch eviction. + * This implementation is very efficient since it does not create any additional * table-like data structures. The {@code FIFO} ordering information is * maintained by attaching ordering metadata to cache entries. */ @@ -39,6 +39,9 @@ public class FifoEvictionPolicy<K, V> implements EvictionPolicy<K, V>, FifoEvict /** Maximum size. */ private volatile int max = CacheConfiguration.DFLT_CACHE_SIZE; + /** Batch size. */ + private volatile int batchSize = 1; + /** FIFO queue. */ private final ConcurrentLinkedDeque8<EvictableEntry<K, V>> queue = new ConcurrentLinkedDeque8<>(); @@ -62,6 +65,20 @@ public class FifoEvictionPolicy<K, V> implements EvictionPolicy<K, V>, FifoEvict } /** + * Constructs FIFO eviction policy with maximum size and given batch size. Empty entries are allowed. + * + * @param max Maximum allowed size of cache before entry will start getting evicted. + * @param batchSize Maximum size of batch. + */ + public FifoEvictionPolicy(int max, int batchSize) { + A.ensure(max > 0, "max > 0"); + A.ensure(batchSize > 0, "batchSize > 0"); + + this.max = max; + this.batchSize = batchSize; + } + + /** * Gets maximum allowed size of cache before entry will start getting evicted. * * @return Maximum allowed size of cache before entry will start getting evicted. @@ -82,6 +99,18 @@ public class FifoEvictionPolicy<K, V> implements EvictionPolicy<K, V>, FifoEvict } /** {@inheritDoc} */ + @Override public int getBatchSize() { + return batchSize; + } + + /** {@inheritDoc} */ + @Override public void setBatchSize(int batchSize) { + A.ensure(batchSize > 0, "batchSize > 0"); + + this.batchSize = batchSize; + } + + /** {@inheritDoc} */ @Override public int getCurrentSize() { return queue.size(); } @@ -158,18 +187,23 @@ public class FifoEvictionPolicy<K, V> implements EvictionPolicy<K, V>, FifoEvict private void shrink() { int max = this.max; + int batchSize = this.batchSize; + int startSize = queue.sizex(); - for (int i = 0; i < startSize && queue.sizex() > max; i++) { - EvictableEntry<K, V> entry = queue.poll(); + // // Shrink only if queue is full. + if (startSize > max) { + for (int i = 0; i < startSize && queue.sizex() > (max - batchSize + 1); i++) { + EvictableEntry<K, V> entry = queue.poll(); - if (entry == null) - break; + if (entry == null) + break; - if (!entry.evict()) { - entry.removeMeta(); + if (!entry.evict()) { + entry.removeMeta(); - touch(entry); + touch(entry); + } } } } http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/658e7aa1/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicyMBean.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicyMBean.java b/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicyMBean.java index 4827e95..63a413e 100644 --- a/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicyMBean.java +++ b/modules/core/src/main/java/org/apache/ignite/cache/eviction/fifo/FifoEvictionPolicyMBean.java @@ -41,6 +41,22 @@ public interface FifoEvictionPolicyMBean { public void setMaxSize(int max); /** + * Gets batch size. + * + * @return batch size. + */ + @MXBeanDescription("Batch size.") + public int getBatchSize(); + + /** + * Sets batch size. + * + * @param batchSize Batch size. + */ + @MXBeanDescription("Set batch size.") + public void setBatchSize(int batchSize); + + /** * Gets current queue size. * * @return Current queue size. http://git-wip-us.apache.org/repos/asf/incubator-ignite/blob/658e7aa1/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/fifo/GridCacheFifoBatchEvictionPolicySelfTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/fifo/GridCacheFifoBatchEvictionPolicySelfTest.java b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/fifo/GridCacheFifoBatchEvictionPolicySelfTest.java new file mode 100644 index 0000000..a3c4610 --- /dev/null +++ b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/fifo/GridCacheFifoBatchEvictionPolicySelfTest.java @@ -0,0 +1,373 @@ +/* + * 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.internal.processors.cache.eviction.fifo; + +import org.apache.ignite.*; +import org.apache.ignite.cache.eviction.*; +import org.apache.ignite.cache.eviction.fifo.*; +import org.apache.ignite.internal.processors.cache.eviction.*; + +import java.util.*; + +import static org.apache.ignite.cache.CacheMode.LOCAL; + +/** + * FIFO batch eviction test. + */ +public class GridCacheFifoBatchEvictionPolicySelfTest extends + GridCacheEvictionAbstractTest<FifoEvictionPolicy<String, String>> { + /** + * @throws Exception If failed. + */ + public void testPolicy() throws Exception { + try { + startGrid(); + + MockEntry e1 = new MockEntry("1", "1"); + MockEntry e2 = new MockEntry("2", "2"); + MockEntry e3 = new MockEntry("3", "3"); + MockEntry e4 = new MockEntry("4", "4"); + MockEntry e5 = new MockEntry("5", "5"); + + FifoEvictionPolicy<String, String> p = policy(); + + p.setMaxSize(4); + p.setBatchSize(2); + + p.onEntryAccessed(false, e1); + + check(p.queue(), e1); + + p.onEntryAccessed(false, e2); + + check(p.queue(), e1, e2); + + p.onEntryAccessed(false, e3); + + check(p.queue(), e1, e2, e3); + + p.onEntryAccessed(false, e4); + + check(p.queue(), e1, e2, e3, e4); + + assertFalse(e1.isEvicted()); + assertFalse(e2.isEvicted()); + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + + assertEquals(4, p.getCurrentSize()); + + p.onEntryAccessed(false, e5); + + // Batch evicted. + check(p.queue(), e3, e4, e5); + + assertEquals(3, p.getCurrentSize()); + + assertTrue(e1.isEvicted()); + assertTrue(e2.isEvicted()); + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + assertFalse(e5.isEvicted()); + + p.onEntryAccessed(false, e1 = new MockEntry("1", "1")); + + check(p.queue(), e3, e4, e5, e1); + + assertEquals(4, p.getCurrentSize()); + + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + assertFalse(e5.isEvicted()); + assertFalse(e1.isEvicted()); + + p.onEntryAccessed(false, e5); + + check(p.queue(), e3, e4, e5, e1); + + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + assertFalse(e5.isEvicted()); + assertFalse(e1.isEvicted()); + + p.onEntryAccessed(false, e1); + + assertEquals(4, p.getCurrentSize()); + + check(p.queue(), e3, e4, e5, e1); + + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + assertFalse(e5.isEvicted()); + assertFalse(e1.isEvicted()); + + p.onEntryAccessed(true, e1); + + assertEquals(3, p.getCurrentSize()); + + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + assertFalse(e5.isEvicted()); + + p.onEntryAccessed(true, e4); + + assertEquals(2, p.getCurrentSize()); + + assertFalse(e3.isEvicted()); + assertFalse(e5.isEvicted()); + + p.onEntryAccessed(true, e5); + + assertEquals(1, p.getCurrentSize()); + + assertFalse(e3.isEvicted()); + + p.onEntryAccessed(true, e3); + + assertEquals(0, p.getCurrentSize()); + + assertFalse(e3.isEvicted()); + + info(p); + } + finally { + stopAllGrids(); + } + } + + /** + * @throws Exception If failed. + */ + public void testMemory() throws Exception { + try { + startGrid(); + + FifoEvictionPolicy<String, String> p = policy(); + + int max = 10; + + int batchSize = 2; + + p.setMaxSize(max); + p.setBatchSize(batchSize); + + int cnt = 11; + + for (int i = 0; i < cnt; i++) + p.onEntryAccessed(false, new MockEntry(Integer.toString(i), Integer.toString(i))); + + info(p); + + assertEquals(cnt - batchSize, p.getCurrentSize()); + } + finally { + stopAllGrids(); + } + } + + /** + * @throws Exception If failed. + */ + public void testRandom() throws Exception { + try { + startGrid(); + + FifoEvictionPolicy<String, String> p = policy(); + + int max = 10; + + p.setMaxSize(max); + p.setBatchSize(2); + + Random rand = new Random(); + + int keys = 31; + + MockEntry[] fifos = new MockEntry[keys]; + + for (int i = 0; i < fifos.length; i++) + fifos[i] = new MockEntry(Integer.toString(i)); + + int runs = 5000000; + + for (int i = 0; i < runs; i++) { + boolean rmv = rand.nextBoolean(); + + int j = rand.nextInt(fifos.length); + + MockEntry e = entry(fifos, j); + + if (rmv) + fifos[j] = new MockEntry(Integer.toString(j)); + + p.onEntryAccessed(rmv, e); + } + + info(p); + + int curSize = p.getCurrentSize(); + + assert curSize <= max : "curSize <= max [curSize=" + curSize + ", max=" + max + ']'; + } + finally { + stopAllGrids(); + } + } + + /** + * @throws Exception If failed. + */ + public void testAllowEmptyEntries() throws Exception { + try { + startGrid(); + + MockEntry e1 = new MockEntry("1"); + + MockEntry e2 = new MockEntry("2"); + + MockEntry e3 = new MockEntry("3"); + + MockEntry e4 = new MockEntry("4"); + + MockEntry e5 = new MockEntry("5"); + + FifoEvictionPolicy<String, String> p = policy(); + + p.setBatchSize(2); + + p.onEntryAccessed(false, e1); + + assertFalse(e1.isEvicted()); + + p.onEntryAccessed(false, e2); + + assertFalse(e1.isEvicted()); + assertFalse(e2.isEvicted()); + + p.onEntryAccessed(false, e3); + + assertFalse(e1.isEvicted()); + assertFalse(e3.isEvicted()); + + p.onEntryAccessed(false, e4); + + assertFalse(e1.isEvicted()); + assertFalse(e3.isEvicted()); + assertFalse(e4.isEvicted()); + + p.onEntryAccessed(false, e5); + + assertFalse(e1.isEvicted()); + assertFalse(e3.isEvicted()); + assertFalse(e5.isEvicted()); + } + finally { + stopAllGrids(); + } + } + + /** + * @throws Exception If failed. + */ + public void testPut() throws Exception { + mode = LOCAL; + syncCommit = true; + plcMax = 10; + + Ignite ignite = startGrid(); + + try { + IgniteCache<Object, Object> cache = ignite.cache(null); + + int cnt = 500; + + int min = Integer.MAX_VALUE; + + int minIdx = 0; + + for (int i = 0; i < cnt; i++) { + cache.put(i, i); + + int cacheSize = cache.size(); + + if (i > plcMax && cacheSize < min) { + min = cacheSize; + minIdx = i; + } + } + + // Batch evicted. + assert min >= plcMax - 1 : "Min cache size is too small: " + min; + + info("Min cache size [min=" + min + ", idx=" + minIdx + ']'); + info("Current cache size " + cache.size()); + info("Current cache key size " + cache.size()); + + min = Integer.MAX_VALUE; + + minIdx = 0; + + // Touch. + for (int i = cnt; --i > cnt - plcMax;) { + cache.get(i); + + int cacheSize = cache.size(); + + if (cacheSize < min) { + min = cacheSize; + minIdx = i; + } + } + + info("----"); + info("Min cache size [min=" + min + ", idx=" + minIdx + ']'); + info("Current cache size " + cache.size()); + info("Current cache key size " + cache.size()); + + // Batch evicted. + assert min >= plcMax - 1 : "Min cache size is too small: " + min; + } + finally { + stopAllGrids(); + } + } + + /** {@inheritDoc} */ + @Override protected FifoEvictionPolicy<String, String> createPolicy(int plcMax) { + return new FifoEvictionPolicy<>(10, 2); + } + + /** {@inheritDoc} */ + @Override protected FifoEvictionPolicy<String, String> createNearPolicy(int nearMax) { + return new FifoEvictionPolicy<>(nearMax); + } + + /** {@inheritDoc} */ + @Override protected void checkNearPolicies(int endNearPlcSize) { + for (int i = 0; i < gridCnt; i++) + for (EvictableEntry<String, String> e : nearPolicy(i).queue()) + assert !e.isCached() : "Invalid near policy size: " + nearPolicy(i).queue(); + } + + /** {@inheritDoc} */ + @Override protected void checkPolicies(int plcMax) { + for (int i = 0; i < gridCnt; i++) + assert policy(i).queue().size() <= plcMax; + } + +}
