A better Rust ATProto crate
1# Vendored in until upstream PR for wasm compat is merged or I reimplement.
2
3# **PLEASE DO NOT TAKE ISSUES WITH THIS IMPL TO UPSTREAM DEVS**
4
5# Mini Moka
6
7[![GitHub Actions][gh-actions-badge]][gh-actions]
8[![crates.io release][release-badge]][crate]
9[![docs][docs-badge]][docs]
10[![dependency status][deps-rs-badge]][deps-rs]
11<!-- [![coverage status][coveralls-badge]][coveralls] -->
12[![license][license-badge]](#license)
13<!-- [](https://app.fossa.com/projects/git%2Bgithub.com%2Fmoka-rs%2Fmini-moka?ref=badge_shield) -->
14
15Mini Moka is a fast, concurrent cache library for Rust. Mini Moka is a light edition
16of [Moka][moka-git].
17
18Mini Moka provides cache implementations on top of hash maps. They support full
19concurrency of retrievals and a high expected concurrency for updates. Mini Moka also
20provides a non-thread-safe cache implementation for single thread applications.
21
22All caches perform a best-effort bounding of a hash map using an entry replacement
23algorithm to determine which entries to evict when the capacity is exceeded.
24
25[gh-actions-badge]: https://github.com/moka-rs/mini-moka/workflows/CI/badge.svg
26[release-badge]: https://img.shields.io/crates/v/mini-moka.svg
27[docs-badge]: https://docs.rs/mini-moka/badge.svg
28[deps-rs-badge]: https://deps.rs/repo/github/moka-rs/mini-moka/status.svg
29<!-- [coveralls-badge]: https://coveralls.io/repos/github/mini-moka-rs/moka/badge.svg?branch=main -->
30[license-badge]: https://img.shields.io/crates/l/mini-moka.svg
31<!-- [fossa-badge]: https://app.fossa.com/api/projects/git%2Bgithub.com%2Fmoka-rs%2Fmini-moka.svg?type=shield -->
32
33[gh-actions]: https://github.com/moka-rs/mini-moka/actions?query=workflow%3ACI
34[crate]: https://crates.io/crates/mini-moka
35[docs]: https://docs.rs/mini-moka
36[deps-rs]: https://deps.rs/repo/github/moka-rs/mini-moka
37<!-- [coveralls]: https://coveralls.io/github/moka-rs/mini-moka?branch=main -->
38<!-- [fossa]: https://app.fossa.com/projects/git%2Bgithub.com%2Fmoka-rs%2Fmini-moka?ref=badge_shield -->
39
40[moka-git]: https://github.com/moka-rs/moka
41[caffeine-git]: https://github.com/ben-manes/caffeine
42
43
44## Features
45
46- Thread-safe, highly concurrent in-memory cache implementation.
47- A cache can be bounded by one of the followings:
48 - The maximum number of entries.
49 - The total weighted size of entries. (Size aware eviction)
50- Maintains near optimal hit ratio by using an entry replacement algorithms inspired
51 by Caffeine:
52 - Admission to a cache is controlled by the Least Frequently Used (LFU) policy.
53 - Eviction from a cache is controlled by the Least Recently Used (LRU) policy.
54 - [More details and some benchmark results are available here][tiny-lfu].
55- Supports expiration policies:
56 - Time to live
57 - Time to idle
58
59<!--
60Mini Moka provides a rich and flexible feature set while maintaining high hit ratio
61and a high level of concurrency for concurrent access. However, it may not be as fast
62as other caches, especially those that focus on much smaller feature sets.
63
64If you do not need features like: time to live, and size aware eviction, you may want
65to take a look at the [Quick Cache][quick-cache] crate.
66-->
67
68[tiny-lfu]: https://github.com/moka-rs/moka/wiki#admission-and-eviction-policies
69<!-- [quick-cache]: https://crates.io/crates/quick_cache -->
70
71
72## Change Log
73
74- [CHANGELOG.md](https://github.com/moka-rs/mini-moka/blob/main/CHANGELOG.md)
75
76
77## Table of Contents
78
79- [Features](#features)
80- [Change Log](#change-log)
81- [Usage](#usage)
82- [Example: Synchronous Cache](#example-synchronous-cache)
83- [Avoiding to clone the value at `get`](#avoiding-to-clone-the-value-at-get)
84- Examples (Part 2)
85 - [Size Aware Eviction](#example-size-aware-eviction)
86 - [Expiration Policies](#example-expiration-policies)
87- [Minimum Supported Rust Versions](#minimum-supported-rust-versions)
88- [Developing Mini Moka](#developing-mini-moka)
89- [Credits](#credits)
90- [License](#license)
91
92
93## Usage
94
95Add this to your `Cargo.toml`:
96
97```toml
98[dependencies]
99mini_moka = "0.10"
100```
101
102
103## Example: Synchronous Cache
104
105The thread-safe, synchronous caches are defined in the `sync` module.
106
107Cache entries are manually added using `insert` method, and are stored in the cache
108until either evicted or manually invalidated.
109
110Here's an example of reading and updating a cache by using multiple threads:
111
112```rust
113// Use the synchronous cache.
114use mini_moka_wasm::sync::Cache;
115
116use std::thread;
117
118fn value(n: usize) -> String {
119 format!("value {}", n)
120}
121
122fn main() {
123 const NUM_THREADS: usize = 16;
124 const NUM_KEYS_PER_THREAD: usize = 64;
125
126 // Create a cache that can store up to 10,000 entries.
127 let cache = Cache::new(10_000);
128
129 // Spawn threads and read and update the cache simultaneously.
130 let threads: Vec<_> = (0..NUM_THREADS)
131 .map(|i| {
132 // To share the same cache across the threads, clone it.
133 // This is a cheap operation.
134 let my_cache = cache.clone();
135 let start = i * NUM_KEYS_PER_THREAD;
136 let end = (i + 1) * NUM_KEYS_PER_THREAD;
137
138 thread::spawn(move || {
139 // Insert 64 entries. (NUM_KEYS_PER_THREAD = 64)
140 for key in start..end {
141 my_cache.insert(key, value(key));
142 // get() returns Option<String>, a clone of the stored value.
143 assert_eq!(my_cache.get(&key), Some(value(key)));
144 }
145
146 // Invalidate every 4 element of the inserted entries.
147 for key in (start..end).step_by(4) {
148 my_cache.invalidate(&key);
149 }
150 })
151 })
152 .collect();
153
154 // Wait for all threads to complete.
155 threads.into_iter().for_each(|t| t.join().expect("Failed"));
156
157 // Verify the result.
158 for key in 0..(NUM_THREADS * NUM_KEYS_PER_THREAD) {
159 if key % 4 == 0 {
160 assert_eq!(cache.get(&key), None);
161 } else {
162 assert_eq!(cache.get(&key), Some(value(key)));
163 }
164 }
165}
166```
167
168
169## Avoiding to clone the value at `get`
170
171For the concurrent cache (`sync` cache), the return type of `get` method is
172`Option<V>` instead of `Option<&V>`, where `V` is the value type. Every time `get` is
173called for an existing key, it creates a clone of the stored value `V` and returns
174it. This is because the `Cache` allows concurrent updates from threads so a value
175stored in the cache can be dropped or replaced at any time by any other thread. `get`
176cannot return a reference `&V` as it is impossible to guarantee the value outlives
177the reference.
178
179If you want to store values that will be expensive to clone, wrap them by
180`std::sync::Arc` before storing in a cache. [`Arc`][rustdoc-std-arc] is a thread-safe
181reference-counted pointer and its `clone()` method is cheap.
182
183[rustdoc-std-arc]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html
184
185```rust,ignore
186use std::sync::Arc;
187
188let key = ...
189let large_value = vec![0u8; 2 * 1024 * 1024]; // 2 MiB
190
191// When insert, wrap the large_value by Arc.
192cache.insert(key.clone(), Arc::new(large_value));
193
194// get() will call Arc::clone() on the stored value, which is cheap.
195cache.get(&key);
196```
197
198
199## Example: Size Aware Eviction
200
201If different cache entries have different "weights" — e.g. each entry has
202different memory footprints — you can specify a `weigher` closure at the cache
203creation time. The closure should return a weighted size (relative size) of an entry
204in `u32`, and the cache will evict entries when the total weighted size exceeds its
205`max_capacity`.
206
207```rust
208use std::convert::TryInto;
209use mini_moka_wasm::sync::Cache;
210
211fn main() {
212 let cache = Cache::builder()
213 // A weigher closure takes &K and &V and returns a u32 representing the
214 // relative size of the entry. Here, we use the byte length of the value
215 // String as the size.
216 .weigher(|_key, value: &String| -> u32 {
217 value.len().try_into().unwrap_or(u32::MAX)
218 })
219 // This cache will hold up to 32MiB of values.
220 .max_capacity(32 * 1024 * 1024)
221 .build();
222 cache.insert(0, "zero".to_string());
223}
224```
225
226Note that weighted sizes are not used when making eviction selections.
227
228
229## Example: Expiration Policies
230
231Mini Moka supports the following expiration policies:
232
233- **Time to live**: A cached entry will be expired after the specified duration past
234 from `insert`.
235- **Time to idle**: A cached entry will be expired after the specified duration past
236 from `get` or `insert`.
237
238To set them, use the `CacheBuilder`.
239
240```rust
241use mini_moka_wasm::sync::Cache;
242use std::time::Duration;
243
244fn main() {
245 let cache = Cache::builder()
246 // Time to live (TTL): 30 minutes
247 .time_to_live(Duration::from_secs(30 * 60))
248 // Time to idle (TTI): 5 minutes
249 .time_to_idle(Duration::from_secs( 5 * 60))
250 // Create the cache.
251 .build();
252
253 // This entry will expire after 5 minutes (TTI) if there is no get().
254 cache.insert(0, "zero");
255
256 // This get() will extend the entry life for another 5 minutes.
257 cache.get(&0);
258
259 // Even though we keep calling get(), the entry will expire
260 // after 30 minutes (TTL) from the insert().
261}
262```
263
264### A note on expiration policies
265
266The cache builders will panic if configured with either `time_to_live` or `time to
267idle` longer than 1000 years. This is done to protect against overflow when computing
268key expiration.
269
270
271## Minimum Supported Rust Versions
272
273Mini Moka's minimum supported Rust versions (MSRV) are the followings:
274
275| Feature | MSRV |
276|:-----------------|:--------------------------:|
277| default features | Rust 1.76.0 (Feb 8, 2024) |
278
279It will keep a rolling MSRV policy of at least 6 months. If only the default features
280are enabled, MSRV will be updated conservatively. When using other features, MSRV
281might be updated more frequently, up to the latest stable. In both cases, increasing
282MSRV is _not_ considered a semver-breaking change.
283
284
285## Developing Mini Moka
286
287**Running All Tests**
288
289To run all tests including doc tests on the README, use the following command:
290
291```console
292$ RUSTFLAGS='--cfg trybuild' cargo test --all-features
293```
294
295
296**Generating the Doc**
297
298```console
299$ cargo +nightly -Z unstable-options --config 'build.rustdocflags="--cfg docsrs"' \
300 doc --no-deps
301```
302
303
304## Credits
305
306### Caffeine
307
308Mini Moka's architecture is heavily inspired by the [Caffeine][caffeine-git] library
309for Java. Thanks go to Ben Manes and all contributors of Caffeine.
310
311
312## License
313
314Mini Moka is distributed under either of
315
316- The MIT license
317- The Apache License (Version 2.0)
318
319at your option.
320
321See [LICENSE-MIT](LICENSE-MIT) and [LICENSE-APACHE](LICENSE-APACHE) for details.
322
323<!-- [](https://app.fossa.com/projects/git%2Bgithub.com%2Fmoka-rs%2Fmini-moka?ref=badge_large) -->