Repository: ignite Updated Branches: refs/heads/ignite-3477-putdown [created] 75ecc8847
ignite-3477 Put optimization. Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/75ecc884 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/75ecc884 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/75ecc884 Branch: refs/heads/ignite-3477-putdown Commit: 75ecc8847e25012376f7a4c9cf7580ab9d793b07 Parents: bac9b69 Author: sboikov <sboi...@gridgain.com> Authored: Fri Feb 3 12:59:23 2017 +0300 Committer: sboikov <sboi...@gridgain.com> Committed: Fri Feb 3 12:59:23 2017 +0300 ---------------------------------------------------------------------- .../cache/database/tree/BPlusTree.java | 246 +++++++++++++------ 1 file changed, 173 insertions(+), 73 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/75ecc884/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 a0dff8c..2976995 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 @@ -279,47 +279,111 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements return NOT_FOUND; } - assert !io.isLeaf() : io; + return searchDown(pageAddr, io, g, needBackIfRouting, cnt, idx); + } + }; + + /** + * @param pageAddr Page address. + * @param io Page IO. + * @param g Operation. + * @param needBackIfRouting Need back flag. + * @param cnt Page items count. + * @param idx Insertion point index. + * @return Result. + * @throws IgniteCheckedException If failed. + */ + private Result searchDown(long pageAddr, BPlusIO<L> io, Get g, boolean needBackIfRouting, int cnt, int idx) + throws IgniteCheckedException { + assert !io.isLeaf() : io; - // If idx == cnt then we go right down, else left down: getLeft(cnt) == getRight(cnt - 1). - g.pageId = inner(io).getLeft(pageAddr, idx); + // If idx == cnt then we go right down, else left down: getLeft(cnt) == getRight(cnt - 1). + g.pageId = inner(io).getLeft(pageAddr, idx); - // If we see the tree in consistent state, then our right down page must be forward for our left down page, - // we need to setup fwdId and/or backId to be able to check this invariant on lower level. - if (idx < cnt) { - // Go left down here. - g.fwdId = inner(io).getRight(pageAddr, idx); - } + // If we see the tree in consistent state, then our right down page must be forward for our left down page, + // we need to setup fwdId and/or backId to be able to check this invariant on lower level. + if (idx < cnt) { + // Go left down here. + g.fwdId = inner(io).getRight(pageAddr, idx); + } + else { + // Go right down here or it is an empty branch. + assert idx == cnt; + + // Here child's forward is unknown to us (we either go right or it is an empty "routing" page), + // need to ask our forward about the child's forward (it must be leftmost child of our forward page). + // This is ok from the locking standpoint because we take all locks in the forward direction. + long fwdId = io.getForward(pageAddr); + + // Setup fwdId. + if (fwdId == 0) + g.fwdId = 0; else { - // Go right down here or it is an empty branch. - assert idx == cnt; + // We can do askNeighbor on forward page here because we always take locks in forward direction. + Result res = askNeighbor(fwdId, g, false); - // Here child's forward is unknown to us (we either go right or it is an empty "routing" page), - // need to ask our forward about the child's forward (it must be leftmost child of our forward page). - // This is ok from the locking standpoint because we take all locks in the forward direction. - long fwdId = io.getForward(pageAddr); + if (res != FOUND) { + assert res == RETRY || res == RETRY_ROOT : res; - // Setup fwdId. - if (fwdId == 0) - g.fwdId = 0; - else { - // We can do askNeighbor on forward page here because we always take locks in forward direction. - Result res = askNeighbor(fwdId, g, false); + return res; // Retry. + } + } - if (res != FOUND) - return res; // Retry. + // Setup backId. + if (cnt != 0) // It is not a routing page and we are going to the right, can get backId here. + g.backId = inner(io).getLeft(pageAddr, cnt - 1); + else if (needBackIfRouting) { + // Can't get backId here because of possible deadlock and it is only needed for remove operation. + return GO_DOWN_X; + } + } + + return GO_DOWN; + } + + /** */ + private final GetPageHandler<Get> searchAndWrite = new SearchAndWrite(); + + /** + * + */ + private class SearchAndWrite extends Search { + /** {@inheritDoc} */ + @Override public Result run0(Page page, long pageAddr, BPlusIO<L> io, Get g, int lvl) + throws IgniteCheckedException { + Put p = (Put)g; + + if (io.getForward(pageAddr) != g.fwdId) + return RETRY; + + boolean needBackIfRouting = g.backId != 0; + + int cnt = io.getCount(pageAddr); + int idx = findInsertionPoint(io, pageAddr, 0, cnt, g.row, g.shift); + + boolean found = idx >= 0; + + if (found) { + if (g.found(io, pageAddr, idx, lvl)) { + doReplace(page, pageAddr, io, p, lvl, idx); + + return FOUND; } + } + else { + if (g.notFound(io, pageAddr, idx, lvl)) { + if (idx >= 0) // We do not support concurrent put of the same key. + throw new IllegalStateException("Duplicate row in index."); - // Setup backId. - if (cnt != 0) // It is not a routing page and we are going to the right, can get backId here. - g.backId = inner(io).getLeft(pageAddr, cnt - 1); - else if (needBackIfRouting) { - // Can't get backId here because of possible deadlock and it is only needed for remove operation. - return GO_DOWN_X; + idx = fix(idx); + + doInsert(page, pageAddr, io, p, lvl, idx); + + return FOUND; } } - return GO_DOWN; + return searchDown(pageAddr, io, g, needBackIfRouting, cnt, idx); } }; @@ -345,31 +409,46 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements if (idx < 0) // Not found, split or merge happened. return RETRY; - // Replace link at idx with new one. - // Need to read link here because `p.finish()` will clear row. - L newRow = p.row; + return doReplace(page, pageAddr, io, p, lvl, idx); + } + }; - // Detach the old row if we are on a leaf page. - if (lvl == 0) { - assert p.oldRow == null; + /** + * @param page Page. + * @param pageAddr Page address. + * @param io Page IO. + * @param p Operation. + * @param lvl Level. + * @param idx Insertion point index. + * @return Result. + * @throws IgniteCheckedException If failed. + */ + private Result doReplace(Page page, long pageAddr, BPlusIO<L> io, Put p, int lvl, int idx) + throws IgniteCheckedException { + // Replace link at idx with new one. + // Need to read link here because `p.finish()` will clear row. + L newRow = p.row; - // Get old row in leaf page to reduce contention at upper level. - p.oldRow = p.needOld ? getRow(io, pageAddr, idx) : (T)Boolean.TRUE; + // Detach the old row if we are on a leaf page. + if (lvl == 0) { + assert p.oldRow == null; - p.finish(); + // Get old row in leaf page to reduce contention at upper level. + p.oldRow = p.needOld ? getRow(io, pageAddr, idx) : (T)Boolean.TRUE; - // Inner replace state must be consistent by the end of the operation. - assert p.needReplaceInner == FALSE || p.needReplaceInner == DONE : p.needReplaceInner; - } + p.finish(); - io.store(pageAddr, idx, newRow, null); + // Inner replace state must be consistent by the end of the operation. + assert p.needReplaceInner == FALSE || p.needReplaceInner == DONE : p.needReplaceInner; + } - if (needWalDeltaRecord(page)) - wal.log(new ReplaceRecord<>(cacheId, page.id(), io, newRow, null, idx)); + io.store(pageAddr, idx, newRow, null); - return FOUND; - } - }; + if (needWalDeltaRecord(page)) + wal.log(new ReplaceRecord<>(cacheId, page.id(), io, newRow, null, idx)); + + return FOUND; + } /** */ private final GetPageHandler<Put> insert = new Insert(); @@ -395,27 +474,42 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements idx = fix(idx); - // Do insert. - L moveUpRow = p.insert(page, io, pageAddr, idx, lvl); + return doInsert(page, pageAddr, io, p, lvl, idx); + } + }; - // Check if split happened. - if (moveUpRow != null) { - p.btmLvl++; // Get high. - p.row = moveUpRow; + /** + * @param page Page. + * @param pageAddr Page address. + * @param io Page IO. + * @param p Operation. + * @param lvl Level. + * @param idx Insertion point index. + * @return Result. + * @throws IgniteCheckedException If failed. + */ + private Result doInsert(Page page, long pageAddr, BPlusIO<L> io, Put p, int lvl, int idx) + throws IgniteCheckedException { + // Do insert. + L moveUpRow = p.insert(page, io, pageAddr, idx, lvl); - // Here forward page can't be concurrently removed because we keep write lock on tail which is the only - // page who knows about the forward page, because it was just produced by split. - p.rightId = io.getForward(pageAddr); - p.tail(page, pageAddr); + // Check if split happened. + if (moveUpRow != null) { + p.btmLvl++; // Get high. + p.row = moveUpRow; - assert p.rightId != 0; - } - else - p.finish(); + // Here forward page can't be concurrently removed because we keep write lock on tail which is the only + // page who knows about the forward page, because it was just produced by split. + p.rightId = io.getForward(pageAddr); + p.tail(page, pageAddr); - return FOUND; + assert p.rightId != 0; } - }; + else + p.finish(); + + return FOUND; + } /** */ private final GetPageHandler<Remove> rmvFromLeaf = new RemoveFromLeaf(); @@ -1942,7 +2036,17 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements p.pageId = pageId; p.fwdId = fwdId; - Result res = readPage(page, this, search, p, lvl, RETRY); + Result res; + + if (lvl == 0) { // Optimistically try write lock and update page. + res = writePage(pageMem, page, this, searchAndWrite, p, lvl, RETRY); + + assert res != NOT_FOUND && res != GO_DOWN && res != GO_DOWN_X : res; + + return res; + } + else + res = readPage(page, this, search, p, lvl, RETRY); switch (res) { case GO_DOWN: @@ -1987,20 +2091,16 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements case FOUND: // Do replace. assert lvl == 0 : "This replace can happen only at the bottom level."; - - // Init args. - p.pageId = pageId; - p.fwdId = fwdId; + assert p.pageId == pageId; + assert p.fwdId == fwdId; return writePage(pageMem, page, this, replace, p, lvl, RETRY); case NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; - - // Init args. - p.pageId = pageId; - p.fwdId = fwdId; + assert p.pageId == pageId; + assert p.fwdId == fwdId; return writePage(pageMem, page, this, insert, p, lvl, RETRY);
