com.bigdata.btree

Class AbstractBTreeTestCase

java.lang.Object

junit.framework.Assert

junit.framework.TestCase

junit.framework.TestCase2

com.bigdata.btree.AbstractBTreeTestCase

All Implemented Interfaces:

junit.framework.Test

Direct Known Subclasses:

AbstractEmbeddedFederationTestCase, AbstractIndexSegmentTestCase, AbstractNodeOrLeafDataRecordTestCase, TestBTree, TestBTreeBranchingFactors, TestBTreeWithBloomFilter, TestChunkedIterators, TestCopyOnWrite, TestDeleteMarkers, TestDirtyIterators, TestDirtyListener, TestFindChild, TestFusedView, TestIncrementalWrite, TestIndexCounter, TestIndexPartitionFencePosts, TestIndexSegmentAddressManager, TestIndexSegmentPlan, TestIndexSegmentWithBloomFilter, TestInsertLookupRemoveKeysInRootLeaf, TestIsolatedFusedView, TestIterators, TestLinearListMethods, TestMixedModeOperations, TestNullValues, TestPutIfAbsent, TestRawRecords, TestRemoveAll, TestReopen, TestSplitJoinRootLeaf, TestSplitJoinThreeLevels, TestSplitRootLeaf, TestTouch, TestTransientBTree, TestTupleFilters, TestUtilMethods

public abstract class AbstractBTreeTestCase
extends TestCase2

Abstract test case for BTree tests.

Version:

$Id$

Author:

Bryan Thompson

Nested Class Summary

Nested classes/interfaces inherited from class junit.framework.TestCase2

TestCase2.MyProperties, TestCase2.RandomType

Field Summary

Fields

Modifier and Type	Field and Description
protected IKeyBuilder	keyBuilder
protected static org.apache.log4j.Logger	log Logger for the test suites in this package.
protected Random	r

Fields inherited from class junit.framework.TestCase2

_randomType

Constructor Summary

Constructors

Constructor and Description
AbstractBTreeTestCase()
AbstractBTreeTestCase(String name)

Method Summary

Methods

