Crate cache_rs

Expand description

§cache-rs

A high-performance cache library for Rust with multiple eviction algorithms, no_std support, and thread-safe concurrent variants.

⚠️ Pre-1.0 Notice: cache-rs is under active development and the API may change between minor versions. We’re rapidly iterating toward a stable 1.0.0 release. Pin your dependency version if you need stability, and check the CHANGELOG when upgrading.

§The Problem with “One Size Fits All” Caching

There is no universally optimal cache eviction algorithm. LRU works beautifully for session stores where recent activity predicts future access, but deploy it on a CDN and a single sequential scan can flush your entire hot working set. LFU excels when popularity is stable, keeping your most-requested assets warm, until yesterday’s viral content blocks today’s trending items from ever getting cached. GDSF maximizes hit rates for variable-sized objects by favoring small popular files, but adds complexity you don’t need when all your cached items are the same size.

Real-world caching infrastructure demands the right algorithm for the job. A database buffer pool needs scan resistance (SLRU). A news feed cache needs frequency tracking with aging (LFUDA). A CDN metadata index needs size-aware eviction (GDSF). Benchmarks across 47 million requests show that algorithm selection can mean the difference between a 30% hit rate and a 90% hit rate. Size-aware algorithms provide 50-90 percentage point improvements when storage constraints dominate.

cache-rs gives you the full toolkit: five battle-tested eviction algorithms with a unified API, so you can choose the right strategy for your workload without rewriting your caching layer.

§Why cache-rs?

cache-rs is a high-performance in-memory cache library that gives you control over how your cache behaves. Instead of a one-size-fits-all eviction policy, you choose from five algorithms (LRU, SLRU, LFU, LFUDA, and GDSF) behind a unified API. Start with LRU for simplicity and speed, swap in SLRU if sequential scans are polluting your cache, or GDSF if your objects vary in size. The API remains the same; only the eviction behavior changes.

The library fits into multiple architectural patterns. Use it as a straightforward in-memory cache for database query results, API responses, or computed values. Use it as a metadata index for disk-backed CDN caches, where you store file locations and headers in cache-rs while the actual content lives on disk. Use it as a cache lookup layer for shared memory systems, where cache-rs tracks keys and offsets while another process or subsystem manages the raw data. The eviction logic stays the same regardless of where your data actually lives, be it in-memory local to cache-rs, or on disk or on shared-memory.

The core design prioritizes predictable, low-latency operations. LRU and SLRU run in O(1) time. The frequency-based algorithms (LFU, LFUDA, GDSF) run in O(log P) where P is the number of distinct priority buckets, though in practice this is often small. The cache stores pointers in a HashMap while values live in cache-friendly linked structures, minimizing memory overhead and cache misses.

For multi-threaded applications, every algorithm has a concurrent counterpart. These use segmented locking rather than a single global lock: keys hash to independent segments, so threads accessing different parts of the cache proceed in parallel. Enable concurrent caches with the concurrent feature flag and wrap in Arc for shared ownership across threads.

You can set dual capacity limits: one for entry count (to bound memory overhead from metadata) and one for total content size (to bound actual data storage). Eviction triggers when either limit is exceeded, giving you precise control over memory consumption.

The library works in no_std environments out of the box. The default build uses hashbrown and requires only alloc, making it suitable for embedded systems and kernel development. If you need standard library features or concurrent caches, opt in with the std or concurrent feature flags.

cache-rs is production-hardened: extensive test coverage, Miri-verified for memory safety, and benchmarked across realistic workloads. It serves as the foundation for cache simulation research, so the algorithms have been validated against real-world access patterns. For a deep dive into how each algorithm performs under different workloads, see our Analysis Report, which covers 47 million cache operations across video streaming, social media, web content, and on-disk caching scenarios.

§Quick Start

[dependencies]
cache-rs = "0.3.0"

All caches follow a unified initialization pattern: create a config struct for your chosen algorithm, then call init(config, hasher). The second parameter accepts an optional custom hasher; pass None to use the default.

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    max_size: u64::MAX,
};
let mut cache = LruCache::init(config, None);

§Common API

All cache types support these core operations:

