Kirill Tkalenko created IGNITE-16518:
----------------------------------------
Summary:
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
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)
