com.bigdata.btree

Class IndexSegment

java.lang.Object

com.bigdata.btree.AbstractBTree

com.bigdata.btree.IndexSegment

All Implemented Interfaces:

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

public class IndexSegment
extends AbstractBTree

An index segment is read-only btree corresponding to some key range of a potentially distributed index. The file format of the index segment includes a metadata record, the leaves of the segment in key order, and the nodes of the segment in an arbitrary order. It is possible to map or buffer the part of the file containing the index nodes or the entire file depending on application requirements.

Note: iterators returned by this class do not support removal (the nodes and leaves will all refuse mutation operations).

Version:

$Id$

Author:

Bryan Thompson

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	IndexSegment.ImmutableLeafCursor Cursor using the double-linked leaves for efficient scans.
protected static class	IndexSegment.ImmutableNodeFactory Factory for immutable nodes and leaves used by the NodeSerializer.
static class	IndexSegment.IndexSegmentTupleCursor<E> Implementation for an immutable IndexSegment.

Nested classes/interfaces inherited from class com.bigdata.btree.AbstractBTree

AbstractBTree.IBTreeCounters

Field Summary

Fields inherited from class com.bigdata.btree.AbstractBTree

branchingFactor, debug, DEBUG, dumpLog, error, ERROR_CLOSED, ERROR_ERROR_STATE, ERROR_LESS_THAN_ZERO, ERROR_READ_ONLY, ERROR_TOO_LARGE, ERROR_TRANSIENT, INFO, log, metadata, ndistinctOnWriteRetentionQueue, nodeSer, readOnly, root, store, storeCache, writeRetentionQueue

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

Constructor and Description
IndexSegment(IndexSegmentStore fileStore) Open a read-only index segment.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	_reopen() This method is responsible for setting up the root leaf (either new or read from the store), the bloom filter, etc.
void	close() Extended to also close the backing file.
protected void	finalize() Extended to explicitly close the IndexSegment and the backing IndexSegmentStore.
IndexSegment.ImmutableNodeFactory.ImmutableLeaf	findLeaf(byte[] key)
long	findLeafAddr(byte[] key) Find the address of the leaf that would span the key.
BloomFilter	getBloomFilter() Return the optional IBloomFilter, transparently AbstractBTree.reopen()ing the index if necessary.
ICheckpoint	getCheckpoint() Returns the most recent ICheckpoint record.
ICounter	getCounter() Operation is disallowed - the counter is only stored in the mutable BTree.
IDirtyListener	getDirtyListener() Return the IDirtyListener.
long	getEntryCount() The #of entries (aka tuples) in the AbstractBTree.
int	getHeight() The height of the btree.
long	getLastCommitTime() The value of the IndexSegmentCheckpoint.commitTime field.
long	getLeafCount() The #of leaf nodes in the AbstractBTree.
long	getMetadataAddr() The address at which the most recent IndexMetadata record was written.
BTree	getMutableBTree() The BTree that is absorbing writes for the view.
long	getNodeCount() The #of non-leaf nodes in the AbstractBTree.
long	getRecordVersion() The value of the record version number that will be assigned to the next node or leaf written onto the backing store.
long	getRevisionTimestamp() The timestamp associated with unisolated writes on this index.
long	getRootAddr() The address of the last written root of the persistent data structure -or- 0L if there is no root.
int	getSourceCount() The #of AbstractBTrees sources for the view.
AbstractBTree[]	getSources() An array containing the ordered sources in the view.
IndexSegmentStore	getStore() The backing store.
long	handleCommit(long commitTime) Flush dirty state to the store in preparation for an atomic commit and return the address from which the persistence capable data structure may be reloaded.
void	invalidate(Throwable t) Mark an ICommitter as invalid.
IndexSegment.ImmutableLeafCursor	newLeafCursor(byte[] key) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
IndexSegment.ImmutableLeafCursor	newLeafCursor(SeekEnum where) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
IndexSegment.ImmutableNodeFactory.ImmutableLeaf	readLeaf(long addr) Type-safe method reads the leaf from the backing file given the address of that leaf.
protected AbstractNode<?>	readNodeOrLeaf(long addr) Extended to transparently re-open the backing IndexSegmentStore.
void	removeAll() Remove all entries in the B+Tree.
void	setDirtyListener(IDirtyListener listener) Set or clear the listener (there can be only one).
void	setLastCommitTime(long lastCommitTime) Sets the lastCommitTime.
String	toString() Fast summary information about the B+Tree.
long	writeCheckpoint() Checkpoint operation must #flush() dirty nodes, dirty persistent data structures, etc, write a new Checkpoint record on the backing store, save a reference to the current Checkpoint, and return the address of that Checkpoint record.
Checkpoint	writeCheckpoint2() Checkpoint operation must #flush() dirty nodes, dirty persistent data structures, etc, write a new Checkpoint record on the backing store, save a reference to the current Checkpoint, and return the address of that Checkpoint record.

Methods inherited from class com.bigdata.btree.AbstractBTree