Method	Description
`put(key, value)`	Insert or update an entry. Returns evicted entry if capacity exceeded.
`put_with_size(key, value, size)`	Insert with explicit size for size-limited caches.
`get(&key)`	Retrieve a reference to the value. Updates access metadata (e.g., moves to front in LRU).
`get_mut(&key)`	Retrieve a mutable reference. Updates access metadata.
`remove(&key)`	Remove and return an entry.
`len()`	Number of entries.
`is_empty()`	Whether cache is empty.
`clear()`	Remove all entries.
`cap()`	Maximum capacity (LRU/LFU/LFUDA/SLRU).

Algorithm-specific methods:

GDSF: Use put(key, value, size) (requires size for priority calculation) and contains_key(&key) to check existence.
GDSF: Use pop(&key) instead of remove(&key) to remove entries.

§Example: Basic Usage

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(100).unwrap(),
    max_size: u64::MAX,
};
let mut cache = LruCache::init(config, None);

// Insert entries
cache.put("user:1001", "Alice");
cache.put("user:1002", "Bob");

// Retrieve (updates LRU position)
assert_eq!(cache.get(&"user:1001"), Some(&"Alice"));

// Check existence (also updates LRU position if present)
assert!(cache.get(&"user:1001").is_some());
assert!(cache.get(&"user:9999").is_none());

// Remove
cache.remove(&"user:1001");
assert_eq!(cache.get(&"user:1001"), None);

§Quick Reference

Scenario	Algorithm	Why
General purpose, simple workload	LRU	Fastest, lowest overhead, predictable behavior
Database buffer pool, file cache	SLRU	Scan resistance protects hot working set
CDN with stable popular content	LFU	Frequency tracking keeps popular items cached
Long-running service, trends change	LFUDA	Aging prevents stale popular items from persisting
Variable-sized objects (images, files)	GDSF	Size-aware eviction maximizes hit rate

§Cache Size Configuration

All cache algorithms in cache-rs share a common configuration pattern with two key sizing parameters: capacity and max_size. Understanding these parameters is essential for tuning your cache to fit your workload and memory constraints.

§Understanding `capacity` and `max_size`

Every cache configuration includes these two fields:

Parameter	Type	Description
`capacity`	`NonZeroUsize`	Maximum number of entries the cache can hold
`max_size`	`u64`	Maximum total size in bytes for cached values

Important: Eviction occurs when either limit would be exceeded by inserting a new entry.

Eviction triggers when:
  (entry_count >= capacity) OR (current_size + new_entry_size > max_size)

This dual-limit approach gives you precise control:

Use capacity to bound metadata overhead (each entry uses ~64-128 bytes for keys, pointers, and internal structures)
Use max_size to bound actual data storage (the cached values themselves)

§Specifying Entry Size

By default, put(key, value) treats each entry as having size 1. For size-aware caching, use put_with_size(key, value, size):

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    max_size: 10 * 1024 * 1024,  // 10 MB
};
let mut cache: LruCache<&str, Vec<u8>> = LruCache::init(config, None);

// Size-aware insertion: this blob consumes 5KB of the 10MB budget
let blob = vec![0u8; 5000];
cache.put_with_size("large-blob", blob, 5000);

Note: For GDSF caches, put(key, value, size) always requires the size parameter since size is integral to the eviction algorithm.

§Sizing Strategies

§Count-Limited Cache (Entry Limit Only)

When you want to limit the number of entries without tracking byte size:

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(10_000).unwrap(),  // Max 10,000 entries
    max_size: u64::MAX,                             // Effectively unlimited size
};
let mut cache: LruCache<&str, &str> = LruCache::init(config, None);

Use case: Caching fixed-size items like user sessions, configuration values, or computed results where entry count is the primary constraint.

§Size-Limited Cache (Byte Budget)

When you have a specific memory budget and variable-sized values:

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

// 100 MB cache for images, documents, etc.
let config = LruCacheConfig {
    capacity: NonZeroUsize::new(100_000).unwrap(), // Reasonable upper bound
    max_size: 100 * 1024 * 1024,                   // 100 MB budget
};
let mut cache = LruCache::init(config, None);

