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

Class BPlusTreeTest

java.lang.Object

org.apache.ignite.internal.persistence.tree.BPlusTreeTest

Direct Known Subclasses:

BPlusTreeWithReuseListTest

public class BPlusTreeTest
extends Object

B+Tree test.

Constructor Summary

Constructors

Constructor	Description
BPlusTreeTest()

Method Summary

Modifier and Type	Method	Description
protected ReuseList	createReuseList()	Creates reuse list.
void	setUp()
void	tearDown()
void	testConcurrentGrowDegenerateTreeAndConcurrentRemove()
void	testCursorConcurrentMerge()
void	testEmptyCursors()
void	testEmptyLeafAfterConcurrentRemoves()	Test checks a rare case when, after a parallel removal from the b+tree (cleaning), an empty leaf could remain.
void	testFind()
void	testFindFirstAndLast()
void	testFindWithClosure()
void	testIsEmpty()
void	testIterate()
void	testIterateConcurrentPutRemove()
void	testIterateConcurrentPutRemove_1()
void	testIterateConcurrentPutRemove_2()
void	testIteratePutRemove_10()
void	testMassivePut1_false()
void	testMassivePut1_true()
void	testMassivePut2_false()
void	testMassivePut2_true()
void	testMassivePut3_false()
void	testMassivePut3_true()
void	testMassiveRemove1_false()
void	testMassiveRemove1_true()
void	testMassiveRemove2_false()
void	testMassiveRemove2_true()
void	testMassiveRemove3_false()
void	testMassiveRemove3_true()
void	testPutRemove_1_20_mm_0()
void	testPutRemove_1_20_mm_1()
void	testPutRemove_1_20_mp_0()
void	testPutRemove_1_20_mp_1()
void	testPutRemove_1_20_pm_0()
void	testPutRemove_1_20_pm_1()
void	testPutRemove_1_20_pp_0()
void	testPutRemove_1_20_pp_1()
void	testPutRemove_2_40_mm_0()
void	testPutRemove_2_40_mm_1()
void	testPutRemove_2_40_mp_0()
void	testPutRemove_2_40_mp_1()
void	testPutRemove_2_40_pm_0()
void	testPutRemove_2_40_pm_1()
void	testPutRemove_2_40_pp_0()
void	testPutRemove_2_40_pp_1()
void	testPutRemove_3_60_mm_0()
void	testPutRemove_3_60_mm_1()
void	testPutRemove_3_60_mp_0()
void	testPutRemove_3_60_mp_1()
void	testPutRemove_3_60_pm_0()
void	testPutRemove_3_60_pm_1()
void	testPutRemove_3_60_pp_0()
void	testPutRemove_3_60_pp_1()
void	testPutRmvFindSizeMultithreaded()	The test verifies that BPlusTree.put(T), BPlusTree.remove(L), BPlusTree.find(L, L), and BPlusTree.size() run concurrently, perform correctly and report correct values.
void	testPutRmvSizeSinglePageContention()	Verifies that in case for threads concurrently calling put and remove on a tree with 1-3 pages, the size() method performs correctly.
void	testPutSizeLivelock()	The test forces BPlusTree.size() method to run into a livelock: during single run the method is picking up new pages which are concurrently added to the tree until the new pages are not added anymore.
void	testRandomInvoke_1_30_0()
void	testRandomInvoke_1_30_1()
void	testRandomPutRemove_1_30_0()
void	testRandomPutRemove_1_30_1()
void	testRetries()
void	testSizeForPutRmvSequential()	Verifies that BPlusTree.size() and BPlusTree.size() methods behave correctly on single-threaded addition and removal of elements in random order.
void	testSizeForRandomPutRmvMultithreaded_3_256()
void	testSizeForRandomPutRmvMultithreaded_5_4()	Verifies that BPlusTree.size() method behaves correctly when run concurrently with BPlusTree.put(T), BPlusTree.remove(L) methods.
void	testSizeForRandomPutRmvMultithreadedAsync_16()	Verifies that concurrent running of BPlusTree.put(T) + BPlusTree.remove(L) sequence and BPlusTree.size() methods results in correct calculation of tree size.
void	testSizeForRandomPutRmvMultithreadedAsync_3()	Verifies that concurrent running of BPlusTree.put(T) + BPlusTree.remove(L) sequence and BPlusTree.size() methods results in correct calculation of tree size.
void	testTestRandomPutRemoveMultithreaded_1_30_0()
void	testTestRandomPutRemoveMultithreaded_1_30_1()
void	testTestRandomPutRemoveMultithreaded_2_50_0()
void	testTestRandomPutRemoveMultithreaded_2_50_1()
void	testTestRandomPutRemoveMultithreaded_3_70_0()
void	testTestRandomPutRemoveMultithreaded_3_70_1()

