Quick Cache

Lightweight and high performance concurrent cache optimized for low cache overhead.

• Small overhead compared to a concurrent hash table
• Scan resistant and high hit rate caching policy (S3-FIFO)
• User defined weight per item
• Scales well with the number of threads
• Atomic operations with get_or_insert and get_value_or_guard functions
• Atomic async operations with get_or_insert_async and get_value_or_guard_async functions
• Non-blocking methods that return immediately on lock contention.
• Closure-based entry API for atomic inspect-and-act patterns (keep, remove, replace)
• Supports item pinning
• Iteration and draining
• Handles zero weight items efficiently
• Allows for customizable lifecycle hooks (e.g. can be used to implement eviction listeners)
• Doesn't use background threads
• Only trivially verifiable usages of unsafe
• Small dependency tree

The implementation is optimized for use cases where the cache access times and overhead can add up to be a significant cost. Features like: time to live, event listeners and others; are partially or not implemented in Quick Cache. If you need these features you may want to take a look at the Moka crate.

Examples

Basic usage

use quick_cache::unsync::Cache;

fn main() {
    let mut cache = Cache::new(5);
    cache.insert("square", "blue");
    cache.insert("circle", "black");
    assert_eq!(*cache.get(&"square").unwrap(), "blue");
    assert_eq!(*cache.get(&"circle").unwrap(), "black");
}

A cache with custom item weights. In this case according to the string length of the value.

use quick_cache::{Weighter, sync::Cache};

#[derive(Clone)]
struct StringWeighter;

impl Weighter<u64, String> for StringWeighter {
    fn weight(&self, _key: &u64, val: &String) -> u64 {
        // Be cautious about zero weights!
        val.len() as u64
    }
}

fn main() {
    let cache = Cache::with_weighter(100, 100_000, StringWeighter);
    cache.insert(1, "1".to_string());
    cache.insert(54, "54".to_string());
    cache.insert(1000, "1000".to_string());
    assert_eq!(cache.get(&1000).unwrap(), "1000");
}

Atomic inspect-and-act with the entry API

use quick_cache::sync::{Cache, EntryAction, EntryResult};

fn main() {
    let cache: Cache<u64, u64> = Cache::new(100);

    // Insert-or-get: if absent, compute and insert; if present, return cached
    let result = cache.entry(&0, None, |_key, val| EntryAction::Retain(*val));
    let value = match result {
        EntryResult::Retained(v) => v,
        EntryResult::Vacant(guard) => {
            let v = 42; // expensive computation
            guard.insert(v).unwrap();
            v
        }
        _ => unreachable!(),
    };
    assert_eq!(value, 42);

    // Conditionally remove: evict entries below a threshold
    let result = cache.entry(&0, None, |_key, val| {
        if *val < 100 {
            EntryAction::<()>::Remove
        } else {
            EntryAction::Retain(())
        }
    });
    assert!(matches!(result, EntryResult::Removed(0, 42)));
}

Using the Equivalent trait for complex keys

use quick_cache::{sync::Cache, Equivalent};

#[derive(Debug, Hash)]
pub struct Pair<A, B>(pub A, pub B);

impl<A, B, C, D> Equivalent<(C, D)> for Pair<A, B>
where
    A: PartialEq<C>,
    B: PartialEq<D>,
{
    fn equivalent(&self, rhs: &(C, D)) -> bool {
        self.0 == rhs.0 && self.1 == rhs.1
    }
}

fn main() {
    let cache: Cache<(String, i32), String> = Cache::new(5);
    cache.insert(("square".to_string(), 2022), "blue".to_string());
    cache.insert(("square".to_string(), 2023), "black".to_string());
    assert_eq!(cache.get(&Pair("square", 2022)).unwrap(), "blue");
}

Benchmarks

Since this crate is performance oriented it needs some comparisons. That said, benchmarks can be misleading so take everything with a pinch of salt.

Benchmarks performed with mokabench in a x64 Linux OS + Intel i9-12900H CPU.

Trace 1 (S3 from the Arc paper)