// Track actual sizes when inserting
let image_data = load_image("photo.jpg");
let image_size = image_data.len() as u64;
cache.put_with_size("photo.jpg", image_data, image_size);

Use case: CDN caches, file caches, response caches where objects vary significantly in size.

§Balanced Cache (Both Limits)

For production systems, set meaningful values for both limits:

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

// 50 MB cache expecting ~5KB average values
let config = LruCacheConfig {
    capacity: NonZeroUsize::new(10_000).unwrap(),  // ~50MB / 5KB
    max_size: 50 * 1024 * 1024,                    // 50 MB
};
let mut cache: LruCache<&str, Vec<u8>> = LruCache::init(config, None);

Memory planning formula:

Total Memory ≈ max_size + (capacity × overhead_per_entry)
overhead_per_entry ≈ 64-128 bytes (keys, pointers, metadata)

§Eviction Behavior Examples

Let’s trace through how the dual-limit eviction works:

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

// Tiny cache for demonstration: 3 entries OR 100 bytes max
let config = LruCacheConfig {
    capacity: NonZeroUsize::new(3).unwrap(),
    max_size: 100,
};
let mut cache: LruCache<&str, &str> = LruCache::init(config, None);

// Insert 3 entries, each with size 30 bytes
cache.put_with_size("a", "value_a", 30);  // entries=1, size=30
cache.put_with_size("b", "value_b", 30);  // entries=2, size=60
cache.put_with_size("c", "value_c", 30);  // entries=3, size=90

// Case 1: Capacity-triggered eviction
// Adding "d" would exceed capacity (3 entries), so "a" is evicted
cache.put_with_size("d", "value_d", 30);  // evicts "a", entries=3, size=90

// Case 2: Size-triggered eviction
// Adding a 50-byte entry would exceed max_size (90 + 50 > 100)
// Multiple entries may be evicted to make room
cache.put_with_size("big", "large_value", 50);  // evicts until size fits

For concurrent caches, capacity and max_size apply to the entire cache (distributed across all segments), not per-segment

§Test with Your Own Traffic

Not sure which algorithm fits your workload? The repository includes a cache-simulator tool that replays your traffic logs against all five algorithms and reports hit rates, byte hit rates, and latency statistics. Feed it your production access patterns and let the data guide your decision.

cd cache-simulator
cargo run --release -- --input your-traffic.log --cache-size 1000

See cache-simulator/README.md for input format and options.

See ALGORITHM_GUIDE.md for detailed use cases and code examples.

§Eviction Algorithms

§LRU (Least Recently Used)

Evicts the entry that hasn’t been accessed for the longest time. This is the simplest and most widely applicable algorithm.

Eviction policy: Maintain a doubly-linked list ordered by access time. On access, move the entry to the front. On eviction, remove from the back.

When to use: General-purpose caching where recent access is a good predictor of future access. Web sessions, query results, configuration data.

Time complexity: O(1) for all operations.

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    max_size: u64::MAX,
};
let mut cache: LruCache<&str, &str> = LruCache::init(config, None);

§SLRU (Segmented LRU)

Divides the cache into two segments: probationary and protected. New entries start in probationary. A second access promotes them to protected. Eviction happens from probationary first.

Eviction policy: Entries must prove their worth by being accessed twice before gaining protection. This provides scan resistance: a sequential read of many items won’t evict your hot working set.

When to use: Database buffer pools, file system caches, any workload mixing random access with sequential scans.

Time complexity: O(1) for all operations.

use cache_rs::SlruCache;
use cache_rs::config::SlruCacheConfig;
use std::num::NonZeroUsize;

let config = SlruCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    protected_capacity: NonZeroUsize::new(200).unwrap(),  // 20% protected
    max_size: u64::MAX,
};
let mut cache: SlruCache<&str, &str> = SlruCache::init(config, None);

§LFU (Least Frequently Used)

Tracks how many times each entry has been accessed. Evicts the entry with the lowest frequency count.

Eviction policy: Maintain frequency counters for each entry. Group entries by frequency in a priority structure. Evict from the lowest frequency group.

When to use: Workloads where some items are consistently more popular than others. API caching, CDN content, static asset serving.

Caveat: Items that were popular historically but aren’t anymore can “stick” in cache. Use LFUDA if popularity changes over time.

