cuckoo_clock/config.rs
1//! This module provides configuration types for [`crate::CuckooFilter`].
2
3use std::{
4 fmt::Display,
5 hash::RandomState,
6 num::{NonZeroU32, NonZeroUsize},
7 ops::{Add, Deref, DerefMut},
8};
9
10use crate::{CuckooFilter, data_block::DataBlockFieldConfiguration};
11
12/// Error type for all configuration options.
13#[derive(Debug)]
14pub enum ConfigError {
15 /// Error due to requesting buckets that are too big to represent (requiring over [`usize::MAX`]
16 /// bytes).
17 BucketTooBig,
18 /// Error due to requesting bucket count that is too big to represent (requiring over [`usize::MAX`]
19 /// buckets). This is affected by `max_entries` and `bucket_size`.
20 BucketCountTooBig,
21 /// Error due to requesting more than 32 bits for any of the fields (fingerprint or associated
22 /// field).
23 BitCountTooHigh,
24 /// Error due to requesting 0 bits for a field. If a field is enabled, it should take up at
25 /// least 1 bit.
26 BitCountTooLow,
27}
28
29impl Display for ConfigError {
30 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31 match self {
32 ConfigError::BucketTooBig => {
33 f.write_str("Filter configuration requires buckets that are too big!")
34 }
35 ConfigError::BucketCountTooBig => {
36 f.write_str("Filter configuration requires bucket count that is too high! Reduce max number of entries or increase bucket size.")
37 }
38 ConfigError::BitCountTooHigh => f.write_str(&format!(
39 "Bit count is too high! Max is {}.",
40 BitCount::MAX.0
41 )),
42 ConfigError::BitCountTooLow => {
43 f.write_str(&format!("Bit count too low! Min is {}.", BitCount::MIN.0))
44 }
45 }
46 }
47}
48
49impl std::error::Error for ConfigError {
50 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
51 None
52 }
53}
54
55/// Builder for [`CuckooConfiguration`].
56///
57/// New instance can be created using [`CuckooConfiguration::builder`].
58///
59/// # Examples
60///
61/// ```
62/// use cuckoo_clock::config::CuckooConfiguration;
63/// let builder = CuckooConfiguration::builder(100_000);
64/// ```
65pub struct CuckooConfigurationBuilder {
66 pub(crate) fingerprint_bits: BitCount,
67 pub(crate) bucket_size: NonZeroUsize,
68 pub(crate) max_entries: usize,
69 pub(crate) max_kicks: usize,
70 pub(crate) lru: Option<LruConfig>,
71 pub(crate) ttl: Option<TtlConfig>,
72 pub(crate) counter: Option<CounterConfig>,
73}
74
75impl CuckooConfigurationBuilder {
76 /// Sets the number of bits used for fingerprint. Higher number of bits should result in less
77 /// collisions, which should result in a lower false positive rate, at the cost of increased
78 /// memory usage.
79 #[must_use]
80 pub const fn fingerprint_bits(mut self, bits: BitCount) -> Self {
81 self.fingerprint_bits = bits;
82 self
83 }
84
85 /// Sets the number of buckets to hold in a bucket. Larger buckets improve filter occupancy
86 /// (space utilization), but they also require larger fingerprints to retain the same false
87 /// positive rate.
88 ///
89 /// 5.1. Optimal bucket size in [the original paper] describes this relation.
90 ///
91 /// [the original paper]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
92 #[must_use]
93 pub const fn bucket_size(mut self, size: NonZeroUsize) -> Self {
94 self.bucket_size = size;
95 self
96 }
97
98 /// Maximum number of kicks to perform if all requested slots are occupied when inserting new
99 /// items. Items will be evicted and moved to their alternate slots until no more evictions are
100 /// required or maximum number of kicks is reached.
101 ///
102 /// If the maximum number of kicks is reached, one item will be lost from the filter.
103 ///
104 /// Increasing this number will increase filter occupancy at the cost of insertion speed.
105 #[must_use]
106 pub const fn max_kicks(mut self, kicks: usize) -> Self {
107 self.max_kicks = kicks;
108 self
109 }
110
111 /// Enables LRU eviction for the filter. Kicks will no longer be performed randomly and will
112 /// always target least recently used items, until either no more evictions are required, max
113 /// number of kicks was reached or the kicked item is to be moved in a bucket with all slots
114 /// occupied by more used items.
115 ///
116 /// When LRU is used, [`crate::CuckooFilter::scan_and_update_full`] should be called
117 /// periodically, to age LRU for all items. It is up to the caller to schedule this process.
118 /// More frequent scans will result in faster aging LRU for all items, requiring item to be
119 /// used more frequently to outlive other items.
120 #[must_use]
121 pub const fn with_lru(mut self, lru: LruConfig) -> Self {
122 self.lru = Some(lru);
123 self
124 }
125
126 /// Enables TTL for items in the filter. TTL will be used to expire items from the filter when
127 /// [`crate::CuckooFilter::scan_and_update_full`] is called.
128 ///
129 /// When TTL is used, [`crate::CuckooFilter::scan_and_update_full`] should be called
130 /// periodically, to age TTL for all items. It is up to the caller to schedule this process.
131 /// More frequent scans will result in lower TTL for all items.
132 #[must_use]
133 pub const fn with_ttl(mut self, ttl: TtlConfig) -> Self {
134 self.ttl = Some(ttl);
135 self
136 }
137
138 /// Enables counter for items in the filter. Counter is just provided as a value that can be
139 /// read when accessing items. It is increased on every access (and can be controlled
140 /// directly).
141 #[must_use]
142 pub const fn with_counter(mut self, counter: CounterConfig) -> Self {
143 self.counter = Some(counter);
144 self
145 }
146
147 /// Validates and builds the configuration.
148 ///
149 /// # Errors
150 ///
151 /// [`ConfigError::BucketTooBig`] if requests buckets are too big to represent with [`usize::MAX`].
152 /// Bucket size is defined as [`Self::bucket_size`] * item bits (sum of all fields bits,
153 /// rounded to byte).
154 pub fn build(&self) -> Result<CuckooConfiguration, ConfigError> {
155 let required_bucket_count = self.max_entries.div_ceil(self.bucket_size.get());
156 let bucket_count = required_bucket_count
157 .checked_next_power_of_two()
158 .ok_or(ConfigError::BucketCountTooBig)?;
159 let ttl_start = *self.fingerprint_bits
160 + if let Some(LruConfig { counter_bits, .. }) = self.lru {
161 *counter_bits
162 } else {
163 0
164 };
165 let counter_start = ttl_start
166 + if let Some(TtlConfig { ttl_bits, .. }) = self.ttl {
167 *ttl_bits
168 } else {
169 0
170 };
171
172 // Sum of bits will never reach the size of `usize`, so no need to do checked adds
173 let mut data_block_size = *self.fingerprint_bits;
174 if let Some(LruConfig { counter_bits, .. }) = self.lru {
175 data_block_size += *counter_bits;
176 }
177 if let Some(TtlConfig { ttl_bits, .. }) = self.ttl {
178 data_block_size += *ttl_bits;
179 }
180 if let Some(CounterConfig { counter_bits, .. }) = self.counter {
181 data_block_size += *counter_bits;
182 }
183 data_block_size = data_block_size.div_ceil(8);
184 Ok(CuckooConfiguration {
185 bucket_size: self.bucket_size.get(),
186 max_kicks: self.max_kicks,
187
188 fingerprint_field_config: DataBlockFieldConfiguration::new(0..*self.fingerprint_bits),
189 lru_field_config: self.lru.clone().map(|lru| {
190 (
191 lru,
192 DataBlockFieldConfiguration::new(
193 *self.fingerprint_bits
194 ..*self.fingerprint_bits
195 + self
196 .lru
197 .as_ref()
198 .map(|l| l.counter_bits)
199 .unwrap_or(BitCount(0)),
200 ),
201 )
202 }),
203 ttl_field_config: self.ttl.clone().map(|ttl| {
204 (
205 ttl,
206 DataBlockFieldConfiguration::new(
207 ttl_start
208 ..ttl_start
209 + *self.ttl.as_ref().map(|t| t.ttl_bits).unwrap_or(BitCount(0)),
210 ),
211 )
212 }),
213 counter_field_config: self.counter.clone().map(|counter| {
214 (
215 counter,
216 DataBlockFieldConfiguration::new(
217 counter_start
218 ..counter_start
219 + *self
220 .counter
221 .as_ref()
222 .map(|c| c.counter_bits)
223 .unwrap_or(BitCount(0)),
224 ),
225 )
226 }),
227 data_block_size,
228 bucket_byte_size: self
229 .bucket_size
230 .get()
231 .checked_mul(data_block_size)
232 .ok_or(ConfigError::BucketTooBig)?,
233 bucket_count,
234 #[expect(clippy::cast_possible_truncation)]
235 buckets_mask: (bucket_count - 1) as u32,
236 })
237 }
238}
239
240/// Strategy to use when aging LRU counter on scans.
241#[derive(Clone, Default, Debug, PartialEq, Eq)]
242#[repr(u8)]
243pub enum LruAgingStrategy {
244 /// Halving the counter value each scan. Useful to age the items more quickly.
245 #[default]
246 Halving,
247 /// Reduces the counter by a fixed amount each scan.
248 Decrement(u32),
249}
250
251impl LruAgingStrategy {
252 pub(crate) const fn age_value(&self, value: u32) -> u32 {
253 match self {
254 LruAgingStrategy::Halving => value >> 1,
255 LruAgingStrategy::Decrement(dec) => value.saturating_sub(*dec),
256 }
257 }
258}
259
260/// Configuration for the LRU field.
261///
262/// Used to define memory used by the LRU field, also affecting its maximum value.
263///
264/// # Examples
265///
266/// ```
267/// use cuckoo_clock::config::LruConfig;
268///
269/// let ttl_config = LruConfig {
270/// counter_bits: 5.try_into()?,
271/// ..Default::default()
272/// };
273/// # Ok::<(), Box<dyn std::error::Error>>(())
274/// ```
275#[derive(Clone, Debug, PartialEq, Eq)]
276pub struct LruConfig {
277 /// Number of bits used to represent the LRU counter.
278 /// Larger bit counts allow more values to be represented, allowing items to "accumulate"
279 /// higher use counts, which will take longer to age.
280 pub counter_bits: BitCount,
281 /// The strategy to use when aging LRU counters.
282 pub aging_strategy: LruAgingStrategy,
283 /// The starting value for LRU counter to use.
284 pub starting_value: u32,
285 /// If set to true, items that already have a 0 counter value will be removed at scan time.
286 pub remove_on_zero: bool,
287 /// Increment to add to LRU counter on each insert and lookup.
288 pub increment: u32,
289}
290
291impl Default for LruConfig {
292 fn default() -> Self {
293 Self {
294 counter_bits: BitCount(8),
295 aging_strategy: LruAgingStrategy::default(),
296 starting_value: 1,
297 remove_on_zero: false,
298 increment: 1,
299 }
300 }
301}
302
303/// Configuration for the TTL field.
304///
305/// Used to define memory used by the TTL field and the default value.
306///
307/// # Examples
308///
309/// ```
310/// use cuckoo_clock::config::TtlConfig;
311///
312/// let ttl_config = TtlConfig {
313/// ttl: 100.try_into()?,
314/// ttl_bits: 7.try_into()?
315/// };
316/// # Ok::<(), Box<dyn std::error::Error>>(())
317/// ```
318#[derive(Clone, Debug, PartialEq, Eq)]
319pub struct TtlConfig {
320 /// The default TTL counter value for newly inserted items. The actual lifetime duration will
321 /// be defined by this value combined with the frequency of calls to
322 /// [`crate::CuckooFilter::scan_and_update_full`]. Each call to
323 /// [`crate::CuckooFilter::scan_and_update_full`] will reduce the counter by 1, until it
324 /// reaches 0, when the item is removed.
325 pub ttl: NonZeroU32,
326 /// Number of bits used to represent the TTL counter.
327 /// Larget bit counts allow higher TTL to be represented.
328 pub ttl_bits: BitCount,
329}
330
331/// Configuration for the generic counter field.
332///
333/// Used to define memory used by the generic counter field, also affecting its maximum value.
334///
335/// # Examples
336///
337/// ```
338/// use cuckoo_clock::config::CounterConfig;
339///
340/// let ttl_config = CounterConfig {
341/// counter_bits: 5.try_into()?,
342/// ..Default::default()
343/// };
344/// # Ok::<(), Box<dyn std::error::Error>>(())
345/// ```
346#[derive(Clone, Debug, PartialEq, Eq)]
347pub struct CounterConfig {
348 /// How many bits are used to represent the generic counter.
349 /// Larget bit counts allow higher counter values to be represented.
350 pub counter_bits: BitCount,
351 /// Diff to apply to counter on each insert.
352 pub change_on_insert: i32,
353 /// Diff to apply to counter on each lookup.
354 pub change_on_lookup: i32,
355}
356
357impl Default for CounterConfig {
358 fn default() -> Self {
359 Self {
360 counter_bits: BitCount(4),
361 change_on_insert: 1,
362 change_on_lookup: 1,
363 }
364 }
365}
366
367/// Configuration for the [`crate::CuckooFilter`].
368///
369/// Used to define main cuckoo filter parameters (capacity, bucket size, fingeprint size,
370/// max kicks), as well as additional features (TTL, LRU, generic counter).
371///
372/// Create a new instance using [`CuckooConfiguration::builder`].
373///
374/// # Examples
375///
376/// ```
377/// use cuckoo_clock::config::CuckooConfiguration;
378///
379/// let config = CuckooConfiguration::builder(100_000)
380/// .fingerprint_bits(14.try_into()?)
381/// .bucket_size(4.try_into()?)
382/// .max_kicks(8)
383/// .build()?;
384/// # Ok::<(), Box<dyn std::error::Error>>(())
385/// ```
386///
387/// ```
388/// use cuckoo_clock::config::{CuckooConfiguration, TtlConfig, LruConfig};
389///
390/// let config = CuckooConfiguration::builder(100_000)
391/// .fingerprint_bits(14.try_into()?)
392/// .with_ttl(TtlConfig {
393/// ttl: 10.try_into()?,
394/// ttl_bits: 4.try_into()?
395/// })
396/// .with_lru(LruConfig {
397/// counter_bits: 6.try_into()?,
398/// ..Default::default()
399/// })
400/// .bucket_size(4.try_into()?)
401/// .max_kicks(8)
402/// .build()?;
403/// # Ok::<(), Box<dyn std::error::Error>>(())
404/// ```
405#[derive(Clone, Debug, PartialEq, Eq)]
406pub struct CuckooConfiguration {
407 pub(crate) bucket_size: usize,
408 pub(crate) max_kicks: usize,
409
410 pub(crate) fingerprint_field_config: DataBlockFieldConfiguration,
411 pub(crate) lru_field_config: Option<(LruConfig, DataBlockFieldConfiguration)>,
412 pub(crate) counter_field_config: Option<(CounterConfig, DataBlockFieldConfiguration)>,
413 pub(crate) ttl_field_config: Option<(TtlConfig, DataBlockFieldConfiguration)>,
414 pub(crate) data_block_size: usize,
415 pub(crate) bucket_byte_size: usize,
416 pub(crate) bucket_count: usize,
417 pub(crate) buckets_mask: u32,
418}
419
420impl CuckooConfiguration {
421 /// Creates a new instance of [`CuckooConfigurationBuilder`] with provided maximum number of
422 /// entries.
423 #[must_use]
424 pub const fn builder(max_entries: usize) -> CuckooConfigurationBuilder {
425 CuckooConfigurationBuilder {
426 fingerprint_bits: BitCount(8),
427 #[expect(clippy::expect_used)]
428 bucket_size: NonZeroUsize::new(4).expect("4 != 0"),
429 max_entries,
430 max_kicks: 500,
431 lru: None,
432 ttl: None,
433 counter: None,
434 }
435 }
436
437 /// Returns the memory usage of filter that would be created from this configuration in bytes.
438 #[must_use]
439 pub const fn get_configured_memory_usage(&self) -> usize {
440 CuckooFilter::<RandomState>::get_expected_memory_usage(
441 self.bucket_byte_size,
442 self.bucket_count,
443 )
444 }
445
446 /// Checks whether this and other configuration have a compatible layout.
447 ///
448 /// If this is true, filter exported by the other configuration can be imported and used with this
449 /// configuration. The only compatible configuration changes are generally ones that don't
450 /// affect size or count of the buckets and items.
451 #[must_use]
452 pub fn compatible_layout(&self, other: &Self) -> bool {
453 if self.bucket_size != other.bucket_size {
454 return false;
455 }
456 if self.bucket_count != other.bucket_count {
457 return false;
458 }
459 if self.buckets_mask != other.buckets_mask {
460 return false;
461 }
462 if self.bucket_byte_size != other.bucket_byte_size {
463 return false;
464 }
465 if self.data_block_size != other.data_block_size {
466 return false;
467 }
468 if self.fingerprint_field_config != other.fingerprint_field_config {
469 return false;
470 }
471 if !Self::field_compatible(&self.lru_field_config, &other.lru_field_config) {
472 return false;
473 }
474 if !Self::field_compatible(&self.counter_field_config, &other.counter_field_config) {
475 return false;
476 }
477 if !Self::field_compatible(&self.ttl_field_config, &other.ttl_field_config) {
478 return false;
479 }
480 true
481 }
482
483 /// Returns the configured bucket size.
484 #[must_use]
485 pub const fn bucket_size(&self) -> usize {
486 self.bucket_size
487 }
488
489 /// Returns the configured max kicks.
490 #[must_use]
491 pub const fn max_kicks(&self) -> usize {
492 self.max_kicks
493 }
494
495 /// Returns the LRU configuration, if available.
496 #[must_use]
497 pub fn lru_config(&self) -> Option<LruConfig> {
498 self.lru_field_config
499 .as_ref()
500 .map(|(lru, _field)| lru.clone())
501 }
502
503 /// Returns the TTL configuration, if available.
504 #[must_use]
505 pub fn ttl_config(&self) -> Option<TtlConfig> {
506 self.ttl_field_config
507 .as_ref()
508 .map(|(ttl, _field)| ttl.clone())
509 }
510
511 /// Returns the counter configuration, if available.
512 #[must_use]
513 pub fn counter_config(&self) -> Option<CounterConfig> {
514 self.counter_field_config
515 .as_ref()
516 .map(|(counter, _field)| counter.clone())
517 }
518
519 /// Returns the actual bucket count for this [`CuckooConfiguration`].
520 ///
521 /// Bucket count is calculated as first next power of two of capacity / bucket_size.
522 /// This means that the actual capacity of the filter is usually bigger than the requested
523 /// capacity.
524 #[must_use]
525 pub const fn get_bucket_count(&self) -> usize {
526 self.bucket_count
527 }
528
529 fn field_compatible<T>(
530 self_field: &Option<(T, DataBlockFieldConfiguration)>,
531 other_field: &Option<(T, DataBlockFieldConfiguration)>,
532 ) -> bool {
533 match (self_field, other_field) {
534 (None, Some(_)) | (Some(_), None) => false,
535 (None, None) => true,
536 (Some((_, self_field_config)), Some((_, other_field_config))) => {
537 self_field_config == other_field_config
538 }
539 }
540 }
541}
542
543/// Number of bits. Used to define sizes of the fields.
544///
545/// This value is limited by [`BitCount::MIN`] and [`BitCount::MAX`] and can only be created using
546/// the [`TryFrom`] trait, to ensure the bit count is validated.
547///
548/// # Examples
549///
550/// ```
551/// use cuckoo_clock::config::BitCount;
552///
553/// let bit_count: BitCount = 8.try_into().unwrap();
554/// let bit_count_max: BitCount = 32.try_into().unwrap();
555/// let bit_count_min: BitCount = 1.try_into().unwrap();
556/// ```
557///
558/// ```should_panic
559/// use cuckoo_clock::config::BitCount;
560///
561/// let bit_count: BitCount = 0.try_into().unwrap();
562/// ```
563///
564/// ```should_panic
565/// use cuckoo_clock::config::BitCount;
566///
567/// let bit_count: BitCount = 40.try_into().unwrap();
568/// ```
569#[derive(Debug, Clone, Copy, PartialEq, Eq)]
570pub struct BitCount(usize);
571
572impl BitCount {
573 /// Maximum allowed value for [`BitCount`]
574 pub const MAX: BitCount = BitCount(32);
575 /// Minimum allowed value for [`BitCount`]
576 pub const MIN: BitCount = BitCount(1);
577}
578
579impl Deref for BitCount {
580 type Target = usize;
581
582 fn deref(&self) -> &Self::Target {
583 &self.0
584 }
585}
586
587impl DerefMut for BitCount {
588 fn deref_mut(&mut self) -> &mut Self::Target {
589 &mut self.0
590 }
591}
592
593impl TryFrom<usize> for BitCount {
594 type Error = ConfigError;
595
596 fn try_from(value: usize) -> Result<Self, Self::Error> {
597 if value > Self::MAX.0 {
598 return Err(ConfigError::BitCountTooHigh);
599 }
600 if value < Self::MIN.0 {
601 return Err(ConfigError::BitCountTooLow);
602 }
603 Ok(Self(value))
604 }
605}
606
607impl From<BitCount> for usize {
608 fn from(value: BitCount) -> Self {
609 value.0
610 }
611}
612
613// Since bit count can't be higher than 32
614// Conversion into any integer is fine
615impl From<BitCount> for u64 {
616 fn from(value: BitCount) -> Self {
617 value.0 as u64
618 }
619}
620
621impl From<BitCount> for u32 {
622 #[expect(clippy::cast_possible_truncation)]
623 fn from(value: BitCount) -> Self {
624 value.0 as u32
625 }
626}
627
628impl From<BitCount> for u16 {
629 #[expect(clippy::cast_possible_truncation)]
630 fn from(value: BitCount) -> Self {
631 value.0 as u16
632 }
633}
634
635impl From<BitCount> for u8 {
636 #[expect(clippy::cast_possible_truncation)]
637 fn from(value: BitCount) -> Self {
638 value.0 as u8
639 }
640}
641
642impl Add<usize> for BitCount {
643 type Output = usize;
644
645 fn add(self, rhs: usize) -> Self::Output {
646 self.0 + rhs
647 }
648}
649
650impl Add<BitCount> for usize {
651 type Output = usize;
652
653 fn add(self, rhs: BitCount) -> Self::Output {
654 self + rhs.0
655 }
656}