alluxio.client.file.cache.cuckoofilter

Class ConcurrentClockCuckooFilter<T>

java.lang.Object

alluxio.client.file.cache.cuckoofilter.ConcurrentClockCuckooFilter<T>

Type Parameters:

T - the type of item

All Implemented Interfaces:

ClockCuckooFilter<T>, Serializable

public class ConcurrentClockCuckooFilter<T>
extends Object
implements ClockCuckooFilter<T>, Serializable

A concurrent cuckoo filter with three customized field: clock, size and scope.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_FPP
static double	DEFAULT_LOAD_FACTOR
static int	TAGS_PER_BUCKET

Method Summary

Modifier and Type	Method and Description
void	aging() A thread-safe method to check aging progress of each segment.
long	approximateElementCount()
long	approximateElementCount(CacheScope scopeInfo)
long	approximateElementSize()
long	approximateElementSize(CacheScope scopeInfo)
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerSize, int bitsPerScope) Create a concurrent cuckoo filter with specified parameters.
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerScope, int prefixBits, int suffixBits, SlidingWindowType slidingWindowType, long windowSize, double fpp, double loadFactor, com.google.common.hash.HashFunction hasher) Create a concurrent cuckoo filter with size encoder.
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerSize, int bitsPerScope, SlidingWindowType slidingWindowType, long windowSize) Create a concurrent cuckoo filter with specified parameters.
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerSize, int bitsPerScope, SlidingWindowType slidingWindowType, long windowSize, double fpp) Create a concurrent cuckoo filter with specified parameters.
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerSize, int bitsPerScope, SlidingWindowType slidingWindowType, long windowSize, double fpp, double loadFactor) Create a concurrent cuckoo filter with specified parameters.
static <T> ConcurrentClockCuckooFilter<T>	create(com.google.common.hash.Funnel<? super T> funnel, long expectedInsertions, int bitsPerClock, int bitsPerSize, int bitsPerScope, SlidingWindowType slidingWindowType, long windowSize, double fpp, double loadFactor, com.google.common.hash.HashFunction hasher) Create a concurrent cuckoo filter with specified parameters.
boolean	delete(T item) Delete an item from cuckoo filter.
double	expectedFpp()
int	getAge(T item) Get the item's clock value (age).
int	getBitsPerClock()
int	getBitsPerScope()
int	getBitsPerSize()
int	getBitsPerTag()
int	getNumBuckets()
String	getSummary()
int	getTagsPerBucket()
void	increaseOperationCount(int count) By calling this method, cuckoo filter is informed of the number of entries have passed.
boolean	mightContain(T item) Check whether an item is in cuckoo filter or not.
boolean	mightContainAndResetClock(T item) Check whether an item is in cuckoo filter (and reset its clock to MAX) or not.
boolean	put(T item, int size, CacheScope scopeInfo) Insert an item into cuckoo filter.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_FPP

public static final double DEFAULT_FPP

See Also:

Constant Field Values

DEFAULT_LOAD_FACTOR

public static final double DEFAULT_LOAD_FACTOR

See Also:

Constant Field Values

TAGS_PER_BUCKET

public static final int TAGS_PER_BUCKET

See Also:

Constant Field Values

Method Detail

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerSize,
                                                        int bitsPerScope,
                                                        SlidingWindowType slidingWindowType,
                                                        long windowSize,
                                                        double fpp,
                                                        double loadFactor,
                                                        com.google.common.hash.HashFunction hasher)

Create a concurrent cuckoo filter with specified parameters.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed cuckoo filter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerSize - the number of bits the size field has

bitsPerScope - the number of bits the scope field has

slidingWindowType - the type of sliding window

windowSize - the size of the sliding window

fpp - the desired false positive probability (must be positive and less than 1.0)

loadFactor - the load factor of cuckoo filter (must be positive and less than 1.0)

hasher - the hash function to be used

Returns:

a ConcurrentClockCuckooFilter

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerScope,
                                                        int prefixBits,
                                                        int suffixBits,
                                                        SlidingWindowType slidingWindowType,
                                                        long windowSize,
                                                        double fpp,
                                                        double loadFactor,
                                                        com.google.common.hash.HashFunction hasher)

Create a concurrent cuckoo filter with size encoder.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed cuckoo filter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerScope - the number of bits the scope field has

prefixBits - the prefix bits number of the size field

suffixBits - the suffix bits number of the size field

slidingWindowType - the type of sliding window

windowSize - the size of the sliding window

fpp - the desired false positive probability (must be positive and less than 1.0)

loadFactor - the load factor of cuckoo filter (must be positive and less than 1.0)

hasher - the hash function to be used

Returns:

a ConcurrentClockCuckooFilter

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerSize,
                                                        int bitsPerScope,
                                                        SlidingWindowType slidingWindowType,
                                                        long windowSize,
                                                        double fpp,
                                                        double loadFactor)

Create a concurrent cuckoo filter with specified parameters.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed BloomFilter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerSize - the number of bits the size field has

bitsPerScope - the number of bits the scope field has

slidingWindowType - the type of sliding window

windowSize - the size of the sliding window

fpp - the desired false positive probability (must be positive and less than 1.0)

loadFactor - the load factor of cuckoo filter (must be positive and less than 1.0)

Returns:

a ConcurrentClockCuckooFilter

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerSize,
                                                        int bitsPerScope,
                                                        SlidingWindowType slidingWindowType,
                                                        long windowSize,
                                                        double fpp)