Modifier and Type	Method and Description
static void	assertChildKeys(long[] childAddr, Node node) Special purpose helper used to vet Node#childAddr.
static void	assertEntryCounts(int[] expected, INodeData node) Special purpose helper used to vet the per-child entry counts for an INodeData.
static void	assertKeys(byte[][] keys, AbstractNode<?> node) Validate the keys in the node.
void	assertKeys(int[] keys, AbstractNode<?> node) Test helper provides backwards compatibility for a large #of tests that were written with int keys.
static void	assertKeys(IRaba expected, IRaba actual) Test helper verifies the #of keys and their ordered values.
protected static void	assertSameAbstractNodeData(IAbstractNodeData n1, IAbstractNodeData n2) Verify all data accessible from INodeData.
static void	assertSameBTree(AbstractBTree expected, IIndex actual) A suite of tests designed to verify that one btree correctly represents the information present in a ground truth btree.
static void	assertSameEntryIterator(IIndex expected, IIndex actual) Verifies the data in the two indices using a batch-oriented key range scans (this can be used to verify a key-range partitioned scale-out index against a ground truth index) - only the keys and values of non-deleted index entries in the expected index are inspected.
static void	assertSameEntryIterator(ITupleIterator expectedItr, ITupleIterator actualItr) Verifies that the iterators visit tuples having the same data in the same order.
static void	assertSameIterator(byte[][] expected, ITupleIterator actual) Method verifies that the actual ITupleIterator produces the expected values in the expected order.
static void	assertSameIterator(String msg, byte[][] expected, ITupleIterator actual) Method verifies that the actual ITupleIterator produces the expected values in the expected order.
static void	assertSameLeaf(Leaf n1, Leaf n2) Compares leaves for the same data.
static void	assertSameLeafData(ILeafData n1, ILeafData n2) Verify all data accessible from ILeafData.
static void	assertSameNode(Node n1, Node n2) Compares two nodes (or leaves) for the same data.
static void	assertSameNodeData(INodeData n1, INodeData n2) Verify all data accessible from INodeData.
static void	assertSameNodeOrLeaf(AbstractNode<?> n1, AbstractNode<?> n2)
static void	assertSameRaba(IRaba expected, IRaba actual) Compares the data in two IRabas but not their capacity or things which depend on their capacity, such as IRaba.isFull() and whether or not they are IRaba.isReadOnly().
void	assertValues(Object[] values, Leaf leaf)
void	assertValues(String msg, Object[] values, Leaf leaf) Test helper verifies the #of values, their ordered values, and that all values beyond the last defined value are null.
protected static long	doEntryIteratorTest(ITupleIterator<?> expectedItr, ITupleIterator<?> actualItr) Compares the total ordering of two B+Trees as revealed by their range iterators
protected static BTree	doInsertKeySequenceTest(BTree btree, int[] keys, SimpleEntry[] entries, int[] order, int trace) Insert key value pairs into the tree in the specified order and verify the expected entry traversal afterwards.
void	doInsertLookupRemoveStressTest(int m, int nkeys, int ntrials) Stress test helper performs random inserts, removal and lookup operations and compares the behavior of the BTree against ground truth as tracked by a TreeMap.
static BTree	doInsertRandomKeySequenceTest(BTree btree, int[] keys, SimpleEntry[] entries, int trace) Insert key value pairs into the tree in a random order and verify the expected entry traversal afterwards.
BTree	doInsertRandomKeySequenceTest(BTree btree, int ninserts, int trace) Insert dense key-value pairs into the tree in a random order and verify the expected entry traversal afterwards.
static BTree	doInsertRandomSparseKeySequenceTest(BTree btree, int ninserts, int trace) Insert a sequence of monotonically increase keys with random spacing into a tree in a random order and verify the expected entry traversal afterwards.
static void	doKnownKeySequenceTest(BTree btree, int[] order, int trace) Present a known sequence.
static void	doRandomIndexOfTest(String label, AbstractBTree btree, byte[][] keys, byte[][] vals) Tests the performance of random lookups of keys and values by entry index.
protected void	doRandomKeyInsertTest(BTree btree, int[] keys, SimpleEntry[] entries, int[] order)
static void	doRandomLookupTest(String label, IIndex btree, byte[][] keys, byte[][] vals) Tests the performance of random IAutoboxBTree.lookup(Object)s on the btree.
void	doRemoveStructureStressTest(int m, int nkeys) Stress test for building up a tree and then removing all keys in a random order.
void	doSplitTest(int m, int trace) Stress test helper inserts random permutations of keys into btrees of order m for several different btrees, #of keys to be inserted, and permutations of keys.
void	doSplitWithDecreasingKeySequence(BTree btree, int m, int ninserts) Creates a sequence of keys in decreasing order and inserts them into the tree.
void	doSplitWithIncreasingKeySequence(BTree btree, int m, int ninserts) Test helper for #test_splitRootLeaf_increasingKeySequence().
BTree	doSplitWithRandomDenseKeySequence(BTree btree, int m, int ninserts) Creates a sequence of dense keys in random order and inserts them into the tree.
BTree	getBTree(int branchingFactor) Return a new btree backed by a simple transient store that will NOT evict leaves or nodes onto the store.
BTree	getBTree(int branchingFactor, ITupleSerializer tupleSer)
static void	getKeysAndValues(AbstractBTree btree, byte[][] keys, byte[][] vals) Extract all keys and values from the btree in key order.
static byte[][]	getRandomKeys(int maxKeys, int nkeys) Generate a set of N random distinct byte[] keys in sorted order using an unsigned byte[] comparison function.
static KV[]	getRandomKeyValues(int N) Generate random key-value data in key order.
protected byte[]	i2k(int v) Encodes an integer as a unsigned byte[] key.
static long	nextLong(Random r, long n) Utility method for random long integers within a range.
protected boolean	useRawRecords() Provide hook to allow specific test cases to determine if rawRecords should be used, failing any overide the value is random.

