cache-mod 0.6.0

High-performance in-process caching with multiple eviction policies (LRU, LFU, TinyLFU, TTL, size-bounded). Async-safe, lock-minimized internals. Typed key-value API. No dependency on any external store.
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

# cache-mod v0.5.0 — TinyLFU, SizedCache, property tests, benchmarks

**The eviction-policy roster is complete.** The public surface that started landing at 0.2.0 now contains all five policies the crate set out to ship: `LruCache`, `LfuCache`, `TtlCache`, `TinyLfuCache`, and `SizedCache`, all behind a single [`Cache`] trait. Property tests and Criterion benchmarks join the suite. Lock-free / arena-backed internals slip to 0.6.0 — a non-API change that can land at any time without breaking call-sites.

## What is cache-mod?

High-performance in-process caching for Rust with five eviction policies all behind one trait. Async-safe (`&self` everywhere, `Send + Sync` cache instances), lock-minimized internals, typed key-value API. No dependency on any external store.

## What's in 0.5.0

### `TinyLfuCache<K, V>` — admission-controlled LRU

The headline policy. A fixed-size **Count-Min Sketch** observes every key the cache encounters (hit or miss), giving the cache a frequency estimate for keys it does not currently store. On capacity overflow, the cache compares the incoming candidate's estimated frequency to the LRU victim's; **admission is granted only if the candidate is warmer**. One-hit-wonders are rejected at the door instead of displacing hot entries.

This is a deliberate semantic deviation from the other four cache types and is surfaced prominently in the type docs: a successful `insert` call on `TinyLfuCache` **does not guarantee** the value is in the cache. If your code path needs strict insertion guarantees, use `LruCache` or `LfuCache` — they always admit.

Reference implementation parameters:

- depth-4 Count-Min Sketch, `u8` saturating counters
- width = `max(64, 2 × capacity)`, rounded to the next power of two
- W-TinyLFU "aging" step: every `10 × capacity` increments, every counter is right-shifted by 1, so the sketch stays responsive to workload shifts
- main cache uses LRU access ordering; the eviction victim is always the least-recently-accessed entry
- single `Mutex<Inner>` for now (consistent with the rest of the family); the lock-strategy upgrade lands in 0.6.0

The SLRU segmentation and doorkeeper Bloom filter from the full W-TinyLFU paper are not part of the 0.5.0 reference impl — they are good candidates for a 1.x quality pass.

### `SizedCache<K, V>` — byte-bound capacity

The first cache type in the crate where the capacity bound is **not** entry count. Each value is weighed at insert time by a user-supplied `fn(&V) -> usize`, and total weight across all entries is kept within `max_weight`. Eviction uses LRU semantics until the new entry fits.

API design notes:

- The weigher is a plain function pointer, not a closure — captured state would force `Box<dyn Fn>` indirection on every weigh call. Hoist state into the value itself if you need it.
- Values whose own weight exceeds `max_weight` are silently rejected (insert returns `None`, value is dropped, cache is unchanged). The alternative — a new error variant — felt heavyweight for a degenerate input.
- [`max_weight()`] and [`total_weight()`] expose the bound and the dynamic in-use weight. [`capacity()`] returns `max_weight` for trait consistency, and the trait rustdoc was updated to cover both interpretations.

Worth highlighting: the weigher's unit is whatever you choose. Common choices include `Vec::len()` for payload bytes, `mem::size_of::<T>() + heap_allocation_estimate` for header-inclusive sizing, or a fixed-cost approximation. The cache does not interpret units — it just sums and compares.

### Internal scaffolding cleanup

Three concrete caches now share a single piece of duplicated machinery: the poison-recovery `lock_inner` helper. Each previously inlined the same six lines; with `TinyLfuCache` and `SizedCache` landing, that would have been five copies. Lifted into a `pub(crate) trait MutexExt::lock_recover` extension in `src/util.rs` and threaded through all five caches. Code reduction is small (~24 lines net) but more importantly there is now one place to change the policy if poison handling ever needs to evolve.

The `find_victim`-style scan helpers stay per-policy because their comparison criteria genuinely differ (LRU = `last_access`, LFU = `count` then `last_access`, TTL = `expires_at`, TinyLFU = LRU on the main, Sized = LRU). A generic-callback abstraction would be more code than it saves.

### Property tests

A new `tests/properties.rs` adds 9 properties via `proptest`, run on every CI invocation:

- Five capacity-invariant tests — one per cache type — drive random sequences of `insert` / `get` / `remove` / `contains_key` and assert `len <= capacity` (or `total_weight <= max_weight` for `SizedCache`) holds after every operation.
- Four insert-then-get round-trip tests confirm that `LruCache`, `LfuCache`, `TtlCache`, and `SizedCache` actually persist a value when inserted into a non-full cache. `TinyLfuCache` is excluded — its admission filter intentionally violates this property.

The smallest property test runs 96 cases per property; the round-trips run 64. Total proptest runtime is under 100 ms on the local machine.

### Criterion benchmarks