Cache	Max Capacity	Clients	Inserts	Reads	Hit Ratio	Duration Secs
QuickCache	100000	1	14300769	16407702	12.841	2.196
QuickCache	100000	3	14301124	16407702	12.839	1.279
QuickCache	100000	6	14300809	16407702	12.841	0.798
LRU+Mutex	100000	1	16025830	16407702	2.327	2.422
TinyUFO	100000	1	15685351	16407702	4.403	11.641
TinyUFO	100000	3	15900217	16407702	3.093	8.828
TinyUFO	100000	6	15918936	16407702	2.979	8.104
Mini Moka	100000	1	14695340	16407702	10.436	9.399
Mini Moka	100000	3	14679119	16407702	10.535	8.490
Mini Moka	100000	6	14706822	16407702	10.366	8.064
QuickCache	400000	1	9435745	16407702	42.492	2.537
QuickCache	400000	3	9437141	16407702	42.483	1.323
QuickCache	400000	6	9436549	16407702	42.487	0.899
LRU+Mutex	400000	1	14432404	16407702	12.039	2.766
TinyUFO	400000	1	11455971	16407702	30.179	14.234
TinyUFO	400000	3	12405638	16407702	24.391	8.695
TinyUFO	400000	6	12551335	16407702	23.503	7.008
Mini Moka	400000	1	9427172	16407702	42.544	8.511
Mini Moka	400000	3	9584914	16407702	41.583	6.624
Mini Moka	400000	6	9656084	16407702	41.149	6.613
QuickCache	800000	1	5184786	16407702	68.400	3.207
QuickCache	800000	3	5185210	16407702	68.398	1.353
QuickCache	800000	6	5185337	16407702	68.397	0.743
LRU+Mutex	800000	1	7120978	16407702	56.600	2.613
TinyUFO	800000	1	5598215	16407702	65.881	10.043
TinyUFO	800000	3	6007956	16407702	63.383	5.077
TinyUFO	800000	6	6071806	16407702	62.994	3.789
Mini Moka	800000	1	4872358	16407702	70.304	8.574
Mini Moka	800000	3	5012764	16407702	69.449	5.363
Mini Moka	800000	6	5529311	16407702	66.301	4.551

Trace 2 (DS1 from the Arc paper)

Cache	Max Capacity	Clients	Inserts	Reads	Hit Ratio	Duration Secs
QuickCache	1000000	1	37208683	43704979	14.864	9.883
QuickCache	1000000	3	37196302	43704979	14.892	4.546
QuickCache	1000000	6	37196402	43704979	14.892	3.585
LRU+Mutex	1000000	1	42356290	43704979	3.086	8.901
TinyUFO	1000000	1	42093670	43704979	3.687	60.135
TinyUFO	1000000	3	42203137	43704979	3.436	35.306
TinyUFO	1000000	6	42214889	43704979	3.409	25.440
Mini Moka	1000000	1	37188446	43704979	14.910	25.833
Mini Moka	1000000	3	37332123	43704979	14.582	23.078
Mini Moka	1000000	6	38104018	43704979	12.815	23.571
QuickCache	4000000	1	24156843	43704979	44.727	9.497
QuickCache	4000000	3	24159591	43704979	44.721	4.257
QuickCache	4000000	6	24204044	43704979	44.619	2.777
LRU+Mutex	4000000	1	34856997	43704979	20.245	10.735
TinyUFO	4000000	1	32607709	43704979	25.391	49.380
TinyUFO	4000000	3	32810383	43704979	24.928	26.440
TinyUFO	4000000	6	32840752	43704979	24.858	20.390
Mini Moka	4000000	1	23863892	43704979	45.398	26.103
Mini Moka	4000000	3	23865870	43704979	45.393	19.896
Mini Moka	4000000	6	25152629	43704979	42.449	17.912
QuickCache	8000000	1	13405437	43704979	69.327	7.703
QuickCache	8000000	3	13406862	43704979	69.324	3.598
QuickCache	8000000	6	13406780	43704979	69.324	2.243
LRU+Mutex	8000000	1	24896662	43704979	43.035	8.995
TinyUFO	8000000	1	20143204	43704979	53.911	28.245
TinyUFO	8000000	3	20339486	43704979	53.462	14.967
TinyUFO	8000000	6	20364270	43704979	53.405	11.206
Mini Moka	8000000	1	14227354	43704979	67.447	29.082
Mini Moka	8000000	3	13762562	43704979	68.510	17.060
Mini Moka	8000000	6	14926093	43704979	65.848	12.294

Trace 3 (SPC1 from the Arc paper)

Cache	Max Capacity	Clients	Inserts	Reads	Hit Ratio	Duration Secs
QuickCache	500000	1	36994843	41351279	10.535	7.880
LRU+Mutex	500000	1	39942249	41351279	3.407	9.820
TinyUFO	500000	1	39197208	41351279	5.209	49.395
Mini Moka	500000	1	36231669	41351279	12.381	25.467
QuickCache	2000000	1	24123918	41351279	41.661	14.611
LRU+Mutex	2000000	1	30181071	41351279	27.013	10.768
TinyUFO	2000000	1	27173449	41351279	34.286	46.476
Mini Moka	2000000	1	24032624	41351279	41.882	31.064
QuickCache	30000000	1	6050363	41351279	85.368	8.170
LRU+Mutex	30000000	1	6050363	41351279	85.368	8.594
TinyUFO	30000000	1	6050363	41351279	85.368	14.065
Mini Moka	30000000	1	6050363	41351279	85.368	34.452

Notes:

• LRU+Mutex: hashlink crate + std::sync::Mutex
• SPC1 only includes 1 client to save space, it follows the same trend as other traces.
• Other Moka variants not included to save space, they perform similarly or worse than Mini Moka. Full results

References

• CLOCK-Pro: An Effective Improvement of the CLOCK Replacement (pdf)
• FIFO queues are all you need for cache eviction (pdf)
• Caffeine (source code)
• Cache2k (source code)

License

This project is licensed under the MIT license.