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);