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

# cache-mod v0.6.0 — Arena-backed internals: O(1) LRU/TinyLFU/Sized, O(log n) LFU

**Implementation-quality milestone.** The public surface that landed across 0.2.0 – 0.5.x is byte-identical in 0.6.0 — every existing call-site compiles and behaves the same — but the internal data structures behind every cache type changed. Asymptotic complexity is better across the board: the 0.5.x `VecDeque::iter().position()` scans are gone from LRU / TinyLFU / SizedCache, and `LfuCache`'s O(n) victim-finding loop is replaced by an ordered priority index.

## 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 changed under the hood

### `LruCache` — arena-backed doubly-linked list

The 0.5.x `LruCache` used `Mutex<{ HashMap<K, V>, VecDeque<K> }>` and scanned the deque on every access to find the entry's position. That scan was O(n) per `get` and per `insert` that touched an existing key.

In 0.6.0 the storage layout is:

- `Vec<Option<Node<K, V>>>` — an arena of nodes addressed by stable `usize` index, with `None` slots queued on a free-list for reuse.
- `Vec<usize>` — the free-list itself, popped on alloc and pushed on dealloc.
- `Option<usize> head, tail` — the most- and least-recently-used node indices.
- `HashMap<K, usize>` — `K` → arena index for keyed lookup.

Promote becomes: unlink the node from its current position in the doubly-linked list, push it to the head. Both operations are O(1) — they only touch the previous and next pointers of the affected node and its neighbours. Eviction is `tail.unlink()` + `dealloc` + `map.remove(&key)`, also O(1).

### `TinyLfuCache` — arena-backed main + unchanged sketch

Same arena shape as `LruCache`. The Count-Min Sketch and admission filter are unchanged: depth-4, `u8` saturating counters, width `max(64, 2 × capacity)` rounded up to a power of two, W-TinyLFU aging step every `10 × capacity` increments. The 0.5.x O(n) victim scan in the admission filter is now an O(1) tail lookup.

### `SizedCache` — arena with weight bookkeeping

Same arena shape; each `Node` additionally carries its `weight`. The 0.5.x `VecDeque::iter().position()` scan is gone. Eviction loops the O(1) tail-pop step until the weight invariant `total_weight + new_weight ≤ max_weight` holds — overall complexity is O(eviction_count), bounded by however many entries the new insert displaces.

### `LfuCache` — BTreeMap priority index

LFU's eviction policy (lowest count, tie-broken by least-recently-accessed) doesn't fit the arena pattern cleanly — every access changes the entry's priority, so head/tail bookkeeping isn't sufficient. The 0.5.x implementation handled this with an O(n) scan to find the minimum.

0.6.0 replaces the scan with a `BTreeMap<(count, age), K>` priority index. The map is sorted by `(count, age)` ascending, so `pop_first()` always returns the lowest-frequency entry with the oldest tie-break. Every access does:

1. Read the entry's old `(count, age)` from `HashMap<K, Entry<V>>`.
2. Remove the old priority from the BTreeMap.
3. Update the entry's count and age.
4. Insert the new priority into the BTreeMap.

That's two O(log n) BTreeMap ops per access. The trade-off: one extra `K::clone()` per access (the BTreeMap needs to know which key to return on eviction). Worth it once the cache holds more than a few dozen entries — at capacity 1024, two O(log) lookups beat one O(n) scan by ~50×.

### `TtlCache` — unchanged

`TtlCache` already uses lazy expiry: every `get` / `contains_key` / `len` cleans expired entries it encounters, and overflow eviction prefers the soonest-expiring entry. The typical TTL access pattern (write-once, evict-on-access) doesn't benefit from arena bookkeeping — most evictions hit an already-expired entry on the first scan iteration. Profiling can drive a future change if a hot-spot emerges; for now, the simpler implementation wins.

### Lock strategy unchanged

Every cache type still uses a single `Mutex<Inner>`. The sharded `Mutex` (DashMap-style) or `crossbeam-epoch` lock-free reclamation upgrade slides to **0.7.0**, a separate concurrency-focused release. Splitting the concerns: 0.6.0 was about algorithmic improvements within a single lock; 0.7.0 will be about scaling across many threads.

## Breaking changes

**None.** Every public symbol — the `Cache` trait, `CacheError`, `LruCache` / `LfuCache` / `TtlCache` / `TinyLfuCache` / `SizedCache` and their constructors and methods — has identical signatures and behaviour against 0.5.x. The same 47 integration tests, 9 property tests, and 18 doctests pass without modification.

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

## Verification

Local run on Windows x86_64, Rust stable:

```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
cargo build --benches --release
```

All green. Test totals are identical to 0.5.1 (no test surface changed):

- Integration tests: **47 passed**.
- Property tests (proptest): **9 passed**.
- Doctests: **18 passed**.

Benchmark numbers are workload-dependent and intentionally not reproduced in the release notes — run `cargo bench` locally to capture your own baseline. The asymptotic improvement is real: at capacity 1024, every previously-O(n) access path is now either O(1) (LRU / TinyLFU / Sized) or O(log n) (LFU).

REPS lint surface declared in `src/lib.rs` is honored: every `deny(...)` clippy / rustc lint from 0.2.0 still holds. No `unsafe` is introduced in this release.

## What's next

`0.7.0` is the concurrency milestone. The single `Mutex<Inner>` becomes a sharded structure (DashMap-style routing by key hash) or moves to `crossbeam-epoch` lock-free reclamation, depending on the throughput / latency trade-off that benchmarking surfaces. 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.6"
```

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

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

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

// Same call surface as 0.5.x — but every `get` and `insert` is now O(1).
cache.insert("requests", 1);
assert_eq!(cache.get(&"requests"), Some(1));
```

## Documentation

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

---

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