LRU Cache With TTL
Hard · Caching
In-memory caches in Node.js servers (like the lru-cache package) combine two limits: a maximum number of entries (least recently used goes first) and a time-to-live per entry.
Implement LruTtlCache({ maxSize, ttl, onEvict }). Times are simulated milliseconds passed as now.
- set(key, value, now, ttl?): the entry expires at now + (ttl ?? defaultTtl). An entry is expired when now >= expiresAt. Setting an existing key replaces value and expiry and makes it most recently used (no onEvict call).
- When a new key is set and the cache already holds maxSize entries: first remove every expired entry (onEvict(key, "expire"), least recently used first). If it is still full, remove the least recently used entry with onEvict(key, "evict"). Then insert.
- get(key, now): returns the value and makes the entry most recently used. It does not extend the TTL. A missing key returns undefined. An expired entry is removed (onEvict(key, "expire")) and undefined is returned.
- peek(key, now): like get, but never changes the recency order (expired entries are still removed).
- delete(key): removes the entry and returns true, or returns false if it was missing. It does not call onEvict.
- keys(now): removes expired entries (with "expire" events, least recently used first), then returns the keys from least to most recently used.
The driver runCache(options, ops) is already written. Ops are ["set", key, value, now, ttl?], ["get", key, now], ["peek", key, now], ["delete", key] and ["keys", now]; it returns a log that includes every onEvict call.