[
https://issues.apache.org/jira/browse/IGNITE-16518?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17490109#comment-17490109
]
Kirill Tkalenko commented on IGNITE-16518:
------------------------------------------
[~ibessonov] Please make code review.
> 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
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> 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)