Methods inherited from class junit.framework.TestCase2

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEqualsWithinUlps, assertSameArray, assertSameArray, assertSameBigDecimal, assertSameBigDecimal, assertSameBigInteger, assertSameBigInteger, assertSameIterator, assertSameIterator, assertSameIteratorAnyOrder, assertSameIteratorAnyOrder, assertSameValue, assertSameValue, assertZeroUlps, assertZeroUlps, fail, getInnerCause, getNormalInt, getProjectBuildPath, getProperties, getRandomObject, getRandomObject, getRandomOrder, getRandomString, getTestInputStream, getTestResource, getTestResource, getUlps, getUlps, isDEBUG, isDEBUG, isINFO, isINFO, isInnerCause, logProperties

Methods inherited from class junit.framework.TestCase

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class java.lang.Object

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

Field Detail

r

protected Random r

keyBuilder

protected IKeyBuilder keyBuilder

log

protected static final org.apache.log4j.Logger log

Logger for the test suites in this package.

Constructor Detail

AbstractBTreeTestCase

public AbstractBTreeTestCase()

AbstractBTreeTestCase

public AbstractBTreeTestCase(String name)

Parameters:

name -

Method Detail

i2k

protected byte[] i2k(int v)

Encodes an integer as a unsigned byte[] key.

Parameters:

v - An integer.

Returns:

The sort key for that integer.

assertKeys

public static void assertKeys(IRaba expected,
              IRaba actual)

Test helper verifies the #of keys and their ordered values.

Parameters:

expected - A ground truth node.

actual - The actual node.

assertKeys

public void assertKeys(int[] keys,
              AbstractNode<?> node)

Test helper provides backwards compatibility for a large #of tests that were written with int keys. Each key is encoded by the KeyBuilder before comparison with the key at the corresponding index in the node.

Parameters:

keys - An array of the defined int keys.

node - The node whose keys will be tested.

assertValues

public void assertValues(String msg,
                Object[] values,
                Leaf leaf)

Test helper verifies the #of values, their ordered values, and that all values beyond the last defined value are null.

Parameters:

msg - A label, typically the node name.

values - An array containing the expected defined values. The #of values in this array should be exactly the #of defined values (that is, do not include trailing nulls or attempt to size the array to the branching factor of the tree).

assertValues

public void assertValues(Object[] values,
                Leaf leaf)

assertSameNodeOrLeaf

public static void assertSameNodeOrLeaf(AbstractNode<?> n1,
                        AbstractNode<?> n2)

assertSameNode

public static void assertSameNode(Node n1,
                  Node n2)

Compares two nodes (or leaves) for the same data.

Parameters:

n1 - The expected node state.

n2 - The actual node state.

assertSameLeaf

public static void assertSameLeaf(Leaf n1,
                  Leaf n2)

Compares leaves for the same data.

Parameters:

n1 - The expected leaf state.

n2 - The actual leaf state.

assertSameAbstractNodeData

protected static void assertSameAbstractNodeData(IAbstractNodeData n1,
                              IAbstractNodeData n2)

Verify all data accessible from INodeData.

assertSameNodeData

public static void assertSameNodeData(INodeData n1,
                      INodeData n2)

Verify all data accessible from INodeData.

assertSameLeafData

public static void assertSameLeafData(ILeafData n1,
                      ILeafData n2)

Verify all data accessible from ILeafData.

assertSameRaba

public static void assertSameRaba(IRaba expected,
                  IRaba actual)