Time complexity: O(log F) where F = distinct frequency values. Since frequencies are small integers (1, 2, 3, …), F is bounded and operations are effectively O(1).

use cache_rs::LfuCache;
use cache_rs::config::LfuCacheConfig;
use std::num::NonZeroUsize;

let config = LfuCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    max_size: u64::MAX,
};
let mut cache: LfuCache<&str, &str> = LfuCache::init(config, None);

§LFUDA (LFU with Dynamic Aging)

Extends LFU with a global age counter that increases on each eviction. New entries start with priority equal to the current age plus their frequency, allowing them to eventually compete with historically popular items.

Eviction policy: Priority = frequency + age_at_insertion. The global age increases each eviction. This prevents old popular items from permanently occupying cache space.

When to use: Long-running services where popularity changes (news feeds, social media, e-commerce with seasonal trends).

Time complexity: O(log P) where P = distinct priority values. Priority = frequency + age, so P can grow with cache size.

use cache_rs::LfudaCache;
use cache_rs::config::LfudaCacheConfig;
use std::num::NonZeroUsize;

let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache: LfudaCache<&str, &str> = LfudaCache::init(config, None);

§GDSF (Greedy Dual-Size Frequency)

Designed for variable-sized objects. Considers frequency, size, and age when making eviction decisions. Smaller popular items get higher priority than large rarely-accessed items.

Eviction policy: Priority = (frequency / size) + age. This maximizes hit rate (not byte hit rate) by preferring many small popular items over few large ones.

When to use: CDN metadata caches, file caches, any workload where object sizes vary significantly.

Note: The put method requires a size parameter.

Time complexity: O(log P) where P = distinct priority buckets. Priority = (frequency/size) + age.

use cache_rs::GdsfCache;
use cache_rs::config::GdsfCacheConfig;
use std::num::NonZeroUsize;

let config = GdsfCacheConfig {
    capacity: NonZeroUsize::new(10000).unwrap(),
    initial_age: 0.0,
    max_size: 100 * 1024 * 1024,  // 100 MB
};
let mut cache: GdsfCache<&str, Vec<u8>> = GdsfCache::init(config, None);

// put() requires size parameter
cache.put("small.txt", "content", 1024);        // 1 KB
cache.put("large.bin", "content", 10_000_000);  // 10 MB

§Concurrent Cache Support

For multi-threaded workloads, enable the concurrent feature:

[dependencies]
cache-rs = { version = "0.3.0", features = ["concurrent"] }

§Why Mutex, Not RwLock?

You might expect a cache to use RwLock so multiple readers can proceed in parallel. However, cache algorithms like LRU, LFU, and SLRU require mutable access even for reads:

LRU: get() moves the accessed item to the front of the recency list
LFU: get() increments the frequency counter and may move items between buckets
SLRU: get() may promote items from probationary to protected segment
LFUDA/GDSF: get() updates priority calculations

Since every get() mutates internal state, RwLock would provide no benefit; all operations need exclusive access anyway. cache-rs uses parking_lot::Mutex for lower overhead and achieves concurrency through segmentation: different keys hash to different segments and can be accessed in parallel.

§Available Types

Type	Base Algorithm
`ConcurrentLruCache`	LRU
`ConcurrentSlruCache`	SLRU
`ConcurrentLfuCache`	LFU
`ConcurrentLfudaCache`	LFUDA
`ConcurrentGdsfCache`	GDSF

§Example

use cache_rs::concurrent::ConcurrentLruCache;
use cache_rs::config::{ConcurrentCacheConfig, LruCacheConfig};
use std::num::NonZeroUsize;
use std::sync::Arc;
use std::thread;

let config = ConcurrentCacheConfig {
    base: LruCacheConfig {
        capacity: NonZeroUsize::new(10_000).unwrap(),
        max_size: u64::MAX,
    },
    segments: 16,  // Power of 2 recommended
};
let cache = Arc::new(ConcurrentLruCache::init(config, None));

let handles: Vec<_> = (0..8).map(|i| {
    let cache = Arc::clone(&cache);
    thread::spawn(move || {
        for j in 0..1000 {
            let key = format!("thread{}-key{}", i, j);
            cache.put(key.clone(), i * 1000 + j);
            cache.get(&key);
        }
    })
}).collect();

