com.sleepycat.je.tree
Class BIN

java.lang.Object
  extended by com.sleepycat.je.tree.Node
      extended by com.sleepycat.je.tree.IN
          extended by com.sleepycat.je.tree.BIN
All Implemented Interfaces:
Loggable, 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
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
(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.
 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.
 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.
 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.
 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 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 String beginTag()
Overrides:
beginTag in class IN

endTag

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


Copyright (c) 2004-2012 Oracle. All rights reserved.