cuckoo_cache/lib.rs
1//! Cuckoo hash based cache storage engine with fixed-size item slots.
2//!
3//! This crate implements an array-based cache that uses cuckoo hashing to map
4//! keys to one of D=4 candidate positions in a flat array of fixed-size slots.
5//! When all candidate positions for a new key are occupied, existing items may
6//! be displaced to their alternative positions, up to a configurable depth.
7//! If displacement fails, an item is evicted according to the configured policy.
8//!
9//! The design is based on the cuckoo storage engine from Pelikan:
10//! <https://github.com/pelikan-io/pelikan>
11//!
12//! Goals:
13//! * O(1) lookup with bounded worst case
14//! * fixed per-item memory overhead
15//! * bounded insertion latency via displacement limits
16//!
17//! Non-goals:
18//! * not designed for concurrent access
19//! * not suited for items larger than the configured slot size
20
21#[macro_use]
22extern crate log;
23
24mod builder;
25mod cuckoo;
26mod error;
27mod item;
28
29#[cfg(feature = "metrics")]
30mod metrics;
31
32#[cfg(test)]
33mod tests;
34
35pub use builder::Builder;
36pub use cuckoo::CuckooCache;
37pub use error::CuckooCacheError;
38pub use item::Item;
39pub use keyvalue::Value;
40
41/// Eviction policy used when all candidate positions are occupied and
42/// displacement cannot free a slot.
43#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
44pub enum Policy {
45 /// Select a random candidate for eviction.
46 #[default]
47 Random,
48 /// Prefer evicting the candidate with the nearest expiration time.
49 Expire,
50}
51
52/// The number of candidate hash positions per item (D in the cuckoo
53/// hashing literature).
54pub(crate) const D: usize = 4;