subms_cuckoo_filter/features/
dynamic.rs

1//! Dynamic cuckoo filter: chains a fresh cuckoo filter at each load
2//! milestone so the structure grows past its initial sizing without
3//! the rejection-at-saturation behaviour of the base filter.
4//!
5//! Algorithm (Chen et al., "Dynamic Cuckoo Filter", 2017): when the
6//! active filter's load factor passes `grow_threshold` (default 0.95),
7//! allocate a new filter at double the bucket count and start inserting
8//! there. Membership query asks every filter; positive if ANY layer
9//! says yes. Delete probes every layer in newest-first order and
10//! removes from the first match (deleting from older layers preserves
11//! the structural integrity of newer ones).
12//!
13//! Why a chain instead of migration: cuckoo filters store partial-key
14//! fingerprints, not keys. Re-bucketing a fingerprint after capacity
15//! grows can lose track of the second candidate bucket (the alt-index
16//! depends on the fingerprint, not the key). The DCF paper sidesteps
17//! this by chaining filters, which gives O(1) amortised insert and
18//! O(L) query where L is the chain length.
19
20use crate::CuckooFilter;
21
22const DEFAULT_INITIAL_BUCKETS_HINT: usize = 1024;
23const DEFAULT_GROW_THRESHOLD: f64 = 0.95;
24const GROWTH_FACTOR: usize = 2;
25/// Slots per bucket. Matches the base filter; layers always share the
26/// same bucket size so query semantics stay consistent.
27const BUCKET_SIZE: usize = 4;
28
29pub struct DynamicCuckooFilter {
30    layers: Vec<CuckooFilter>,
31    layer_capacities: Vec<usize>,
32    grow_threshold: f64,
33}
34
35impl DynamicCuckooFilter {
36    /// Build a dynamic cuckoo filter starting sized for
37    /// `initial_capacity` entries. Auto-grows at 95% load.
38    pub fn new(initial_capacity: usize) -> Self {
39        Self::with_threshold(initial_capacity, DEFAULT_GROW_THRESHOLD)
40    }
41
42    /// Build with a custom grow threshold in `(0.0, 1.0)`. Lower
43    /// thresholds grow earlier (more layers, lower per-layer pressure);
44    /// higher thresholds delay growth at the cost of risk-of-rejection.
45    pub fn with_threshold(initial_capacity: usize, grow_threshold: f64) -> Self {
46        let cap = initial_capacity.max(DEFAULT_INITIAL_BUCKETS_HINT / BUCKET_SIZE);
47        let t = if grow_threshold.is_finite() && grow_threshold > 0.0 && grow_threshold < 1.0 {
48            grow_threshold
49        } else {
50            DEFAULT_GROW_THRESHOLD
51        };
52        Self {
53            layers: vec![CuckooFilter::with_capacity(cap)],
54            layer_capacities: vec![cap],
55            grow_threshold: t,
56        }
57    }
58
59    pub fn layer_count(&self) -> usize {
60        self.layers.len()
61    }
62
63    pub fn len(&self) -> usize {
64        self.layers.iter().map(|l| l.len()).sum()
65    }
66
67    pub fn is_empty(&self) -> bool {
68        self.len() == 0
69    }
70
71    /// Insert a key into the active layer. Grows if the active layer
72    /// crosses the load threshold OR rejects the insert outright.
73    pub fn insert(&mut self, key: &str) -> bool {
74        if self.should_grow() {
75            self.grow();
76        }
77        let active = self.layers.len() - 1;
78        if self.layers[active].insert(key) {
79            return true;
80        }
81        // Saturation at the active layer despite the threshold check:
82        // grow once more and retry. Layer growth is bounded by the
83        // global `len()` so this terminates even under pathological
84        // collisions.
85        self.grow();
86        let active = self.layers.len() - 1;
87        self.layers[active].insert(key)
88    }
89
90    /// Membership over every layer. False positives possible (same FPR
91    /// model as the base; cumulative FPR is bounded by sum across
92    /// layers but typically dominated by the active layer).
93    pub fn contains(&self, key: &str) -> bool {
94        self.layers.iter().any(|l| l.contains(key))
95    }
96
97    /// Delete a single occurrence. Probes newest-first so duplicate
98    /// keys are removed in reverse insertion order.
99    pub fn delete(&mut self, key: &str) -> bool {
100        for layer in self.layers.iter_mut().rev() {
101            if layer.delete(key) {
102                return true;
103            }
104        }
105        false
106    }
107
108    pub fn load_factor(&self) -> f64 {
109        let active = self.layers.len() - 1;
110        let cap = self.layer_capacities[active];
111        if cap == 0 {
112            0.0
113        } else {
114            self.layers[active].len() as f64 / cap as f64
115        }
116    }
117
118    fn should_grow(&self) -> bool {
119        let active = self.layers.len() - 1;
120        let cap = self.layer_capacities[active];
121        if cap == 0 {
122            return false;
123        }
124        self.layers[active].len() as f64 / cap as f64 >= self.grow_threshold
125    }
126
127    fn grow(&mut self) {
128        let last = self.layer_capacities.len() - 1;
129        let new_cap = self.layer_capacities[last] * GROWTH_FACTOR;
130        self.layers.push(CuckooFilter::with_capacity(new_cap));
131        self.layer_capacities.push(new_cap);
132    }
133}
134
135#[cfg(test)]
136#[path = "dynamic_tests.rs"]
137mod tests;
subms_cuckoo_filter/features/dynamic.rs

subms_cuckoo_filter/features/
dynamic.rs
