# iqdb-cache v0.4.0 — Eviction Policies + Feature Freeze
**One cache, four ways to forget.** v0.4.0 makes the eviction strategy a choice. The cache ships LRU (the default), LFU, FIFO, and ARC behind a single `CacheConfig::policy` knob — all built on one arena-backed ordered-map primitive, all bounded to capacity, all transparent. This release also **freezes the feature set**: the public surface is complete, and the run to 1.0 is hardening, not new capability.
## What is iqdb-cache?
An in-process caching layer between the database and an index. It wraps any `iqdb_index::IndexCore` as a `CachedIndex` — itself an `IndexCore` — and memoizes search results, turning a repeated query into a memory read. It stays opt-in: a database is correct with no cache, and the policy choice only changes the hit rate, never the results.
## What's new in 0.4.0
### `EvictionPolicy` — pick the strategy, not the implementation
```rust
use iqdb_cache::{CacheConfig, CachedIndex, EvictionPolicy};
let cached = CachedIndex::with_config(
iqdb_cache::doc_stub::stub_index(),
CacheConfig::new().capacity(4096).policy(EvictionPolicy::Arc),
);
assert_eq!(cached.policy(), EvictionPolicy::Arc);
```
| Policy | Evicts | Best for |
|---|---|---|
| `Lru` *(default)* | the least-recently-used entry | shifting query hot-sets — the strongest general default |
| `Lfu` | the least-frequently-used entry (ties: LRU) | stable, skewed workloads where a few queries dominate |
| `Fifo` | the oldest *inserted* entry, ignoring access | uniform reuse — the cheapest policy |
| `Arc` | adaptively, balancing recency and frequency | workloads that shift between the two |
All four are exact caches: correctness never depends on the policy, only the hit rate does.
### One primitive, four policies
The internals were reworked onto a single `OrderedMap` — an arena-backed linked hash map with `O(1)` insert-front, lookup, promote, arbitrary remove, and pop-back, and a free-list so removals recycle storage. Every policy composes it:
- **LRU / FIFO** share one recency list; LRU promotes on access, FIFO does not.
- **LFU** groups keys into frequency buckets (each an `OrderedMap`) and tracks a min-frequency pointer, so eviction of the least-frequent / least-recent key is `O(1)`.
- **ARC** keeps two value lists (recency `T1`, frequency `T2`) and two ghost lists (`B1`, `B2`), adapting its target split as ghost hits arrive — staying LRU-like or LFU-like as the workload demands, with occupancy always within capacity.
The whole crate remains `#![forbid(unsafe_code)]`.
### Eviction accounting
`CacheStats` gains an `evictions` counter — the lifetime number of entries the policy discarded to make room — alongside the existing `hits`, `misses`, `len`, and `capacity`.
## Performance
Hit cost by policy on the reference machine — a top-10 search over 10,000 vectors at dim 64, the same query served repeatedly (`cargo bench`):
| Path | Time | vs. uncached |
|------|------|--------------|
| `uncached_scan` (full scan) | ~234 µs | 1× |
| `Fifo` hit | **~250 ns** | ~935× |
| `Lru` hit | ~278 ns | ~840× |
| `Arc` hit | ~387 ns | ~605× |
| `Lfu` hit | ~1.17 µs | ~200× |
FIFO is cheapest (no reordering); LFU is heaviest (it moves the key between frequency buckets on every hit) but still ~200× faster than recomputing. The shared-primitive rework kept the default-LRU hit path within ~5% of 0.3 (~250 ns vs ~238 ns). A TTL, when configured, adds ~29 ns for the monotonic clock read.
## Feature freeze
With this release the public **feature set is complete**: the `CachedIndex` wrapper, mutation-exact invalidation, optional TTL, the four eviction policies, and the stats surface. There is no `todo!` or `unimplemented!` anywhere in the crate. The remaining 0.x work is stabilization — `loom` concurrency model-checks and the **API freeze** at 0.5, then alpha/beta/rc hardening to 1.0 — not new surface. See `dev/ROADMAP.md`.
## Breaking changes
**Pre-1.0 API churn, but source-compatible.** Everything is additive: `new`, `with_capacity`, and `with_config` keep their signatures and default to LRU, exactly as before. `CacheStats` gains a public `evictions` field (relevant only if you construct the struct by hand). No new dependencies.
## Verification
Each policy is covered by unit tests of its eviction order (LRU protects the recently used, FIFO does not, LFU evicts the least frequent, ARC keeps occupancy bounded while promoting frequents) and by property tests that — across all four policies, with caches smaller than the query set — every search still equals a brute-force reference index and the cache never exceeds capacity. An integration test pins the eviction counter, and the `policy_hit` benchmark tracks each policy's hit cost. The same gates run across the CI matrix (Linux, macOS, Windows) on stable and the 1.87 MSRV:
```bash
cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
```
MSRV: Rust 1.87.
## What's next
- **v0.5.0 — concurrency + API freeze.** `loom` model-checks for the shared-cache path, and the public API frozen and recorded for the 1.x series.
## Installation
```toml
[dependencies]
iqdb-cache = "0.4"
```
## Documentation
- [README](https://github.com/jamesgober/iqdb-cache/blob/main/README.md)
- [API reference](https://github.com/jamesgober/iqdb-cache/blob/main/docs/API.md)
- [ROADMAP](https://github.com/jamesgober/iqdb-cache/blob/main/dev/ROADMAP.md)
- [Standards (REPS)](https://github.com/jamesgober/iqdb-cache/blob/main/REPS.md)
- [CHANGELOG](https://github.com/jamesgober/iqdb-cache/blob/main/CHANGELOG.md)
---
**Full diff:** [`v0.3.0...v0.4.0`](https://github.com/jamesgober/iqdb-cache/compare/v0.3.0...v0.4.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/iqdb-cache/blob/main/CHANGELOG.md).