Simcache

A flexible, generic caching library for Rust with pluggable eviction policies and TTL support.

Overview

Simcache is designed around the Strategy pattern, allowing you to swap eviction policies at compile time while maintaining type safety and zero-cost abstractions. The library provides a clean separation between cache storage and eviction logic.

Core Design Principles

Generic Architecture with Trait-Based Eviction Policies

Design Choice: The cache is parameterized over three generic types: Simcache<K, V, E> where E implements the EvictionPolicy<K> trait.

Benefits:

• Compile-time policy selection: No runtime overhead for policy dispatch
• Type safety: Ensures eviction policies are compatible with key types
• Extensibility: Easy to add new eviction algorithms without modifying core cache logic
• Zero-cost abstractions: No dynamic dispatch or vtables

Trade-offs:

• Compile-time binding: Cannot change eviction policy after cache creation
• Code bloat: Each policy combination generates separate code
• Complex type signatures: Generic parameters make API more verbose

Dual Storage Strategy

Design Choice: The cache uses HashMap<K, (V, Option<Instant>)> for primary storage, with each eviction policy maintaining its own auxiliary data structures.

Benefits:

• O(1) lookups: HashMap provides constant-time access to values
• Flexible TTL: Optional expiration timestamps per item
• Policy independence: Each eviction policy can optimize its own data structures
• Memory efficiency: TTL storage is optional (uses Option<Instant>)

Trade-offs:

• Duplicate key storage: Keys are stored in both HashMap and policy structures

3. Eviction Policy Implementations

LRU (Least Recently Used)

Data Structure: VecDeque<K>

Design Choice: Simple queue-based approach with linear search for key removal.

Benefits:

• Simple implementation: Easy to understand and debug
• Low memory overhead: Single VecDeque stores access order
• Cache-friendly: VecDeque provides good memory locality

Trade-offs:

• O(n) key updates: Finding and removing existing keys requires linear search
• Frequent allocations: May trigger reallocations during queue operations
• Poor performance: Scales poorly with cache size for write-heavy workloads

LFU (Least Frequently Used)

Data Structure: HashMap<K, usize> + BTreeMap<usize, HashSet<K>>

Design Choice: Dual data structure approach for efficient frequency tracking.

Benefits:

• O(log n) eviction: BTreeMap provides efficient minimum frequency lookup
• O(1) frequency updates: HashMap allows constant-time count increments
• Efficient frequency grouping: Multiple keys with same frequency handled elegantly
• Clean empty bucket management: Automatic cleanup of empty frequency buckets

Trade-offs:

• Higher memory overhead: Two separate data structures plus HashSets
• Complex implementation: More intricate bookkeeping for frequency management

4. TTL (Time-To-Live) Integration

Design Choice: TTL is checked lazily during get() operations, with expired items removed immediately.

Benefits:

• Lazy expiration: No background threads or timers needed
• Efficient for read patterns: Expired items discovered naturally during access
• Simple implementation: No complex scheduling or cleanup logic
• Memory conscious: Expired items are removed as soon as they're accessed

Trade-offs:

• Lazy cleanup: Expired items may linger in memory until accessed
• Performance spikes: Expiration checking adds overhead to every get() call

5. Capacity Management

Design Choice: Eviction is triggered when inserting a new key would exceed max_capacity.

Benefits:

• Predictable memory usage: Hard limit on cache size
• Simple logic: Clear eviction trigger point
• Flexible sizing: Configurable maximum capacity

Trade-offs:

• No differentiation: Doesn't prioritize expired items for eviction
• Size estimation: Doesn't account for actual memory usage, only item count

Usage Examples

use simcache::{Simcache, eviction::{LRU, LFU}};
use std::time::Duration;

// LRU Cache
let mut lru_cache: Simcache<&str, String, LRU<&str>> = Simcache::new(100);
lru_cache.insert("key1", "value1".to_string(), None);

// LFU Cache with TTL
let mut lfu_cache: Simcache<i32, String, LFU<i32>> = Simcache::new(50);
lfu_cache.insert(1, "data".to_string(), Some(Duration::from_secs(300)));

// Pre-allocated cache
let mut cache = Simcache::new_with_capacity(1000, 1000);

Performance Characteristics

Operation	LRU	LFU
get()	O(n)	O(1)
insert()	O(n)	O(log n)
remove()	O(n)	O(log n)
Memory overhead	Low	High

Design Trade-offs Summary

Benefits of Current Design:

• Type safety: Compile-time guarantees about policy compatibility
• Performance: Zero-cost abstractions with efficient core operations
• Flexibility: Easy to add new eviction policies
• Simplicity: Clean separation of concerns

Limitations:

• LRU performance: Linear time complexity for updates limits scalability
• Memory usage: Dual storage and policy structures increase overhead
• TTL handling: Lazy expiration may allow temporary capacity violations
• Inflexibility: Cannot change policies at runtime

Recommended Use Cases:

• Small to medium caches
• Applications prioritizing correctness over maximum performance
• Scenarios requiring custom eviction policies
• Systems with predictable access patterns

Future Improvements

1. LRU Optimization: Replace VecDeque with HashMap + doubly-linked list for O(1) operations
2. Active TTL Management: Optional background cleanup for expired items
3. Memory-aware Eviction: Consider actual memory usage, not just item count
4. Concurrent Access: Thread-safe variants using locks or lock-free data structures
5. Metrics Collection: Built-in cache hit/miss statistics and performance monitoring