org.apache.hadoop.hbase.io.hfile

Class HFileBlockIndex.BlockIndexReader

java.lang.Object

org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexReader

All Implemented Interfaces:

HeapSize

Direct Known Subclasses:

HFileBlockIndex.ByteArrayKeyBlockIndexReader, HFileBlockIndex.CellBasedKeyBlockIndexReader

Enclosing class:

HFileBlockIndex

abstract static class HFileBlockIndex.BlockIndexReader
extends Object
implements HeapSize

The reader will always hold the root level index in the memory. Index blocks at all other levels will be cached in the LRU cache in practice, although this API does not enforce that.

All non-root (leaf and intermediate) index blocks contain what we call a "secondary index": an array of offsets to the entries within the block. This allows us to do binary search for the entry corresponding to the given key without having to deserialize the block.

Field Summary

Fields

Modifier and Type	Field and Description
protected int[]	blockDataSizes
protected long[]	blockOffsets
protected int	midKeyEntry
protected long	midLeafBlockOffset
protected int	midLeafBlockOnDiskSize
protected int	rootCount
protected int	searchTreeLevel The number of levels in the block index tree.

Constructor Summary

Constructors

Constructor and Description
BlockIndexReader()

Method Summary

Modifier and Type	Method and Description
protected abstract void	add(byte[] key, long offset, int dataSize)
(package private) static int	binarySearchNonRootIndex(Cell key, ByteBuff nonRootIndex, CellComparator comparator) Performs a binary search over a non-root level index block.
protected abstract long	calculateHeapSizeForBlockKeys(long heapSize)
void	ensureNonEmpty() Verifies that the block index is non-empty and throws an IllegalStateException otherwise.
protected byte[]	getNonRootIndexedKey(ByteBuff nonRootIndex, int i) The indexed key at the ith position in the nonRootIndex.
int	getRootBlockCount()
int	getRootBlockDataSize(int i)
long	getRootBlockOffset(int i)
long	heapSize()
protected abstract void	initialize(int numEntries)
abstract boolean	isEmpty()
abstract BlockWithScanInfo	loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other scan info such as the key that starts the next HFileBlock.
(package private) static int	locateNonRootIndexEntry(ByteBuff nonRootBlock, Cell key, CellComparator comparator) Search for one key using the secondary index in a non-root block.
abstract Cell	midkey(HFile.CachingBlockReader cachingBlockReader) An approximation to the HFile's mid-key.
void	readMultiLevelIndexRoot(HFileBlock blk, int numEntries) Read the root-level metadata of a multi-level block index.
void	readRootIndex(DataInput in, int numEntries) Read in the root-level index from the given input stream.
DataInputStream	readRootIndex(HFileBlock blk, int numEntries) Read in the root-level index from the given input stream.
int	rootBlockContainingKey(byte[] key, int offset, int length) Finds the root-level index block containing the given key.
abstract int	rootBlockContainingKey(byte[] key, int offset, int length, CellComparator comp) Finds the root-level index block containing the given key.
abstract int	rootBlockContainingKey(Cell key) Finds the root-level index block containing the given key.
HFileBlock	seekToDataBlock(Cell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding, HFile.CachingBlockReader cachingBlockReader) Return the data block which contains this key.

Methods inherited from class java.lang.Object

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

Field Detail

blockOffsets

protected long[] blockOffsets

blockDataSizes

protected int[] blockDataSizes

rootCount

protected int rootCount

midLeafBlockOffset

protected long midLeafBlockOffset

midLeafBlockOnDiskSize

protected int midLeafBlockOnDiskSize

midKeyEntry

protected int midKeyEntry

searchTreeLevel

protected int searchTreeLevel

The number of levels in the block index tree. One if there is only root level, two for root and leaf levels, etc.

Constructor Detail

BlockIndexReader

BlockIndexReader()

Method Detail

isEmpty

public abstract boolean isEmpty()

Returns:

true if the block index is empty.

ensureNonEmpty

public void ensureNonEmpty()

Verifies that the block index is non-empty and throws an IllegalStateException otherwise.

seekToDataBlock

public HFileBlock seekToDataBlock(Cell key,
                                  HFileBlock currentBlock,
                                  boolean cacheBlocks,
                                  boolean pread,
                                  boolean isCompaction,
                                  DataBlockEncoding expectedDataBlockEncoding,
                                  HFile.CachingBlockReader cachingBlockReader)
                           throws IOException

Return the data block which contains this key. This function will only be called when the HFile version is larger than 1.

Parameters:

key - the key we are looking for

currentBlock - the current block, to avoid re-reading the same block

cacheBlocks -

pread -

isCompaction -

expectedDataBlockEncoding - the data block encoding the caller is expecting the data block to be in, or null to not perform this check and return the block irrespective of the encoding

Returns:

reader a basic way to load blocks

Throws:

IOException

loadDataBlockWithScanInfo

public abstract BlockWithScanInfo loadDataBlockWithScanInfo(Cell key,
                                                            HFileBlock currentBlock,
                                                            boolean cacheBlocks,
                                                            boolean pread,
                                                            boolean isCompaction,
                                                            DataBlockEncoding expectedDataBlockEncoding,
                                                            HFile.CachingBlockReader cachingBlockReader)
                                                     throws IOException

Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other scan info such as the key that starts the next HFileBlock. This function will only be called when the HFile version is larger than 1.

