cache_mod/
ttl.rs

1//! Time-To-Live (TTL) cache — sharded, lazy-expiry reference implementation.
2
3use core::hash::Hash;
4use std::collections::HashMap;
5use std::num::NonZeroUsize;
6use std::time::{Duration, Instant};
7
8use crate::cache::Cache;
9use crate::error::CacheError;
10use crate::sharding::{self, Sharded};
11use crate::util::MutexExt;
12
13/// Fallback deadline span (~100 years) used when `Instant + ttl` would
14/// overflow. No realistic cache lifetime approaches this.
15const FAR_FUTURE: Duration = Duration::from_secs(60 * 60 * 24 * 365 * 100);
16
17/// A bounded, thread-safe cache with per-entry time-to-live.
18///
19/// Each entry is stamped with a deadline at insert time. On every access
20/// ([`get`](Cache::get), [`contains_key`](Cache::contains_key),
21/// [`len`](Cache::len)), expired entries are removed lazily. On overflow,
22/// the entry with the **soonest expiration** is evicted — already-expired
23/// entries are naturally preferred over live ones.
24///
25/// Both [`insert`](Cache::insert) and [`insert_with_ttl`](TtlCache::insert_with_ttl)
26/// reset the deadline on the affected entry — writes always re-arm the timer.
27///
28/// # Implementation
29///
30/// Sharded into up to 16 independent stores keyed by hash of `K`. Each
31/// shard owns its own `HashMap` and applies expiry / overflow eviction
32/// locally. Tiny caches (< 32 entries) use a single shard.
33///
34/// Eviction is **per-shard approximate** — overflow inside one shard
35/// evicts the soonest-expiring entry within that shard, not necessarily
36/// the soonest-expiring entry globally. Lazy expiry remains exact within
37/// the operating shard.
38///
39/// # Example
40///
41/// ```
42/// use std::time::Duration;
43/// use cache_mod::{Cache, TtlCache};
44///
45/// let cache: TtlCache<&'static str, u32> =
46///     TtlCache::new(4, Duration::from_secs(60)).expect("capacity > 0");
47///
48/// cache.insert("session", 42);
49/// assert_eq!(cache.get(&"session"), Some(42));
50/// ```
51pub struct TtlCache<K, V> {
52    capacity: NonZeroUsize,
53    default_ttl: Duration,
54    sharded: Sharded<Inner<K, V>>,
55}
56
57struct Entry<V> {
58    value: V,
59    expires_at: Instant,
60}
61
62struct Inner<K, V> {
63    capacity: NonZeroUsize,
64    map: HashMap<K, Entry<V>>,
65}
66
67impl<K, V> Inner<K, V>
68where
69    K: Eq + Hash + Clone,
70{
71    fn with_capacity(capacity: NonZeroUsize) -> Self {
72        let cap = capacity.get();
73        Self {
74            capacity,
75            map: HashMap::with_capacity(cap),
76        }
77    }
78}
79
80impl<K, V> TtlCache<K, V>
81where
82    K: Eq + Hash + Clone,
83    V: Clone,
84{
85    /// Creates a cache with the given capacity and default time-to-live.
86    ///
87    /// `ttl` is applied to every `insert` that does not specify its own.
88    /// Returns [`CacheError::InvalidCapacity`] if `capacity == 0`.
89    ///
90    /// # Example
91    ///
92    /// ```
93    /// use std::time::Duration;
94    /// use cache_mod::TtlCache;
95    ///
96    /// let cache: TtlCache<String, u32> =
97    ///     TtlCache::new(128, Duration::from_secs(300)).expect("capacity > 0");
98    /// ```
99    pub fn new(capacity: usize, ttl: Duration) -> Result<Self, CacheError> {
100        let cap = NonZeroUsize::new(capacity).ok_or(CacheError::InvalidCapacity)?;
101        Ok(Self::with_capacity(cap, ttl))
102    }
103
104    /// Creates a cache with the given non-zero capacity and default TTL.
105    /// Infallible.
106    ///
107    /// # Example
108    ///
109    /// ```
110    /// use std::num::NonZeroUsize;
111    /// use std::time::Duration;
112    /// use cache_mod::TtlCache;
113    ///
114    /// let cap = NonZeroUsize::new(64).expect("64 != 0");
115    /// let cache: TtlCache<String, u32> =
116    ///     TtlCache::with_capacity(cap, Duration::from_secs(60));
117    /// ```
118    pub fn with_capacity(capacity: NonZeroUsize, ttl: Duration) -> Self {
119        let num_shards = sharding::shard_count(capacity);
120        let per_shard = sharding::per_shard_capacity(capacity, num_shards);
121        let sharded = Sharded::from_factory(num_shards, |_| Inner::with_capacity(per_shard));
122        Self {
123            capacity,
124            default_ttl: ttl,
125            sharded,
126        }
127    }
128
129    /// Inserts `value` under `key` with a per-call TTL that overrides the
130    /// cache default. The deadline is `now + ttl`.
131    ///
132    /// Returns the previously-stored **live** value if `key` was already
133    /// present and not yet expired. An expired-but-not-yet-cleaned entry
134    /// is treated as absent: the call returns `None` and replaces it.
135    ///
136    /// # Example
137    ///
138    /// ```
139    /// use std::time::Duration;
140    /// use cache_mod::{Cache, TtlCache};
141    ///
142    /// let cache: TtlCache<u32, u32> =
143    ///     TtlCache::new(4, Duration::from_secs(60)).expect("capacity > 0");
144    ///
145    /// cache.insert_with_ttl(1, 10, Duration::from_secs(5));
146    /// assert_eq!(cache.get(&1), Some(10));
147    /// ```
148    pub fn insert_with_ttl(&self, key: K, value: V, ttl: Duration) -> Option<V> {
149        let deadline = compute_deadline(ttl);
150        let mut inner = self.sharded.shard_for(&key).lock_recover();
151        Self::insert_inner(&mut inner, key, value, deadline)
152    }
153
154    fn insert_inner(inner: &mut Inner<K, V>, key: K, value: V, deadline: Instant) -> Option<V> {
155        let now = Instant::now();
156
157        if let Some(existing) = inner.map.get_mut(&key) {
158            if existing.expires_at > now {
159                let old = core::mem::replace(&mut existing.value, value);
160                existing.expires_at = deadline;
161                return Some(old);
162            }
163        }
164
165        let _ = inner.map.remove(&key);
166
167        if inner.map.len() >= inner.capacity.get() {
168            if let Some(victim) = find_victim(&inner.map) {
169                let _ = inner.map.remove(&victim);
170            }
171        }
172
173        let _ = inner.map.insert(
174            key,
175            Entry {
176                value,
177                expires_at: deadline,
178            },
179        );
180        None
181    }
182}
183
184impl<K, V> Cache<K, V> for TtlCache<K, V>
185where
186    K: Eq + Hash + Clone,
187    V: Clone,
188{
189    fn get(&self, key: &K) -> Option<V> {
190        let mut inner = self.sharded.shard_for(key).lock_recover();
191        let now = Instant::now();
192        let expires_at = inner.map.get(key).map(|e| e.expires_at)?;
193        if expires_at <= now {
194            let _ = inner.map.remove(key);
195            return None;
196        }
197        inner.map.get(key).map(|e| e.value.clone())
198    }
199
200    fn insert(&self, key: K, value: V) -> Option<V> {
201        let deadline = compute_deadline(self.default_ttl);
202        let mut inner = self.sharded.shard_for(&key).lock_recover();
203        Self::insert_inner(&mut inner, key, value, deadline)
204    }
205
206    fn remove(&self, key: &K) -> Option<V> {
207        let mut inner = self.sharded.shard_for(key).lock_recover();
208        inner.map.remove(key).map(|e| e.value)
209    }
210
211    fn contains_key(&self, key: &K) -> bool {
212        let mut inner = self.sharded.shard_for(key).lock_recover();
213        let now = Instant::now();
214        let Some(expires_at) = inner.map.get(key).map(|e| e.expires_at) else {
215            return false;
216        };
217        if expires_at > now {
218            return true;
219        }
220        let _ = inner.map.remove(key);
221        false
222    }
223
224    fn len(&self) -> usize {
225        let mut total = 0;
226        for mutex in self.sharded.iter() {
227            let mut inner = mutex.lock_recover();
228            purge_expired(&mut inner.map);
229            total += inner.map.len();
230        }
231        total
232    }
233
234    fn clear(&self) {
235        for mutex in self.sharded.iter() {
236            let mut inner = mutex.lock_recover();
237            inner.map.clear();
238        }
239    }
240
241    fn capacity(&self) -> usize {
242        self.capacity.get()
243    }
244}
245
246fn compute_deadline(ttl: Duration) -> Instant {
247    let now = Instant::now();
248    match now.checked_add(ttl) {
249        Some(t) => t,
250        None => now.checked_add(FAR_FUTURE).unwrap_or(now),
251    }
252}
253
254fn find_victim<K, V>(map: &HashMap<K, Entry<V>>) -> Option<K>
255where
256    K: Clone,
257{
258    map.iter()
259        .min_by_key(|(_, e)| e.expires_at)
260        .map(|(k, _)| k.clone())
261}
262
263fn purge_expired<K, V>(map: &mut HashMap<K, Entry<V>>) {
264    let now = Instant::now();
265    map.retain(|_, entry| entry.expires_at > now);
266}
cache_mod/ttl.rs

cache_mod/
ttl.rs