for handle in handles {
    handle.join().unwrap();
}

§Zero-Copy Access

Use get_with to process values without cloning:

use cache_rs::concurrent::ConcurrentLruCache;
use cache_rs::config::{ConcurrentCacheConfig, LruCacheConfig};
use std::num::NonZeroUsize;

let config = ConcurrentCacheConfig {
    base: LruCacheConfig {
        capacity: NonZeroUsize::new(100).unwrap(),
        max_size: u64::MAX,
    },
    segments: 16,
};
let cache: ConcurrentLruCache<String, Vec<u8>> = ConcurrentLruCache::init(config, None);
cache.put("data".to_string(), vec![1u8; 1024]);

// Process in-place without cloning
let sum: Option<u8> = cache.get_with(&"data".to_string(), |bytes| {
    bytes.iter().copied().sum()
});

§Advanced: Disk-Backed and Tiered Caches

While cache-rs works great as a standalone in-memory cache, it also excels as the metadata layer for disk-backed caching systems. In this pattern, you store actual content on disk (or in object storage, or any external system), while cache-rs tracks what is cached and makes eviction decisions. When cache-rs evicts an entry, you use that signal to delete the corresponding file from disk.

This separation is common in production infrastructure: CDN edge servers keep files on disk but need in-memory metadata to decide which files to keep. Database buffer pools track page locations without duplicating page data. Object storage gateways maintain indexes mapping keys to storage backends. The example below shows this two-tier pattern in action.

§Two-Tier Cache Pattern

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use std::num::NonZeroUsize;
use std::path::PathBuf;
use std::fs;

/// Metadata for disk-cached content
#[derive(Clone)]
struct DiskEntry {
    path: PathBuf,
    size: u64,
}

struct TieredCache {
    index: LruCache<String, DiskEntry>,  // In-memory index
    cache_dir: PathBuf,                   // Disk storage
}

impl TieredCache {
    fn new(capacity: usize, cache_dir: PathBuf) -> Self {
        let config = LruCacheConfig {
            capacity: NonZeroUsize::new(capacity).unwrap(),
            max_size: u64::MAX,
        };
        fs::create_dir_all(&cache_dir).unwrap();
        TieredCache {
            index: LruCache::init(config, None),
            cache_dir,
        }
    }

    fn get(&mut self, key: &str) -> Option<Vec<u8>> {
        // Check index for disk location
        let entry = self.index.get(&key.to_string())?;
        
        // Read from disk
        fs::read(&entry.path).ok()
    }

    fn put(&mut self, key: &str, content: &[u8]) {
        let path = self.cache_dir.join(format!("{:x}.cache", self.hash(key)));
        
        // Write to disk
        fs::write(&path, content).unwrap();
        
        // Update index (may evict old entry)
        if let Some((_, evicted)) = self.index.put(
            key.to_string(),
            DiskEntry { path: path.clone(), size: content.len() as u64 }
        ) {
            // Clean up evicted file from disk
            let _ = fs::remove_file(&evicted.path);
        }
    }

    fn hash(&self, s: &str) -> u64 {
        s.bytes().fold(0u64, |acc, b| acc.wrapping_mul(31).wrapping_add(b as u64))
    }
}

§Performance

Algorithm	Get	Put	Memory Overhead
LRU	~887ns	~850ns	~80 bytes/entry
SLRU	~983ns	~950ns	~90 bytes/entry
LFU	~22.7µs	~22µs	~100 bytes/entry
LFUDA	~20.5µs	~21µs	~110 bytes/entry
GDSF	~7.5µs	~8µs	~120 bytes/entry

Run benchmarks: cargo bench

§`no_std` Support

cache-rs works out of the box in no_std environments:

#![no_std]
extern crate alloc;

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use core::num::NonZeroUsize;
use alloc::string::String;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(10).unwrap(),
    max_size: u64::MAX,
};
let mut cache: LruCache<String, &str> = LruCache::init(config, None);
cache.put(String::from("key"), "value");

§Feature Flags

