Package org.apache.ignite.internal.persistence.tree

Class BPlusTreeReplaceRemoveRaceTest

java.lang.Object

org.apache.ignite.internal.persistence.tree.BPlusTreeReplaceRemoveRaceTest

public class BPlusTreeReplaceRemoveRaceTest
extends Object

Test is based on BPlusTreeSelfTest and has a partial copy of its code.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	BPlusTreeReplaceRemoveRaceTest.Pair	Short for T2<Integer, Integer>.
protected static class	BPlusTreeReplaceRemoveRaceTest.TestPairTree	Test tree, maps Integer to Integer.

Field Summary

Fields

Modifier and Type	Field	Description
protected static final int	PAGE_SIZE
protected PageMemory	pageMem

Constructor Summary

Constructors

Constructor	Description
BPlusTreeReplaceRemoveRaceTest()

Method Summary

Modifier and Type	Method	Description
void	setUp()
void	tearDown()
void	testConcurrentPutRemove()	Tests a very specific scenario for concurrent replace and remove that used to corrupt the tree before the fix.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

PAGE_SIZE

protected static final int PAGE_SIZE

See Also:

• Constant Field Values

pageMem

protected PageMemory pageMem

Constructor Details

BPlusTreeReplaceRemoveRaceTest

public BPlusTreeReplaceRemoveRaceTest()

Method Details

setUp

public void setUp()

tearDown

public void tearDown()
              throws IgniteCheckedException

Throws:

IgniteCheckedException

testConcurrentPutRemove

public void testConcurrentPutRemove()
                             throws Exception

Tests a very specific scenario for concurrent replace and remove that used to corrupt the tree before the fix.

Consider the following tree, represented by a tree variable in test:

                                    [ 5:0 ]
                                /            \
                 [ 2:0 | 4:0 ]                  [ 6:0 ]
               /       |       \               /       \
 [ 1:0 | 2:0 ]   [ 3:0 | 4:0 ]   [ 5:0 ]   [ 6:0 ]   [ 7:0 ]
 

Individual replace 4:0 to 4:8 would take two steps and look like this:

 // Inner node goes first.
                                    [ 5:0 ]
                                /            \
                 [ 2:0 | 4:8 ]                  [ 6:0 ]
               /       |       \               /       \
 [ 1:0 | 2:0 ]   [ 3:0 | 4:0 ]   [ 5:0 ]   [ 6:0 ]   [ 7:0 ]

 // Leaf node goes last.
                                    [ 5:0 ]
                                /            \
                 [ 2:0 | 4:8 ]                  [ 6:0 ]
               /       |       \               /       \
 [ 1:0 | 2:0 ]   [ 3:0 | 4:8 ]   [ 5:0 ]   [ 6:0 ]   [ 7:0 ]
 

Note that inbetween these two updates tree is fully unlocked and available for modifications. So, if one tries to remove 5:0 during the replacement, following modifications would happen:

 // Inner node update from replacement goes first, as before.
                                    [ 5:0 ]
                                /            \
                 [ 2:0 | 4:8 ]                  [ 6:0 ]
               /       |       \               /       \
 [ 1:0 | 2:0 ]   [ 3:0 | 4:0 ]   [ 5:0 ]   [ 6:0 ]   [ 7:0 ]

 // Removal of 5:0 starts from the leaf.
                                    [ 5:0 ]
                                /            \
                 [ 2:0 | 4:8 ]                  [ 6:0 ]
               /       |       \               /       \
 [ 1:0 | 2:0 ]   [ 3:0 | 4:0 ]   []        [ 6:0 ]   [ 7:0 ]

 // Merge of empty branch is now required, 4:8 is removed from inner node.
                                [ 5:0 ]
                            /              \
                 [ 2:0 ]                        [ 6:0 ]
               /         \                     /       \
 [ 1:0 | 2:0 ]             [ 3:0 | 4:0 ]   [ 6:0 ]   [ 7:0 ]

 // Inner replace is happening in the root. To do that, closest left value is retrieved from the leaf, it's 4:0.
                                [ 4:0 ]
                            /              \
                 [ 2:0 ]                        [ 6:0 ]
               /         \                     /       \
 [ 1:0 | 2:0 ]             [ 3:0 | 4:0 ]   [ 6:0 ]   [ 7:0 ]

 // At this point removal is complete. Last replacement step will do the following.
                               [ 4:0 ]
                            /              \
                 [ 2:0 ]                        [ 6:0 ]
               /         \                     /       \
 [ 1:0 | 2:0 ]             [ 3:0 | 4:8 ]   [ 6:0 ]   [ 7:0 ]
 

It is clear that root has an invalid value 4:0, hence the tree should be considered corrupted. This is the exact situation that test is trying to check.

Several iterations are required for this, given that there's no guaranteed way to force a tree to perform page modifications in the desired order. Typically, less than 10 attempts have been required to get a corrupted tree. Value 50 is arbitrary and has been chosen to be big enough for test to fail in case of regression, but not too big so that test won't run for too long.

Throws:

Exception - If failed.