Expandable Cuckoo Filter

A high-performance, persistent, and auto-expanding Cuckoo Filter for Rust.

Features

• Auto-Expansion: Automatically chains new filters when the current one reaches capacity (~80% load factor), ensuring zero insertion failures.
• Deterministic Persistence: Robust export and import methods using raw byte serialization (no compression bloat).
• Orthogonal Hashing: Uses a node_id based seeding strategy to ensure that filters for different nodes generate uncorrelated false positives.
• Thread-Safe: Internal state protected by RwLock for concurrent access.
• Fuzzer Verified: Extensively tested with proptest for set semantics and persistence roundtrips.

Why this instead of a Bloom Filter?

Unlike Bloom filters, Cuckoo filters support deletion without significant overhead and typically offer higher space efficiency for low false-positivity rates. This implementation adds dynamic sizing, solving the "fixed capacity" limitation of standard Cuckoo filters.

Usage

use expandable_cuckoo_filter::ExpandableCuckooFilter;

// Create a new filter with a unique node ID and initial capacity
let filter = ExpandableCuckooFilter::new("node-1", 1000);

// Insert items
filter.insert("hello");
filter.insert("world");

// Check presence
assert!(filter.contains("hello"));

// Remove items
filter.remove("hello");
assert!(!filter.contains("hello"));

// Persistence
let bytes = filter.export().unwrap();
let restored = ExpandableCuckooFilter::new("node-1", 1000);
restored.import(&bytes).unwrap();

Internal Architecture

This crate "patches" the standard cuckoofilter behavior by salting keys with a stable seed derived from the node_id. This prevents "zombie filters" and is the foundation for the orthogonal-cuckoo consensus system. This double hashing adds approx 18ns per operation (benchmarks show 23.7ns / operation for the raw CuckooFilter and 41.3ns / operation for ExpandableCuckooFilter).