Struct CuckooFilter 

pub struct CuckooFilter<H: BuildHasher> { /* private fields */ }

Thread-safe cuckoo filter, with support for TTL, LRU and custom counters associated with the stored data.

Instances of CuckooFilter can be cloned and used across different threads. To ensure thread safety, locks are used, but locking is done per bucket, meaning that 2 separate threads can freely access different buckets without conflicts. In most cases locks shouldn’t block, because optimal cuckoo filter configuration will have a large number of buckets, reducing the change of concurrent access to the same bucket.

Instances of CuckooFilter build using CuckooFilter::new_random_exportable or with a BuildHasher that also implements ExportableBuildHasher can be exported and imported, using CuckooFilter::exporter and CuckooFilter::import. Note that configuration is stored in the exported data too and can’t be changed, because any changes to the configuration data would invalidate all of the stored data.

Examples

Basic cuckoo filter with default configuration

use cuckoo_clock::{CuckooFilter, config::CuckooConfiguration};

let filter = CuckooFilter::new_random(CuckooConfiguration::builder(100_000).build()?);

// None returned from insertion means no entry was evicted
assert!(filter.insert("example_data").is_none());

// Insertion must have been successful
assert!(filter.contains("example_data"));

// Deletion must have been successful
assert!(filter.remove("example_data"));
assert!(!filter.contains("example_data"));

More complex use-case, with additional options

use cuckoo_clock::{CuckooFilter, config::{CuckooConfiguration, CounterConfig, TtlConfig}};

let filter = CuckooFilter::new_random(
    CuckooConfiguration::builder(10_000_000)
        .fingerprint_bits(18.try_into()?)
        .bucket_size(8.try_into()?)
        .with_counter(CounterConfig {
            counter_bits: 4.try_into()?,
            ..Default::default()
        })
        .with_ttl(TtlConfig {
            ttl: 600.try_into()?,
            ttl_bits: 10.try_into()?
        })
        .build()?
);

// In this case, we use `insert_if_not_present` to ensure no duplicates, because we care about
// the counter
// None returned from insertion means no entry was evicted
assert!(filter.insert_if_not_present("example_data").is_none());
assert!(filter.insert_if_not_present("example_data").is_none());

// Insertion must have been successful
assert!(filter.contains("example_data"));

// Counter should be 4 now.
// We have accessed this item 3 times, but `get_associated_data` also counts as an access.
assert_eq!(filter.get_associated_data("example_data").unwrap().get_counter()?, 4);

Export/import

use std::{collections::VecDeque, io::Read};
use cuckoo_clock::{CuckooFilter, config::CuckooConfiguration};

let filter = CuckooFilter::new_random_exportable(CuckooConfiguration::builder(100_000).build()?);

// None returned from insertion means no entry was evicted
assert!(filter.insert("example_data").is_none());

let mut buf = Vec::new();
filter.exporter().write_to(&mut buf)?;

let mut buf = VecDeque::from(buf);
let imported_filter = CuckooFilter::import_random_exportable(&mut buf)?;

// The inserted data is available in the imported filter
assert!(filter.contains("example_data"));

Implementations

impl CuckooFilter<RandomState>

pub fn new_random(configuration: CuckooConfiguration) -> Self

Creates a new instance of CuckooFilter, using RandomState as its BuildHasher.

Panics

Panics if allocation of buckets fails (if too much memory was requested).

impl CuckooFilter<ExportableRandomState>

pub fn new_random_exportable(configuration: CuckooConfiguration) -> Self

Creates a new instance of CuckooFilter, using ExportableBuildHasher based on RandomState as its BuildHasher. This instance supports export using [CuckooFilter::export].

Panics

Panics if allocation of buckets fails (if too much memory was requested).

pub fn import_random_exportable(reader: impl Read) -> Result<Self, ImportError>

Creates a new instance of CuckooFilter, using ExportableBuildHasher based on exported data.

Panics

Panics if allocation of buckets fails (if too much memory was requested).

