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.