Design an In-Memory Key-Value Store with TTL
Fast recall
Quick revision
Core answer
Storage choice (ConcurrentHashMap), expiration strategies (lazy vs active), data structures for scheduled eviction (DelayQueue vs timing wheel), and concurrency correctness.
Polling all keys on a timer (O(N) on every tick), or using `Timer`/`ScheduledExecutorService` for each key's expiration (memory blow-up).
Walk through the lazy + active hybrid, explain when DelayQueue is fine vs when a timing wheel is needed, and discuss memory reclamation for expired entries that haven't been evicted yet.
Interview-ready guide
Interview answer
The data structure
ConcurrentHashMap keyed by the user's key, value is an Entry record holding (value, expiresAt). All operations are O(1) average for the map; the interesting question is expiration.
Two strategies, used together
- Lazy on get: check expiresAt; if past, remove and return null. Cheap, only touches keys you actually read.
- Active sweep: a background thread that knows what's expiring next and removes it.
Lazy alone leaves never-accessed-again expired keys sitting in memory forever. Active alone has a brief race window where get could return an expired value before the sweeper gets to it. Together: correctness from lazy, memory bound from active.
What active sweep data structure
Naive scan of all keys on a timer is O(N) per tick — melts at 10M keys.
One ScheduledExecutorService task per key blows up memory — 200 bytes per scheduled task times 10M = 2 GB just for scheduler overhead.
DelayQueue — a single PriorityQueue of expiry events ordered by time. O(log N) insertion. Background thread blocks on take() until next expiry. Works well to about 1M pending entries.
Hashed timing wheel (Netty's pattern) — array of buckets each representing a time slot. Schedule is O(1), tick processing is proportional to bucket size, not total entries. Hierarchical wheels (multiple resolutions) handle large TTL ranges.
The hybrid implementation
DelayQueue + lazy is the sweet spot for most cases:
- put creates an Entry, puts it in the map, offers it to the DelayQueue
- get checks expiry lazily
- A daemon sweeper thread blocks on
expiryQ.take(), processes expired entries one at a time
Critical correctness detail: when the sweeper picks up an entry, it checks map.get(key) == thatExactEntry before removing — because the user might have called put again with a different TTL, in which case the queue entry is stale and should be skipped.
Use System.nanoTime() for TTL math (monotonic, clock-skew-proof); only use currentTimeMillis for human-display.
When to upgrade to timing wheel
DelayQueue's O(log N) insertion becomes the bottleneck somewhere around 10M+ pending entries with ms-precision TTLs. At that point, switch to a hashed wheel. For Java, use io.netty.util.HashedWheelTimer rather than rolling your own.
LLD
TtlKvStorefacade with put/get/delete/setTtlStorageinterface (ConcurrentMapStorage impl) — swappable for sharded backend laterExpirationStrategyinterface (DelayQueue impl, TimingWheel impl, lazy-only impl) — swap based on scaleEntryrecord with value + expiresAtNs
Edge cases
- Updating value with new TTL: put replaces both; old queue entry skipped via reference check
- TTL = 0: reject or treat as immediate
- setTtl on missing key: false/no-op per contract
- Memory reclamation: track sweep lag; alert if active sweep falls behind
- OOM risk if sweeper stalls: combine with LRU, evict by recency under memory pressure
Failure modes
- Sweeper crash: lazy expiration still correct for accessed keys; memory grows for the rest; watchdog restart
- Hot key with frequent TTL updates: garbage queue entries accumulate; periodic compaction
- Timing-wheel latency spikes from huge buckets: batch-process across ticks
Recommendation
ConcurrentHashMap with Entry(value, expiresAtNs), lazy expiration on get for correctness, plus a single DelayQueue-backed sweeper thread for active eviction with reference-equality skip-stale logic. Upgrade to a hashed (or hierarchical) timing wheel once pending entries exceed the low millions or precision needs become tight. For production, lean on Caffeine's `expireAfterWrite`/`expireAfterAccess` or Netty's HashedWheelTimer rather than rolling your own.
Design an In-Memory Key-Value Store with TTL
Direct Answer
Use a ConcurrentHashMap keyed by String holding Entry(value, expiresAt) records. Combine lazy expiration on access (cheap, only touches keys you read) with active expiration via a DelayQueue or hashed timing wheel for efficient bulk eviction. For very large datasets, replace the global delay queue with a hierarchical timing wheel (Netty's pattern) — O(1) schedule and tick, low memory overhead, scales to millions of pending expirations.
Common Mistakes & Pitfalls
Polling all keys on a timer (O(N) on every tick), or using Timer/ScheduledExecutorService for each key's expiration (memory blow-up).
Check your understanding
Answer these without looking back at the article.
- How would you implement `ttl(key)` returning the remaining time to live?
- Combine TTL with a max-size LRU policy — what's the eviction priority order?
- How would you make the store distributed across multiple JVMs while preserving TTL semantics?
- What changes if you need persistence (survive process restarts)?
Related interview prep categories
2Want a guided curriculum order?
These modules are also sequenced in our flagship backend interview track — open it when you prefer an ordered path instead of browsing by topic.