assertNotReadOnly, assertNotTransient, contains, contains, decodeRecordAddr, dump, dump, dumpPages, encodeRecordAddr, getBranchingFactor, getBtreeCounters, getContainsTuple, getCounters, getIndexMetadata, getLevel, getLevel, getLookupTuple, getNodeSerializer, getReadLockCount, getResourceMetadata, getRightMostNode, getRoot, getRootOrFinger, getStatistics, getUtilization, getWriteTuple, indexOf, insert, insert, insert, isBalanced, isOpen, isReadOnly, isTransient, keyAt, lookup, lookup, lookup, putIfAbsent, rangeCheck, rangeCopy, rangeCount, rangeCount, rangeCount, rangeCountExact, rangeCountExactWithDeleted, rangeIterator, rangeIterator, rangeIterator, rangeIterator, rangeIterator, readLock, recycle, remove, remove, remove, reopen, scan, setBTreeCounters, submit, submit, submit, touch, valueAt, valueAt, writeLock, writeNodeOrLeaf, writeNodeRecursive, writeNodeRecursiveCallersThread, writeNodeRecursiveConcurrent

Methods inherited from class java.lang.Object

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

Constructor Detail

IndexSegment

public IndexSegment(IndexSegmentStore fileStore)

Open a read-only index segment.

Parameters:

fileStore - The store containing the IndexSegment.

See Also:

IndexSegmentStore.loadIndexSegment()

Method Detail

getHeight

public final int getHeight()

Description copied from interface: IBTreeStatistics

The height of the btree. The height is the #of levels minus one. A btree with only a root leaf has height := 0. A btree with a root node and one level of leaves under it has height := 1. Note that all leaves of a btree are at the same height (this is what is means for the btree to be "balanced"). Also note that the height only changes when we split or join the root node (a btree maintains balance by growing and shrinking in levels from the top rather than the leaves).

See Also:

ISimpleTreeIndexAccess.isBalanced()

getNodeCount

public final long getNodeCount()

Description copied from interface: IBTreeStatistics

The #of non-leaf nodes in the AbstractBTree. This is zero (0) for a new btree.

getLeafCount

public final long getLeafCount()

Description copied from interface: IBTreeStatistics

The #of leaf nodes in the AbstractBTree. This is one (1) for a new btree.

getEntryCount

public final 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

Specified by:

getEntryCount in class AbstractBTree

getCheckpoint

public final ICheckpoint getCheckpoint()

Description copied from interface: ICheckpointProtocol

Returns the most recent ICheckpoint record.

Returns:

The most recent ICheckpoint record and never null.

getRecordVersion

public long getRecordVersion()

Description copied from interface: ICheckpointProtocol

The value of the record version number that will be assigned to the next node or leaf written onto the backing store. This number is incremented each time a node or leaf is written onto the backing store. The initial value is ZERO (0). The first value assigned to a node or leaf will be ZERO (0). TODO Nobody is actually incrementing this value right now.

getMetadataAddr

public long getMetadataAddr()

Description copied from interface: ICheckpointProtocol

The address at which the most recent IndexMetadata record was written.

getRootAddr

public long getRootAddr()

Description copied from interface: ICheckpointProtocol

The address of the last written root of the persistent data structure -or- 0L if there is no root. A 0L return may be an indication that an empty data structure will be created on demand.

setLastCommitTime

public void setLastCommitTime(long lastCommitTime)

Description copied from interface: ICheckpointProtocol

Sets the lastCommitTime.

Note: The lastCommitTime is set by a combination of the AbstractJournal and Name2Addr based on the actual commitTime of the commit during which an Name2Addr.Entry for that index was last committed. It is set for both historical index reads and unisolated index reads using Name2Addr.Entry.commitTime. The lastCommitTime for an unisolated index will advance as commits are performed with that index.

Parameters:

lastCommitTime - The timestamp of the last committed state of this index.

writeCheckpoint

public long writeCheckpoint()

Description copied from interface: ICheckpointProtocol

Checkpoint operation must #flush() dirty nodes, dirty persistent data structures, etc, write a new Checkpoint record on the backing store, save a reference to the current Checkpoint, and return the address of that Checkpoint record.

Note: A checkpoint by itself is NOT an atomic commit. The commit protocol is at the store level and uses Checkpoints to ensure that the state of the persistence capable data structure is current on the backing store.

Returns:

The address at which the Checkpoint record for the persistence capable was written onto the store. The data structure can be reloaded from this Checkpoint record.

writeCheckpoint2

public Checkpoint writeCheckpoint2()

Description copied from interface: ICheckpointProtocol

Checkpoint operation must #flush() dirty nodes, dirty persistent data structures, etc, write a new Checkpoint record on the backing store, save a reference to the current Checkpoint, and return the address of that Checkpoint record.

Note: A checkpoint by itself is NOT an atomic commit. The commit protocol is at the store level and uses Checkpoints to ensure that the state of the persistence capable data structure is current on the backing store.

Returns:

The Checkpoint record for the persistent data structure which was written onto the store. The persistent data structure can be reloaded from this Checkpoint record.

getDirtyListener

public IDirtyListener getDirtyListener()

Description copied from interface: ICheckpointProtocol

Return the IDirtyListener.

setDirtyListener

public void setDirtyListener(IDirtyListener listener)

