com.sleepycat.je.tree

Class BIN

java.lang.Object

com.sleepycat.je.tree.Node

com.sleepycat.je.tree.IN

com.sleepycat.je.tree.BIN

All Implemented Interfaces:

Loggable, java.lang.Comparable<IN>

Direct Known Subclasses:

DBIN

public class BIN
extends IN
implements Loggable

A BIN represents a Bottom Internal Node in the JE tree.

Field Summary

Fields inherited from class com.sleepycat.je.tree.IN

ACCUMULATED_LIMIT, BIN_LEVEL, databaseImpl, DBMAP_LEVEL, EXACT_MATCH, INSERT_SUCCESS, latch, LEVEL_MASK, MAIN_LEVEL, MAX_LEVEL, MAY_EVICT_LNS, MAY_EVICT_NODE, MAY_NOT_EVICT, MIN_LEVEL

Fields inherited from class com.sleepycat.je.tree.Node

NULL_NODE_ID

Constructor Summary

Constructors

Constructor and Description
BIN()
BIN(DatabaseImpl db, byte[] identifierKey, int maxEntriesPerNode, int level)
BIN(SizeofMarker marker) For Sizeof, set all array fields to null, since they are not part of the fixed overhead.

Method Summary

Methods

Modifier and Type	Method and Description
(package private) void	accumulateStats(TreeWalkerStatsAccumulator acc)
void	addCursor(CursorImpl cursor) Register a cursor with this BIN.
(package private) void	adjustCursors(IN newSibling, int newSiblingLow, int newSiblingHigh) Adjust any cursors that are referring to this BIN.
(package private) void	adjustCursorsForInsert(int insertIndex) Adjust cursors referring to this BIN following an insert.
void	afterLog(LogManager logManager, INLogItem item, INLogContext context) Overrides the IN method to account for deltas.
void	beforeLog(LogManager logManager, INLogItem item, INLogContext context) Overrides the IN method to account for deltas.
java.lang.String	beginTag()
(package private) void	clearEntry(int idx) Overridden to account for VLSNCache entries.
void	clearKnownDeleted(int index) Clear the known deleted flag.
boolean	compress(LocalUtilizationTracker localTracker) Compress this BIN by removing any entries that are deleted.
long	computeMemorySize() Adds VLSNCache size to computed memory size.
(package private) void	copyEntries(int from, int to, int n) Overridden to account for VLSNCache entries.
(package private) void	copyEntry(int idx, IN from, int fromIdx) Overridden to account for VLSNCache entries.
protected IN	createNewInstance(byte[] identifierKey, int maxEntries, int level) Create a new BIN.
BINReference	createReference() Create a holder object that encapsulates information about this BIN for the INCompressor.
java.lang.String	endTag()
(package private) boolean	entryZeroKeyComparesLow() Indicates whether entry 0's key is "special" in that it always compares less than any other key.
void	evictLN(int index) Evict a single LN if allowed and adjust the memory budget.
long	evictLNs() Reduce memory consumption by evicting all LN targets.
Node	fetchTarget(int idx) We require exclusive latches on a BIN, so this method does not need to declare that it throws RelatchRequiredException.
(package private) int	getChildEvictionType() Note that the IN may or may not be latched when this method is called.
java.util.Set<CursorImpl>	getCursorSet()
protected long	getFixedMemoryOverhead()
long	getLastDeltaVersion() Overrides the IN method to account for deltas.
long	getLastLoggedVersion() Overrides the IN method to account for deltas.
LogEntryType	getLogType() Get the log type of this node.
long	getTreeAdminMemorySize() Returns the treeAdmin memory in objects referenced by this BIN.
long	getVLSN(int idx, boolean allowFetch) Returns the VLSN.
VLSNCache	getVLSNCache() For unit testing.
(package private) boolean	hasPinnedChildren() Note that the IN may or may not be latched when this method is called.
void	incEvictStats(Evictor.EvictionSource source) We categorize eviction stats by the type of IN, so IN subclasses update different stats.
void	incFetchStats(EnvironmentImpl envImpl, boolean isMiss) We categorize fetch stats by the type of node, so node subclasses update different stats.
(package private) boolean	isAlwaysLatchedExclusively()
boolean	isBIN()
boolean	isCompressible()
protected boolean	isEvictionProhibited() Note that the IN may or may not be latched when this method is called.
(package private) boolean	isValidForDelete() Check if this node fits the qualifications for being part of a deletable subtree.
void	logDirtyChildren() When splits and checkpoints intermingle in a deferred write databases, a checkpoint target may appear which has a valid target but a null LSN.
int	nCursors()
void	queueSlotDeletion() This method is called whenever a deleted slot is observed (when the slot's PendingDeleted or KnownDeleted flag is set), to ensure that the slot is compressed away.
void	removeCursor(CursorImpl cursor) Unregister a cursor with this bin.
void	setKnownDeleted(int index) Mark this entry as deleted, using the delete flag.
void	setKnownDeletedClearAll(int index)
(package private) void	setLastLoggedLsn(long lsn) Overrides the IN method to account for deltas.
void	setProhibitNextDelta() If cleaned or compressed, must log full version.
(package private) void	setTarget(int idx, Node target) Updates the VLSN cache when an LN target is evicted.
java.lang.String	shortClassName()
boolean	shouldLogDelta() Decide whether to log a full or partial BIN, depending on the ratio of the delta size to full BIN size, and the number of deltas that have been logged since the last full.
(package private) void	splitSpecial(IN parent, int parentIndex, int maxEntriesPerNode, byte[] key, boolean leftSide, CacheMode cacheMode) Called when we know we are about to split on behalf of a key that is the minimum (leftSide) or maximum (!leftSide) of this node.
(package private) boolean	validateSubtreeBeforeDelete(int index)
void	verifyCursors() For each cursor in this BIN's cursor set, ensure that the cursor is actually referring to this BIN.

Methods inherited from class com.sleepycat.je.tree.IN

accountForDeferredWriteSubtreeRemoval, accountForSubtreeRemoval, afterLogCommon, beforeLogCommon, changeMemorySize, clearLsnCompaction, clearPendingDeleted, compactMemory, compareTo, compareToKeyPrefix, deleteEntry, deleteEntry, dumpDeletedState, dumpKeys, dumpLog, dumpLogAdditional, dumpString, equals, fetchTargetWithExclusiveLatch, findEntry, findEntry, findParent, getBudgetedMemorySize, getCompactMaxKeyLength, getDatabase, getDatabaseId, getDirty, getEntryLsnByteArray, getEntryLsnLongArray, getEvictionType, getGeneration, getGenericLogType, getIdentifierKey, getInListResident, getInMemorySize, getKey, getKeyComparator, getKeyPrefix, getKeyVals, getLastFullVersion, getLatchQueueLength, getLatchString, getLevel, getLogSize, getLsn, getMaxEntries, getMigrate, getNEntries, getNodeId, getRecalcToggle, getState, getTarget, getTargets, hashCode, hasResidentChildren, init, initEntryLsn, initMemorySize, insertEntry, insertEntry1, isDbRoot, isDirty, isEntryKnownDeleted, isEntryPendingDeleted, isEvictable, isIN, isKeyInBounds, isLatchOwnerForRead, isLatchOwnerForWrite, isRoot, isStateKnownDeleted, isStatePendingDeleted, latch, latch, latchNoWait, latchNoWait, latchShared, latchShared, log, log, log, logicalEquals, makeFetchErrorMsg, needsSplitting, optionalLog, optionalLogProvisional, postFetchInit, postRecoveryInit, prepareForSlotReuse, printMemorySize, readFromLog, rebuildINList, recalcKeyPrefix, releaseLatch, releaseLatchIfOwner, resetAndGetMemorySize, setDatabase, setDirty, setGeneration, setGeneration, setIdentifierKey, setInListResident, setIsRoot, setKeyPrefix, setLastFullLsn, setLsnElement, setMigrate, setNodeId, setPendingDeleted, setRecalcToggle, shouldUpdateLsn, split, splitInternal, toString, trackProvisionalObsolete, updateEntry, updateEntry, updateEntry, updateMemorySize, updateMemorySize, updateNode, updateNode, updateNode, verify, verifyKeyPrefix, verifyMemorySize, writeToLog

Methods inherited from class com.sleepycat.je.tree.Node

containsDuplicates, dump, getMemorySizeIncludedByParent, getTransactionId, getType, isLN

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.sleepycat.je.log.Loggable

dumpLog, getLogSize, getTransactionId, logicalEquals, readFromLog, writeToLog

Constructor Detail

BIN

public BIN()

BIN

public BIN(DatabaseImpl db,
   byte[] identifierKey,
   int maxEntriesPerNode,
   int level)

BIN

public BIN(SizeofMarker marker)

For Sizeof, set all array fields to null, since they are not part of the fixed overhead.

Method Detail

getVLSN

public long getVLSN(int idx,
           boolean allowFetch)

Returns the VLSN. VLSN.NULL_VLSN.getSequence() (-1) is returned in two cases: 1) This is a standalone environment. 2) The VLSN is not cached (perhaps VLSN caching is not configured), and the allowFetch param is false. WARNING: Because the VLSNCache is only updated when an LN is evicted, it is critical that getVLSN returns the VLSN for a resident LN before getting the VLSN from the cache.

