com.bigdata.btree

Class AbstractBTree

java.lang.Object

com.bigdata.btree.AbstractBTree

All Implemented Interfaces:

IAutoboxBTree, IBTreeStatistics, ICheckpointProtocol, IIndex, IIndexLocalCounter, ILinearList, ILocalBTreeView, IRangeQuery, IReadWriteLockManager, ISimpleBTree, ISimpleIndexAccess, ISimpleTreeIndexAccess, ICounterSetAccess, ICommitter

Direct Known Subclasses:

BTree, IndexSegment

public abstract class AbstractBTree
extends Object
implements IIndex, IAutoboxBTree, ILinearList, IBTreeStatistics, ILocalBTreeView, ISimpleTreeIndexAccess, ICheckpointProtocol

Base class for mutable and immutable B+-Tree implementations.

The B+-Tree implementation supports variable length unsigned byte[] keys and provides a IKeyBuilder utilities designed to make it possible to generate keys from any combination of primitive data types and Unicode strings. The total ordering imposed by the index is that of a bit-wise comparison of the variable length unsigned byte[] keys. Encoding Unicode keys is support by an integration with ICU4J and applications may choose the locale, strength, and other properties that govern the sort order of sort keys generated from Unicode strings. Sort keys produces by different collator objects are NOT compatible and applications that use Unicode data in their keys MUST make sure that they use a collator that imposes the same sort order each time they provision a KeyBuilder.

The use of variable length unsigned byte[] keys makes it possible for the B+-Tree to perform very fast comparison of a search key with keys in the nodes and leaves of the tree. To support fast search, the leading prefix is factored out each time a node or leaf is made immutable, e.g., directly proceeding serialization. Further, the separator keys are chosen to be the shortest separator key in order to further shorten the keys in the nodes of the tree.

The B+Tree can optionally maintain version metadata (a version timestamp and deletion marker). Version metadata MUST be enabled (a) if the index will be used with transactional isolation; or (b) if the index is part of a scale-out index. In both cases the version timestamps and deletion markers play a critical role when reading from a fused view of an ordered set of indices describing an index or an index partition. Note that the existence of deletion markers means that rangeCount(byte[], byte[]) and getEntryCount() are upper bounds as deleted entries will be reported until they are purged from the index by a compacting merge of the view.

Author:

Bryan Thompson

See Also:

KeyBuilder

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	AbstractBTree.IBTreeCounters Interface declaring namespaces for performance counters collected for a B+Tree.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	branchingFactor The branching factor for the btree.
protected boolean	debug Flag turns on the use of AbstractNode.assertInvariants() and is automatically enabled when the logger is set to Level.DEBUG.
protected static boolean	DEBUG True iff the log level is DEBUG or less.
static org.apache.log4j.Logger	dumpLog Log for dump(PrintStream) and friends.
protected Throwable	error This field is set if an error is encountered that renders an unisolated index object unusable.
protected static String	ERROR_CLOSED The index is already closed.
protected static String	ERROR_ERROR_STATE An unisolated index view is in an error state.
protected static String	ERROR_LESS_THAN_ZERO A parameter was less than zero.
protected static String	ERROR_READ_ONLY The index is read-only but a mutation operation was requested.
protected static String	ERROR_TOO_LARGE A parameter was too large.
protected static String	ERROR_TRANSIENT The index is transient (not backed by persistent storage) but an operation that requires persistence was requested.
protected static boolean	INFO True iff the log level is INFO or less.
protected static org.apache.log4j.Logger	log Log for btree opeations.
protected IndexMetadata	metadata The metadata record for the index.
protected int	ndistinctOnWriteRetentionQueue The #of distinct nodes and leaves on the writeRetentionQueue.
protected NodeSerializer	nodeSer Used to serialize and de-serialize the nodes and leaves of the tree.
protected boolean	readOnly When true the AbstractBTree does not permit mutation.
protected AbstractNode<?>	root The root of the btree.
protected IRawStore	store The persistence store -or- null iff the B+Tree is transient.
protected ConcurrentMap<Long,Object>	storeCache Deprecated.
protected IHardReferenceQueue<PO>	writeRetentionQueue Nodes (that is nodes or leaves) are added to a hard reference queue when they are created or read from the store.

Fields inherited from interface com.bigdata.btree.IRangeQuery

ALL, CURSOR, DEFAULT, DELETED, FIXED_LENGTH_SUCCESSOR, KEYS, NONE, PARALLEL, READONLY, REMOVEALL, REVERSE, VALS

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	AbstractBTree(IRawStore store, INodeFactory nodeFactory, boolean readOnly, IndexMetadata metadata, IRecordCompressorFactory<?> recordCompressorFactory)

Method Summary

Methods