Description copied from interface: ICheckpointProtocol

Set or clear the listener (there can be only one).

Parameters:

listener - The listener.

handleCommit

public long handleCommit(long commitTime)

Description copied from interface: ICommitter

Flush dirty state to the store in preparation for an atomic commit and return the address from which the persistence capable data structure may be reloaded.

Parameters:

commitTime - The timestamp assigned to the commit.

Returns:

The address of the record from which the persistence capable data structure may be reloaded. If no changes have been made then the previous address should be returned as it is still valid.

invalidate

public void invalidate(Throwable t)

Description copied from interface: ICommitter

Mark an ICommitter as invalid. This will prevent it from allowing any writes through to the backing store.

Parameters:

t - A cause (required).

See Also:

https://jira.blazegraph.com/browse/BLZG-1953

toString

public String toString()

Fast summary information about the B+Tree.

Overridden to be thread-safe without requiring any locks.

Overrides:

toString in class AbstractBTree

close

public void close()

Extended to also close the backing file.

Specified by:

close in interface ICheckpointProtocol

Overrides:

close in class AbstractBTree

getStore

public final IndexSegmentStore getStore()

The backing store.

Overridden to a more constrained type.

finalize

protected void finalize()
                 throws Throwable

Extended to explicitly close the IndexSegment and the backing IndexSegmentStore. A finalizer is necessary for this class because we maintain IndexSegments in a weak value cache and do not explicitly close then before their reference is cleared. This leads to the IndexSegmentStore being left open. The finalizer fixes that.

Overrides:

finalize in class Object

Throws:

Throwable

_reopen

protected void _reopen()

Description copied from class: AbstractBTree

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 AbstractBTree.reopen() once AbstractBTree.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.

Specified by:

_reopen in class AbstractBTree

getBloomFilter

public final BloomFilter getBloomFilter()

Description copied from class: AbstractBTree

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

Specified by:

getBloomFilter in interface ILocalBTreeView

Specified by:

getBloomFilter in class AbstractBTree

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).

getLastCommitTime

public final long getLastCommitTime()

The value of the IndexSegmentCheckpoint.commitTime field.

Specified by:

getLastCommitTime in interface ICheckpointProtocol

Specified by:

getLastCommitTime in class AbstractBTree

See Also:

ICheckpointProtocol.getLastCommitTime()

getRevisionTimestamp

public final long getRevisionTimestamp()

Description copied from class: AbstractBTree

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.

Specified by:

getRevisionTimestamp in class AbstractBTree

Returns:

The revision timestamp to be assigned to an unisolated write.

Throws:

UnsupportedOperationException - always since the IndexSegment is read-only.

getCounter

public final ICounter getCounter()

Operation is disallowed - the counter is only stored in the mutable BTree.

removeAll

public final void removeAll()

Description copied from class: AbstractBTree

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

Specified by:

removeAll in class AbstractBTree

Throws:

UnsupportedOperationException - always.

readLeaf

public IndexSegment.ImmutableNodeFactory.ImmutableLeaf readLeaf(long addr)

Type-safe method reads the leaf from the backing file given the address of that leaf. This method is suitable for ad-hoc examination of the leaf or for a low-level iterator based on the prior/next leaf addresses.

Note: The parent is NOT set on the leaf but it MAY be defined if the leaf was read from cache.

Parameters:

addr - The address of a leaf.

Returns:

That leaf.

readNodeOrLeaf

protected AbstractNode<?> readNodeOrLeaf(long addr)

Extended to transparently re-open the backing IndexSegmentStore.

Overrides:

readNodeOrLeaf in class AbstractBTree

Parameters:

addr - The address in the store.

Returns:

The node or leaf.

findLeaf

public IndexSegment.ImmutableNodeFactory.ImmutableLeaf findLeaf(byte[] key)

findLeafAddr

public long findLeafAddr(byte[] key)

Find the address of the leaf that would span the key.

Parameters:

key - The key

Returns:

The address of the leaf which would span that key.

Throws:

IllegalArgumentException - if the key is null.

RuntimeException - if the key does not lie within the optional key-range constraints for an index partition.

newLeafCursor

public IndexSegment.ImmutableLeafCursor newLeafCursor(SeekEnum where)

Description copied from class: AbstractBTree

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.

Specified by:

newLeafCursor in class AbstractBTree

newLeafCursor

public IndexSegment.ImmutableLeafCursor newLeafCursor(byte[] key)

Description copied from class: AbstractBTree

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.

Specified by:

newLeafCursor in class AbstractBTree

Parameters:

key - The key (required).

getMutableBTree

public BTree getMutableBTree()

Description copied from interface: ILocalBTreeView

The BTree that is absorbing writes for the view.

getSourceCount

public int getSourceCount()

Description copied from interface: ILocalBTreeView

The #of AbstractBTrees sources for the view. This will be ONE (1) if the view is a BTree.

getSources

public AbstractBTree[] getSources()

Description copied from interface: ILocalBTreeView

An array containing the ordered sources in the view. Changes to the array DO NOT affect the view. If the view is an AbstractBTree then the array will contain a single element which is that AbstractBTree.