Repository: ignite Updated Branches: refs/heads/master 24cee46b1 -> 0bdfa20cd
IGNITE-4958 Make data pages recyclable into index/meta/etc pages and vice versa - Fixes #3780. Signed-off-by: Ivan Rakov <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/0bdfa20c Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/0bdfa20c Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/0bdfa20c Branch: refs/heads/master Commit: 0bdfa20cd393ea896a59f0fbd9270f8b8128dae6 Parents: 24cee46 Author: Dmitriy Sorokin <[email protected]> Authored: Thu May 24 01:56:01 2018 +0300 Committer: Ivan Rakov <[email protected]> Committed: Thu May 24 01:56:01 2018 +0300 ---------------------------------------------------------------------- .../ignite/internal/pagemem/PageIdUtils.java | 5 +- .../internal/pagemem/wal/record/WALRecord.java | 5 +- .../wal/record/delta/RotatedIdPartRecord.java | 66 ++++++++ .../cache/persistence/DataStructure.java | 34 ++++- .../persistence/freelist/AbstractFreeList.java | 104 ++++++++----- .../cache/persistence/freelist/PagesList.java | 60 ++++++-- .../cache/persistence/tree/BPlusTree.java | 29 +--- .../cache/persistence/tree/io/PageIO.java | 35 ++++- .../tree/reuse/LongListReuseBag.java | 46 ++++++ .../persistence/wal/record/RecordTypes.java | 1 + .../wal/serializer/RecordDataV1Serializer.java | 24 +++ .../pagemem/impl/PageIdUtilsSelfTest.java | 3 +- ...ageEvictionPagesRecyclingAndReusingTest.java | 153 +++++++++++++++++++ .../pagemem/FillFactorMetricTest.java | 5 +- .../IgniteCacheEvictionSelfTestSuite.java | 3 + 15 files changed, 479 insertions(+), 94 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageIdUtils.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageIdUtils.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageIdUtils.java index 2754d79..1335269 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageIdUtils.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/PageIdUtils.java @@ -184,7 +184,10 @@ public final class PageIdUtils { * @return New page ID. */ public static long rotatePageId(long pageId) { - long updatedRotationId = (pageId >> PAGE_IDX_SIZE + PART_ID_SIZE + FLAG_SIZE) + 1; + long updatedRotationId = (pageId >>> PAGE_IDX_SIZE + PART_ID_SIZE + FLAG_SIZE) + 1; + + if (updatedRotationId > MAX_ITEMID_NUM) + updatedRotationId = 1; // We always want non-zero updatedRotationId return (pageId & PAGE_ID_MASK) | (updatedRotationId << (PAGE_IDX_SIZE + PART_ID_SIZE + FLAG_SIZE)); http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/WALRecord.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/WALRecord.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/WALRecord.java index 4fae179..52bd034 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/WALRecord.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/WALRecord.java @@ -175,7 +175,10 @@ public abstract class WALRecord { EXCHANGE, /** Baseline topology record. */ - BASELINE_TOP_RECORD; + BASELINE_TOP_RECORD, + + /** Rotated id part record. */ + ROTATED_ID_PART_RECORD; /** */ private static final RecordType[] VALS = RecordType.values(); http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/delta/RotatedIdPartRecord.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/delta/RotatedIdPartRecord.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/delta/RotatedIdPartRecord.java new file mode 100644 index 0000000..24a45c6 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/wal/record/delta/RotatedIdPartRecord.java @@ -0,0 +1,66 @@ +/* + * 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.pagemem.wal.record.delta; + +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO; +import org.apache.ignite.internal.util.typedef.internal.S; + +/** + * Rotated (when page has been recycled) id part delta record. + */ +public class RotatedIdPartRecord extends PageDeltaRecord { + /** Rotated id part. */ + private byte rotatedIdPart; + + /** + * @param grpId Group id. + * @param pageId Page id. + * @param rotatedIdPart Rotated id part. + */ + public RotatedIdPartRecord(int grpId, long pageId, int rotatedIdPart) { + super(grpId, pageId); + + assert rotatedIdPart >= 0 && rotatedIdPart <= 0xFF; + + this.rotatedIdPart = (byte) rotatedIdPart; + } + + /** {@inheritDoc} */ + @Override public void applyDelta(PageMemory pageMem, long pageAddr) throws IgniteCheckedException { + PageIO.setRotatedIdPart(pageAddr, rotatedIdPart); + } + + /** {@inheritDoc} */ + @Override public RecordType type() { + return RecordType.ROTATED_ID_PART_RECORD; + } + + /** + * @return Rotated id part. + */ + public byte rotatedIdPart() { + return rotatedIdPart; + } + + /** {@inheritDoc} */ + @Override public String toString() { + return S.toString(RotatedIdPartRecord.class, this, "super", super.toString()); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/DataStructure.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/DataStructure.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/DataStructure.java index 663a139..0177407 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/DataStructure.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/DataStructure.java @@ -25,6 +25,7 @@ import org.apache.ignite.internal.pagemem.PageIdUtils; import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager; import org.apache.ignite.internal.pagemem.wal.record.delta.RecycleRecord; +import org.apache.ignite.internal.pagemem.wal.record.delta.RotatedIdPartRecord; import org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseBag; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseList; @@ -36,6 +37,7 @@ import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_DATA; import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_IDX; import static org.apache.ignite.internal.pagemem.PageIdAllocator.INDEX_PARTITION; import static org.apache.ignite.internal.pagemem.PageIdAllocator.MAX_PARTITION_ID; +import static org.apache.ignite.internal.pagemem.PageIdUtils.MAX_ITEMID_NUM; /** * Base class for all the data structures based on {@link PageMemory}. @@ -346,7 +348,7 @@ public abstract class DataStructure implements PageLockListener { * @param page Page pointer. * @param pageAddr Page address. * @param walPlc Full page WAL record policy. - * @return Rotated page ID. + * @return Recycled page ID. * @throws IgniteCheckedException If failed. */ protected final long recyclePage( @@ -354,14 +356,34 @@ public abstract class DataStructure implements PageLockListener { long page, long pageAddr, Boolean walPlc) throws IgniteCheckedException { - long rotated = PageIdUtils.rotatePageId(pageId); + long recycled = 0; - PageIO.setPageId(pageAddr, rotated); + boolean needWalDeltaRecord = needWalDeltaRecord(pageId, page, walPlc); - if (needWalDeltaRecord(pageId, page, walPlc)) - wal.log(new RecycleRecord(grpId, pageId, rotated)); + if (PageIdUtils.tag(pageId) == FLAG_DATA) { + int rotatedIdPart = PageIO.getRotatedIdPart(pageAddr); - return rotated; + if (rotatedIdPart != 0) { + recycled = PageIdUtils.link(pageId, rotatedIdPart > MAX_ITEMID_NUM ? 1 : rotatedIdPart); + + PageIO.setRotatedIdPart(pageAddr, 0); + + if (needWalDeltaRecord) + wal.log(new RotatedIdPartRecord(grpId, pageId, 0)); + } + } + + if (recycled == 0) + recycled = PageIdUtils.rotatePageId(pageId); + + assert PageIdUtils.itemId(recycled) > 0 && PageIdUtils.itemId(recycled) <= MAX_ITEMID_NUM : U.hexLong(recycled); + + PageIO.setPageId(pageAddr, recycled); + + if (needWalDeltaRecord) + wal.log(new RecycleRecord(grpId, pageId, recycled)); + + return recycled; } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/AbstractFreeList.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/AbstractFreeList.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/AbstractFreeList.java index 5f5948d..c1a48bb 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/AbstractFreeList.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/AbstractFreeList.java @@ -28,18 +28,18 @@ import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageInsertFragmen import org.apache.ignite.internal.pagemem.wal.record.delta.DataPageInsertRecord; 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.persistence.DataRegionMetricsImpl; import org.apache.ignite.internal.processors.cache.persistence.DataRegion; +import org.apache.ignite.internal.processors.cache.persistence.DataRegionMetricsImpl; import org.apache.ignite.internal.processors.cache.persistence.Storable; import org.apache.ignite.internal.processors.cache.persistence.evict.PageEvictionTracker; import org.apache.ignite.internal.processors.cache.persistence.tree.io.AbstractDataPageIO; import org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPagePayload; import org.apache.ignite.internal.processors.cache.persistence.tree.io.IOVersions; import org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO; +import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.LongListReuseBag; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseBag; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseList; import org.apache.ignite.internal.processors.cache.persistence.tree.util.PageHandler; -import org.apache.ignite.internal.util.typedef.T2; import org.apache.ignite.internal.util.typedef.internal.U; /** @@ -76,9 +76,6 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp private final int MIN_SIZE_FOR_DATA_PAGE; /** */ - private final int emptyDataPagesBucket; - - /** */ private final PageHandler<T, Boolean> updateRow = new UpdateRowHandler(); /** */ @@ -256,12 +253,12 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp } /** */ - private final PageHandler<Void, Long> rmvRow; + private final PageHandler<ReuseBag, Long> rmvRow; /** * */ - private final class RemoveRowHandler extends PageHandler<Void, Long> { + private final class RemoveRowHandler extends PageHandler<ReuseBag, Long> { /** Indicates whether partition ID should be masked from page ID. */ private final boolean maskPartId; @@ -277,7 +274,7 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp long pageAddr, PageIO iox, Boolean walPlc, - Void ignored, + ReuseBag reuseBag, int itemId) throws IgniteCheckedException { AbstractDataPageIO<T> io = (AbstractDataPageIO<T>)iox; @@ -296,21 +293,27 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp if (newFreeSpace > MIN_PAGE_FREE_SPACE) { int newBucket = bucket(newFreeSpace, false); - if (oldFreeSpace > MIN_PAGE_FREE_SPACE) { + boolean putIsNeeded = oldFreeSpace <= MIN_PAGE_FREE_SPACE; + + if (!putIsNeeded) { int oldBucket = bucket(oldFreeSpace, false); if (oldBucket != newBucket) { // It is possible that page was concurrently taken for put, in this case put will handle bucket change. pageId = maskPartId ? PageIdUtils.maskPartitionId(pageId) : pageId; - if (removeDataPage(pageId, page, pageAddr, io, oldBucket)) - put(null, pageId, page, pageAddr, newBucket); + + putIsNeeded = removeDataPage(pageId, page, pageAddr, io, oldBucket); } } - else - put(null, pageId, page, pageAddr, newBucket); - if (io.isEmpty(pageAddr)) + if (io.isEmpty(pageAddr)) { evictionTracker.forgetPage(pageId); + + if (putIsNeeded) + reuseBag.addFreePage(recyclePage(pageId, page, pageAddr, null)); + } + else if (putIsNeeded) + put(null, pageId, page, pageAddr, newBucket); } // For common case boxed 0L will be cached inside of Long, so no garbage will be produced. @@ -365,8 +368,6 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp this.memMetrics = memMetrics; - emptyDataPagesBucket = bucket(MIN_SIZE_FOR_DATA_PAGE, false); - init(metaPageId, initNew); } @@ -473,44 +474,63 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp if (written != 0) memMetrics.incrementLargeEntriesPages(); - int freeSpace = Math.min(MIN_SIZE_FOR_DATA_PAGE, rowSize - written); + int remaining = rowSize - written; long pageId = 0L; - if (freeSpace == MIN_SIZE_FOR_DATA_PAGE) - pageId = takeEmptyPage(emptyDataPagesBucket, ioVersions()); - - boolean reuseBucket = false; - - // TODO: properly handle reuse bucket. - if (pageId == 0L) { - for (int b = bucket(freeSpace, false) + 1; b < BUCKETS - 1; b++) { - pageId = takeEmptyPage(b, ioVersions()); - - if (pageId != 0L) { - reuseBucket = isReuseBucket(b); + for (int b = remaining < MIN_SIZE_FOR_DATA_PAGE ? bucket(remaining, false) + 1 : REUSE_BUCKET; b < BUCKETS; b++) { + pageId = takeEmptyPage(b, ioVersions()); - break; - } - } + if (pageId != 0L) + break; } - boolean allocated = pageId == 0L; + AbstractDataPageIO<T> initIo = null; - if (allocated) + if (pageId == 0L) { pageId = allocateDataPage(row.partition()); + + initIo = ioVersions().latest(); + } + else if (PageIdUtils.tag(pageId) != PageIdAllocator.FLAG_DATA) + pageId = initReusedPage(pageId, row.partition()); else pageId = PageIdUtils.changePartitionId(pageId, (row.partition())); - AbstractDataPageIO<T> init = reuseBucket || allocated ? ioVersions().latest() : null; - - written = write(pageId, writeRow, init, row, written, FAIL_I); + written = write(pageId, writeRow, initIo, row, written, FAIL_I); assert written != FAIL_I; // We can't fail here. } while (written != COMPLETE); } + /** + * @param reusedPageId Reused page id. + * @param partId Partition id. + * @return Prepared page id. + * + * @see PagesList#initReusedPage(long, long, long, int, byte, PageIO) + */ + private long initReusedPage(long reusedPageId, int partId) throws IgniteCheckedException { + long reusedPage = acquirePage(reusedPageId); + try { + long reusedPageAddr = writeLock(reusedPageId, reusedPage); + + assert reusedPageAddr != 0; + + try { + return initReusedPage(reusedPageId, reusedPage, reusedPageAddr, + partId, PageIdAllocator.FLAG_DATA, ioVersions().latest()); + } + finally { + writeUnlock(reusedPageId, reusedPage, reusedPageAddr, true); + } + } + finally { + releasePage(reusedPageId, reusedPage); + } + } + /** {@inheritDoc} */ @Override public boolean updateDataRow(long link, T row) throws IgniteCheckedException { assert link != 0; @@ -532,7 +552,9 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp long pageId = PageIdUtils.pageId(link); int itemId = PageIdUtils.itemId(link); - long nextLink = write(pageId, rmvRow, itemId, FAIL_L); + ReuseBag bag = new LongListReuseBag(); + + long nextLink = write(pageId, rmvRow, bag, itemId, FAIL_L); assert nextLink != FAIL_L; // Can't fail here. @@ -542,10 +564,12 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp itemId = PageIdUtils.itemId(nextLink); pageId = PageIdUtils.pageId(nextLink); - nextLink = write(pageId, rmvRow, itemId, FAIL_L); + nextLink = write(pageId, rmvRow, bag, itemId, FAIL_L); assert nextLink != FAIL_L; // Can't fail here. } + + reuseList.addForRecycle(bag); } /** {@inheritDoc} */ @@ -567,7 +591,7 @@ public abstract class AbstractFreeList<T extends Storable> extends PagesList imp * @return Number of empty data pages in free list. */ public int emptyDataPages() { - return bucketsSize[emptyDataPagesBucket].intValue(); + return bucketsSize[REUSE_BUCKET].intValue(); } /** {@inheritDoc} */ http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/PagesList.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/PagesList.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/PagesList.java index ed77674..905507e 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/PagesList.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/freelist/PagesList.java @@ -35,6 +35,7 @@ import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListInitNewPageR import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListRemovePageRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListSetNextRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.PagesListSetPreviousRecord; +import org.apache.ignite.internal.pagemem.wal.record.delta.RotatedIdPartRecord; import org.apache.ignite.internal.processors.cache.persistence.DataStructure; import org.apache.ignite.internal.processors.cache.persistence.freelist.io.PagesListMetaIO; import org.apache.ignite.internal.processors.cache.persistence.freelist.io.PagesListNodeIO; @@ -55,6 +56,7 @@ import static java.lang.Boolean.FALSE; import static java.lang.Boolean.TRUE; import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_DATA; import static org.apache.ignite.internal.pagemem.PageIdAllocator.FLAG_IDX; +import static org.apache.ignite.internal.pagemem.PageIdUtils.MAX_ITEMID_NUM; import static org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO.getPageId; /** @@ -855,6 +857,8 @@ public abstract class PagesList extends DataStructure { try { while ((nextId = bag.pollFreePage()) != 0L) { + assert PageIdUtils.itemId(nextId) > 0 && PageIdUtils.itemId(nextId) <= MAX_ITEMID_NUM : U.hexLong(nextId); + int idx = io.addPage(prevAddr, nextId, pageSize()); if (idx == -1) { // Attempt to add page failed: the node page is full. @@ -1070,6 +1074,10 @@ public abstract class PagesList extends DataStructure { dirty = true; + assert !isReuseBucket(bucket) || + PageIdUtils.itemId(pageId) > 0 && PageIdUtils.itemId(pageId) <= MAX_ITEMID_NUM + : "Incorrectly recycled pageId in reuse bucket: " + U.hexLong(pageId); + dataPageId = pageId; if (io.isEmpty(tailAddr)) { @@ -1108,18 +1116,8 @@ public abstract class PagesList extends DataStructure { decrementBucketSize(bucket); - if (initIoVers != null) { - dataPageId = PageIdUtils.changeType(tailId, FLAG_DATA); - - PageIO initIo = initIoVers.latest(); - - initIo.initNewPage(tailAddr, dataPageId, pageSize()); - - if (needWalDeltaRecord(tailId, tailPage, null)) { - wal.log(new InitNewPageRecord(grpId, tailId, initIo.getType(), - initIo.getVersion(), dataPageId)); - } - } + if (initIoVers != null) + dataPageId = initReusedPage(tailId, tailPage, tailAddr, 0, FLAG_DATA, initIoVers.latest()); else dataPageId = recyclePage(tailId, tailPage, tailAddr, null); @@ -1151,6 +1149,44 @@ public abstract class PagesList extends DataStructure { } /** + * Reused page must obtain correctly assembled page id, then initialized by proper {@link PageIO} instance + * and non-zero {@code itemId} of reused page id must be saved into special place. + * + * @param reusedPageId Reused page id. + * @param reusedPage Reused page. + * @param reusedPageAddr Reused page address. + * @param partId Partition id. + * @param flag Flag. + * @param initIo Initial io. + * @return Prepared page id. + */ + protected final long initReusedPage(long reusedPageId, long reusedPage, long reusedPageAddr, + int partId, byte flag, PageIO initIo) throws IgniteCheckedException { + + long newPageId = PageIdUtils.pageId(partId, flag, PageIdUtils.pageIndex(reusedPageId)); + + initIo.initNewPage(reusedPageAddr, newPageId, pageSize()); + + boolean needWalDeltaRecord = needWalDeltaRecord(reusedPageId, reusedPage, null); + + if (needWalDeltaRecord) { + wal.log(new InitNewPageRecord(grpId, reusedPageId, initIo.getType(), + initIo.getVersion(), newPageId)); + } + + int itemId = PageIdUtils.itemId(reusedPageId); + + if (itemId != 0) { + PageIO.setRotatedIdPart(reusedPageAddr, itemId); + + if (needWalDeltaRecord) + wal.log(new RotatedIdPartRecord(grpId, newPageId, itemId)); + } + + return newPageId; + } + + /** * @param dataId Data page ID. * @param dataPage Data page pointer. * @param dataAddr Data page address. http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java index 4d05095..e30de5a 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java @@ -17,7 +17,6 @@ package org.apache.ignite.internal.processors.cache.persistence.tree; -import java.io.Externalizable; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; @@ -50,6 +49,7 @@ import org.apache.ignite.internal.processors.cache.persistence.tree.io.BPlusLeaf import org.apache.ignite.internal.processors.cache.persistence.tree.io.BPlusMetaIO; import org.apache.ignite.internal.processors.cache.persistence.tree.io.IOVersions; import org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO; +import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.LongListReuseBag; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseBag; import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseList; import org.apache.ignite.internal.processors.cache.persistence.tree.util.PageHandler; @@ -2156,7 +2156,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements if (reuseList == null) return -1; - DestroyBag bag = new DestroyBag(); + LongListReuseBag bag = new LongListReuseBag(); long pagesCnt = 0; @@ -4836,31 +4836,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements } /** - * Reuse bag for destroy. - */ - protected static final class DestroyBag extends GridLongList implements ReuseBag { - /** */ - private static final long serialVersionUID = 0L; - - /** - * Default constructor for {@link Externalizable}. - */ - public DestroyBag() { - // No-op. - } - - /** {@inheritDoc} */ - @Override public void addFreePage(long pageId) { - add(pageId); - } - - /** {@inheritDoc} */ - @Override public long pollFreePage() { - return isEmpty() ? 0 : remove(); - } - } - - /** * */ private static class TreeMetaData { http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java index c940c39..4534bb5 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java @@ -109,16 +109,25 @@ public abstract class PageIO { public static final int PAGE_ID_OFF = CRC_OFF + 4; /** */ - private static final int RESERVED_1_OFF = PAGE_ID_OFF + 8; + public static final int ROTATED_ID_PART_OFF = PAGE_ID_OFF + 8; /** */ - private static final int RESERVED_2_OFF = RESERVED_1_OFF + 8; + private static final int RESERVED_BYTE_OFF = ROTATED_ID_PART_OFF + 1; + + /** */ + private static final int RESERVED_SHORT_OFF = RESERVED_BYTE_OFF + 1; + + /** */ + private static final int RESERVED_INT_OFF = RESERVED_SHORT_OFF + 2; + + /** */ + private static final int RESERVED_2_OFF = RESERVED_INT_OFF + 4; /** */ private static final int RESERVED_3_OFF = RESERVED_2_OFF + 8; /** */ - public static final int COMMON_HEADER_END = RESERVED_3_OFF + 8; // 40=type(2)+ver(2)+crc(4)+pageId(8)+reserved(3*8) + public static final int COMMON_HEADER_END = RESERVED_3_OFF + 8; // 40=type(2)+ver(2)+crc(4)+pageId(8)+rotatedIdPart(1)+reserved(1+2+4+2*8) /* All the page types. */ @@ -301,6 +310,24 @@ public abstract class PageIO { /** * @param pageAddr Page address. + * @return Rotated page ID part. + */ + public static int getRotatedIdPart(long pageAddr) { + return PageUtils.getUnsignedByte(pageAddr, ROTATED_ID_PART_OFF); + } + + /** + * @param pageAddr Page address. + * @param rotatedIdPart Rotated page ID part. + */ + public static void setRotatedIdPart(long pageAddr, int rotatedIdPart) { + PageUtils.putUnsignedByte(pageAddr, ROTATED_ID_PART_OFF, rotatedIdPart); + + assert getRotatedIdPart(pageAddr) == rotatedIdPart; + } + + /** + * @param pageAddr Page address. * @return Checksum. */ public static int getCrc(long pageAddr) { @@ -415,7 +442,7 @@ public abstract class PageIO { setPageId(pageAddr, pageId); setCrc(pageAddr, 0); - PageUtils.putLong(pageAddr, RESERVED_1_OFF, 0L); + PageUtils.putLong(pageAddr, ROTATED_ID_PART_OFF, 0L); // 1 + reserved(1+2+4) PageUtils.putLong(pageAddr, RESERVED_2_OFF, 0L); PageUtils.putLong(pageAddr, RESERVED_3_OFF, 0L); } http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java new file mode 100644 index 0000000..415c603 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java @@ -0,0 +1,46 @@ +/* + * 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.persistence.tree.reuse; + +import java.io.Externalizable; +import org.apache.ignite.internal.util.GridLongList; + +/** + * {@link GridLongList}-based reuse bag. + */ +public final class LongListReuseBag extends GridLongList implements ReuseBag { + /** */ + private static final long serialVersionUID = 0L; + + /** + * Default constructor for {@link Externalizable}. + */ + public LongListReuseBag() { + // No-op. + } + + /** {@inheritDoc} */ + @Override public void addFreePage(long pageId) { + add(pageId); + } + + /** {@inheritDoc} */ + @Override public long pollFreePage() { + return isEmpty() ? 0 : remove(); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/record/RecordTypes.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/record/RecordTypes.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/record/RecordTypes.java index 9654748..1807d1d 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/record/RecordTypes.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/record/RecordTypes.java @@ -65,5 +65,6 @@ public final class RecordTypes { DELTA_TYPE_SET.add(WALRecord.RecordType.PAGE_LIST_META_RESET_COUNT_RECORD); DELTA_TYPE_SET.add(WALRecord.RecordType.DATA_PAGE_UPDATE_RECORD); DELTA_TYPE_SET.add(WALRecord.RecordType.BTREE_META_PAGE_INIT_ROOT2); + DELTA_TYPE_SET.add(WALRecord.RecordType.ROTATED_ID_PART_RECORD); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/serializer/RecordDataV1Serializer.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/serializer/RecordDataV1Serializer.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/serializer/RecordDataV1Serializer.java index e8d116b..f433d26 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/serializer/RecordDataV1Serializer.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/wal/serializer/RecordDataV1Serializer.java @@ -73,6 +73,7 @@ import org.apache.ignite.internal.pagemem.wal.record.delta.PartitionMetaStateRec import org.apache.ignite.internal.pagemem.wal.record.delta.RecycleRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.RemoveRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.ReplaceRecord; +import org.apache.ignite.internal.pagemem.wal.record.delta.RotatedIdPartRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.SplitExistingPageRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.SplitForwardPageRecord; import org.apache.ignite.internal.pagemem.wal.record.delta.TrackingPageDeltaRecord; @@ -286,6 +287,9 @@ public class RecordDataV1Serializer implements RecordDataSerializer { case PAGE_LIST_META_RESET_COUNT_RECORD: return /*cacheId*/ 4 + /*pageId*/ 8; + case ROTATED_ID_PART_RECORD: + return 4 + 8 + 1; + case SWITCH_SEGMENT_RECORD: return 0; @@ -835,6 +839,16 @@ public class RecordDataV1Serializer implements RecordDataSerializer { res = new PageListMetaResetCountRecord(cacheId, pageId); break; + case ROTATED_ID_PART_RECORD: + cacheId = in.readInt(); + pageId = in.readLong(); + + byte rotatedIdPart = in.readByte(); + + res = new RotatedIdPartRecord(cacheId, pageId, rotatedIdPart); + + break; + case SWITCH_SEGMENT_RECORD: throw new EOFException("END OF SEGMENT"); @@ -1351,6 +1365,16 @@ public class RecordDataV1Serializer implements RecordDataSerializer { break; + case ROTATED_ID_PART_RECORD: + RotatedIdPartRecord rotatedIdPartRecord = (RotatedIdPartRecord) rec; + + buf.putInt(rotatedIdPartRecord.groupId()); + buf.putLong(rotatedIdPartRecord.pageId()); + + buf.put(rotatedIdPartRecord.rotatedIdPart()); + + break; + case TX_RECORD: txRecordSerializer.write((TxRecord)rec, buf); http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/test/java/org/apache/ignite/internal/pagemem/impl/PageIdUtilsSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/internal/pagemem/impl/PageIdUtilsSelfTest.java b/modules/core/src/test/java/org/apache/ignite/internal/pagemem/impl/PageIdUtilsSelfTest.java index 2984067..8b41944 100644 --- a/modules/core/src/test/java/org/apache/ignite/internal/pagemem/impl/PageIdUtilsSelfTest.java +++ b/modules/core/src/test/java/org/apache/ignite/internal/pagemem/impl/PageIdUtilsSelfTest.java @@ -34,7 +34,8 @@ public class PageIdUtilsSelfTest extends GridCommonAbstractTest { assertEquals(0x0102FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0x0002FFFFFFFFFFFFL)); assertEquals(0x0B02FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0x0A02FFFFFFFFFFFFL)); assertEquals(0x1002FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0x0F02FFFFFFFFFFFFL)); - assertEquals(0x0002FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0xFF02FFFFFFFFFFFFL)); + assertEquals(0x0102FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0xFE02FFFFFFFFFFFFL)); + assertEquals(0x0102FFFFFFFFFFFFL, PageIdUtils.rotatePageId(0xFF02FFFFFFFFFFFFL)); } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/paged/PageEvictionPagesRecyclingAndReusingTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/paged/PageEvictionPagesRecyclingAndReusingTest.java b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/paged/PageEvictionPagesRecyclingAndReusingTest.java new file mode 100644 index 0000000..9c777fb --- /dev/null +++ b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/eviction/paged/PageEvictionPagesRecyclingAndReusingTest.java @@ -0,0 +1,153 @@ +/* + * 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.paged; + +import java.util.Random; +import org.apache.ignite.IgniteCache; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.cache.CacheAtomicityMode; +import org.apache.ignite.cache.CacheMode; +import org.apache.ignite.cache.CacheWriteSynchronizationMode; +import org.apache.ignite.configuration.CacheConfiguration; +import org.apache.ignite.configuration.DataPageEvictionMode; +import org.apache.ignite.configuration.IgniteConfiguration; +import org.apache.ignite.internal.IgniteEx; +import org.apache.ignite.internal.processors.cache.persistence.tree.reuse.ReuseList; + +/** + * + */ +public class PageEvictionPagesRecyclingAndReusingTest extends PageEvictionAbstractTest { + /** Test timeout. */ + private static final long TEST_TIMEOUT = 10 * 60 * 1000; + + /** Number of small entries. */ + private static final int SMALL_ENTRIES = ENTRIES * 10; + + /** {@inheritDoc} */ + @Override protected IgniteConfiguration getConfiguration(String gridName) throws Exception { + return setEvictionMode(DataPageEvictionMode.RANDOM_LRU, super.getConfiguration(gridName)); + } + + /** {@inheritDoc} */ + @Override protected void afterTest() throws Exception { + stopAllGrids(); + } + + /** {@inheritDoc} */ + @Override protected long getTestTimeout() { + return TEST_TIMEOUT; + } + + /** + * @throws Exception If failed. + */ + public void testPagesRecyclingAndReusingAtomicReplicated() throws Exception { + testPagesRecyclingAndReusing(CacheAtomicityMode.ATOMIC, CacheMode.REPLICATED); + } + + /** + * @throws Exception If failed. + */ + public void testPagesRecyclingAndReusingAtomicLocal() throws Exception { + testPagesRecyclingAndReusing(CacheAtomicityMode.ATOMIC, CacheMode.LOCAL); + } + + /** + * @throws Exception If failed. + */ + public void testPagesRecyclingAndReusingTxReplicated() throws Exception { + testPagesRecyclingAndReusing(CacheAtomicityMode.TRANSACTIONAL, CacheMode.REPLICATED); + } + + /** + * @throws Exception If failed. + */ + public void testPagesRecyclingAndReusingTxLocal() throws Exception { + testPagesRecyclingAndReusing(CacheAtomicityMode.TRANSACTIONAL, CacheMode.LOCAL); + } + + /** + * @param atomicityMode Atomicity mode. + * @param cacheMode Cache mode. + */ + private void testPagesRecyclingAndReusing(CacheAtomicityMode atomicityMode, CacheMode cacheMode) throws Exception { + IgniteEx ignite = startGrid(0); + + CacheConfiguration<Object, Object> cfg = cacheConfig("evict-fair", null, cacheMode, atomicityMode, + CacheWriteSynchronizationMode.PRIMARY_SYNC); + + IgniteCache<Object, Object> cache = ignite(0).getOrCreateCache(cfg); + + ReuseList reuseList = ignite.context().cache().context().database().reuseList(null); + + putRemoveCycles(cache, reuseList); + + long recycledPagesCnt1 = reuseList.recycledPagesCount(); + + putRemoveCycles(cache, reuseList); + + long recycledPagesCnt2 = reuseList.recycledPagesCount(); + + assert recycledPagesCnt1 == recycledPagesCnt2 : "Possible recycled pages leak!"; + } + + /** + * @param cache Cache. + * @param reuseList Reuse list. + */ + private void putRemoveCycles(IgniteCache<Object, Object> cache, ReuseList reuseList) throws IgniteCheckedException { + for (int i = 1; i <= ENTRIES; i++) { + cache.put(i, new TestObject(PAGE_SIZE / 4 - 50)); + + if (i % (ENTRIES / 10) == 0) + System.out.println(">>> Entries put: " + i); + } + + System.out.println("### Recycled pages count: " + reuseList.recycledPagesCount()); + + for (int i = 1; i <= ENTRIES; i++) { + cache.remove(i); + + if (i % (ENTRIES / 10) == 0) + System.out.println(">>> Entries removed: " + i); + } + + System.out.println("### Recycled pages count: " + reuseList.recycledPagesCount()); + + Random rnd = new Random(); + + for (int i = 1; i <= SMALL_ENTRIES; i++) { + cache.put(i, rnd.nextInt()); + + if (i % (SMALL_ENTRIES / 10) == 0) + System.out.println(">>> Small entries put: " + i); + } + + System.out.println("### Recycled pages count: " + reuseList.recycledPagesCount()); + + for (int i = 1; i <= SMALL_ENTRIES; i++) { + cache.remove(i); + + if (i % (SMALL_ENTRIES / 10) == 0) + System.out.println(">>> Small entries removed: " + i); + } + + System.out.println("### Recycled pages count: " + reuseList.recycledPagesCount()); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/persistence/pagemem/FillFactorMetricTest.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/persistence/pagemem/FillFactorMetricTest.java b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/persistence/pagemem/FillFactorMetricTest.java index cdea7bc..42eaf36 100644 --- a/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/persistence/pagemem/FillFactorMetricTest.java +++ b/modules/core/src/test/java/org/apache/ignite/internal/processors/cache/persistence/pagemem/FillFactorMetricTest.java @@ -202,9 +202,10 @@ public class FillFactorMetricTest extends GridCommonAbstractTest { // Wait for cache to be cleared clearFut.get(); - // Fill factor will typically be 0.8, occupied pages mostly partition metadata + // Since refactoring of AbstractFreeList with recycling empty data pages, + // fill factor after cache cleaning will about 0.99, no more obsolete typically value 0.8 for (float fillFactor : curFillFactor) - assertTrue("FillFactor too high: " + fillFactor, fillFactor < 0.85); + assertTrue("FillFactor too low: " + fillFactor, fillFactor > 0.9); } doneFlag.set(true); http://git-wip-us.apache.org/repos/asf/ignite/blob/0bdfa20c/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheEvictionSelfTestSuite.java ---------------------------------------------------------------------- diff --git a/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheEvictionSelfTestSuite.java b/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheEvictionSelfTestSuite.java index 1d4fdf7..f2ac1c0 100644 --- a/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheEvictionSelfTestSuite.java +++ b/modules/core/src/test/java/org/apache/ignite/testsuites/IgniteCacheEvictionSelfTestSuite.java @@ -38,6 +38,7 @@ import org.apache.ignite.internal.processors.cache.eviction.lru.LruNearOnlyNearE import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionDataStreamerTest; import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionMetricTest; import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionMultinodeMixedRegionsTest; +import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionPagesRecyclingAndReusingTest; import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionReadThroughTest; import org.apache.ignite.internal.processors.cache.eviction.paged.PageEvictionTouchOrderTest; import org.apache.ignite.internal.processors.cache.eviction.paged.Random2LruNearEnabledPageEvictionMultinodeTest; @@ -94,6 +95,8 @@ public class IgniteCacheEvictionSelfTestSuite extends TestSuite { suite.addTest(new TestSuite(PageEvictionMetricTest.class)); + suite.addTest(new TestSuite(PageEvictionPagesRecyclingAndReusingTest.class)); + return suite; } }
