You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by ag...@apache.org on 2018/08/30 12:24:31 UTC
[25/45] ignite git commit: IGNITE-4191: MVCC and transactional SQL
support. Joint multi-man-years efforts of Semen Boikov, Igor Seliverstov,
Alexander Paschenko, Igor Sapego, Sergey Kalashnikov, Roman Kondakov,
Pavel Kuznetsov, Ivan Pavlukhin, Andrey Mas
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
index 8a63a00..125bc35 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
@@ -930,12 +930,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param upper Upper bound.
+ * @param c Filter closure.
* @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
* @return Cursor.
* @throws IgniteCheckedException If failed.
*/
- private GridCursor<T> findLowerUnbounded(L upper, Object x) throws IgniteCheckedException {
- ForwardCursor cursor = new ForwardCursor(null, upper, x);
+ private GridCursor<T> findLowerUnbounded(L upper, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
+ ForwardCursor cursor = new ForwardCursor(null, upper, c, x);
long firstPageId;
@@ -953,7 +954,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
long pageAddr = readLock(firstPageId, firstPage); // We always merge pages backwards, the first page is never removed.
try {
- cursor.init(pageAddr, io(pageAddr), 0);
+ cursor.init(pageAddr, io(pageAddr), -1);
}
finally {
readUnlock(firstPageId, firstPage, pageAddr);
@@ -981,13 +982,25 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** {@inheritDoc} */
public final GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException {
+ return find(lower, upper, null, x);
+ }
+
+ /**
+ * @param lower Lower bound inclusive or {@code null} if unbounded.
+ * @param upper Upper bound inclusive or {@code null} if unbounded.
+ * @param c Filter closure.
+ * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ * @return Cursor.
+ * @throws IgniteCheckedException If failed.
+ */
+ public final GridCursor<T> find(L lower, L upper, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
checkDestroyed();
try {
if (lower == null)
- return findLowerUnbounded(upper, x);
+ return findLowerUnbounded(upper, c, x);
- ForwardCursor cursor = new ForwardCursor(lower, upper, x);
+ ForwardCursor cursor = new ForwardCursor(lower, upper, c, x);
cursor.find();
@@ -1004,43 +1017,159 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
}
+ /**
+ * @param lower Lower bound inclusive.
+ * @param upper Upper bound inclusive.
+ * @param c Closure applied for all found items, iteration is stopped if closure returns {@code false}.
+ * @throws IgniteCheckedException If failed.
+ */
+ public void iterate(L lower, L upper, TreeRowClosure<L, T> c) throws IgniteCheckedException {
+ checkDestroyed();
+
+ try {
+ ClosureCursor cursor = new ClosureCursor(lower, upper, c);
+
+ cursor.iterate();
+ }
+ catch (IgniteCheckedException e) {
+ throw new IgniteCheckedException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ catch (RuntimeException e) {
+ throw new IgniteException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ catch (AssertionError e) {
+ throw new AssertionError("Assertion error on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ finally {
+ checkDestroyed();
+ }
+ }
+
+ /**
+ * @param lower Lower bound inclusive.
+ * @param upper Upper bound inclusive.
+ * @param c Closure applied for all found items.
+ * @throws IgniteCheckedException If failed.
+ */
+ public void visit(L lower, L upper, TreeVisitorClosure<L, T> c) throws IgniteCheckedException {
+ checkDestroyed();
+
+ try {
+ new TreeVisitor(lower, upper, c).visit();
+ }
+ catch (IgniteCheckedException e) {
+ throw new IgniteCheckedException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ catch (RuntimeException e) {
+ throw new IgniteException("Runtime failure on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ catch (AssertionError e) {
+ throw new AssertionError("Assertion error on bounds: [lower=" + lower + ", upper=" + upper + "]", e);
+ }
+ finally {
+ checkDestroyed();
+ }
+ }
+
/** {@inheritDoc} */
@Override public T findFirst() throws IgniteCheckedException {
+ return findFirst(null);
+ }
+
+ /**
+ * Returns a value mapped to the lowest key, or {@code null} if tree is empty or no entry matches the passed filter.
+ * @param filter Filter closure.
+ * @return Value.
+ * @throws IgniteCheckedException If failed.
+ */
+ public T findFirst(TreeRowClosure<L, T> filter) throws IgniteCheckedException {
checkDestroyed();
try {
- long firstPageId;
-
- long metaPage = acquirePage(metaPageId);
- try {
- firstPageId = getFirstPageId(metaPageId, metaPage, 0);
- }
- finally {
- releasePage(metaPageId, metaPage);
- }
+ for (;;) {
+ long curPageId;
- long page = acquirePage(firstPageId);
+ long metaPage = acquirePage(metaPageId);
- try {
- long pageAddr = readLock(firstPageId, page);
+ try {
+ curPageId = getFirstPageId(metaPageId, metaPage, 0); // Level 0 is always at the bottom.
+ }
+ finally {
+ releasePage(metaPageId, metaPage);
+ }
+ long curPage = acquirePage(curPageId);
try {
- BPlusIO<L> io = io(pageAddr);
+ long curPageAddr = readLock(curPageId, curPage);
- int cnt = io.getCount(pageAddr);
+ if (curPageAddr == 0)
+ continue; // The first page has gone: restart scan.
- if (cnt == 0)
- return null;
+ try {
+ BPlusIO<L> io = io(curPageAddr);
- return getRow(io, pageAddr, 0);
+ assert io.isLeaf();
+
+ for (;;) {
+ int cnt = io.getCount(curPageAddr);
+
+ for (int i = 0; i < cnt; ++i) {
+ if (filter == null || filter.apply(this, io, curPageAddr, i))
+ return getRow(io, curPageAddr, i);
+ }
+
+ long nextPageId = io.getForward(curPageAddr);
+
+ if (nextPageId == 0)
+ return null;
+
+ long nextPage = acquirePage(nextPageId);
+
+ try {
+ long nextPageAddr = readLock(nextPageId, nextPage);
+
+ // In the current implementation the next page can't change when the current page is locked.
+ assert nextPageAddr != 0 : nextPageAddr;
+
+ try {
+ long pa = curPageAddr;
+ curPageAddr = 0; // Set to zero to avoid double unlocking in finalizer.
+
+ readUnlock(curPageId, curPage, pa);
+
+ long p = curPage;
+ curPage = 0; // Set to zero to avoid double release in finalizer.
+
+ releasePage(curPageId, p);
+
+ curPageId = nextPageId;
+ curPage = nextPage;
+ curPageAddr = nextPageAddr;
+
+ nextPage = 0;
+ nextPageAddr = 0;
+ }
+ finally {
+ if (nextPageAddr != 0)
+ readUnlock(nextPageId, nextPage, nextPageAddr);
+ }
+ }
+ finally {
+ if (nextPage != 0)
+ releasePage(nextPageId, nextPage);
+ }
+ }
+ }
+ finally {
+ if (curPageAddr != 0)
+ readUnlock(curPageId, curPage, curPageAddr);
+ }
}
finally {
- readUnlock(firstPageId, page, pageAddr);
+ if (curPage != 0)
+ releasePage(curPageId, curPage);
}
}
- finally {
- releasePage(firstPageId, page);
- }
}
catch (IgniteCheckedException e) {
throw new IgniteCheckedException("Runtime failure on first row lookup", e);
@@ -1056,13 +1185,26 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** {@inheritDoc} */
@SuppressWarnings("unchecked")
@Override public T findLast() throws IgniteCheckedException {
+ return findLast(null);
+ }
+
+ /**
+ * Returns a value mapped to the greatest key, or {@code null} if tree is empty or no entry matches the passed filter.
+ * @param c Filter closure.
+ * @return Value.
+ * @throws IgniteCheckedException If failed.
+ */
+ public T findLast(final TreeRowClosure<L, T> c) throws IgniteCheckedException {
checkDestroyed();
try {
- GetOne g = new GetOne(null, null, true);
- doFind(g);
+ if (c == null) {
+ GetOne g = new GetOne(null, null, null, true);
+ doFind(g);
- return (T)g.row;
+ return (T)g.row;
+ } else
+ return new GetLast(c).find();
}
catch (IgniteCheckedException e) {
throw new IgniteCheckedException("Runtime failure on last row lookup", e);
@@ -1078,15 +1220,25 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param row Lookup row for exact match.
* @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ * @return Found result or {@code null}
+ * @throws IgniteCheckedException If failed.
+ */
+ public final <R> R findOne(L row, Object x) throws IgniteCheckedException {
+ return findOne(row, null, x);
+ }
+
+ /**
+ * @param row Lookup row for exact match.
+ * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
* @return Found result or {@code null}.
* @throws IgniteCheckedException If failed.
*/
@SuppressWarnings("unchecked")
- public final <R> R findOne(L row, Object x) throws IgniteCheckedException {
+ public final <R> R findOne(L row, TreeRowClosure<L, T> c, Object x) throws IgniteCheckedException {
checkDestroyed();
try {
- GetOne g = new GetOne(row, x, false);
+ GetOne g = new GetOne(row, c, x, false);
doFind(g);
@@ -1110,7 +1262,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
@SuppressWarnings("unchecked")
@Override public final T findOne(L row) throws IgniteCheckedException {
- return findOne(row, null);
+ return findOne(row, null, null);
}
/**
@@ -2388,6 +2540,88 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
}
+
+ /**
+ * @param c Get.
+ * @throws IgniteCheckedException If failed.
+ */
+ private void doVisit(TreeVisitor c) throws IgniteCheckedException {
+ for (;;) { // Go down with retries.
+ c.init();
+
+ switch (visitDown(c, c.rootId, 0L, c.rootLvl)) {
+ case RETRY:
+ case RETRY_ROOT:
+ checkInterrupted();
+
+ continue;
+
+ default:
+ return;
+ }
+ }
+ }
+
+ /**
+ * @param v Tree visitor.
+ * @param pageId Page ID.
+ * @param fwdId Expected forward page ID.
+ * @param lvl Level.
+ * @return Result code.
+ * @throws IgniteCheckedException If failed.
+ */
+ private Result visitDown(final TreeVisitor v, final long pageId, final long fwdId, final int lvl)
+ throws IgniteCheckedException {
+ long page = acquirePage(pageId);
+
+ try {
+ for (;;) {
+ v.checkLockRetry();
+
+ // Init args.
+ v.pageId = pageId;
+ v.fwdId = fwdId;
+
+ Result res = read(pageId, page, search, v, lvl, RETRY);
+
+ switch (res) {
+ case GO_DOWN:
+ case GO_DOWN_X:
+ assert v.pageId != pageId;
+ assert v.fwdId != fwdId || fwdId == 0;
+
+ // Go down recursively.
+ res = visitDown(v, v.pageId, v.fwdId, lvl - 1);
+
+ switch (res) {
+ case RETRY:
+ checkInterrupted();
+
+ continue; // The child page got split, need to reread our page.
+
+ default:
+ return res;
+ }
+
+ case NOT_FOUND:
+ assert lvl == 0 : lvl;
+
+ return v.init(pageId, page, fwdId);
+
+ case FOUND:
+ throw new IllegalStateException(); // Must never be called because we always have a shift.
+
+ default:
+ return res;
+ }
+ }
+ }
+ finally {
+ if (v.canRelease(pageId, lvl))
+ releasePage(pageId, page);
+ }
+ }
+
/**
* @param io IO.
* @param pageAddr Page address.
@@ -2602,15 +2836,20 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** */
Object x;
+ /** */
+ TreeRowClosure<L, T> c;
+
/**
* @param row Row.
+ * @param c Closure filter.
* @param x Implementation specific argument.
* @param findLast Ignore row passed, find last row
*/
- private GetOne(L row, Object x, boolean findLast) {
+ private GetOne(L row, TreeRowClosure<L,T> c, Object x, boolean findLast) {
super(row, findLast);
this.x = x;
+ this.c = c;
}
/** {@inheritDoc} */
@@ -2620,7 +2859,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (lvl != 0 && !canGetRowFromInner)
return false;
- row = getRow(io, pageAddr, idx, x);
+ row = c == null || c.apply(BPlusTree.this, io,pageAddr, idx) ? getRow(io, pageAddr, idx, x) : null;
return true;
}
@@ -2631,14 +2870,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
private final class GetCursor extends Get {
/** */
- ForwardCursor cursor;
+ AbstractForwardCursor cursor;
/**
* @param lower Lower bound.
* @param shift Shift.
* @param cursor Cursor.
*/
- GetCursor(L lower, int shift, ForwardCursor cursor) {
+ GetCursor(L lower, int shift, AbstractForwardCursor cursor) {
super(lower, false);
assert shift != 0; // Either handle range of equal rows or find a greater row after concurrent merge.
@@ -2664,97 +2903,452 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
- * Put operation.
+ * Get a cursor for range.
*/
- public final class Put extends Get {
- /** Mark of NULL value of page id. It means valid value can't be equal this value. */
- private static final long NULL_PAGE_ID = 0L;
-
- /** Mark of NULL value of page. */
- private static final long NULL_PAGE = 0L;
-
- /** Mark of NULL value of page address. */
- private static final long NULL_PAGE_ADDRESS = 0L;
-
- /** Right child page ID for split row. */
- long rightId;
-
- /** Replaced row if any. */
- T oldRow;
-
- /**
- * This page is kept locked after split until insert to the upper level will not be finished. It is needed
- * because split row will be "in flight" and if we'll release tail, remove on split row may fail.
- */
- long tailId;
-
+ private final class TreeVisitor extends Get {
/** */
- long tailPage;
+ long nextPageId;
/** */
- long tailAddr;
+ L upper;
- /**
- * Bottom level for insertion (insert can't go deeper). Will be incremented on split on each level.
- */
- short btmLvl;
+ /** */
+ TreeVisitorClosure<L, T> p;
/** */
- Bool needReplaceInner = FALSE;
+ private boolean dirty;
/** */
- final boolean needOld;
+ private boolean writing;
/**
- * @param row Row.
- * @param needOld {@code True} If need return old value.
+ * @param lower Lower bound.
*/
- private Put(T row, boolean needOld) {
- super(row, false);
+ TreeVisitor(L lower, L upper, TreeVisitorClosure<L, T> p) {
+ super(lower, false);
- this.needOld = needOld;
+ this.shift = -1;
+ this.upper = upper;
+ this.p = p;
}
/** {@inheritDoc} */
- @Override boolean found(BPlusIO<L> io, long pageAddr, int idx, int lvl) {
- if (lvl == 0) // Leaf: need to stop.
- return true;
+ @Override boolean found(BPlusIO<L> io, long pageAddr, int idx, int lvl) throws IgniteCheckedException {
+ throw new IllegalStateException(); // Must never be called because we always have a shift.
+ }
- assert btmLvl == 0; // It can not be insert.
+ /** {@inheritDoc} */
+ @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl) throws IgniteCheckedException {
+ if (lvl != 0)
+ return false;
- // If we can get full row from the inner page, we have to replace it with the new one. On the way down
- // we can not miss inner key even in presence of concurrent operations because of `triangle` invariant +
- // concurrent inner replace handling by retrying from root.
- if (canGetRowFromInner && needReplaceInner == FALSE)
- needReplaceInner = TRUE;
+ if (!(writing = (p.state() & TreeVisitorClosure.CAN_WRITE) != 0))
+ init(pageAddr, io, idx);
- return false;
+ return true;
}
- /** {@inheritDoc} */
- @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl) {
- assert btmLvl >= 0 : btmLvl;
- assert lvl >= btmLvl : lvl;
+ Result init(long pageId, long page, long fwdId) throws IgniteCheckedException {
+ // Init args.
+ this.pageId = pageId;
+ this.fwdId = fwdId;
- return lvl == btmLvl;
- }
+ if (writing) {
+ long pageAddr = writeLock(pageId, page);
- /**
- * @param tailId Tail page ID.
- * @param tailPage Tail page pointer.
- * @param tailPageAddr Tail page address
- */
- private void tail(long tailId, long tailPage, long tailPageAddr) {
- assert (tailId == NULL_PAGE_ID) == (tailPage == NULL_PAGE);
- assert (tailPage == NULL_PAGE) == (tailPageAddr == NULL_PAGE_ADDRESS);
+ if (pageAddr == 0)
+ return RETRY;
- if (this.tailPage != NULL_PAGE)
- writeUnlockAndClose(this.tailId, this.tailPage, this.tailAddr, null);
+ try {
+ BPlusIO<L> io = io(pageAddr);
- this.tailId = tailId;
- this.tailPage = tailPage;
- this.tailAddr = tailPageAddr;
- }
+ // Check triangle invariant.
+ if (io.getForward(pageAddr) != fwdId)
+ return RETRY;
+
+ init(pageAddr, io, -1);
+ } finally {
+ unlock(pageId, page, pageAddr);
+ }
+ }
+
+ return NOT_FOUND;
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param io IO.
+ * @param startIdx Start index.
+ * @throws IgniteCheckedException If failed.
+ */
+ private void init(long pageAddr, BPlusIO<L> io, int startIdx) throws IgniteCheckedException {
+ nextPageId = 0;
+
+ int cnt = io.getCount(pageAddr);
+
+ if (cnt != 0)
+ visit(pageAddr, io, startIdx, cnt);
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param io IO.
+ * @param startIdx Start index.
+ * @param cnt Number of rows in the buffer.
+ * @throws IgniteCheckedException If failed.
+ */
+ @SuppressWarnings("unchecked")
+ private void visit(long pageAddr, BPlusIO<L> io, int startIdx, int cnt)
+ throws IgniteCheckedException {
+ assert io.isLeaf() : io;
+ assert cnt != 0 : cnt; // We can not see empty pages (empty tree handled in init).
+ assert startIdx >= -1 : startIdx;
+ assert cnt >= startIdx;
+
+ checkDestroyed();
+
+ nextPageId = io.getForward(pageAddr);
+
+ if (startIdx == -1)
+ startIdx = findLowerBound(pageAddr, io, cnt);
+
+ if (cnt == startIdx)
+ return; // Go to the next page;
+
+ cnt = findUpperBound(pageAddr, io, startIdx, cnt);
+
+ for (int i = startIdx; i < cnt; i++) {
+ int state = p.visit(BPlusTree.this, io, pageAddr, i, wal);
+
+ boolean stop = (state & TreeVisitorClosure.STOP) != 0;
+
+ if (writing)
+ dirty = dirty || (state & TreeVisitorClosure.DIRTY) != 0;
+
+ if (stop) {
+ nextPageId = 0; // The End.
+
+ return;
+ }
+ }
+
+ if (nextPageId != 0) {
+ row = io.getLookupRow(BPlusTree.this, pageAddr, cnt - 1); // Need save last row.
+
+ shift = 1;
+ }
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param io IO.
+ * @param cnt Count.
+ * @return Adjusted to lower bound start index.
+ * @throws IgniteCheckedException If failed.
+ */
+ private int findLowerBound(long pageAddr, BPlusIO<L> io, int cnt) throws IgniteCheckedException {
+ assert io.isLeaf();
+
+ // Compare with the first row on the page.
+ int cmp = compare(0, io, pageAddr, 0, row);
+
+ if (cmp < 0 || (cmp == 0 && shift == 1)) {
+ int idx = findInsertionPoint(0, io, pageAddr, 0, cnt, row, shift);
+
+ assert idx < 0;
+
+ return fix(idx);
+ }
+
+ return 0;
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param io IO.
+ * @param low Start index.
+ * @param cnt Number of rows in the buffer.
+ * @return Corrected number of rows with respect to upper bound.
+ * @throws IgniteCheckedException If failed.
+ */
+ private int findUpperBound(long pageAddr, BPlusIO<L> io, int low, int cnt) throws IgniteCheckedException {
+ assert io.isLeaf();
+
+ // Compare with the last row on the page.
+ int cmp = compare(0, io, pageAddr, cnt - 1, upper);
+
+ if (cmp > 0) {
+ int idx = findInsertionPoint(0, io, pageAddr, low, cnt, upper, 1);
+
+ assert idx < 0;
+
+ cnt = fix(idx);
+
+ nextPageId = 0; // The End.
+ }
+
+ return cnt;
+ }
+
+ /**
+ * @throws IgniteCheckedException If failed.
+ */
+ private void nextPage() throws IgniteCheckedException {
+ for (;;) {
+ if (nextPageId == 0)
+ return;
+
+ long pageId = nextPageId;
+ long page = acquirePage(pageId);
+ try {
+ long pageAddr = lock(pageId, page); // Doing explicit null check.
+
+ // If concurrent merge occurred we have to reinitialize cursor from the last returned row.
+ if (pageAddr == 0L)
+ break;
+
+ try {
+ BPlusIO<L> io = io(pageAddr);
+
+ visit(pageAddr, io, -1, io.getCount(pageAddr));
+ }
+ finally {
+ unlock(pageId, page, pageAddr);
+ }
+ }
+ finally {
+ releasePage(pageId, page);
+ }
+ }
+
+ doVisit(this); // restart from last read row
+ }
+
+ private void unlock(long pageId, long page, long pageAddr) {
+ if (writing) {
+ writeUnlock(pageId, page, pageAddr, dirty);
+
+ dirty = false; // reset dirty flag
+ }
+ else
+ readUnlock(pageId, page, pageAddr);
+ }
+
+ private long lock(long pageId, long page) {
+ if (writing = ((p.state() & TreeVisitorClosure.CAN_WRITE) != 0))
+ return writeLock(pageId, page);
+ else
+ return readLock(pageId, page);
+ }
+
+ /**
+ * @throws IgniteCheckedException If failed.
+ */
+ private void visit() throws IgniteCheckedException {
+ doVisit(this);
+
+ while (nextPageId != 0)
+ nextPage();
+ }
+ }
+
+ /**
+ * Get the last item in the tree which matches the passed filter.
+ */
+ private final class GetLast extends Get {
+ private final TreeRowClosure<L, T> c;
+ private boolean retry = true;
+ private long lastPageId;
+ private T row0;
+
+ /**
+ * @param c Filter closure.
+ */
+ public GetLast(TreeRowClosure<L, T> c) {
+ super(null, true);
+
+ assert c != null;
+
+ this.c = c;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean found(BPlusIO<L> io, long pageAddr, int idx, int lvl) throws IgniteCheckedException {
+ if (lvl != 0)
+ return false;
+
+ for (int i = idx; i >= 0; i--) {
+ if (c.apply(BPlusTree.this, io, pageAddr, i)) {
+ retry = false;
+ row0 = getRow(io, pageAddr, i);
+
+ return true;
+ }
+ }
+
+ if(pageId == rootId)
+ retry = false; // We are at the root page, there are no other leafs.
+
+ if (retry) {
+ findLast = false;
+
+ // Restart from an item before the first item in the leaf (last item on the previous leaf).
+ row0 = getRow(io, pageAddr, 0);
+ shift = -1;
+
+ lastPageId = pageId; // Track leafs to detect a loop over the first leaf in the tree.
+ }
+
+ return true;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl) throws IgniteCheckedException {
+ if (lvl != 0)
+ return false;
+
+ if(io.getCount(pageAddr) == 0) {
+ // it's an empty tree
+ retry = false;
+
+ return true;
+ }
+
+ if (idx == 0 && lastPageId == pageId) {
+ // not found
+ retry = false;
+ row0 = null;
+
+ return true;
+ }
+ else {
+ for (int i = idx; i >= 0; i--) {
+ if (c.apply(BPlusTree.this, io, pageAddr, i)) {
+ retry = false;
+ row0 = getRow(io, pageAddr, i);
+
+ break;
+ }
+ }
+ }
+
+ if (retry) {
+ // Restart from an item before the first item in the leaf (last item on the previous leaf).
+ row0 = getRow(io, pageAddr, 0);
+
+ lastPageId = pageId; // Track leafs to detect a loop over the first leaf in the tree.
+ }
+
+ return true;
+ }
+
+ /**
+ * @return Last item in the tree.
+ * @throws IgniteCheckedException If failure.
+ */
+ public T find() throws IgniteCheckedException {
+ while (retry) {
+ row = row0;
+
+ doFind(this);
+ }
+
+ return row0;
+ }
+ }
+
+ /**
+ * Put operation.
+ */
+ public final class Put extends Get {
+ /** Mark of NULL value of page id. It means valid value can't be equal this value. */
+ private static final long NULL_PAGE_ID = 0L;
+
+ /** Mark of NULL value of page. */
+ private static final long NULL_PAGE = 0L;
+
+ /** Mark of NULL value of page address. */
+ private static final long NULL_PAGE_ADDRESS = 0L;
+
+ /** Right child page ID for split row. */
+ long rightId;
+
+ /** Replaced row if any. */
+ T oldRow;
+
+ /**
+ * This page is kept locked after split until insert to the upper level will not be finished. It is needed
+ * because split row will be "in flight" and if we'll release tail, remove on split row may fail.
+ */
+ long tailId;
+
+ /** */
+ long tailPage;
+
+ /** */
+ long tailAddr;
+
+ /**
+ * Bottom level for insertion (insert can't go deeper). Will be incremented on split on each level.
+ */
+ short btmLvl;
+
+ /** */
+ Bool needReplaceInner = FALSE;
+
+ /** */
+ final boolean needOld;
+
+ /**
+ * @param row Row.
+ * @param needOld {@code True} If need return old value.
+ */
+ private Put(T row, boolean needOld) {
+ super(row, false);
+
+ this.needOld = needOld;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean found(BPlusIO<L> io, long pageAddr, int idx, int lvl) {
+ if (lvl == 0) // Leaf: need to stop.
+ return true;
+
+ assert btmLvl == 0; // It can not be insert.
+
+ // If we can get full row from the inner page, we have to replace it with the new one. On the way down
+ // we can not miss inner key even in presence of concurrent operations because of `triangle` invariant +
+ // concurrent inner replace handling by retrying from root.
+ if (canGetRowFromInner && needReplaceInner == FALSE)
+ needReplaceInner = TRUE;
+
+ return false;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean notFound(BPlusIO<L> io, long pageAddr, int idx, int lvl) {
+ assert btmLvl >= 0 : btmLvl;
+ assert lvl >= btmLvl : lvl;
+
+ return lvl == btmLvl;
+ }
+
+ /**
+ * @param tailId Tail page ID.
+ * @param tailPage Tail page pointer.
+ * @param tailPageAddr Tail page address
+ */
+ private void tail(long tailId, long tailPage, long tailPageAddr) {
+ assert (tailId == NULL_PAGE_ID) == (tailPage == NULL_PAGE);
+ assert (tailPage == NULL_PAGE) == (tailPageAddr == NULL_PAGE_ADDRESS);
+
+ if (this.tailPage != NULL_PAGE)
+ writeUnlockAndClose(this.tailId, this.tailPage, this.tailAddr, null);
+
+ this.tailId = tailId;
+ this.tailPage = tailPage;
+ this.tailAddr = tailPageAddr;
+ }
/** {@inheritDoc} */
@Override public boolean canRelease(long pageId, int lvl) {
@@ -4520,7 +5114,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Full detached data row.
* @throws IgniteCheckedException If failed.
*/
- protected final T getRow(BPlusIO<L> io, long pageAddr, int idx) throws IgniteCheckedException {
+ public final T getRow(BPlusIO<L> io, long pageAddr, int idx) throws IgniteCheckedException {
return getRow(io, pageAddr, idx, null);
}
@@ -4534,54 +5128,60 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Data row.
* @throws IgniteCheckedException If failed.
*/
- protected abstract T getRow(BPlusIO<L> io, long pageAddr, int idx, Object x) throws IgniteCheckedException;
+ public abstract T getRow(BPlusIO<L> io, long pageAddr, int idx, Object x) throws IgniteCheckedException;
/**
- * Forward cursor.
+ *
*/
@SuppressWarnings("unchecked")
- private final class ForwardCursor implements GridCursor<T> {
+ private abstract class AbstractForwardCursor {
/** */
- private T[] rows = (T[])EMPTY;
-
- /** */
- private int row = -1;
+ long nextPageId;
/** */
- private long nextPageId;
-
- /** */
- private L lowerBound;
+ L lowerBound;
/** */
private int lowerShift = -1; // Initially it is -1 to handle multiple equal rows.
/** */
- private final L upperBound;
-
- /** */
- private final Object x;
+ final L upperBound;
/**
* @param lowerBound Lower bound.
* @param upperBound Upper bound.
*/
- ForwardCursor(L lowerBound, L upperBound) {
+ AbstractForwardCursor(L lowerBound, L upperBound) {
this.lowerBound = lowerBound;
this.upperBound = upperBound;
- this.x = null;
}
/**
- * @param lowerBound Lower bound.
- * @param upperBound Upper bound.
- * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ *
*/
- ForwardCursor(L lowerBound, L upperBound, Object x) {
- this.lowerBound = lowerBound;
- this.upperBound = upperBound;
- this.x = x;
- }
+ abstract void init0();
+
+ /**
+ * @param pageAddr Page address.
+ * @param io IO.
+ * @param startIdx Start index.
+ * @param cnt Number of rows in the buffer.
+ * @return {@code true} If we were able to fetch rows from this page.
+ * @throws IgniteCheckedException If failed.
+ */
+ abstract boolean fillFromBuffer0(long pageAddr, BPlusIO<L> io, int startIdx, int cnt)
+ throws IgniteCheckedException;
+
+ /**
+ * @return {@code True} If we have rows to return after reading the next page.
+ * @throws IgniteCheckedException If failed.
+ */
+ abstract boolean reinitialize0() throws IgniteCheckedException;
+
+ /**
+ * @param readDone {@code True} if traversed all rows.
+ */
+ abstract void onNotFound(boolean readDone);
/**
* @param pageAddr Page address.
@@ -4589,9 +5189,10 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param startIdx Start index.
* @throws IgniteCheckedException If failed.
*/
- private void init(long pageAddr, BPlusIO<L> io, int startIdx) throws IgniteCheckedException {
+ final void init(long pageAddr, BPlusIO<L> io, int startIdx) throws IgniteCheckedException {
nextPageId = 0;
- row = -1;
+
+ init0();
int cnt = io.getCount(pageAddr);
@@ -4599,16 +5200,10 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (cnt == 0) {
assert io.getForward(pageAddr) == 0L;
- rows = null;
- }
- else if (!fillFromBuffer(pageAddr, io, startIdx, cnt)) {
- if (rows != EMPTY) {
- assert rows.length > 0; // Otherwise it makes no sense to create an array.
-
- // Fake clear.
- rows[0] = null;
- }
+ onNotFound(true);
}
+ else if (!fillFromBuffer(pageAddr, io, startIdx, cnt))
+ onNotFound(false);
}
/**
@@ -4618,7 +5213,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Adjusted to lower bound start index.
* @throws IgniteCheckedException If failed.
*/
- private int findLowerBound(long pageAddr, BPlusIO<L> io, int cnt) throws IgniteCheckedException {
+ final int findLowerBound(long pageAddr, BPlusIO<L> io, int cnt) throws IgniteCheckedException {
assert io.isLeaf();
// Compare with the first row on the page.
@@ -4643,7 +5238,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Corrected number of rows with respect to upper bound.
* @throws IgniteCheckedException If failed.
*/
- private int findUpperBound(long pageAddr, BPlusIO<L> io, int low, int cnt) throws IgniteCheckedException {
+ final int findUpperBound(long pageAddr, BPlusIO<L> io, int low, int cnt) throws IgniteCheckedException {
assert io.isLeaf();
// Compare with the last row on the page.
@@ -4675,84 +5270,20 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
throws IgniteCheckedException {
assert io.isLeaf() : io;
assert cnt != 0 : cnt; // We can not see empty pages (empty tree handled in init).
- assert startIdx >= 0 : startIdx;
+ assert startIdx >= 0 || startIdx == -1: startIdx;
assert cnt >= startIdx;
checkDestroyed();
nextPageId = io.getForward(pageAddr);
- if (lowerBound != null && startIdx == 0)
- startIdx = findLowerBound(pageAddr, io, cnt);
-
- if (upperBound != null && cnt != startIdx)
- cnt = findUpperBound(pageAddr, io, startIdx, cnt);
-
- cnt -= startIdx;
-
- if (cnt == 0)
- return false;
-
- if (rows == EMPTY)
- rows = (T[])new Object[cnt];
-
- int foundCnt = 0;
-
- for (int i = 0; i < cnt; i++) {
- T r = getRow(io, pageAddr, startIdx + i, x);
-
- if (r != null)
- rows = GridArrays.set(rows, foundCnt++, r);
- }
-
- if (foundCnt == 0) {
- rows = (T[])EMPTY;
-
- return false;
- }
-
- GridArrays.clearTail(rows, foundCnt);
-
- return true;
- }
-
- /** {@inheritDoc} */
- @SuppressWarnings("SimplifiableIfStatement")
- @Override public boolean next() throws IgniteCheckedException {
- if (rows == null)
- return false;
-
- if (++row < rows.length && rows[row] != null) {
- clearLastRow(); // Allow to GC the last returned row.
-
- return true;
- }
-
- return nextPage();
- }
-
- /**
- * @return Cleared last row.
- */
- private T clearLastRow() {
- if (row == 0)
- return null;
-
- int last = row - 1;
-
- T r = rows[last];
-
- assert r != null;
-
- rows[last] = null;
-
- return r;
+ return fillFromBuffer0(pageAddr, io, startIdx, cnt);
}
/**
* @throws IgniteCheckedException If failed.
*/
- private void find() throws IgniteCheckedException {
+ final void find() throws IgniteCheckedException {
assert lowerBound != null;
doFind(new GetCursor(lowerBound, lowerShift, this));
@@ -4768,21 +5299,20 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// to the previous lower bound.
find();
- return next();
+ return reinitialize0();
}
/**
+ * @param lastRow Last read row (to be used as new lower bound).
* @return {@code true} If we have rows to return after reading the next page.
* @throws IgniteCheckedException If failed.
*/
- private boolean nextPage() throws IgniteCheckedException {
- updateLowerBound(clearLastRow());
-
- row = 0;
+ final boolean nextPage(L lastRow) throws IgniteCheckedException {
+ updateLowerBound(lastRow);
for (;;) {
if (nextPageId == 0) {
- rows = null;
+ onNotFound(true);
return false; // Done.
}
@@ -4799,7 +5329,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
try {
BPlusIO<L> io = io(pageAddr);
- if (fillFromBuffer(pageAddr, io, 0, io.getCount(pageAddr)))
+ if (fillFromBuffer(pageAddr, io, -1, io.getCount(pageAddr)))
return true;
// Continue fetching forward.
@@ -4820,12 +5350,239 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param lower New exact lower bound.
*/
- private void updateLowerBound(T lower) {
+ private void updateLowerBound(L lower) {
if (lower != null) {
lowerShift = 1; // Now we have the full row an need to avoid duplicates.
lowerBound = lower; // Move the lower bound forward for further concurrent merge retries.
}
}
+ }
+
+ /**
+ * Closure cursor.
+ */
+ @SuppressWarnings("unchecked")
+ private final class ClosureCursor extends AbstractForwardCursor {
+ /** */
+ private final TreeRowClosure<L, T> p;
+
+ /** */
+ private L lastRow;
+
+ /**
+ * @param lowerBound Lower bound.
+ * @param upperBound Upper bound.
+ * @param p Row predicate.
+ */
+ ClosureCursor(L lowerBound, L upperBound, TreeRowClosure<L, T> p) {
+ super(lowerBound, upperBound);
+
+ assert lowerBound != null;
+ assert upperBound != null;
+ assert p != null;
+
+ this.p = p;
+ }
+
+ /** {@inheritDoc} */
+ @Override void init0() {
+ // No-op.
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean fillFromBuffer0(long pageAddr, BPlusIO<L> io, int startIdx, int cnt)
+ throws IgniteCheckedException {
+ if (startIdx == -1)
+ startIdx = findLowerBound(pageAddr, io, cnt);
+
+ if (cnt == startIdx)
+ return false;
+
+ for (int i = startIdx; i < cnt; i++) {
+ int cmp = compare(0, io, pageAddr, i, upperBound);
+
+ if (cmp > 0) {
+ nextPageId = 0; // The End.
+
+ return false;
+ }
+
+ boolean stop = !p.apply(BPlusTree.this, io, pageAddr, i);
+
+ if (stop) {
+ nextPageId = 0; // The End.
+
+ return true;
+ }
+ }
+
+ if (nextPageId != 0)
+ lastRow = io.getLookupRow(BPlusTree.this, pageAddr, cnt - 1); // Need save last row.
+
+ return true;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean reinitialize0() throws IgniteCheckedException {
+ return true;
+ }
+
+ /** {@inheritDoc} */
+ @Override void onNotFound(boolean readDone) {
+ nextPageId = 0;
+ }
+
+ /**
+ * @throws IgniteCheckedException If failed.
+ */
+ private void iterate() throws IgniteCheckedException {
+ find();
+
+ if (nextPageId == 0) {
+ return;
+ }
+
+ for (;;) {
+ L lastRow0 = lastRow;
+
+ lastRow = null;
+
+ nextPage(lastRow0);
+
+ if (nextPageId == 0)
+ return;
+ }
+ }
+ }
+
+ /**
+ * Forward cursor.
+ */
+ @SuppressWarnings("unchecked")
+ private final class ForwardCursor extends AbstractForwardCursor implements GridCursor<T> {
+ /** */
+ final Object x;
+
+ /** */
+ private T[] rows = (T[])EMPTY;
+
+ /** */
+ private int row = -1;
+
+ /** */
+ private final TreeRowClosure<L, T> c;
+
+ /**
+ * @param lowerBound Lower bound.
+ * @param upperBound Upper bound.
+ * @param c Filter closure.
+ * @param x Implementation specific argument, {@code null} always means that we need to return full detached data row.
+ */
+ ForwardCursor(L lowerBound, L upperBound, TreeRowClosure<L, T> c, Object x) {
+ super(lowerBound, upperBound);
+
+ this.c = c;
+ this.x = x;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean fillFromBuffer0(long pageAddr, BPlusIO<L> io, int startIdx, int cnt) throws IgniteCheckedException {
+ if (startIdx == -1) {
+ if (lowerBound != null)
+ startIdx = findLowerBound(pageAddr, io, cnt);
+ else
+ startIdx = 0;
+ }
+
+ if (upperBound != null && cnt != startIdx)
+ cnt = findUpperBound(pageAddr, io, startIdx, cnt);
+
+ int cnt0 = cnt - startIdx;
+
+ if (cnt0 == 0)
+ return false;
+
+ if (rows == EMPTY)
+ rows = (T[])new Object[cnt0];
+
+ int resCnt = 0;
+
+ for (int idx = startIdx; idx < cnt; idx++) {
+ if (c == null || c.apply(BPlusTree.this, io, pageAddr, idx))
+ rows = GridArrays.set(rows, resCnt++, getRow(io, pageAddr, idx, x));
+ }
+
+ if (resCnt == 0) {
+ rows = (T[])EMPTY;
+
+ return false;
+ }
+
+ GridArrays.clearTail(rows, resCnt);
+
+ return true;
+ }
+
+ /** {@inheritDoc} */
+ @Override boolean reinitialize0() throws IgniteCheckedException {
+ return next();
+ }
+
+ /** {@inheritDoc} */
+ @Override void onNotFound(boolean readDone) {
+ if (readDone)
+ rows = null;
+ else {
+ if (rows != EMPTY) {
+ assert rows.length > 0; // Otherwise it makes no sense to create an array.
+
+ // Fake clear.
+ rows[0] = null;
+ }
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override void init0() {
+ row = -1;
+ }
+
+ /** {@inheritDoc} */
+ @SuppressWarnings("SimplifiableIfStatement")
+ @Override public boolean next() throws IgniteCheckedException {
+ if (rows == null)
+ return false;
+
+ if (++row < rows.length && rows[row] != null) {
+ clearLastRow(); // Allow to GC the last returned row.
+
+ return true;
+ }
+
+ T lastRow = clearLastRow();
+
+ row = 0;
+
+ return nextPage(lastRow);
+ }
+
+ /**
+ * @return Cleared last row.
+ */
+ private T clearLastRow() {
+ if (row == 0)
+ return null;
+
+ int last = row - 1;
+
+ T r = rows[last];
+
+ assert r != null;
+
+ rows[last] = null;
+
+ return r;
+ }
/** {@inheritDoc} */
@Override public T get() {
@@ -4962,6 +5719,36 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
+ * A generic visitor-style interface for performing inspection/modification operations on the tree.
+ */
+ public interface TreeVisitorClosure<L, T extends L> {
+ /** */
+ int STOP = 0x01;
+ /** */
+ int CAN_WRITE = STOP << 1;
+ /** */
+ int DIRTY = CAN_WRITE << 1;
+
+ /**
+ * Performs inspection or operation on a specified row.
+ *
+ * @param tree The tree.
+ * @param io Th tree IO object.
+ * @param pageAddr The page address.
+ * @param idx The item index.
+ * @return state bitset.
+ * @throws IgniteCheckedException If failed.
+ */
+ public int visit(BPlusTree<L, T> tree, BPlusIO<L> io, long pageAddr, int idx, IgniteWriteAheadLogManager wal)
+ throws IgniteCheckedException;
+
+ /**
+ * @return state bitset.
+ */
+ public int state();
+ }
+
+ /**
* @return Return number of retries.
*/
protected int getLockRetries() {
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java
index 50b5779..4a12045 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/AbstractDataPageIO.java
@@ -81,6 +81,7 @@ public abstract class AbstractDataPageIO<T extends Storable> extends PageIO {
public static final int MIN_DATA_PAGE_OVERHEAD = ITEMS_OFF + ITEM_SIZE + PAYLOAD_LEN_SIZE + LINK_SIZE;
/**
+ * @param type Page type.
* @param ver Page format version.
*/
protected AbstractDataPageIO(int type, int ver) {
@@ -502,6 +503,23 @@ public abstract class AbstractDataPageIO<T extends Storable> extends PageIO {
/**
* @param pageAddr Page address.
+ * @param itemId Item to position on.
+ * @param pageSize Page size.
+ * @param reqLen Required payload length.
+ * @return Offset to start of actual fragment data.
+ */
+ public int getPayloadOffset(final long pageAddr, final int itemId, final int pageSize, int reqLen) {
+ int dataOff = getDataOffset(pageAddr, itemId, pageSize);
+
+ int payloadSize = getPageEntrySize(pageAddr, dataOff, 0);
+
+ assert payloadSize >= reqLen : payloadSize;
+
+ return dataOff + PAYLOAD_LEN_SIZE + (isFragmented(pageAddr, dataOff) ? LINK_SIZE : 0);
+ }
+
+ /**
+ * @param pageAddr Page address.
* @param idx Item index.
* @return Item.
*/
@@ -982,6 +1000,16 @@ public abstract class AbstractDataPageIO<T extends Storable> extends PageIO {
int payloadSize = payload != null ? payload.length :
Math.min(rowSize - written, getFreeSpace(pageAddr));
+ if (row != null) {
+ int remain = rowSize - written - payloadSize;
+ int hdrSize = row.headerSize();
+
+ // We need page header (i.e. MVCC info) is located entirely on the very first page in chain.
+ // So we force moving it to the next page if it could not fit entirely on this page.
+ if (remain > 0 && remain < hdrSize)
+ payloadSize -= hdrSize - remain;
+ }
+
int fullEntrySize = getPageEntrySize(payloadSize, SHOW_PAYLOAD_LEN | SHOW_LINK | SHOW_ITEM);
int dataOff = getDataOffsetForWrite(pageAddr, fullEntrySize, directCnt, indirectCnt, pageSize);
@@ -1227,13 +1255,6 @@ public abstract class AbstractDataPageIO<T extends Storable> extends PageIO {
}
/**
- * @param row Row.
- * @return Row size in page.
- * @throws IgniteCheckedException if failed.
- */
- public abstract int getRowSize(T row) throws IgniteCheckedException;
-
- /**
* Defines closure interface for applying computations to data page items.
*
* @param <T> Closure return type.
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/DataPageIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/DataPageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/DataPageIO.java
index 8a04749..87e37f6 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/DataPageIO.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/DataPageIO.java
@@ -21,16 +21,27 @@ import java.nio.ByteBuffer;
import org.apache.ignite.IgniteCheckedException;
import org.apache.ignite.internal.pagemem.PageUtils;
import org.apache.ignite.internal.processors.cache.CacheObject;
-import org.apache.ignite.internal.processors.cache.KeyCacheObject;
+import org.apache.ignite.internal.processors.cache.mvcc.MvccUtils;
+import org.apache.ignite.internal.processors.cache.mvcc.MvccVersion;
import org.apache.ignite.internal.processors.cache.persistence.CacheDataRow;
import org.apache.ignite.internal.processors.cache.version.GridCacheVersion;
import org.apache.ignite.internal.util.GridStringBuilder;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.CACHE_ID;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.EXPIRE_TIME;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.KEY;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.MVCC_INFO;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.VALUE;
+import static org.apache.ignite.internal.processors.cache.persistence.tree.io.DataPageIO.EntryPart.VERSION;
+
/**
* Data pages IO.
*/
public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
/** */
+ public static final int MVCC_INFO_SIZE = 40;
+
+ /** */
public static final IOVersions<DataPageIO> VERSIONS = new IOVersions<>(
new DataPageIO(1)
);
@@ -43,21 +54,74 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
}
/** {@inheritDoc} */
- @Override
- protected void writeFragmentData(
- final CacheDataRow row,
- final ByteBuffer buf,
- final int rowOff,
- final int payloadSize
- ) throws IgniteCheckedException {
+ @Override protected void writeRowData(long pageAddr, int dataOff, int payloadSize, CacheDataRow row,
+ boolean newRow) throws IgniteCheckedException {
+ long addr = pageAddr + dataOff;
+
+ int cacheIdSize = row.cacheId() != 0 ? 4 : 0;
+ int mvccInfoSize = row.mvccCoordinatorVersion() > 0 ? MVCC_INFO_SIZE : 0;
+
+ if (newRow) {
+ PageUtils.putShort(addr, 0, (short)payloadSize);
+ addr += 2;
+
+ if (mvccInfoSize > 0) {
+ assert MvccUtils.mvccVersionIsValid(row.mvccCoordinatorVersion(), row.mvccCounter(), row.mvccOperationCounter());
+
+ // xid_min.
+ PageUtils.putLong(addr, 0, row.mvccCoordinatorVersion());
+ PageUtils.putLong(addr, 8, row.mvccCounter());
+ PageUtils.putInt(addr, 16, row.mvccOperationCounter() | (row.mvccTxState() << MVCC_HINTS_BIT_OFF));
+
+ assert row.newMvccCoordinatorVersion() == 0
+ || MvccUtils.mvccVersionIsValid(row.newMvccCoordinatorVersion(), row.newMvccCounter(), row.newMvccOperationCounter());
+
+ // xid_max.
+ PageUtils.putLong(addr, 20, row.newMvccCoordinatorVersion());
+ PageUtils.putLong(addr, 28, row.newMvccCounter());
+ PageUtils.putInt(addr, 36, row.newMvccOperationCounter() | (row.newMvccTxState() << MVCC_HINTS_BIT_OFF));
+
+ addr += mvccInfoSize;
+ }
+
+ if (cacheIdSize != 0) {
+ PageUtils.putInt(addr, 0, row.cacheId());
+
+ addr += cacheIdSize;
+ }
+
+ addr += row.key().putValue(addr);
+ }
+ else
+ addr += (2 + mvccInfoSize + cacheIdSize + row.key().valueBytesLength(null));
+
+ addr += row.value().putValue(addr);
+
+ CacheVersionIO.write(addr, row.version(), false);
+ addr += CacheVersionIO.size(row.version(), false);
+
+ PageUtils.putLong(addr, 0, row.expireTime());
+ }
+
+ /** {@inheritDoc} */
+ @Override protected void writeFragmentData(CacheDataRow row, ByteBuffer buf, int rowOff,
+ int payloadSize) throws IgniteCheckedException {
final int keySize = row.key().valueBytesLength(null);
+
final int valSize = row.value().valueBytesLength(null);
- int written = writeFragment(row, buf, rowOff, payloadSize, EntryPart.CACHE_ID, keySize, valSize);
- written += writeFragment(row, buf, rowOff + written, payloadSize - written, EntryPart.KEY, keySize, valSize);
- written += writeFragment(row, buf, rowOff + written, payloadSize - written, EntryPart.EXPIRE_TIME, keySize, valSize);
- written += writeFragment(row, buf, rowOff + written, payloadSize - written, EntryPart.VALUE, keySize, valSize);
- written += writeFragment(row, buf, rowOff + written, payloadSize - written, EntryPart.VERSION, keySize, valSize);
+ int written = writeFragment(row, buf, rowOff, payloadSize,
+ MVCC_INFO, keySize, valSize);
+ written += writeFragment(row, buf, rowOff + written, payloadSize - written,
+ CACHE_ID, keySize, valSize);
+ written += writeFragment(row, buf, rowOff + written, payloadSize - written,
+ KEY, keySize, valSize);
+ written += writeFragment(row, buf, rowOff + written, payloadSize - written,
+ EXPIRE_TIME, keySize, valSize);
+ written += writeFragment(row, buf, rowOff + written, payloadSize - written,
+ VALUE, keySize, valSize);
+ written += writeFragment(row, buf, rowOff + written, payloadSize - written,
+ VERSION, keySize, valSize);
assert written == payloadSize;
}
@@ -65,9 +129,13 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
/**
* Try to write fragment data.
*
+ * @param row Row.
+ * @param buf Byte buffer.
* @param rowOff Offset in row data bytes.
* @param payloadSize Data length that should be written in this fragment.
* @param type Type of the part of entry.
+ * @param keySize Key size.
+ * @param valSize Value size.
* @return Actually written data.
* @throws IgniteCheckedException If fail.
*/
@@ -87,35 +155,42 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
final int curLen;
int cacheIdSize = row.cacheId() == 0 ? 0 : 4;
+ int mvccInfoSize = row.mvccCoordinatorVersion() > 0 ? MVCC_INFO_SIZE : 0;
switch (type) {
- case CACHE_ID:
+ case MVCC_INFO:
prevLen = 0;
- curLen = cacheIdSize;
+ curLen = mvccInfoSize;
+
+ break;
+
+ case CACHE_ID:
+ prevLen = mvccInfoSize;
+ curLen = mvccInfoSize + cacheIdSize;
break;
case KEY:
- prevLen = cacheIdSize;
- curLen = cacheIdSize + keySize;
+ prevLen = mvccInfoSize + cacheIdSize;
+ curLen = mvccInfoSize + cacheIdSize + keySize;
break;
case EXPIRE_TIME:
- prevLen = cacheIdSize + keySize;
- curLen = cacheIdSize + keySize + 8;
+ prevLen = mvccInfoSize + cacheIdSize + keySize;
+ curLen = mvccInfoSize + cacheIdSize + keySize + 8;
break;
case VALUE:
- prevLen = cacheIdSize + keySize + 8;
- curLen = cacheIdSize + keySize + valSize + 8;
+ prevLen = mvccInfoSize + cacheIdSize + keySize + 8;
+ curLen = mvccInfoSize + cacheIdSize + keySize + valSize + 8;
break;
case VERSION:
- prevLen = cacheIdSize + keySize + valSize + 8;
- curLen = cacheIdSize + keySize + valSize + CacheVersionIO.size(row.version(), false) + 8;
+ prevLen = mvccInfoSize + cacheIdSize + keySize + valSize + 8;
+ curLen = mvccInfoSize + cacheIdSize + keySize + valSize + CacheVersionIO.size(row.version(), false) + 8;
break;
@@ -128,13 +203,22 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
final int len = Math.min(curLen - rowOff, payloadSize);
- if (type == EntryPart.EXPIRE_TIME)
+ if (type == EXPIRE_TIME)
writeExpireTimeFragment(buf, row.expireTime(), rowOff, len, prevLen);
- else if (type == EntryPart.CACHE_ID)
+ else if (type == CACHE_ID)
writeCacheIdFragment(buf, row.cacheId(), rowOff, len, prevLen);
- else if (type != EntryPart.VERSION) {
+ else if (type == MVCC_INFO)
+ writeMvccInfoFragment(buf,
+ row.mvccCoordinatorVersion(),
+ row.mvccCounter(),
+ row.mvccOperationCounter() | (row.mvccTxState() << MVCC_HINTS_BIT_OFF),
+ row.newMvccCoordinatorVersion(),
+ row.newMvccCounter(),
+ row.newMvccOperationCounter() | (row.newMvccTxState() << MVCC_HINTS_BIT_OFF),
+ len);
+ else if (type != VERSION) {
// Write key or value.
- final CacheObject co = type == EntryPart.KEY ? row.key() : row.value();
+ final CacheObject co = type == KEY ? row.key() : row.value();
co.putValue(buf, rowOff - prevLen, len);
}
@@ -145,6 +229,236 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
}
/**
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @param ver New version.
+ */
+ public void updateVersion(long pageAddr, int dataOff, MvccVersion ver) {
+ long addr = pageAddr + dataOff;
+
+ updateVersion(addr, ver.coordinatorVersion(), ver.counter(), ver.operationCounter());
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param itemId Item ID.
+ * @param pageSize Page size.
+ * @param mvccCrd Mvcc coordinator.
+ * @param mvccCntr Mvcc counter.
+ * @param mvccOpCntr Operation counter.
+ */
+ public void updateVersion(long pageAddr, int itemId, int pageSize, long mvccCrd, long mvccCntr, int mvccOpCntr) {
+ int dataOff = getDataOffset(pageAddr, itemId, pageSize);
+
+ long addr = pageAddr + dataOff + (isFragmented(pageAddr, dataOff) ? 10 : 2);
+
+ updateVersion(addr, mvccCrd, mvccCntr, mvccOpCntr);
+ }
+
+ /**
+ * @param addr Address.
+ * @param mvccCrd Mvcc coordinator.
+ * @param mvccCntr Mvcc counter.
+ */
+ private void updateVersion(long addr, long mvccCrd, long mvccCntr, int mvccOpCntr) {
+ PageUtils.putLong(addr, 0, mvccCrd);
+ PageUtils.putLong(addr, 8, mvccCntr);
+ PageUtils.putInt(addr, 16, mvccOpCntr);
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @param newVer New version.
+ */
+ public void updateNewVersion(long pageAddr, int dataOff, MvccVersion newVer, byte newTxState) {
+ long addr = pageAddr + dataOff;
+
+ updateNewVersion(addr, newVer.coordinatorVersion(), newVer.counter(),
+ (newVer.operationCounter() & ~MVCC_HINTS_MASK) | ((int)newTxState << MVCC_HINTS_BIT_OFF));
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param itemId Item ID.
+ * @param pageSize Page size.
+ * @param mvccCrd Mvcc coordinator.
+ * @param mvccCntr Mvcc counter.
+ * @param mvccOpCntr Operation counter.
+ */
+ public void updateNewVersion(long pageAddr, int itemId, int pageSize, long mvccCrd, long mvccCntr, int mvccOpCntr) {
+ int dataOff = getDataOffset(pageAddr, itemId, pageSize);
+
+ long addr = pageAddr + dataOff + (isFragmented(pageAddr, dataOff) ? 10 : 2);
+
+ updateNewVersion(addr, mvccCrd, mvccCntr, mvccOpCntr);
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param itemId Item ID.
+ * @param pageSize Page size.
+ * @param txState Tx state hint.
+ */
+ public void updateTxState(long pageAddr, int itemId, int pageSize, byte txState) {
+ int dataOff = getDataOffset(pageAddr, itemId, pageSize);
+
+ long addr = pageAddr + dataOff + (isFragmented(pageAddr, dataOff) ? 10 : 2);
+
+ int opCntr = mvccOperationCounter(addr, 0);
+
+ mvccOperationCounter(addr, 0, ((int)txState << MVCC_HINTS_BIT_OFF) | (opCntr & ~MVCC_HINTS_MASK));
+ }
+
+ /**
+ * @param pageAddr Page address.
+ * @param itemId Item ID.
+ * @param pageSize Page size.
+ * @param txState Tx state hint.
+ */
+ public void updateNewTxState(long pageAddr, int itemId, int pageSize, byte txState) {
+ int dataOff = getDataOffset(pageAddr, itemId, pageSize);
+
+ long addr = pageAddr + dataOff + (isFragmented(pageAddr, dataOff) ? 10 : 2);
+
+ int opCntr = newMvccOperationCounter(addr, 0);
+
+ newMvccOperationCounter(addr, 0, ((int)txState << MVCC_HINTS_BIT_OFF) | (opCntr & ~MVCC_HINTS_MASK));
+ }
+
+ /**
+ * Marks row removed.
+ *
+ * @param addr Address.
+ * @param mvccCrd Mvcc coordinator.
+ * @param mvccCntr Mvcc counter.
+ */
+ private void updateNewVersion(long addr, long mvccCrd, long mvccCntr, int mvccOpCntr) {
+ // Skip xid_min.
+ addr += 20;
+
+ PageUtils.putLong(addr, 0, mvccCrd);
+ PageUtils.putLong(addr, 8, mvccCntr);
+ PageUtils.putInt(addr, 16, mvccOpCntr);
+ }
+
+ /**
+ * Returns MVCC coordinator number.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return MVCC coordinator number.
+ */
+ public long mvccCoordinator(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ return PageUtils.getLong(addr, 0);
+ }
+
+ /**
+ * Returns MVCC counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return MVCC counter value.
+ */
+ public long mvccCounter(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ return PageUtils.getLong(addr, 8);
+ }
+
+ /**
+ * Returns MVCC operation counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return MVCC counter value.
+ */
+ public int mvccOperationCounter(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ return PageUtils.getInt(addr, 16);
+ }
+
+ /**
+ * Sets MVCC operation counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @param opCntr MVCC counter value.
+ */
+ public void mvccOperationCounter(long pageAddr, int dataOff, int opCntr) {
+ long addr = pageAddr + dataOff;
+
+ PageUtils.putInt(addr, 16, opCntr);
+ }
+
+ /**
+ * Returns new MVCC coordinator number.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return New MVCC coordinator number.
+ */
+ public long newMvccCoordinator(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ // Skip xid_min.
+ addr += 20;
+
+ return PageUtils.getLong(addr, 0);
+ }
+
+ /**
+ * Returns new MVCC counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return New MVCC counter value.
+ */
+ public long newMvccCounter(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ // Skip xid_min.
+ addr += 20;
+
+ return PageUtils.getLong(addr, 8);
+ }
+
+ /**
+ * Returns MVCC operation counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @return MVCC counter value.
+ */
+ public int newMvccOperationCounter(long pageAddr, int dataOff) {
+ long addr = pageAddr + dataOff;
+
+ // Skip xid_min.
+ addr += 20;
+
+ return PageUtils.getInt(addr, 16);
+ }
+
+ /**
+ * Sets MVCC new operation counter value.
+ *
+ * @param pageAddr Page address.
+ * @param dataOff Data offset.
+ * @param opCntr MVCC operation counter value.
+ */
+ public void newMvccOperationCounter(long pageAddr, int dataOff, int opCntr) {
+ long addr = pageAddr + dataOff;
+
+ // Skip xid_min.
+ addr += 20;
+
+ PageUtils.putInt(addr, 16, opCntr);
+ }
+
+ /**
* @param buf Byte buffer.
* @param ver Version.
* @param rowOff Row offset.
@@ -181,7 +495,6 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
*/
private void writeExpireTimeFragment(ByteBuffer buf, long expireTime, int rowOff, int len, int prevLen) {
int size = 8;
-
if (size <= len)
buf.putLong(expireTime);
else {
@@ -222,77 +535,35 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
}
/**
- *
+ * @param buf Byte buffer.
+ * @param mvccCrd Coordinator version.
+ * @param mvccCntr Counter.
+ * @param mvccOpCntr Operation counter.
+ * @param newMvccCrd New coordinator version.
+ * @param newMvccCntr New counter version.
+ * @param newMvccOpCntr New operation counter.
+ * @param len Length.
*/
- private enum EntryPart {
- /** */
- KEY,
-
- /** */
- VALUE,
-
- /** */
- VERSION,
-
- /** */
- EXPIRE_TIME,
-
- /** */
- CACHE_ID
- }
-
- /** {@inheritDoc} */
- @Override
- protected void writeRowData(
- long pageAddr,
- int dataOff,
- int payloadSize,
- CacheDataRow row,
- boolean newRow
- ) throws IgniteCheckedException {
- long addr = pageAddr + dataOff;
-
- int cacheIdSize = row.cacheId() != 0 ? 4 : 0;
-
- if (newRow) {
- PageUtils.putShort(addr, 0, (short)payloadSize);
- addr += 2;
-
- if (cacheIdSize != 0) {
- PageUtils.putInt(addr, 0, row.cacheId());
-
- addr += cacheIdSize;
- }
-
- addr += row.key().putValue(addr);
- }
- else
- addr += (2 + cacheIdSize + row.key().valueBytesLength(null));
+ private void writeMvccInfoFragment(ByteBuffer buf, long mvccCrd, long mvccCntr, int mvccOpCntr, long newMvccCrd,
+ long newMvccCntr, int newMvccOpCntr, int len) {
+ if (mvccCrd == 0)
+ return;
- addr += row.value().putValue(addr);
+ assert len >= MVCC_INFO_SIZE : "Mvcc info should fit on the one page!";
- CacheVersionIO.write(addr, row.version(), false);
- addr += CacheVersionIO.size(row.version(), false);
+ assert MvccUtils.mvccVersionIsValid(mvccCrd, mvccCntr, mvccOpCntr);
- PageUtils.putLong(addr, 0, row.expireTime());
- }
+ // xid_min.
+ buf.putLong(mvccCrd);
+ buf.putLong(mvccCntr);
+ buf.putInt(mvccOpCntr);
- /** {@inheritDoc} */
- @Override
- protected void writeRowData(
- long pageAddr,
- int dataOff,
- byte[] payload
- ) {
- PageUtils.putShort(pageAddr, dataOff, (short)payload.length);
- dataOff += 2;
-
- PageUtils.putBytes(pageAddr, dataOff, payload);
- }
+ assert newMvccCrd == 0 || MvccUtils.mvccVersionIsValid(newMvccCrd, newMvccCntr, newMvccOpCntr);
- /** {@inheritDoc} */
- @Override public int getRowSize(CacheDataRow row) throws IgniteCheckedException {
- return getRowSize(row, row.cacheId() != 0);
+ // xid_max.
+ buf.putLong(newMvccCrd);
+ buf.putLong(newMvccCntr);
+ buf.putInt(newMvccOpCntr);
}
/** {@inheritDoc} */
@@ -303,18 +574,25 @@ public class DataPageIO extends AbstractDataPageIO<CacheDataRow> {
}
/**
- * @param row Row.
- * @param withCacheId If {@code true} adds cache ID size.
- * @return Entry size on page.
- * @throws IgniteCheckedException If failed.
+ *
*/
- public static int getRowSize(CacheDataRow row, boolean withCacheId) throws IgniteCheckedException {
- KeyCacheObject key = row.key();
- CacheObject val = row.value();
+ enum EntryPart {
+ /** */
+ KEY,
- int keyLen = key.valueBytesLength(null);
- int valLen = val.valueBytesLength(null);
+ /** */
+ VALUE,
+
+ /** */
+ VERSION,
- return keyLen + valLen + CacheVersionIO.size(row.version(), false) + 8 + (withCacheId ? 4 : 0);
+ /** */
+ EXPIRE_TIME,
+
+ /** */
+ CACHE_ID,
+
+ /** */
+ MVCC_INFO
}
}
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/IOVersions.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/IOVersions.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/IOVersions.java
index d74d344..9dcad9b 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/IOVersions.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/IOVersions.java
@@ -17,6 +17,8 @@
package org.apache.ignite.internal.processors.cache.persistence.tree.io;
+import org.apache.ignite.internal.util.typedef.internal.S;
+
/**
* Registry for IO versions.
*/
@@ -99,4 +101,9 @@ public final class IOVersions<V extends PageIO> {
return res;
}
+
+ /** {@inheritDoc} */
+ @Override public String toString() {
+ return S.toString(IOVersions.class, this);
+ }
}
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java
index 4534bb5..f167d0c 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/PageIO.java
@@ -25,6 +25,8 @@ import org.apache.ignite.internal.pagemem.PageIdUtils;
import org.apache.ignite.internal.pagemem.PageMemory;
import org.apache.ignite.internal.pagemem.PageUtils;
import org.apache.ignite.internal.pagemem.wal.IgniteWriteAheadLogManager;
+import org.apache.ignite.internal.processors.cache.mvcc.txlog.TxLogInnerIO;
+import org.apache.ignite.internal.processors.cache.mvcc.txlog.TxLogLeafIO;
import org.apache.ignite.internal.processors.cache.persistence.IndexStorageImpl;
import org.apache.ignite.internal.processors.cache.persistence.freelist.io.PagesListMetaIO;
import org.apache.ignite.internal.processors.cache.persistence.freelist.io.PagesListNodeIO;
@@ -33,10 +35,14 @@ import org.apache.ignite.internal.processors.cache.persistence.tree.util.PageHan
import org.apache.ignite.internal.processors.cache.persistence.tree.util.PageLockListener;
import org.apache.ignite.internal.processors.cache.tree.CacheIdAwareDataInnerIO;
import org.apache.ignite.internal.processors.cache.tree.CacheIdAwareDataLeafIO;
+import org.apache.ignite.internal.processors.cache.tree.mvcc.data.MvccCacheIdAwareDataInnerIO;
+import org.apache.ignite.internal.processors.cache.tree.mvcc.data.MvccCacheIdAwareDataLeafIO;
import org.apache.ignite.internal.processors.cache.tree.CacheIdAwarePendingEntryInnerIO;
import org.apache.ignite.internal.processors.cache.tree.CacheIdAwarePendingEntryLeafIO;
import org.apache.ignite.internal.processors.cache.tree.DataInnerIO;
import org.apache.ignite.internal.processors.cache.tree.DataLeafIO;
+import org.apache.ignite.internal.processors.cache.tree.mvcc.data.MvccDataInnerIO;
+import org.apache.ignite.internal.processors.cache.tree.mvcc.data.MvccDataLeafIO;
import org.apache.ignite.internal.processors.cache.tree.PendingEntryInnerIO;
import org.apache.ignite.internal.processors.cache.tree.PendingEntryLeafIO;
import org.apache.ignite.internal.util.GridStringBuilder;
@@ -87,6 +93,12 @@ public abstract class PageIO {
/** */
private static IOVersions<? extends BPlusLeafIO<?>> h2LeafIOs;
+ /** */
+ private static IOVersions<? extends BPlusInnerIO<?>> h2MvccInnerIOs;
+
+ /** */
+ private static IOVersions<? extends BPlusLeafIO<?>> h2MvccLeafIOs;
+
/** Maximum payload size. */
public static final short MAX_PAYLOAD_SIZE = 2048;
@@ -97,6 +109,12 @@ public abstract class PageIO {
private static List<IOVersions<? extends BPlusLeafIO<?>>> h2ExtraLeafIOs = new ArrayList<>(MAX_PAYLOAD_SIZE);
/** */
+ private static List<IOVersions<? extends BPlusInnerIO<?>>> h2ExtraMvccInnerIOs = new ArrayList<>(MAX_PAYLOAD_SIZE);
+
+ /** */
+ private static List<IOVersions<? extends BPlusLeafIO<?>>> h2ExtraMvccLeafIOs = new ArrayList<>(MAX_PAYLOAD_SIZE);
+
+ /** */
public static final int TYPE_OFF = 0;
/** */
@@ -129,6 +147,12 @@ public abstract class PageIO {
/** */
public static final int COMMON_HEADER_END = RESERVED_3_OFF + 8; // 40=type(2)+ver(2)+crc(4)+pageId(8)+rotatedIdPart(1)+reserved(1+2+4+2*8)
+ /** */
+ public static final int MVCC_HINTS_MASK = 0xC0000000;
+
+ /** */
+ public static final int MVCC_HINTS_BIT_OFF = 30;
+
/* All the page types. */
/** */
@@ -200,19 +224,55 @@ public abstract class PageIO {
/** */
public static final short T_DATA_REF_METASTORAGE_LEAF = 23;
+ /** */
+ public static final short T_DATA_REF_MVCC_INNER = 24;
+
+ /** */
+ public static final short T_DATA_REF_MVCC_LEAF = 25;
+
+ /** */
+ public static final short T_CACHE_ID_DATA_REF_MVCC_INNER = 26;
+
+ /** */
+ public static final short T_CACHE_ID_DATA_REF_MVCC_LEAF = 27;
+
+ /** */
+ public static final short T_H2_MVCC_REF_LEAF = 28;
+
+ /** */
+ public static final short T_H2_MVCC_REF_INNER = 29;
+
+ /** */
+ public static final short T_TX_LOG_LEAF = 30;
+
+ /** */
+ public static final short T_TX_LOG_INNER = 31;
+
/** Index for payload == 1. */
- public static final short T_H2_EX_REF_LEAF_START = 10000;
+ public static final short T_H2_EX_REF_LEAF_START = 10_000;
/** */
public static final short T_H2_EX_REF_LEAF_END = T_H2_EX_REF_LEAF_START + MAX_PAYLOAD_SIZE - 1;
/** */
- public static final short T_H2_EX_REF_INNER_START = 20000;
+ public static final short T_H2_EX_REF_INNER_START = 20_000;
/** */
public static final short T_H2_EX_REF_INNER_END = T_H2_EX_REF_INNER_START + MAX_PAYLOAD_SIZE - 1;
/** */
+ public static final short T_H2_EX_REF_MVCC_LEAF_START = 23_000;
+
+ /** */
+ public static final short T_H2_EX_REF_MVCC_LEAF_END = T_H2_EX_REF_MVCC_LEAF_START + MAX_PAYLOAD_SIZE - 1;
+
+ /** */
+ public static final short T_H2_EX_REF_MVCC_INNER_START = 26_000;
+
+ /** */
+ public static final short T_H2_EX_REF_MVCC_INNER_END = T_H2_EX_REF_MVCC_INNER_START + MAX_PAYLOAD_SIZE - 1;
+
+ /** */
private final int ver;
/** */
@@ -363,13 +423,19 @@ public abstract class PageIO {
*
* @param innerIOs Inner IO versions.
* @param leafIOs Leaf IO versions.
+ * @param mvccInnerIOs Inner IO versions with mvcc enabled.
+ * @param mvccLeafIOs Leaf IO versions with mvcc enabled.
*/
public static void registerH2(
IOVersions<? extends BPlusInnerIO<?>> innerIOs,
- IOVersions<? extends BPlusLeafIO<?>> leafIOs
+ IOVersions<? extends BPlusLeafIO<?>> leafIOs,
+ IOVersions<? extends BPlusInnerIO<?>> mvccInnerIOs,
+ IOVersions<? extends BPlusLeafIO<?>> mvccLeafIOs
) {
h2InnerIOs = innerIOs;
h2LeafIOs = leafIOs;
+ h2MvccInnerIOs = mvccInnerIOs;
+ h2MvccLeafIOs = mvccLeafIOs;
}
/**
@@ -377,8 +443,10 @@ public abstract class PageIO {
*
* @param innerExtIOs Extra versions.
*/
- public static void registerH2ExtraInner(IOVersions<? extends BPlusInnerIO<?>> innerExtIOs) {
- h2ExtraInnerIOs.add(innerExtIOs);
+ public static void registerH2ExtraInner(IOVersions<? extends BPlusInnerIO<?>> innerExtIOs, boolean mvcc) {
+ List<IOVersions<? extends BPlusInnerIO<?>>> ios = mvcc ? h2ExtraMvccInnerIOs : h2ExtraInnerIOs;
+
+ ios.add(innerExtIOs);
}
/**
@@ -386,24 +454,30 @@ public abstract class PageIO {
*
* @param leafExtIOs Extra versions.
*/
- public static void registerH2ExtraLeaf(IOVersions<? extends BPlusLeafIO<?>> leafExtIOs) {
- h2ExtraLeafIOs.add(leafExtIOs);
+ public static void registerH2ExtraLeaf(IOVersions<? extends BPlusLeafIO<?>> leafExtIOs, boolean mvcc) {
+ List<IOVersions<? extends BPlusLeafIO<?>>> ios = mvcc ? h2ExtraMvccLeafIOs : h2ExtraLeafIOs;
+
+ ios.add(leafExtIOs);
}
/**
* @param idx Index.
* @return IOVersions for given idx.
*/
- public static IOVersions<? extends BPlusInnerIO<?>> getInnerVersions(int idx) {
- return h2ExtraInnerIOs.get(idx);
+ public static IOVersions<? extends BPlusInnerIO<?>> getInnerVersions(int idx, boolean mvcc) {
+ List<IOVersions<? extends BPlusInnerIO<?>>> ios = mvcc ? h2ExtraMvccInnerIOs : h2ExtraInnerIOs;
+
+ return ios.get(idx);
}
/**
* @param idx Index.
* @return IOVersions for given idx.
*/
- public static IOVersions<? extends BPlusLeafIO<?>> getLeafVersions(int idx) {
- return h2ExtraLeafIOs.get(idx);
+ public static IOVersions<? extends BPlusLeafIO<?>> getLeafVersions(int idx, boolean mvcc) {
+ List<IOVersions<? extends BPlusLeafIO<?>>> ios = mvcc ? h2ExtraMvccLeafIOs : h2ExtraLeafIOs;
+
+ return ios.get(idx);
}
/**
@@ -525,13 +599,18 @@ public abstract class PageIO {
*/
@SuppressWarnings("unchecked")
public static <Q extends BPlusIO<?>> Q getBPlusIO(int type, int ver) throws IgniteCheckedException {
-
if (type >= T_H2_EX_REF_LEAF_START && type <= T_H2_EX_REF_LEAF_END)
return (Q)h2ExtraLeafIOs.get(type - T_H2_EX_REF_LEAF_START).forVersion(ver);
if (type >= T_H2_EX_REF_INNER_START && type <= T_H2_EX_REF_INNER_END)
return (Q)h2ExtraInnerIOs.get(type - T_H2_EX_REF_INNER_START).forVersion(ver);
+ if (type >= T_H2_EX_REF_MVCC_LEAF_START && type <= T_H2_EX_REF_MVCC_LEAF_END)
+ return (Q)h2ExtraMvccLeafIOs.get(type - T_H2_EX_REF_MVCC_LEAF_START).forVersion(ver);
+
+ if (type >= T_H2_EX_REF_MVCC_INNER_START && type <= T_H2_EX_REF_MVCC_INNER_END)
+ return (Q)h2ExtraMvccInnerIOs.get(type - T_H2_EX_REF_MVCC_INNER_START).forVersion(ver);
+
switch (type) {
case T_H2_REF_INNER:
if (h2InnerIOs == null)
@@ -545,6 +624,24 @@ public abstract class PageIO {
return (Q)h2LeafIOs.forVersion(ver);
+ case T_H2_MVCC_REF_INNER:
+ if (h2MvccInnerIOs == null)
+ break;
+
+ return (Q)h2MvccInnerIOs.forVersion(ver);
+
+ case T_H2_MVCC_REF_LEAF:
+ if (h2MvccLeafIOs == null)
+ break;
+
+ return (Q)h2MvccLeafIOs.forVersion(ver);
+
+ case T_TX_LOG_INNER:
+ return (Q)TxLogInnerIO.VERSIONS.forVersion(ver);
+
+ case T_TX_LOG_LEAF:
+ return (Q)TxLogLeafIO.VERSIONS.forVersion(ver);
+
case T_DATA_REF_INNER:
return (Q)DataInnerIO.VERSIONS.forVersion(ver);
@@ -557,6 +654,18 @@ public abstract class PageIO {
case T_CACHE_ID_AWARE_DATA_REF_LEAF:
return (Q)CacheIdAwareDataLeafIO.VERSIONS.forVersion(ver);
+ case T_CACHE_ID_DATA_REF_MVCC_INNER:
+ return (Q) MvccCacheIdAwareDataInnerIO.VERSIONS.forVersion(ver);
+
+ case T_CACHE_ID_DATA_REF_MVCC_LEAF:
+ return (Q) MvccCacheIdAwareDataLeafIO.VERSIONS.forVersion(ver);
+
+ case T_DATA_REF_MVCC_INNER:
+ return (Q)MvccDataInnerIO.VERSIONS.forVersion(ver);
+
+ case T_DATA_REF_MVCC_LEAF:
+ return (Q)MvccDataLeafIO.VERSIONS.forVersion(ver);
+
case T_METASTORE_INNER:
return (Q)IndexStorageImpl.MetaStoreInnerIO.VERSIONS.forVersion(ver);
http://git-wip-us.apache.org/repos/asf/ignite/blob/00bb4d4d/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/SimpleDataPageIO.java
----------------------------------------------------------------------
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/SimpleDataPageIO.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/SimpleDataPageIO.java
index f02e3a0..14489b7 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/SimpleDataPageIO.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/io/SimpleDataPageIO.java
@@ -113,12 +113,6 @@ public class SimpleDataPageIO extends AbstractDataPageIO<MetastorageDataRow> {
}
/** {@inheritDoc} */
- @Override public int getRowSize(MetastorageDataRow row) throws IgniteCheckedException {
- return 4 + row.value().length;
- }
-
-
- /** {@inheritDoc} */
@Override protected void printPage(long addr, int pageSize, GridStringBuilder sb) throws IgniteCheckedException {
sb.a("SimpleDataPageIO [\n");
printPageLayout(addr, pageSize, sb);