IGNITE-4534 - Added offheap evictions
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/ff5b3e16 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/ff5b3e16 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/ff5b3e16 Branch: refs/heads/ignite-3477-master Commit: ff5b3e16850e503b79a13c44b667140d23c1f080 Parents: baa3835 Author: Ivan Rakov <[email protected]> Authored: Mon Apr 10 19:23:43 2017 +0300 Committer: Alexey Goncharuk <[email protected]> Committed: Mon Apr 10 19:23:43 2017 +0300 ---------------------------------------------------------------------- .../configuration/DataPageEvictionMode.java | 32 +++ .../MemoryPolicyConfiguration.java | 70 ++++++ .../ignite/internal/pagemem/PageSupport.java | 10 + .../pagemem/impl/PageMemoryNoStoreImpl.java | 8 + .../internal/pagemem/impl/PageNoStoreImpl.java | 0 .../cache/CacheOffheapEvictionManager.java | 6 +- .../processors/cache/GridCacheAdapter.java | 2 + .../processors/cache/GridCacheEntryEx.java | 5 +- .../cache/GridCacheEvictionManager.java | 2 +- .../processors/cache/GridCacheMapEntry.java | 32 ++- .../cache/IgniteCacheOffheapManagerImpl.java | 34 ++- .../processors/cache/database/CacheDataRow.java | 5 + .../cache/database/CacheDataRowAdapter.java | 116 ++++++++- .../IgniteCacheDatabaseSharedManager.java | 126 ++++++++-- .../processors/cache/database/MemoryPolicy.java | 19 +- .../evict/FairFifoPageEvictionTracker.java | 74 ++++++ .../database/evict/NoOpPageEvictionTracker.java | 50 ++++ .../evict/PageAbstractEvictionTracker.java | 243 +++++++++++++++++++ .../database/evict/PageEvictionTracker.java | 52 ++++ .../evict/Random2LruPageEvictionTracker.java | 180 ++++++++++++++ .../evict/RandomLruPageEvictionTracker.java | 157 ++++++++++++ .../cache/database/freelist/FreeListImpl.java | 62 +++-- .../cache/database/tree/io/DataPageIO.java | 110 ++++++++- .../dht/atomic/GridDhtAtomicCache.java | 2 + .../cache/distributed/near/GridNearTxLocal.java | 2 + .../distributed/near/GridNearTxRemote.java | 4 +- .../local/atomic/GridLocalAtomicCache.java | 6 +- .../cacheobject/IgniteCacheObjectProcessor.java | 7 - .../IgniteCacheObjectProcessorImpl.java | 16 -- .../processors/cache/GridCacheTestEntryEx.java | 2 +- .../dht/GridCacheDhtEntrySelfTest.java | 4 +- .../paged/PageEvictionAbstractTest.java | 124 ++++++++++ .../paged/PageEvictionMultinodeTest.java | 110 +++++++++ .../paged/PageEvictionReadThroughTest.java | 140 +++++++++++ .../paged/PageEvictionTouchOrderTest.java | 109 +++++++++ .../paged/PageEvictionWithRebalanceTest.java | 81 +++++++ .../Random2LruPageEvictionMultinodeTest.java | 30 +++ ...Random2LruPageEvictionWithRebalanceTest.java | 30 +++ .../RandomLruPageEvictionMultinodeTest.java | 30 +++ .../RandomLruPageEvictionWithRebalanceTest.java | 30 +++ .../cache/eviction/paged/TestObject.java | 78 ++++++ .../database/FreeListImplSelfTest.java | 13 +- .../IgniteCacheEvictionSelfTestSuite.java | 13 + .../processors/query/h2/opt/GridH2Row.java | 5 + 44 files changed, 2130 insertions(+), 101 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/configuration/DataPageEvictionMode.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/configuration/DataPageEvictionMode.java b/modules/core/src/main/java/org/apache/ignite/configuration/DataPageEvictionMode.java new file mode 100644 index 0000000..bada68e --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/configuration/DataPageEvictionMode.java @@ -0,0 +1,32 @@ +/* +* 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.configuration; + +/** + * Enumeration defines data page eviction modes. + */ +public enum DataPageEvictionMode { + /** Disabled. */ + DISABLED, + + /** Random lru. */ + RANDOM_LRU, + + /** Random 2-lru. */ + RANDOM_2_LRU +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/configuration/MemoryPolicyConfiguration.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/configuration/MemoryPolicyConfiguration.java b/modules/core/src/main/java/org/apache/ignite/configuration/MemoryPolicyConfiguration.java index 2add64f..d6203c6 100644 --- a/modules/core/src/main/java/org/apache/ignite/configuration/MemoryPolicyConfiguration.java +++ b/modules/core/src/main/java/org/apache/ignite/configuration/MemoryPolicyConfiguration.java @@ -19,6 +19,8 @@ package org.apache.ignite.configuration; import java.io.Serializable; import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.processors.cache.database.MemoryPolicy; +import org.apache.ignite.internal.processors.cache.database.freelist.FreeList; +import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO; /** * Configuration bean used for creating {@link MemoryPolicy} instances. @@ -43,6 +45,18 @@ public final class MemoryPolicyConfiguration implements Serializable { return name; } + /** Algorithm for per-page eviction. If {@link DataPageEvictionMode#DISABLED} set, eviction is not performed. */ + private DataPageEvictionMode pageEvictionMode = DataPageEvictionMode.DISABLED; + + /** Allocation of new {@link DataPageIO} pages is stopped when this percentage of pages are allocated. */ + private double evictionThreshold = 0.9; + + /** Allocation of new {@link DataPageIO} pages is stopped by maintaining this amount of empty pages in + * corresponding {@link FreeList} bucket. Pages get into the bucket through evicting all data entries one by one. + * Higher load and contention require larger pool size. + */ + private int emptyPagesPoolSize = 100; + /** * @param name Unique name of MemoryPolicy. */ @@ -83,4 +97,60 @@ public final class MemoryPolicyConfiguration implements Serializable { return this; } + + /** + * Gets data page eviction mode. + */ + public DataPageEvictionMode getPageEvictionMode() { + return pageEvictionMode; + } + + /** + * Sets data page eviction mode. + * + * @param evictionMode Eviction mode. + */ + public MemoryPolicyConfiguration setPageEvictionMode(DataPageEvictionMode evictionMode) { + pageEvictionMode = evictionMode; + + return this; + } + + /** + * Gets data page eviction threshold. + * + * @return Data page eviction threshold. + */ + public double getEvictionThreshold() { + return evictionThreshold; + } + + /** + * Sets data page eviction threshold. + * + * @param evictionThreshold Eviction threshold. + */ + public MemoryPolicyConfiguration setEvictionThreshold(double evictionThreshold) { + this.evictionThreshold = evictionThreshold; + + return this; + } + + /** + * Gets empty pages pool size. + */ + public int getEmptyPagesPoolSize() { + return emptyPagesPoolSize; + } + + /** + * Sets empty pages pool size. + * + * @param emptyPagesPoolSize Empty pages pool size. + */ + public MemoryPolicyConfiguration setEmptyPagesPoolSize(int emptyPagesPoolSize) { + this.emptyPagesPoolSize = emptyPagesPoolSize; + + return this; + } } http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageSupport.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageSupport.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageSupport.java index 8076f28..0f39058 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageSupport.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageSupport.java @@ -53,6 +53,16 @@ public interface PageSupport { public long readLock(int cacheId, long pageId, long page); /** + * Obtains read lock without checking page tag. + * + * @param cacheId Cache ID. + * @param pageId Page ID. + * @param page Page pointer. + * @return Pointer for reading the page. + */ + public long readLockForce(int cacheId, long pageId, long page); + + /** * Releases locked page. * * @param cacheId Cache ID. http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryNoStoreImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryNoStoreImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryNoStoreImpl.java index f24113c..7134cff 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryNoStoreImpl.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryNoStoreImpl.java @@ -416,6 +416,14 @@ public class PageMemoryNoStoreImpl implements PageMemory { } /** {@inheritDoc} */ + public long readLockForce(int cacheId, long pageId, long page) { + if (rwLock.readLock(page + LOCK_OFFSET, -1)) + return page + PAGE_OVERHEAD; + + return 0L; + } + + /** {@inheritDoc} */ @Override public void readUnlock(int cacheId, long pageId, long page) { rwLock.readUnlock(page + LOCK_OFFSET); } http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageNoStoreImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageNoStoreImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageNoStoreImpl.java new file mode 100644 index 0000000..e69de29 http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/CacheOffheapEvictionManager.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/CacheOffheapEvictionManager.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/CacheOffheapEvictionManager.java index 99df39d..f8e9f32 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/CacheOffheapEvictionManager.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/CacheOffheapEvictionManager.java @@ -27,10 +27,6 @@ import org.apache.ignite.internal.util.typedef.internal.U; import org.jetbrains.annotations.Nullable; /** - * TODO GG-11140. - * - * Temporary implementation, ignores configured EvictionPolicy, evictions to be reconsidered as - * part of GG-11140. * */ public class CacheOffheapEvictionManager extends GridCacheManagerAdapter implements CacheEvictionManager { @@ -51,7 +47,7 @@ public class CacheOffheapEvictionManager extends GridCacheManagerAdapter impleme return; } - boolean evicted = e.evictInternal(GridCacheVersionManager.EVICT_VER, null); + boolean evicted = e.evictInternal(GridCacheVersionManager.EVICT_VER, null, false); if (evicted) cctx.cache().removeEntry(e); http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheAdapter.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheAdapter.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheAdapter.java index 9a6ff11..d791b7c 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheAdapter.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheAdapter.java @@ -2073,6 +2073,8 @@ public abstract class GridCacheAdapter<K, V> implements IgniteInternalCache<K, V GridCacheEntryEx entry = null; try { + ctx.shared().database().ensureFreeSpace(ctx.memoryPolicy()); + entry = entryEx(key); entry.unswap(); http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEntryEx.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEntryEx.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEntryEx.java index 99f9744..2066342 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEntryEx.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEntryEx.java @@ -213,11 +213,12 @@ public interface GridCacheEntryEx { /** * @param obsoleteVer Version for eviction. * @param filter Optional filter. + * @param evictOffheap Evict offheap value flag. * @return {@code True} if entry could be evicted. * @throws IgniteCheckedException In case of error. */ - public boolean evictInternal(GridCacheVersion obsoleteVer, @Nullable CacheEntryPredicate[] filter) - throws IgniteCheckedException; + public boolean evictInternal(GridCacheVersion obsoleteVer, @Nullable CacheEntryPredicate[] filter, + boolean evictOffheap) throws IgniteCheckedException; /** * Evicts entry when batch evict is performed. When called, does not write entry data to swap, but instead http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEvictionManager.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEvictionManager.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEvictionManager.java index 26f37a7..0deae07 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEvictionManager.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheEvictionManager.java @@ -135,7 +135,7 @@ public class GridCacheEvictionManager extends GridCacheManagerAdapter implements boolean hasVal = recordable && entry.hasValue(); - boolean evicted = entry.evictInternal(obsoleteVer, filter); + boolean evicted = entry.evictInternal(obsoleteVer, filter, false); if (evicted) { // Remove manually evicted entry from policy. http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheMapEntry.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheMapEntry.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheMapEntry.java index 7fad9f5..9e2cd70 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheMapEntry.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/GridCacheMapEntry.java @@ -43,6 +43,7 @@ import org.apache.ignite.internal.processors.affinity.AffinityTopologyVersion; import org.apache.ignite.internal.processors.cache.GridCacheUpdateAtomicResult.UpdateOutcome; import org.apache.ignite.internal.processors.cache.database.CacheDataRow; import org.apache.ignite.internal.processors.cache.database.CacheDataRowAdapter; +import org.apache.ignite.internal.processors.cache.database.MemoryPolicy; import org.apache.ignite.internal.processors.cache.distributed.dht.GridDhtCacheEntry; import org.apache.ignite.internal.processors.cache.distributed.dht.GridDhtLocalPartition; import org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicAbstractUpdateFuture; @@ -809,6 +810,8 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme boolean touch = false; try { + ensureFreeSpace(); + synchronized (this) { long ttl = ttlExtras(); @@ -908,6 +911,8 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme long updateCntr0; + ensureFreeSpace(); + synchronized (this) { checkObsolete(); @@ -1641,6 +1646,9 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme AtomicCacheUpdateClosure c; + if (!primary && !isNear()) + ensureFreeSpace(); + synchronized (this) { checkObsolete(); @@ -2567,6 +2575,8 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme GridDrType drType, boolean fromStore ) throws IgniteCheckedException, GridCacheEntryRemovedException { + ensureFreeSpace(); + synchronized (this) { checkObsolete(); @@ -3378,6 +3388,16 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme } /** + * Evicts necessary number of data pages if per-page eviction is configured in current {@link MemoryPolicy}. + */ + private void ensureFreeSpace() throws IgniteCheckedException { + // Deadlock alert: evicting data page causes removing (and locking) all entries on the page one by one. + assert !Thread.holdsLock(this); + + cctx.shared().database().ensureFreeSpace(cctx.memoryPolicy()); + } + + /** * @return Entry which holds key, value and version. */ private synchronized <K, V> CacheEntryImplEx<K, V> wrapVersionedWithValue() { @@ -3387,8 +3407,12 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme } /** {@inheritDoc} */ - @Override public boolean evictInternal(GridCacheVersion obsoleteVer, @Nullable CacheEntryPredicate[] filter) + @Override public boolean evictInternal( + GridCacheVersion obsoleteVer, + @Nullable CacheEntryPredicate[] filter, + boolean evictOffheap) throws IgniteCheckedException { + boolean marked = false; try { @@ -3411,6 +3435,9 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme // Nullify value after swap. value(null); + if (evictOffheap) + removeValue(); + marked = true; return true; @@ -3451,6 +3478,9 @@ public abstract class GridCacheMapEntry extends GridMetadataAwareAdapter impleme // Nullify value after swap. value(null); + if (evictOffheap) + removeValue(); + marked = true; return true; http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java index e022e57..73edbe1 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/IgniteCacheOffheapManagerImpl.java @@ -28,6 +28,7 @@ import javax.cache.Cache; import org.apache.ignite.IgniteCheckedException; import org.apache.ignite.IgniteException; import org.apache.ignite.cluster.ClusterNode; +import org.apache.ignite.configuration.DataPageEvictionMode; import org.apache.ignite.internal.NodeStoppingException; import org.apache.ignite.internal.pagemem.FullPageId; import org.apache.ignite.internal.pagemem.PageIdUtils; @@ -37,7 +38,6 @@ import org.apache.ignite.internal.processors.affinity.AffinityTopologyVersion; import org.apache.ignite.internal.processors.cache.database.CacheDataRow; import org.apache.ignite.internal.processors.cache.database.CacheDataRowAdapter; import org.apache.ignite.internal.processors.cache.database.CacheSearchRow; -import org.apache.ignite.internal.processors.cache.database.IgniteCacheDatabaseSharedManager; import org.apache.ignite.internal.processors.cache.database.RootPage; import org.apache.ignite.internal.processors.cache.database.RowStore; import org.apache.ignite.internal.processors.cache.database.freelist.FreeList; @@ -965,8 +965,12 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple CacheObject val, GridCacheVersion ver, long expireTime, - @Nullable CacheDataRow oldRow) throws IgniteCheckedException { - DataRow dataRow = new DataRow(key, val, ver, partId, expireTime); + @Nullable CacheDataRow oldRow) throws IgniteCheckedException + { + int cacheId = cctx.memoryPolicy().config().getPageEvictionMode() == DataPageEvictionMode.DISABLED ? + 0 : cctx.cacheId(); + + DataRow dataRow = new DataRow(key, val, ver, partId, expireTime, cacheId); if (canUpdateOldRow(oldRow, dataRow) && rowStore.updateRow(oldRow.link(), dataRow)) dataRow.link(oldRow.link()); @@ -997,7 +1001,10 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple throw new NodeStoppingException("Operation has been cancelled (node is stopping)."); try { - DataRow dataRow = new DataRow(key, val, ver, p, expireTime); + int cacheId = cctx.memoryPolicy().config().getPageEvictionMode() != DataPageEvictionMode.DISABLED ? + cctx.cacheId() : 0; + + DataRow dataRow = new DataRow(key, val, ver, p, expireTime, cacheId); CacheObjectContext coCtx = cctx.cacheObjectContext(); @@ -1140,9 +1147,12 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple CacheDataRow row = dataTree.findOne(new SearchRow(key), CacheDataRowAdapter.RowData.NO_KEY); - if (row != null) + if (row != null) { row.key(key); + cctx.memoryPolicy().evictionTracker().touchPage(row.link()); + } + return row; } @@ -1345,7 +1355,7 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple * @param part Partition. * @param expireTime Expire time. */ - DataRow(KeyCacheObject key, CacheObject val, GridCacheVersion ver, int part, long expireTime) { + DataRow(KeyCacheObject key, CacheObject val, GridCacheVersion ver, int part, long expireTime, int cacheId) { super(0); this.hash = key.hashCode(); @@ -1354,6 +1364,7 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple this.ver = ver; this.part = part; this.expireTime = expireTime; + this.cacheId = cacheId; } /** {@inheritDoc} */ @@ -1473,6 +1484,9 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple if (data.nextLink() == 0) { long addr = pageAddr + data.offset(); + if (cctx.memoryPolicy().config().getPageEvictionMode() != DataPageEvictionMode.DISABLED) + addr += 4; // Skip cache id. + final int len = PageUtils.getInt(addr, 0); int lenCmp = Integer.compare(len, bytes.length); @@ -1672,6 +1686,14 @@ public class IgniteCacheOffheapManagerImpl extends GridCacheManagerAdapter imple @Override public int getHash(long pageAddr, int idx) { return PageUtils.getInt(pageAddr, offset(idx) + 8); } + + /** {@inheritDoc} */ + @Override public void visit(long pageAddr, IgniteInClosure<CacheSearchRow> c) { + int cnt = getCount(pageAddr); + + for (int i = 0; i < cnt; i++) + c.apply(new CacheDataRowAdapter(getLink(pageAddr, i))); + } } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRow.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRow.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRow.java index cc26b21..e0076d5 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRow.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRow.java @@ -36,6 +36,11 @@ public interface CacheDataRow extends CacheSearchRow { public GridCacheVersion version(); /** + * @return Cache id. Stored only if memory policy with configured per-page eviction is used. + */ + public int cacheId(); + + /** * @return Expire time. */ public long expireTime(); http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRowAdapter.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRowAdapter.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRowAdapter.java index eca59d6..afeada5 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRowAdapter.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/CacheDataRowAdapter.java @@ -19,12 +19,14 @@ package org.apache.ignite.internal.processors.cache.database; import java.nio.ByteBuffer; import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.configuration.DataPageEvictionMode; import org.apache.ignite.internal.pagemem.PageIdUtils; import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.pagemem.PageUtils; import org.apache.ignite.internal.processors.cache.CacheObject; import org.apache.ignite.internal.processors.cache.CacheObjectContext; import org.apache.ignite.internal.processors.cache.GridCacheContext; +import org.apache.ignite.internal.processors.cache.GridCacheSharedContext; import org.apache.ignite.internal.processors.cache.IncompleteCacheObject; import org.apache.ignite.internal.processors.cache.IncompleteObject; import org.apache.ignite.internal.processors.cache.KeyCacheObject; @@ -36,6 +38,7 @@ import org.apache.ignite.internal.util.tostring.GridToStringExclude; import org.apache.ignite.internal.util.tostring.GridToStringInclude; import org.apache.ignite.internal.util.typedef.internal.S; import org.apache.ignite.internal.util.typedef.internal.U; +import org.jetbrains.annotations.Nullable; import static org.apache.ignite.internal.pagemem.PageIdUtils.itemId; import static org.apache.ignite.internal.pagemem.PageIdUtils.pageId; @@ -63,6 +66,10 @@ public class CacheDataRowAdapter implements CacheDataRow { @GridToStringInclude protected GridCacheVersion ver; + /** */ + @GridToStringInclude + protected int cacheId; + /** * @param link Link. */ @@ -92,14 +99,35 @@ public class CacheDataRowAdapter implements CacheDataRow { * @throws IgniteCheckedException If failed. */ public final void initFromLink(GridCacheContext<?, ?> cctx, RowData rowData) throws IgniteCheckedException { - assert cctx != null : "cctx"; + initFromLink(cctx, cctx.shared(), cctx.memoryPolicy().pageMemory(), rowData); + } + + /** + * Read row from data pages. + * Can be called with cctx == null, if cache instance is unknown, but its ID is stored in the data row. + * + * @param cctx Cctx. + * @param sharedCtx Shared context. + * @param pageMem Page memory. + * @param rowData Row data. + */ + public final void initFromLink( + @Nullable GridCacheContext<?, ?> cctx, + GridCacheSharedContext<?, ?> sharedCtx, + PageMemory pageMem, + RowData rowData) + throws IgniteCheckedException { assert link != 0 : "link"; assert key == null : "key"; - final CacheObjectContext coctx = cctx.cacheObjectContext(); - final PageMemory pageMem = cctx.memoryPolicy().pageMemory(); + CacheObjectContext coctx = null; + + if (cctx != null) { + cacheId = cctx.memoryPolicy().config().getPageEvictionMode() == DataPageEvictionMode.DISABLED ? + cctx.cacheId() : 0; // Force cacheId reading for evictable memory policies. - final int cacheId = cctx.cacheId(); + coctx = cctx.cacheObjectContext(); + } long nextLink = link; IncompleteObject<?> incomplete = null; @@ -126,7 +154,7 @@ public class CacheDataRowAdapter implements CacheDataRow { if (first) { if (nextLink == 0) { // Fast path for a single page row. - readFullRow(coctx, pageAddr + data.offset(), rowData); + readFullRow(sharedCtx, coctx, pageAddr + data.offset(), rowData); return; } @@ -141,7 +169,7 @@ public class CacheDataRowAdapter implements CacheDataRow { boolean keyOnly = rowData == RowData.KEY_ONLY; - incomplete = readFragment(coctx, buf, keyOnly, incomplete); + incomplete = readFragment(sharedCtx, coctx, buf, keyOnly, incomplete); if (keyOnly && key != null) return; @@ -168,11 +196,24 @@ public class CacheDataRowAdapter implements CacheDataRow { * @return Read object. */ private IncompleteObject<?> readFragment( + GridCacheSharedContext<?, ?> sharedCtx, CacheObjectContext coctx, ByteBuffer buf, boolean keyOnly, IncompleteObject<?> incomplete ) throws IgniteCheckedException { + if (cacheId == 0) { + incomplete = readIncompleteCacheId(buf, incomplete); + + if (cacheId == 0) + return incomplete; + + incomplete = null; + } + + if (coctx == null) + coctx = sharedCtx.cacheContext(cacheId).cacheObjectContext(); + // Read key. if (key == null) { incomplete = readIncompleteKey(coctx, buf, (IncompleteCacheObject)incomplete); @@ -215,9 +256,23 @@ public class CacheDataRowAdapter implements CacheDataRow { * @param rowData Required row data. * @throws IgniteCheckedException If failed. */ - private void readFullRow(CacheObjectContext coctx, long addr, RowData rowData) throws IgniteCheckedException { + private void readFullRow( + GridCacheSharedContext<?, ?> sharedCtx, + CacheObjectContext coctx, + long addr, + RowData rowData) + throws IgniteCheckedException { int off = 0; + if (cacheId == 0) { + cacheId = PageUtils.getInt(addr, off); + + off += 4; + } + + if (coctx == null) + coctx = sharedCtx.cacheContext(cacheId).cacheObjectContext(); + int len = PageUtils.getInt(addr, off); off += 4; @@ -255,6 +310,44 @@ public class CacheDataRowAdapter implements CacheDataRow { } /** + * @param buf Buffer. + * @param incomplete Incomplete. + */ + private IncompleteObject<?> readIncompleteCacheId( + ByteBuffer buf, + IncompleteObject<?> incomplete + ) { + if (incomplete == null) { + int remaining = buf.remaining(); + + if (remaining == 0) + return null; + + int size = 4; + + if (remaining >= size) { + cacheId = buf.getInt(); + + return null; + } + + incomplete = new IncompleteObject<>(new byte[size]); + } + + incomplete.readData(buf); + + if (incomplete.isReady()) { + final ByteBuffer timeBuf = ByteBuffer.wrap(incomplete.data()); + + timeBuf.order(buf.order()); + + cacheId = timeBuf.getInt(); + } + + return incomplete; + } + + /** * @param coctx Cache object context. * @param buf Buffer. * @param incomplete Incomplete object. @@ -313,7 +406,7 @@ public class CacheDataRowAdapter implements CacheDataRow { private IncompleteObject<?> readIncompleteExpireTime( ByteBuffer buf, IncompleteObject<?> incomplete - ) throws IgniteCheckedException { + ) { if (incomplete == null) { int remaining = buf.remaining(); @@ -414,13 +507,18 @@ public class CacheDataRowAdapter implements CacheDataRow { /** * @param key Key. */ - public void key(KeyCacheObject key) { + @Override public void key(KeyCacheObject key) { assert key != null; this.key = key; } /** {@inheritDoc} */ + @Override public int cacheId() { + return cacheId; + } + + /** {@inheritDoc} */ @Override public CacheObject value() { assert val != null : "Value is not ready: " + this; http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/IgniteCacheDatabaseSharedManager.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/IgniteCacheDatabaseSharedManager.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/IgniteCacheDatabaseSharedManager.java index d61130b..2d2295c 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/IgniteCacheDatabaseSharedManager.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/IgniteCacheDatabaseSharedManager.java @@ -29,6 +29,7 @@ import org.apache.ignite.IgniteLogger; import org.apache.ignite.MemoryMetrics; import org.apache.ignite.cluster.ClusterNode; import org.apache.ignite.configuration.IgniteConfiguration; +import org.apache.ignite.configuration.DataPageEvictionMode; import org.apache.ignite.configuration.MemoryConfiguration; import org.apache.ignite.configuration.MemoryPolicyConfiguration; import org.apache.ignite.internal.GridKernalContext; @@ -40,7 +41,13 @@ import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.pagemem.snapshot.StartFullSnapshotAckDiscoveryMessage; import org.apache.ignite.internal.pagemem.impl.PageMemoryNoStoreImpl; import org.apache.ignite.internal.processors.cache.GridCacheContext; +import org.apache.ignite.internal.processors.cache.GridCacheMapEntry; import org.apache.ignite.internal.processors.cache.GridCacheSharedManagerAdapter; +import org.apache.ignite.internal.processors.cache.database.evict.FairFifoPageEvictionTracker; +import org.apache.ignite.internal.processors.cache.database.evict.NoOpPageEvictionTracker; +import org.apache.ignite.internal.processors.cache.database.evict.PageEvictionTracker; +import org.apache.ignite.internal.processors.cache.database.evict.Random2LruPageEvictionTracker; +import org.apache.ignite.internal.processors.cache.database.evict.RandomLruPageEvictionTracker; import org.apache.ignite.internal.processors.cache.database.freelist.FreeList; import org.apache.ignite.internal.processors.cache.database.freelist.FreeListImpl; import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseList; @@ -102,7 +109,7 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap initPageMemoryPolicies(dbCfg); - startPageMemoryPools(); + startMemoryPolicies(); initPageMemoryDataStructures(dbCfg); } @@ -123,8 +130,8 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap FreeListImpl freeList = new FreeListImpl(0, cctx.igniteInstanceName(), - memPlc.pageMemory(), memMetrics, + memPlc, null, cctx.wal(), 0L, @@ -148,9 +155,12 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap /** * */ - private void startPageMemoryPools() { - for (MemoryPolicy memPlc : memPlcMap.values()) + private void startMemoryPolicies() { + for (MemoryPolicy memPlc : memPlcMap.values()) { memPlc.pageMemory().start(); + + memPlc.evictionTracker().start(); + } } /** @@ -205,9 +215,7 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap for (MemoryPolicyConfiguration memPlcCfg : memPlcsCfgs) { MemoryMetricsImpl memMetrics = new MemoryMetricsImpl(memPlcCfg); - PageMemory pageMem = initMemory(dbCfg, memPlcCfg, memMetrics); - - MemoryPolicy memPlc = new MemoryPolicy(pageMem, memMetrics, memPlcCfg); + MemoryPolicy memPlc = initMemory(dbCfg, memPlcCfg, memMetrics); memPlcMap.put(memPlcCfg.getName(), memPlc); @@ -222,7 +230,7 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap MemoryMetricsImpl sysMemMetrics = new MemoryMetricsImpl(sysPlcCfg); - memPlcMap.put(SYSTEM_MEMORY_POLICY_NAME, new MemoryPolicy(initMemory(dbCfg, sysPlcCfg, sysMemMetrics), sysMemMetrics, sysPlcCfg)); + memPlcMap.put(SYSTEM_MEMORY_POLICY_NAME, initMemory(dbCfg, sysPlcCfg, sysMemMetrics)); memMetricsMap.put(SYSTEM_MEMORY_POLICY_NAME, sysMemMetrics); } @@ -253,9 +261,7 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap * @param memMetrics MemoryMetrics instance. */ private MemoryPolicy createDefaultMemoryPolicy(MemoryConfiguration dbCfg, MemoryPolicyConfiguration memPlcCfg, MemoryMetricsImpl memMetrics) { - PageMemory pageMem = initMemory(dbCfg, memPlcCfg, memMetrics); - - return new MemoryPolicy(pageMem, memMetrics, memPlcCfg); + return initMemory(dbCfg, memPlcCfg, memMetrics); } /** @@ -285,6 +291,8 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap checkPolicyName(plcCfg.getName(), plcNames); checkPolicySize(plcCfg); + + checkPolicyEvictionProperties(plcCfg, dbCfg); } } @@ -307,6 +315,7 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap /** * @param plcCfg MemoryPolicyConfiguration to validate. + * @throws IgniteCheckedException If config is invalid. */ private static void checkPolicySize(MemoryPolicyConfiguration plcCfg) throws IgniteCheckedException { if (plcCfg.getSize() < MIN_PAGE_MEMORY_SIZE) @@ -314,8 +323,35 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap } /** + * @param plcCfg MemoryPolicyConfiguration to validate. + * @param dbCfg Memory configuration. + * @throws IgniteCheckedException If config is invalid. + */ + protected void checkPolicyEvictionProperties(MemoryPolicyConfiguration plcCfg, MemoryConfiguration dbCfg) + throws IgniteCheckedException { + if (plcCfg.getPageEvictionMode() == DataPageEvictionMode.DISABLED) + return; + + if (plcCfg.getEvictionThreshold() < 0.5 || plcCfg.getEvictionThreshold() > 0.999) { + throw new IgniteCheckedException("Page eviction threshold must be between 0.5 and 0.999: " + + plcCfg.getName()); + } + + if (plcCfg.getEmptyPagesPoolSize() <= 10) + throw new IgniteCheckedException("Evicted pages pool size should be greater than 10: " + plcCfg.getName()); + + long maxPoolSize = plcCfg.getSize() / dbCfg.getPageSize() / 10; + + if (plcCfg.getEmptyPagesPoolSize() >= maxPoolSize) { + throw new IgniteCheckedException("Evicted pages pool size should be lesser than " + maxPoolSize + + ": " + plcCfg.getName()); + } + } + + /** * @param plcName MemoryPolicy name to validate. * @param observedNames Names of MemoryPolicies observed before. + * @throws IgniteCheckedException If config is invalid. */ private static void checkPolicyName(String plcName, Set<String> observedNames) throws IgniteCheckedException { if (plcName == null || plcName.isEmpty()) @@ -406,8 +442,11 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap /** {@inheritDoc} */ @Override protected void stop0(boolean cancel) { if (memPlcMap != null) { - for (MemoryPolicy memPlc : memPlcMap.values()) + for (MemoryPolicy memPlc : memPlcMap.values()) { memPlc.pageMemory().stop(); + + memPlc.evictionTracker().stop(); + } } } @@ -512,12 +551,49 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap } /** + * See {@link GridCacheMapEntry#ensureFreeSpace()} + * + * @param memPlc Memory policy. + */ + public void ensureFreeSpace(MemoryPolicy memPlc) throws IgniteCheckedException { + if (memPlc == null) + return; + + MemoryPolicyConfiguration plcCfg = memPlc.config(); + + if (plcCfg.getPageEvictionMode() == DataPageEvictionMode.DISABLED) + return; + + long memorySize = plcCfg.getSize(); + + PageMemory pageMem = memPlc.pageMemory(); + + int sysPageSize = pageMem.systemPageSize(); + + FreeListImpl freeListImpl = freeListMap.get(plcCfg.getName()); + + for (;;) { + long allocatedPagesCnt = pageMem.loadedPages(); + + int emptyDataPagesCnt = freeListImpl.emptyDataPages(); + + boolean shouldEvict = allocatedPagesCnt > (memorySize / sysPageSize * plcCfg.getEvictionThreshold()) && + emptyDataPagesCnt < plcCfg.getEmptyPagesPoolSize(); + + if (shouldEvict) + memPlc.evictionTracker().evictDataPage(); + else + break; + } + } + + /** * @param dbCfg memory configuration with common parameters. * @param plc memory policy with PageMemory specific parameters. * @param memMetrics {@link MemoryMetrics} object to collect memory usage metrics. - * @return Page memory instance. + * @return Memory policy instance. */ - private PageMemory initMemory(MemoryConfiguration dbCfg, MemoryPolicyConfiguration plc, MemoryMetricsImpl memMetrics) { + private MemoryPolicy initMemory(MemoryConfiguration dbCfg, MemoryPolicyConfiguration plc, MemoryMetricsImpl memMetrics) { long[] sizes = calculateFragmentSizes( dbCfg.getConcurrencyLevel(), plc.getSize()); @@ -532,7 +608,27 @@ public class IgniteCacheDatabaseSharedManager extends GridCacheSharedManagerAdap true, sizes); - return createPageMemory(memProvider, dbCfg.getPageSize(), memMetrics); + PageMemory pageMem = createPageMemory(memProvider, dbCfg.getPageSize(), memMetrics); + + return new MemoryPolicy(pageMem, plc, memMetrics, createPageEvictionTracker(plc, pageMem)); + } + + /** + * @param plc Memory Policy Configuration. + * @param pageMem Page memory. + */ + private PageEvictionTracker createPageEvictionTracker(MemoryPolicyConfiguration plc, PageMemory pageMem) { + if (Boolean.getBoolean("override.fair.fifo.page.eviction.tracker")) + return new FairFifoPageEvictionTracker(pageMem, plc, cctx); + + switch (plc.getPageEvictionMode()) { + case RANDOM_LRU: + return new RandomLruPageEvictionTracker(pageMem, plc, cctx); + case RANDOM_2_LRU: + return new Random2LruPageEvictionTracker(pageMem, plc, cctx); + default: + return new NoOpPageEvictionTracker(); + } } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/MemoryPolicy.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/MemoryPolicy.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/MemoryPolicy.java index be23b38..90e5ac1 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/MemoryPolicy.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/MemoryPolicy.java @@ -19,6 +19,7 @@ package org.apache.ignite.internal.processors.cache.database; import org.apache.ignite.MemoryMetrics; import org.apache.ignite.configuration.MemoryPolicyConfiguration; import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.database.evict.PageEvictionTracker; /** * Memory policy provides access to objects configured with {@link MemoryPolicyConfiguration} configuration. @@ -33,15 +34,24 @@ public class MemoryPolicy { /** */ private final MemoryPolicyConfiguration cfg; + /** */ + private final PageEvictionTracker evictionTracker; + /** * @param pageMem PageMemory instance. * @param memMetrics MemoryMetrics instance. * @param cfg Configuration of given MemoryPolicy. + * @param evictionTracker Eviction tracker. */ - public MemoryPolicy(PageMemory pageMem, MemoryMetrics memMetrics, MemoryPolicyConfiguration cfg) { + public MemoryPolicy( + PageMemory pageMem, + MemoryPolicyConfiguration cfg, + MemoryMetrics memMetrics, + PageEvictionTracker evictionTracker) { this.pageMem = pageMem; this.memMetrics = memMetrics; this.cfg = cfg; + this.evictionTracker = evictionTracker; } /** @@ -64,4 +74,11 @@ public class MemoryPolicy { public MemoryMetrics memoryMetrics() { return memMetrics; } + + /** + * + */ + public PageEvictionTracker evictionTracker() { + return evictionTracker; + } } http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/FairFifoPageEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/FairFifoPageEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/FairFifoPageEvictionTracker.java new file mode 100644 index 0000000..8847013 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/FairFifoPageEvictionTracker.java @@ -0,0 +1,74 @@ +/* +* 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.database.evict; + +import java.util.LinkedList; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.IgniteException; +import org.apache.ignite.configuration.MemoryPolicyConfiguration; +import org.apache.ignite.internal.pagemem.PageIdUtils; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.GridCacheSharedContext; + +/** + * On-heap FIFO page eviction tracker. Only for test purposes. + */ +public class FairFifoPageEvictionTracker extends PageAbstractEvictionTracker { + /** Page usage deque. */ + private final LinkedList<Integer> pageUsageList = new LinkedList<>(); + + /** + * @param pageMem Page memory. + * @param plcCfg Memory policy configuration. + * @param sharedCtx Shared context. + */ + public FairFifoPageEvictionTracker(PageMemory pageMem, + MemoryPolicyConfiguration plcCfg, + GridCacheSharedContext sharedCtx) { + super(pageMem, plcCfg, sharedCtx); + } + + /** {@inheritDoc} */ + @Override public void start() throws IgniteException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void stop() throws IgniteException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public synchronized void touchPage(long pageId) throws IgniteCheckedException { + pageUsageList.addLast(PageIdUtils.pageIndex(pageId)); + } + + /** {@inheritDoc} */ + @Override public synchronized void evictDataPage() throws IgniteCheckedException { + evictDataPage(pageUsageList.pollFirst()); + } + + /** {@inheritDoc} */ + @Override public synchronized void forgetPage(long pageId) throws IgniteCheckedException { + // No-op. + } + + /** {@inheritDoc} */ + @Override protected synchronized boolean checkTouch(long pageId) { + return true; + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/NoOpPageEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/NoOpPageEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/NoOpPageEvictionTracker.java new file mode 100644 index 0000000..ba466bf --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/NoOpPageEvictionTracker.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.internal.processors.cache.database.evict; + +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.IgniteException; + +/** + * + */ +public class NoOpPageEvictionTracker implements PageEvictionTracker { + /** {@inheritDoc} */ + @Override public void start() throws IgniteException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void stop() throws IgniteException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void touchPage(long pageId) throws IgniteCheckedException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void evictDataPage() throws IgniteCheckedException { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void forgetPage(long pageId) throws IgniteCheckedException { + // No-op. + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageAbstractEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageAbstractEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageAbstractEvictionTracker.java new file mode 100644 index 0000000..88de545 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageAbstractEvictionTracker.java @@ -0,0 +1,243 @@ +/* +* 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.database.evict; + +import java.util.List; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.configuration.MemoryConfiguration; +import org.apache.ignite.configuration.MemoryPolicyConfiguration; +import org.apache.ignite.internal.pagemem.PageIdUtils; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.GridCacheContext; +import org.apache.ignite.internal.processors.cache.GridCacheEntryEx; +import org.apache.ignite.internal.processors.cache.GridCacheSharedContext; +import org.apache.ignite.internal.processors.cache.database.CacheDataRowAdapter; +import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO; +import org.apache.ignite.internal.processors.cache.version.GridCacheVersionManager; +import org.apache.ignite.internal.util.typedef.internal.U; + +/** + * + */ +public abstract class PageAbstractEvictionTracker implements PageEvictionTracker { + /** This number of least significant bits is dropped from timestamp. */ + private static final int COMPACT_TS_SHIFT = 8; // Enough if grid works for less than 17 years. + + /** Millis in day. */ + private final static int DAY = 24 * 60 * 60 * 1000; + + /** Page memory. */ + protected final PageMemory pageMem; + + /** Tracking array size. */ + final int trackingSize; + + /** Base compact timestamp. */ + private final long baseCompactTs; + + /** Shared context. */ + private final GridCacheSharedContext sharedCtx; + + /* TODO: IGNITE-4921: Will be removed after segments refactoring >>>> */ + protected final int segBits; + protected final int idxBits; + protected final int segMask; + protected final int idxMask; + protected final int segmentPageCount; + /* <<<< */ + + /** + * @param pageMem Page memory. + * @param plcCfg Memory policy configuration. + * @param sharedCtx Shared context. + */ + PageAbstractEvictionTracker( + PageMemory pageMem, + MemoryPolicyConfiguration plcCfg, + GridCacheSharedContext sharedCtx + ) { + this.pageMem = pageMem; + + this.sharedCtx = sharedCtx; + + MemoryConfiguration memCfg = sharedCtx.kernalContext().config().getMemoryConfiguration(); + + /* TODO: IGNITE-4921: Will be removed after segments refactoring >>>> */ + int concurrencyLevel = memCfg.getConcurrencyLevel(); + + if (concurrencyLevel < 1) + concurrencyLevel = Runtime.getRuntime().availableProcessors(); + + int pageSize = memCfg.getPageSize(); + + long segSize = plcCfg.getSize() / concurrencyLevel; + + if (segSize < 1024 * 1024) + segSize = 1024 * 1024; + + segmentPageCount = (int)(segSize / pageSize); + + segBits = Integer.SIZE - Integer.numberOfLeadingZeros(concurrencyLevel - 1); + + idxBits = PageIdUtils.PAGE_IDX_SIZE - segBits; + + segMask = ~(-1 << segBits); + + idxMask = ~(-1 << idxBits); + /* <<<< */ + + trackingSize = segmentPageCount << segBits; + + baseCompactTs = (U.currentTimeMillis() - DAY) >> COMPACT_TS_SHIFT; + // We subtract day to avoid fail in case of daylight shift or timezone change. + } + + /** + * @param pageIdx Page index. + * @return true if at least one data row has been evicted + * @throws IgniteCheckedException If failed. + */ + final boolean evictDataPage(int pageIdx) throws IgniteCheckedException { + long fakePageId = PageIdUtils.pageId(0, (byte)0, pageIdx); + + long page = pageMem.acquirePage(0, fakePageId); + + List<CacheDataRowAdapter> rowsToEvict; + + try { + long pageAddr = pageMem.readLockForce(0, fakePageId, page); + + try { + if (PageIO.getType(pageAddr) != PageIO.T_DATA) + return false; // Can't evict: page has been recycled into non-data page. + + DataPageIO io = DataPageIO.VERSIONS.forPage(pageAddr); + + long realPageId = PageIO.getPageId(pageAddr); + + if (!checkTouch(realPageId)) + return false; // Can't evict: another thread concurrently invoked forgetPage() + + rowsToEvict = io.forAllItems(pageAddr, new DataPageIO.CC<CacheDataRowAdapter>() { + @Override public CacheDataRowAdapter apply(long link) throws IgniteCheckedException { + CacheDataRowAdapter row = new CacheDataRowAdapter(link); + + row.initFromLink(null, sharedCtx, pageMem, CacheDataRowAdapter.RowData.KEY_ONLY); + + assert row.cacheId() != 0 : "Cache ID should be stored in rows of evictable cache"; + + return row; + } + }); + } + finally { + pageMem.readUnlock(0, fakePageId, page); + } + } + finally { + pageMem.releasePage(0, fakePageId, page); + } + + boolean evictionDone = false; + + for (CacheDataRowAdapter dataRow : rowsToEvict) { + GridCacheContext<?, ?> cacheCtx = sharedCtx.cacheContext(dataRow.cacheId()); + + if (!cacheCtx.userCache()) + continue; + + GridCacheEntryEx entryEx = cacheCtx.cache().entryEx(dataRow.key()); + + evictionDone |= entryEx.evictInternal(GridCacheVersionManager.EVICT_VER, null, true); + } + + return evictionDone; + } + + /** + * @param pageId Page ID. + * @return true if page was touched at least once. + */ + protected abstract boolean checkTouch(long pageId); + + /** + * @param epochMilli Time millis. + * @return Compact timestamp. Comparable and fits in 4 bytes. + */ + final long compactTimestamp(long epochMilli) { + return (epochMilli >> COMPACT_TS_SHIFT) - baseCompactTs; + } + + /** + * Resolves position in tracking array by page index. + * + * @param pageIdx Page index. + * @return Position of page in tracking array. + */ + int trackingIdx(int pageIdx) { + int inSegmentPageIdx = inSegmentPageIdx(pageIdx); + + assert inSegmentPageIdx < segmentPageCount : inSegmentPageIdx; + + int trackingIdx = segmentIdx(pageIdx) * segmentPageCount + inSegmentPageIdx; + + assert trackingIdx < trackingSize : trackingIdx; + + return trackingIdx; + } + + /** + * Reverse of {@link #trackingIdx(int)}. + * + * @param trackingIdx Tracking index. + * @return Page index. + */ + int pageIdx(int trackingIdx) { + assert trackingIdx < trackingSize; + + long res = 0; + + long segIdx = trackingIdx / segmentPageCount; + long pageIdx = trackingIdx % segmentPageCount; + + res = (res << segBits) | (segIdx & segMask); + res = (res << idxBits) | (pageIdx & idxMask); + + assert (res & (-1L << 32)) == 0 : res; + + return (int)res; + } + + /* TODO: IGNITE-4921: Will be removed after segments refactoring >>>> */ + /** + * @param pageIdx Page index. + * @return Number of segment. + */ + private int segmentIdx(int pageIdx) { + return (pageIdx >> idxBits) & segMask; + } + + /** + * @param pageIdx Page index. + * @return Number of page inside segment. + */ + private int inSegmentPageIdx(int pageIdx) { + return pageIdx & idxMask; + } + /* <<<< */ +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageEvictionTracker.java new file mode 100644 index 0000000..b13dcf8 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/PageEvictionTracker.java @@ -0,0 +1,52 @@ +/* +* 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.database.evict; + +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.lifecycle.LifecycleAware; + +/** + * Entry point for per-page eviction. Accepts information about touching data pages, + * capable of evicting "the least needed" page (according to implemented eviction algorithm). + */ +public interface PageEvictionTracker extends LifecycleAware { + /** + * Call this method when data page is accessed. + * + * @param pageId Page id. + * @throws IgniteCheckedException In case of page memory error. + */ + public void touchPage(long pageId) throws IgniteCheckedException; + + /** + * Evicts one data page. + * In most cases, all entries will be removed from the page. + * Method guarantees removing at least one entry from "evicted" data page. Removing all entries may be + * not possible, as some of them can be used by active transactions. + * + * @throws IgniteCheckedException In case of page memory error. + */ + public void evictDataPage() throws IgniteCheckedException; + + /** + * Call this method when last entry is removed from data page. + * + * @param pageId Page id. + * @throws IgniteCheckedException In case of page memory error. + */ + public void forgetPage(long pageId) throws IgniteCheckedException; +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/Random2LruPageEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/Random2LruPageEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/Random2LruPageEvictionTracker.java new file mode 100644 index 0000000..f0ad813 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/Random2LruPageEvictionTracker.java @@ -0,0 +1,180 @@ +/* +* 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.database.evict; + +import java.util.concurrent.ThreadLocalRandom; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.IgniteException; +import org.apache.ignite.IgniteLogger; +import org.apache.ignite.configuration.MemoryConfiguration; +import org.apache.ignite.configuration.MemoryPolicyConfiguration; +import org.apache.ignite.internal.pagemem.PageIdUtils; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.GridCacheSharedContext; +import org.apache.ignite.internal.util.GridUnsafe; +import org.apache.ignite.internal.util.typedef.internal.LT; +import org.apache.ignite.internal.util.typedef.internal.U; + +/** + * + */ +public class Random2LruPageEvictionTracker extends PageAbstractEvictionTracker { + /** Evict attempts limit. */ + private static final int EVICT_ATTEMPTS_LIMIT = 30; + + /** LRU Sample size. */ + private static final int SAMPLE_SIZE = 5; + + /** Maximum sample search spin count */ + private static final int SAMPLE_SPIN_LIMIT = SAMPLE_SIZE * 1000; + + /** Logger. */ + private final IgniteLogger log; + + /** Tracking array ptr. */ + private long trackingArrPtr; + + /** + * @param pageMem Page memory. + * @param plcCfg Policy config. + * @param sharedCtx Shared context. + */ + public Random2LruPageEvictionTracker( + PageMemory pageMem, + MemoryPolicyConfiguration plcCfg, + GridCacheSharedContext<?, ?> sharedCtx + ) { + super(pageMem, plcCfg, sharedCtx); + + MemoryConfiguration memCfg = sharedCtx.kernalContext().config().getMemoryConfiguration(); + + assert plcCfg.getSize() / memCfg.getPageSize() < Integer.MAX_VALUE; + + log = sharedCtx.logger(getClass()); + } + + /** {@inheritDoc} */ + @Override public void start() throws IgniteException { + trackingArrPtr = GridUnsafe.allocateMemory(trackingSize * 8); + + GridUnsafe.setMemory(trackingArrPtr, trackingSize * 8, (byte)0); + } + + /** {@inheritDoc} */ + @Override public void stop() throws IgniteException { + GridUnsafe.freeMemory(trackingArrPtr); + } + + /** {@inheritDoc} */ + @Override public void touchPage(long pageId) throws IgniteCheckedException { + int pageIdx = PageIdUtils.pageIndex(pageId); + + long latestTs = compactTimestamp(U.currentTimeMillis()); + + assert latestTs >= 0 && latestTs < Integer.MAX_VALUE; + + boolean success; + + do { + int trackingIdx = trackingIdx(pageIdx); + + int firstTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 8); + + int secondTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 8 + 4); + + if (firstTs <= secondTs) + success = GridUnsafe.compareAndSwapInt(null, trackingArrPtr + trackingIdx * 8, firstTs, (int)latestTs); + else { + success = GridUnsafe.compareAndSwapInt( + null, trackingArrPtr + trackingIdx * 8 + 4, secondTs, (int)latestTs); + } + } while (!success); + } + + /** {@inheritDoc} */ + @Override public void evictDataPage() throws IgniteCheckedException { + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + + int evictAttemptsCnt = 0; + + while (evictAttemptsCnt < EVICT_ATTEMPTS_LIMIT) { + int lruTrackingIdx = -1; + + int lruCompactTs = Integer.MAX_VALUE; + + int dataPagesCnt = 0; + + int sampleSpinCnt = 0; + + while (dataPagesCnt < SAMPLE_SIZE) { + int trackingIdx = rnd.nextInt(trackingSize); + + int firstTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 8); + + int secondTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 8 + 4); + + int minTs = Math.min(firstTs, secondTs); + + int maxTs = Math.max(firstTs, secondTs); + + if (maxTs != 0) { + // We chose data page with at least one touch. + if (minTs < lruCompactTs) { + lruTrackingIdx = trackingIdx; + + lruCompactTs = minTs; + } + + dataPagesCnt++; + } + + sampleSpinCnt++; + + if (sampleSpinCnt > SAMPLE_SPIN_LIMIT) { + LT.warn(log, "Too many attempts to choose data page: " + SAMPLE_SPIN_LIMIT); + + return; + } + } + + if (evictDataPage(pageIdx(lruTrackingIdx))) + return; + + evictAttemptsCnt++; + } + + LT.warn(log, "Too many failed attempts to evict page: " + EVICT_ATTEMPTS_LIMIT); + } + + /** {@inheritDoc} */ + @Override protected boolean checkTouch(long pageId) { + int trackingIdx = trackingIdx(PageIdUtils.pageIndex(pageId)); + + int firstTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 8); + + return firstTs != 0; + } + + /** {@inheritDoc} */ + @Override public void forgetPage(long pageId) { + int pageIdx = PageIdUtils.pageIndex(pageId); + + int trackingIdx = trackingIdx(pageIdx); + + GridUnsafe.putLongVolatile(null, trackingArrPtr + trackingIdx * 8, 0L); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/RandomLruPageEvictionTracker.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/RandomLruPageEvictionTracker.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/RandomLruPageEvictionTracker.java new file mode 100644 index 0000000..8818b1c --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/evict/RandomLruPageEvictionTracker.java @@ -0,0 +1,157 @@ +/* +* 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.database.evict; + +import java.util.concurrent.ThreadLocalRandom; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.IgniteException; +import org.apache.ignite.IgniteLogger; +import org.apache.ignite.configuration.MemoryConfiguration; +import org.apache.ignite.configuration.MemoryPolicyConfiguration; +import org.apache.ignite.internal.pagemem.PageIdUtils; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.GridCacheSharedContext; +import org.apache.ignite.internal.util.GridUnsafe; +import org.apache.ignite.internal.util.typedef.internal.LT; +import org.apache.ignite.internal.util.typedef.internal.U; + +/** + * + */ +public class RandomLruPageEvictionTracker extends PageAbstractEvictionTracker { + /** Evict attempts limit. */ + private static final int EVICT_ATTEMPTS_LIMIT = 30; + + /** LRU Sample size. */ + private static final int SAMPLE_SIZE = 5; + + /** Maximum sample search spin count */ + private static final int SAMPLE_SPIN_LIMIT = SAMPLE_SIZE * 1000; + + /** Logger. */ + private final IgniteLogger log; + + /** Tracking array ptr. */ + private long trackingArrPtr; + + /** + * @param pageMem Page memory. + * @param plcCfg Policy config. + * @param sharedCtx Shared context. + */ + public RandomLruPageEvictionTracker( + PageMemory pageMem, + MemoryPolicyConfiguration plcCfg, + GridCacheSharedContext<?, ?> sharedCtx + ) { + super(pageMem, plcCfg, sharedCtx); + + MemoryConfiguration memCfg = sharedCtx.kernalContext().config().getMemoryConfiguration(); + + assert plcCfg.getSize() / memCfg.getPageSize() < Integer.MAX_VALUE; + + log = sharedCtx.logger(getClass()); + } + + /** {@inheritDoc} */ + @Override public void start() throws IgniteException { + trackingArrPtr = GridUnsafe.allocateMemory(trackingSize * 4); + + GridUnsafe.setMemory(trackingArrPtr, trackingSize * 4, (byte)0); + } + + /** {@inheritDoc} */ + @Override public void stop() throws IgniteException { + GridUnsafe.freeMemory(trackingArrPtr); + } + + /** {@inheritDoc} */ + @Override public void touchPage(long pageId) throws IgniteCheckedException { + int pageIdx = PageIdUtils.pageIndex(pageId); + + long res = compactTimestamp(U.currentTimeMillis()); + + assert res >= 0 && res < Integer.MAX_VALUE; + + GridUnsafe.putIntVolatile(null, trackingArrPtr + trackingIdx(pageIdx) * 4, (int)res); + } + + /** {@inheritDoc} */ + @Override public void evictDataPage() throws IgniteCheckedException { + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + + int evictAttemptsCnt = 0; + + while (evictAttemptsCnt < EVICT_ATTEMPTS_LIMIT) { + int lruTrackingIdx = -1; + + int lruCompactTs = Integer.MAX_VALUE; + + int dataPagesCnt = 0; + + int sampleSpinCnt = 0; + + while (dataPagesCnt < SAMPLE_SIZE) { + int sampleTrackingIdx = rnd.nextInt(trackingSize); + + int compactTs = GridUnsafe.getIntVolatile(null, trackingArrPtr + sampleTrackingIdx * 4); + + if (compactTs != 0) { + // We chose data page with at least one touch. + if (compactTs < lruCompactTs) { + lruTrackingIdx = sampleTrackingIdx; + + lruCompactTs = compactTs; + } + + dataPagesCnt++; + } + + sampleSpinCnt++; + + if (sampleSpinCnt > SAMPLE_SPIN_LIMIT) { + LT.warn(log, "Too many attempts to choose data page: " + SAMPLE_SPIN_LIMIT); + + return; + } + } + + if (evictDataPage(pageIdx(lruTrackingIdx))) + return; + + evictAttemptsCnt++; + } + + LT.warn(log, "Too many failed attempts to evict page: " + EVICT_ATTEMPTS_LIMIT); + } + + /** {@inheritDoc} */ + @Override protected boolean checkTouch(long pageId) { + int trackingIdx = trackingIdx(PageIdUtils.pageIndex(pageId)); + + int ts = GridUnsafe.getIntVolatile(null, trackingArrPtr + trackingIdx * 4); + + return ts != 0; + } + + /** {@inheritDoc} */ + @Override public void forgetPage(long pageId) { + int pageIdx = PageIdUtils.pageIndex(pageId); + + GridUnsafe.putIntVolatile(null, trackingArrPtr + trackingIdx(pageIdx) * 4, 0); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/ff5b3e16/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java index d433172..cb68f7b 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeListImpl.java @@ -22,7 +22,6 @@ import org.apache.ignite.IgniteCheckedException; import org.apache.ignite.IgniteLogger; import org.apache.ignite.internal.pagemem.PageIdAllocator; import org.apache.ignite.internal.pagemem.PageIdUtils; -import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.pagemem.PageUtils; import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager; import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageInsertFragmentRecord; @@ -31,6 +30,8 @@ import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageRemoveRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageUpdateRecord; import org.apache.ignite.internal.processors.cache.database.CacheDataRow; import org.apache.ignite.internal.processors.cache.database.MemoryMetricsImpl; +import org.apache.ignite.internal.processors.cache.database.MemoryPolicy; +import org.apache.ignite.internal.processors.cache.database.evict.PageEvictionTracker; import org.apache.ignite.internal.processors.cache.database.tree.io.CacheVersionIO; import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO; import org.apache.ignite.internal.processors.cache.database.tree.io.DataPagePayload; @@ -71,17 +72,22 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { private final int MIN_SIZE_FOR_DATA_PAGE; /** */ + private final int emptyDataPagesBucket; + + /** */ private final PageHandler<CacheDataRow, Boolean> updateRow = new UpdateRowHandler(); /** */ private final MemoryMetricsImpl memMetrics; + /** */ + private final PageEvictionTracker evictionTracker; + /** * */ private final class UpdateRowHandler extends PageHandler<CacheDataRow, Boolean> { - @Override - public Boolean run( + @Override public Boolean run( int cacheId, long pageId, long page, @@ -97,6 +103,8 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { boolean updated = io.updateRow(pageAddr, itemId, pageSize(), null, row, rowSize); + evictionTracker.touchPage(pageId); + if (updated && needWalDeltaRecord(pageId, page, walPlc)) { // TODO This record must contain only a reference to a logical WAL record with the actual data. byte[] payload = new byte[rowSize]; @@ -125,8 +133,7 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { * */ private final class WriteRowHandler extends PageHandler<CacheDataRow, Integer> { - @Override - public Integer run( + @Override public Integer run( int cacheId, long pageId, long page, @@ -156,6 +163,9 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { put(null, pageId, page, pageAddr, bucket); } + if (written == rowSize) + evictionTracker.touchPage(pageId); + // Avoid boxing with garbage generation for usual case. return written == rowSize ? COMPLETE : written; } @@ -287,6 +297,9 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { } else put(null, pageId, page, pageAddr, newBucket); + + if (io.isEmpty(pageAddr)) + evictionTracker.forgetPage(pageId); } // For common case boxed 0L will be cached inside of Long, so no garbage will be produced. @@ -297,8 +310,8 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { /** * @param cacheId Cache ID. * @param name Name (for debug purpose). - * @param pageMem Page memory. * @param memMetrics Memory metrics. + * @param memPlc Memory policy. * @param reuseList Reuse list or {@code null} if this free list will be a reuse list for itself. * @param wal Write ahead log manager. * @param metaPageId Metadata page ID. @@ -308,13 +321,14 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { public FreeListImpl( int cacheId, String name, - PageMemory pageMem, MemoryMetricsImpl memMetrics, + MemoryPolicy memPlc, ReuseList reuseList, IgniteWriteAheadLogManager wal, long metaPageId, boolean initNew) throws IgniteCheckedException { - super(cacheId, name, pageMem, BUCKETS, wal, metaPageId); + super(cacheId, name, memPlc.pageMemory(), BUCKETS, wal, metaPageId); + this.evictionTracker = memPlc.evictionTracker(); this.reuseList = reuseList == null ? this : reuseList; int pageSize = pageMem.pageSize(); @@ -337,6 +351,8 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { this.memMetrics = memMetrics; + emptyDataPagesBucket = bucket(MIN_SIZE_FOR_DATA_PAGE, false); + init(metaPageId, initNew); } @@ -446,25 +462,26 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { int freeSpace = Math.min(MIN_SIZE_FOR_DATA_PAGE, rowSize - written); - int bucket = bucket(freeSpace, false); + long pageId = 0L; + + if (freeSpace == MIN_SIZE_FOR_DATA_PAGE) + pageId = takeEmptyPage(emptyDataPagesBucket, DataPageIO.VERSIONS); - long pageId = 0; boolean reuseBucket = false; // TODO: properly handle reuse bucket. - for (int b = bucket + 1; b < BUCKETS - 1; b++) { - pageId = takeEmptyPage(b, DataPageIO.VERSIONS); + if (pageId == 0L) { + for (int b = bucket(freeSpace, false) + 1; b < BUCKETS - 1; b++) { + pageId = takeEmptyPage(b, DataPageIO.VERSIONS); - if (pageId != 0L) { - reuseBucket = isReuseBucket(b); + if (pageId != 0L) { + reuseBucket = isReuseBucket(b); - break; + break; + } } } - if (pageId == 0L) - pageId = takeEmptyPage(bucket, DataPageIO.VERSIONS); - boolean allocated = pageId == 0L; if (allocated) @@ -531,6 +548,13 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { return bucket == REUSE_BUCKET; } + /** + * @return Number of empty data pages in free list. + */ + public int emptyDataPages() { + return bucketsSize[emptyDataPagesBucket].intValue(); + } + /** {@inheritDoc} */ @Override public void addForRecycle(ReuseBag bag) throws IgniteCheckedException { assert reuseList == this: "not allowed to be a reuse list"; @@ -561,7 +585,7 @@ public class FreeListImpl extends PagesList implements FreeList, ReuseList { int keyLen = row.key().valueBytesLength(null); int valLen = row.value().valueBytesLength(null); - return keyLen + valLen + CacheVersionIO.size(row.version(), false) + 8; + return keyLen + valLen + CacheVersionIO.size(row.version(), false) + 8 + (row.cacheId() == 0 ? 0 : 4); } /** {@inheritDoc} */
