org.apache.hadoop.hbase.util

Class BloomFilterUtil

java.lang.Object

org.apache.hadoop.hbase.util.BloomFilterUtil

@InterfaceAudience.Private
public final class BloomFilterUtil
extends Object

Utility methods related to BloomFilters

Field Summary

Fields

Modifier and Type	Field and Description
static byte[]	bitvals Bit-value lookup array to prevent doing the same work over and over
static double	LOG2_SQUARED Used in computing the optimal Bloom filter size.
private static Random	randomGeneratorForTest A random number generator to use for "fake lookups" when testing to estimate the ideal false positive rate.
static String	STATS_RECORD_SEP Record separator for the Bloom filter statistics human-readable string

Constructor Summary

Constructors

Modifier	Constructor and Description
private	BloomFilterUtil() Private constructor to keep this class from being instantiated.

Method Summary

Modifier and Type	Method and Description
static double	actualErrorRate(long maxKeys, long bitSize, int functionCount) Computes the actual error rate for the given number of elements, number of bits, and number of hash functions.
(package private) static boolean	checkBit(int pos, ByteBuff bloomBuf, int bloomOffset) Check if bit at specified index is 1.
static long	computeBitSize(long maxKeys, double errorRate)
static int	computeFoldableByteSize(long bitSize, int foldFactor) Increases the given byte size of a Bloom filter until it can be folded by the given factor.
static long	computeMaxKeys(long bitSize, double errorRate, int hashCount) The maximum number of keys we can put into a Bloom filter of a certain size to get the given error rate, with the given number of hash functions.
static boolean	contains(byte[] buf, int offset, int length, ByteBuff bloomBuf, int bloomOffset, int bloomSize, Hash hash, int hashCount)
private static <T> boolean	contains(ByteBuff bloomBuf, int bloomOffset, int bloomSize, Hash hash, int hashCount, HashKey<T> hashKey)
static boolean	contains(Cell cell, ByteBuff bloomBuf, int bloomOffset, int bloomSize, Hash hash, int hashCount, BloomType type)
static BloomFilterChunk	createBySize(int byteSizeHint, double errorRate, int hashType, int foldFactor, BloomType bloomType) Creates a Bloom filter chunk of the given size.
static String	formatStats(BloomFilterBase bloomFilter) A human-readable string with statistics for the given Bloom filter.
static long	idealMaxKeys(long bitSize, double errorRate) The maximum number of keys we can put into a Bloom filter of a certain size to maintain the given error rate, assuming the number of hash functions is chosen optimally and does not even have to be an integer (hence the "ideal" in the function name).
static int	optimalFunctionCount(int maxKeys, long bitSize)
static void	setFakeLookupMode(boolean enabled)
static String	toString(BloomFilterChunk bloomFilter)

Methods inherited from class java.lang.Object

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

Field Detail

STATS_RECORD_SEP

public static final String STATS_RECORD_SEP

Record separator for the Bloom filter statistics human-readable string

See Also:

Constant Field Values

LOG2_SQUARED

public static final double LOG2_SQUARED

Used in computing the optimal Bloom filter size. This approximately equals 0.480453.

randomGeneratorForTest

private static Random randomGeneratorForTest

A random number generator to use for "fake lookups" when testing to estimate the ideal false positive rate.

bitvals

public static final byte[] bitvals

Bit-value lookup array to prevent doing the same work over and over

Constructor Detail

BloomFilterUtil

private BloomFilterUtil()

Private constructor to keep this class from being instantiated.

Method Detail

computeBitSize

public static long computeBitSize(long maxKeys,
                                  double errorRate)

Parameters:

maxKeys -

errorRate -

Returns:

the number of bits for a Bloom filter than can hold the given number of keys and provide the given error rate, assuming that the optimal number of hash functions is used and it does not have to be an integer.

setFakeLookupMode

public static void setFakeLookupMode(boolean enabled)

idealMaxKeys

public static long idealMaxKeys(long bitSize,
                                double errorRate)

The maximum number of keys we can put into a Bloom filter of a certain size to maintain the given error rate, assuming the number of hash functions is chosen optimally and does not even have to be an integer (hence the "ideal" in the function name).

Parameters:

bitSize -

errorRate -

Returns:

maximum number of keys that can be inserted into the Bloom filter

See Also:

for a more precise estimate

computeMaxKeys

public static long computeMaxKeys(long bitSize,
                                  double errorRate,
                                  int hashCount)

The maximum number of keys we can put into a Bloom filter of a certain size to get the given error rate, with the given number of hash functions.

Parameters:

bitSize -

errorRate -

hashCount -

Returns:

the maximum number of keys that can be inserted in a Bloom filter to maintain the target error rate, if the number of hash functions is provided.

actualErrorRate

public static double actualErrorRate(long maxKeys,
                                     long bitSize,
                                     int functionCount)

Computes the actual error rate for the given number of elements, number of bits, and number of hash functions. Taken directly from the Wikipedia Bloom filter article.

Parameters:

maxKeys -

bitSize -

functionCount -

Returns:

the actual error rate

computeFoldableByteSize

public static int computeFoldableByteSize(long bitSize,
                                          int foldFactor)

Increases the given byte size of a Bloom filter until it can be folded by the given factor.

Parameters:

bitSize -

foldFactor -

Returns:

Foldable byte size

optimalFunctionCount

public static int optimalFunctionCount(int maxKeys,
                                       long bitSize)

createBySize

public static BloomFilterChunk createBySize(int byteSizeHint,
                                            double errorRate,
                                            int hashType,
                                            int foldFactor,
                                            BloomType bloomType)

Creates a Bloom filter chunk of the given size.

Parameters:

byteSizeHint - the desired number of bytes for the Bloom filter bit array. Will be increased so that folding is possible.

errorRate - target false positive rate of the Bloom filter

hashType - Bloom filter hash function type

foldFactor -

bloomType -

Returns:

the new Bloom filter of the desired size

contains

public static boolean contains(byte[] buf,
                               int offset,
                               int length,
                               ByteBuff bloomBuf,
                               int bloomOffset,
                               int bloomSize,
                               Hash hash,
                               int hashCount)

contains

private static <T> boolean contains(ByteBuff bloomBuf,
                                    int bloomOffset,
                                    int bloomSize,
                                    Hash hash,
                                    int hashCount,
                                    HashKey<T> hashKey)

contains

public static boolean contains(Cell cell,
                               ByteBuff bloomBuf,
                               int bloomOffset,
                               int bloomSize,
                               Hash hash,
                               int hashCount,
                               BloomType type)

checkBit

static boolean checkBit(int pos,
                        ByteBuff 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.

formatStats

public static String formatStats(BloomFilterBase bloomFilter)

A human-readable string with statistics for the given Bloom filter.

Parameters:

bloomFilter - the Bloom filter to output statistics for;

Returns:

a string consisting of "<key>: <value>" parts separated by STATS_RECORD_SEP.

toString

public static String toString(BloomFilterChunk bloomFilter)