Create a concurrent cuckoo filter with specified parameters.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed BloomFilter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerSize - the number of bits the size field has

bitsPerScope - the number of bits the scope field has

slidingWindowType - the type of sliding window

windowSize - the size of the sliding window

fpp - the desired false positive probability (must be positive and less than 1.0)

Returns:

a ConcurrentClockCuckooFilter

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerSize,
                                                        int bitsPerScope,
                                                        SlidingWindowType slidingWindowType,
                                                        long windowSize)

Create a concurrent cuckoo filter with specified parameters.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed BloomFilter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerSize - the number of bits the size field has

bitsPerScope - the number of bits the scope field has

slidingWindowType - the type of sliding window

windowSize - the size of the sliding window

Returns:

a ConcurrentClockCuckooFilter

create

public static <T> ConcurrentClockCuckooFilter<T> create(com.google.common.hash.Funnel<? super T> funnel,
                                                        long expectedInsertions,
                                                        int bitsPerClock,
                                                        int bitsPerSize,
                                                        int bitsPerScope)

Create a concurrent cuckoo filter with specified parameters.

Type Parameters:

T - the type of item

Parameters:

funnel - the funnel of T's that the constructed BloomFilter will use

expectedInsertions - the number of expected insertions to the constructed ConcurrentClockCuckooFilter; must be positive; must be a power of 2

bitsPerClock - the number of bits the clock field has

bitsPerSize - the number of bits the size field has

bitsPerScope - the number of bits the scope field has

Returns:

a ConcurrentClockCuckooFilter

put

public boolean put(T item,
                   int size,
                   CacheScope scopeInfo)

Description copied from interface: ClockCuckooFilter

Insert an item into cuckoo filter.

Specified by:

put in interface ClockCuckooFilter<T>

Parameters:

item - the object to be inserted

size - the size of this item

scopeInfo - the scope this item belongs to

Returns:

true if inserted successfully; false otherwise

mightContainAndResetClock

public boolean mightContainAndResetClock(T item)

Description copied from interface: ClockCuckooFilter

Check whether an item is in cuckoo filter (and reset its clock to MAX) or not.

Specified by:

mightContainAndResetClock in interface ClockCuckooFilter<T>

Parameters:

item - the item to be checked

Returns:

true if item is in cuckoo filter; false otherwise

mightContain

public boolean mightContain(T item)

Description copied from interface: ClockCuckooFilter

Check whether an item is in cuckoo filter or not. This method will not change item's clock.

Specified by:

mightContain in interface ClockCuckooFilter<T>

Parameters:

item - the item to be checked

Returns:

true if item is in cuckoo filter; false otherwise

delete

public boolean delete(T item)

Description copied from interface: ClockCuckooFilter

Delete an item from cuckoo filter.

Specified by:

delete in interface ClockCuckooFilter<T>

Parameters:

item - the item to be deleted

Returns:

true if the item is deleted; false otherwise

aging

public void aging()

Description copied from interface: ClockCuckooFilter

A thread-safe method to check aging progress of each segment. Should be called on each T/(2^C), where T is the window size and C is the bits number of the CLOCK field.

Specified by:

aging in interface ClockCuckooFilter<T>

getAge

public int getAge(T item)

Get the item's clock value (age).

Parameters:

item - the item to be queried

Returns:

the clock value

getSummary

public String getSummary()

Returns:

the summary of this cuckoo filter

expectedFpp

public double expectedFpp()

Specified by:

expectedFpp in interface ClockCuckooFilter<T>

Returns:

the probability that ClockCuckooFilter.mightContain(Object) will erroneously return true for an object that has not actually been put in the ConcurrentCuckooFilter.

approximateElementCount

public long approximateElementCount()

Specified by:

approximateElementCount in interface ClockCuckooFilter<T>

Returns:

the number of items in this cuckoo filter

approximateElementCount

public long approximateElementCount(CacheScope scopeInfo)

Specified by:

approximateElementCount in interface ClockCuckooFilter<T>

Parameters:

scopeInfo - the scope to be queried

Returns:

the number of items of specified scope in this cuckoo filter

approximateElementSize

public long approximateElementSize()

Specified by:

approximateElementSize in interface ClockCuckooFilter<T>

Returns:

the size of items in this cuckoo filter

approximateElementSize

public long approximateElementSize(CacheScope scopeInfo)

Specified by:

approximateElementSize in interface ClockCuckooFilter<T>

Parameters:

scopeInfo - the scope to be queried

Returns:

the size of items of specified scope in this cuckoo filter

increaseOperationCount

public void increaseOperationCount(int count)

By calling this method, cuckoo filter is informed of the number of entries have passed.

Parameters:

count - the number of operations have passed

getNumBuckets

public int getNumBuckets()

Returns:

the number of buckets this cuckoo filter has

getTagsPerBucket

public int getTagsPerBucket()

Returns:

the number of slots per bucket has

getBitsPerTag

public int getBitsPerTag()

Returns:

the number of bits per slot has

getBitsPerClock

public int getBitsPerClock()

Returns:

the number of bits per slot's clock field has

getBitsPerSize

public int getBitsPerSize()

Returns:

the number of bits per slot's size field has

getBitsPerScope

public int getBitsPerScope()

Returns:

the number of bits per slot's scope field has