Modifier and Type	Method and Description
protected abstract void	_reopen() This method is responsible for setting up the root leaf (either new or read from the store), the bloom filter, etc.
protected void	assertNotReadOnly()
protected void	assertNotTransient()
void	close() The contract for ICheckpointProtocol.close() is to reduce the resource burden of the index while not rendering the index inoperative.
boolean	contains(byte[] key) Core method to decide whether the index has a (non-deleted) entry under a key.
boolean	contains(Object key) Return true iff there is an entry for the key.
static long	decodeRecordAddr(byte[] buf) Decodes a signed long value as encoded by #appendSigned(long).
boolean	dump(org.apache.log4j.Level level, PrintStream out)
boolean	dump(PrintStream out) Recursive dump of the tree.
BaseIndexStats	dumpPages(boolean recursive, boolean visitLeaves) Reports statistics for the index.
static byte[]	encodeRecordAddr(ByteArrayBuffer recordAddrBuf, long addr) Encode a raw record address into a byte[] suitable for storing in the value associated with a tuple and decoding using decodeRecordAddr(byte[])
abstract BloomFilter	getBloomFilter() Return the optional IBloomFilter, transparently reopen()ing the index if necessary.
int	getBranchingFactor() The branching factor for the btree.
BTreeCounters	getBtreeCounters() Counters tracking various aspects of the btree.
Tuple	getContainsTuple() Return a Tuple that may be used to test for the existence of tuples having a given key within the AbstractBTree.
CounterSet	getCounters() Return performance counters.
abstract long	getEntryCount() The #of entries (aka tuples) in the AbstractBTree.
IndexMetadata	getIndexMetadata() The metadata for the index.
abstract long	getLastCommitTime() The timestamp associated with the last IAtomicStore.commit() in which writes buffered by this index were made restart-safe on the backing store.
int	getLevel(AbstractNode t) Return the level of t below the root node or leaf.
int	getLevel(AbstractNode t, AbstractNode node) Return the level of t below the given node or leaf.
Tuple	getLookupTuple() Return a Tuple that may be used to copy the value associated with a key out of the AbstractBTree.
NodeSerializer	getNodeSerializer() The object responsible for (de-)serializing the nodes and leaves of the IIndex.
int	getReadLockCount() Return the #of read-locks held by the current thread for a mutable index view.
IResourceMetadata[]	getResourceMetadata() The description of the resources comprising the index view.
abstract long	getRevisionTimestamp() The timestamp associated with unisolated writes on this index.
AbstractNode	getRightMostNode(boolean nodesOnly) Utility method returns the right-most node in the B+Tree.
protected AbstractNode<?>	getRoot() The root of the btree.
protected AbstractNode<?>	getRootOrFinger(byte[] key) Returns the node or leaf to be used for search.
IBTreeStatistics	getStatistics() Return a statistics snapshot of the B+Tree.
IBTreeUtilizationReport	getUtilization() Computes and returns the utilization of the tree.
Tuple	getWriteTuple() Private instance used for mutation operations (insert, remove) which are single threaded.
long	indexOf(byte[] key) Lookup the index position of the key.
byte[]	insert(byte[] key, byte[] value) Insert or update a value under the key.
Tuple	insert(byte[] key, byte[] value, boolean delete, boolean putIfAbsent, long timestamp, Tuple tuple) Core method for inserting or updating a value under a key.
Object	insert(Object key, Object value) Insert with auto-magic handling of keys and value objects.
boolean	isBalanced() Return true iff the tree is balanced.
boolean	isOpen() An "open" index has may have some buffered data.
boolean	isReadOnly() Return true iff this B+Tree is read-only.
boolean	isTransient() Return true iff this is a transient data structure (no backing store).
byte[]	keyAt(long index) Return the key for the identified entry.
byte[]	lookup(byte[] key) Lookup a value for a key.
Tuple	lookup(byte[] key, Tuple tuple) Core method for retrieving a value under a key.
Object	lookup(Object key) Lookup a value for a key.
abstract ILeafCursor	newLeafCursor(byte[] key) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
abstract ILeafCursor	newLeafCursor(SeekEnum where) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
byte[]	putIfAbsent(byte[] key, byte[] value) Insert or update a value under the key iff there is no entry for that key in the index.
protected boolean	rangeCheck(byte[] key, boolean allowUpperBound) Deprecated. This method has been disabled. It always returns true. The method is disabled because it forces the caller to ensure that the query lies within the specified range. While that is all well and good, this places an undue burden on FusedView which must substitute the actual key range of a shard view for the caller's key range. This makes the test effectively into a self-check of whether FusedView has correctly done this substitution rather than a check of whether a request was mapped onto the correct shard, which was the original purpose of this test. The logic for performing such range checks was moved into RangeCheckUtil.
long	rangeCopy(IIndex src, byte[] fromKey, byte[] toKey, boolean overflow) Copy all data, including deleted index entry markers and timestamps iff supported by the source and target.
long	rangeCount() Return the #of tuples in the index.
long	rangeCount(byte[] fromKey, byte[] toKey) Return the #of tuples in a half-open key range.
long	rangeCount(Object fromKey, Object toKey) Variant implicitly converts the optional application keys into unsigned byte[]s.
long	rangeCountExact(byte[] fromKey, byte[] toKey) Return the exact #of tuples in a half-open key range.
long	rangeCountExactWithDeleted(byte[] fromKey, byte[] toKey) Note: rangeCount(byte[], byte[]) already reports deleted tuples for an AbstractBTree so this method is just delegated to that one.
ITupleIterator	rangeIterator() Visits all tuples in key order.
ITupleIterator	rangeIterator(byte[] fromKey, byte[] toKey) Return an iterator that visits the entries in a half-open key range.
ITupleIterator	rangeIterator(byte[] fromKey, byte[] toKey, int capacityIsIgnored, int flags, IFilter filter) Designated variant (the one that gets overridden) for an iterator that visits the entries in a half-open key range.
ITupleIterator	rangeIterator(Object fromKey, Object toKey) Variant implicitly converts the optional application keys into unsigned byte[]s.
ITupleIterator	rangeIterator(Object fromKey, Object toKey, int capacity, int flags, IFilter filter) Variant implicitly converts the optional application keys into unsigned byte[]s.
Lock	readLock() Return a Lock that may be used to obtain a shared read lock which is used (in the absence of other concurrency control mechanisms) to permit concurrent readers on an unisolated index while serializing access to that index when a writer must run.
protected AbstractNode<?>	readNodeOrLeaf(long addr) Read a node or leaf from the store.
protected int	recycle(long addr) Recycle (aka delete) the allocation.
byte[]	remove(byte[] key) Remove the tuple under that key (will write a delete marker if delete markers are enabled).
Tuple	remove(byte[] key, Tuple tuple) Core method for deleting a value under a key.
Object	remove(Object key) Remove the key and its associated value.
abstract void	removeAll() Remove all entries in the B+Tree.
void	reopen() (Re-) open the index.
ICloseableIterator<?>	scan() Visit all entries in the index in the natural order of the index (dereferencing visited tuples to the application objects stored within those tuples).
void	setBTreeCounters(BTreeCounters btreeCounters) Replace the BTreeCounters.
void	submit(byte[] fromKey, byte[] toKey, IKeyRangeIndexProcedure proc, IResultHandler handler) The procedure will be transparently applied against each index partition spanned by the given key range.
<T> T	submit(byte[] key, ISimpleIndexProcedure<T> proc) Submits an index procedure that operations on a single key to the appropriate index partition returning the result of that procedure.
void	submit(int fromIndex, int toIndex, byte[][] keys, byte[][] vals, AbstractKeyArrayIndexProcedureConstructor ctor, IResultHandler aggregator) Runs a procedure against an index.
String	toString() Fast summary information about the B+Tree.
protected void	touch(AbstractNode<?> node) This method is responsible for putting the node or leaf onto the ring buffer which controls (a) how long we retain a hard reference to the node or leaf; and (b) for writes, when the node or leaf is evicted with a zero reference count and made persistent (along with all dirty children).
byte[]	valueAt(long index) Return the value for the identified entry.
Tuple	valueAt(long index, Tuple tuple)
Lock	writeLock() Return a Lock that may be used to obtain an exclusive write lock which is used (in the absence of other concurrency control mechanisms) to serialize all processes accessing an unisolated index when a writer must run.
protected long	writeNodeOrLeaf(AbstractNode<?> node) Codes the node and writes the coded record on the store (non-recursive).
protected void	writeNodeRecursive(AbstractNode<?> node) Write a dirty node and its children using a post-order traversal that first writes any dirty leaves and then (recursively) their parent nodes.
protected void	writeNodeRecursiveCallersThread(AbstractNode<?> node) This is the historical implementation and runs entirely in the caller's thread.
protected void	writeNodeRecursiveConcurrent(AbstractNode<?> node) Writes the dirty nodes and leaves in level sets (one level at a time) with up to one thread per dirty node/leave in a given level.

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.bigdata.btree.IBTreeStatistics

getHeight, getLeafCount, getNodeCount

Methods inherited from interface com.bigdata.btree.ILocalBTreeView

getMutableBTree, getSourceCount, getSources

Methods inherited from interface com.bigdata.btree.IIndexLocalCounter

getCounter

Methods inherited from interface com.bigdata.btree.ISimpleTreeIndexAccess

getHeight, getLeafCount, getNodeCount

Methods inherited from interface com.bigdata.btree.ICheckpointProtocol

getCheckpoint, getDirtyListener, getMetadataAddr, getRecordVersion, getRootAddr, setDirtyListener, setLastCommitTime, writeCheckpoint, writeCheckpoint2

Methods inherited from interface com.bigdata.journal.ICommitter

handleCommit, invalidate

Methods inherited from interface com.bigdata.btree.ISimpleIndexAccess

getStore

Field Detail

ERROR_CLOSED

protected static final String ERROR_CLOSED

The index is already closed.

See Also:

Constant Field Values

ERROR_LESS_THAN_ZERO

protected static final String ERROR_LESS_THAN_ZERO

A parameter was less than zero.

See Also:

Constant Field Values

ERROR_TOO_LARGE

protected static final String ERROR_TOO_LARGE

A parameter was too large.

See Also:

Constant Field Values

ERROR_READ_ONLY

protected static final String ERROR_READ_ONLY

The index is read-only but a mutation operation was requested.

See Also:

Constant Field Values

ERROR_TRANSIENT

protected static final String ERROR_TRANSIENT

The index is transient (not backed by persistent storage) but an operation that requires persistence was requested.

See Also:

Constant Field Values

ERROR_ERROR_STATE

