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_budgetpops 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§
- Insert
IfAbsent NoEvict Result - Result of attempting to insert a key into a non-evicting replay barrier.