Parameters:

key - the key we are looking for

currentBlock - the current block, to avoid re-reading the same block

expectedDataBlockEncoding - the data block encoding the caller is expecting the data block to be in, or null to not perform this check and return the block irrespective of the encoding.

Returns:

the BlockWithScanInfo which contains the DataBlock with other scan info such as nextIndexedKey.

Throws:

IOException

midkey

public abstract Cell midkey(HFile.CachingBlockReader cachingBlockReader)
                     throws IOException

An approximation to the HFile's mid-key. Operates on block boundaries, and does not go inside blocks. In other words, returns the first key of the middle block of the file.

Returns:

the first key of the middle block

Throws:

IOException

getRootBlockOffset

public long getRootBlockOffset(int i)

Parameters:

i - from 0 to - 1

getRootBlockDataSize

public int getRootBlockDataSize(int i)

Parameters:

i - zero-based index of a root-level block

Returns:

the on-disk size of the root-level block for version 2, or the uncompressed size for version 1

getRootBlockCount

public int getRootBlockCount()

Returns:

the number of root-level blocks in this block index

rootBlockContainingKey

public abstract int rootBlockContainingKey(byte[] key,
                                           int offset,
                                           int length,
                                           CellComparator comp)

Finds the root-level index block containing the given key.

Parameters:

key - Key to find

comp - the comparator to be used

Returns:

Offset of block containing key (between 0 and the number of blocks - 1) or -1 if this file does not contain the request.

rootBlockContainingKey

public int rootBlockContainingKey(byte[] key,
                                  int offset,
                                  int length)

Finds the root-level index block containing the given key.

Parameters:

key - Key to find

Returns:

Offset of block containing key (between 0 and the number of blocks - 1) or -1 if this file does not contain the request.

rootBlockContainingKey

public abstract int rootBlockContainingKey(Cell key)

Finds the root-level index block containing the given key.

Parameters:

key - Key to find

getNonRootIndexedKey

protected byte[] getNonRootIndexedKey(ByteBuff nonRootIndex,
                                      int i)

The indexed key at the ith position in the nonRootIndex. The position starts at 0.

Parameters:

nonRootIndex -

i - the ith position

Returns:

The indexed key at the ith position in the nonRootIndex.

binarySearchNonRootIndex

static int binarySearchNonRootIndex(Cell key,
                                    ByteBuff nonRootIndex,
                                    CellComparator comparator)

Performs a binary search over a non-root level index block. Utilizes the secondary index, which records the offsets of (offset, onDiskSize, firstKey) tuples of all entries.

Parameters:

key - the key we are searching for offsets to individual entries in the blockIndex buffer

nonRootIndex - the non-root index block buffer, starting with the secondary index. The position is ignored.

Returns:

the index i in [0, numEntries - 1] such that keys[i] <= key < keys[i + 1], if keys is the array of all keys being searched, or -1 otherwise

Throws:

IOException

locateNonRootIndexEntry

static int locateNonRootIndexEntry(ByteBuff nonRootBlock,
                                   Cell key,
                                   CellComparator comparator)

Search for one key using the secondary index in a non-root block. In case of success, positions the provided buffer at the entry of interest, where the file offset and the on-disk-size can be read.

Parameters:

nonRootBlock - a non-root block without header. Initial position does not matter.

key - the byte array containing the key

Returns:

the index position where the given key was found, otherwise return -1 in the case the given key is before the first key.

readRootIndex

public void readRootIndex(DataInput in,
                          int numEntries)
                   throws IOException

Read in the root-level index from the given input stream. Must match what was written into the root level by HFileBlockIndex.BlockIndexWriter.writeIndexBlocks(FSDataOutputStream) at the offset that function returned.

Parameters:

in - the buffered input stream or wrapped byte input stream

numEntries - the number of root-level index entries

Throws:

IOException

initialize

protected abstract void initialize(int numEntries)

add

protected abstract void add(byte[] key,
                            long offset,
                            int dataSize)

readRootIndex

public DataInputStream readRootIndex(HFileBlock blk,
                                     int numEntries)
                              throws IOException

Read in the root-level index from the given input stream. Must match what was written into the root level by HFileBlockIndex.BlockIndexWriter.writeIndexBlocks(FSDataOutputStream) at the offset that function returned.

Parameters:

blk - the HFile block

numEntries - the number of root-level index entries

Returns:

the buffered input stream or wrapped byte input stream

Throws:

IOException

readMultiLevelIndexRoot

public void readMultiLevelIndexRoot(HFileBlock blk,
                                    int numEntries)
                             throws IOException

Read the root-level metadata of a multi-level block index. Based on readRootIndex(DataInput, int), but also reads metadata necessary to compute the mid-key in a multi-level index.

Parameters:

blk - the HFile block

numEntries - the number of root-level index entries

Throws:

IOException

heapSize

public long heapSize()

Specified by:

heapSize in interface HeapSize

Returns:

Approximate 'exclusive deep size' of implementing object. Includes count of payload and hosting object sizings.

calculateHeapSizeForBlockKeys

protected abstract long calculateHeapSizeForBlockKeys(long heapSize)