Feature	Description
(default)	`no_std` + `hashbrown`
`std`	Standard library support
`concurrent`	Thread-safe caches (requires `std`)
`nightly`	Nightly optimizations

§Roadmap & Contributing

cache-rs provides a solid foundation for cache eviction, but several features commonly needed in production systems are not yet implemented. Contributions are welcome!

§Planned Features

Feature	Description	Status
TTL Support	Time-based expiration for cache entries	Not started
Eviction Callbacks	Hooks to notify when entries are evicted (for cleanup, persistence, metrics)	Not started
Admission Policies	Decide whether to cache an item at all (e.g., TinyLFU admission)	Not started
Enhanced Metrics	Hit/miss counters, eviction counts, latency histograms	Basic
Async Support	`async`-compatible concurrent caches	Not started
Weighted Entries	Custom cost functions beyond simple size	Not started

§How to Contribute

# Run the full validation suite before submitting
cargo test --features "std,concurrent"
cargo fmt --all -- --check
cargo clippy --features "std,concurrent" -- -D warnings
cargo doc --no-deps --document-private-items

See CONTRIBUTING.md for detailed guidelines.

§Documentation

API Documentation
Algorithm Guide: Detailed examples and use cases for each algorithm
Analysis Report: Empirical evaluation across 47M requests
Examples
Benchmarks
Miri Analysis: Memory safety verification

§License

This project is licensed under the MIT license. See LICENSE file for details.

§Security

See SECURITY.md.

§Code Reference

This section provides quick code examples and API references for each cache algorithm.

§Algorithm Selection Guide

┌─────────────────────────────────────────────────────────────────────────────┐
│                    Which Cache Algorithm Should I Use?                       │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                              │
│  Is your workload primarily...                                               │
│                                                                              │
│  ┌─────────────────┐                                                         │
│  │ Recency-based?  │──Yes──▶ Are you worried about scans?                   │
│  │ (recent = hot)  │              │                                          │
│  └────────┬────────┘         Yes  │  No                                      │
│           │                   │   │                                          │
│          No                   ▼   ▼                                          │
│           │               ┌──────────┐  ┌──────────┐                         │
│           │               │   SLRU   │  │   LRU    │                         │
│           ▼               └──────────┘  └──────────┘                         │
│  ┌─────────────────┐                                                         │
│  │ Frequency-based?│──Yes──▶ Does popularity change over time?              │
│  │ (popular = hot) │              │                                          │
│  └────────┬────────┘         Yes  │  No                                      │
│           │                   │   │                                          │
│          No                   ▼   ▼                                          │
│           │               ┌──────────┐  ┌──────────┐                         │
│           │               │  LFUDA   │  │   LFU    │                         │
│           ▼               └──────────┘  └──────────┘                         │
│  ┌─────────────────┐                                                         │
│  │ Variable-sized  │──Yes──▶ ┌──────────┐                                   │
│  │    objects?     │         │   GDSF   │                                    │
│  └─────────────────┘         └──────────┘                                    │
│                                                                              │
└─────────────────────────────────────────────────────────────────────────────┘

§Quick Reference

Algorithm	Description	Best Use Case
`LruCache`	Least Recently Used	General purpose, recency-based access
`SlruCache`	Segmented LRU	Mixed workloads with scans
`LfuCache`	Least Frequently Used	Stable popularity patterns
`LfudaCache`	LFU with Dynamic Aging	Long-running, evolving popularity
`GdsfCache`	Greedy Dual Size Frequency	CDNs, variable-sized objects

§Performance Characteristics

Algorithm	Get	Put	Remove	Memory/Entry	Scan Resist	Adapts
LRU	O(1)	O(1)	O(1)	~80 bytes	Poor	N/A
SLRU	O(1)	O(1)	O(1)	~90 bytes	Good	N/A
LFU	O(1)	O(1)	O(1)	~100 bytes	Excellent	No
LFUDA	O(1)	O(1)	O(1)	~110 bytes	Excellent	Yes
GDSF	O(1)	O(1)	O(1)	~120 bytes	Good	Yes

§Code Examples

§LRU (Least Recently Used)

Evicts the item that hasn’t been accessed for the longest time. Simple and effective for workloads with temporal locality.

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use core::num::NonZeroUsize;

