Free lesson · Concurrency Interview Mastery

Exercise: Design a Thread-Safe Cache with TTL

Hard5 min readconcurrencymultithreadinginterview-prep

This exercise builds the lazy-expiration cache, adds active expiration, and diagnoses the classic TTL-cache concurrency bugs. Reason each through before the solution - the goal is to wield the atomic conditional remove (avoiding the check-then-act race on expiry) and to weigh lazy versus active reclamation.

Important: Two anchors: store an absolute expiry time and remove expired entries with an atomic conditional remove (map.remove(key, entry) - only if still this entry), so a concurrent fresh put is never clobbered; and lazy expiration keeps reads correct but leaks memory for untouched keys - a background sweeper reclaims it.

Part 1 - Lazy expiration

Your task: Implement put and get on a concurrent map with lazy expiration. Explain why you store absolute expiry time and how get handles an expired entry safely.

map = ConcurrentHashMap<K, Entry>, Entry = {value, expiryTime}. put(k,v,ttl): map.put(k, Entry(v, now()+ttl)) - store absolute time so expiry is a simple <= now() check. get(k): e = map.get(k); if e==null return null; if e.expiryTime <= now(): map.remove(k, e); return null; return e.value. The conditional remove(k, e) removes only if the key still maps to this entry, avoiding clobbering a concurrent fresh put. </details>

Part 2 - Active expiration

Your task: Add a background sweeper that reclaims expired entries even if they're never accessed. How do you make it efficient rather than scanning the whole map every time?

A ScheduledExecutorService runs a sweep periodically. Naive: scan all entries, remove expired - O(n) per sweep. Efficient: maintain a DelayQueue or priority queue of (expiryTime, key) ordered by expiry; the sweeper pops only entries whose expiry has passed (O(log n) each), removing each from the map with a conditional remove (only if still the expired entry). Pair lazy (correctness) with the sweeper (memory hygiene). </details>

Part 3 - Find the bugs

// Bug A - non-atomic expiry removal:
function get(key):
    entry = map.get(key)
    if entry != null and entry.expiryTime <= now():
        map.remove(key)                  // <-- unconditional remove
        return null
    return entry == null ? null : entry.value

// Bug B - TTL stored as duration:
function put(key, value, ttlMillis):
    map.put(key, new Entry(value, ttlMillis))     // <-- stores the duration
function get(key):
    entry = map.get(key)
    if entry != null and entry.expiryTime <= now(): ...   // compares duration to now()

Your task: Identify each bug and its effect.

Bug A: map.remove(key) removes unconditionally. Between reading the expired entry and removing, another thread could put a fresh value for key - the unconditional remove then deletes the new value (data loss). Fix: map.remove(key, entry) (conditional - only if still the expired entry). Bug B: the entry stores the TTL duration (e.g., 5000ms) as expiryTime, but get compares it to now() (a large absolute timestamp). Since 5000 <= now() is always true, every entry is treated as expired immediately. Fix: store now() + ttlMillis (absolute expiry). </details>

Solution

Part 1 - Lazy expiration

class Entry<V>:
    value: V
    expiryTime: long             # absolute: now() + ttl

map = ConcurrentHashMap<K, Entry<V>>()

function put(key, value, ttlMillis):
    map.put(key, new Entry(value, now() + ttlMillis))

function get(key):
    entry = map.get(key)
    if entry == null:
        return null
    if entry.expiryTime <= now():            # expired
        map.remove(key, entry)               # ATOMIC conditional remove
        return null
    return entry.value

Storing the absolute expiry time (now() + ttlMillis) makes the expiry check a trivial comparison against the current time, with no need to separately track insertion time. The crucial concurrency detail is the atomic conditional remove: map.remove(key, entry) removes the mapping only if key currently maps to this exact entry. If, between our map.get and our remove, another thread called put(key, freshValue, ...), then key now maps to a different entry, so our conditional remove does nothing and the fresh value is preserved. An unconditional map.remove(key) would instead clobber the fresh value - the check-then-act race. This lazy approach keeps reads correct (an expired entry is never returned) with no background machinery.

Part 2 - Active expiration

