Design a TTL-Aware LRU Cache Without Full Expiration Scans

Design an in-memory cache that combines a capacity limit, least-recently-used eviction, and time-to-live expiration. Explain how reads and writes update its state, how concurrent access is coordinated, and how expiration can be maintained without periodically scanning every key. ### Constraints & Assumptions - The source describes an open-ended cache discussion that settles on TTL plus LRU, followed by an alternative to full-table expiration scans. - **Practice contract:** capacity is a count of entries; a write assigns or replaces a key's value and expiration deadline; a successful read refreshes recency but does not extend TTL. A key is expired when the current monotonic time is at or after its deadline. - The source does not supply API names, capacity, TTL units, or concurrency guarantees. Treat the practice contract as explicit choices, not original company requirements. - Logical expiration must be correct on access even if background cleanup has not yet reclaimed the entry. ### Clarifying Questions to Ask - Is capacity measured in entries or bytes, and do expired entries count while awaiting cleanup? - Does a read refresh TTL, and does an update replace both value and expiration? - What must happen for zero capacity or a nonpositive TTL? - Are operations linearizable across threads, or is weaker consistency acceptable? ### Part 1 — Combine Expiration and LRU Describe the lookup and recency structures, read/write behavior, and eviction order. Specify how an expired key is removed without returning stale data. #### What This Part Should Cover - Constant-time key lookup and recency updates under ordinary hash-map assumptions. - Separation of recency order from expiration order. - Consistent removal from all live-entry structures. ### Part 2 — Replace the Expiration Scan Propose an expiry index or scheduling structure. Explain how it handles rewritten keys whose old expiration records remain queued, and discuss the memory and timing trade-offs. #### What This Part Should Cover - Due-entry processing without an unconditional full-map scan. - Stale-record detection using version or identity. - Cleanup backlog, bounded work, and concurrency with reads/writes. ```hint A recently read item may expire next LRU order reflects access history, while TTL order reflects deadlines. One list does not generally answer both eviction questions. ``` ### What a Strong Answer Covers - Precise TTL and recency behavior with no stale reads. - Capacity enforcement, synchronized mutations, and removal consistency. - A practical expiry mechanism with explicit update, memory, and cleanup costs. ### Follow-up Questions - How would byte-based capacity change eviction accounting? - When might a timing wheel be preferable to a heap, and what expiration precision does it require? - How could a burst of expirations affect a foreground operation if cleanup runs while holding one global lock?