Skip to main content

hyprstream_util/
ttl_cache.rs

1//! Generic TTL cache with lazy, version-tagged eviction.
2//!
3//! `TtlCache<K, V>` is the shared eviction substrate used across
4//! hyprstream. It was extracted from the OAuth Client ID Metadata
5//! Document cache (`hyprstream::services::oauth::cimd_cache`) so that
6//! the same tested implementation can back both that cache and the
7//! discovery placement directory (see epic #523 / #524) — one eviction
8//! impl, no `moka` dependency.
9//!
10//! # Design
11//!
12//! * `entries: HashMap<K, Entry<V>>` — O(1) lookup.
13//! * `heap: BinaryHeap<Reverse<HeapEntry<K>>>` — min-heap of
14//!   `(expires_at, key, version)` for O(log n) ordered eviction.
15//! * **Lazy deletion** via a per-key version counter: on re-insert we
16//!   push a new heap node but do NOT walk the heap to remove the old
17//!   one. The reaper discards heap nodes whose version no longer
18//!   matches the map entry's version.
19//! * **Heartbeat refresh = re-insert.** Re-inserting a key bumps its
20//!   version tag and extends its expiry; the prior heap node becomes
21//!   stale and is reaped lazily.
22//! * **Inline reap** at every access, bounded to `reap_budget` pops per
23//!   call to keep tail latency predictable. No background task.
24//! * **Capacity bound**: when full, evict the next-to-expire entry.
25//!
26//! # Concurrency
27//!
28//! Thread-safe and cheap to share via `Arc`. All mutable state lives
29//! behind a single `parking_lot::Mutex`; operations are short, in-memory
30//! and lock-free of any `.await`, so the synchronous lock never spans an
31//! I/O point even when called from async code.
32
33use std::borrow::Borrow;
34use std::cmp::Reverse;
35use std::collections::{BinaryHeap, HashMap};
36use std::hash::Hash;
37use std::sync::atomic::{AtomicU64, Ordering};
38use std::time::{Duration, Instant};
39
40use parking_lot::Mutex;
41
42/// Result of attempting to insert a key into a non-evicting replay barrier.
43///
44/// Callers must distinguish a duplicate (a replay was blocked) from a full
45/// barrier (new traffic was refused to preserve previously recorded security
46/// state).
47#[derive(Debug, Clone, Copy, Eq, PartialEq)]
48pub enum InsertIfAbsentNoEvictResult {
49    /// The previously unseen key was recorded.
50    Inserted,
51    /// The key was already present and still live.
52    Duplicate,
53    /// The barrier had no capacity for a new key.
54    Full,
55}
56
57/// A cached value with its expiry instant and version tag.
58#[derive(Debug, Clone)]
59struct Entry<V> {
60    value: V,
61    expires_at: Instant,
62    /// Monotonic version per key, bumped on every insert. The reaper
63    /// compares this to a heap node's `version` to detect stale nodes
64    /// left behind by re-inserts.
65    version: u64,
66}
67
68/// Heap node ordered by `expires_at` (ties broken by key for
69/// determinism). Wrapped in `Reverse` to make the `BinaryHeap` a
70/// min-heap over `expires_at`.
71#[derive(Debug, Clone, Eq, PartialEq)]
72struct HeapEntry<K> {
73    expires_at: Instant,
74    key: K,
75    version: u64,
76}
77
78impl<K: Ord> Ord for HeapEntry<K> {
79    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
80        self.expires_at
81            .cmp(&other.expires_at)
82            .then_with(|| self.key.cmp(&other.key))
83    }
84}
85impl<K: Ord> PartialOrd for HeapEntry<K> {
86    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
87        Some(self.cmp(other))
88    }
89}
90
91struct Inner<K, V> {
92    entries: HashMap<K, Entry<V>>,
93    heap: BinaryHeap<Reverse<HeapEntry<K>>>,
94}
95
96/// Generic per-entry-TTL cache with lazy version-tagged eviction and a
97/// capacity bound. See the module docs for the design.
98///
99/// # Examples
100///
101/// ```
102/// use std::time::Duration;
103///
104/// use hyprstream_util::{InsertIfAbsentNoEvictResult, TtlCache};
105///
106/// let cache: TtlCache<String, u32> = TtlCache::new(16, 8);
107/// cache.insert("session-1".to_owned(), 42, Duration::from_secs(60));
108/// assert_eq!(cache.get("session-1"), Some(42));
109///
110/// // `insert_if_absent_no_evict` is the replay-barrier primitive: while the
111/// // entry is live, re-inserting the same key is reported as a duplicate, and
112/// // a full barrier reports exhaustion instead of evicting live replay state
113/// // (unlike `insert_if_absent`, which may evict to admit the new key).
114/// assert_eq!(
115///     cache.insert_if_absent_no_evict("session-1".to_owned(), 7, Duration::from_secs(60)),
116///     InsertIfAbsentNoEvictResult::Duplicate,
117/// );
118///
119/// // At capacity, a new key is refused rather than displacing a live entry.
120/// let barrier: TtlCache<String, u32> = TtlCache::new(1, 8);
121/// assert_eq!(
122///     barrier.insert_if_absent_no_evict("jti-a".to_owned(), 1, Duration::from_secs(60)),
123///     InsertIfAbsentNoEvictResult::Inserted,
124/// );
125/// assert_eq!(
126///     barrier.insert_if_absent_no_evict("jti-b".to_owned(), 2, Duration::from_secs(60)),
127///     InsertIfAbsentNoEvictResult::Full,
128/// );
129/// assert_eq!(barrier.get("jti-a"), Some(1), "live replay state preserved");
130/// ```
131pub struct TtlCache<K, V> {
132    inner: Mutex<Inner<K, V>>,
133    /// Maximum number of live entries. When full, an insert of a new key
134    /// first evicts the next-to-expire entry.
135    max_entries: usize,
136    /// Maximum heap pops per inline reap; bounds tail latency while
137    /// amortizing cleanup.
138    reap_budget: usize,
139    next_version: AtomicU64,
140}
141
142impl<K, V> TtlCache<K, V>
143where
144    K: Clone + Eq + Hash + Ord,
145{
146    /// Create a cache bounded to `max_entries`, reaping at most
147    /// `reap_budget` expired heap nodes per access.
148    #[must_use]
149    pub fn new(max_entries: usize, reap_budget: usize) -> Self {
150        Self {
151            inner: Mutex::new(Inner {
152                entries: HashMap::new(),
153                heap: BinaryHeap::new(),
154            }),
155            max_entries,
156            reap_budget,
157            next_version: AtomicU64::new(1),
158        }
159    }
160
161    /// Insert (or replace) `key` with `value`, expiring after `ttl`.
162    ///
163    /// Re-inserting an existing key refreshes it: a new version is
164    /// assigned and the prior heap node becomes stale (reaped lazily).
165    /// If the cache is at capacity and `key` is new, the next-to-expire
166    /// entry is evicted first.
167    pub fn insert(&self, key: K, value: V, ttl: Duration) {
168        let now = Instant::now();
169        let expires_at = now + ttl;
170        let version = self.next_version.fetch_add(1, Ordering::Relaxed);
171
172        let mut inner = self.inner.lock();
173        Self::reap(&mut inner, now, self.reap_budget);
174
175        if inner.entries.len() >= self.max_entries && !inner.entries.contains_key(&key) {
176            Self::evict_one(&mut inner);
177        }
178
179        inner.entries.insert(
180            key.clone(),
181            Entry {
182                value,
183                expires_at,
184                version,
185            },
186        );
187        inner.heap.push(Reverse(HeapEntry {
188            expires_at,
189            key,
190            version,
191        }));
192    }
193
194    /// Atomically insert `key` only if no live (unexpired) entry exists
195    /// for it, returning `true` if the key was newly inserted.
196    ///
197    /// Returns `false` when a live entry already exists — i.e. this key
198    /// is a duplicate/replay within its validity window. The check and
199    /// the insert happen under a single lock, so concurrent callers for
200    /// the same key cannot both observe "absent" (the race that a
201    /// `get`-then-`insert` sequence would open). Expired entries are
202    /// reaped inline first, so an expired entry does not block insertion.
203    ///
204    /// This is the primitive for replay/dedup caches (e.g. DPoP `jti`
205    /// replay prevention, RFC 9449 §11.1): a caller proceeds only when
206    /// this returns `true`, and rejects on `false`.
207    pub fn insert_if_absent(&self, key: K, value: V, ttl: Duration) -> bool {
208        let now = Instant::now();
209        let expires_at = now + ttl;
210        let version = self.next_version.fetch_add(1, Ordering::Relaxed);
211
212        let mut inner = self.inner.lock();
213        Self::reap(&mut inner, now, self.reap_budget);
214
215        if inner.entries.contains_key(&key) {
216            return false;
217        }
218        if inner.entries.len() >= self.max_entries {
219            Self::evict_one(&mut inner);
220        }
221        inner.entries.insert(
222            key.clone(),
223            Entry {
224                value,
225                expires_at,
226                version,
227            },
228        );
229        inner.heap.push(Reverse(HeapEntry {
230            expires_at,
231            key,
232            version,
233        }));
234        true
235    }
236
237    /// Atomically insert `key` only if it is absent and capacity is available.
238    ///
239    /// Unlike [`Self::insert_if_absent`], this variant never evicts a live
240    /// entry to make room. This fail-closed behavior is intended for replay caches
241    /// whose live entries are security state: evicting one early would allow
242    /// the corresponding assertion to be accepted again. The result separates
243    /// a blocked replay from exhaustion, so operators can alert on the latter.
244    pub fn insert_if_absent_no_evict(
245        &self,
246        key: K,
247        value: V,
248        ttl: Duration,
249    ) -> InsertIfAbsentNoEvictResult {
250        let now = Instant::now();
251        let expires_at = now + ttl;
252        let version = self.next_version.fetch_add(1, Ordering::Relaxed);
253
254        let mut inner = self.inner.lock();
255        Self::reap(&mut inner, now, self.reap_budget);
256
257        if inner.entries.contains_key(&key) {
258            return InsertIfAbsentNoEvictResult::Duplicate;
259        }
260        if inner.entries.len() >= self.max_entries {
261            return InsertIfAbsentNoEvictResult::Full;
262        }
263        inner.entries.insert(
264            key.clone(),
265            Entry {
266                value,
267                expires_at,
268                version,
269            },
270        );
271        inner.heap.push(Reverse(HeapEntry {
272            expires_at,
273            key,
274            version,
275        }));
276        InsertIfAbsentNoEvictResult::Inserted
277    }
278
279    /// Look up `key`, returning a clone of the value if present and not
280    /// yet expired. Performs a bounded inline reap first.
281    ///
282    /// Accepts any borrowed form of the key (e.g. `&str` for a
283    /// `String`-keyed cache) to avoid allocating on lookup.
284    pub fn get<Q>(&self, key: &Q) -> Option<V>
285    where
286        K: Borrow<Q>,
287        Q: Hash + Eq + ?Sized,
288        V: Clone,
289    {
290        let now = Instant::now();
291        let mut inner = self.inner.lock();
292        Self::reap(&mut inner, now, self.reap_budget);
293        let entry = inner.entries.get(key)?;
294        if now >= entry.expires_at {
295            None
296        } else {
297            Some(entry.value.clone())
298        }
299    }
300
301    /// Number of live (un-reaped) entries.
302    #[must_use]
303    pub fn len(&self) -> usize {
304        self.inner.lock().entries.len()
305    }
306
307    /// True when no entries are present.
308    #[must_use]
309    pub fn is_empty(&self) -> bool {
310        self.inner.lock().entries.is_empty()
311    }
312
313    /// Reap up to `budget` expired entries from the front of the heap.
314    /// Stale heap nodes (version mismatch) are discarded without
315    /// touching the map.
316    fn reap(inner: &mut Inner<K, V>, now: Instant, budget: usize) {
317        for _ in 0..budget {
318            let expired = match inner.heap.peek() {
319                Some(Reverse(top)) => top.expires_at <= now,
320                None => break,
321            };
322            if !expired {
323                break;
324            }
325            let Some(Reverse(popped)) = inner.heap.pop() else {
326                break;
327            };
328            if let Some(entry) = inner.entries.get(&popped.key) {
329                if entry.version == popped.version && entry.expires_at <= now {
330                    inner.entries.remove(&popped.key);
331                }
332                // else: stale heap node (entry was refreshed) — drop silently.
333            }
334        }
335    }
336
337    /// Evict the single next-to-expire entry. Walks past stale heap
338    /// nodes (version mismatch) until it finds a live victim, then
339    /// terminates.
340    fn evict_one(inner: &mut Inner<K, V>) {
341        while let Some(Reverse(top)) = inner.heap.pop() {
342            if let Some(entry) = inner.entries.get(&top.key) {
343                if entry.version == top.version {
344                    inner.entries.remove(&top.key);
345                    return;
346                }
347                // Stale heap node — keep popping.
348            }
349        }
350    }
351}
352
353#[cfg(test)]
354#[allow(clippy::unwrap_used, clippy::expect_used)]
355mod tests {
356    use super::*;
357
358    #[test]
359    fn insert_and_get_roundtrip() {
360        let cache: TtlCache<String, u32> = TtlCache::new(10_000, 16);
361        cache.insert("a".to_owned(), 1, Duration::from_secs(60));
362        assert_eq!(cache.get("a"), Some(1));
363        assert_eq!(cache.len(), 1);
364        assert!(!cache.is_empty());
365    }
366
367    #[test]
368    fn borrowed_key_lookup_avoids_allocation() {
369        // String-keyed cache, looked up by &str.
370        let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
371        cache.insert("https://a.test/c".to_owned(), 7, Duration::from_secs(60));
372        let key: &str = "https://a.test/c";
373        assert_eq!(cache.get(key), Some(7));
374    }
375
376    #[test]
377    fn expired_entry_returns_none() {
378        let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
379        cache.insert("a".to_owned(), 1, Duration::from_millis(5));
380        std::thread::sleep(Duration::from_millis(20));
381        assert_eq!(cache.get("a"), None);
382    }
383
384    #[test]
385    fn reinsert_refreshes_and_does_not_leak_heap() {
386        let cache: TtlCache<String, u32> = TtlCache::new(10_000, 32);
387        // Five short-TTL versions of the same key.
388        for v in 0..5 {
389            cache.insert("a".to_owned(), v, Duration::from_millis(5));
390        }
391        std::thread::sleep(Duration::from_millis(20));
392        // A long-TTL re-insert; the reap during insert clears stale nodes.
393        cache.insert("a".to_owned(), 99, Duration::from_secs(60));
394        assert_eq!(cache.len(), 1);
395        assert_eq!(cache.get("a"), Some(99));
396    }
397
398    #[test]
399    fn refresh_extends_expiry() {
400        let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
401        cache.insert("a".to_owned(), 1, Duration::from_millis(30));
402        std::thread::sleep(Duration::from_millis(15));
403        // Heartbeat: re-insert before expiry extends the lifetime.
404        cache.insert("a".to_owned(), 2, Duration::from_secs(60));
405        std::thread::sleep(Duration::from_millis(30));
406        // Original TTL has elapsed, but the refresh keeps it alive.
407        assert_eq!(cache.get("a"), Some(2));
408    }
409
410    #[test]
411    fn capacity_bound_evicts_next_to_expire() {
412        let cache: TtlCache<String, u32> = TtlCache::new(2, 16);
413        cache.insert("a".to_owned(), 1, Duration::from_secs(10));
414        cache.insert("b".to_owned(), 2, Duration::from_secs(60));
415        // Capacity reached; inserting a 3rd evicts the next-to-expire (a).
416        cache.insert("c".to_owned(), 3, Duration::from_secs(30));
417        assert_eq!(cache.len(), 2);
418        assert_eq!(cache.get("a"), None);
419        assert_eq!(cache.get("b"), Some(2));
420        assert_eq!(cache.get("c"), Some(3));
421    }
422
423    #[test]
424    fn evict_one_terminates_under_stale_heap_pressure() {
425        // Small reap budget keeps reap from clearing the stale nodes, so
426        // evict_one must walk past them to find a live victim.
427        let cache: TtlCache<String, u32> = TtlCache::new(2, 4);
428        for v in 0..50 {
429            cache.insert("a".to_owned(), v, Duration::from_secs(120));
430        }
431        cache.insert("b".to_owned(), 1, Duration::from_secs(60));
432        assert_eq!(cache.len(), 2, "A + B at capacity");
433
434        // Insert C — triggers evict_one past 49 stale A nodes.
435        cache.insert("c".to_owned(), 2, Duration::from_secs(180));
436        assert_eq!(cache.len(), 2, "still 2 after eviction");
437        assert_eq!(cache.get("b"), None, "B (shortest TTL) is the victim");
438        assert!(cache.get("a").is_some(), "A still present");
439        assert_eq!(cache.get("c"), Some(2), "C just inserted");
440    }
441
442    #[test]
443    fn lazy_delete_keeps_live_entry_after_stale_node_reaped() {
444        // Insert short-lived v0, then refresh to long-lived v1 before
445        // expiry. The v0 heap node is now stale; reaping it must NOT
446        // evict the live v1 entry.
447        let cache: TtlCache<String, u32> = TtlCache::new(10, 16);
448        cache.insert("a".to_owned(), 0, Duration::from_millis(5));
449        cache.insert("a".to_owned(), 1, Duration::from_secs(60));
450        std::thread::sleep(Duration::from_millis(20));
451        // get triggers a reap that pops the stale (expired) v0 node.
452        assert_eq!(cache.get("a"), Some(1));
453        assert_eq!(cache.len(), 1);
454    }
455
456    #[test]
457    fn insert_if_absent_rejects_duplicate_within_window() {
458        let cache: TtlCache<String, ()> = TtlCache::new(10, 16);
459        assert!(cache.insert_if_absent("jti-1".to_owned(), (), Duration::from_secs(60)));
460        assert!(!cache.insert_if_absent("jti-1".to_owned(), (), Duration::from_secs(60)));
461        assert!(cache.insert_if_absent("jti-2".to_owned(), (), Duration::from_secs(60)));
462        assert_eq!(cache.len(), 2);
463    }
464
465    #[test]
466    fn insert_if_absent_accepts_after_expiry() {
467        let cache: TtlCache<String, ()> = TtlCache::new(10, 16);
468        assert!(cache.insert_if_absent("jti".to_owned(), (), Duration::from_millis(5)));
469        std::thread::sleep(Duration::from_millis(20));
470        assert!(cache.insert_if_absent("jti".to_owned(), (), Duration::from_secs(60)));
471    }
472
473    #[test]
474    fn insert_if_absent_no_evict_fails_closed_at_capacity() {
475        let cache: TtlCache<String, ()> = TtlCache::new(2, 16);
476        assert_eq!(
477            cache.insert_if_absent_no_evict("jti-1".to_owned(), (), Duration::from_secs(60)),
478            InsertIfAbsentNoEvictResult::Inserted
479        );
480        assert_eq!(
481            cache.insert_if_absent_no_evict("jti-2".to_owned(), (), Duration::from_secs(60)),
482            InsertIfAbsentNoEvictResult::Inserted
483        );
484
485        assert_eq!(
486            cache.insert_if_absent_no_evict("jti-1".to_owned(), (), Duration::from_secs(60)),
487            InsertIfAbsentNoEvictResult::Duplicate,
488            "a replay and capacity exhaustion must be distinguishable"
489        );
490        assert_eq!(
491            cache.insert_if_absent_no_evict("jti-3".to_owned(), (), Duration::from_secs(60)),
492            InsertIfAbsentNoEvictResult::Full,
493            "a full barrier must not evict the earlier jti"
494        );
495        assert_eq!(cache.len(), 2);
496        assert_eq!(cache.get("jti-1"), Some(()));
497        assert_eq!(cache.get("jti-2"), Some(()));
498    }
499}