Skip to main content

Module ttl_cache

Module ttl_cache 

Source
Expand description

Generic TTL cache with lazy, version-tagged eviction.

TtlCache<K, V> is the shared eviction substrate used across hyprstream. It was extracted from the OAuth Client ID Metadata Document cache (hyprstream::services::oauth::cimd_cache) so that the same tested implementation can back both that cache and the discovery placement directory (see epic #523 / #524) — one eviction impl, no moka dependency.

§Design

  • entries: HashMap<K, Entry<V>> — O(1) lookup.
  • heap: BinaryHeap<Reverse<HeapEntry<K>>> — min-heap of (expires_at, key, version) for O(log n) ordered eviction.
  • Lazy deletion via a per-key version counter: on re-insert we push a new heap node but do NOT walk the heap to remove the old one. The reaper discards heap nodes whose version no longer matches the map entry’s version.
  • Heartbeat refresh = re-insert. Re-inserting a key bumps its version tag and extends its expiry; the prior heap node becomes stale and is reaped lazily.
  • Inline reap at every access, bounded to reap_budget pops per call to keep tail latency predictable. No background task.
  • Capacity bound: when full, evict the next-to-expire entry.

§Concurrency

Thread-safe and cheap to share via Arc. All mutable state lives behind a single parking_lot::Mutex; operations are short, in-memory and lock-free of any .await, so the synchronous lock never spans an I/O point even when called from async code.

Structs§

TtlCache
Generic per-entry-TTL cache with lazy version-tagged eviction and a capacity bound. See the module docs for the design.

Enums§

InsertIfAbsentNoEvictResult
Result of attempting to insert a key into a non-evicting replay barrier.