Package org.apache.hadoop.hbase.util

Class BloomFilterChunk

java.lang.Object

org.apache.hadoop.hbase.util.BloomFilterChunk

All Implemented Interfaces:

BloomFilterBase

@Private
public class BloomFilterChunk
extends Object
implements BloomFilterBase

The basic building block for the CompoundBloomFilter

Field Summary

Fields

Modifier and Type	Field	Description
protected ByteBuffer	bloom	Bloom bits
protected BloomType	bloomType	The type of bloom
protected long	byteSize	Bytes (B) in the array.
protected final Hash	hash	Hash Function
protected int	hashCount	Number of hash functions
protected final int	hashType	Hash type
protected int	keyCount	Keys currently in the bloom
protected int	maxKeys	Max Keys expected for the bloom

Constructor Summary

Constructors

Constructor	Description
BloomFilterChunk(int maxKeys, double errorRate, int hashType, int foldFactor)	Determines & initializes bloom filter meta data from user config.
BloomFilterChunk(int hashType, BloomType bloomType)
BloomFilterChunk(DataInput meta)	Loads bloom filter meta data from file input.

Method Summary

Modifier and Type	Method	Description
double	actualErrorRate()	Computes the error rate for this Bloom filter, taking into account the actual number of hash functions and keys inserted.
(package private) void	add(byte[] buf, int offset, int len)
void	add(Cell cell)
void	allocBloom()
(package private) void	bloomCheck(ByteBuffer bloom)
void	compactBloom()
BloomFilterChunk	createAnother()	Creates another similar Bloom filter.
(package private) static boolean	get(int pos, ByteBuffer bloomBuf, int bloomOffset)	Check if bit at specified index is 1.
long	getByteSize()	Returns Size of the bloom, in bytes
int	getHashCount()
int	getHashType()
long	getKeyCount()	Returns The number of keys added to the bloom
long	getMaxKeys()	Returns The max number of keys that can be inserted to maintain the desired error rate
(package private) void	sanityCheck()
(package private) void	set(long pos)	Set the bit at the specified index to 1.
private void	setHashLoc(int hash1, int hash2)
String	toString()
void	writeBloom(DataOutput out)	Writes just the bloom filter to the output array

Methods inherited from class java.lang.Object

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

Field Details

byteSize

protected long byteSize

Bytes (B) in the array. This actually has to fit into an int.

hashCount

protected int hashCount

Number of hash functions

hashType

protected final int hashType

Hash type

hash

protected final Hash hash

Hash Function

keyCount

protected int keyCount

Keys currently in the bloom

maxKeys

protected int maxKeys

Max Keys expected for the bloom

bloom

protected ByteBuffer bloom

Bloom bits

bloomType

protected BloomType bloomType

The type of bloom

Constructor Details

BloomFilterChunk

public BloomFilterChunk(DataInput meta)
                 throws IOException,
IllegalArgumentException

Loads bloom filter meta data from file input.

Parameters:

meta - stored bloom meta data

Throws:

IllegalArgumentException - meta data is invalid

IOException

BloomFilterChunk

public BloomFilterChunk(int hashType,
 BloomType bloomType)

BloomFilterChunk

public BloomFilterChunk(int maxKeys,
 double errorRate,
 int hashType,
 int foldFactor)
                 throws IllegalArgumentException

Determines & initializes bloom filter meta data from user config. Call allocBloom() to allocate bloom filter data.

Parameters:

maxKeys - Maximum expected number of keys that will be stored in this bloom

errorRate - Desired false positive error rate. Lower rate = more storage required

hashType - Type of hash function to use

foldFactor - When finished adding entries, you may be able to 'fold' this bloom to save space. Tradeoff potentially excess bytes in bloom for ability to fold if keyCount is exponentially greater than maxKeys.

Throws:

IllegalArgumentException

Method Details

actualErrorRate

public double actualErrorRate()

Computes the error rate for this Bloom filter, taking into account the actual number of hash functions and keys inserted. The return value of this function changes as a Bloom filter is being populated. Used for reporting the actual error rate of compound Bloom filters when writing them out.

Returns:

error rate for this particular Bloom filter

createAnother

public BloomFilterChunk createAnother()

Creates another similar Bloom filter. Does not copy the actual bits, and sets the new filter's key count to zero.

Returns:

a Bloom filter with the same configuration as this

allocBloom

public void allocBloom()

sanityCheck

void sanityCheck()
          throws IllegalArgumentException

Throws:

IllegalArgumentException

bloomCheck

void bloomCheck(ByteBuffer bloom)
         throws IllegalArgumentException

Throws:

IllegalArgumentException

add

void add(byte[] buf,
 int offset,
 int len)

add

public void add(Cell cell)

setHashLoc

private void setHashLoc(int hash1,
 int hash2)

set

void set(long pos)

Set the bit at the specified index to 1.

Parameters:

pos - index of bit

get

static boolean get(int pos,
 ByteBuffer bloomBuf,
 int bloomOffset)

Check if bit at specified index is 1.

Parameters:

pos - index of bit

Returns:

true if bit at specified index is 1, false if 0.

getKeyCount

public long getKeyCount()

Description copied from interface: BloomFilterBase

Returns The number of keys added to the bloom

Specified by:

getKeyCount in interface BloomFilterBase

getMaxKeys

public long getMaxKeys()

Description copied from interface: BloomFilterBase

Returns The max number of keys that can be inserted to maintain the desired error rate

Specified by:

getMaxKeys in interface BloomFilterBase

getByteSize

public long getByteSize()

Description copied from interface: BloomFilterBase

Returns Size of the bloom, in bytes

Specified by:

getByteSize in interface BloomFilterBase

getHashType

public int getHashType()

compactBloom

public void compactBloom()

writeBloom

public void writeBloom(DataOutput out)
                throws IOException

Writes just the bloom filter to the output array

Parameters:

out - OutputStream to place bloom

Throws:

IOException - Error writing bloom array

getHashCount

public int getHashCount()

toString

public String toString()

Overrides:

toString in class Object