protected static final String ERROR_ERROR_STATE

An unisolated index view is in an error state. It must be discarded and reloaded from the current checkpoint record.

See Also:

Invalidate BTree objects if error occurs during eviction , Constant Field Values

log

protected static final org.apache.log4j.Logger log

Log for btree opeations.

INFO

protected static final boolean INFO

True iff the log level is INFO or less.

DEBUG

protected static final boolean DEBUG

True iff the log level is DEBUG or less.

dumpLog

public static final org.apache.log4j.Logger dumpLog

Log for dump(PrintStream) and friends.

debug

protected final boolean debug

Flag turns on the use of AbstractNode.assertInvariants() and is automatically enabled when the logger is set to Level.DEBUG.

store

protected final IRawStore store

The persistence store -or- null iff the B+Tree is transient.

readOnly

protected final boolean readOnly

When true the AbstractBTree does not permit mutation.

storeCache

@Deprecated
protected final ConcurrentMap<Long,Object> storeCache

Deprecated.

Optional cache for INodeData and ILeafData instances and always null if the B+Tree is transient.

branchingFactor

protected final int branchingFactor

The branching factor for the btree.

root

protected volatile AbstractNode<?> root

The root of the btree. This is initially a leaf until the leaf is split, at which point it is replaced by a node. The root is also replaced each time copy-on-write triggers a cascade of updates.

This hard reference is cleared to null if an index is closed. getRoot() automatically uses reopen() to reload the root so that closed indices may be transparently made ready for further use (indices are closed to reduce their resource burden, not to make their references invalid). The AbstractNode and derived classes assume that the root is non-null. This assumption is valid if close() is invoked by the application in a manner consistent with the single-threaded contract for the AbstractBTree.

Note: This field MUST be marked as [volatile] in order to guarantee correct semantics for double-checked locking in reopen() and reopen().

See Also:

http://en.wikipedia.org/wiki/Double-checked_locking

error

protected volatile Throwable error

This field is set if an error is encountered that renders an unisolated index object unusable. For example, this can occur if an error was detected during incremental eviction of dirty nodes for a mutable index view since that means that there are partly serialized (and possibly inconsistenly serialized) evicted pages. Once this becomes non- null the index MUST be reloaded from the most recent checkpoint before it can be used (that is, you need to obtain a new view of the unisolated index since this field is sticky once set).

See Also:

Invalidate BTree objects if error occurs during eviction

nodeSer

protected final NodeSerializer nodeSer

Used to serialize and de-serialize the nodes and leaves of the tree.

writeRetentionQueue

protected final IHardReferenceQueue<PO> writeRetentionQueue

Nodes (that is nodes or leaves) are added to a hard reference queue when they are created or read from the store. On eviction from the queue a dirty node is serialized by a listener against the IRawStore. The nodes and leaves refer to their parent with a WeakReferences. Likewise, nodes refer to their children with a WeakReference. The hard reference queue in combination with touch(AbstractNode) and with hard references held on the stack ensures that the parent and/or children remain reachable during operations. Once the node is no longer strongly reachable weak references to that node may be cleared by the VM - in this manner the node will become unreachable by navigation from its ancestors in the btree. The special role of the hard reference queue is to further ensure that dirty nodes remain dirty by defering persistence until the reference count for the node is zero during an eviction from the queue.

Note that nodes are evicted as new nodes are added to the hard reference queue. This occurs in two situations: (1) when a new node is created during a split of an existing node; and (2) when a node is read in from the store. Inserts on this hard reference queue always drive evictions. Incremental writes basically make it impossible for the commit set to get "too large" - the maximum #of nodes to be written is bounded by the size of the hard reference queue. This helps to ensure fast commit operations on the store.

The minimum capacity for the hard reference queue is two (2) so that a split may occur without forcing eviction of either node participating in the split.

Note: The code in Node.postOrderNodeIterator(boolean, boolean) and DirtyChildIterator MUST NOT touch the hard reference queue since those iterators are used when persisting a node using a post-order traversal. If a hard reference queue eviction drives the serialization of a node and we touch the hard reference queue during the post-order traversal then we break down the semantics of HardReferenceQueue.add(Object) as the eviction does not necessarily cause the queue to reduce in length. Another way to handle this is to have HardReferenceQueue.add(Object) begin to evict objects before is is actually at capacity, but that is also a bit fragile.

Note: The writeRetentionQueue uses a HardReferenceQueue. This is based on a RingBuffer and is very fast. It does not use a HashMap because we can resolve the WeakReference to the child Node or Leaf using top-down navigation as long as the Node or Leaf remains strongly reachable (that is, as long as it is on the writeRetentionQueue or otherwise strongly held). This means that lookup in a map is not required for top-down navigation.

ndistinctOnWriteRetentionQueue

protected int ndistinctOnWriteRetentionQueue

The #of distinct nodes and leaves on the writeRetentionQueue.

metadata

protected IndexMetadata metadata

The metadata record for the index. This data rarely changes during the life of the BTree object, but it CAN be changed.

Constructor Detail

AbstractBTree

protected AbstractBTree(IRawStore store,
             INodeFactory nodeFactory,
             boolean readOnly,
             IndexMetadata metadata,
             IRecordCompressorFactory<?> recordCompressorFactory)

Parameters:

store - The persistence store.

nodeFactory - Object that provides a factory for node and leaf objects.

readOnly - true IFF it is known that the AbstractBTree is read-only.

metadata - The IndexMetadata object for this B+Tree.

recordCompressorFactory - Object that knows how to (de-)compress the serialized data records.

Method Detail

getBtreeCounters

public final BTreeCounters getBtreeCounters()

Counters tracking various aspects of the btree.

setBTreeCounters

public final void setBTreeCounters(BTreeCounters btreeCounters)

Replace the BTreeCounters.

Note: This is used by the IndexManager to ensure that an index loaded from its backing store uses the BTreeCounters associated with that index since the DataService was last (re-)started.

Parameters:

btreeCounters - The counters to be used.

Throws:

IllegalArgumentException - if the argument is null.

getBloomFilter

public abstract BloomFilter getBloomFilter()

Return the optional IBloomFilter, transparently reopen()ing the index if necessary.

Specified by:

getBloomFilter in interface ILocalBTreeView

Returns:

The bloom filter -or- null if there is no bloom filter (including the case where there is a bloom filter but it has been disabled since the BTree has grown too large and the expected error rate of the bloom filter would be too high).

getCounters

public final CounterSet getCounters()

Return performance counters.

Interesting performance counters and other statistics about the index.

Return some "statistics" about the btree including both the static CounterSet and the BTreeCounterss.

Note: counters reporting directly on the AbstractBTree use a snapshot mechanism which prevents a hard reference to the AbstractBTree from being attached to the return CounterSet object. One consequence is that these counters will not update until the next time you invoke getCounters().

Note: In order to snapshot the counters use OneShotInstrument to prevent the inclusion of an inner class with a reference to the outer AbstractBTree instance.

