ignite-db - wip mm+
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/42ac3b3b Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/42ac3b3b Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/42ac3b3b Branch: refs/heads/ignite-db-x-10884 Commit: 42ac3b3bdcd8b5d6fe00774c9cf950ab01c356ea Parents: 74dfb8f Author: S.Vladykin <[email protected]> Authored: Tue Apr 26 03:36:14 2016 +0300 Committer: S.Vladykin <[email protected]> Committed: Tue Apr 26 03:36:14 2016 +0300 ---------------------------------------------------------------------- .../ignite/internal/pagemem/impl/PageImpl.java | 2 +- .../cache/database/tree/BPlusTree.java | 148 +++++++++--- .../processors/database/BPlusTreeSelfTest.java | 240 +++++++------------ 3 files changed, 196 insertions(+), 194 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/42ac3b3b/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 9f42d93..1e1fb78 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 @@ -243,7 +243,7 @@ class PageImpl extends AbstractQueuedSynchronizer implements Page { boolean releaseReference() { int refs = refCntUpd.decrementAndGet(this); - assert refs >= 0; + assert refs >= 0: fullId.pageId(); return refs == 0; } http://git-wip-us.apache.org/repos/asf/ignite/blob/42ac3b3b/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 a24c38a..848d167 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 @@ -41,6 +41,7 @@ import org.apache.ignite.internal.processors.cache.database.tree.util.PageHandle 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.U; import static org.apache.ignite.internal.processors.cache.database.tree.util.PageHandler.readPage; @@ -1254,8 +1255,8 @@ public abstract class BPlusTree<L, T extends L> { assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; - // TODO race on go down? - if (p.needReplaceInner == TRUE) { // Need to replace ref in inner page. + // Need to replace key in inner page. There is no race because we keep tail lock after split. + if (p.needReplaceInner == TRUE) { p.needReplaceInner = FALSE; // Protect from retries. res = writePage(page, replace, p, lvl, Put.RETRY); @@ -1665,6 +1666,50 @@ public abstract class BPlusTree<L, T extends L> { } /** + * @throws IgniteCheckedException If failed. + */ + private void mergeEmptyBranch() throws IgniteCheckedException { + Tail<L> t = tail; + + assert t.getCount() > 0; + + boolean leaf = false; + + // Find empty branch beginning. + for (Tail<L> t0 = t.down; t0 != null; t0 = t0.down) { + assert t0.type == Tail.EXACT: t0.type; + + if (t0.getCount() != 0) + t = t0; + + leaf = t0.lvl == 0; + } + + if (!leaf) // Can not merge empty branches in the middle of tree. + return; + + while (t.lvl != 0) { // If we've found empty branch, merge it top down. + boolean res = merge(t, true); + + assert res; + + t = t.down; + } + } + + /** + * @param t Tail. + * @return {@code true} If merged successfully or end reached. + * @throws IgniteCheckedException + */ + private boolean mergeDown(Tail<L> t) throws IgniteCheckedException { + if (t.down == null || t.down.sibling == null) + return true; + + return mergeDown(t.down) && merge(t, false); + } + + /** * Process tail and finish. * * @return {@code false} If failed to finish and we need to lock more pages up. @@ -1675,12 +1720,12 @@ public abstract class BPlusTree<L, T extends L> { assert tail.type == Tail.EXACT; // Need to lock more. - if (tail.down == null || needReplaceInner == TRUE || tail.io.getCount(tail.buf) == 0) + if (tail.down == null || needReplaceInner == TRUE || tail.getCount() == 0) return false; - // Merge from the top to the bottom. - for (Tail<L> t = tail; t.down != null; t = t.down) - merge(t); + mergeEmptyBranch(); + + boolean mergeMore = mergeDown(tail); if (needReplaceInner == READY) { // Need to replace inner key with new max key for the left subtree. @@ -1689,11 +1734,15 @@ public abstract class BPlusTree<L, T extends L> { needReplaceInner = DONE; } -// if (cnt == 0 && lvl != 0 && getRootLevel(meta) == lvl) TODO -// freePage(page, buf, io, lvl); // Free root. + if (tail.getCount() == 0 && tail.lvl != 0 && getRootLevel(meta) == tail.lvl) + freePage(tail.page, tail.buf, tail.io, tail.lvl, false); // Free root. + else if (mergeMore) { + doReleaseTail(tail.down); -// if (needMergeMore) -// return false; + tail.down = null; + + return false; + } releaseTail(); finish(); @@ -1819,32 +1868,37 @@ public abstract class BPlusTree<L, T extends L> { * @param prnt Parent tail. * @param left Left child tail. * @param right Right child tail. + * @param emptyBranch If we are merging an empty branch. * @return {@code true} If merged successfully. * @throws IgniteCheckedException If failed. */ - private boolean mergePages(Tail<L> prnt, Tail<L> left, Tail<L> right) throws IgniteCheckedException { + private boolean doMerge(Tail<L> prnt, Tail<L> left, Tail<L> right, boolean emptyBranch) + throws IgniteCheckedException { assert right.io == left.io; // Otherwise incompatible. assert left.io.getForward(left.buf) == right.page.id(); - int prntCnt = prnt.io.getCount(prnt.buf); - int backCnt = left.io.getCount(left.buf); - int curCnt = right.io.getCount(right.buf); + int prntCnt = prnt.getCount(); + int leftCnt = left.getCount(); + int rightCnt = right.getCount(); assert prntCnt > 0: prntCnt; - int newCnt = backCnt + curCnt; + int newCnt = leftCnt + rightCnt; - // Need to move down split key in inner pages, but for the last key it will be a special case merge. - if (left.lvl != 0 && false) // TODO + // Need to move down split key in inner pages. For empty branch merge parent key will be just dropped. + if (left.lvl != 0 && !emptyBranch) newCnt++; - if (newCnt > left.io.getMaxCount(left.buf)) + if (newCnt > left.io.getMaxCount(left.buf)) { + assert !emptyBranch; + return false; + } left.io.setCount(left.buf, newCnt); // Move down split key in inner pages. - if (left.lvl != 0) { + if (left.lvl != 0 && !emptyBranch) { int prntIdx = prnt.idx; if (prntIdx == prntCnt) // It was a right turn. @@ -1852,22 +1906,24 @@ public abstract class BPlusTree<L, T extends L> { // We can be sure that we have enough free space to store split key here, // because we've done remove already and did not release child locks. - left.io.store(left.buf, backCnt, prnt.io, prnt.buf, prntIdx); + left.io.store(left.buf, leftCnt, prnt.io, prnt.buf, prntIdx); - backCnt++; + leftCnt++; } - left.io.copyItems(right.buf, left.buf, 0, backCnt, curCnt, true); + left.io.copyItems(right.buf, left.buf, 0, leftCnt, rightCnt, !emptyBranch || rightCnt != 0); left.io.setForward(left.buf, right.io.getForward(right.buf)); // Fix index for the right move: remove last item. + // For the empty branch we always remove the last item, because we always drop right child after merge. int prntIdx = prnt.idx == prntCnt ? prntCnt - 1 : prnt.idx; - // Remove split key from parent. - doRemove(prnt.io, prnt.buf, prntCnt, prntIdx); + // Remove split key from parent. Index -1 means that it is not actually our parent and we should not remove. + if (prntIdx != -1) + doRemove(prnt.io, prnt.buf, prntCnt, prntIdx); - // Forward page is now empty and has no links. - freePage(right.page, right.buf, right.io, right.lvl); + // 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); return true; } @@ -1877,9 +1933,10 @@ public abstract class BPlusTree<L, T extends L> { * @param buf Buffer. * @param io IO. * @param lvl Level. + * @param release Release write lock and release page. * @throws IgniteCheckedException If failed. */ - private void freePage(Page page, ByteBuffer buf, BPlusIO io, int lvl) + private void freePage(Page page, ByteBuffer buf, BPlusIO io, int lvl, boolean release) throws IgniteCheckedException { if (getFirstPageId(meta, lvl) == page.id()) { // This logic will handle root as well. @@ -1900,7 +1957,8 @@ public abstract class BPlusTree<L, T extends L> { emptyPages.add(page.fullId()); - writeUnlockAndClose(page); + if (release) + writeUnlockAndClose(page); } /** @@ -1925,31 +1983,32 @@ public abstract class BPlusTree<L, T extends L> { Tail<L> inner = tail; assert inner.type == Tail.EXACT: inner.type; - assert innerIdx < inner.io.getCount(inner.buf); + assert innerIdx < inner.getCount(); - int cnt = leaf.io.getCount(leaf.buf); + int cnt = leaf.getCount(); assert cnt > 0: cnt; // Leaf must be merged at this point already if it was empty. - if (innerIdx < inner.io.getCount(inner.buf)) { + if (innerIdx < inner.getCount()) { // Update inner key with the new biggest key of left subtree. inner.io.store(inner.buf, innerIdx, leaf.io, leaf.buf, cnt - 1); leaf.io.setRemoveId(leaf.buf, globalRmvId.get()); } else { // If after leaf merge parent have lost inner key, we don't need to update it anymore. - assert innerIdx == inner.io.getCount(inner.buf); + assert innerIdx == inner.getCount(); assert inner(inner.io).getLeft(inner.buf, innerIdx) == leaf.page.id(); } } /** * @param prnt Parent for merge. + * @param emptyBranch If we are merging an empty branch. * @return {@code true} If merged, {@code false} if not (because of insufficient space or empty parent). * @throws IgniteCheckedException If failed. */ - private boolean merge(Tail<L> prnt) throws IgniteCheckedException { - if (prnt.io.getCount(prnt.buf) == 0) + private boolean merge(Tail<L> prnt, boolean emptyBranch) throws IgniteCheckedException { + if (prnt.getCount() == 0) return false; // Parent is an empty routing page, child forward page will have another parent. Tail<L> right = prnt.down; @@ -1967,7 +2026,7 @@ public abstract class BPlusTree<L, T extends L> { assert right.io == left.io: "must always be the same"; // Otherwise can be not compatible. - if (!mergePages(prnt, left, right)) + if (!doMerge(prnt, left, right, emptyBranch)) return false; // left from BACK becomes EXACT. @@ -1998,10 +2057,15 @@ public abstract class BPlusTree<L, T extends L> { * Release pages for all locked levels at the tail. */ private void releaseTail() { - Tail t = tail; + doReleaseTail(tail); tail = null; + } + /** + * @param t Tail. + */ + private void doReleaseTail(Tail<L> t) { while (t != null) { writeUnlockAndClose(t.page); @@ -2162,6 +2226,18 @@ public abstract class BPlusTree<L, T extends L> { this.lvl = (byte)lvl; this.idx = (short)idx; } + + /** + * @return Count. + */ + private int getCount() { + return io.getCount(buf); + } + + /** {@inheritDoc} */ + @Override public String toString() { + return S.toString(Tail.class, this, "pageId", page.id(), "cnt", getCount()); + } } /** http://git-wip-us.apache.org/repos/asf/ignite/blob/42ac3b3b/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 6dcb237..de2ca10 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 @@ -61,7 +61,10 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { private static final int CACHE_ID = 100500; /** */ - private static int MAX_COUNT = 0; + private static int MAX_ITEMS_COUNT = 0; + + /** */ + private static int CNT = 10; /** */ private static int PUT_INC = 1; @@ -75,6 +78,11 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** */ private ReuseList reuseList; + @Override + protected long getTestTimeout() { + return 25 * 60 * 1000; + } + /** {@inheritDoc} */ @Override protected void beforeTest() throws Exception { long seed = System.nanoTime(); @@ -99,233 +107,151 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { @Override protected void afterTest() throws Exception { pageMem.stop(); - MAX_COUNT = 0; + MAX_ITEMS_COUNT = 0; PUT_INC = 1; RMV_INC = -1; + CNT = 10; } /** * @throws IgniteCheckedException If failed. */ - public void testSingle1() throws IgniteCheckedException { - MAX_COUNT = 1; + public void testPutRemove_1_10_mm_1() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; PUT_INC = -1; RMV_INC = -1; - doTestPutRemoveForwardBackward(true); + doTestPutRemove(true); } /** - * @param canGetRow Can get row from inner page. * @throws IgniteCheckedException If failed. */ - private void doTestPutRemoveForwardBackward(boolean canGetRow) throws IgniteCheckedException { - TestTree tree = createTestTree(canGetRow); - - long cnt = 10; - - for (long x = PUT_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += PUT_INC) { - assertNull(tree.findOne(x)); - - tree.put(x); - - assertEquals(x, tree.findOne(x).longValue()); - } - - X.println(tree.printTree()); - - assertNull(tree.findOne(-1L)); - - for (long x = 0; x < cnt; x++) - assertEquals(x, tree.findOne(x).longValue()); - - assertNull(tree.findOne(cnt)); - - for (long x = RMV_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += RMV_INC) { - X.println(" -- " + x); - - assertEquals(x, tree.remove(x).longValue()); - - assertNull(tree.findOne(x)); - - X.println(tree.printTree()); - } + public void testPutRemove_1_10_mm_0() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = -1; + RMV_INC = -1; - assertFalse(tree.find(null, null).next()); + doTestPutRemove(false); } /** * @throws IgniteCheckedException If failed. */ - public void testPutFindRemoveForward0() throws IgniteCheckedException { - doTestPutFindRemoveForward(false); - } + public void testPutRemove_1_10_pm_1() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = 1; + RMV_INC = -1; - /** - * @throws IgniteCheckedException If failed. - */ - public void testPutFindRemoveForward1() throws IgniteCheckedException { - doTestPutFindRemoveForward(true); + doTestPutRemove(true); } /** - * @param canGetRow Can get row from inner page. * @throws IgniteCheckedException If failed. */ - private void doTestPutFindRemoveForward(boolean canGetRow) throws IgniteCheckedException { - TestTree tree = createTestTree(canGetRow); - - long cnt = 100_000; - - for (long x = 0; x < cnt; x++) { - assertNull(tree.findOne(x)); - - tree.put(x); - - assertEquals(x, tree.findOne(x).longValue()); - } - - assertNull(tree.findOne(-1L)); - - for (long x = 0; x < cnt; x++) - assertEquals(x, tree.findOne(x).longValue()); - - assertNull(tree.findOne(cnt)); - - for (long x = 0; x < cnt; x++) { - assertEquals(x, tree.remove(x).longValue()); - - assertNull(tree.findOne(x)); - } + public void testPutRemove_1_10_pm_0() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = 1; + RMV_INC = -1; - assertFalse(tree.find(null, null).next()); + doTestPutRemove(false); } /** * @throws IgniteCheckedException If failed. */ - public void testPutRemoveFindBackward0() throws IgniteCheckedException { - doTestPutFindRemoveBackward(false); - } + public void testPutRemove_1_10_pp_1() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = 1; + RMV_INC = 1; - /** - * @throws IgniteCheckedException If failed. - */ - public void testPutRemoveFindBackward1() throws IgniteCheckedException { - doTestPutFindRemoveBackward(true); + doTestPutRemove(true); } /** - * @param canGetRow Can get row from inner page. * @throws IgniteCheckedException If failed. */ - private void doTestPutFindRemoveBackward(boolean canGetRow) throws IgniteCheckedException { - TestTree tree = createTestTree(canGetRow); - - long cnt = 100_000; - - for (long x = cnt - 1; x >= 0; x--) { - assertNull(tree.findOne(x)); - - tree.put(x); - - assertEquals(x, tree.findOne(x).longValue()); - } - - assertNull(tree.findOne(cnt)); - - for (long x = cnt - 1; x >= 0; x--) - assertEquals(x, tree.findOne(x).longValue()); - - assertNull(tree.findOne(-1L)); - - for (long x = cnt - 1; x >= 0; x--) { - assertEquals(x, tree.remove(x).longValue()); - - assertNull(tree.findOne(x)); - } + public void testPutRemove_1_10_pp_0() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = 1; + RMV_INC = 1; - assertFalse(tree.find(null, null).next()); + doTestPutRemove(false); } /** * @throws IgniteCheckedException If failed. */ - public void testPutRemoveFindRandom0() throws IgniteCheckedException { - doTestPutRemoveFindRandom(false); + public void testPutRemove_1_10_mp_1() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = -1; + RMV_INC = 1; + + doTestPutRemove(true); } /** * @throws IgniteCheckedException If failed. */ - public void testPutRemoveFindRandom1() throws IgniteCheckedException { - doTestPutRemoveFindRandom(true); + public void testPutRemove_1_10_mp_0() throws IgniteCheckedException { + MAX_ITEMS_COUNT = 1; + CNT = 10; + PUT_INC = -1; + RMV_INC = 1; + + doTestPutRemove(false); } /** * @param canGetRow Can get row from inner page. * @throws IgniteCheckedException If failed. */ - private void doTestPutRemoveFindRandom(boolean canGetRow) throws IgniteCheckedException { + private void doTestPutRemove(boolean canGetRow) throws IgniteCheckedException { TestTree tree = createTestTree(canGetRow); - Map<Long,Long> map = new HashMap<>(); - - int cnt = 100_000; - - for (int i = 0, end = 30 * cnt; i < end; i++) { -// if (i % 1000 == 0) -// X.println(" -> " + i); - - long x = tree.randomInt(cnt); - - switch(tree.randomInt(3)) { - case 0: -// X.println("Put: " + x); - - assertEquals(map.put(x, x), tree.put(x)); - - case 1: -// X.println("Get: " + x); - - assertEquals(map.get(x), tree.findOne(x)); + long cnt = 10; - break; + for (long x = PUT_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += PUT_INC) { + assertNull(tree.findOne(x)); - case 2: -// X.println("Rmv: " + x); + tree.put(x); - assertEquals(map.remove(x), tree.remove(x)); + assertEquals(x, tree.findOne(x).longValue()); + } - break; + X.println(tree.printTree()); - default: - fail(); - } - } + assertNull(tree.findOne(-1L)); - assertFalse(map.isEmpty()); + for (long x = 0; x < cnt; x++) + assertEquals(x, tree.findOne(x).longValue()); - for (Long x : map.keySet()) - assertEquals(map.get(x), tree.findOne(x)); + assertNull(tree.findOne(cnt)); - GridCursor<Long> cursor = tree.find(null, null); + for (long x = RMV_INC > 0 ? 0 : cnt - 1; x >= 0 && x < cnt; x += RMV_INC) { + X.println(" -- " + x); - while (cursor.next()) { - Long x = cursor.get(); + assertEquals(x, tree.remove(x).longValue()); - assert x != null; + X.println(tree.printTree()); - assertEquals(map.remove(x), x); + assertNull(tree.findOne(x)); } - assertTrue(map.isEmpty()); + assertFalse(tree.find(null, null).next()); } /** * @throws IgniteCheckedException If failed. */ - public void testRandomRemove0() throws IgniteCheckedException { + public void _testRandomRemove0() throws IgniteCheckedException { // seed: 1461177795261173000, 1461187841179332000 doTestRandomRemove(false); } @@ -333,7 +259,7 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** * @throws IgniteCheckedException If failed. */ - public void testRandomRemove1() throws IgniteCheckedException { + public void _testRandomRemove1() throws IgniteCheckedException { // seed: 1461188744119034000 1461188844311788000 1461189099834526000 doTestRandomRemove(true); } @@ -519,8 +445,8 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** {@inheritDoc} */ @Override public int getMaxCount(ByteBuffer buf) { - if (MAX_COUNT != 0) - return MAX_COUNT; + if (MAX_ITEMS_COUNT != 0) + return MAX_ITEMS_COUNT; return super.getMaxCount(buf); } @@ -558,8 +484,8 @@ public class BPlusTreeSelfTest extends GridCommonAbstractTest { /** {@inheritDoc} */ @Override public int getMaxCount(ByteBuffer buf) { - if (MAX_COUNT != 0) - return MAX_COUNT; + if (MAX_ITEMS_COUNT != 0) + return MAX_ITEMS_COUNT; return super.getMaxCount(buf); }