Compares the data in two IRabas but not their capacity or things which depend on their capacity, such as IRaba.isFull() and whether or not they are IRaba.isReadOnly(). If the expected IRaba.isKeys(), then both must represent keys and the search API will also be tested.

Parameters:

expected -

actual -

assertChildKeys

public static void assertChildKeys(long[] childAddr,
                   Node node)

Special purpose helper used to vet Node#childAddr.

Parameters:

childAddr - An array all of whose values will be tested against the corresponding child identities in the node.

node - The node.

assertKeys

public static void assertKeys(byte[][] keys,
              AbstractNode<?> node)

Validate the keys in the node.

Parameters:

keys - An array all of whose entries will be tested against the corresponding keys in the node.

node - The node.

assertEntryCounts

public static void assertEntryCounts(int[] expected,
                     INodeData node)

Special purpose helper used to vet the per-child entry counts for an INodeData.

Parameters:

expected - An array all of whose values will be tested against the corresponding elements in the node as returned by INodeData#getChildEntryCounts(). The sum of the expected array is also tested against the value returned by IAbstractNodeData#getSpannedTupleCount().

node - The node.

getBTree

public BTree getBTree(int branchingFactor)

Return a new btree backed by a simple transient store that will NOT evict leaves or nodes onto the store. The leaf cache will be large and cache evictions will cause exceptions if they occur. This provides an indication if cache evictions are occurring so that the tests of basic tree operations in this test suite are known to be conducted in an environment without incremental writes of leaves onto the store. This avoids copy-on-write scenarios and let's us test with the knowledge that there should always be a hard reference to a child or parent.

Parameters:

branchingFactor - The branching factor.

getBTree

public BTree getBTree(int branchingFactor,
             ITupleSerializer tupleSer)

useRawRecords

protected boolean useRawRecords()

Provide hook to allow specific test cases to determine if rawRecords should be used, failing any overide the value is random.

Returns:

whether to use raw records

doSplitWithIncreasingKeySequence

public void doSplitWithIncreasingKeySequence(BTree btree,
                                    int m,
                                    int ninserts)

Test helper for #test_splitRootLeaf_increasingKeySequence(). creates a sequence of keys in increasing order and inserts them into the tree. Note that you do not know, in general, how many inserts it will take to split the root node since the split decisions are path dependent. They depend on the manner in which the leaves get filled, whether or not holes are created in the leaves, etc. Once all keys have been inserted into the tree the keys are removed in forward order (from the smallest to the largest). This stresses a specific pattern of joining leaves and nodes together with their right sibling.

Parameters:

m - The branching factor.

ninserts - The #of keys to insert.

doSplitWithDecreasingKeySequence

public void doSplitWithDecreasingKeySequence(BTree btree,
                                    int m,
                                    int ninserts)

Creates a sequence of keys in decreasing order and inserts them into the tree. Note that you do not know, in general, how many inserts it will take to split the root node since the split decisions are path dependent. They depend on the manner in which the leaves get filled, whether or not holes are created in the leaves, etc. Once all keys have been inserted into the tree the keys are removed in reverse order (from the largest to the smallest). This stresses a specific pattern of joining leaves and nodes together with their left sibling.

Parameters:

m - The branching factor.

ninserts - The #of keys to insert.

doSplitTest

public void doSplitTest(int m,
               int trace)

Stress test helper inserts random permutations of keys into btrees of order m for several different btrees, #of keys to be inserted, and permutations of keys. Several random permutations of dense and sparse keys are inserted. The #of keys to be inserted is also varied.

doInsertRandomKeySequenceTest

public BTree doInsertRandomKeySequenceTest(BTree btree,
                                  int ninserts,
                                  int trace)

Insert dense key-value pairs into the tree in a random order and verify the expected entry traversal afterwards.

Parameters:

m - The branching factor. The tree.

ninserts - The #of distinct key-value pairs to insert.

trace - The trace level (zero disables most tracing).

doInsertRandomSparseKeySequenceTest