Note: This method reports information that is NOT available from BTreeCounterss. Some of this information is either static or relatively static (e.g., the UUID for this index or its implementation class). Other information is dynamic (such as the #of nodes and leaves or the current size of the writeRetentionQueue). The dynamic information is valid for the specific index view as of the moment that it is sampled.

Specified by:

getCounters in interface IIndex

Specified by:

getCounters in interface ICounterSetAccess

See Also:

BTreeCounters.getCounters(), Expose performance counters for read-only indices

close

public void close()

The contract for ICheckpointProtocol.close() is to reduce the resource burden of the index while not rendering the index inoperative. An index that has been closed MAY be reopened at any time (conditional on the continued availability of the backing store). Such an index reference remains valid after a ICheckpointProtocol.close(). A closed index is transparently reopened by any access to the index data (scanning the index, probing the index, etc).

Note: A ICheckpointProtocol.close() on a dirty index MUST discard writes rather than flushing them to the store and MUST NOT update its Checkpoint record - (ICheckpointProtocol.close() is used to discard indices with partial writes when an AbstractTask fails). If you are seeking to ICheckpointProtocol.close() a mutable index view that state can be recovered by ICheckpointProtocol.reopen() then you MUST write a new Checkpoint record before closing the index.

Note: CLOSING A TRANSIENT INDEX WILL DISCARD ALL DATA!

This implementation clears the hard reference queue (releasing all node references), releases the hard reference to the root node, and releases the buffers on the NodeSerializer (they will be naturally reallocated on reuse).

Note: AbstractBTree is NOT thread-safe and close() MUST be invoked in a context in which there will not be concurrent threads -- the natural choice being the single-threaded commit service on the journal.

Specified by:

close in interface ICheckpointProtocol

Throws:

IllegalStateException - if the root is null, indicating that the index is already closed.

IllegalStateException - if the root is dirty (this implies that this is a mutable btree and there are mutations that have not been written through to the store)

reopen

public final void reopen()

(Re-) open the index. This method is part of a ICheckpointProtocol.close() / ICheckpointProtocol.reopen() protocol. That protocol may be used to reduce the resource burden of an index. This method is automatically invoked by a variety of methods that need to ensure that the index is available for use..

This method delegates to _reopen() if double-checked locking demonstrates that the root is null (indicating that the index has been closed). This method is automatically invoked by a variety of methods that need to ensure that the index is available for use.

Specified by:

reopen in interface ICheckpointProtocol

See Also:

ICheckpointProtocol.close(), ICheckpointProtocol.isOpen(), #getRoot()

_reopen

protected abstract void _reopen()

This method is responsible for setting up the root leaf (either new or read from the store), the bloom filter, etc. It is invoked by reopen() once root has been show to be null with double-checked locking. When invoked in this context, the caller is guaranteed to hold a lock on this. This is done to ensure that at most one thread gets to re-open the index from the backing store.

isOpen

public final boolean isOpen()

Description copied from interface: ICheckpointProtocol

An "open" index has may have some buffered data. A closed index will have to re-read any backing data from the backing store.

Specified by:

isOpen in interface ICheckpointProtocol

Returns:

If the index is "open".

See Also:

ICheckpointProtocol.close(), ICheckpointProtocol.reopen()

isTransient

public final boolean isTransient()

Return true iff this is a transient data structure (no backing store).

assertNotTransient

protected final void assertNotTransient()

isReadOnly

public final boolean isReadOnly()

Return true iff this B+Tree is read-only.

Specified by:

isReadOnly in interface IReadWriteLockManager

assertNotReadOnly

protected final void assertNotReadOnly()

Throws:

UnsupportedOperationException - if the B+Tree is read-only.

See Also:

isReadOnly()

getLastCommitTime

public abstract long getLastCommitTime()

The timestamp associated with the last IAtomicStore.commit() in which writes buffered by this index were made restart-safe on the backing store. The lastCommitTime is set when the index is loaded from the backing store and updated after each commit. It is ZERO (0L) when BTree is first created and will remain ZERO (0L) until the BTree is committed. If the backing store does not support atomic commits, then this value will always be ZERO (0L).

Note: This is fixed for an IndexSegment.

Specified by:

getLastCommitTime in interface ICheckpointProtocol

See Also:

ICheckpointProtocol.getLastCommitTime()

getRevisionTimestamp

public abstract long getRevisionTimestamp()

The timestamp associated with unisolated writes on this index. This timestamp is designed to allow the interleaving of full transactions (whose revision timestamp is assigned by the transaction service) with unisolated operations on the same indices.

The revision timestamp assigned by this method is lastCommitTime+1. The reasoning is as follows. Revision timestamps are assigned by the transaction manager when the transaction is validated as part of its commit protocol. Therefore, revision timestamps are assigned after the transaction write set is complete. Further, the assigned revisionTimestamp will be strictly LT the commitTime for that transaction. By using lastCommitTime+1 we are guaranteed that the revisionTimestamp for new writes (which will be part of some future commit point) will always be strictly GT the revisionTimestamp of historical writes (which were part of some prior commit point).

Note: Unisolated operations using this timestamp ARE NOT validated. The timestamp is simply applied to the tuple when it is inserted or updated and will become part of the restart safe state of the B+Tree once the unisolated operation participates in a commit.

Note: If an unisolated operation were to execute concurrent with a transaction commit for the same index then that could produce inconsistent results in the index and could trigger concurrent modification errors. In order to avoid such concurrent modification errors, unisolated operations which are to be mixed with full transactions MUST ensure that they have exclusive access to the unisolated index before proceeding. There are two ways to do this: (1) take the application off line for transactions; (2) submit your unisolated operations to the IConcurrencyManager which will automatically impose the necessary constraints on concurrent access to the unisolated indices.

Returns:

The revision timestamp to be assigned to an unisolated write.

Throws:

UnsupportedOperationException - if the index is read-only.

getResourceMetadata

public final IResourceMetadata[] getResourceMetadata()

Description copied from interface: IIndex

The description of the resources comprising the index view.

Specified by:

getResourceMetadata in interface IIndex

getIndexMetadata

public IndexMetadata getIndexMetadata()

The metadata for the index. This is full of good stuff about the index.

Note: The same method is exposed by ICheckpointProtocol. It is also exposed here in order to provide access to the IndexMetadata to remote clients in the scale-out architecture.

Note: If the B+Tree is read-only then the metadata object will be cloned to avoid potential modification. However, only a single cloned copy of the metadata record will be shared between all callers for a given instance of this class.

Specified by:

getIndexMetadata in interface ICheckpointProtocol

Specified by:

getIndexMetadata in interface IIndex

Returns:

The metadata record for this btree and never null.

See Also:

ICheckpointProtocol.getIndexMetadata()

toString

public String toString()

Fast summary information about the B+Tree.

Overrides:

toString in class Object

dumpPages

public BaseIndexStats dumpPages(boolean recursive,
                       boolean visitLeaves)

Description copied from interface: ICheckpointProtocol

Reports statistics for the index.

Specified by:

dumpPages in interface ICheckpointProtocol

Parameters:

recursive - When true, also collects statistics on the pages (nodes and leaves) using a low-level approach.

visitLeaves - When true and recursive:=true then the leaves of the index are also visited.

Returns:

Some interesting statistics about the index (and optionally the pages in that index) which the caller can print out.

See Also:

pre-heat the journal on startup

rangeCheck

protected final boolean rangeCheck(byte[] key,
                 boolean allowUpperBound)

Deprecated. This method has been disabled. It always returns true.

The method is disabled because it forces the caller to ensure that the query lies within the specified range. While that is all well and good, this places an undue burden on FusedView which must substitute the actual key range of a shard view for the caller's key range. This makes the test effectively into a self-check of whether FusedView has correctly done this substitution rather than a check of whether a request was mapped onto the correct shard, which was the original purpose of this test. The logic for performing such range checks was moved into RangeCheckUtil.

Iff the B+Tree is an index partition then verify that the key lies within the key range of an index partition.

Note: An index partition is identified by IndexMetadata.getPartitionMetadata() returning non- null.

Note: This method is used liberally in asserts to detect errors that can arise is client code when an index partition is split, joined, or moved.

Parameters:

key - The key.

allowUpperBound - true iff the key represents an inclusive upper bound and thus must be allowed to be LTE to the right separator key for the index partition. For example, this would be true for the toKey parameter on rangeCount or rangeIterator methods.

Returns:

true always.

Throws:

IllegalArgumentException - if the key is null

KeyOutOfRangeException - if the key does not lie within the index partition.

See Also:

KeyAfterPartitionException

getBranchingFactor

public final int getBranchingFactor()

Description copied from interface: IBTreeStatistics

The branching factor for the btree.

Specified by:

getBranchingFactor in interface IBTreeStatistics

isBalanced

public final boolean isBalanced()

Return true iff the tree is balanced.

Note: Not all tree-structured indices are balanced. For example, the BTree is balanced, but the HTree is not balanced. The height of an unbalanced tree must be discovered through a traversal of the tree.

Specified by:

isBalanced in interface ISimpleTreeIndexAccess

Returns:

true since a B+Tree is a balanced tree.

getEntryCount

public abstract long getEntryCount()

Description copied from interface: IBTreeStatistics

The #of entries (aka tuples) in the AbstractBTree. This is zero (0) for a new B+Tree. When the B+Tree supports delete markers, this value also includes tuples which have been marked as deleted.

Specified by:

getEntryCount in interface IBTreeStatistics

Specified by:

getEntryCount in interface ISimpleTreeIndexAccess

getStatistics

public IBTreeStatistics getStatistics()

Return a statistics snapshot of the B+Tree.

getUtilization

public IBTreeUtilizationReport getUtilization()

Description copied from interface: IBTreeStatistics

Computes and returns the utilization of the tree. The utilization figures do not factor in the space requirements of nodes and leaves.

Specified by:

getUtilization in interface IBTreeStatistics

getNodeSerializer

public final NodeSerializer getNodeSerializer()

The object responsible for (de-)serializing the nodes and leaves of the IIndex.

getRoot

protected final AbstractNode<?> getRoot()

The root of the btree. This is initially a leaf until the leaf is split, at which point it is replaced by a node. The root is also replaced each time copy-on-write triggers a cascade of updates.

The hard reference to the root node is cleared if the index is closed. This method automatically reopen()s the index if it is closed, making it available for use.

getRootOrFinger

protected AbstractNode<?> getRootOrFinger(byte[] key)

Returns the node or leaf to be used for search. This implementation is aware of the #finger and will return it if the key lies within the finger.

Parameters:

key - The key.

Returns:

Either the root node of the tree or a recently touched leaf that is known to span the key.

getWriteTuple

public final Tuple getWriteTuple()

Private instance used for mutation operations (insert, remove) which are single threaded. Both IRangeQuery.KEYS and IRangeQuery.VALS are requested so that indices which encode part of the application object within the key can recover the application object in insert(Object, Object) and remove(Object).

While the Tuple is not safe for use by concurrent threads, the mutation API is not safe for concurrent threads either.

getLookupTuple

public final Tuple getLookupTuple()

Return a Tuple that may be used to copy the value associated with a key out of the AbstractBTree.

While the returned Tuple is not safe for use by concurrent threads, each instance returned by this method is safe for use by the thread in which it was obtained.

See Also:

lookup(byte[], Tuple)

getContainsTuple

public final Tuple getContainsTuple()

Return a Tuple that may be used to test for the existence of tuples having a given key within the AbstractBTree.

The tuple does not copy either the keys or the values. Contains is implemented as a lookup operation that either return this tuple or null. When isolation is supported, the version metadata is examined to determine if the matching entry is flagged as deleted in which case contains() will report "false".

While the returned Tuple is not safe for use by concurrent threads, each instance returned by this method is safe for use by the thread in which it was obtained.

See Also:

contains(byte[])

insert

public final Object insert(Object key,
            Object value)

Description copied from interface: IAutoboxBTree

Insert with auto-magic handling of keys and value objects.

Specified by:

insert in interface IAutoboxBTree

Parameters:

key - The key is implicitly converted to an unsigned byte[].

value - The value is implicitly converted to a byte[].

Returns:

The de-serialized old value -or- null if there was no value stored under that key.

insert

public final byte[] insert(byte[] key,
            byte[] value)

Description copied from interface: ISimpleBTree

Insert or update a value under the key.

Specified by:

insert in interface ISimpleBTree

Parameters:

key - The key.

value - The value (may be null).

Returns:

The previous value under that key or null if the key was not found or if the previous entry for that key was marked as deleted.

putIfAbsent

public final byte[] putIfAbsent(byte[] key,
                 byte[] value)

Description copied from interface: ISimpleBTree

Insert or update a value under the key iff there is no entry for that key in the index. This is equivalent to

 if (!contains(key))
        insert(key, value);
 

However, if the index allows null values to be stored under a key and the application in fact stores null values for some tuples, then caller is not able to decide using this method whether or not the mutation was applied based on the return value. For these cases if the caller needs to know whether or not the conditional mutation actually took place, the caller CAN use the pattern if(!contains()) insert(key,value); to obtain that information.

Specified by:

putIfAbsent in interface ISimpleBTree

Parameters:

key - The key.

value - The value (may be null).

Returns:

The previous value under that key or null if the key was not found or if the previous entry for that key was marked as deleted. Note that the return value MAY be null even if there was an entry under the key. This is because the index is capable of storing a null value. In such cases the conditional mutation WAS NOT applied.

See Also:

(putIfAbsent)

insert

public final Tuple insert(byte[] key,
           byte[] value,
           boolean delete,
           boolean putIfAbsent,
           long timestamp,
           Tuple tuple)

Core method for inserting or updating a value under a key.

Parameters:

key - The variable length unsigned byte[] key.

value - The variable length byte[] value (MAY be null).

delete - true iff the index entry should be marked as deleted (this behavior is supported iff the btree supports delete markers).

putIfAbsent - When true, a pre-existing entry for the key will NOT be replaced (unless it is a deleted tuple, which is the same as if there was no entry under the key). This should ONLY be true when the top-level method is putIfAbsent. Historical code paths should specify false for an unconditional mutation. See BLZG-1539.

timestamp - The timestamp to be associated with the new or updated index entry (required iff the btree supports transactional isolation and otherwise 0L).

tuple - Data and metadata for the old value under the key will be copied onto this object (optional).

Returns:

tuple -or- null if there was no entry under that key. See ITuple.isDeletedVersion() to determine whether or not the entry is marked as deleted.

Throws:

UnsupportedOperationException - if the index is read-only.

remove

public final Object remove(Object key)

Description copied from interface: IAutoboxBTree

Remove the key and its associated value.

Specified by:

remove in interface IAutoboxBTree

Parameters:

key - The key is implicitly converted to an unsigned byte[].

Returns:

The de-serialized value stored under that key or null if the key was not found.

remove

public final byte[] remove(byte[] key)

Remove the tuple under that key (will write a delete marker if delete markers are enabled).

Specified by:

remove in interface ISimpleBTree

Parameters:

key - The key.

Returns:

The value stored under that key or null if the key was not found or if the previous entry under that key was marked as deleted.

remove

public final Tuple remove(byte[] key,
           Tuple tuple)

Core method for deleting a value under a key. If there is an entry under the key then it is removed from the index. It is an error to use this method if delete markers are being maintained. remove(byte[]) uses #insert(byte[], byte[], boolean, long, Tuple) instead of this method to mark the index entry as deleted when delete markers are being maintained.

Note: removing a key has no effect on the optional bloom filter. If a key is removed from the index by this method then the bloom filter will report a false positive for that key, which will be detected when we test the index itself. This works out fine in the scale-out design since the bloom filter is per AbstractBTree instance and split/join/move operations all result in new mutable BTrees with new bloom filters to absorb new writes. For a non-scale-out deployment, this can cause the performance of the bloom filter to degrade if you are removing a lot of keys. However, in the special case of a BTree that does NOT use delete markers, BTree.removeAll() will create a new root leaf and a new (empty) bloom filter as well.

Parameters:

key - The search key.

tuple - An object that will be used to report data and metadata for the pre-existing version (optional).

Returns:

tuple or null if there was no version under that key.

Throws:

UnsupportedOperationException - if delete markers are being maintained.

UnsupportedOperationException - if the index is read-only.

removeAll

public abstract void removeAll()

Remove all entries in the B+Tree.

Note: The IIndexManager defines methods for registering (adding) and dropping indices vs removing the entries in an individual AbstractBTree.

Specified by:

removeAll in interface ISimpleIndexAccess

lookup

public Object lookup(Object key)

Description copied from interface: IAutoboxBTree

Lookup a value for a key.

Specified by:

lookup in interface IAutoboxBTree

Parameters:

key - The key is implicitly converted to an unsigned byte[].

Returns:

The de-serialized value or null if there is no entry for that key.

lookup

public byte[] lookup(byte[] key)

Description copied from interface: ISimpleBTree

Lookup a value for a key.

Specified by:

lookup in interface ISimpleBTree

Returns:

The value stored under that key or null if there is no entry for that key or if the entry under that key is marked as deleted.

lookup

public Tuple lookup(byte[] key,
           Tuple tuple)

Core method for retrieving a value under a key. This method allows you to differentiate an index entry whose value is null from a missing index entry or (when delete markers are enabled) from a deleted index entry. Applies the optional bloom filter if it exists. If the bloom filter exists and reports true, then looks up the value for the key in the index (note that the key might not exist in the index since a bloom filter allows false positives, further the key might exist for a deleted entry).

Parameters:

key - The search key.

tuple - An object that will be used to report data and metadata for the pre-existing version (required).

Returns:

tuple or null if there is no entry in the index under the key.

contains

public boolean contains(Object key)

Description copied from interface: IAutoboxBTree

Return true iff there is an entry for the key.

Specified by:

contains in interface IAutoboxBTree

Parameters:

key - The key is implicitly converted to an unsigned byte[].

Returns:

True if the btree contains an entry for that key.

contains

public boolean contains(byte[] key)

Core method to decide whether the index has a (non-deleted) entry under a key. Applies the optional bloom filter if it exists. If the bloom filter reports true, then verifies that the key does in fact exist in the index.

Specified by:

contains in interface ISimpleBTree

Parameters:

key - The key.

Returns:

true iff the key does not exist. Or, if the btree supports isolation, if the key exists but it is marked as "deleted".

indexOf

public long indexOf(byte[] key)

Description copied from interface: ILinearList

Lookup the index position of the key.

Note that ILinearList.indexOf(byte[]) is the basis for implementing the IRangeQuery interface.

Specified by:

indexOf in interface ILinearList

Parameters:

key - The key.

Returns:

The index of the search key, if found; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be found it it were inserted into the btree without intervening mutations. Note that this guarantees that the return value will be >= 0 if and only if the key is found. When found the index will be in [0:nentries). Adding or removing entries in the tree may invalidate the index.

pos = -(pos+1) will convert an insertion point to the index at which the key would be found if it were inserted - this is also the index of the predecessor of key in the index.

See Also:

ILinearList.keyAt(long), ILinearList.valueAt(long)

keyAt

public byte[] keyAt(long index)

Description copied from interface: ILinearList

Return the key for the identified entry. This performs an efficient search whose cost is essentially the same as ISimpleBTree.lookup(byte[]).

Specified by:

keyAt in interface ILinearList

Parameters:

index - The index position of the entry (origin zero).

Returns:

The key at that index position.

See Also:

ILinearList.indexOf(byte[]), ILinearList.valueAt(long)

valueAt

public byte[] valueAt(long index)

Description copied from interface: ILinearList

Return the value for the identified entry. This performs an efficient search whose cost is essentially the same as ISimpleBTree.lookup(byte[]).

Specified by:

valueAt in interface ILinearList

Parameters:

index - The index position of the entry (origin zero).

Returns:

The value at that index position -or- null if there is a deleted entry at that index position then

See Also:

ILinearList.indexOf(byte[]), ILinearList.keyAt(long)

valueAt

public final Tuple valueAt(long index,
            Tuple tuple)

rangeCountExact

public final long rangeCountExact(byte[] fromKey,
                   byte[] toKey)

Description copied from interface: IRangeQuery

Return the exact #of tuples in a half-open key range. The fromKey and toKey need not exist in the B+Tree.

Note: If the index supports deletion markers then this operation will require a key-range scan.

Specified by:

rangeCountExact in interface IRangeQuery

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The exact #of tuples in the half-open key range.

rangeCount

public final long rangeCount()

Description copied from interface: IRangeQuery

Return the #of tuples in the index.

Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.

Specified by:

rangeCount in interface IRangeQuery

Specified by:

rangeCount in interface ISimpleIndexAccess

Returns:

The #of tuples in the index.

See Also:

ISimpleIndexAccess.rangeCount()

rangeCount

public final long rangeCount(Object fromKey,
              Object toKey)

Variant implicitly converts the optional application keys into unsigned byte[]s.

Parameters:

fromKey -

toKey -

Returns:

rangeCount

public final long rangeCount(byte[] fromKey,
              byte[] toKey)

Return the #of tuples in a half-open key range. The fromKey and toKey need not exist in the B+Tree.

Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.

This method computes the #of entries in the half-open range using AbstractNode#indexOf(Object). Since it does not scan the tuples it can not differentiate between deleted and undeleted tuples for an index that supports delete markers, but the result will be exact if delete markers are not being used. The cost is equal to the cost of lookup of the both keys. If both keys are null, then the cost is zero (no IOs).

Specified by:

rangeCount in interface IRangeQuery

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The #of tuples in the half-open key range.

rangeCountExactWithDeleted

public long rangeCountExactWithDeleted(byte[] fromKey,
                              byte[] toKey)

Note: rangeCount(byte[], byte[]) already reports deleted tuples for an AbstractBTree so this method is just delegated to that one. However, FusedView.rangeCountExactWithDeleted(byte[], byte[]) treats this case differently since it must report the exact range count when considering all sources at once. It uses a range iterator scan visiting both deleted and undeleted tuples for that.

Specified by:

rangeCountExactWithDeleted in interface IRangeQuery

Parameters:

fromKey - The lowest key that will be counted (inclusive). When null there is no lower bound.

toKey - The first key that will not be counted (exclusive). When null there is no upper bound.

Returns:

The exact #of deleted and undeleted tuples in the half-open key range.

See Also:

IRangeQuery.rangeCountExact(byte[], byte[])

scan

public final ICloseableIterator<?> scan()

Description copied from interface: ISimpleIndexAccess

Visit all entries in the index in the natural order of the index (dereferencing visited tuples to the application objects stored within those tuples).

Specified by:

scan in interface ISimpleIndexAccess

rangeIterator

public final ITupleIterator rangeIterator()

Description copied from interface: IRangeQuery

Visits all tuples in key order. This is identical to

 rangeIterator(null, null)
 

Specified by:

rangeIterator in interface IRangeQuery

Returns:

An iterator that will visit all entries in key order.

rangeIterator

public final ITupleIterator rangeIterator(Object fromKey,
                           Object toKey)

Variant implicitly converts the optional application keys into unsigned byte[]s.

Parameters:

fromKey -

toKey -

Returns:

rangeIterator

public final ITupleIterator rangeIterator(byte[] fromKey,
                           byte[] toKey)

Description copied from interface: IRangeQuery

Return an iterator that visits the entries in a half-open key range. When toKey EQ fromKey nothing will be visited. It is an error if toKey LT fromKey.

Specified by:

rangeIterator in interface IRangeQuery

Parameters:

fromKey - The first key that will be visited (inclusive lower bound). When null there is no lower bound.

toKey - The first key that will NOT be visited (exclusive upper bound). When null there is no upper bound.

See Also:

SuccessorUtil, which may be used to compute the successor of a value before encoding it as a component of a key., BytesUtil#successor(byte[]), which may be used to compute the successor of an encoded key., EntryFilter, which may be used to filter the entries visited by the iterator.

rangeIterator

public final ITupleIterator rangeIterator(Object fromKey,
                           Object toKey,
                           int capacity,
                           int flags,
                           IFilter filter)

Variant implicitly converts the optional application keys into unsigned byte[]s.

Parameters:

fromKey -

toKey -

Returns:

rangeIterator

public ITupleIterator rangeIterator(byte[] fromKey,
                           byte[] toKey,
                           int capacityIsIgnored,
                           int flags,
                           IFilter filter)

Designated variant (the one that gets overridden) for an iterator that visits the entries in a half-open key range. When toKey EQ fromKey nothing will be visited. It is an error if toKey LT fromKey.

Core implementation.

Note: If IRangeQuery.CURSOR is specified the returned iterator supports traversal with concurrent modification by a single-threaded process (the BTree is NOT thread-safe for writers). Write are permitted iff AbstractBTree allows writes.

Note: IRangeQuery.REVERSE is handled here by wrapping the underlying ITupleCursor.

Note: IRangeQuery.REMOVEALL is handled here by wrapping the iterator.

Note: FusedView.rangeIterator(byte[], byte[], int, int, IFilter) is also responsible for constructing an ITupleIterator in a manner similar to this method. If you are updating the logic here, then check the logic in that method as well!

Specified by:

rangeIterator in interface IRangeQuery

Parameters:

fromKey - The first key that will be visited (inclusive lower bound). When null there is no lower bound.

toKey - The first key that will NOT be visited (exclusive upper bound). When null there is no upper bound.

capacityIsIgnored - The #of entries to buffer at a time. This is a hint and MAY be zero (0) to use an implementation specific default capacity. A non-zero value may be used if you know that you want at most N results or if you want to override the default #of results to be buffered before sending them across a network interface. (Note that you can control the default value using IBigdataClient.Options#DEFAULT_CLIENT_RANGE_QUERY_CAPACITY).

flags - A bitwise OR of IRangeQuery.KEYS, IRangeQuery.VALS, etc.

filter - An optional object used to construct a stacked iterator. When IRangeQuery.CURSOR is specified in flags, the base iterator will implement ITupleCursor and the first filter in the stack can safely cast the source iterator to an ITupleCursor. If the outermost filter in the stack does not implement ITupleIterator, then it will be wrapped an ITupleIterator.

See Also:

SuccessorUtil, which may be used to compute the successor of a value before encoding it as a component of a key., BytesUtil#successor(byte[]), which may be used to compute the successor of an encoded key., IFilterConstructor, which may be used to construct an iterator stack performing filtering or other operations.

rangeCopy

public long rangeCopy(IIndex src,
             byte[] fromKey,
             byte[] toKey,
             boolean overflow)

Copy all data, including deleted index entry markers and timestamps iff supported by the source and target. The goal is an exact copy of the data in the source btree.

Parameters:

src - The source index.

fromKey - The first key that will be copied (inclusive). When null there is no lower bound.

toKey - The first key that will NOT be copied (exclusive). When null there is no upper bound.

overflow - When true the IOverflowHandler defined for the source index (if any) will be applied to copy raw records onto the backing store for this index. This value SHOULD be false if the two indices have the same backing store and true otherwise.

Returns:

The #of index entries that were copied.

Throws:

UnsupportedOperationException - if the src and this do not have the same setting for IndexMetadata.getDeleteMarkers()

UnsupportedOperationException - if the src and this do not have the same setting for IndexMetadata.getVersionTimestamps()

See Also:

CompactTask, OverflowManager

submit

public <T> T submit(byte[] key,
           ISimpleIndexProcedure<T> proc)

Description copied from interface: IIndex

Submits an index procedure that operations on a single key to the appropriate index partition returning the result of that procedure.

Specified by:

submit in interface IIndex

Parameters:

key - The key.

proc - The procedure.

Returns:

The value returned by IIndexProcedure.apply(IIndex)

submit

public void submit(byte[] fromKey,
          byte[] toKey,
          IKeyRangeIndexProcedure proc,
          IResultHandler handler)

Description copied from interface: IIndex

The procedure will be transparently applied against each index partition spanned by the given key range.

Note: Since this variant of submit() does not split keys the fromIndex and toIndex in the Splits reported to the IResultHandler will be zero (0).

Specified by:

submit in interface IIndex

Parameters:

fromKey - The lower bound (inclusive) -or- null if there is no lower bound.

toKey - The upper bound (exclusive) -or- null if there is no upper bound.

proc - The procedure. If the procedure implements the IParallelizableIndexProcedure marker interface then it MAY be executed in parallel against the relevant index partition(s).

submit

public void submit(int fromIndex,
          int toIndex,
          byte[][] keys,
          byte[][] vals,
          AbstractKeyArrayIndexProcedureConstructor ctor,
          IResultHandler aggregator)

Description copied from interface: IIndex

Runs a procedure against an index.

Note: This may be used to send custom logic together with the data to a remote index or index partition. When the index is remote both the procedure and the return value MUST be Serializable.

Note: The scale-out indices add support for auto-split of the procedure such that it runs locally against each relevant index partition.

Specified by:

submit in interface IIndex

Parameters:

fromIndex - The index of the first key to be used (inclusive).

toIndex - The index of the last key to be used (exclusive).

keys - The keys (required).

vals - The values (optional depending on the procedure).

ctor - An object that can create instances of the procedure.

aggregator - When defined, results from each procedure application will be reported to this object. TODO In order to allow parallelization within a shard, we need to modify this method signature to pass in an IResultHandler constructor object. That might be something which could be pushed down onto the ctor argument. It would be used in scale-out to create a DS local result handler so we can locally aggregate when parallelizing against each shard and then return that aggregated result to the client which would extract the aggregate result across the shards from the client's result handler. See BLZG-1537.

See Also:

(Schedule more IOs when loading data)

getRightMostNode

public AbstractNode getRightMostNode(boolean nodesOnly)

Utility method returns the right-most node in the B+Tree.

Parameters:

nodesOnly - when true the search will halt at the right-most non-leaf. Otherwise it will return the right-most leaf.

Returns:

The right-most child in the B+Tree -or- null if the root of the B+Tree is a leaf and nodesOnly == true.

newLeafCursor

public abstract ILeafCursor newLeafCursor(SeekEnum where)

Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree. The cursor will be initially positioned on the leaf identified by the symbolic constant.

newLeafCursor

public abstract ILeafCursor newLeafCursor(byte[] key)

Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree. The cursor will be initially positioned on the leaf that spans the given key.

Parameters:

key - The key (required).

Throws:

IllegalArgumentException - if key is null.

dump

public boolean dump(PrintStream out)

Recursive dump of the tree.

Parameters:

out - The dump is written on this stream.

Returns:

true unless an inconsistency is detected.

dump

public boolean dump(org.apache.log4j.Level level,
           PrintStream out)

getLevel

public int getLevel(AbstractNode t)

Return the level of t below the root node or leaf.

Parameters:

t - A node or leaf that belongs to this B+Tree.

Returns:

ZERO (0) iff t == root and otherwise the number of levels that t is below the root.

Throws:

IllegalArgumentException - if t is null.

IllegalArgumentException - if t does not belong to this B+Tree.

getLevel

public int getLevel(AbstractNode t,
           AbstractNode node)

Return the level of t below the given node or leaf.

Parameters:

t - A node or leaf that belongs to this B+Tree.

node - A node or leaf that is either t or (recursively) some parent of t.

Returns:

ZERO (0) iff t == root and otherwise the number of levels that t is below the root.

Throws:

IllegalArgumentException - if t is null.

IllegalArgumentException - if t does not belong to this B+Tree.

IllegalArgumentException - if node is null.

IllegalArgumentException - if node does not belong to this B+Tree.

NotChildException - if t is neither node nor some descendant of node.

touch

protected void touch(AbstractNode<?> node)

This method is responsible for putting the node or leaf onto the ring buffer which controls (a) how long we retain a hard reference to the node or leaf; and (b) for writes, when the node or leaf is evicted with a zero reference count and made persistent (along with all dirty children). The concurrency requirements and the implementation behavior and guarentees differ depending on whether the B+Tree is read-only or mutable for two reasons: For writers, the B+Tree is single-threaded so there is no contention. For readers, every touch on the B+Tree goes through this point, so it is vital to make this method non-blocking.

Writers

This method guarantees that the specified node will NOT be synchronously persisted as a side effect and thereby made immutable. (Of course, the node may be already immutable.)

In conjunction with DefaultEvictionListener, this method guarantees that the reference counter for the node will reflect the #of times that the node is actually present on the writeRetentionQueue.

If the node is not found on a scan of the head of the queue, then it is appended to the queue and its AbstractNode.referenceCount is incremented. If a node is being appended to the queue and the queue is at capacity, then this will cause a reference to be evicted from the queue. If the reference counter for the evicted node or leaf is zero and the evicted node or leaf is dirty, then a data record will be coded for the evicted node or leaf and written onto the backing store. A subsequent attempt to modify the node or leaf will force copy-on-write for that node or leaf.

For the mutable B+Tree we also track the #of references to the node/leaf on the ring buffer. When that reference count reaches zero we do an eviction and the node/leaf is written onto the backing store if it is dirty. Those reference counting games DO NOT matter for read-only views so we can take a code path which does not update the per-node/leaf reference count and we do not need to use either synchronization or atomic counters to track the reference counts.

Readers

In order to reduce contention for the lock required to update the backing queue, the writeRetentionQueue is configured to collect references for touched nodes or leaves in a thread-local queue and then batch those references through to the backing hard reference queue while holding the lock.

Parameters:

node - The node or leaf.

writeNodeRecursive

protected final void writeNodeRecursive(AbstractNode<?> node)

Write a dirty node and its children using a post-order traversal that first writes any dirty leaves and then (recursively) their parent nodes. The parent nodes are guaranteed to be dirty if there is a dirty child so this never triggers copy-on-write. This is used as part of the commit protocol where it is invoked with the root of the tree, but it may also be used to incrementally flush dirty non-root Nodes. Note: This will throw an exception if the backing store is read-only.

Parameters:

node - The root of the hierarchy of nodes to be written. The node MUST be dirty. The node this does NOT have to be the root of the tree and it does NOT have to be a Node.

See Also:

(Reduce commit latency by parallel checkpoint by level of dirty pages in an index)

writeNodeRecursiveCallersThread

protected final void writeNodeRecursiveCallersThread(AbstractNode<?> node)

This is the historical implementation and runs entirely in the caller's thread.

Parameters:

node -

writeNodeRecursiveConcurrent

protected final void writeNodeRecursiveConcurrent(AbstractNode<?> node)

Writes the dirty nodes and leaves in level sets (one level at a time) with up to one thread per dirty node/leave in a given level. This can reduce the latency of ICheckpointProtocol.writeCheckpoint() or for a Node evicted from the writeRetentionQueue. Whether this is driven by ICheckpointProtocol.writeCheckpoint() or touch(AbstractNode), we have the same contract with respect to eviction as the single-threaded eviction logic - we are just doing it in parallel level sets.

Parameters:

node -

See Also:

(Reduce commit latency by parallel checkpoint by level of dirty pages in an index)

writeNodeOrLeaf

protected long writeNodeOrLeaf(AbstractNode<?> node)

Codes the node and writes the coded record on the store (non-recursive). The node MUST be dirty. If the node has a parent, then the parent is notified of the persistent identity assigned to the node by the store. This method is NOT recursive and dirty children of a node will NOT be visited. By coding the nodes and leaves as they are evicted from the writeRetentionQueue, the B+Tree continuously converts nodes and leaves to their more compact coded record forms which results in a smaller in memory footprint.

Note: For a transient B+Tree, this merely codes the node but does not write the node on the store (there is none).

Returns:

The persistent identity assigned by the store.

Throws:

UnsupportedOperationException - if the B+Tree (or the backing store) is read-only.

readNodeOrLeaf

protected AbstractNode<?> readNodeOrLeaf(long addr)

Read a node or leaf from the store.

Note: Callers SHOULD be synchronized in order to ensure that only one thread will read the desired node or leaf in from the store and attach the reference to the newly read node or leaf as appropriate into the existing data structures (e.g., as the root reference or as a child of a node or leaf already live in memory).

Parameters:

addr - The address in the store.

Returns:

The node or leaf.

Throws:

IllegalArgumentException - if the address is IAddressManager.NULL.

encodeRecordAddr

public static byte[] encodeRecordAddr(ByteArrayBuffer recordAddrBuf,
                      long addr)

Encode a raw record address into a byte[] suitable for storing in the value associated with a tuple and decoding using decodeRecordAddr(byte[])

Parameters:

recordAddrBuf - The buffer that will be used to format the record address.

addr - The raw record address.

Returns:

A newly allocated byte[] which encodes that address.

decodeRecordAddr

public static long decodeRecordAddr(byte[] buf)

Decodes a signed long value as encoded by #appendSigned(long).

Parameters:

buf - The buffer containing the encoded record address.

Returns:

The signed long value.

recycle

protected int recycle(long addr)

Recycle (aka delete) the allocation. This method also adjusts the #of bytes released in the BTreeCounters.

Parameters:

addr - The address to be recycled.

Returns:

The #of bytes which were recycled and ZERO (0) if the address is IAddressManager.NULL.

readLock

public final Lock readLock()

Description copied from interface: IReadWriteLockManager

Return a Lock that may be used to obtain a shared read lock which is used (in the absence of other concurrency control mechanisms) to permit concurrent readers on an unisolated index while serializing access to that index when a writer must run. This is exposed for processes which need to obtain the write lock to coordinate external operations.

Note: If the persistence capable data structure is read-only then the returned Lock is a singleton that ignores all lock requests. This is because our read-only persistence capable data structures are already thread-safe for concurrent readers.

Specified by:

readLock in interface IReadWriteLockManager

Returns:

The lock.

writeLock

public final Lock writeLock()

Description copied from interface: IReadWriteLockManager

Return a Lock that may be used to obtain an exclusive write lock which is used (in the absence of other concurrency control mechanisms) to serialize all processes accessing an unisolated index when a writer must run. This is exposed for processes which need to obtain the write lock to coordinate external operations.

Specified by:

writeLock in interface IReadWriteLockManager

Returns:

The lock.

getReadLockCount

public final int getReadLockCount()

Description copied from interface: IReadWriteLockManager

Return the #of read-locks held by the current thread for a mutable index view.

Specified by:

getReadLockCount in interface IReadWriteLockManager

Returns:

The #of reentrant read locks held by the current thread -or- ZERO if the index is read-only (read locks are not tracked for a read-only index view).