getVLSNCache

public VLSNCache getVLSNCache()

For unit testing.

setTarget

void setTarget(int idx,
             Node target)

Updates the VLSN cache when an LN target is evicted. See VLSNCache.

Overrides:

setTarget in class IN

copyEntry

void copyEntry(int idx,
             IN from,
             int fromIdx)

Overridden to account for VLSNCache entries.

Overrides:

copyEntry in class IN

copyEntries

void copyEntries(int from,
               int to,
               int n)

Overridden to account for VLSNCache entries.

Overrides:

copyEntries in class IN

clearEntry

void clearEntry(int idx)

Overridden to account for VLSNCache entries.

Overrides:

clearEntry in class IN

computeMemorySize

public long computeMemorySize()

Adds VLSNCache size to computed memory size.

Overrides:

computeMemorySize in class IN

createReference

public BINReference createReference()

Create a holder object that encapsulates information about this BIN for the INCompressor.

createNewInstance

protected IN createNewInstance(byte[] identifierKey,
                   int maxEntries,
                   int level)

Create a new BIN. Need this because we can't call newInstance() without getting a 0 for nodeId.

Overrides:

createNewInstance in class IN

isAlwaysLatchedExclusively

boolean isAlwaysLatchedExclusively()

Overrides:

isAlwaysLatchedExclusively in class IN

