[
https://issues.apache.org/jira/browse/IGNITE-16518?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Kirill Tkalenko updated IGNITE-16518:
-------------------------------------
Description:
Found that the test sometimes fails:
*BPlusTreeReuseListPageMemoryImplTest.testMassiveRemove2_true* flaky.
https://ci.ignite.apache.org/project.html?tab=testDetails&projectId=IgniteTests24Java8&testNameId=7031624718556126435&page=1
Explanation
{noformat}
Here’s a tree and a set of operations that lead to undesired results:
[ 2 ]
/ \
[ 1 ] [ 3 | 4 ]
/ \ / | \
[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
// Remove 2
[ 1 ]
/ \
[ ] [ 3 | 4 ]
| / | \
[ 1 ] [ 3 ] [ 4 ] [ 5 ]
// Remove 5
[ 1 ]
/ \
[ ] [ 3 ]
| / \
[ 1 ] [ 3 ] [ 4 ]
// Remove 4
[ 1 ]
/ \
[ ] [ ]
| |
[ 1 ] [ 3 ]
// Remove 3
[ 1 ]
|
[ ]
|
[ 1 ]
// Remove 1
[ ]
|
[ ]
{noformat}
It’s clear that at some point we have a whole level consisting of routing
nodes. This later leads to somewhat incorrect “cut tree root” operation that
leaves empty leaf.
Possible solutions
* root cutting should probably be recursive and should proceed until root node
is not empty or is a leaf.
* merge operation should work better with routing nodes - every time there’s a
merge, we should consider the possibility to merge empty neighbor as well.
* re-balance data from neighbor when node becomes a router node. Might be
impossible or very challenging in current implementation.
Option 1 is the easiest one. Given the rarity of the case, I’d go with it.
was:
Found that the test sometimes fails:
*BPlusTreeReuseListPageMemoryImplTest.testMassiveRemove2_true* flaky.
https://ci.ignite.apache.org/project.html?tab=testDetails&projectId=IgniteTests24Java8&testNameId=7031624718556126435&page=1
Explanation
{noformat}
Here’s a tree and a set of operations that lead to undesired results:
[ 2 ]
/ \
[ 1 ] [ 3 | 4 ]
/ \ / | \
[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
// Remove 2
[ 1 ]
/ \
[ ] [ 3 | 4 ]
| / | \
[ 1 ] [ 3 ] [ 4 ] [ 5 ]
// Remove 5
[ 1 ]
/ \
[ ] [ 3 ]
| / \
[ 1 ] [ 3 ] [ 4 ]
// Remove 4
[ 1 ]
/ \
[ ] [ ]
| |
[ 1 ] [ 3 ]
// Remove 3
[ 1 ]
|
[ ]
|
[ 1 ]
// Remove 1
[ ]
|
[ ]
{noformat}
It’s clear that at some point we have a whole level consisting of routing
nodes. This later leads to somewhat incorrect “cut tree root” operation that
leaves empty leaf.
Possible solutions
root cutting should probably be recursive and should proceed until root node is
not empty or is a leaf.
merge operation should work better with routing nodes - every time there’s a
merge, we should consider the possibility to merge empty neighbor as well.
re-balance data from neighbor when node becomes a router node. Might be
impossible or very challenging in current implementation.
Option 1 is the easiest one. Given the rarity of the case, I’d go with it.
> BPlusTreeReuseListPageMemoryImplTest.testMassiveRemove2_true flaky
> ------------------------------------------------------------------
>
> Key: IGNITE-16518
> URL: https://issues.apache.org/jira/browse/IGNITE-16518
> Project: Ignite
> Issue Type: Bug
> Components: data structures
> Reporter: Kirill Tkalenko
> Assignee: Kirill Tkalenko
> Priority: Major
> Fix For: 2.13
>
>
> Found that the test sometimes fails:
> *BPlusTreeReuseListPageMemoryImplTest.testMassiveRemove2_true* flaky.
> https://ci.ignite.apache.org/project.html?tab=testDetails&projectId=IgniteTests24Java8&testNameId=7031624718556126435&page=1
> Explanation
> {noformat}
> Here’s a tree and a set of operations that lead to undesired results:
> [ 2 ]
> / \
> [ 1 ] [ 3 | 4 ]
> / \ / | \
> [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]
> // Remove 2
> [ 1 ]
> / \
> [ ] [ 3 | 4 ]
> | / | \
> [ 1 ] [ 3 ] [ 4 ] [ 5 ]
> // Remove 5
> [ 1 ]
> / \
> [ ] [ 3 ]
> | / \
> [ 1 ] [ 3 ] [ 4 ]
> // Remove 4
> [ 1 ]
> / \
> [ ] [ ]
> | |
> [ 1 ] [ 3 ]
> // Remove 3
> [ 1 ]
> |
> [ ]
> |
> [ 1 ]
> // Remove 1
> [ ]
> |
> [ ]
> {noformat}
> It’s clear that at some point we have a whole level consisting of routing
> nodes. This later leads to somewhat incorrect “cut tree root” operation that
> leaves empty leaf.
> Possible solutions
> * root cutting should probably be recursive and should proceed until root
> node is not empty or is a leaf.
> * merge operation should work better with routing nodes - every time there’s
> a merge, we should consider the possibility to merge empty neighbor as well.
> * re-balance data from neighbor when node becomes a router node. Might be
> impossible or very challenging in current implementation.
> Option 1 is the easiest one. Given the rarity of the case, I’d go with it.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
