quick-cache

quick_cache is a Rust crate providing an in-memory concurrent cache optimized for low overhead relative to a bare concurrent hash table. It implements a scan-resistant eviction policy derived from CLOCK-Pro and the more recently published S3-FIFO algorithm, which the crate’s own benchmarks (run with mokabench against Moka, TinyUFO, and a plain LRU+Mutex baseline) show delivering substantially higher hit ratios at a given capacity across multiple real-world access traces.

Beyond raw eviction performance, the crate exposes primitives for coordinating concurrent access: get_or_insert and the closure-based entry API let multiple threads race to fill the same missing key without duplicating work, an Equivalent-trait integration avoids allocating owned keys for lookups on composite key types, and a Weighter trait supports per-item cost accounting instead of assuming every entry costs the same. It ships both sync::Cache (thread-safe, sharded, configurable between parking_lot, crossbeam ShardedLock, or std Mutex) and unsync::Cache (single-threaded, no atomics) from a shared core, and is validated with an unusually thorough CI pipeline covering multi-platform tests, miri, cargo-fuzz, and Shuttle-based deterministic concurrency testing.

What You Get

• A thread-safe sync::Cache and a single-threaded unsync::Cache sharing one core implementation
• Scan-resistant S3-FIFO/CLOCK-Pro eviction policy tuned for high hit rates under real-world access traces
• Atomic get_or_insert/entry APIs (with async variants) for coordinating cache fills and mutations across threads
• Pluggable Weighter, Lifecycle, and hasher/synchronization-backend traits for customization
• Iteration, draining, and item-pinning support

Common Use Cases

• Caching expensive database or API query results in a backend service
• Memoizing concurrent computations so identical work isn’t repeated across threads
• Bounding memory usage of a cache via custom per-item weights
• Building eviction listeners or resource-cleanup hooks via the Lifecycle trait

Under The Hood

Architecture quick_cache implements a sharded cache design centered on shard.rs (~1,500 lines), which pairs a hashbrown HashTable for lookups with a LinkedSlab for O(1) eviction-order bookkeeping, driven by a CLOCK-Pro/S3-FIFO-inspired hot/cold state machine (ResidentState) using atomic reference counters to track recency without full locking on every access. Two front-ends sit on this shared core: sync::Cache (thread-safe, sharded across per-key-hash locks selected via parking_lot, crossbeam ShardedLock, or std Mutex) and unsync::Cache (single-threaded, no atomics), swapped in via conditional compilation in shim.rs so one codebase serves both concurrency models. The placeholder mechanism (SharedPlaceholder trait, EntryOrPlaceholder enum) is the coordination primitive behind get_or_insert and the closure-based entry API: a placeholder token is inserted under the shard lock, the lock is released while the caller computes a value, and the placeholder is swapped for the resident entry — letting concurrent misses on the same key avoid duplicated computation. Because both front-ends delegate to this single shard module, any change to the resident/state machine has to stay consistent across both concurrency models at once.

Tech Stack The crate targets Rust edition 2021 (rust-version 1.85) with a deliberately small, mostly-optional dependency tree: hashbrown 0.17 for SwissTable-based lookups, equivalent 1.0 for borrowed-key access, optional foldhash 0.2 (custom-hasher feature, on by default) as the default fast hasher, optional parking_lot 0.12 (on by default) and crossbeam-utils 0.8 (sharded-lock feature) as alternative synchronization backends, and optional shuttle 0.8 for deterministic concurrency testing. Dev-dependencies (criterion, rand/rand_distr, tokio) support benchmarking and the async entry-API test surface. There is no I/O, network, or database dependency — this is a pure in-memory data-structure crate.

Code Quality Testing is extensive: lib.rs and sync.rs carry runnable doctest examples, shard.rs and unsync.rs have inline unit tests, and a dedicated 444-line shuttle_tests.rs module exercises the concurrent code paths under the Shuttle deterministic scheduler. CI runs cargo test across ubuntu/macos/windows with several feature-flag combinations, a separate Shuttle-tests job, a cargo-fuzz job against a fuzz/ target directory, rustfmt + clippy with -D warnings, and a miri job for undefined-behavior detection — a notably rigorous pipeline for a low-level concurrent data structure. Roughly 48 unsafe blocks appear across src/, consistent with the crate’s stated goal of keeping unsafe usage “trivially verifiable,” with miri and Shuttle specifically there to continuously validate that claim.

API Design The public API centers on a small set of well-named, composable primitives: insert/get for the basic case, get_or_insert/get_or_insert_async for coordinated cache-fill, and a closure-based entry API (Retain/Remove/ReplaceWithGuard) for atomic inspect-and-act patterns — all documented with runnable examples in the crate-level docs. The Equivalent trait integration lets callers query composite keys without allocating an owned key just for a lookup, a real ergonomic gain over std HashMap’s Borrow-based API, while Weighter and Lifecycle are single-method traits that add per-item cost accounting and extension hooks (eviction listeners, item pinning) without baking those features into the core type. Getting started needs minimal boilerplate — Cache::new(capacity) covers the common case — with a fairly deep customization ceiling available only when needed.