Methods inherited from class java.lang.Object

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

Constructor Details

BPlusTreeTest

public BPlusTreeTest()

Method Details

setUp

public void setUp()

tearDown

public void tearDown()
              throws IgniteCheckedException

Throws:

IgniteCheckedException

testFind

public void testFind()
              throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testRetries

public void testRetries()
                 throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testIsEmpty

public void testIsEmpty()
                 throws Exception

Throws:

Exception - if failed.

testFindWithClosure

public void testFindWithClosure()
                         throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_mm_1

public void testPutRemove_1_20_mm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_mm_0

public void testPutRemove_1_20_mm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_pm_1

public void testPutRemove_1_20_pm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_pm_0

public void testPutRemove_1_20_pm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_pp_1

public void testPutRemove_1_20_pp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_pp_0

public void testPutRemove_1_20_pp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_mp_1

public void testPutRemove_1_20_mp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_1_20_mp_0

public void testPutRemove_1_20_mp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_mm_1

public void testPutRemove_2_40_mm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_mm_0

public void testPutRemove_2_40_mm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_pm_1

public void testPutRemove_2_40_pm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_pm_0

public void testPutRemove_2_40_pm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_pp_1

public void testPutRemove_2_40_pp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_pp_0

public void testPutRemove_2_40_pp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_mp_1

public void testPutRemove_2_40_mp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_2_40_mp_0

public void testPutRemove_2_40_mp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_mm_1

public void testPutRemove_3_60_mm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_mm_0

public void testPutRemove_3_60_mm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_pm_1

public void testPutRemove_3_60_pm_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_pm_0

public void testPutRemove_3_60_pm_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_pp_1

public void testPutRemove_3_60_pp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_pp_0

public void testPutRemove_3_60_pp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_mp_1

public void testPutRemove_3_60_mp_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testPutRemove_3_60_mp_0

public void testPutRemove_3_60_mp_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testRandomInvoke_1_30_1

public void testRandomInvoke_1_30_1()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testRandomInvoke_1_30_0

public void testRandomInvoke_1_30_0()
                             throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testRandomPutRemove_1_30_0

public void testRandomPutRemove_1_30_0()
                                throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testRandomPutRemove_1_30_1

public void testRandomPutRemove_1_30_1()
                                throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testMassiveRemove3_false

public void testMassiveRemove3_false()
                              throws Exception

Throws:

Exception - If failed.

testMassiveRemove3_true

public void testMassiveRemove3_true()
                             throws Exception

Throws:

Exception - If failed.

testMassiveRemove2_false

public void testMassiveRemove2_false()
                              throws Exception

Throws:

Exception - If failed.

testMassiveRemove2_true

public void testMassiveRemove2_true()
                             throws Exception

Throws:

Exception - If failed.

testMassiveRemove1_false

public void testMassiveRemove1_false()
                              throws Exception

Throws:

Exception - If failed.

testMassiveRemove1_true

public void testMassiveRemove1_true()
                             throws Exception

Throws:

Exception - If failed.

testMassivePut1_true

public void testMassivePut1_true()
                          throws Exception

Throws:

Exception - If failed.

testMassivePut1_false

public void testMassivePut1_false()
                           throws Exception

Throws:

Exception - If failed.

testMassivePut2_true

public void testMassivePut2_true()
                          throws Exception

Throws:

Exception - If failed.

testMassivePut2_false

public void testMassivePut2_false()
                           throws Exception

Throws:

Exception

testMassivePut3_true

public void testMassivePut3_true()
                          throws Exception

Throws:

Exception - If failed.

testMassivePut3_false

public void testMassivePut3_false()
                           throws Exception

Throws:

Exception

testEmptyCursors

public void testEmptyCursors()
                      throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testCursorConcurrentMerge

public void testCursorConcurrentMerge()
                               throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testSizeForPutRmvSequential

public void testSizeForPutRmvSequential()
                                 throws IgniteCheckedException

Verifies that BPlusTree.size() and BPlusTree.size() methods behave correctly on single-threaded addition and removal of elements in random order.

Throws:

IgniteCheckedException - If failed.

testSizeForRandomPutRmvMultithreaded_5_4

public void testSizeForRandomPutRmvMultithreaded_5_4()
                                              throws Exception

Verifies that BPlusTree.size() method behaves correctly when run concurrently with BPlusTree.put(T), BPlusTree.remove(L) methods. Please see details in doTestSizeForRandomPutRmvMultithreaded(int, int, int).

Throws:

Exception - If failed.

testSizeForRandomPutRmvMultithreaded_3_256

