com.bigdata.resources
Class SplitUtility

java.lang.Object
  com.bigdata.resources.SplitUtility

public class SplitUtility
extends Object

Utility methods for ISimpleSplitHandlers and friends.

Version:

$Id: SplitUtility.java 4523 2011-05-18 18:14:45Z thompsonbry $

Author:

Bryan Thompson

Nested Class Summary

protected static class

SplitUtility.BuildIndexSegmentSplitTask Task used to build an IndexSegment from a restricted key-range of an index during a SplitIndexPartitionTask.

Constructor Summary

SplitUtility()

Method Summary

static SplitResult	buildSplits(com.bigdata.resources.ViewMetadata vmd, Split[] splits, Event parentEvent) Build N index segments based on those split points.
static Split[]	getSplits(IPartitionIdFactory partitionIdFactory, LocalPartitionMetadata oldpmd, IndexSegment seg, long nominalShardSize, ISimpleSplitHandler splitHandler) Choose a set of splits which may be reasonably expected to divide the IndexSegment into extents each of which is approximately 50% full.
static Split[]	tailSplit(ResourceManager resourceManager, BTree btree) Identifies the splits for an index with heavy write append behavior.
static void	validateSplits(IIndex src, Split[] splits) Validate splits, including: that the separator keys are strictly ascending, that the separator keys perfectly cover the source key range without overlap, that the rightSeparator for each split is the leftSeparator for the prior split, that the fromIndex offsets are strictly ascending, etc.
static void	validateSplits(LocalPartitionMetadata originalPartitionMetadata, Split[] splits, boolean checkFromToIndex) Validate splits, including: that the separator keys are strictly ascending, that the separator keys perfectly cover the source key range without overlap, that the rightSeparator for each split is the leftSeparator for the prior split, that the fromIndex offsets are strictly ascending, etc.

Methods inherited from class java.lang.Object

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

Constructor Detail

SplitUtility

public SplitUtility()

Method Detail

validateSplits

public static void validateSplits(IIndex src,
                                  Split[] splits)

Validate splits, including: that the separator keys are strictly ascending, that the separator keys perfectly cover the source key range without overlap, that the rightSeparator for each split is the leftSeparator for the prior split, that the fromIndex offsets are strictly ascending, etc.

Parameters:

src - The source index.

splits - The recommended split points.

Throws:

IllegalArgumentException - if either argument is null.

IllegalArgumentException - if the source index is not an index partition (if {@link IndexMetadata#getPartitionMetadata() returns null).

validateSplits

public static void validateSplits(LocalPartitionMetadata originalPartitionMetadata,
                                  Split[] splits,
                                  boolean checkFromToIndex)

Validate splits, including: that the separator keys are strictly ascending, that the separator keys perfectly cover the source key range without overlap, that the rightSeparator for each split is the leftSeparator for the prior split, that the fromIndex offsets are strictly ascending, etc.

Parameters:

originalPartitionMetadata - The description of the key range of the index partition.

splits - The recommended split points.

checkFromToIndex - If the Split.fromIndex, Split.toIndex and Split.ntuples fields should be validated.

Throws:

IllegalArgumentException - if any argument is null.

tailSplit

public static Split[] tailSplit(ResourceManager resourceManager,
                                BTree btree)

Identifies the splits for an index with heavy write append behavior.

The split point is chosen by locating the right-most non-leaf node. The key range which would enter that node is placed within the new right-sibling index partition (the tail). The rest of the key range is placed within the new left-sibling index partition (the head).

Parameters:

btree - The BTree.

Returns:

The splits (split[0] is the head split, split[1] is the tail split).

buildSplits

public static SplitResult buildSplits(com.bigdata.resources.ViewMetadata vmd,
                                      Split[] splits,
                                      Event parentEvent)
                               throws InterruptedException,
                                      ExecutionExceptions

Build N index segments based on those split points.

Note: This is done in parallel to minimize latency.

Note: The generated IndexSegments are on the retentionSet and MUST be removed from that set once it has been incorporated in a restart safe manner into an index partition view or once the task fails.

Throws:

InterruptedException

ExecutionExceptions

See Also:

StoreManager.retentionSetAdd(java.util.UUID)

TODO:

The operation could be serialized (or run with limited parallelism) in order to minimize the RAM burden for buffers during index segment creation. You can also limit the parallelism to some upper bound. During normal operations, the #of splits generated should be fairly small, e.g., N >= 2 and N ~ 2. This requires a thread pool (or delegate for a thread pool) that can impose a limit on the actual parallelism.

getSplits

public static Split[] getSplits(IPartitionIdFactory partitionIdFactory,
                                LocalPartitionMetadata oldpmd,
                                IndexSegment seg,
                                long nominalShardSize,
                                ISimpleSplitHandler splitHandler)

Choose a set of splits which may be reasonably expected to divide the IndexSegment into extents each of which is approximately 50% full. The first split MUST use the leftSeparator of the index view as its leftSeparator. The last split MUST use the rightSeparator of the index view as its rightSeparator. The #of splits SHOULD be chosen such that the resulting index partitions are approximately 50% full.

Parameters:

keyRange - The left and right separator keys for the view.

seg - The IndexSegment containing most of the data for the view.

nominalShardSize - The nominal size of an index partition (typically 200MB).

splitHandler - Applies an application constraint to the choice of the separator key (optional).

Returns:

A Split[] array contains everything that we need to define the new index partitions -or- null if a more detailed examination reveals that the index SHOULD NOT be split at this time. The returned array MUST containing at least two elements. If the IndexSegment CAN NOT be split, this MUST return null rather than array with a single element.

See Also:

src/architecture/SplitMath.xls