isBIN

public boolean isBIN()

Overrides:

isBIN in class Node

setLastLoggedLsn

void setLastLoggedLsn(long lsn)

Overrides the IN method to account for deltas. This method relies on setLastFullVersion being called first when a delta is fetched, which is done by BINDelta.reconstituteBIN.

Overrides:

setLastLoggedLsn in class IN

getLastLoggedVersion

public long getLastLoggedVersion()

Overrides the IN method to account for deltas.

Overrides:

getLastLoggedVersion in class IN

getLastDeltaVersion

public long getLastDeltaVersion()

Overrides the IN method to account for deltas. Public for unit testing.

Overrides:

getLastDeltaVersion in class IN

setProhibitNextDelta

public void setProhibitNextDelta()

If cleaned or compressed, must log full version.

Overrides:

setProhibitNextDelta in class IN

isEvictionProhibited

protected boolean isEvictionProhibited()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

isEvictionProhibited in class IN

hasPinnedChildren

boolean hasPinnedChildren()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

hasPinnedChildren in class IN

getChildEvictionType

int getChildEvictionType()

Note that the IN may or may not be latched when this method is called. Returning the wrong answer is OK in that case (it will be called again later when latched), but an exception should not occur.

Overrides:

getChildEvictionType in class IN

entryZeroKeyComparesLow

boolean entryZeroKeyComparesLow()

Indicates whether entry 0's key is "special" in that it always compares less than any other key. BIN's don't have the special key, but IN's do.

Overrides:

entryZeroKeyComparesLow in class IN

setKnownDeleted

public void setKnownDeleted(int index)

Mark this entry as deleted, using the delete flag. Only BINS may do this.

Overrides:

setKnownDeleted in class IN

Parameters:

index - indicates target entry

setKnownDeletedClearAll