# (expiryTime, key) ordered by expiry; sweeper pops only what has actually expired
delayQueue = DelayQueue<ExpiringKey>()      # ExpiringKey.getDelay() = expiryTime - now()
scheduler  = ScheduledExecutorService

function put(key, value, ttlMillis):
    expiry = now() + ttlMillis
    map.put(key, new Entry(value, expiry))
    delayQueue.put(new ExpiringKey(key, expiry))

# sweeper loop (background thread):
function sweep():
    while true:
        expiringKey = delayQueue.take()      # blocks until an entry's delay elapses
        entry = map.get(expiringKey.key)
        if entry != null and entry.expiryTime <= now():
            map.remove(expiringKey.key, entry)   # conditional remove

The sweeper reclaims memory for entries that are never get-accessed (which lazy expiration would leave forever). The efficiency trick is the DelayQueue (a priority queue whose take() blocks until the head's delay elapses): the sweeper sleeps until the next entry actually expires, then pops exactly that entry - O(log n) per expiry - rather than periodically scanning the whole map (O(n) per sweep). Each popped key is removed with a conditional remove (so a fresh put since the entry was queued isn't clobbered). Pairing this with Part 1's lazy check gives the production-grade combination: lazy guarantees reads never see expired data; the sweeper guarantees memory is reclaimed regardless of access pattern. (A simpler ScheduledExecutorService scanning periodically also works but is O(n) per scan.)

Part 3 - The bugs

Bug A - unconditional removal (check-then-act race). map.remove(key) removes whatever is currently mapped, not specifically the expired entry we observed. Sequence: thread 1 reads an expired entry for key; thread 2 calls put(key, freshValue) (now key maps to a fresh, live entry); thread 1 calls map.remove(key) - deleting the fresh value thread 2 just inserted. Result: silent data loss, and the next get is a spurious miss. The fix is the conditional remove map.remove(key, entry), which removes only if key still maps to the expired entry we saw - so if thread 2's fresh put happened, our remove is a no-op. This is the canonical check-then-act race in a TTL cache, and the conditional (CAS-style) remove is the canonical fix.

Bug B - TTL stored as duration instead of absolute time. new Entry(value, ttlMillis) stores the duration (e.g., 5000) in the expiryTime field, but get compares expiryTime <= now(), where now() is a large absolute timestamp (e.g., milliseconds since epoch). Since 5000 <= now() is essentially always true, every entry is judged expired the instant it's read - the cache never returns anything. The fix is to store the absolute expiry: now() + ttlMillis. This is a common, easy-to-miss bug: the expiry field must be a point in time comparable to now(), not a duration. (Symmetrically, if you store duration you must also store insertion time and compare insertionTime + duration <= now() - but storing absolute expiry is simpler.)

Both bugs reinforce the essentials: atomic conditional removal (Bug A) and absolute expiry time (Bug B).

Common mistakes

Warning: Watch for: (1) Unconditional expiry removal - clobbers a concurrent fresh put; use remove(key, entry). (2) Storing TTL as duration - compared against now(), everything looks expired; store absolute now()+ttl. (3) Using a plain HashMap - not thread-safe; use ConcurrentHashMap (or explicit locking). (4) Lazy-only with an unbounded keyspace - untouched expired entries leak memory; add a sweeper. (5) Sweeper scanning the whole map - O(n); use a DelayQueue/PQ ordered by expiry. (6) Non-atomic refresh-on-access - use compute/merge for per-key read-modify-write.

Why this exercise matters for interviews

Interview: The TTL cache is a staple concurrency design question, and this exercise mirrors the typical interview arc. Part 1 (lazy expiration) centers on the atomic conditional remove - catching and fixing the check-then-act race is the key concurrency signal. Part 2 (active expiration) tests whether you can make reclamation efficient (a DelayQueue by expiry, not an O(n) scan) and recognize that production caches do both lazy and active. Part 3 (bugs) targets the two signature errors: unconditional removal (race) and duration-vs-absolute expiry. The throughline interviewers reward: a concurrent map with absolute-expiry entries, atomic conditional removal for expiry, lazy+active expiration for correctness+memory, and awareness that size-bounded LRU eviction is the hard extension (reach for Caffeine/Guava).

Back to Concurrency Interview Mastery