quick_cache/
lib.rs

1//! Lightweight, high performance concurrent cache. It allows very fast access to the cached items
2//! with little overhead compared to a plain concurrent hash table. No allocations are ever performed
3//! unless the cache internal state table needs growing (which will eventually stabilize).
4//!
5//! # Eviction policy
6//!
7//! The current eviction policy is a modified version of the Clock-PRO algorithm, very similar to the
8//! later published S3-FIFO algorithm. It's "scan resistent" and provides high hit rates,
9//! significantly better than a LRU eviction policy and comparable to other state-of-the art algorithms
10//! like W-TinyLFU.
11//!
12//! # Thread safety and Concurrency
13//!
14//! Both `sync` (thread-safe) and `unsync` (non thread-safe) implementations are provided. The latter
15//! offers slightly better performance when thread safety is not required.
16//!
17//! # Equivalent keys
18//!
19//! The cache uses the [`Equivalent`](https://docs.rs/equivalent/1.0.1/equivalent/trait.Equivalent.html) trait
20//! for gets/removals. It can help work around the `Borrow` limitations.
21//! For example, if the cache key is a tuple `(K, Q)`, you wouldn't be able to access such keys without
22//! building a `&(K, Q)` and thus potentially cloning `K` and/or `Q`.
23//!
24//! # User defined weight
25//!
26//! By implementing the [Weighter] trait the user can define different weights for each cache entry.
27//!
28//! # Atomic operations
29//!
30//! By using the `get_or_insert` or `get_value_or_guard` family of functions (both sync and async variants
31//! are available, they can be mix and matched) the user can coordinate the insertion of entries, so only
32//! one value is "computed" and inserted after a cache miss.
33//!
34//! The `entry` family of functions provide a closure-based API for atomically
35//! inspecting and acting on existing entries (keep, remove, or replace) while also coordinating
36//! insertion on cache misses.
37//!
38//! # Lifecycle hooks
39//!
40//! A user can optionally provide a custom [Lifecycle] implementation to hook into the lifecycle of cache entries.
41//!
42//! Example use cases:
43//! * item pinning, so even if the item occupies weight but isn't allowed to be evicted
44//! * send evicted items to a channel, achieving the equivalent to an eviction listener feature.
45//! * zero out item weights so they are left in the cache instead of evicted.
46//!
47//! # Approximate memory usage
48//!
49//! The memory overhead per entry is `21` bytes.
50//!
51//! The memory usage of the cache data structures can be estimated as:
52//! `(size_of::<K>() + size_of::<V>() + 21) * (length * 1.5).next_power_of_two()`
53//!
54//! Actual memory usage may vary depending on the cache options and the key and value types, which can have external
55//! allocations (e.g. `String`, `Vec`, etc.). The above formula only accounts for the cache's data structures.
56//!
57//! The `1.5` value in the formula above results from `1 + G`, where `G` is the configured ghost allocation specified
58//! in [`OptionsBuilder::ghost_allocation`], which is `0.5` by default.
59//!
60//! # Hasher
61//!
62//! By default the crate uses [ahash](https://crates.io/crates/ahash), which is enabled (by default) via
63//! a crate feature with the same name. If the `ahash` feature is disabled the crate defaults to the std lib
64//! implementation instead (currently Siphash13). Note that a custom hasher can also be provided if desirable.
65//!
66//! # Synchronization primitives
67//!
68//! By default the crate uses [parking_lot](https://crates.io/crates/parking_lot), which is enabled (by default) via
69//! a crate feature with the same name. If the `parking_lot` feature is disabled the crate defaults to the std lib
70//! implementation instead.
71//!
72//! # Cargo Features
73//!
74//! | Feature | Default | Description |
75//! |---------|---------|-------------|
76//! | `ahash` | ✓ | Use [ahash](https://crates.io/crates/ahash) as the default hasher. When disabled, falls back to std lib's `RandomState` (currently SipHash-1-3). |
77//! | `parking_lot` | ✓ | Use [parking_lot](https://crates.io/crates/parking_lot) for synchronization primitives. When disabled, falls back to std lib's `RwLock`. |
78//! | `shuttle` | | Enable [shuttle](https://crates.io/crates/shuttle) testing support for concurrency testing. |
79//! | `stats` | | Enable cache statistics tracking via the `hits()` and `misses()` methods. |
80#![allow(clippy::type_complexity)]
81#![cfg_attr(docsrs, feature(doc_cfg))]
82
83#[cfg(not(fuzzing))]
84mod linked_slab;
85#[cfg(fuzzing)]
86pub mod linked_slab;
87mod options;
88#[cfg(not(feature = "shuttle"))]
89mod rw_lock;
90mod shard;
91mod shim;
92/// Concurrent cache variants that can be used from multiple threads.
93pub mod sync;
94mod sync_placeholder;
95/// Non-concurrent cache variants.
96pub mod unsync;
97pub use equivalent::Equivalent;
98
99#[cfg(all(test, feature = "shuttle"))]
100mod shuttle_tests;
101
102pub use options::{Options, OptionsBuilder};
103
104#[cfg(feature = "ahash")]
105pub type DefaultHashBuilder = ahash::RandomState;
106#[cfg(not(feature = "ahash"))]
107pub type DefaultHashBuilder = std::collections::hash_map::RandomState;
108
109/// Defines the weight of a cache entry.
110///
111/// # Example
112///
113/// ```
114/// use quick_cache::{sync::Cache, Weighter};
115///
116/// #[derive(Clone)]
117/// struct StringWeighter;
118///
119/// impl Weighter<u64, String> for StringWeighter {
120///     fn weight(&self, _key: &u64, val: &String) -> u64 {
121///         // Be cautious about zero weights!
122///         val.len() as u64
123///     }
124/// }
125///
126/// let cache = Cache::with_weighter(100, 100_000, StringWeighter);
127/// cache.insert(1, "1".to_string());
128/// ```
129pub trait Weighter<Key, Val> {
130    /// Returns the weight of the cache item.
131    ///
132    /// For performance reasons, this function should be trivially cheap as
133    /// it's called during the cache eviction routine.
134    /// If weight is expensive to calculate, consider caching it alongside the value.
135    ///
136    /// Zero (0) weight items are allowed and will be ignored when looking for eviction
137    /// candidates. Such items can only be manually removed or overwritten.
138    ///
139    /// Note that it's undefined behavior for a cache item to change its weight.
140    /// The only exception to this is when Lifecycle::before_evict is called.
141    ///
142    /// It's also undefined behavior in release mode if the summing of weights overflows,
143    /// although this is unlikely to be a problem in practice.
144    fn weight(&self, key: &Key, val: &Val) -> u64;
145}
146
147/// Each cache entry weights exactly `1` unit of weight.
148#[derive(Debug, Clone, Default)]
149pub struct UnitWeighter;
150
151impl<Key, Val> Weighter<Key, Val> for UnitWeighter {
152    #[inline]
153    fn weight(&self, _key: &Key, _val: &Val) -> u64 {
154        1
155    }
156}
157
158/// Hooks into the lifetime of the cache items.
159///
160/// The functions should be small and very fast, otherwise the cache performance might be negatively affected.
161pub trait Lifecycle<Key, Val> {
162    type RequestState;
163
164    /// Returns whether the item is pinned. Items that are pinned can't be evicted.
165    /// Note that a pinned item can still be replaced with get_mut, insert, replace and similar APIs.
166    ///
167    /// Compared to zero (0) weight items, pinned items still consume (non-zero) weight even if they can't
168    /// be evicted. Furthermore, zero (0) weight items are separated from the other entries, which allows
169    /// having a large number of them without impacting performance, but moving them in/out or the evictable
170    /// section has a small cost. Pinning on the other hand doesn't separate entries, so during eviction
171    /// the cache may visit pinned entries but will ignore them.
172    #[allow(unused_variables)]
173    #[inline]
174    fn is_pinned(&self, key: &Key, val: &Val) -> bool {
175        false
176    }
177
178    /// Called before the insert request starts, e.g.: insert, replace.
179    fn begin_request(&self) -> Self::RequestState;
180
181    /// Called when a cache item is about to be evicted.
182    /// Note that value replacement (e.g. insertions for the same key) won't call this method.
183    ///
184    /// This is the only time the item can change its weight. If the item weight becomes zero (0) it
185    /// will be left in the cache, otherwise it'll still be removed. Zero (0) weight items aren't evictable
186    /// and are kept separated from the other items so it's possible to have a large number of them without
187    /// negatively affecting eviction performance.
188    #[allow(unused_variables)]
189    #[inline]
190    fn before_evict(&self, state: &mut Self::RequestState, key: &Key, val: &mut Val) {}
191
192    /// Called when an item is evicted.
193    fn on_evict(&self, state: &mut Self::RequestState, key: Key, val: Val);
194
195    /// Called after a request finishes, e.g.: insert, replace.
196    ///
197    /// Notes:
198    /// This will _not_ be called when using `_with_lifecycle` apis, which will return the RequestState instead.
199    /// This will _not_ be called if the request errored (e.g. a replace didn't find a value to replace).
200    /// If needed, Drop for RequestState can be used to detect these cases.
201    #[allow(unused_variables)]
202    #[inline]
203    fn end_request(&self, state: Self::RequestState) {}
204}
205
206/// The memory used by the cache
207///
208/// This struct exposes some implementation details, may change in the future
209#[non_exhaustive]
210#[derive(Debug, Copy, Clone)]
211pub struct MemoryUsed {
212    pub entries: usize,
213    pub map: usize,
214}
215
216impl MemoryUsed {
217    pub fn total(&self) -> usize {
218        self.entries + self.map
219    }
220}
221
222#[cfg(test)]
223mod tests {
224    use std::{
225        hash::Hash,
226        sync::{atomic::AtomicUsize, Arc},
227        time::Duration,
228    };
229
230    use super::*;
231    #[derive(Clone)]
232    struct StringWeighter;
233
234    impl Weighter<u64, String> for StringWeighter {
235        fn weight(&self, _key: &u64, val: &String) -> u64 {
236            val.len() as u64
237        }
238    }
239
240    #[test]
241    fn test_new() {
242        sync::Cache::<(u64, u64), u64>::new(0);
243        sync::Cache::<(u64, u64), u64>::new(1);
244        sync::Cache::<(u64, u64), u64>::new(2);
245        sync::Cache::<(u64, u64), u64>::new(3);
246        sync::Cache::<(u64, u64), u64>::new(usize::MAX);
247        sync::Cache::<u64, u64>::new(0);
248        sync::Cache::<u64, u64>::new(1);
249        sync::Cache::<u64, u64>::new(2);
250        sync::Cache::<u64, u64>::new(3);
251        sync::Cache::<u64, u64>::new(usize::MAX);
252    }
253
254    #[test]
255    fn test_capacity_one() {
256        // Sync cache with capacity 1 should be able to hold one item
257        let cache = sync::Cache::<u64, u64>::new(1);
258        cache.insert(1, 10);
259        assert_eq!(cache.get(&1), Some(10));
260        // Inserting a second key should evict the first
261        cache.insert(2, 20);
262        assert_eq!(cache.get(&2), Some(20));
263        assert_eq!(cache.get(&1), None);
264
265        // Unsync cache with capacity 1 should also work
266        let mut cache = unsync::Cache::<u64, u64>::new(1);
267        cache.insert(1, 10);
268        assert_eq!(cache.get(&1), Some(&10));
269        cache.insert(2, 20);
270        assert_eq!(cache.get(&2), Some(&20));
271        assert_eq!(cache.get(&1), None);
272
273        // Capacity 0 should store nothing
274        let cache = sync::Cache::<u64, u64>::new(0);
275        cache.insert(1, 10);
276        assert_eq!(cache.get(&1), None);
277    }
278
279    #[test]
280    fn test_custom_cost() {
281        let cache = sync::Cache::with_weighter(100, 100_000, StringWeighter);
282        cache.insert(1, "1".to_string());
283        cache.insert(54, "54".to_string());
284        cache.insert(1000, "1000".to_string());
285        assert_eq!(cache.get(&1000).unwrap(), "1000");
286    }
287
288    #[test]
289    fn test_change_get_mut_change_weight() {
290        let mut cache = unsync::Cache::with_weighter(100, 100_000, StringWeighter);
291        cache.insert(1, "1".to_string());
292        assert_eq!(cache.get(&1).unwrap(), "1");
293        assert_eq!(cache.weight(), 1);
294        let _old = {
295            cache
296                .get_mut(&1)
297                .map(|mut v| std::mem::replace(&mut *v, "11".to_string()))
298        };
299        let _old = {
300            cache
301                .get_mut(&1)
302                .map(|mut v| std::mem::replace(&mut *v, "".to_string()))
303        };
304        assert_eq!(cache.get(&1).unwrap(), "");
305        assert_eq!(cache.weight(), 0);
306        cache.validate(false);
307    }
308
309    #[derive(Debug, Hash)]
310    pub struct Pair<A, B>(pub A, pub B);
311
312    impl<A, B, C, D> PartialEq<(A, B)> for Pair<C, D>
313    where
314        C: PartialEq<A>,
315        D: PartialEq<B>,
316    {
317        fn eq(&self, rhs: &(A, B)) -> bool {
318            self.0 == rhs.0 && self.1 == rhs.1
319        }
320    }
321
322    impl<A, B, X> Equivalent<X> for Pair<A, B>
323    where
324        Pair<A, B>: PartialEq<X>,
325        A: Hash + Eq,
326        B: Hash + Eq,
327    {
328        fn equivalent(&self, other: &X) -> bool {
329            *self == *other
330        }
331    }
332
333    #[test]
334    fn test_equivalent() {
335        let mut cache = unsync::Cache::new(5);
336        cache.insert(("square".to_string(), 2022), "blue".to_string());
337        cache.insert(("square".to_string(), 2023), "black".to_string());
338        assert_eq!(cache.get(&Pair("square", 2022)).unwrap(), "blue");
339    }
340
341    #[test]
342    fn test_borrow_keys() {
343        let cache = sync::Cache::<(Vec<u8>, Vec<u8>), u64>::new(0);
344        cache.get(&Pair(&b""[..], &b""[..]));
345        let cache = sync::Cache::<(String, String), u64>::new(0);
346        cache.get(&Pair("", ""));
347    }
348
349    #[test]
350    #[cfg_attr(miri, ignore)]
351    fn test_get_or_insert() {
352        use rand::prelude::*;
353        for _i in 0..2000 {
354            dbg!(_i);
355            let mut entered = AtomicUsize::default();
356            let cache = sync::Cache::<(u64, u64), u64>::new(100);
357            const THREADS: usize = 100;
358            let wg = std::sync::Barrier::new(THREADS);
359            let solve_at = rand::rng().random_range(0..THREADS);
360            std::thread::scope(|s| {
361                for _ in 0..THREADS {
362                    s.spawn(|| {
363                        wg.wait();
364                        let result = cache.get_or_insert_with(&(1, 1), || {
365                            let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
366                            if before == solve_at {
367                                Ok(1)
368                            } else {
369                                Err(())
370                            }
371                        });
372                        assert!(matches!(result, Ok(1) | Err(())));
373                    });
374                }
375            });
376            assert_eq!(*entered.get_mut(), solve_at + 1);
377        }
378    }
379
380    #[test]
381    fn test_get_or_insert_unsync() {
382        let mut cache = unsync::Cache::<u64, u64>::new(100);
383        let guard = cache.get_ref_or_guard(&0).unwrap_err();
384        guard.insert(0);
385        assert_eq!(cache.get_ref_or_guard(&0).ok().copied(), Some(0));
386        let guard = cache.get_mut_or_guard(&1).err().unwrap();
387        guard.insert(1);
388        let v = *cache.get_mut_or_guard(&1).ok().unwrap().unwrap();
389        assert_eq!(v, 1);
390        let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
391        assert_eq!(result, Ok(Some(&0)));
392        let result = cache.get_or_insert_with::<_, ()>(&1, || panic!());
393        assert_eq!(result, Ok(Some(&1)));
394        let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
395        assert_eq!(result, Ok(Some(&3)));
396        let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
397        assert_eq!(result, Err(()));
398    }
399
400    #[tokio::test]
401    async fn test_get_or_insert_sync() {
402        use crate::sync::*;
403        let cache = sync::Cache::<u64, u64>::new(100);
404        let GuardResult::Guard(guard) = cache.get_value_or_guard(&0, None) else {
405            panic!();
406        };
407        guard.insert(0).unwrap();
408        let GuardResult::Value(v) = cache.get_value_or_guard(&0, None) else {
409            panic!();
410        };
411        assert_eq!(v, 0);
412        let Err(guard) = cache.get_value_or_guard_async(&1).await else {
413            panic!();
414        };
415        guard.insert(1).unwrap();
416        let Ok(v) = cache.get_value_or_guard_async(&1).await else {
417            panic!();
418        };
419        assert_eq!(v, 1);
420
421        let result = cache.get_or_insert_with::<_, ()>(&0, || panic!());
422        assert_eq!(result, Ok(0));
423        let result = cache.get_or_insert_with::<_, ()>(&3, || Ok(3));
424        assert_eq!(result, Ok(3));
425        let result = cache.get_or_insert_with::<_, ()>(&4, || Err(()));
426        assert_eq!(result, Err(()));
427        let result = cache
428            .get_or_insert_async::<_, ()>(&0, async { panic!() })
429            .await;
430        assert_eq!(result, Ok(0));
431        let result = cache
432            .get_or_insert_async::<_, ()>(&4, async { Err(()) })
433            .await;
434        assert_eq!(result, Err(()));
435        let result = cache
436            .get_or_insert_async::<_, ()>(&4, async { Ok(4) })
437            .await;
438        assert_eq!(result, Ok(4));
439    }
440
441    #[test]
442    fn test_retain_unsync() {
443        let mut cache = unsync::Cache::<u64, u64>::new(100);
444        let ranges = 0..10;
445        for i in ranges.clone() {
446            let guard = cache.get_ref_or_guard(&i).unwrap_err();
447            guard.insert(i);
448            assert_eq!(cache.get_ref_or_guard(&i).ok().copied(), Some(i));
449        }
450        let small = 3;
451        cache.retain(|&key, &val| val > small && key > small);
452        for i in ranges.clone() {
453            let actual = cache.get(&i);
454            if i > small {
455                assert!(actual.is_some());
456                assert_eq!(*actual.unwrap(), i);
457            } else {
458                assert!(actual.is_none());
459            }
460        }
461        let big = 7;
462        cache.retain(|&key, &val| val < big && key < big);
463        for i in ranges {
464            let actual = cache.get(&i);
465            if i > small && i < big {
466                assert!(actual.is_some());
467                assert_eq!(*actual.unwrap(), i);
468            } else {
469                assert!(actual.is_none());
470            }
471        }
472    }
473
474    #[tokio::test]
475    async fn test_retain_sync() {
476        use crate::sync::*;
477        let cache = Cache::<u64, u64>::new(100);
478        let ranges = 0..10;
479        for i in ranges.clone() {
480            let GuardResult::Guard(guard) = cache.get_value_or_guard(&i, None) else {
481                panic!();
482            };
483            guard.insert(i).unwrap();
484            let GuardResult::Value(v) = cache.get_value_or_guard(&i, None) else {
485                panic!();
486            };
487            assert_eq!(v, i);
488        }
489        let small = 4;
490        cache.retain(|&key, &val| val > small && key > small);
491        for i in ranges.clone() {
492            let actual = cache.get(&i);
493            if i > small {
494                assert!(actual.is_some());
495                assert_eq!(actual.unwrap(), i);
496            } else {
497                assert!(actual.is_none());
498            }
499        }
500        let big = 8;
501        cache.retain(|&key, &val| val < big && key < big);
502        for i in ranges {
503            let actual = cache.get(&i);
504            if i > small && i < big {
505                assert!(actual.is_some());
506                assert_eq!(actual.unwrap(), i);
507            } else {
508                assert!(actual.is_none());
509            }
510        }
511    }
512
513    #[test]
514    #[cfg_attr(miri, ignore)]
515    fn test_value_or_guard() {
516        use crate::sync::*;
517        use rand::prelude::*;
518        for _i in 0..2000 {
519            dbg!(_i);
520            let mut entered = AtomicUsize::default();
521            let cache = sync::Cache::<(u64, u64), u64>::new(100);
522            const THREADS: usize = 100;
523            let wg = std::sync::Barrier::new(THREADS);
524            let solve_at = rand::rng().random_range(0..THREADS);
525            std::thread::scope(|s| {
526                for _ in 0..THREADS {
527                    s.spawn(|| {
528                        wg.wait();
529                        loop {
530                            match cache.get_value_or_guard(&(1, 1), Some(Duration::from_millis(1)))
531                            {
532                                GuardResult::Value(v) => assert_eq!(v, 1),
533                                GuardResult::Guard(g) => {
534                                    let before =
535                                        entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
536                                    if before == solve_at {
537                                        g.insert(1).unwrap();
538                                    }
539                                }
540                                GuardResult::Timeout => continue,
541                            }
542                            break;
543                        }
544                    });
545                }
546            });
547            assert_eq!(*entered.get_mut(), solve_at + 1);
548        }
549    }
550
551    #[tokio::test(flavor = "multi_thread")]
552    #[cfg_attr(miri, ignore)]
553    async fn test_get_or_insert_async() {
554        use rand::prelude::*;
555        for _i in 0..5000 {
556            dbg!(_i);
557            let entered = Arc::new(AtomicUsize::default());
558            let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
559            const TASKS: usize = 100;
560            let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
561            let solve_at = rand::rng().random_range(0..TASKS);
562            let mut tasks = Vec::new();
563            for _ in 0..TASKS {
564                let cache = cache.clone();
565                let wg = wg.clone();
566                let entered = entered.clone();
567                let task = tokio::spawn(async move {
568                    wg.wait().await;
569                    let result = cache
570                        .get_or_insert_async(&(1, 1), async {
571                            let before = entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
572                            if before == solve_at {
573                                Ok(1)
574                            } else {
575                                Err(())
576                            }
577                        })
578                        .await;
579                    assert!(matches!(result, Ok(1) | Err(())));
580                });
581                tasks.push(task);
582            }
583            for task in tasks {
584                task.await.unwrap();
585            }
586            assert_eq!(cache.get(&(1, 1)), Some(1));
587            assert_eq!(
588                entered.load(std::sync::atomic::Ordering::Relaxed),
589                solve_at + 1
590            );
591        }
592    }
593
594    #[tokio::test(flavor = "multi_thread")]
595    #[cfg_attr(miri, ignore)]
596    async fn test_value_or_guard_async() {
597        use rand::prelude::*;
598        for _i in 0..5000 {
599            dbg!(_i);
600            let entered = Arc::new(AtomicUsize::default());
601            let cache = Arc::new(sync::Cache::<(u64, u64), u64>::new(100));
602            const TASKS: usize = 100;
603            let wg = Arc::new(tokio::sync::Barrier::new(TASKS));
604            let solve_at = rand::rng().random_range(0..TASKS);
605            let mut tasks = Vec::new();
606            for _ in 0..TASKS {
607                let cache = cache.clone();
608                let wg = wg.clone();
609                let entered = entered.clone();
610                let task = tokio::spawn(async move {
611                    wg.wait().await;
612                    loop {
613                        match tokio::time::timeout(
614                            Duration::from_millis(1),
615                            cache.get_value_or_guard_async(&(1, 1)),
616                        )
617                        .await
618                        {
619                            Ok(Ok(r)) => assert_eq!(r, 1),
620                            Ok(Err(g)) => {
621                                let before =
622                                    entered.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
623                                if before == solve_at {
624                                    g.insert(1).unwrap();
625                                }
626                            }
627                            Err(_) => continue,
628                        }
629                        break;
630                    }
631                });
632                tasks.push(task);
633            }
634            for task in tasks {
635                task.await.unwrap();
636            }
637            assert_eq!(cache.get(&(1, 1)), Some(1));
638            assert_eq!(
639                entered.load(std::sync::atomic::Ordering::Relaxed),
640                solve_at + 1
641            );
642        }
643    }
644}
quick_cache/lib.rs

quick_cache/
lib.rs