public void setKnownDeletedClearAll(int index)

clearKnownDeleted

public void clearKnownDeleted(int index)

Clear the known deleted flag. Only BINS may do this.

Overrides:

clearKnownDeleted in class IN

Parameters:

index - indicates target entry

getFixedMemoryOverhead

protected long getFixedMemoryOverhead()

Overrides:

getFixedMemoryOverhead in class IN

getTreeAdminMemorySize

public long getTreeAdminMemorySize()

Returns the treeAdmin memory in objects referenced by this BIN. Specifically, this refers to the DbFileSummaryMap held by MapLNs

Overrides:

getTreeAdminMemorySize in class IN

getCursorSet

public java.util.Set<CursorImpl> getCursorSet()

addCursor

public void addCursor(CursorImpl cursor)

Register a cursor with this BIN. Caller has this BIN already latched.

Parameters:

cursor - Cursor to register.

removeCursor

public void removeCursor(CursorImpl cursor)

Unregister a cursor with this bin. Caller has this BIN already latched.

Parameters:

cursor - Cursor to unregister.

nCursors

public int nCursors()

Returns:

the number of cursors currently referring to this BIN.

splitSpecial

void splitSpecial(IN parent,
                int parentIndex,
                int maxEntriesPerNode,
                byte[] key,
                boolean leftSide,
                CacheMode cacheMode)
            throws DatabaseException

Called when we know we are about to split on behalf of a key that is the minimum (leftSide) or maximum (!leftSide) of this node. This is achieved by just forcing the split to occur either one element in from the left or the right (i.e. splitIndex is 1 or nEntries - 1).

Overrides:

splitSpecial in class IN

Throws:

DatabaseException

adjustCursors

void adjustCursors(IN newSibling,
                 int newSiblingLow,
                 int newSiblingHigh)

Adjust any cursors that are referring to this BIN. This method is called during a split operation. "this" is the BIN being split. newSibling is the new BIN into which the entries from "this" between newSiblingLow and newSiblingHigh have been copied.

Overrides:

adjustCursors in class IN

Parameters:

newSibling - - the newSibling into which "this" has been split.

newSiblingLow -

newSiblingHigh - - the low and high entry of "this" that were moved into newSibling.

verifyCursors

public void verifyCursors()

For each cursor in this BIN's cursor set, ensure that the cursor is actually referring to this BIN.

adjustCursorsForInsert

void adjustCursorsForInsert(int insertIndex)

Adjust cursors referring to this BIN following an insert.

Overrides:

adjustCursorsForInsert in class IN

Parameters:

insertIndex - - The index of the new entry.

compress

public boolean compress(LocalUtilizationTracker localTracker)
                 throws DatabaseException

Compress this BIN by removing any entries that are deleted. No cursors may be present on the BIN. Caller is responsible for latching and unlatching this node.

Parameters:

localTracker - is used only for temporary DBs, and may be specified to consolidate multiple tracking operations. If null, the tracking is performed immediately in this method.

Returns:

true if all deleted slots were compressed, or false if one or more slots could not be compressed because we were unable to obtain a lock.

Throws:

DatabaseException

queueSlotDeletion

public void queueSlotDeletion()