impl<H: ExportableBuildHasher + BuildHasher> CuckooFilter<H>

pub fn import(reader: impl Read) -> Result<Self, ImportError>

Creates a cuckoo filter from its exported state.

Panics

Panics if allocation of buckets fails (if too much memory was requested).

pub fn import_config( reader: impl Read, ) -> Result<(H, CuckooConfiguration), ImportError>

Creates a cuckoo filter configuration from its exported state - skips the actual state.

pub fn import_state( hasher: H, configuration: CuckooConfiguration, reader: impl Read, ) -> Result<Self, ImportError>

Creates a cuckoo filter from its exported state and already read hasher and configuration. This assumes that these 2 were already read from the provided reader.

Panics

Panics if allocation of buckets fails (if too much memory was requested).

pub fn exporter<'a>(&'a self) -> CuckooFilterExporter<'a, H>

Prepares an exporter for this CuckooFilter, enabling to persist it and import it later using CuckooFilter::import.

impl<H: BuildHasher> CuckooFilter<H>

pub fn new(configuration: CuckooConfiguration, build_hasher: H) -> Self

Creates a new instance of CuckooFilter, using provided BuildHasher.

Panics

Panics if allocation of buckets fails (if too much memory was requested).

pub const fn get_bucket_count(&self) -> usize

Returns the actual bucket count for this CuckooFilter.

Bucket count is calculated as first next power of two of capacity / bucket_size. This means that the actual capacity of the filter is usually bigger than the requested capacity.

pub fn get_item_count(&self) -> usize

Returns the actual number of items currently stored in this CuckooFilter.

pub fn get_configuration(&self) -> CuckooConfiguration

Returns the configuration for this CuckooFilter.

pub fn get_memory_usage(&self) -> usize

Returns the memory usage of this filter in bytes.

pub fn insert_if_not_present<K: Hash + ?Sized>( &self, key: &K, ) -> Option<Fingerprint>

Inserts a new item into the filter, only if the filter doesn’t contain it already.

This is slower than CuckooFilter::insert, but it ensures that no duplicates are present in the filter. That can be useful when AssociatedData is used, to ensure consistent results.

Returns fingerprint of the item that was evicted from the filter, if eviction had to take place to finalize the insertion. It is possible that the item that was just inserted gets evicted in random kicking process. That can be confirmed using Fingerprint::matches_key.

pub fn insert_if_not_present_with_update<K: Hash + ?Sized>( &self, key: &K, insert_values: InsertValues, lookup_update: LookupValues, ) -> Option<Fingerprint>

Inserts a new item into the filter, only if the filter doesn’t contain it already. Also applies provided updates.

This is similar to CuckooFilter::insert_if_not_present, but it also updates found values, or starts off values with different values.

pub fn insert<K: Hash + ?Sized>(&self, key: &K) -> Option<Fingerprint>

Inserts a new item into the filter.

If both target buckets for this item are full, random item is kicked out of one of these 2 buckets and moved into its alternate bucket, starting a recursive kicking process, which stops once an empty slot is found in alternate bucket of a kicked item, or crate::config::CuckooConfigurationBuilder::max_kicks is reached.

Returns fingerprint of the item that was evicted from the filter, if eviction had to take place to finalize the insertion. It is possible that the item that was just inserted gets evicted in random kicking process. That can be confirmed using Fingerprint::matches_key.

pub fn insert_with_defaults<K: Hash + ?Sized>( &self, key: &K, default: InsertValues, ) -> Option<Fingerprint>

Inserts a new item into the filter, with defined defaults for associated data.

This is similar to CuckooFilter::insert, but allows overrides for associated data defaults.

pub fn contains_with_update<K: Hash + ?Sized>( &self, key: &K, update: LookupValues, ) -> bool

Check if this key is stored in the filter and applies the provided LookupValues.

This is similar to CuckooFilter::contains, but allows overrides for updates on successful lookup.

pub fn contains<K: Hash + ?Sized>(&self, key: &K) -> bool

