quick_cache 0.6.9

Lightweight and high performance concurrent cache
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201

# Quick Cache

[![Crates.io](https://img.shields.io/crates/v/quick_cache.svg)](https://crates.io/crates/quick_cache)
[![Docs](https://docs.rs/quick_cache/badge.svg)](https://docs.rs/quick_cache/latest)
[![CI](https://github.com/arthurprs/quick-cache/actions/workflows/ci.yml/badge.svg)](https://github.com/arthurprs/quick-cache/actions/workflows/ci.yml)

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

* Small overhead compared to a concurrent hash table
* Scan resistent and high hit rate caching policy
* 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
* Supports item pinning
* 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, iterators, 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](https://crates.io/crates/moka) crate.

## Examples

Basic usage

```rust
use quick_cache::unsync::Cache;

fn main() {
    let 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.

```rust
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 cautions out 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");
}
```

Using the `Equivalent` trait for complex keys

```rust
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](https://github.com/moka-rs/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](https://github.com/arthurprs/quick-cache/issues/49#issuecomment-2323322103)

## References

* [CLOCK-Pro: An Effective Improvement of the CLOCK Replacement (pdf)](https://www.usenix.org/legacy/events/usenix05/tech/general/full_papers/jiang/jiang.pdf)
* [FIFO queues are all you need for cache eviction (pdf)](https://dl.acm.org/doi/10.1145/3600006.3613147)
* [Caffeine (source code)](https://github.com/ben-manes/caffeine)
* [Cache2k (source code)](https://github.com/cache2k/cache2k)

## License

This project is licensed under the MIT license.