let config = LruCacheConfig {
    capacity: NonZeroUsize::new(2).unwrap(),
    max_size: u64::MAX,
};
let mut cache = LruCache::init(config, None);
cache.put("a", 1);
cache.put("b", 2);
cache.get(&"a");      // "a" becomes most recently used
cache.put("c", 3);    // "b" evicted (least recently used)
assert!(cache.get(&"b").is_none());

§SLRU (Segmented LRU)

Divides cache into probationary and protected segments. Items enter probationary and are promoted to protected on second access. Excellent scan resistance.

use cache_rs::SlruCache;
use cache_rs::config::SlruCacheConfig;
use core::num::NonZeroUsize;

let config = SlruCacheConfig {
    capacity: NonZeroUsize::new(100).unwrap(),
    protected_capacity: NonZeroUsize::new(20).unwrap(),
    max_size: u64::MAX,
};
let mut cache = SlruCache::init(config, None);

cache.put("hot", 1);
cache.get(&"hot");  // Promoted to protected segment!

§LFU (Least Frequently Used)

Tracks access frequency and evicts the least frequently accessed item. Great for workloads with stable popularity patterns.

use cache_rs::LfuCache;
use cache_rs::config::LfuCacheConfig;
use core::num::NonZeroUsize;

let config = LfuCacheConfig {
    capacity: NonZeroUsize::new(2).unwrap(),
    max_size: u64::MAX,
};
let mut cache = LfuCache::init(config, None);
cache.put("rare", 1);
cache.put("popular", 2);

// Access "popular" multiple times
for _ in 0..10 { cache.get(&"popular"); }

cache.put("new", 3);  // "rare" evicted (lowest frequency)
assert!(cache.get(&"popular").is_some());

§LFUDA (LFU with Dynamic Aging)

Addresses LFU’s “cache pollution” problem by incorporating aging. Old popular items gradually lose priority, allowing new items to compete fairly.

use cache_rs::LfudaCache;
use cache_rs::config::LfudaCacheConfig;
use core::num::NonZeroUsize;

let config = LfudaCacheConfig {
    capacity: NonZeroUsize::new(100).unwrap(),
    initial_age: 0,
    max_size: u64::MAX,
};
let mut cache = LfudaCache::init(config, None);

// Old popular items will eventually age out if not accessed
for i in 0..100 {
    cache.put(i, i);
}

§GDSF (Greedy Dual-Size Frequency)

Combines frequency, size, and aging. Priority = (Frequency / Size) + Age. Ideal for caching variable-sized objects like images or API responses.

use cache_rs::GdsfCache;
use cache_rs::config::GdsfCacheConfig;
use core::num::NonZeroUsize;

let config = GdsfCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    initial_age: 0.0,
    max_size: 10 * 1024 * 1024,  // 10MB
};
let mut cache: GdsfCache<String, Vec<u8>> = GdsfCache::init(config, None);

// Size-aware insertion
cache.put("small.txt".to_string(), vec![0u8; 100], 100);
cache.put("large.bin".to_string(), vec![0u8; 10000], 10000);
// Small items get higher priority per byte

§Concurrent Caches

Enable the concurrent feature for thread-safe versions:

[dependencies]
cache-rs = { version = "0.3", features = ["concurrent"] }

use cache_rs::ConcurrentLruCache;
use std::sync::Arc;

let cache = Arc::new(ConcurrentLruCache::new(10_000));

// Safe to share across threads
let cache_clone = Arc::clone(&cache);
std::thread::spawn(move || {
    cache_clone.put("key".to_string(), 42);
});

Concurrent caches use lock striping for high throughput:

┌────────────────────────────────────────────────────────────────────┐
│              ConcurrentCache (16 segments)                         │
│                                                                    │
│  ┌─────────┐ ┌─────────┐ ┌─────────┐     ┌─────────┐              │
│  │Segment 0│ │Segment 1│ │Segment 2│ ... │Segment15│              │
│  │ [Mutex] │ │ [Mutex] │ │ [Mutex] │     │ [Mutex] │              │
│  └─────────┘ └─────────┘ └─────────┘     └─────────┘              │
│       ▲           ▲           ▲               ▲                   │
│       │           │           │               │                   │
│  hash(k1)%16  hash(k2)%16  hash(k3)%16   hash(kN)%16              │
└────────────────────────────────────────────────────────────────────┘