Check if this key is stored in the filter.

Returns true if this key might be present in the filter. If false is returned, then the key is definitely not present.

pub fn get_associated_data<K: Hash + ?Sized>( &self, key: &K, ) -> Option<AssociatedData>

Loads associated data of a key stored in the filter.

Returns None if this filter is not present in the filter. Returns associated data for the first item with the fingerprint matching this key’s fingerprint. Note that it is recommended to use CuckooFilter::insert_if_not_present if consistent AssociatedData is required.

pub fn get_associated_data_with_update<K: Hash + ?Sized>( &self, key: &K, update: LookupValues, ) -> Option<AssociatedData>

Loads associated data of a key stored in the filter and applies the provided LookupValues.

This is similar to CuckooFilter::get_associated_data, but allows overrides for updates on successful lookup.

pub fn remove<K: Hash + ?Sized>(&self, key: &K) -> bool

Removes this key from the filter, if present.

Returns true if the key was present in the filter.

pub fn scan_and_update_full(&self) -> usize

Scans all buckets of this filter and reduces TTL and LRU counters.

If LRU and/or TTL features are used, this must be called periodically. Each call to this function will age all the LRU and TTL counters. The frequency of calls will affect both LRU and TTL in different ways:

• TTL will get reduced by 1 on each call, meaning that scanning each second indirectly sets the unit of TTL field to be seconds.
• LRU will get halved on each call. By scanning more frequently, items will require more frequent usage to stay in the filter.

This is a no-op if both LRU and TTL are disabled.

Examples

use cuckoo_clock::{CuckooFilter, config::{CuckooConfiguration, CounterConfig, TtlConfig}};

let filter = CuckooFilter::new_random(
    CuckooConfiguration::builder(10_000)
        .with_ttl(TtlConfig {
            ttl: 3.try_into()?,
            ttl_bits: 2.try_into()?
        })
        .build()?
);

filter.insert("example_data");

assert!(filter.contains("example_data"));

filter.scan_and_update_full();
assert!(filter.contains("example_data"));

filter.scan_and_update_full();
assert!(filter.contains("example_data"));

// The item will get removed now, due to expired TTL
filter.scan_and_update_full();
assert!(!filter.contains("example_data"));

pub fn scan_and_update_full_partition( &self, total_partitions: NonZeroUsize, partition_index: usize, ) -> usize

Scans a single group of buckets of this filter and reduces TTL and LRU counters.

This is the same as CuckooFilter::scan_and_update_full, but it more suitable for parallelization, by splitting buckets into partitions to process in parallel.

pub fn scan_and_update_ttl(&self) -> usize

Scans all buckets of this filter and reduces TTL counters.

Similar to CuckooFilter::scan_and_update_full, but updates only TTL counters. This allows more control, enabling different update frequency for TTL and LRU.

This is a no-op if TTL is disabled.

pub fn scan_and_update_ttl_partition( &self, total_partitions: NonZeroUsize, partition_index: usize, ) -> usize

Scans a single group of buckets of this filter and reduces TTL counters.

This is the same as CuckooFilter::scan_and_update_ttl, but it more suitable for parallelization, by splitting buckets into partitions to process in parallel.

pub fn scan_and_update_lru(&self) -> usize

Scans all buckets of this filter and reduces LRU counters.

Similar to CuckooFilter::scan_and_update_full, but updates only LRU counters. This allows more control, enabling different update frequency for TTL and LRU.

This is a no-op if LRU is disabled.

pub fn scan_and_update_lru_partition( &self, total_partitions: NonZeroUsize, partition_index: usize, ) -> usize

Scans a single group of buckets of this filter and reduces LRU counters.

This is the same as CuckooFilter::scan_and_update_lru, but it more suitable for parallelization, by splitting buckets into partitions to process in parallel.

Trait Implementations

impl<H: Clone + BuildHasher> Clone for CuckooFilter<H>

fn clone(&self) -> CuckooFilter<H>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.