alluxio.client.file.cache.cuckoofilter

Interface ClockCuckooFilter<T>

Type Parameters:

T - the type of instances that the ClockCuckooFilter accepts

All Known Implementing Classes:

ConcurrentClockCuckooFilter

public interface ClockCuckooFilter<T>

This interface represents a clock cuckoo filter that supports Put/Get/Delete operations.

Cuckoo filter is an approximate structure for membership query. Apart from Put and Get, it also supports deleting items from filter, which is not allowed in bloom filter. See "Cuckoo Filter: Practically Better Than Bloom" by Fan et al. for more detailed description.

Clock cuckoo filter is an extension of basic cuckoo filter. Specifically, it has the following features: 1) sliding window model: it will automatically delete stale items, which means they are not accessed over a recent interval; 2) size estimation: it can not only report the approximate number of unique items in it, but also the total size of those items; 3) hierarchy: we assume items are organized in a hierarchical level structure, and it can report the statistics of a specific level.

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)
boolean	delete(T item) Delete an item from cuckoo filter.
double	expectedFpp()
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.

Method Detail

put

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

Insert an item into cuckoo filter.

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

boolean mightContainAndResetClock(T item)

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

Parameters:

item - the item to be checked

Returns:

true if item is in cuckoo filter; false otherwise

mightContain

boolean mightContain(T item)

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

Parameters:

item - the item to be checked

Returns:

true if item is in cuckoo filter; false otherwise

delete

boolean delete(T item)

Delete an item from cuckoo filter.

Parameters:

item - the item to be deleted

Returns:

true if the item is deleted; false otherwise

aging

void aging()

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.

expectedFpp

double expectedFpp()

Returns:

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

approximateElementCount

long approximateElementCount()

Returns:

the number of items in this cuckoo filter

approximateElementCount

long approximateElementCount(CacheScope scopeInfo)

Parameters:

scopeInfo - the scope to be queried

Returns:

the number of items of specified scope in this cuckoo filter

approximateElementSize

long approximateElementSize()

Returns:

the size of items in this cuckoo filter

approximateElementSize

long approximateElementSize(CacheScope scopeInfo)

Parameters:

scopeInfo - the scope to be queried

Returns:

the size of items of specified scope in this cuckoo filter