§Dual-Limit Capacity

All caches support both entry count and size limits:

use cache_rs::LruCache;
use cache_rs::config::LruCacheConfig;
use core::num::NonZeroUsize;

// Limit by both count (1000 entries) AND size (10MB)
let config = LruCacheConfig {
    capacity: NonZeroUsize::new(1000).unwrap(),
    max_size: 10 * 1024 * 1024,
};
let mut cache: LruCache<String, Vec<u8>> = LruCache::init(config, None);

// Track size explicitly
let data = vec![0u8; 1024];
cache.put_with_size("file.bin".to_string(), data, 1024);

§Modules

lru: Least Recently Used cache implementation
slru: Segmented LRU cache implementation
lfu: Least Frequently Used cache implementation
lfuda: LFU with Dynamic Aging cache implementation
gdsf: Greedy Dual Size Frequency cache implementation
config: Configuration structures for all cache algorithms
metrics: Metrics collection for cache performance monitoring
concurrent: Thread-safe concurrent cache implementations (requires concurrent feature)

Re-exports§

pub use gdsf::GdsfCache;
pub use lfu::LfuCache;
pub use lfuda::LfudaCache;
pub use lru::LruCache;
pub use slru::SlruCache;
pub use entry::CacheEntry;
pub use meta::GdsfMeta;
pub use meta::LfuMeta;
pub use meta::LfudaMeta;
pub use meta::SlruMeta;
pub use meta::SlruSegment;
pub use concurrent::ConcurrentGdsfCache;
pub use concurrent::ConcurrentLfuCache;
pub use concurrent::ConcurrentLfudaCache;
pub use concurrent::ConcurrentLruCache;
pub use concurrent::ConcurrentSlruCache;

Modules§

concurrent: Concurrent cache implementations.
config: Cache configuration structures.
entry: Unified cache entry type.
gdsf: Greedy Dual-Size Frequency (GDSF) cache implementation.
lfu: Least Frequently Used (LFU) cache implementation.
lfuda: Least Frequently Used with Dynamic Aging (LFUDA) cache implementation.
lru: Least Recently Used (LRU) cache implementation.
meta: Algorithm-specific metadata types.
metrics: Cache metrics system.
slru: Segmented LRU (SLRU) cache implementation.

Crate cache_rs

Crate cache_rs Copy item path

§cache-rs

§The Problem with “One Size Fits All” Caching

§Why cache-rs?

§Quick Start

§Common API

§Example: Basic Usage

§Quick Reference

§Cache Size Configuration

§Understanding capacity and max_size

§Specifying Entry Size

§Sizing Strategies

§Count-Limited Cache (Entry Limit Only)

§Size-Limited Cache (Byte Budget)

§Balanced Cache (Both Limits)

§Eviction Behavior Examples

§Test with Your Own Traffic

§Eviction Algorithms

§LRU (Least Recently Used)

§SLRU (Segmented LRU)

§LFU (Least Frequently Used)

§LFUDA (LFU with Dynamic Aging)

§GDSF (Greedy Dual-Size Frequency)

§Concurrent Cache Support

§Why Mutex, Not RwLock?

§Available Types

§Example

§Zero-Copy Access

§Advanced: Disk-Backed and Tiered Caches

§Two-Tier Cache Pattern

§Performance

§no_std Support

§Feature Flags

§Roadmap & Contributing

§Planned Features

§How to Contribute

§Documentation

§License

§Security

§Code Reference

§Algorithm Selection Guide

§Quick Reference

§Performance Characteristics

§Code Examples

§LRU (Least Recently Used)

§SLRU (Segmented LRU)

§LFU (Least Frequently Used)

§LFUDA (LFU with Dynamic Aging)

§GDSF (Greedy Dual-Size Frequency)

§Concurrent Caches

§Dual-Limit Capacity

§Modules

Re-exports§

Modules§

Crate cache_rs

§Understanding `capacity` and `max_size`

§`no_std` Support