ignite-db - reuse list
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/4282d802 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/4282d802 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/4282d802 Branch: refs/heads/ignite-db-x-10884 Commit: 4282d802f16188cdea05d6b2d2c0f3c222e343b6 Parents: 3351840 Author: S.Vladykin <[email protected]> Authored: Mon Apr 18 10:10:07 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Mon Apr 18 10:10:07 2016 +0300 ---------------------------------------------------------------------- .../cache/database/tree/BPlusTree.java | 19 +++++ .../cache/database/tree/io/PageIO.java | 6 ++ .../cache/database/tree/reuse/ReuseList.java | 73 ++++++++++++++++ .../cache/database/tree/reuse/ReuseTree.java | 88 ++++++++++++++++++++ .../database/tree/reuse/io/ReuseInnerIO.java | 84 +++++++++++++++++++ .../database/tree/reuse/io/ReuseLeafIO.java | 62 ++++++++++++++ .../query/h2/database/freelist/FreeTree.java | 7 -- .../h2/database/freelist/io/FreeLeafIO.java | 6 +- .../IgniteDbSingleNodePutGetSelfTest.java | 2 +- 9 files changed, 335 insertions(+), 12 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/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 9d3c995..5e725da 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 @@ -491,6 +491,13 @@ public abstract class BPlusTree<L, T extends L> { } /** + * @return Cache ID. + */ + public int getCacheId() { + return cacheId; + } + + /** * @throws IgniteCheckedException If failed. */ protected void initNew() throws IgniteCheckedException { @@ -822,6 +829,8 @@ public abstract class BPlusTree<L, T extends L> { * @throws IgniteCheckedException If failed. */ public T removeCeil(L row) throws IgniteCheckedException { + assert row != null; + return remove(row, true); } @@ -831,10 +840,20 @@ public abstract class BPlusTree<L, T extends L> { * @throws IgniteCheckedException If failed. */ public T remove(L row) throws IgniteCheckedException { + assert row != null; + return remove(row, false); } /** + * @return Removed row. + * @throws IgniteCheckedException If failed. + */ + public T removeFirst() throws IgniteCheckedException { + return remove(null, false); // TODO + } + + /** * @param row Lookup row. * @param ceil If we can remove ceil row when we can not find exact. * @return Removed row. http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java index 01dfe1b..62b72eb 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/io/PageIO.java @@ -59,6 +59,12 @@ public abstract class PageIO { public static final short T_FREE_INNER = 6; /** */ + public static final short T_REUSE_LEAF = 7; + + /** */ + public static final short T_REUSE_INNER = 8; + + /** */ private final int ver; /** */ http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/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 new file mode 100644 index 0000000..48d0b7c --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseList.java @@ -0,0 +1,73 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.processors.cache.database.tree.reuse; + +import java.util.concurrent.ThreadLocalRandom; +import org.apache.ignite.IgniteCheckedException; +import org.apache.ignite.internal.pagemem.FullPageId; +import org.apache.ignite.internal.pagemem.PageMemory; +import org.apache.ignite.internal.processors.cache.GridCacheContext; +import org.apache.ignite.internal.processors.cache.database.MetadataStorage; +import org.apache.ignite.lang.IgniteBiTuple; + +/** + * Reuse list for index pages. + */ +public class ReuseList { + /** */ + private final ReuseTree[] trees = new ReuseTree[16]; + + /** */ + private final GridCacheContext<?,?> cctx; + + /** + * @param cctx Cache context. + * @throws IgniteCheckedException If failed. + */ + public ReuseList(GridCacheContext<?,?> cctx) throws IgniteCheckedException { + this.cctx = cctx; + + PageMemory pageMem = cctx.shared().database().pageMemory(); + + MetadataStorage metaStore = cctx.shared().database().meta(); + + for (int i = 0; i < trees.length; i++) { + String idxName = i + "##" + cctx.cacheId() + "_reuse"; + + IgniteBiTuple<FullPageId,Boolean> t = metaStore.getOrAllocateForIndex(cctx.cacheId(), idxName); + + trees[i] = new ReuseTree(cctx.cacheId(), pageMem, t.get1(), t.get2()); + } + } + + /** + * @return Page ID. + * @throws IgniteCheckedException If failed. + */ + public FullPageId take() throws IgniteCheckedException { + return trees[ThreadLocalRandom.current().nextInt(trees.length)].removeFirst(); + } + + /** + * @param fullPageId Page ID. + * @throws IgniteCheckedException If failed. + */ + public void put(FullPageId fullPageId) throws IgniteCheckedException { + trees[ThreadLocalRandom.current().nextInt(trees.length)].put(fullPageId); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/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 new file mode 100644 index 0000000..0a5c0e2 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/ReuseTree.java @@ -0,0 +1,88 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.processors.cache.database.tree.reuse; + +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.tree.BPlusTree; +import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.PageIO; +import org.apache.ignite.internal.processors.cache.database.tree.reuse.io.ReuseInnerIO; +import org.apache.ignite.internal.processors.cache.database.tree.reuse.io.ReuseLeafIO; + +/** + * Reuse tree for index pages. + */ +public class ReuseTree extends BPlusTree<FullPageId, FullPageId> { + /** + * @param cacheId Cache ID. + * @param pageMem Page memory. + * @param metaPageId Meta page ID. + * @param initNew Initialize new index. + * @throws IgniteCheckedException If failed. + */ + public ReuseTree(int cacheId, PageMemory pageMem, FullPageId metaPageId, boolean initNew) throws IgniteCheckedException { + super(cacheId, pageMem, metaPageId); + + if (initNew) + initNew(); + } + + /** {@inheritDoc} */ + @Override protected BPlusIO<FullPageId> io(int type, int ver) { + if (type == PageIO.T_REUSE_INNER) + return ReuseInnerIO.VERSIONS.forVersion(ver); + + assert type == PageIO.T_REUSE_LEAF: type; + + return ReuseLeafIO.VERSIONS.forVersion(ver); + } + + /** {@inheritDoc} */ + @Override protected BPlusInnerIO<FullPageId> latestInnerIO() { + return ReuseInnerIO.VERSIONS.latest(); + } + + /** {@inheritDoc} */ + @Override protected BPlusLeafIO<FullPageId> latestLeafIO() { + return ReuseLeafIO.VERSIONS.latest(); + } + + /** {@inheritDoc} */ + @Override protected int compare(BPlusIO<FullPageId> io, ByteBuffer buf, int idx, FullPageId fullPageId) + throws IgniteCheckedException { + long pageIdx = io.isLeaf() ? + PageIdUtils.pageIdx(((ReuseLeafIO)io).getPageId(buf, idx)) : + (((ReuseInnerIO)io).getPageIndex(buf, idx) & 0xFFFFFFFFL ); + + return Long.compare(pageIdx, PageIdUtils.pageIdx(fullPageId.pageId())); + } + + /** {@inheritDoc} */ + @Override protected FullPageId getRow(BPlusIO<FullPageId> io, ByteBuffer buf, int idx) + throws IgniteCheckedException { + assert io.isLeaf(); + + return new FullPageId(((ReuseLeafIO)io).getPageId(buf, idx) , cacheId); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/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 new file mode 100644 index 0000000..b09e29b --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseInnerIO.java @@ -0,0 +1,84 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.processors.cache.database.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; +import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusInnerIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; + +/** + * Reuse list inner page IO routines. + */ +public class ReuseInnerIO extends BPlusInnerIO<FullPageId> { + /** */ + public static final IOVersions<ReuseInnerIO> VERSIONS = new IOVersions<>( + new ReuseInnerIO(1) + ); + + /** + * @param ver Page format version. + */ + protected ReuseInnerIO(int ver) { + super(T_REUSE_INNER, ver, false, 4); + } + + /** {@inheritDoc} */ + @Override public void store(ByteBuffer dst, int dstIdx, BPlusIO<FullPageId> srcIo, ByteBuffer src, int srcIdx) { + int pageIdx = srcIo.isLeaf() ? + (int)PageIdUtils.pageIdx(((ReuseLeafIO)srcIo).getPageId(src, srcIdx)) : + ((ReuseInnerIO)srcIo).getPageIndex(src, srcIdx); + + store(dst, dstIdx, pageIdx); + } + + /** + * @param buf Buffer. + * @param idx Item index. + * @return Page number. + */ + public int getPageIndex(ByteBuffer buf, int idx) { + return buf.getInt(offset(idx, SHIFT_LINK)); + } + + /** + * @param buf Buffer. + * @param idx Index. + * @param pageIdx Page index. + */ + private void store(ByteBuffer buf, int idx, int pageIdx) { + buf.putInt(offset(idx, SHIFT_LINK), pageIdx); + } + + /** {@inheritDoc} */ + @Override public void store(ByteBuffer buf, int idx, FullPageId fullPageId) { + store(buf, idx, (int)PageIdUtils.pageIdx(fullPageId.pageId())); + } + + /** {@inheritDoc} */ + @Override public FullPageId getLookupRow(BPlusTree<FullPageId,?> tree, ByteBuffer buf, int idx) + throws IgniteCheckedException { + int pageIdx = getPageIndex(buf, idx); + + return new FullPageId(PageIdUtils.pageId(0, pageIdx), tree.getCacheId()); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/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 new file mode 100644 index 0000000..69d08c9 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/database/tree/reuse/io/ReuseLeafIO.java @@ -0,0 +1,62 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.processors.cache.database.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.BPlusLeafIO; +import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; + +/** + * Reuse list leaf page IO routines. + */ +public class ReuseLeafIO extends BPlusLeafIO<FullPageId> { + /** */ + public static final IOVersions<ReuseLeafIO> VERSIONS = new IOVersions<>( + new ReuseLeafIO(1) + ); + + /** + * @param ver Page format version. + */ + protected ReuseLeafIO(int ver) { + super(T_REUSE_LEAF, ver, 8); + } + + /** {@inheritDoc} */ + @Override public void store(ByteBuffer buf, int idx, FullPageId fullPageId) { + buf.putLong(offset(idx), fullPageId.pageId()); + } + + /** + * @param buf Buffer. + * @param idx Index. + * @return Page ID. + */ + public long getPageId(ByteBuffer buf, int idx) { + return buf.getLong(offset(idx)); + } + + /** {@inheritDoc} */ + @Override public FullPageId getLookupRow(BPlusTree<FullPageId,?> tree, ByteBuffer buf, int idx) + throws IgniteCheckedException { + return new FullPageId(getPageId(buf, idx), tree.getCacheId()); + } +} http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java index 8eccfd6..6d61bd7 100644 --- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java +++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/FreeTree.java @@ -93,11 +93,4 @@ public class FreeTree extends BPlusTree<FreeItem, FreeItem> { return row; } - - /** - * @return Cache ID. - */ - public int cacheId() { - return cacheId; - } } http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java index 4c6babe..ee71f18 100644 --- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java +++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/freelist/io/FreeLeafIO.java @@ -18,11 +18,10 @@ package org.apache.ignite.internal.processors.query.h2.database.freelist.io; import java.nio.ByteBuffer; -import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeItem; -import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeTree; import org.apache.ignite.internal.processors.cache.database.tree.BPlusTree; import org.apache.ignite.internal.processors.cache.database.tree.io.BPlusLeafIO; import org.apache.ignite.internal.processors.cache.database.tree.io.IOVersions; +import org.apache.ignite.internal.processors.query.h2.database.freelist.FreeItem; /** * Routines for free list leaf pages. @@ -66,7 +65,6 @@ public class FreeLeafIO extends BPlusLeafIO<FreeItem> implements FreeIO { @Override public FreeItem getLookupRow(BPlusTree<FreeItem, ?> tree, ByteBuffer buf, int idx) { int off = offset(idx); - return new FreeItem(buf.getShort(off), buf.getShort(off + 2), buf.getLong(off + 4), - ((FreeTree)tree).cacheId()); + return new FreeItem(buf.getShort(off), buf.getShort(off + 2), buf.getLong(off + 4), tree.getCacheId()); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/4282d802/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/IgniteDbSingleNodePutGetSelfTest.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/IgniteDbSingleNodePutGetSelfTest.java b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/IgniteDbSingleNodePutGetSelfTest.java index c8eb08e..7570f80 100644 --- a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/IgniteDbSingleNodePutGetSelfTest.java +++ b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/database/IgniteDbSingleNodePutGetSelfTest.java @@ -478,7 +478,7 @@ public class IgniteDbSingleNodePutGetSelfTest extends GridCommonAbstractTest { } } - public void testRandomPutGetRemove() { + public void _testRandomPutGetRemove() { IgniteEx ig = grid(0); final IgniteCache<Integer, DbValue> cache = ig.cache(null);
