You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by sb...@apache.org on 2019/02/26 12:17:31 UTC
[ignite] branch ignite-invokeAll updated (fc3b142 -> 613a4b0)
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a change to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git.
from fc3b142 invokeAll
new 1435c5b switchToNextRow
new 6d8f53b nextRow field
new 6cb4837 fixing concurrent issues
new 596f31a simplified the code and fixed routing pages handling
new 5368c25 minor
new 8e87906 fixed concurrent tests
new 7eed161 refactor
new 00ce2f9 simplify reuse bag
new 2c05b9b Revert "simplify reuse bag"
new d945a5c reuse
new 613a4b0 Merge branch 'data-load' into ignite-invokeAll
The 11 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../cache/persistence/tree/BPlusTree.java | 293 ++++++++++++++++-----
.../persistence/tree/reuse/LongListReuseBag.java | 21 ++
.../cache/persistence/tree/reuse/ReuseBag.java | 8 +
.../persistence/tree/reuse/SinglePageReuseBag.java | 9 +
.../apache/ignite/internal/util/GridLongList.java | 2 +-
.../database/BPlusTreeReuseSelfTest.java | 2 +
6 files changed, 267 insertions(+), 68 deletions(-)
[ignite] 09/11: Revert "simplify reuse bag"
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 2c05b9bee976438a9163f8cf7c5a6ca44a0d68f4
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Mon Feb 25 09:15:16 2019 +0300
Revert "simplify reuse bag"
This reverts commit 00ce2f97
---
.../internal/processors/cache/persistence/tree/reuse/ReuseBag.java | 5 +++++
.../processors/cache/persistence/tree/reuse/SinglePageReuseBag.java | 5 +++++
2 files changed, 10 insertions(+)
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
index 7ea44e4b..5d4579d 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
@@ -36,4 +36,9 @@ public interface ReuseBag {
* @return {@code true} if no contained page IDs for reuse.
*/
boolean isEmpty();
+
+ /**
+ * @return Number of pages for reuse in this bag.
+ */
+ int size();
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
index 0059f13..16a3868 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
@@ -62,6 +62,11 @@ public final class SinglePageReuseBag implements ReuseBag {
}
/** {@inheritDoc} */
+ @Override public int size() {
+ return pageId == 0L ? 0 : 1;
+ }
+
+ /** {@inheritDoc} */
@Override public String toString() {
return S.toString(SinglePageReuseBag.class, this, "pageId", U.hexLong(pageId));
}
[ignite] 05/11: minor
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 5368c2505ee4e3ac6a7aca89f7fd721bb0d1a55b
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 16:37:53 2019 +0300
minor
---
.../ignite/internal/processors/cache/persistence/tree/BPlusTree.java | 4 +---
1 file changed, 1 insertion(+), 3 deletions(-)
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 e4fa862..8d484ca 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
@@ -3058,8 +3058,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (fwdId == 0L || compare(io, pageAddr, cnt - 1, nextRow) >= 0)
gettingHighLvl = lvl;
else {
- // TODO may be compare to currently found insertion point instead of the rightmost row in the page??
-
// Because we unfinalize it after each switch to the next row.
assert gettingHighLvl >= 0: gettingHighLvl + " " + lvl;
@@ -3102,7 +3100,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// If it is a routing page or the search row is out of bounds for this page, need to get higher.
if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0)
- return Integer.MIN_VALUE; // Will be ignored, will get higher because gettingHigh flag was not reset.
+ return Integer.MIN_VALUE; // Will be ignored, we will get higher because gettingHigh flag was not reset.
gettingHigh = false; // Starting from this point we are high enough to have valid search.
}
[ignite] 08/11: simplify reuse bag
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 00ce2f97ac053646843b22517186445f4c7e68e6
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Mon Feb 25 09:13:22 2019 +0300
simplify reuse bag
---
.../internal/processors/cache/persistence/tree/reuse/ReuseBag.java | 5 -----
.../processors/cache/persistence/tree/reuse/SinglePageReuseBag.java | 5 -----
2 files changed, 10 deletions(-)
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
index 5d4579d..7ea44e4b 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
@@ -36,9 +36,4 @@ public interface ReuseBag {
* @return {@code true} if no contained page IDs for reuse.
*/
boolean isEmpty();
-
- /**
- * @return Number of pages for reuse in this bag.
- */
- int size();
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
index 16a3868..0059f13 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
@@ -62,11 +62,6 @@ public final class SinglePageReuseBag implements ReuseBag {
}
/** {@inheritDoc} */
- @Override public int size() {
- return pageId == 0L ? 0 : 1;
- }
-
- /** {@inheritDoc} */
@Override public String toString() {
return S.toString(SinglePageReuseBag.class, this, "pageId", U.hexLong(pageId));
}
[ignite] 07/11: refactor
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 7eed161402c2ccad0e2842811592fa5977d5991e
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 18:57:10 2019 +0300
refactor
---
.../cache/persistence/tree/BPlusTree.java | 46 +++++++++++++++++-----
1 file changed, 37 insertions(+), 9 deletions(-)
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 3d6adf2..37d7f68 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
@@ -3092,7 +3092,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// We should not touch the root to avoid contention on it, thus it is good idea to have it < rootLvl.
gettingHighLvl = retryJustHappened ?
lvl + 1 : // If the retry just happened, then we may guess that the tree was not changed much.
- (lvl + rootLvl) >>> 1; // Middle point between the root and the current level.
+ guessHighLevel(lvl);
// TODO Maybe we can have a better heuristic?
}
@@ -3104,6 +3104,39 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
+ * @param lvl Current level.
+ * @return Some level between the current and root.
+ */
+ private int guessHighLevel(int lvl) {
+ // Middle point between the root and the current level.
+ return (lvl + rootLvl) >>> 1;
+ }
+
+ /**
+ * @param lvl Current level.
+ * @param io Page IO.
+ * @param pageAddr Page address.
+ * @param cnt Row count.
+ * @return {@code true} If we need to get higher, {@code false} if we are high enough.
+ * @throws IgniteCheckedException If failed.
+ */
+ private boolean jumpHigher(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
+ assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough.
+
+ // If it is a routing page or the search row is out of bounds for this page, need to get higher.
+ if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0) {
+ // Jump higher: avoid moving page by page.
+ gettingHighLvl = guessHighLevel(lvl);
+
+ return true;
+ }
+
+ // Starting from this point we are high enough to have valid search.
+ gettingHigh = false;
+ return false;
+ }
+
+ /**
* @param lvl Level.
* @param io Page IO.
* @param pageAddr Page address.
@@ -3114,14 +3147,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
final int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
throws IgniteCheckedException {
- if (gettingHigh) {
- assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough.
-
- // If it is a routing page or the search row is out of bounds for this page, need to get higher.
- if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0)
- return Integer.MIN_VALUE; // Will be ignored, we will get higher because gettingHigh flag was not reset.
-
- gettingHigh = false; // Starting from this point we are high enough to have valid search.
+ if (gettingHigh && jumpHigher(lvl, io, pageAddr, cnt)) {
+ // The result will be ignored, we will get higher because gettingHigh flag was not reset.
+ return Integer.MIN_VALUE;
}
int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
[ignite] 04/11: simplified the code and fixed routing pages handling
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 596f31af64c26c3ab4808219205e1d3691753071
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 16:35:03 2019 +0300
simplified the code and fixed routing pages handling
---
.../cache/persistence/tree/BPlusTree.java | 70 +++++++---------------
1 file changed, 20 insertions(+), 50 deletions(-)
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 2eba7cc..e4fa862 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
@@ -3026,18 +3026,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
- * If we are not on the right edge of the page or there are no forward pages,
- * then we are high enough to have valid search from here.
- *
- * @param idx Insertion point.
- * @param cnt Row count.
- * @return {@code true} If this search result is always valid and can be used.
- */
- private boolean isValidSearch(int idx, int cnt) {
- return -idx - 1 != cnt || fwdId == 0L;
- }
-
- /**
* Marks level to get high with the next row after the current row will be processed.
*
* @param lvl Current level.
@@ -3049,6 +3037,16 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
private void markHighLevelForNextRow(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
throws IgniteCheckedException {
+ // This flag must always be reset at this point:
+ // it makes no sense to mark levels for the next rows while we are getting high.
+ assert !gettingHigh;
+
+ // For empty pages we do nothing: if we finalize the level we may miss better opportunities lower,
+ // on the other hand, no need to mark this level because it is just an empty routing page - we will
+ // waste resources on locking and reading it when we will get high.
+ if (cnt == 0)
+ return;
+
// If the high level is finalized we do not need to mark lower levels.
if (gettingHighLvl < 0 && lvl < -gettingHighLvl)
return;
@@ -3056,9 +3054,12 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Compare the next row with the rightmost row in the page (the next search row must always be greater than the current one).
// Mark the level if the rightmost row is greater or equal to the next search row.
// For all the rightmost pages with no forwards (including the root page) we always will have valid search.
+ // For empty pages we have to finalize
if (fwdId == 0L || compare(io, pageAddr, cnt - 1, nextRow) >= 0)
gettingHighLvl = lvl;
else {
+ // TODO may be compare to currently found insertion point instead of the rightmost row in the page??
+
// Because we unfinalize it after each switch to the next row.
assert gettingHighLvl >= 0: gettingHighLvl + " " + lvl;
@@ -3095,52 +3096,21 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
final int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
throws IgniteCheckedException {
- int idx;
if (gettingHigh) {
assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough.
- idx = findInsertionPointStartingFromRight(row, lvl, io, pageAddr, cnt);
+ // If it is a routing page or the search row is out of bounds for this page, need to get higher.
+ if (cnt == 0 || compare(lvl, io, pageAddr, cnt - 1, row) < 0)
+ return Integer.MIN_VALUE; // Will be ignored, will get higher because gettingHigh flag was not reset.
- if (isValidSearch(idx, cnt))
- gettingHigh = false;
+ gettingHigh = false; // Starting from this point we are high enough to have valid search.
}
- else
- idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
-
- if (nextRow != null && !gettingHigh)
- markHighLevelForNextRow(lvl, io, pageAddr, cnt);
-
- return idx;
- }
-
- /**
- * Like usual {@link #findInsertionPoint} but starting with the rightmost row instead of the middle row.
- *
- * @param searchRow Search row.
- * @param lvl Level.
- * @param io Page IO.
- * @param pageAddr Page address.
- * @param cnt Row count.
- * @return Insertion point.
- */
- final int findInsertionPointStartingFromRight(L searchRow, int lvl, BPlusIO<L> io, long pageAddr, int cnt)
- throws IgniteCheckedException {
- int idx;
- if (cnt == 0)
- idx = -1; // The page is empty, nothing to search (and need to get higher if there are forward pages).
- else {
- // Try to compare with the rightmost row before doing binary search.
- int cmp = compare(lvl, io, pageAddr, cnt - 1, searchRow);
+ int idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
- if (cmp > 0) // Search row is less than the last row in the page, need to do binary search.
- idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, searchRow, shift);
- else if (cmp == 0)
- idx = cnt - 1; // Search row is equal to the last row in the page.
- else
- idx = -cnt - 1; // Search row is greater than the last row in the page.
- }
+ if (nextRow != null)
+ markHighLevelForNextRow(lvl, io, pageAddr, cnt);
return idx;
}
[ignite] 11/11: Merge branch 'data-load' into ignite-invokeAll
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 613a4b009cc0729da19fa473c8de1862e78e7d7e
Merge: fc3b142 d945a5c
Author: sboikov <sb...@apache.org>
AuthorDate: Tue Feb 26 15:12:17 2019 +0300
Merge branch 'data-load' into ignite-invokeAll
.../cache/persistence/tree/BPlusTree.java | 293 ++++++++++++++++-----
.../persistence/tree/reuse/LongListReuseBag.java | 21 ++
.../cache/persistence/tree/reuse/ReuseBag.java | 8 +
.../persistence/tree/reuse/SinglePageReuseBag.java | 9 +
.../apache/ignite/internal/util/GridLongList.java | 2 +-
.../database/BPlusTreeReuseSelfTest.java | 2 +
6 files changed, 267 insertions(+), 68 deletions(-)
diff --cc modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/BPlusTree.java
index d794840,99efaff..bb52347
--- 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
@@@ -4035,10 -4177,10 +4177,10 @@@ public abstract class BPlusTree<L, T ex
Iterator<? extends L> sortedRows;
/** */
- Function<L, InvokeClosure<T>> closures;
+ Function<L, ? extends InvokeClosure<T>> closures;
/** */
- ReuseBag reuseBag;
+ ReuseBag reuseBag = new LongListReuseBag();
/**
* @param firstRow The first row.
[ignite] 03/11: fixing concurrent issues
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 6cb48373558061ecfa6a5a7657c55ce9aca614c6
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 16:00:37 2019 +0300
fixing concurrent issues
---
.../cache/persistence/tree/BPlusTree.java | 137 ++++++++++++++++++---
.../database/BPlusTreeReuseSelfTest.java | 2 +
2 files changed, 123 insertions(+), 16 deletions(-)
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 f911280..2eba7cc 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
@@ -1322,6 +1322,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
try {
for (;;) {
+ if (g.needGetHigher(lvl))
+ return RETRY;
+
g.checkLockRetry();
// Init args.
@@ -1928,6 +1931,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
Result res = RETRY;
for (;;) {
+ if (x.needGetHigher(lvl))
+ return RETRY;
+
if (res == RETRY)
x.checkLockRetry();
@@ -2098,6 +2104,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
try {
for (;;) {
+ if (r.needGetHigher(lvl))
+ return RETRY;
+
r.checkLockRetry();
// Init args.
@@ -2593,7 +2602,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param pageId Page ID.
* @param page Page pointer.
- * @param pageAddr Page address
+ * @param pageAddr Page address.
* @param io IO.
* @param fwdId Forward page ID.
* @param fwdBuf Forward buffer.
@@ -2630,7 +2639,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/**
* @param pageId Page ID.
* @param page Page pointer.
- * @param pageAddr Page address
+ * @param pageAddr Page address.
* @param walPlc Full page WAL record policy.
*/
private void writeUnlockAndClose(long pageId, long page, long pageAddr, Boolean walPlc) {
@@ -2669,6 +2678,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
try {
for (;;) {
+ if (p.needGetHigher(lvl))
+ return RETRY;
+
p.checkLockRetry();
// Init args.
@@ -2890,11 +2902,16 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
int lockRetriesCnt = getLockRetries();
/**
- * Used when invokeAll operation updated one or more keys on the left side of the tree
+ * Used when {@link InvokeAll} or another batch operation updated one or more keys on the left side of the tree
* and needs to get high enough to find the rest of rows on the right side.
*/
boolean gettingHigh;
+ /**
+ * Used in batch operations like {@link InvokeAll}:
+ */
+ int gettingHighLvl;
+
/** Used in batch operations like {@link InvokeAll}. */
L nextRow;
@@ -2979,6 +2996,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert !gettingHigh;
gettingHigh = true;
+ if (gettingHighLvl < 0) // Unfinalize high level.
+ gettingHighLvl = -gettingHighLvl;
+
// Reinitialize state to continue working with the next row.
lockRetriesCnt = getLockRetries();
@@ -2996,6 +3016,76 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/**
+ * Check for batch operations needed after switching to the next row.
+ *
+ * @param lvl Current level.
+ * @return {@code true} If need to get higher.
+ */
+ final boolean needGetHigher(int lvl) {
+ return gettingHigh && lvl < Math.abs(gettingHighLvl);
+ }
+
+ /**
+ * If we are not on the right edge of the page or there are no forward pages,
+ * then we are high enough to have valid search from here.
+ *
+ * @param idx Insertion point.
+ * @param cnt Row count.
+ * @return {@code true} If this search result is always valid and can be used.
+ */
+ private boolean isValidSearch(int idx, int cnt) {
+ return -idx - 1 != cnt || fwdId == 0L;
+ }
+
+ /**
+ * Marks level to get high with the next row after the current row will be processed.
+ *
+ * @param lvl Current level.
+ * @param io Page IO.
+ * @param pageAddr Page address.
+ * @param idx Index of the current row.
+ * @param cnt Row count.
+ * @throws IgniteCheckedException If failed.
+ */
+ private void markHighLevelForNextRow(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
+ throws IgniteCheckedException {
+ // If the high level is finalized we do not need to mark lower levels.
+ if (gettingHighLvl < 0 && lvl < -gettingHighLvl)
+ return;
+
+ // Compare the next row with the rightmost row in the page (the next search row must always be greater than the current one).
+ // Mark the level if the rightmost row is greater or equal to the next search row.
+ // For all the rightmost pages with no forwards (including the root page) we always will have valid search.
+ if (fwdId == 0L || compare(io, pageAddr, cnt - 1, nextRow) >= 0)
+ gettingHighLvl = lvl;
+ else {
+ // Because we unfinalize it after each switch to the next row.
+ assert gettingHighLvl >= 0: gettingHighLvl + " " + lvl;
+
+ // If the marked high level is lower then the current level, it means that we jumped high after
+ // processing previous rows and comparing here the new next row for the first time. We have already
+ // compared this new next row to the page bound and it known to be greater, it means that
+ // the correct high level for the new next row is even higher than the current level and we do not know
+ // exactly where it is. Thus, we just guess it is somewhere between lvl and rootLvl.
+ // We do not want to mark high levels for more than one next row because in presence of
+ // concurrent modifications these levels often will be wrong, producing pointless extra work,
+ // there also will be space overhead of storing them.
+ if (gettingHighLvl <= lvl) {
+ assert rootLvl > lvl; // Because otherwise we must be in the root here and must end up marking level in prev branch.
+
+ // Heuristic to guess level for the next row.
+ gettingHighLvl = (lvl + rootLvl) >>> 1;
+
+ assert gettingHighLvl < rootLvl; // We should not touch root to avoid contention on it.
+ }
+
+ // Finalize the previous marked level since the next row is out of bounds in the current subtree.
+ // We do this finalization to avoid extra work on lower levels, where we already know the high level.
+ gettingHighLvl = -gettingHighLvl - 1;
+ }
+ }
+
+ /**
* @param lvl Level.
* @param io Page IO.
* @param pageAddr Page address.
@@ -3003,43 +3093,55 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Insertion point.
* @throws IgniteCheckedException If failed.
*/
- int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
- return gettingHigh ?
- findInsertionPointGettingHigh(lvl, io, pageAddr, cnt) :
- findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
+ final int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt)
+ throws IgniteCheckedException {
+ int idx;
+
+ if (gettingHigh) {
+ assert lvl >= Math.abs(gettingHighLvl); // We should not get here until we are high enough.
+
+ idx = findInsertionPointStartingFromRight(row, lvl, io, pageAddr, cnt);
+
+ if (isValidSearch(idx, cnt))
+ gettingHigh = false;
+ }
+ else
+ idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
+
+ if (nextRow != null && !gettingHigh)
+ markHighLevelForNextRow(lvl, io, pageAddr, cnt);
+
+ return idx;
}
/**
- * For compound operations like {@link InvokeAll}.
+ * Like usual {@link #findInsertionPoint} but starting with the rightmost row instead of the middle row.
*
+ * @param searchRow Search row.
* @param lvl Level.
* @param io Page IO.
* @param pageAddr Page address.
* @param cnt Row count.
* @return Insertion point.
*/
- protected final int findInsertionPointGettingHigh(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
+ final int findInsertionPointStartingFromRight(L searchRow, int lvl, BPlusIO<L> io, long pageAddr, int cnt)
+ throws IgniteCheckedException {
int idx;
if (cnt == 0)
idx = -1; // The page is empty, nothing to search (and need to get higher if there are forward pages).
else {
// Try to compare with the rightmost row before doing binary search.
- int cmp = compare(lvl, io, pageAddr, cnt - 1, row);
+ int cmp = compare(lvl, io, pageAddr, cnt - 1, searchRow);
if (cmp > 0) // Search row is less than the last row in the page, need to do binary search.
- idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
+ idx = findInsertionPoint(lvl, io, pageAddr, 0, cnt, searchRow, shift);
else if (cmp == 0)
idx = cnt - 1; // Search row is equal to the last row in the page.
else
idx = -cnt - 1; // Search row is greater than the last row in the page.
}
- // If we are not on the right edge of the page or there are no forward pages,
- // then we are high enough to have valid search from here.
- if (-idx - 1 != cnt || fwdId == 0L)
- gettingHigh = false;
-
return idx;
}
@@ -3054,6 +3156,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
backId = g.backId;
shift = g.shift;
findLast = g.findLast;
+ // Do not copy batch related fields.
}
/**
@@ -3078,6 +3181,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.rootId = rootId;
this.rootLvl = rootLvl;
this.rmvId = rmvId;
+ gettingHigh = false;
+ gettingHighLvl = rootLvl;
}
/**
diff --git a/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeReuseSelfTest.java b/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeReuseSelfTest.java
index 417efd1..38002c2 100644
--- a/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeReuseSelfTest.java
+++ b/modules/core/src/test/java/org/apache/ignite/internal/processors/database/BPlusTreeReuseSelfTest.java
@@ -355,6 +355,8 @@ public class BPlusTreeReuseSelfTest extends BPlusTreeSelfTest {
tree.invokeAll(all.iterator(), null, new UpdateAllClosure());
+ tree.validateTree();
+
assertEqualContents(tree, set);
}
}
[ignite] 02/11: nextRow field
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 6d8f53b31dbef26636da42804cfb6e0cfe1c2787
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Fri Feb 22 21:26:33 2019 +0300
nextRow field
---
.../cache/persistence/tree/BPlusTree.java | 44 +++++++++++++++++-----
1 file changed, 34 insertions(+), 10 deletions(-)
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 a02df7d..f911280 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
@@ -2895,6 +2895,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
boolean gettingHigh;
+ /** Used in batch operations like {@link InvokeAll}. */
+ L nextRow;
+
/**
* @param row Row.
* @param findLast find last row.
@@ -2908,6 +2911,18 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.findLast = findLast;
}
+ /**
+ * @param sortedRows Sorted rows.
+ */
+ final void takeNextRow(Iterator<? extends L> sortedRows) {
+ if (sortedRows.hasNext()) {
+ nextRow = sortedRows.next();
+ assert nextRow != null;
+ }
+ else
+ nextRow = null;
+ }
+
@SuppressWarnings({"unchecked", "WrapperTypeMayBePrimitive"})
protected final T convertOldRow(boolean needOld, T oldRow) {
if (needOld)
@@ -2952,10 +2967,14 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param sortedRows Sorted rows.
* @return {@code true} If was successfully switched to the next row.
*/
- protected final boolean doNextRow(Result res, Iterator<? extends L> sortedRows) {
- if (res.retry || !isFinished() || !sortedRows.hasNext())
+ protected final boolean doSwitchToNextRow(Result res, Iterator<? extends L> sortedRows) {
+ if (nextRow == null || res.retry || !isFinished())
return false;
+ // Switch to the next row.
+ row = nextRow;
+ takeNextRow(sortedRows);
+
// Well need to get high enough to start new search.
assert !gettingHigh;
gettingHigh = true;
@@ -2963,9 +2982,6 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Reinitialize state to continue working with the next row.
lockRetriesCnt = getLockRetries();
- row = sortedRows.next();
- assert row != null;
-
return true;
}
@@ -3002,7 +3018,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param cnt Row count.
* @return Insertion point.
*/
- private int findInsertionPointGettingHigh(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
+ protected final int findInsertionPointGettingHigh(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
int idx;
if (cnt == 0)
@@ -3224,11 +3240,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.sortedRows = sortedRows;
foundRows = new ArrayList<>();
+
+ takeNextRow(sortedRows);
}
/** {@inheritDoc} */
@Override boolean switchToNextRow(Result res) {
- if (!doNextRow(res, sortedRows))
+ if (!doSwitchToNextRow(res, sortedRows))
return false;
// Reset state.
@@ -3656,11 +3674,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.sortedRows = sortedRows;
oldRows = new ArrayList<>();
+
+ takeNextRow(sortedRows);
}
/** {@inheritDoc} */
@Override boolean switchToNextRow(Result res) {
- if (!doNextRow(res, sortedRows))
+ if (!doSwitchToNextRow(res, sortedRows))
return false;
// Reset state.
@@ -4051,11 +4071,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.sortedRows = sortedRows;
this.closures = closures;
+
+ takeNextRow(sortedRows);
}
/** {@inheritDoc} */
@Override boolean switchToNextRow(Result res) throws IgniteCheckedException {
- if (!doNextRow(res, sortedRows))
+ if (!doSwitchToNextRow(res, sortedRows))
return false;
reuseFreePagesFromBag(reuseBag, 15);
@@ -4404,11 +4426,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
this.sortedRows = sortedRows;
removedRows = new ArrayList<>();
+
+ takeNextRow(sortedRows);
}
/** {@inheritDoc} */
@Override boolean switchToNextRow(Result res) throws IgniteCheckedException {
- if (!doNextRow(res, sortedRows))
+ if (!doSwitchToNextRow(res, sortedRows))
return false;
reuseFreePagesFromBag(reuseBag, 15);
[ignite] 01/11: switchToNextRow
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 1435c5bcdff4ae2c424e7ad02c14195133f7c6dd
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Fri Feb 22 20:49:35 2019 +0300
switchToNextRow
---
.../cache/persistence/tree/BPlusTree.java | 44 +++++++++++-----------
1 file changed, 22 insertions(+), 22 deletions(-)
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 63a3d2c..a02df7d 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
@@ -1301,7 +1301,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
Result res = findDown(g, g.rootId, 0L, g.rootLvl);
- if (!res.retry && !g.nextRow(res))
+ if (!res.retry && !g.switchToNextRow(res))
return;
checkInterrupted();
@@ -1354,7 +1354,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
case FOUND:
g.finish();
- if (g.nextRow(res))
+ if (g.switchToNextRow(res))
continue;
// Intentional fallthrough.
@@ -1884,7 +1884,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert x.isFinished(): res;
}
- if (x.nextRow(FOUND))
+ if (x.switchToNextRow(FOUND))
continue;
return;
@@ -1960,7 +1960,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (res != RETRY)
res = invokeDown(x, x.pageId, x.backId, x.fwdId, lvl - 1);
- if (x.nextRow(res))
+ if (x.switchToNextRow(res))
continue;
if (res == RETRY_ROOT || x.isFinished())
@@ -1980,7 +1980,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = x.finishOrLockTail(pageId, page, backId, fwdId, lvl);
- if (x.nextRow(res))
+ if (x.switchToNextRow(res))
continue;
return res;
@@ -1991,7 +1991,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = x.onNotFound(pageId, page, fwdId, lvl);
- if (x.nextRow(res))
+ if (x.switchToNextRow(res))
continue;
return res;
@@ -2002,7 +2002,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = x.onFound(pageId, page, backId, fwdId, lvl);
- if (x.nextRow(res))
+ if (x.switchToNextRow(res))
continue;
return res;
@@ -2059,7 +2059,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert r.isFinished();
}
- if (r.nextRow(FOUND))
+ if (r.switchToNextRow(FOUND))
continue;
return r.rmvdRow;
@@ -2126,7 +2126,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
case GO_DOWN:
res = removeDown(r, r.pageId, r.backId, r.fwdId, lvl - 1);
- if (r.nextRow(res))
+ if (r.switchToNextRow(res))
continue;
if (res == RETRY) {
@@ -2140,7 +2140,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = r.finishOrLockTail(pageId, page, backId, fwdId, lvl);
- if (r.nextRow(res))
+ if (r.switchToNextRow(res))
continue;
return res;
@@ -2151,7 +2151,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
r.finish();
- if (r.nextRow(res))
+ if (r.switchToNextRow(res))
continue;
return res;
@@ -2159,7 +2159,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
case FOUND:
res = r.tryRemoveFromLeaf(pageId, page, backId, fwdId, lvl);
- if (r.nextRow(res))
+ if (r.switchToNextRow(res))
continue;
return res;
@@ -2447,7 +2447,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
continue;
}
- if (p.nextRow(FOUND))
+ if (p.switchToNextRow(FOUND))
continue;
return p.oldRow;
@@ -2689,7 +2689,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (res != RETRY) // Go down recursively.
res = putDown(p, p.pageId, p.fwdId, lvl - 1);
- if (p.nextRow(res))
+ if (p.switchToNextRow(res))
continue;
if (res == RETRY_ROOT || p.isFinished())
@@ -2705,7 +2705,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = p.tryReplace(pageId, page, fwdId, lvl);
- if (p.nextRow(res))
+ if (p.switchToNextRow(res))
continue;
return res;
@@ -2716,7 +2716,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
res = p.tryInsert(pageId, page, fwdId, lvl);
- if (p.nextRow(res))
+ if (p.switchToNextRow(res))
continue;
return res;
@@ -2975,7 +2975,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param res Last result.
* @return {@code true} If we have switched to the next row to process it.
*/
- boolean nextRow(Result res) throws IgniteCheckedException {
+ boolean switchToNextRow(Result res) throws IgniteCheckedException {
return false;
}
@@ -2987,7 +2987,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return Insertion point.
* @throws IgniteCheckedException If failed.
*/
- final int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
+ int findInsertionPointx(int lvl, BPlusIO<L> io, long pageAddr, int cnt) throws IgniteCheckedException {
return gettingHigh ?
findInsertionPointGettingHigh(lvl, io, pageAddr, cnt) :
findInsertionPoint(lvl, io, pageAddr, 0, cnt, row, shift);
@@ -3227,7 +3227,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/** {@inheritDoc} */
- @Override boolean nextRow(Result res) {
+ @Override boolean switchToNextRow(Result res) {
if (!doNextRow(res, sortedRows))
return false;
@@ -3659,7 +3659,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/** {@inheritDoc} */
- @Override boolean nextRow(Result res) {
+ @Override boolean switchToNextRow(Result res) {
if (!doNextRow(res, sortedRows))
return false;
@@ -4054,7 +4054,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/** {@inheritDoc} */
- @Override boolean nextRow(Result res) throws IgniteCheckedException {
+ @Override boolean switchToNextRow(Result res) throws IgniteCheckedException {
if (!doNextRow(res, sortedRows))
return false;
@@ -4407,7 +4407,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/** {@inheritDoc} */
- @Override boolean nextRow(Result res) throws IgniteCheckedException {
+ @Override boolean switchToNextRow(Result res) throws IgniteCheckedException {
if (!doNextRow(res, sortedRows))
return false;
[ignite] 10/11: reuse
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit d945a5cef04c1be25858a6444edb21607a085e92
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Mon Feb 25 11:05:47 2019 +0300
reuse
---
.../cache/persistence/tree/BPlusTree.java | 31 ++++++++++++++++------
.../persistence/tree/reuse/LongListReuseBag.java | 21 +++++++++++++++
.../cache/persistence/tree/reuse/ReuseBag.java | 8 ++++++
.../persistence/tree/reuse/SinglePageReuseBag.java | 9 +++++++
.../apache/ignite/internal/util/GridLongList.java | 2 +-
5 files changed, 62 insertions(+), 9 deletions(-)
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 37d7f68..99efaff 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
@@ -2957,7 +2957,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @return The same or new reuse bag containing the given page id.
*/
protected final ReuseBag addFreePageToBag(ReuseBag reuseBag, long pageId) throws IgniteCheckedException {
- if (invoke != null && invoke.addFreePage(pageId))
+ if (invoke != null && invoke.addFreePageForReuse(pageId))
return reuseBag;
assert pageId != 0L;
@@ -3984,7 +3984,9 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
private L insertWithSplit(long pageId, long page, long pageAddr, BPlusIO<L> io, int idx, int lvl)
throws IgniteCheckedException {
- long fwdId = allocatePage(null);
+ ReuseBag bag = invoke == null ? null : invoke.getReuseBag();
+
+ long fwdId = allocatePage(bag);
long fwdPage = acquirePage(fwdId);
try {
@@ -4032,7 +4034,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
if (!hadFwd && lvl == getRootLevel()) { // We are splitting root.
- long newRootId = allocatePage(null);
+ long newRootId = allocatePage(bag);
long newRootPage = acquirePage(newRootId);
try {
@@ -4178,7 +4180,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
Function<L, InvokeClosure<T>> closures;
/** */
- ReuseBag reuseBag;
+ ReuseBag reuseBag = new LongListReuseBag();
/**
* @param firstRow The first row.
@@ -4200,7 +4202,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (!doSwitchToNextRow(res, sortedRows))
return false;
- reuseFreePagesFromBag(reuseBag, 15);
+ if (reuseBag.size() > 128)
+ reuseFreePagesFromBag(reuseBag.take(64), 0);
// Create a new closure for the switched row.
clo = closures.apply(row);
@@ -4214,13 +4217,18 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
/** {@inheritDoc} */
- @Override boolean addFreePage(long pageId) throws IgniteCheckedException {
+ @Override boolean addFreePageForReuse(long pageId) throws IgniteCheckedException {
reuseBag = addFreePageToBag(reuseBag, pageId);
return true;
}
/** {@inheritDoc} */
+ @Override public ReuseBag getReuseBag() {
+ return reuseBag;
+ }
+
+ /** {@inheritDoc} */
@Override void releaseAll() throws IgniteCheckedException {
super.releaseAll();
@@ -4522,9 +4530,16 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @param pageId Page Id for reuse.
* @return {@code true} If it was accepted.
*/
- boolean addFreePage(long pageId) throws IgniteCheckedException {
+ boolean addFreePageForReuse(long pageId) throws IgniteCheckedException {
return false;
}
+
+ /**
+ * @return Reuse bag for this operation.
+ */
+ ReuseBag getReuseBag() {
+ return null;
+ }
}
/**
@@ -4555,7 +4570,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (!doSwitchToNextRow(res, sortedRows))
return false;
- reuseFreePagesFromBag(reuseBag, 15);
+ reuseFreePagesFromBag(reuseBag, 16);
// Reset state.
rmvdRow = null;
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java
index c7be05e..3381be8 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/LongListReuseBag.java
@@ -35,6 +35,13 @@ public final class LongListReuseBag extends GridLongList implements ReuseBag {
}
/**
+ * @param pageIds Page ids.
+ */
+ public LongListReuseBag(long[] pageIds) {
+ super(pageIds);
+ }
+
+ /**
* @param size Initial size.
* @param bag Bag to take pages from.
*/
@@ -62,4 +69,18 @@ public final class LongListReuseBag extends GridLongList implements ReuseBag {
@Override public long pollFreePage() {
return isEmpty() ? 0L : remove();
}
+
+ /** {@inheritDoc} */
+ @Override public ReuseBag take(int cnt) {
+ assert cnt > 0: cnt;
+
+ if (cnt > size())
+ return null;
+
+ long[] res = new long[cnt];
+ System.arraycopy(arr, size() - cnt, res, 0, cnt);
+ pop(cnt);
+
+ return new LongListReuseBag(res);
+ }
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
index 5d4579d..65aac99 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/ReuseBag.java
@@ -41,4 +41,12 @@ public interface ReuseBag {
* @return Number of pages for reuse in this bag.
*/
int size();
+
+ /**
+ * Takes and removes {@code cnt} pages from this bag.
+ *
+ * @param cnt Number of pages to take.
+ * @return Bag or {@code null} if there are not enough pages in this bag.
+ */
+ ReuseBag take(int cnt);
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
index 16a3868..468bf84 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/processors/cache/persistence/tree/reuse/SinglePageReuseBag.java
@@ -67,6 +67,15 @@ public final class SinglePageReuseBag implements ReuseBag {
}
/** {@inheritDoc} */
+ @Override public ReuseBag take(int cnt) {
+ assert cnt > 0: cnt;
+
+ long id = pollFreePage();
+
+ return id == 0L ? null : new SinglePageReuseBag(id);
+ }
+
+ /** {@inheritDoc} */
@Override public String toString() {
return S.toString(SinglePageReuseBag.class, this, "pageId", U.hexLong(pageId));
}
diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/GridLongList.java b/modules/core/src/main/java/org/apache/ignite/internal/util/GridLongList.java
index 1c022b0..0d34ea0 100644
--- a/modules/core/src/main/java/org/apache/ignite/internal/util/GridLongList.java
+++ b/modules/core/src/main/java/org/apache/ignite/internal/util/GridLongList.java
@@ -48,7 +48,7 @@ public class GridLongList implements Message, Externalizable {
public static final long[] EMPTY_ARRAY = new long[0];
/** */
- private long[] arr;
+ protected long[] arr;
/** */
private int idx;
[ignite] 06/11: fixed concurrent tests
Posted by sb...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
sboikov pushed a commit to branch ignite-invokeAll
in repository https://gitbox.apache.org/repos/asf/ignite.git
commit 8e87906346f26825a053bbfba69c0164b5bdda12
Author: Sergi Vladykin <se...@gmail.com>
AuthorDate: Sun Feb 24 17:51:00 2019 +0300
fixed concurrent tests
---
.../cache/persistence/tree/BPlusTree.java | 43 ++++++++++++++++------
1 file changed, 31 insertions(+), 12 deletions(-)
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 8d484ca..3d6adf2 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
@@ -3047,9 +3047,23 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (cnt == 0)
return;
- // If the high level is finalized we do not need to mark lower levels.
- if (gettingHighLvl < 0 && lvl < -gettingHighLvl)
- return;
+ boolean retryJustHappened = false;
+
+ // Handle finalized high level.
+ if (gettingHighLvl < 0) {
+ // Do not need to mark levels lower than the finalized high level:
+ // we already know that the next row is in another subtree.
+ if (lvl < -gettingHighLvl)
+ return;
+
+ // We unfinalize the high level after each switch to the next row,
+ // so we can not get finalized high level from the previous processed row.
+ // The current level is higher or equal to the finalized high level,
+ // thus we have a RETRY (not RETRY_ROOT, because it resets gettingHighLvl field to rootLvl).
+ // Unfinalize the high level to handle the new tree state.
+ retryJustHappened = true;
+ gettingHighLvl = -gettingHighLvl;
+ }
// Compare the next row with the rightmost row in the page (the next search row must always be greater than the current one).
// Mark the level if the rightmost row is greater or equal to the next search row.
@@ -3058,29 +3072,34 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (fwdId == 0L || compare(io, pageAddr, cnt - 1, nextRow) >= 0)
gettingHighLvl = lvl;
else {
- // Because we unfinalize it after each switch to the next row.
- assert gettingHighLvl >= 0: gettingHighLvl + " " + lvl;
+ assert gettingHighLvl >= 0;
// If the marked high level is lower then the current level, it means that we jumped high after
- // processing previous rows and comparing here the new next row for the first time. We have already
- // compared this new next row to the page bound and it known to be greater, it means that
+ // processing previous rows and comparing here the new next row for the first time.
+ // Or otherwise it was a concurrent tree modification that caused the retry in this thread.
+ //
+ // We have already compared this new next row to the page bound and it known to be greater, it means that
// the correct high level for the new next row is even higher than the current level and we do not know
- // exactly where it is. Thus, we just guess it is somewhere between lvl and rootLvl.
+ // exactly where it is. We can only guess it is somewhere between lvl and rootLvl.
+ //
// We do not want to mark high levels for more than one next row because in presence of
// concurrent modifications these levels often will be wrong, producing pointless extra work,
// there also will be space overhead of storing them.
if (gettingHighLvl <= lvl) {
assert rootLvl > lvl; // Because otherwise we must be in the root here and must end up marking level in prev branch.
- // Heuristic to guess level for the next row.
- gettingHighLvl = (lvl + rootLvl) >>> 1;
+ // Heuristic to guess the high level for the next row.
+ // We should not touch the root to avoid contention on it, thus it is good idea to have it < rootLvl.
+ gettingHighLvl = retryJustHappened ?
+ lvl + 1 : // If the retry just happened, then we may guess that the tree was not changed much.
+ (lvl + rootLvl) >>> 1; // Middle point between the root and the current level.
- assert gettingHighLvl < rootLvl; // We should not touch root to avoid contention on it.
+ // TODO Maybe we can have a better heuristic?
}
// Finalize the previous marked level since the next row is out of bounds in the current subtree.
// We do this finalization to avoid extra work on lower levels, where we already know the high level.
- gettingHighLvl = -gettingHighLvl - 1;
+ gettingHighLvl = -gettingHighLvl;
}
}