public static BTree doInsertRandomSparseKeySequenceTest(BTree btree,
                                        int ninserts,
                                        int trace)

Insert a sequence of monotonically increase keys with random spacing into a tree in a random order and verify the expected entry traversal afterwards.

Parameters:

m - The branching factor for the source B+Tree.

ninserts - The #of distinct key-value pairs to insert.

trace - The trace level (zero disables most tracing).

Returns:

The populated BTree.

doInsertRandomKeySequenceTest

public static BTree doInsertRandomKeySequenceTest(BTree btree,
                                  int[] keys,
                                  SimpleEntry[] entries,
                                  int trace)

Insert key value pairs into the tree in a random order and verify the expected entry traversal afterwards.

Parameters:

m - The branching factor for the source B+Tree.

keys - The keys.

entries - The entries.

trace - The trace level (zero disables most tracing).

Returns:

The populated BTree.

doKnownKeySequenceTest

public static void doKnownKeySequenceTest(BTree btree,
                          int[] order,
                          int trace)

Present a known sequence.

Parameters:

m - The branching factor.

order - The key presentation sequence.

trace - The trace level.

doInsertKeySequenceTest

protected static BTree doInsertKeySequenceTest(BTree btree,
                            int[] keys,
                            SimpleEntry[] entries,
                            int[] order,
                            int trace)

Insert key value pairs into the tree in the specified order and verify the expected entry traversal afterwards. If the test fails, then the details necessary to recreate the test (m, ninserts, and the order[]) are printed out.

Parameters:

m - The branching factor for the source B+Tree.

keys - The keys.

entries - The entries.

order - The order in which the key-entry pairs will be inserted.

trace - The trace level (zero disables most tracing).

Returns:

The populated BTree.

doSplitWithRandomDenseKeySequence

public BTree doSplitWithRandomDenseKeySequence(BTree btree,
                                      int m,
                                      int ninserts)

Creates a sequence of dense keys in random order and inserts them into the tree. Note that the split decision points are path dependent and can not be predicated given random inserts.

Parameters:

m - The branching factor.

ninserts - The #of keys to insert.

doRandomKeyInsertTest

protected void doRandomKeyInsertTest(BTree btree,
                         int[] keys,
                         SimpleEntry[] entries,
                         int[] order)

doInsertLookupRemoveStressTest

public void doInsertLookupRemoveStressTest(int m,
                                  int nkeys,
                                  int ntrials)

Stress test helper performs random inserts, removal and lookup operations and compares the behavior of the BTree against ground truth as tracked by a TreeMap. Note: This test uses dense keys, but that is not a requirement.

Parameters:

m - The branching factor

nkeys - The #of distinct keys.

ntrials - The #of trials.

doRemoveStructureStressTest

public void doRemoveStructureStressTest(int m,
                               int nkeys)

Stress test for building up a tree and then removing all keys in a random order. The test populates a btree with enough keys to split the root leaf at least once then verifies that delete correctly removes each keys and any unused leaves and finally replaces the root node with a root leaf. All inserted keys are eventually deleted by this test and the end state is an empty btree of height zero(0) having a single root leaf.

assertSameBTree

public static void assertSameBTree(AbstractBTree expected,
                   IIndex actual)

A suite of tests designed to verify that one btree correctly represents the information present in a ground truth btree. The test verifies the #of entries, key type, the AbstractBTree.rangeIterator(), and also both lookup by key and lookup by entry index. The height, branching factor, #of nodes and #of leaves may differ (the test does not presume that the btrees were built with the same branching factor, but merely with the same data and key type).

Parameters:

expected - The ground truth btree.

actual - The btree that is being validated.

doEntryIteratorTest

protected static long doEntryIteratorTest(ITupleIterator<?> expectedItr,
                       ITupleIterator<?> actualItr)

Compares the total ordering of two B+Trees as revealed by their range iterators

Parameters:

expected - The ground truth iterator.

actual - The iterator to be tested.

Returns:

The #of tuples that were visited in actual.

See Also:

#doRandomLookupTest(String, AbstractBTree, byte[][], Object[]), #doRandomIndexOfTest(String, AbstractBTree, byte[][], Object[])

getKeysAndValues

public static void getKeysAndValues(AbstractBTree btree,
                    byte[][] keys,
                    byte[][] vals)

Extract all keys and values from the btree in key order. The caller must correctly dimension the arrays before calling this method.

Parameters:

btree - The btree.

keys - The keys in key order (out).

vals - The values in key order (out).

doRandomLookupTest

public static void doRandomLookupTest(String label,
                      IIndex btree,
                      byte[][] keys,
                      byte[][] vals)

Tests the performance of random IAutoboxBTree.lookup(Object)s on the btree. This vets the separator keys and the childAddr and/or childRef arrays since those are responsible for lookup.

Parameters:

label - A descriptive label for error messages.

btree - The btree.

keys - the keys in key order.

vals - the values in key order.

doRandomIndexOfTest

public static void doRandomIndexOfTest(String label,
                       AbstractBTree btree,
                       byte[][] keys,
                       byte[][] vals)

Tests the performance of random lookups of keys and values by entry index. This vets the separator keys and childRef/childAddr arrays, which are used to lookup the entry index for a key, and also vets the childEntryCount[] array, since that is responsible for lookup by entry index.

Parameters:

label - A descriptive label for error messages.

btree - The btree.

keys - the keys in key order.

vals - the values in key order.

assertSameIterator

public static void assertSameIterator(byte[][] expected,
                      ITupleIterator actual)

Method verifies that the actual ITupleIterator produces the expected values in the expected order. Errors are reported if too few or too many values are produced, etc.

assertSameIterator

public static void assertSameIterator(String msg,
                      byte[][] expected,
                      ITupleIterator actual)

Method verifies that the actual ITupleIterator produces the expected values in the expected order. Errors are reported if too few or too many values are produced, etc.

assertSameEntryIterator

public static void assertSameEntryIterator(IIndex expected,
                           IIndex actual)

Verifies the data in the two indices using a batch-oriented key range scans (this can be used to verify a key-range partitioned scale-out index against a ground truth index) - only the keys and values of non-deleted index entries in the expected index are inspected. Deleted index entries in the actual index are ignored.

Parameters:

expected -

actual -

assertSameEntryIterator

public static void assertSameEntryIterator(ITupleIterator expectedItr,
                           ITupleIterator actualItr)

Verifies that the iterators visit tuples having the same data in the same order.

Parameters:

expectedItr -

actualItr -

getRandomKeys

public static byte[][] getRandomKeys(int maxKeys,
                     int nkeys)

Generate a set of N random distinct byte[] keys in sorted order using an unsigned byte[] comparison function.

Parameters:

maxKeys - The capacity of the array.

nkeys - The #of keys to generate.

Returns:

A byte[][] with nkeys non-null byte[] entries and a capacity of maxKeys.

getRandomKeyValues

public static KV[] getRandomKeyValues(int N)

Generate random key-value data in key order.

Note: The auto-split feature of the scale-out indices depends on the assumption that the data are presented in key order.

Note: This method MAY return entries having duplicate keys.

Parameters:

N - The #of key-value pairs to generate.

Returns:

The random key-value data, sorted in ascending order by key.

See Also:

ClientIndexView#submit(int, byte[][], byte[][], com.bigdata.btree.IIndexProcedure.IIndexProcedureConstructor, com.bigdata.btree.IResultHandler)

nextLong

public static long nextLong(Random r,
            long n)

Utility method for random long integers within a range.

Parameters:

r - The random number.

n - The range.

Returns:

The random number in that range.

Throws:

IllegalArgumentException - if n is negative.

See Also:

Random.nextInt(int)