This method is called whenever a deleted slot is observed (when the slot's PendingDeleted or KnownDeleted flag is set), to ensure that the slot is compressed away. This is an attempt to process slots that were not compressed during the mainstream record deletion process because of cursors on the BIN during compress, or a crash prior to compression.

isCompressible

public boolean isCompressible()

Overrides:

isCompressible in class Node

evictLNs

public long evictLNs()
              throws DatabaseException

Reduce memory consumption by evicting all LN targets. Note that this may cause LNs to be logged, which would require marking this BIN dirty. The BIN should be latched by the caller.

Returns:

number of evicted bytes. Note that a 0 return does not necessarily mean that the BIN had no evictable LNs. It's possible that resident, dirty LNs were not lockable.

Throws:

DatabaseException

evictLN

public void evictLN(int index)
             throws DatabaseException

Evict a single LN if allowed and adjust the memory budget.

Throws:

DatabaseException

validateSubtreeBeforeDelete

boolean validateSubtreeBeforeDelete(int index)

Overrides:

validateSubtreeBeforeDelete in class IN

isValidForDelete

boolean isValidForDelete()
                   throws DatabaseException

Check if this node fits the qualifications for being part of a deletable subtree. It may not have any LN children. We assume that this is only called under an assert.

Overrides:

isValidForDelete in class IN

Returns:

true if you're part of a deletable subtree.

Throws:

DatabaseException

accumulateStats

void accumulateStats(TreeWalkerStatsAccumulator acc)

Overrides:

accumulateStats in class IN

beginTag

public java.lang.String beginTag()

Overrides:

beginTag in class IN

endTag

public java.lang.String endTag()

Overrides:

endTag in class IN

logDirtyChildren

public void logDirtyChildren()
                      throws DatabaseException

Description copied from class: IN

When splits and checkpoints intermingle in a deferred write databases, a checkpoint target may appear which has a valid target but a null LSN. Deferred write dbs are written out in checkpoint style by either Database.sync() or a checkpoint which has cleaned a file containing deferred write entries. For example, INa | BINb A checkpoint or Database.sync starts The INList is traversed, dirty nodes are selected BINb is bypassed on the INList, since it's not dirty BINb is split, creating a new sibling, BINc, and dirtying INa INa is selected as a dirty node for the ckpt If this happens, INa is in the selected dirty set, but not its dirty child BINb and new child BINc. In a durable db, the existence of BINb and BINc are logged anyway. But in a deferred write db, there is an entry that points to BINc, but no logged version. This will not cause problems with eviction, because INa can't be evicted until BINb and BINc are logged, are non-dirty, and are detached. But it can cause problems at recovery, because INa will have a null LSN for a valid entry, and the LN children of BINc will not find a home. To prevent this, search for all dirty children that might have been missed during the selection phase, and write them out. It's not sufficient to write only null-LSN children, because the existing sibling must be logged lest LN children recover twice (once in the new sibling, once in the old existing sibling.

Overrides:

logDirtyChildren in class IN

Throws:

DatabaseException

See Also:

IN.logDirtyChildren()

incEvictStats

public void incEvictStats(Evictor.EvictionSource source)

Description copied from class: IN

We categorize eviction stats by the type of IN, so IN subclasses update different stats.

Overrides:

incEvictStats in class IN

See Also:

IN.incEvictStats(com.sleepycat.je.evictor.Evictor.EvictionSource)

incFetchStats

public void incFetchStats(EnvironmentImpl envImpl,
                 boolean isMiss)

Description copied from class: Node

We categorize fetch stats by the type of node, so node subclasses update different stats.

Overrides:

incFetchStats in class IN

See Also:

Node.incFetchStats(com.sleepycat.je.dbi.EnvironmentImpl, boolean)

getLogType

public LogEntryType getLogType()

Description copied from class: IN

Get the log type of this node.

Overrides:

getLogType in class IN

See Also:

IN.getLogType()

shortClassName

public java.lang.String shortClassName()

Overrides:

shortClassName in class IN

beforeLog

public void beforeLog(LogManager logManager,
             INLogItem item,
             INLogContext context)

Overrides the IN method to account for deltas.

Overrides:

beforeLog in class IN

afterLog

public void afterLog(LogManager logManager,
            INLogItem item,
            INLogContext context)

Overrides the IN method to account for deltas. See beforeLog.

Overrides:

afterLog in class IN

shouldLogDelta

public boolean shouldLogDelta()

Decide whether to log a full or partial BIN, depending on the ratio of the delta size to full BIN size, and the number of deltas that have been logged since the last full. Other factors are taken into account: + a delta cannot be logged if the BIN has never been logged before + deltas are not currently supported for DeferredWrite databases + this particular delta may have been prohibited because the cleaner is migrating the BIN or a slot has been deleted + if there are no dirty slots, we might as well log a full BIN

Returns:

true if we should log the deltas of this BIN

fetchTarget

public Node fetchTarget(int idx)
                 throws DatabaseException

We require exclusive latches on a BIN, so this method does not need to declare that it throws RelatchRequiredException.

Overrides:

fetchTarget in class IN

Returns:

the target node or null.

Throws:

DatabaseException