A new `benches/cache_ops.rs` ships a five-group Criterion suite (`LruCache` / `LfuCache` / `TtlCache` / `TinyLfuCache` / `SizedCache`), each covering `get_hit` and `insert_existing` at capacity 1024. Gated behind `required-features = ["std"]` so `--no-default-features` builds still pass. Numbers are a regression detector, not a marketing claim — there's no scoreboard against other cache crates yet. Run with `cargo bench`.

## What's not in 0.5.0

Deferred to 0.6.0:

- **Lock-free / arena-backed internals.** The reference `Mutex<{ HashMap, VecDeque }>` machinery is correct but does a lot of redundant work (`VecDeque::iter().position()` scans, full HashMap scans for eviction). Replacing this with a stable-index doubly-linked list arena gives O(1) LRU updates and O(1) LFU bucket selection, without changing the public surface. A sharded-Mutex or `crossbeam-epoch` decision lands as part of that work.
- **W-TinyLFU SLRU + doorkeeper.** The 0.5.0 `TinyLfuCache` ships the admission filter (which is most of the value) on top of a flat LRU main cache. The full W-TinyLFU paper adds an SLRU-segmented main cache and a Bloom doorkeeper to further reduce sketch pollution. Both are candidates for a 1.x quality pass and do not affect the public API.

## Breaking changes

**None.** Three new public types (`TinyLfuCache`, `SizedCache`, and `MutexExt` — `pub(crate)`, not exposed) and one rustdoc-text change to `Cache::capacity`. Every 0.4.0 call-site compiles and behaves identically against 0.5.0.

The crate remains pre-1.0; minor versions may break in the future. Pin exact versions.

## Verification

Local run on Windows x86_64, Rust stable. Identical commands pass via the configured CI matrix (Linux / macOS / Windows on stable + MSRV 1.75):

```bash
cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo clippy --all-targets --no-default-features -- -D warnings
cargo test --all-features
cargo doc --no-deps --all-features
```

Optional:

```bash
cargo bench                                # the new Criterion suite
```

All green. Test totals:

- Integration tests: **47 passed** (11 LRU + 8 LFU + 13 TTL + 6 TinyLFU + 9 Sized).
- Property tests (proptest, in `tests/properties.rs`): **9 passed**, each running 64–96 random op sequences.
- Doctests: **18 passed**.

REPS lint surface declared in `src/lib.rs` is honored: every `deny(...)` clippy/rustc lint from 0.2.0 still holds. The single `#[allow(clippy::ptr_arg)]` in `tests/smoke.rs` is justified inline — the `SizedCache` weigher signature requires `&Vec<u8>` to match the function-pointer type. No `unsafe` is introduced in this release.

## What's next

`0.6.0` is the implementation-quality milestone. The reference `Mutex`-guarded internals of `LruCache`, `LfuCache`, and `TtlCache` are replaced by arena-backed, O(1)-update versions. Either sharded `Mutex` (DashMap-style) or `crossbeam-epoch`-based lock-free reclamation is layered on top, with Criterion regression numbers vs the 0.5.0 baselines. Public surface stays byte-identical.

`0.9.0` is the hardening + audit pass; `1.0.0` is the API freeze.

## Installation

```toml
[dependencies]
cache-mod = "0.5"
```

MSRV: Rust 1.75. Edition 2021. `default-features = ["std"]`.

```rust
use cache_mod::{Cache, TinyLfuCache};

let cache: TinyLfuCache<&'static str, u32> = TinyLfuCache::new(256).expect("capacity > 0");

// Build up frequency signal for keys that should stay hot.
for _ in 0..32 {
    let _ = cache.get(&"hot");
    let _ = cache.insert("hot", 1);
}

// A cold candidate is rejected unless its sketch frequency outranks the LRU.
assert_eq!(cache.get(&"hot"), Some(1));
```

```rust
use cache_mod::{Cache, SizedCache};

fn byte_weight(v: &Vec<u8>) -> usize { v.len() }

let cache: SizedCache<&'static str, Vec<u8>> =
    SizedCache::new(4 * 1024, byte_weight).expect("max_weight > 0");

cache.insert("hero-image", vec![0u8; 512]);
assert_eq!(cache.total_weight(), 512);
assert_eq!(cache.max_weight(), 4096);
```

## Documentation

- [README](https://github.com/jamesgober/cache-mod/blob/main/README.md)
- [CHANGELOG](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md)
- [REPS standards](https://github.com/jamesgober/cache-mod/blob/main/REPS.md)
- [API reference](https://docs.rs/cache-mod/0.5.0)

---

**Full diff:** [`v0.4.0...v0.5.0`](https://github.com/jamesgober/cache-mod/compare/v0.4.0...v0.5.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/cache-mod/blob/main/CHANGELOG.md#050---2026-05-20).

[`Cache`]: https://docs.rs/cache-mod/0.5.0/cache_mod/trait.Cache.html
[`max_weight()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/struct.SizedCache.html#method.max_weight
[`total_weight()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/struct.SizedCache.html#method.total_weight
[`capacity()`]: https://docs.rs/cache-mod/0.5.0/cache_mod/trait.Cache.html#tymethod.capacity