ignite-db - rotate page id after reuse
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/86b9fa83 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/86b9fa83 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/86b9fa83 Branch: refs/heads/ignite-db-x-gg-11124 Commit: 86b9fa836bf0fac4c2c6b9fc064ad07090d873dd Parents: bbd4e9f Author: S.Vladykin <[email protected]> Authored: Fri Apr 29 04:31:21 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Fri Apr 29 04:31:21 2016 +0300 ---------------------------------------------------------------------- .../ignite/internal/pagemem/PageIdUtils.java | 15 +- .../ignite/internal/pagemem/impl/PageImpl.java | 2 +- .../internal/pagemem/impl/PageMemoryImpl.java | 22 +- .../processors/cache/database/RowStore.java | 117 +-------- .../cache/database/freelist/FreeList.java | 18 +- .../cache/database/freelist/FreeTree.java | 3 +- .../cache/database/freelist/io/FreeInnerIO.java | 14 +- .../cache/database/freelist/io/FreeLeafIO.java | 2 +- .../cache/database/tree/BPlusTree.java | 247 ++++++++++--------- .../cache/database/tree/reuse/ReuseBag.java | 8 +- .../cache/database/tree/reuse/ReuseList.java | 20 +- .../cache/database/tree/reuse/ReuseTree.java | 25 +- .../database/tree/reuse/io/ReuseInnerIO.java | 18 +- .../database/tree/reuse/io/ReuseLeafIO.java | 17 +- .../cache/database/tree/util/PageHandler.java | 21 +- .../processors/database/BPlusTreeSelfTest.java | 22 +- 16 files changed, 255 insertions(+), 316 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/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 2c28178..956634a 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 @@ -131,8 +131,8 @@ public final class PageIdUtils { * @param pageId Page id. * @return Page ID. */ - public static long pageIdx(long pageId) { - return pageId & PAGE_IDX_MASK; + public static int pageIdx(long pageId) { + return (int)(pageId & PAGE_IDX_MASK); // 30 bytes } /** @@ -191,7 +191,6 @@ public final class PageIdUtils { int fileId = 0; fileId = (fileId << FLAG_SIZE) | (flag & FLAG_MASK); - fileId = (fileId << PART_ID_SIZE) | (partId & PART_ID_MASK); return pageId(fileId, pageIdx); @@ -225,4 +224,14 @@ public final class PageIdUtils { return pageId(partId + 1, PageIdAllocator.FLAG_IDX, pageIdx); } + + /** + * @param pageId Page ID. + * @return Page ID with masked partition ID. + */ + public static long maskPartId(long pageId) { + assert flag(pageId) == PageIdAllocator.FLAG_IDX; // Possible only for index pages. + + return pageId & ~((long)PART_ID_MASK << PAGE_IDX_SIZE); + } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageImpl.java index 91e7798..f7d5601 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageImpl.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageImpl.java @@ -252,7 +252,7 @@ class PageImpl extends AbstractQueuedSynchronizer implements Page { boolean releaseReference() { int refs = refCntUpd.decrementAndGet(this); - assert refs >= 0: fullId.pageId(); + assert refs >= 0: fullId; return refs == 0; } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryImpl.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryImpl.java b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryImpl.java index 7611675..56160f2 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryImpl.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/pagemem/impl/PageMemoryImpl.java @@ -470,7 +470,7 @@ public class PageMemoryImpl implements PageMemory { /** * @return Total number of loaded pages in memory. */ - public long totalPages() { + public long loadedPages() { long total = 0; for (Segment seg : segments) { @@ -488,6 +488,26 @@ public class PageMemoryImpl implements PageMemory { } /** + * @return Total number of acquired pages. + */ + public long acquiredPages() { + long total = 0; + + for (Segment seg : segments) { + seg.readLock().lock(); + + try { + total += seg.acquiredPages.size(); + } + finally { + seg.readLock().unlock(); + } + } + + return total; + } + + /** * @param ptr Pointer to wrap. * @param len Memory location length. * @return Wrapped buffer. http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/RowStore.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/RowStore.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/RowStore.java index fa55322..9816c9f 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/RowStore.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/RowStore.java @@ -17,22 +17,13 @@ package org.apache.ignite.internal.processors.cache.database; -import java.nio.ByteBuffer; import org.apache.ignite.IgniteCheckedException; import org.apache.ignite.internal.pagemem.FullPageId; import org.apache.ignite.internal.pagemem.Page; -import org.apache.ignite.internal.pagemem.PageIdAllocator; import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.processors.cache.CacheObjectContext; import org.apache.ignite.internal.processors.cache.GridCacheContext; import org.apache.ignite.internal.processors.cache.database.freelist.FreeList; -import org.apache.ignite.internal.processors.cache.database.tree.io.DataPageIO; -import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler; - -import static org.apache.ignite.internal.pagemem.PageIdUtils.dwordsOffset; -import static org.apache.ignite.internal.pagemem.PageIdUtils.linkFromDwordOffset; -import static org.apache.ignite.internal.pagemem.PageIdUtils.pageId; -import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.writePage; /** * Data store for H2 rows. @@ -50,46 +41,6 @@ public class RowStore<T extends CacheDataRow> { /** */ protected final CacheObjectContext coctx; - /** */ - private volatile long lastDataPageId; - - /** */ - @Deprecated - private final PageHandler<CacheDataRow> writeRow = new PageHandler<CacheDataRow>() { - @Override public int run(Page page, ByteBuffer buf, CacheDataRow row, int ignore) throws IgniteCheckedException { - int entrySize = DataPageIO.getEntrySize(coctx, row.key(), row.value()); - - DataPageIO io = DataPageIO.VERSIONS.forPage(buf); - - if (io.isEnoughSpace(buf, entrySize)) - return -1; - - int idx = io.addRow(coctx, buf, row.key(), row.value(), row.version(), entrySize); - - assert idx >= 0: idx; - - row.link(linkFromDwordOffset(page.id(), idx)); - - assert row.link() != 0; - - return idx; - } - }; - - /** */ - @Deprecated - private final PageHandler<Void> rmvRow = new PageHandler<Void>() { - @Override public int run(Page page, ByteBuffer buf, Void ignore, int itemId) throws IgniteCheckedException { - DataPageIO io = DataPageIO.VERSIONS.forPage(buf); - - assert DataPageIO.check(itemId): itemId; - - io.removeRow(buf, (byte)itemId); - - return 0; - } - }; - /** * @param cctx Cache context. */ @@ -114,83 +65,19 @@ public class RowStore<T extends CacheDataRow> { } /** - * @param part Partition. - * @return Allocated page. - * @throws IgniteCheckedException if failed. - */ - private Page allocatePage(int part) throws IgniteCheckedException { - FullPageId fullPageId = pageMem.allocatePage(cctx.cacheId(), part, PageIdAllocator.FLAG_DATA); - - return pageMem.page(fullPageId); - } - - /** * @param link Row link. * @throws IgniteCheckedException If failed. */ public void removeRow(long link) throws IgniteCheckedException { assert link != 0; - if (freeList == null) { - try (Page page = page(pageId(link))) { - writePage(page, rmvRow, null, dwordsOffset(link)); - } - } - else - freeList.removeRow(link); - } - - /** - * @param expLastDataPageId Expected last data page ID. - * @return Next data page ID. - */ - private synchronized long nextDataPage(long expLastDataPageId, int partId) throws IgniteCheckedException { - if (expLastDataPageId != lastDataPageId) - return lastDataPageId; - - long pageId; - - try (Page page = allocatePage(partId)) { - pageId = page.id(); - - ByteBuffer buf = page.getForInitialWrite(); - - DataPageIO.VERSIONS.latest().initNewPage(buf, page.id()); - } - - return lastDataPageId = pageId; + freeList.removeRow(link); } /** * @param row Row. */ public void addRow(CacheDataRow row) throws IgniteCheckedException { - if (freeList == null) - writeRowDataOld(row); - else - freeList.insertRow(row); - } - - /** - * @param row Row. - * @throws IgniteCheckedException If failed. - */ - @Deprecated - private void writeRowDataOld(CacheDataRow row) throws IgniteCheckedException { - assert row.link() == 0; - - while (row.link() == 0) { - long pageId = lastDataPageId; - - if (pageId == 0) - pageId = nextDataPage(0, row.partition()); - - try (Page page = page(pageId)) { - if (writePage(page, writeRow, row, -1) >= 0) - return; // Successful write. - } - - nextDataPage(pageId, row.partition()); - } + freeList.insertRow(row); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java index 3d09316..2a6aed8 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeList.java @@ -53,7 +53,7 @@ public class FreeList { /** */ private final PageHandler<CacheDataRow> writeRow = new PageHandler<CacheDataRow>() { - @Override public int run(Page page, ByteBuffer buf, CacheDataRow row, int entrySize) + @Override public int run(long pageId, Page page, ByteBuffer buf, CacheDataRow row, int entrySize) throws IgniteCheckedException { DataPageIO io = DataPageIO.VERSIONS.forPage(buf); @@ -61,12 +61,12 @@ public class FreeList { assert idx >= 0; - row.link(PageIdUtils.linkFromDwordOffset(page.id(), idx)); + row.link(PageIdUtils.linkFromDwordOffset(pageId, idx)); int freeSpace = io.getFreeSpace(buf); // Put our free item. - tree(row.partition()).put(new FreeItem(freeSpace, page.id(), cctx.cacheId())); + tree(row.partition()).put(new FreeItem(freeSpace, pageId, cctx.cacheId())); return 0; } @@ -74,7 +74,7 @@ public class FreeList { /** */ private final PageHandler<FreeTree> removeRow = new PageHandler<FreeTree>() { - @Override public int run(Page page, ByteBuffer buf, FreeTree tree, int itemId) throws IgniteCheckedException { + @Override public int run(long pageId, Page page, ByteBuffer buf, FreeTree tree, int itemId) throws IgniteCheckedException { assert tree != null; DataPageIO io = DataPageIO.VERSIONS.forPage(buf); @@ -88,13 +88,13 @@ public class FreeList { int newFreeSpace = io.getFreeSpace(buf); // Move page to the new position with respect to the new free space. - FreeItem item = tree.remove(new FreeItem(oldFreeSpace, page.id(), cctx.cacheId())); + FreeItem item = tree.remove(new FreeItem(oldFreeSpace, pageId, cctx.cacheId())); // If item is null, then it was removed concurrently by insertRow, because // in removeRow we own the write lock on this page. Thus we can be sure that // insertRow will update position correctly after us. if (item != null) { - FreeItem old = tree.put(new FreeItem(newFreeSpace, page.id(), cctx.cacheId())); + FreeItem old = tree.put(new FreeItem(newFreeSpace, pageId, cctx.cacheId())); assert old == null; } @@ -176,7 +176,7 @@ public class FreeList { FreeTree tree = tree(partId); try (Page page = pageMem.page(new FullPageId(pageId, cctx.cacheId()))) { - writePage(page, removeRow, tree, itemId); + writePage(pageId, page, removeRow, tree, itemId); } } @@ -207,10 +207,10 @@ public class FreeList { io.initNewPage(buf, page.id()); - writeRow.run(page, buf, row, entrySize); + writeRow.run(page.id(), page, buf, row, entrySize); } else - writePage(page, writeRow, row, entrySize); + writePage(page.id(), page, writeRow, row, entrySize); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java index e64ab94..ca769e7 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/FreeTree.java @@ -20,6 +20,7 @@ package org.apache.ignite.internal.processors.cache.database.freelist; import java.nio.ByteBuffer; import org.apache.ignite.IgniteCheckedException; import org.apache.ignite.internal.pagemem.FullPageId; +import org.apache.ignite.internal.pagemem.PageIdUtils; import org.apache.ignite.internal.pagemem.PageMemory; import org.apache.ignite.internal.processors.cache.database.freelist.io.FreeIO; import org.apache.ignite.internal.processors.cache.database.freelist.io.FreeInnerIO; @@ -68,7 +69,7 @@ public class FreeTree extends BPlusTree<FreeItem, FreeItem> { int res = Short.compare(((FreeIO)io).getFreeSpace(buf, idx), row.freeSpace()); if (res == 0) - res = Integer.compare(((FreeIO)io).getPageIndex(buf, idx), FreeInnerIO.pageIndex(row.pageId())); + res = Integer.compare(((FreeIO)io).getPageIndex(buf, idx), PageIdUtils.pageIdx(row.pageId())); return res; } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java index 14c7a00..9082965 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeInnerIO.java @@ -26,24 +26,12 @@ public class FreeInnerIO extends BPlusInnerIO<FreeItem> implements FreeIO { super(T_FREE_INNER, ver, false, 6); // freeSpace(2) + pageIndex(4) } - /** - * @param pageId Page Id. - * @return Page index. - */ - public static int pageIndex(long pageId) { - long idx = PageIdUtils.pageIdx(pageId); - - assert idx >= 0 && idx < Integer.MAX_VALUE: idx; - - return (int)idx; - } - /** {@inheritDoc} */ @Override public void store(ByteBuffer buf, int idx, FreeItem row) { int off = offset(idx); buf.putShort(off, row.freeSpace()); - buf.putInt(off + 2, pageIndex(row.pageId())); + buf.putInt(off + 2, PageIdUtils.pageIdx(row.pageId())); } /** {@inheritDoc} */ http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java index edde01c..210f0ba 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/freelist/io/FreeLeafIO.java @@ -49,7 +49,7 @@ public class FreeLeafIO extends BPlusLeafIO<FreeItem> implements FreeIO { int off = offset(idx); buf.putShort(off, row.freeSpace()); - buf.putInt(off + 2, FreeInnerIO.pageIndex(row.pageId())); + buf.putInt(off + 2, PageIdUtils.pageIdx(row.pageId())); } /** {@inheritDoc} */ http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java index 409c737..e45b8ca 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/BPlusTree.java @@ -18,7 +18,6 @@ package org.apache.ignite.internal.processors.cache.database.tree; import java.nio.ByteBuffer; -import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; @@ -42,10 +41,10 @@ import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO; import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseBag; import org.apache.ignite.internal.processors.cache.database.tree.reuse.ReuseList; import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler; +import org.apache.ignite.internal.util.GridLongList; import org.apache.ignite.internal.util.lang.GridCursor; import org.apache.ignite.internal.util.lang.GridTreePrinter; import org.apache.ignite.internal.util.typedef.F; -import org.apache.ignite.internal.util.typedef.internal.S; import org.apache.ignite.internal.util.typedef.internal.SB; import org.apache.ignite.internal.util.typedef.internal.U; @@ -171,7 +170,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Get> askNeighbor = new GetPageHandler<Get>() { - @Override public int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Get g, int isBack) { + @Override public int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Get g, int isBack) { assert !io.isLeaf(); // Inner page. if (isBack == TRUE) { @@ -182,7 +181,7 @@ public abstract class BPlusTree<L, T extends L> { // here io.getLeft(cnt) is the same, but handles negative index if count is 0. long res = inner(io).getLeft(buf, idx); - assert res != 0 : "inner page with no route down: " + page.fullId(); + assert res != 0 : "inner page with no route down: " + pageId; g.backId = res; } @@ -192,7 +191,7 @@ public abstract class BPlusTree<L, T extends L> { // Leftmost child. long res = inner(io).getLeft(buf, 0); - assert res != 0 : "inner page with no route down: " + page.fullId(); + assert res != 0 : "inner page with no route down: " + pageId; g.fwdId = res; } @@ -203,7 +202,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Get> search = new GetPageHandler<Get>() { - @Override public int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Get g, int lvl) + @Override public int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Get g, int lvl) throws IgniteCheckedException { boolean needBackIfRouting = g.backId != 0; @@ -272,22 +271,15 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Put> replace = new GetPageHandler<Put>() { - @Override public int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Put p, int lvl) + @Override public int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Put p, int lvl) throws IgniteCheckedException { assert p.btmLvl == 0 : "split is impossible with replace"; int cnt = io.getCount(buf); int idx = findInsertionPoint(io, buf, cnt, p.row); - if (idx < 0) { // Not found, split or merge happened. - long fwdId = io.getForward(buf); - - assert fwdId != 0; - - p.pageId = fwdId; - + if (idx < 0) // Not found, split or merge happened. return Put.RETRY; - } // Replace link at idx with new one. // Need to read link here because `p.finish()` will clear row. @@ -311,7 +303,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Put> insert = new GetPageHandler<Put>() { - @Override public int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Put p, int lvl) + @Override public int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Put p, int lvl) throws IgniteCheckedException { assert p.btmLvl == lvl: "we must always insert at the bottom level: " + p.btmLvl + " " + lvl; @@ -350,7 +342,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Remove> removeFromLeaf = new GetPageHandler<Remove>() { - @Override public int run0(Page leaf, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) + @Override public int run0(long leafId, Page leaf, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { assert lvl == 0: lvl; assert r.removed == null; @@ -396,7 +388,7 @@ public abstract class BPlusTree<L, T extends L> { if (r.fwdId != 0 && r.backId == 0) r.lockForward(0); - r.addTail(leaf, buf, io, 0, Tail.EXACT, -1); + r.addTail(leafId, leaf, buf, io, 0, Tail.EXACT, -1); } return Remove.FOUND; @@ -405,7 +397,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Remove> lockBackAndRemoveFromLeaf = new GetPageHandler<Remove>() { - @Override protected int run0(Page back, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) + @Override protected int run0(long backId, Page back, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { // Check that we have consistent view of the world. if (io.getForward(buf) != r.pageId) @@ -416,7 +408,7 @@ public abstract class BPlusTree<L, T extends L> { // Keep locks on back and leaf pages for subsequent merges. if (res == Remove.FOUND && r.tail != null) - r.addTail(back, buf, io, lvl, Tail.BACK, -1); + r.addTail(backId, back, buf, io, lvl, Tail.BACK, -1); return res; } @@ -424,7 +416,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Remove> lockBackAndTail = new GetPageHandler<Remove>() { - @Override public int run0(Page back, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) + @Override public int run0(long backId, Page back, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { // Check that we have consistent view of the world. if (io.getForward(buf) != r.pageId) @@ -434,7 +426,7 @@ public abstract class BPlusTree<L, T extends L> { int res = r.doLockTail(lvl); if (res == Remove.FOUND) - r.addTail(back, buf, io, lvl, Tail.BACK, -1); + r.addTail(backId, back, buf, io, lvl, Tail.BACK, -1); return res; } @@ -442,9 +434,9 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Remove> lockTailForward = new GetPageHandler<Remove>() { - @Override protected int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) + @Override protected int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { - r.addTail(page, buf, io, lvl, Tail.FORWARD, -1); + r.addTail(pageId, page, buf, io, lvl, Tail.FORWARD, -1); return Remove.FOUND; } @@ -452,7 +444,7 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Remove> lockTail = new GetPageHandler<Remove>() { - @Override public int run0(Page page, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) + @Override public int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, Remove r, int lvl) throws IgniteCheckedException { assert lvl > 0: lvl; // We are not at the bottom. @@ -481,7 +473,7 @@ public abstract class BPlusTree<L, T extends L> { } // Check that we have a correct view of the world. - if (lvl != 0 && inner(io).getLeft(buf, idx) != r.getTail(lvl - 1).page.id()) { + if (lvl != 0 && inner(io).getLeft(buf, idx) != r.getTail(lvl - 1).pageId) { assert !found; return Remove.RETRY; @@ -491,7 +483,7 @@ public abstract class BPlusTree<L, T extends L> { if (r.fwdId != 0 && r.backId == 0) r.lockForward(lvl); - r.addTail(page, buf, io, lvl, Tail.EXACT, idx); + r.addTail(pageId, page, buf, io, lvl, Tail.EXACT, idx); return Remove.FOUND; } @@ -499,7 +491,8 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Long> updateFirst = new PageHandler<Long>() { - @Override public int run(Page meta, ByteBuffer buf, Long pageId, int lvl) throws IgniteCheckedException { + @Override public int run(long metaId, Page meta, ByteBuffer buf, Long pageId, int lvl) + throws IgniteCheckedException { assert pageId != null; BPlusMetaIO io = BPlusMetaIO.VERSIONS.forPage(buf); @@ -520,7 +513,8 @@ public abstract class BPlusTree<L, T extends L> { /** */ private final PageHandler<Long> newRoot = new PageHandler<Long>() { - @Override public int run(Page meta, ByteBuffer buf, Long rootPageId, int lvl) throws IgniteCheckedException { + @Override public int run(long metaId, Page meta, ByteBuffer buf, Long rootPageId, int lvl) + throws IgniteCheckedException { assert rootPageId != null; BPlusMetaIO io = BPlusMetaIO.VERSIONS.forPage(buf); @@ -553,6 +547,7 @@ public abstract class BPlusTree<L, T extends L> { assert pageMem != null; assert innerIos != null; assert leafIos != null; + assert PageIdUtils.flag(metaPageId.pageId()) == PageIdAllocator.FLAG_META; this.innerIos = innerIos; this.leafIos = leafIos; @@ -580,11 +575,13 @@ public abstract class BPlusTree<L, T extends L> { io.initNewPage(buf, metaPageId); - try (Page root = allocatePage(null)) { - latestLeafIO().initNewPage(root.getForInitialWrite(), root.id()); + long rootId = allocatePage(null); + + try (Page root = page(rootId)) { + latestLeafIO().initNewPage(root.getForInitialWrite(), rootId); io.setLevelsCount(buf, 1); - io.setFirstPageId(buf, 0, root.id()); + io.setFirstPageId(buf, 0, rootId); } } } @@ -727,7 +724,7 @@ public abstract class BPlusTree<L, T extends L> { g.pageId = pageId; g.fwdId = fwdId; - int res = readPage(page, search, g, lvl); + int res = readPage(pageId, page, search, g, lvl); switch (res) { case Get.GO_DOWN: @@ -761,7 +758,7 @@ public abstract class BPlusTree<L, T extends L> { } } finally { - if (g.canRelease(page, lvl)) + if (g.canRelease(pageId, page, lvl)) page.close(); } } @@ -807,10 +804,10 @@ public abstract class BPlusTree<L, T extends L> { b.append("fwd=").append(formatPageId(fwdId)).append(' '); if (!io.isLeaf()) { - b.append("lm=").append(inner(io).getLeft(buf, 0)).append(' '); + b.append("lm=").append(formatPageId(inner(io).getLeft(buf, 0))).append(' '); if (cnt > 0) - b.append("rm=").append(inner(io).getRight(buf, cnt - 1)).append(' '); + b.append("rm=").append(formatPageId(inner(io).getRight(buf, cnt - 1))).append(' '); } if (keys) @@ -950,7 +947,7 @@ public abstract class BPlusTree<L, T extends L> { r.fwdId = fwdId; r.backId = backId; - int res = readPage(page, search, r, lvl); + int res = readPage(pageId, page, search, r, lvl); switch (res) { case Remove.GO_DOWN_X: @@ -977,7 +974,7 @@ public abstract class BPlusTree<L, T extends L> { } if (!r.isFinished() && !r.finishTail()) - return r.lockTail(page, backId, fwdId, lvl); + return r.lockTail(pageId, page, backId, fwdId, lvl); return res; @@ -998,7 +995,7 @@ public abstract class BPlusTree<L, T extends L> { assert lvl == 0 : lvl; assert r.removed == null; - res = r.removeFromLeaf(page, backId, fwdId); + res = r.removeFromLeaf(pageId, page, backId, fwdId); if (res == Remove.NOT_FOUND) { assert r.ceil: "must be a retry if not a ceiling remove"; @@ -1020,7 +1017,7 @@ public abstract class BPlusTree<L, T extends L> { finally { r.page = null; - if (r.canRelease(page, lvl)) + if (r.canRelease(pageId, page, lvl)) page.close(); } } @@ -1214,7 +1211,7 @@ public abstract class BPlusTree<L, T extends L> { */ private int askNeighbor(long pageId, Get g, boolean back) throws IgniteCheckedException { try (Page page = page(pageId)) { - return readPage(page, askNeighbor, g, back ? TRUE : FALSE); + return readPage(pageId, page, askNeighbor, g, back ? TRUE : FALSE); } } @@ -1238,7 +1235,7 @@ public abstract class BPlusTree<L, T extends L> { p.pageId = pageId; p.fwdId = fwdId; - int res = readPage(page, search, p, lvl); + int res = readPage(pageId, page, search, p, lvl); switch (res) { case Put.GO_DOWN: @@ -1251,7 +1248,7 @@ public abstract class BPlusTree<L, T extends L> { if (p.needReplaceInner == TRUE) { p.needReplaceInner = FALSE; // Protect from retries. - res = writePage(page, replace, p, lvl); + res = writePage(pageId, page, replace, p, lvl); if (res != Put.FOUND) return res; // Need to retry. @@ -1277,7 +1274,7 @@ public abstract class BPlusTree<L, T extends L> { p.pageId = pageId; p.fwdId = fwdId; - return writePage(page, replace, p, lvl); + return writePage(pageId, page, replace, p, lvl); case Put.NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; @@ -1287,7 +1284,7 @@ public abstract class BPlusTree<L, T extends L> { p.pageId = pageId; p.fwdId = fwdId; - return writePage(page, insert, p, lvl); + return writePage(pageId, page, insert, p, lvl); default: return res; @@ -1295,7 +1292,7 @@ public abstract class BPlusTree<L, T extends L> { } } finally{ - if (p.canRelease(page, lvl)) + if (p.canRelease(pageId, page, lvl)) page.close(); } } @@ -1430,11 +1427,12 @@ public abstract class BPlusTree<L, T extends L> { } /** + * @param pageId Page ID. * @param page Page. * @param lvl Level. * @return {@code true} If we can release the given page. */ - boolean canRelease(Page page, int lvl) { + boolean canRelease(long pageId, Page page, int lvl) { return page != null; } } @@ -1565,7 +1563,7 @@ public abstract class BPlusTree<L, T extends L> { } /** - * @param tail Tail lock. + * @param tail Tail page. */ private void tail(Page tail) { if (this.tail != null) @@ -1575,7 +1573,7 @@ public abstract class BPlusTree<L, T extends L> { } /** {@inheritDoc} */ - @Override boolean canRelease(Page page, int lvl) { + @Override boolean canRelease(long pageId, Page page, int lvl) { return page != null && tail != page; } @@ -1646,12 +1644,14 @@ public abstract class BPlusTree<L, T extends L> { */ private L insertWithSplit(BPlusIO<L> io, final ByteBuffer buf, int idx, int lvl) throws IgniteCheckedException { - try (Page fwd = allocatePage(bag)) { + long fwdId = allocatePage(bag); + + try (Page fwd = page(fwdId)) { // Need to check this before the actual split, because after the split we will have new forward page here. boolean hadFwd = io.getForward(buf) != 0; ByteBuffer fwdBuf = fwd.getForInitialWrite(); - io.initNewPage(fwdBuf, fwd.id()); + io.initNewPage(fwdBuf, fwdId); boolean midShift = splitPage(io, buf, fwdBuf, idx); @@ -1677,25 +1677,23 @@ public abstract class BPlusTree<L, T extends L> { io.setCount(buf, cnt - 1); if (!hadFwd && lvl == getRootLevel(meta)) { // We are splitting root. - long newRootId; - - try (Page newRoot = allocatePage(bag)) { - newRootId = newRoot.id(); + long newRootId = allocatePage(bag); + try (Page newRoot = page(newRootId)) { if (io.isLeaf()) io = latestInnerIO(); ByteBuffer newRootBuf = newRoot.getForInitialWrite(); - io.initNewPage(newRootBuf, newRoot.id()); + io.initNewPage(newRootBuf, newRootId); io.setCount(newRootBuf, 1); inner(io).setLeft(newRootBuf, 0, PageIO.getPageId(buf)); io.store(newRootBuf, 0, moveUpRow); - inner(io).setRight(newRootBuf, 0, fwd.id()); + inner(io).setRight(newRootBuf, 0, fwdId); } - int res = writePage(meta, newRoot, newRootId, lvl + 1); + int res = writePage(metaPageId, meta, newRoot, newRootId, lvl + 1); assert res == TRUE : "failed to update meta page"; @@ -1759,16 +1757,19 @@ public abstract class BPlusTree<L, T extends L> { /** {@inheritDoc} */ @SuppressWarnings("unchecked") - @Override public FullPageId pollFreePage() { + @Override public long pollFreePage() { assert bag == null; if (freePages == null) - return null; + return 0; - if (freePages.getClass() == ArrayDeque.class) - return ((ArrayDeque<FullPageId>)freePages).poll(); + if (freePages.getClass() == GridLongList.class) { + GridLongList list = ((GridLongList)freePages); - FullPageId res = (FullPageId)freePages; + return list.isEmpty() ? 0 : list.remove(); + } + + long res = (long)freePages; freePages = null; @@ -1777,27 +1778,25 @@ public abstract class BPlusTree<L, T extends L> { /** {@inheritDoc} */ @SuppressWarnings("unchecked") - @Override public void addFreePage(FullPageId pageId) { - assert pageId != null; + @Override public void addFreePage(long pageId) { + assert pageId != 0; assert bag == null; if (freePages == null) freePages = pageId; else { - ArrayDeque<Object> queue; + GridLongList list; - if (freePages.getClass() == ArrayDeque.class) - queue = (ArrayDeque<Object>)freePages; + if (freePages.getClass() == GridLongList.class) + list = (GridLongList)freePages; else { - assert freePages instanceof FullPageId; + list = new GridLongList(4); - queue = new ArrayDeque<>(8); - - queue.add(freePages); - freePages = queue; + list.add((Long)freePages); + freePages = list; } - queue.add(pageId); + list.add(pageId); } } @@ -1919,7 +1918,7 @@ public abstract class BPlusTree<L, T extends L> { if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta) == tail.lvl) { // Free root if it became empty after merge. - freePage(tail.page, tail.buf, tail.io, tail.lvl, false); + freePage(tail.pageId, tail.page, tail.buf, tail.io, tail.lvl, false); } else if (tail.sibling != null && tail.getCount() + tail.sibling.getCount() < tail.io.getMaxCount(tail.buf)) { @@ -1938,15 +1937,16 @@ public abstract class BPlusTree<L, T extends L> { } /** + * @param leafId Leaf page ID. * @param leaf Leaf page. * @param backId Back page ID. * @param fwdId Forward ID. * @return Result code. * @throws IgniteCheckedException If failed. */ - private int removeFromLeaf(Page leaf, long backId, long fwdId) throws IgniteCheckedException { + private int removeFromLeaf(long leafId, Page leaf, long backId, long fwdId) throws IgniteCheckedException { // Init parameters. - this.pageId = leaf.id(); + this.pageId = leafId; this.page = leaf; this.backId = backId; this.fwdId = fwdId; @@ -1958,10 +1958,10 @@ public abstract class BPlusTree<L, T extends L> { Page back = page(backId); try { - return writePage(back, lockBackAndRemoveFromLeaf, this, 0); + return writePage(backId, back, lockBackAndRemoveFromLeaf, this, 0); } finally { - if (canRelease(back, 0)) + if (canRelease(backId, back, 0)) back.close(); } } @@ -1974,7 +1974,7 @@ public abstract class BPlusTree<L, T extends L> { private int doRemoveFromLeaf() throws IgniteCheckedException { assert page != null; - return writePage(page, removeFromLeaf, this, 0); + return writePage(pageId, page, removeFromLeaf, this, 0); } /** @@ -1985,10 +1985,11 @@ public abstract class BPlusTree<L, T extends L> { private int doLockTail(int lvl) throws IgniteCheckedException { assert page != null; - return writePage(page, lockTail, this, lvl); + return writePage(pageId, page, lockTail, this, lvl); } /** + * @param pageId Page ID. * @param page Page. * @param backId Back page ID. * @param fwdId Expected forward page ID. @@ -1996,11 +1997,11 @@ public abstract class BPlusTree<L, T extends L> { * @return Result code. * @throws IgniteCheckedException If failed. */ - private int lockTail(Page page, long backId, long fwdId, int lvl) throws IgniteCheckedException { + private int lockTail(long pageId, Page page, long backId, long fwdId, int lvl) throws IgniteCheckedException { assert tail != null; // Init parameters for the handlers. - this.pageId = page.id(); + this.pageId = pageId; this.page = page; this.fwdId = fwdId; this.backId = backId; @@ -2011,10 +2012,10 @@ public abstract class BPlusTree<L, T extends L> { Page back = page(backId); try { - return writePage(back, lockBackAndTail, this, lvl); + return writePage(backId, back, lockBackAndTail, this, lvl); } finally { - if (canRelease(back, lvl)) + if (canRelease(backId, back, lvl)) back.close(); } } @@ -2027,7 +2028,7 @@ public abstract class BPlusTree<L, T extends L> { assert fwdId != 0; assert backId == 0; - int res = writePage(page(fwdId), lockTailForward, this, lvl); + int res = writePage(fwdId, page(fwdId), lockTailForward, this, lvl); // Must always be called from lock on back page, thus we should never fail here. assert res == Remove.FOUND: res; @@ -2061,7 +2062,7 @@ public abstract class BPlusTree<L, T extends L> { private boolean doMerge(Tail<L> prnt, Tail<L> left, Tail<L> right) throws IgniteCheckedException { assert right.io == left.io; // Otherwise incompatible. - assert left.io.getForward(left.buf) == right.page.id(); + assert left.io.getForward(left.buf) == right.pageId; int prntCnt = prnt.getCount(); int leftCnt = left.getCount(); @@ -2116,12 +2117,13 @@ public abstract class BPlusTree<L, T extends L> { doRemove(prnt.io, prnt.buf, prntCnt, prntIdx); // Forward page is now empty and has no links, can free and release it right away. - freePage(right.page, right.buf, right.io, right.lvl, true); + freePage(right.pageId, right.page, right.buf, right.io, right.lvl, true); return true; } /** + * @param pageId Page ID. * @param page Page. * @param buf Buffer. * @param io IO. @@ -2130,13 +2132,13 @@ public abstract class BPlusTree<L, T extends L> { * @throws IgniteCheckedException If failed. */ @SuppressWarnings("unchecked") - private void freePage(Page page, ByteBuffer buf, BPlusIO io, int lvl, boolean release) + private void freePage(long pageId, Page page, ByteBuffer buf, BPlusIO io, int lvl, boolean release) throws IgniteCheckedException { - if (getFirstPageId(meta, lvl) == page.id()) { + if (getFirstPageId(meta, lvl) == pageId) { // This logic will handle root as well. long fwdId = io.getForward(buf); - int res = writePage(meta, updateFirst, fwdId, lvl); + int res = writePage(metaPageId, meta, updateFirst, fwdId, lvl); assert res == TRUE: res; } @@ -2145,12 +2147,13 @@ public abstract class BPlusTree<L, T extends L> { io.setRemoveId(buf, Long.MAX_VALUE); // Rotate page ID to avoid concurrency issues with reused pages. - PageIO.setPageId(buf, PageIdUtils.rotatePageId(PageIO.getPageId(buf))); + pageId = PageIdUtils.rotatePageId(pageId); + PageIO.setPageId(buf, pageId); if (release) writeUnlockAndClose(page); - bag().addFreePage(page.fullId()); + bag().addFreePage(pageId); } /** @@ -2189,7 +2192,7 @@ public abstract class BPlusTree<L, T extends L> { else { // If after leaf merge parent have lost inner key, we don't need to update it anymore. assert innerIdx == innerCnt; - assert inner(inner.io).getLeft(inner.buf, innerIdx) == leaf.page.id(); + assert inner(inner.io).getLeft(inner.buf, innerIdx) == leaf.pageId; } } @@ -2233,6 +2236,7 @@ public abstract class BPlusTree<L, T extends L> { } else { // left is already EXACT. assert left.type == Tail.EXACT: left.type; + assert left.sibling != null; left.sibling = null; } @@ -2271,8 +2275,8 @@ public abstract class BPlusTree<L, T extends L> { } /** {@inheritDoc} */ - @Override boolean canRelease(Page page, int lvl) { - return page != null && !isTail(page.id(), lvl); + @Override boolean canRelease(long pageId, Page page, int lvl) { + return page != null && !isTail(pageId, lvl); } /** @@ -2288,12 +2292,12 @@ public abstract class BPlusTree<L, T extends L> { return false; if (t.lvl == lvl) { - if (t.page.id() == pageId) + if (t.pageId == pageId) return true; t = t.sibling; - return t != null && t.page.id() == pageId; + return t != null && t.pageId == pageId; } t = t.down; @@ -2303,6 +2307,7 @@ public abstract class BPlusTree<L, T extends L> { } /** + * @param pageId Page ID. * @param page Page. * @param buf Buffer. * @param io IO. @@ -2310,8 +2315,8 @@ public abstract class BPlusTree<L, T extends L> { * @param type Type. * @param idx Insertion index or negative flag describing if the page is primary in this tail branch. */ - private void addTail(Page page, ByteBuffer buf, BPlusIO<L> io, int lvl, byte type, int idx) { - Tail<L> t = new Tail<>(page, buf, io, type, lvl, idx); + private void addTail(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, int lvl, byte type, int idx) { + Tail<L> t = new Tail<>(pageId, page, buf, io, type, lvl, idx); if (tail == null) tail = t; @@ -2376,6 +2381,9 @@ public abstract class BPlusTree<L, T extends L> { static final byte FORWARD = 2; /** */ + final long pageId; + + /** */ final Page page; /** */ @@ -2400,6 +2408,7 @@ public abstract class BPlusTree<L, T extends L> { Tail<L> down; /** + * @param pageId Page ID. * @param page Write locked page. * @param buf Buffer. * @param io IO. @@ -2407,12 +2416,14 @@ public abstract class BPlusTree<L, T extends L> { * @param lvl Level. * @param idx Insertion index. */ - private Tail(Page page, ByteBuffer buf, BPlusIO<L> io, byte type, int lvl, int idx) { + private Tail(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, byte type, int lvl, int idx) { assert type == BACK || type == EXACT || type == FORWARD: type; assert idx == -1 || (idx >= 0 && idx <= Short.MAX_VALUE): idx ; assert lvl >= 0 && lvl <= Byte.MAX_VALUE: lvl; assert page != null; + assert pageId != 0; + this.pageId = pageId; this.page = page; this.buf = buf; this.io = io; @@ -2430,7 +2441,8 @@ public abstract class BPlusTree<L, T extends L> { /** {@inheritDoc} */ @Override public String toString() { - return S.toString(Tail.class, this, "pageId", page.id(), "cnt", getCount(), "lvl", lvl, "sibling", sibling); + return new SB("Tail[").a("pageId=").appendHex(pageId).a(", cnt= ").a(getCount()) + .a(", lvl=" + lvl).a(", sibling=").a(sibling).a("]").toString(); } } @@ -2493,6 +2505,9 @@ public abstract class BPlusTree<L, T extends L> { * @throws IgniteCheckedException If failed. */ private Page page(long pageId) throws IgniteCheckedException { + if (PageIdUtils.flag(pageId) == PageIdAllocator.FLAG_IDX) + pageId = PageIdUtils.maskPartId(pageId); + return pageMem.page(new FullPageId(pageId, cacheId)); } @@ -2500,16 +2515,18 @@ public abstract class BPlusTree<L, T extends L> { * @param bag Reuse bag. * @return Allocated page. */ - private Page allocatePage(ReuseBag bag) throws IgniteCheckedException { - FullPageId pageId = bag != null ? bag.pollFreePage() : null; + private long allocatePage(ReuseBag bag) throws IgniteCheckedException { + long pageId = bag != null ? bag.pollFreePage() : 0; - if (pageId == null && reuseList != null) + if (pageId == 0 && reuseList != null) pageId = reuseList.take(this, bag); - if (pageId == null) - pageId = pageMem.allocatePage(cacheId, -1, PageIdAllocator.FLAG_IDX); + if (pageId == 0) // TODO make pageMem.allocatePage return long + pageId = pageMem.allocatePage(cacheId, 0, PageIdAllocator.FLAG_IDX).pageId(); - return pageMem.page(pageId); + assert pageId != 0; + + return pageId; } /** @@ -2695,9 +2712,10 @@ public abstract class BPlusTree<L, T extends L> { */ private abstract class GetPageHandler<G extends Get> extends PageHandler<G> { /** {@inheritDoc} */ - @Override public final int run(Page page, ByteBuffer buf, G g, int lvl) throws IgniteCheckedException { + @Override public final int run(long pageId, Page page, ByteBuffer buf, G g, int lvl) + throws IgniteCheckedException { // The page was merged and removed. - if (PageIO.getPageId(buf) != page.id()) + if (PageIO.getPageId(buf) != pageId) return Get.RETRY; BPlusIO<L> io = io(buf); @@ -2707,10 +2725,11 @@ public abstract class BPlusTree<L, T extends L> { if (g.rmvId < io.getRemoveId(buf)) return Get.RETRY_ROOT; - return run0(page, buf, io, g, lvl); + return run0(pageId, page, buf, io, g, lvl); } /** + * @param pageId Page ID. * @param page Page. * @param buf Buffer. * @param io IO. @@ -2719,12 +2738,12 @@ public abstract class BPlusTree<L, T extends L> { * @return Result code. * @throws IgniteCheckedException If failed. */ - protected abstract int run0(Page page, ByteBuffer buf, BPlusIO<L> io, G g, int lvl) + protected abstract int run0(long pageId, Page page, ByteBuffer buf, BPlusIO<L> io, G g, int lvl) throws IgniteCheckedException; /** {@inheritDoc} */ - @Override public final boolean releaseAfterWrite(Page page, G g, int lvl) { - return g.canRelease(page, lvl); + @Override public final boolean releaseAfterWrite(long pageId, Page page, G g, int lvl) { + return g.canRelease(pageId, page, lvl); } } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseBag.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseBag.java index 7fce7b7..903e93f 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseBag.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseBag.java @@ -17,8 +17,6 @@ package org.apache.ignite.internal.processors.cache.database.tree.reuse; -import org.apache.ignite.internal.pagemem.FullPageId; - /** * Reuse bag for free index pages. */ @@ -26,10 +24,10 @@ public interface ReuseBag { /** * @param pageId Free page ID for reuse. */ - public void addFreePage(FullPageId pageId); + public void addFreePage(long pageId); /** - * @return Free page ID for reuse or {@code null} if empty. + * @return Free page ID for reuse or {@code 0} if empty. */ - public FullPageId pollFreePage(); + public long pollFreePage(); } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java index c1e3d53..e28babc 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java @@ -30,9 +30,6 @@ import org.apache.ignite.lang.IgniteBiTuple; */ public final class ReuseList { /** */ - private static final FullPageId MIN = new FullPageId(0,0); - - /** */ private final ReuseTree[] trees; /** @@ -99,15 +96,17 @@ public final class ReuseList { /** * @param client Client tree. * @param bag Reuse bag. - * @return Page ID. + * @return Page ID or {@code 0} if none available. * @throws IgniteCheckedException If failed. */ - public FullPageId take(BPlusTree<?,?> client, ReuseBag bag) throws IgniteCheckedException { + public long take(BPlusTree<?,?> client, ReuseBag bag) throws IgniteCheckedException { if (trees == null) - return null; + return 0; // Remove and return page at min possible position. - return tree(client).removeCeil(MIN, bag); + Long pageId = tree(client).removeCeil(0L, bag); + + return pageId != null ? pageId : 0; } /** @@ -116,13 +115,12 @@ public final class ReuseList { * @throws IgniteCheckedException If failed. */ public void add(BPlusTree<?,?> client, ReuseBag bag) throws IgniteCheckedException { - if (bag == null) - return; + assert bag != null; for (int i = client.randomInt(trees.length);;) { - FullPageId pageId = bag.pollFreePage(); + long pageId = bag.pollFreePage(); - if (pageId == null) + if (pageId == 0) break; trees[i].put(pageId, bag); http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java index 36f767d..fa8aa11 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java @@ -30,7 +30,7 @@ import org.apache.ignite.internal.processors.cache.database.tree.reuse.io.ReuseL /** * Reuse tree for index pages. */ -public final class ReuseTree extends BPlusTree<FullPageId, FullPageId> { +public final class ReuseTree extends BPlusTree<Number, Long> { /** * @param reuseList Reuse list. * @param cacheId Cache ID. @@ -48,20 +48,31 @@ public final class ReuseTree extends BPlusTree<FullPageId, FullPageId> { } /** {@inheritDoc} */ - @Override protected int compare(BPlusIO<FullPageId> io, ByteBuffer buf, int idx, FullPageId fullPageId) + @Override protected int compare(BPlusIO<Number> io, ByteBuffer buf, int idx, Number row) throws IgniteCheckedException { - long pageIdx = io.isLeaf() ? + int pageIdx = io.isLeaf() ? PageIdUtils.pageIdx(((ReuseLeafIO)io).getPageId(buf, idx)) : - (((ReuseInnerIO)io).getPageIndex(buf, idx) & 0xFFFFFFFFL); + (((ReuseInnerIO)io).getPageIndex(buf, idx)); - return Long.compare(pageIdx, PageIdUtils.pageIdx(fullPageId.pageId())); + return Integer.compare(pageIdx, toPageIndex(row)); + } + + /** + * @param row Lookup row. + * @return Page index. + */ + private static int toPageIndex(Number row) { + if (row.getClass() == Integer.class) + return row.intValue(); + + return PageIdUtils.pageIdx(row.longValue()); } /** {@inheritDoc} */ - @Override protected FullPageId getRow(BPlusIO<FullPageId> io, ByteBuffer buf, int idx) + @Override protected Long getRow(BPlusIO<Number> io, ByteBuffer buf, int idx) throws IgniteCheckedException { assert io.isLeaf(); - return new FullPageId(((ReuseLeafIO)io).getPageId(buf, idx) , getCacheId()); + return ((ReuseLeafIO)io).getPageId(buf, idx); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java index 522efba..db3914d 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java @@ -19,7 +19,6 @@ package org.apache.ignite.internal.processors.cache.database.tree.reuse.io; import java.nio.ByteBuffer; import org.apache.ignite.IgniteCheckedException; -import org.apache.ignite.internal.pagemem.FullPageId; import org.apache.ignite.internal.pagemem.PageIdUtils; import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree; import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO; @@ -29,7 +28,7 @@ import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; /** * Reuse list inner page IO routines. */ -public final class ReuseInnerIO extends BPlusInnerIO<FullPageId> { +public final class ReuseInnerIO extends BPlusInnerIO<Number> { /** */ public static final IOVersions<ReuseInnerIO> VERSIONS = new IOVersions<>( new ReuseInnerIO(1) @@ -43,9 +42,9 @@ public final class ReuseInnerIO extends BPlusInnerIO<FullPageId> { } /** {@inheritDoc} */ - @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<FullPageId> srcIo, ByteBuffer src, int srcIdx) { + @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<Number> srcIo, ByteBuffer src, int srcIdx) { int pageIdx = srcIo.isLeaf() ? - (int)PageIdUtils.pageIdx(((ReuseLeafIO)srcIo).getPageId(src, srcIdx)) : + PageIdUtils.pageIdx(((ReuseLeafIO)srcIo).getPageId(src, srcIdx)) : ((ReuseInnerIO)srcIo).getPageIndex(src, srcIdx); store(dst, dstIdx, pageIdx); @@ -70,15 +69,14 @@ public final class ReuseInnerIO extends BPlusInnerIO<FullPageId> { } /** {@inheritDoc} */ - @Override public void store(ByteBuffer buf, int idx, FullPageId fullPageId) { - store(buf, idx, (int)PageIdUtils.pageIdx(fullPageId.pageId())); + @Override public void store(ByteBuffer buf, int idx, Number row) { + store(buf, idx, row.getClass() == Integer.class ? row.intValue() : + PageIdUtils.pageIdx(row.longValue())); } /** {@inheritDoc} */ - @Override public FullPageId getLookupRow(BPlusTree<FullPageId,?> tree, ByteBuffer buf, int idx) + @Override public Number getLookupRow(BPlusTree<Number,?> tree, ByteBuffer buf, int idx) throws IgniteCheckedException { - int pageIdx = getPageIndex(buf, idx); - - return new FullPageId(PageIdUtils.pageId(0, pageIdx), tree.getCacheId()); + return getPageIndex(buf, idx); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java index 3d2d37a..5bf47ce 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java @@ -19,7 +19,6 @@ package org.apache.ignite.internal.processors.cache.database.tree.reuse.io; import java.nio.ByteBuffer; import org.apache.ignite.IgniteCheckedException; -import org.apache.ignite.internal.pagemem.FullPageId; import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree; import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO; import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO; @@ -28,7 +27,7 @@ import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; /** * Reuse list leaf page IO routines. */ -public final class ReuseLeafIO extends BPlusLeafIO<FullPageId> { +public final class ReuseLeafIO extends BPlusLeafIO<Number> { /** */ public static final IOVersions<ReuseLeafIO> VERSIONS = new IOVersions<>( new ReuseLeafIO(1) @@ -38,16 +37,18 @@ public final class ReuseLeafIO extends BPlusLeafIO<FullPageId> { * @param ver Page format version. */ protected ReuseLeafIO(int ver) { - super(T_REUSE_LEAF, ver, 8); + super(T_REUSE_LEAF, ver, 8); // TODO we can store only 6 bytes here: pageIdx(4) + partId(2) } /** {@inheritDoc} */ - @Override public void store(ByteBuffer buf, int idx, FullPageId fullPageId) { - buf.putLong(offset(idx), fullPageId.pageId()); + @Override public void store(ByteBuffer buf, int idx, Number pageId) { + assert pageId.getClass() == Long.class; + + buf.putLong(offset(idx), pageId.longValue()); } /** {@inheritDoc} */ - @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<FullPageId> srcIo, ByteBuffer src, int srcIdx) { + @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<Number> srcIo, ByteBuffer src, int srcIdx) { assert srcIo == this; dst.putLong(offset(dstIdx), getPageId(src, srcIdx)); @@ -63,8 +64,8 @@ public final class ReuseLeafIO extends BPlusLeafIO<FullPageId> { } /** {@inheritDoc} */ - @Override public FullPageId getLookupRow(BPlusTree<FullPageId,?> tree, ByteBuffer buf, int idx) + @Override public Number getLookupRow(BPlusTree<Number,?> tree, ByteBuffer buf, int idx) throws IgniteCheckedException { - return new FullPageId(getPageId(buf, idx), tree.getCacheId()); + return getPageId(buf, idx); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/util/PageHandler.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/util/PageHandler.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/util/PageHandler.java index d2cf58b..84a5588 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/util/PageHandler.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/util/PageHandler.java @@ -24,11 +24,11 @@ import org.apache.ignite.internal.util.GridUnsafe; import sun.nio.ch.DirectBuffer; /** - * Page handler. Can do {@link #readPage(Page, PageHandler, Object, int)} - * and {@link #writePage(Page, PageHandler, Object, int)} operations. + * Page handler. */ public abstract class PageHandler<X> { /** + * @param pageId Page ID. * @param page Page. * @param buf Page buffer. * @param arg Argument. @@ -36,19 +36,21 @@ public abstract class PageHandler<X> { * @return Result. * @throws IgniteCheckedException If failed. */ - public abstract int run(Page page, ByteBuffer buf, X arg, int intArg) throws IgniteCheckedException; + public abstract int run(long pageId, Page page, ByteBuffer buf, X arg, int intArg) throws IgniteCheckedException; /** + * @param pageId Page ID. * @param page Page. * @param arg Argument. * @param intArg Argument of type {@code int}. * @return {@code true} If release. */ - public boolean releaseAfterWrite(Page page, X arg, int intArg) { + public boolean releaseAfterWrite(long pageId, Page page, X arg, int intArg) { return true; } /** + * @param pageId Page ID. * @param page Page. * @param h Handler. * @param arg Argument. @@ -56,7 +58,7 @@ public abstract class PageHandler<X> { * @return Handler result. * @throws IgniteCheckedException If failed. */ - public static <X> int readPage(Page page, PageHandler<X> h, X arg, int intArg) + public static <X> int readPage(long pageId, Page page, PageHandler<X> h, X arg, int intArg) throws IgniteCheckedException { assert page != null; @@ -65,7 +67,7 @@ public abstract class PageHandler<X> { assert buf != null; try { - return h.run(page, buf, arg, intArg); + return h.run(pageId, page, buf, arg, intArg); } finally { page.releaseRead(); @@ -73,6 +75,7 @@ public abstract class PageHandler<X> { } /** + * @param pageId Page ID. * @param page Page. * @param h Handler. * @param arg Argument. @@ -80,7 +83,7 @@ public abstract class PageHandler<X> { * @return Handler result. * @throws IgniteCheckedException If failed. */ - public static <X> int writePage(Page page, PageHandler<X> h, X arg, int intArg) + public static <X> int writePage(long pageId, Page page, PageHandler<X> h, X arg, int intArg) throws IgniteCheckedException { assert page != null; @@ -93,12 +96,12 @@ public abstract class PageHandler<X> { assert buf != null; try { - res = h.run(page, buf, arg, intArg); + res = h.run(pageId, page, buf, arg, intArg); ok = true; } finally { - if (h.releaseAfterWrite(page, arg, intArg)) + if (h.releaseAfterWrite(pageId, page, arg, intArg)) page.releaseWrite(ok); } http://git-wip-us.apache.org/repos/asf/ignite/blob/86b9fa83/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java index 4a1d2ed..8917bf2 100644 --- a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java +++ b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeSelfTest.java @@ -99,7 +99,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { reuseList = createReuseList(CACHE_ID, pageMem, 2, new MetaStore() { @Override public IgniteBiTuple<FullPageId,Boolean> getOrAllocateForIndex(int cacheId, String idxName) throws IgniteCheckedException { - return new T2<>(allocatePage(), true); + return new T2<>(allocateMetaPage(), true); } }); } @@ -125,6 +125,8 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { assertTrue("Reuse size: " + size, size < 2000); } + assertEquals(0, ((PageMemoryImpl)pageMem).acquiredPages()); + pageMem.stop(); MAX_PER_PAGE = 0; @@ -498,10 +500,14 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { for (int i = 0 ; i < loops; i++) { Long x = (long)tree.randomInt(CNT); - if (i % 100_000 == 0) - X.println(" --> " + i + " " + x); + boolean put = tree.randomInt(2) == 0; + + if (i % 100_000 == 0) { + X.println(" --> " + (put ? "put " : "rmv ") + i + " " + x); + X.println(tree.printTree()); + } - if (tree.randomInt(2) == 0) + if (put) assertEquals(map.put(x, x), tree.put(x)); else { if (map.remove(x) != null) @@ -531,7 +537,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { * @throws IgniteCheckedException If failed. */ private TestTree createTestTree(boolean canGetRow) throws IgniteCheckedException { - TestTree tree = new TestTree(reuseList, canGetRow, CACHE_ID, pageMem, allocatePage()); + TestTree tree = new TestTree(reuseList, canGetRow, CACHE_ID, pageMem, allocateMetaPage()); assertEquals(0, tree.size()); assertEquals(0, tree.rootLevel()); @@ -540,11 +546,11 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { } /** - * @return Allocated full page ID. + * @return Allocated meta page ID. * @throws IgniteCheckedException If failed. */ - private FullPageId allocatePage() throws IgniteCheckedException { - return pageMem.allocatePage(CACHE_ID, -1, PageIdAllocator.FLAG_IDX); + private FullPageId allocateMetaPage() throws IgniteCheckedException { + return pageMem.allocatePage(CACHE_ID, 0, PageIdAllocator.FLAG_META); } /**