public void testSizeForRandomPutRmvMultithreaded_3_256()
                                                throws Exception

Throws:

Exception

testSizeForRandomPutRmvMultithreadedAsync_16

public void testSizeForRandomPutRmvMultithreadedAsync_16()
                                                  throws Exception

Verifies that concurrent running of BPlusTree.put(T) + BPlusTree.remove(L) sequence and BPlusTree.size() methods results in correct calculation of tree size.

Throws:

Exception

See Also:

• doTestSizeForRandomPutRmvMultithreadedAsync() for details.

testSizeForRandomPutRmvMultithreadedAsync_3

public void testSizeForRandomPutRmvMultithreadedAsync_3()
                                                 throws Exception

Verifies that concurrent running of BPlusTree.put(T) + BPlusTree.remove(L) sequence and BPlusTree.size() methods results in correct calculation of tree size.

Throws:

Exception

See Also:

• doTestSizeForRandomPutRmvMultithreadedAsync() for details.

testPutSizeLivelock

public void testPutSizeLivelock()
                         throws Exception

The test forces BPlusTree.size() method to run into a livelock: during single run the method is picking up new pages which are concurrently added to the tree until the new pages are not added anymore. Test verifies that despite livelock condition a size from a valid range is returned. NB: This test has to be changed with the integration of IGNITE-3478.

Throws:

Exception - if test failed

testPutRmvSizeSinglePageContention

public void testPutRmvSizeSinglePageContention()
                                        throws Exception

Verifies that in case for threads concurrently calling put and remove on a tree with 1-3 pages, the size() method performs correctly.

Throws:

Exception - If failed.

testPutRmvFindSizeMultithreaded

public void testPutRmvFindSizeMultithreaded()
                                     throws Exception

The test verifies that BPlusTree.put(T), BPlusTree.remove(L), BPlusTree.find(L, L), and BPlusTree.size() run concurrently, perform correctly and report correct values. A sliding window of numbers is maintainted in the tests. NB: This test has to be changed with the integration of IGNITE-3478.

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_1_30_0

public void testTestRandomPutRemoveMultithreaded_1_30_0()
                                                 throws Exception

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_1_30_1

public void testTestRandomPutRemoveMultithreaded_1_30_1()
                                                 throws Exception

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_2_50_0

public void testTestRandomPutRemoveMultithreaded_2_50_0()
                                                 throws Exception

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_2_50_1

public void testTestRandomPutRemoveMultithreaded_2_50_1()
                                                 throws Exception

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_3_70_0

public void testTestRandomPutRemoveMultithreaded_3_70_0()
                                                 throws Exception

Throws:

Exception - If failed.

testTestRandomPutRemoveMultithreaded_3_70_1

public void testTestRandomPutRemoveMultithreaded_3_70_1()
                                                 throws Exception

Throws:

Exception - If failed.

testFindFirstAndLast

public void testFindFirstAndLast()
                          throws IgniteCheckedException

Throws:

IgniteCheckedException - If failed.

testIterate

public void testIterate()
                 throws Exception

Throws:

Exception - If failed.

testIterateConcurrentPutRemove

public void testIterateConcurrentPutRemove()
                                    throws Exception

Throws:

Exception - If failed.

testIterateConcurrentPutRemove_1

public void testIterateConcurrentPutRemove_1()
                                      throws Exception

Throws:

Exception - If failed.

testIterateConcurrentPutRemove_2

public void testIterateConcurrentPutRemove_2()
                                      throws Exception

Throws:

Exception - If failed.

testIteratePutRemove_10

public void testIteratePutRemove_10()
                             throws Exception

Throws:

Exception - If failed.

testConcurrentGrowDegenerateTreeAndConcurrentRemove

public void testConcurrentGrowDegenerateTreeAndConcurrentRemove()
                                                         throws Exception

Throws:

Exception - If failed.

testEmptyLeafAfterConcurrentRemoves

public void testEmptyLeafAfterConcurrentRemoves()
                                         throws Exception

Test checks a rare case when, after a parallel removal from the b+tree (cleaning), an empty leaf could remain. Schematically, this can happen like this: B+tree before clearing: [ 2 ] / \ [ 1 ] [ 3 | 4 ] / \ / | \ [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] Parallel deletions of keys: 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 before cutting root and inner node: [ ] | [ ] ^^^ An empty leaf remains so that this does not happen when "1" is removed, an empty root and an inner node remain, which we will cut off (BPlusTree.Remove#cutRoot). Remove 1 after cutting root and inner node: [ ]

Throws:

Exception - If failed.

createReuseList

protected ReuseList createReuseList()

Creates reuse list.

Returns:

the created list or null.