You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by se...@apache.org on 2025/07/10 13:44:17 UTC
(ignite) branch master updated: IGNITE-25652 Fix BPlusTree corruption during concurrent removes (#12147)
This is an automated email from the ASF dual-hosted git repository.
sergeychugunov pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push:
new 59aeb4ca513 IGNITE-25652 Fix BPlusTree corruption during concurrent removes (#12147)
59aeb4ca513 is described below
commit 59aeb4ca51389c89b8e475c8b6beb645ba297945
Author: Phillippko <ph...@gmail.com>
AuthorDate: Thu Jul 10 17:44:11 2025 +0400
IGNITE-25652 Fix BPlusTree corruption during concurrent removes (#12147)
```needReplaceInner``` uses 4 state Bool, though it is not actually required
When ```mergeEmptyBranch``` releases tail for retry, ```needReplaceInner``` is not set back from ```READY``` to ```TRUE```
Checks ```needReplaceInner == TRUE``` then return false and node is not replaced correctly
Replaced 4 state Bool with normal boolean to simplify code
https://issues.apache.org/jira/browse/IGNITE-25652
---
.../cache/persistence/tree/BPlusTree.java | 45 ++++++++++------------
1 file changed, 20 insertions(+), 25 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 dd36238d875..060d357b025 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
@@ -653,14 +653,13 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
// Retry must reset these fields when we release the whole branch without remove.
- assert r.needReplaceInner == FALSE : "needReplaceInner";
- assert r.needMergeEmptyBranch == FALSE : "needMergeEmptyBranch";
+ assert !r.needReplaceInner && r.needMergeEmptyBranch == FALSE
+ : "needReplaceInner=" + r.needReplaceInner + ", needMergeEmptyBranch=" + r.needMergeEmptyBranch;
if (cnt == rmvCnt) // It was the last element on the leaf.
r.needMergeEmptyBranch = TRUE;
- if (needReplaceInner)
- r.needReplaceInner = TRUE;
+ r.needReplaceInner = needReplaceInner;
Tail<L> t = r.addTail(leafId, leafPage, leafAddr, io, 0, Tail.EXACT);
@@ -722,7 +721,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
Result res = doRemoveOrLockTail(idx, cnt, highIdx - idx + 1, leafId, leafPage, leafAddr, io, r);
// Search row should point to the rightmost element, otherwise we won't find it on the inner node.
- if (res == FOUND && r.needReplaceInner == TRUE)
+ if (res == FOUND && r.needReplaceInner)
r.row = getRow(io, leafAddr, highIdx, r.x);
return res;
@@ -4321,7 +4320,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
*/
public class Remove extends Update implements ReuseBag {
/** */
- Bool needReplaceInner = FALSE;
+ boolean needReplaceInner;
/** */
Bool needMergeEmptyBranch = FALSE;
@@ -4545,7 +4544,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
assert !isRemoved() : "removed";
// These fields will be setup again on remove from leaf.
- needReplaceInner = FALSE;
+ needReplaceInner = false;
needMergeEmptyBranch = FALSE;
releaseTail();
@@ -4571,16 +4570,17 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Here we wanted to do a regular merge after all the important operations,
// so we can leave this invalid tail as is. We have no other choice here
// because our tail is not long enough for retry. Exiting.
- assert isRemoved();
- assert needReplaceInner != TRUE && needMergeEmptyBranch != TRUE;
+ assert isRemoved() && !needReplaceInner && needMergeEmptyBranch != TRUE
+ : "isRemoved=" + isRemoved() + ", needReplaceInner=" + needReplaceInner
+ + ", needMergeEmptyBranch=" + needMergeEmptyBranch;
return false;
}
/** {@inheritDoc} */
@Override protected Result finishTail() throws IgniteCheckedException {
- assert !isFinished();
- assert tail.type == Tail.EXACT && tail.lvl >= 0 : tail;
+ assert !isFinished() && tail.type == Tail.EXACT && tail.lvl >= 0 && needMergeEmptyBranch != READY
+ : "isFinished=" + isFinished() + ", tail=" + tail + ", needMergeEmptyBranch=" + needMergeEmptyBranch;
if (tail.lvl == 0) {
// At the bottom level we can't have a tail without a sibling, it means we have higher levels.
@@ -4598,14 +4598,11 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
}
else {
// Try to find inner key on inner level.
- if (needReplaceInner == TRUE) {
+ if (needReplaceInner && !isInnerKeyInTail()) {
// Since we setup needReplaceInner in leaf page write lock and do not release it,
// we should not be able to miss the inner key. Even if concurrent merge
// happened the inner key must still exist.
- if (!isInnerKeyInTail())
- return NOT_FOUND; // Lock the whole branch up to the inner key.
-
- needReplaceInner = READY;
+ return NOT_FOUND; // Lock the whole branch up to the inner key.
}
// Try to merge an empty branch.
@@ -4632,14 +4629,12 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// The actual row remove may happen here as well.
mergeBottomUp(tail);
- if (needReplaceInner == READY) {
+ if (needReplaceInner) {
replaceInner(); // Replace inner key with new max key for the left subtree.
- needReplaceInner = DONE;
+ needReplaceInner = false;
}
- assert needReplaceInner != TRUE;
-
// Loop is needed to prevent the rare case when, after parallel remove of keys, empty root remains.
// B+tree after removes key: [empty_root] - [empty_inner_node] - [5] ==>
// B+tree after cutting empty root: [5]
@@ -4860,8 +4855,8 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
if (t.down == null) {
// It is just a regular merge in progress.
- assert needMergeEmptyBranch != TRUE;
- assert needReplaceInner != TRUE;
+ assert needMergeEmptyBranch != TRUE && !needReplaceInner
+ : "needMergeEmptyBranch=" + needMergeEmptyBranch + ", needReplaceInner" + needReplaceInner;
return true;
}
@@ -5034,7 +5029,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
* @throws IgniteCheckedException If failed.
*/
private void replaceInner() throws IgniteCheckedException {
- assert needReplaceInner == READY : needReplaceInner;
+ assert needReplaceInner;
int innerIdx;
@@ -6215,7 +6210,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
/** {@inheritDoc} */
@Override protected boolean releaseForRetry(Tail<L> t) {
// Reset search row to lower bound.
- if (t.lvl <= 1 && needReplaceInner != FALSE)
+ if (t.lvl <= 1 && needReplaceInner)
row = lower;
return super.releaseForRetry(t);
@@ -6230,7 +6225,7 @@ public abstract class BPlusTree<L, T extends L> extends DataStructure implements
// Continue operation - restart from the root.
row = lower;
- needReplaceInner = FALSE;
+ needReplaceInner = false;
needMergeEmptyBranch = FALSE;
rmvd = null;