Free lesson · Concurrency Interview Mastery
Designing a Thread-Safe Cache with TTL
Now the module shifts from canonical puzzles to design problems - the "design a thread-safe X" questions that dominate real concurrency interviews. The first is one of the most common: a thread-safe cache where entries expire after a time-to-live (TTL). It sounds simple - a map with timestamps - but the concurrency makes it genuinely interesting: many threads read and write simultaneously, entries must expire correctly without a check-then-act race, and you must decide when expiration happens (lazily on access, or actively via a background sweeper) - a trade-off between simplicity and memory. This problem exercises concurrent maps, atomic compound operations, the lazy-vs-active background-work decision (which recurs in the rate limiter next), and eviction policies. It's a favorite because it has a clean core that you can extend in many directions, letting an interviewer calibrate depth. We'll design the API, identify the concurrency hazards, and build a solution from a concurrent map plus careful atomicity.
Requirements and API
The cache stores key-value pairs, each with a TTL after which it's considered absent. The core API:
interface TTLCache<K, V>:
put(key: K, value: V, ttlMillis: long) # store with a time-to-live
get(key: K) -> V or null # return value if present AND not expired
remove(key: K) # explicit removal
# optional: size(), clear()
The requirements:
- Correctness under concurrency: any number of threads may
getandputsimultaneously, on the same or different keys, without corrupting the cache or returning stale/torn data. - TTL semantics: a
getfor an expired entry must behave as a miss (return null), and the expired entry should eventually be reclaimed (not leak memory forever). - Performance: reads (typically the dominant operation in a cache) should be highly concurrent - a single global lock that serializes every
getwould defeat the purpose of a cache. - Optional extensions: a maximum size with an eviction policy (LRU), refresh-on-access (sliding TTL), and per-entry vs. global TTL.
The central design tension is when and how expired entries are removed, and how to make the compound operations (check-expiry-then-act) atomic without a coarse global lock.
The concurrency challenges
Three hazards define the problem:
- Concurrent reads and writes on the structure. The backing map must tolerate simultaneous
get/put. A plainHashMapis not thread-safe (concurrent writes can corrupt it, even infinite-loop in older implementations), so we need a concurrent map or explicit locking - and ideally one that permits concurrent reads rather than serializing them. - The expiry check-then-act race. A
getthat does "look up entry → check if expired → if expired, remove it" is a compound operation. Between the check and the remove, another thread couldputa fresh value for that key - and the naive remove would then delete the new value. The expiry decision and the action on it must be atomic with respect to other operations on that key. - Reclaiming expired entries. Expired entries that are never accessed again sit in the map consuming memory. Deciding whether to clean them lazily (only when touched) or actively (a background sweep) is a memory-vs-overhead trade-off with concurrency implications (the sweeper races with readers/writers).
The design
The backbone is a concurrent map from key to an entry holding the value and its absolute expiry time, with lazy expiration on read and an optional active sweeper:
class Entry<V>:
value: V
expiryTime: long # ABSOLUTE time (now + ttl), not the duration
map = ConcurrentHashMap<K, Entry<V>>()
function put(key, value, ttlMillis):
map.put(key, new Entry(value, now() + ttlMillis)) # store absolute expiry
function get(key):
entry = map.get(key)
if entry == null: return null
if entry.expiryTime <= now(): # expired
map.remove(key, entry) # ATOMIC conditional remove (see below)
return null
return entry.value
Two design choices are crucial. First, store the absolute expiry time (now() + ttl), not the TTL duration - so checking expiry is a simple expiryTime <= now() comparison with no need to track when the entry was inserted separately. Second, the expiry-triggered removal uses a conditional/atomic remove - map.remove(key, entry) removes the key only if it currently maps to this exact expired entry. This closes the check-then-act race: if another thread put a fresh entry between our read and our remove, the map no longer maps the key to our (expired) entry, so the conditional remove is a no-op and the fresh value survives. This is the atomic-compound-operation discipline (Module 5/6) applied via the concurrent map's CAS-based conditional methods.
flowchart TD
GET["get(key)"] --> LOOK["entry = map.get(key)"]
LOOK --> NULL{entry null?}
NULL -->|yes| MISS[return null]
NULL -->|no| EXP{"expiryTime <= now()?"}
EXP -->|"no (live)"| HIT[return entry.value]
EXP -->|"yes (expired)"| CREM["map.remove(key, entry)<br/>ATOMIC: only if still THIS entry"]
CREM --> MISS
PUT["put(key, value, ttl)"] --> STORE["map.put(key,<br/>Entry(value, now()+ttl))"]
SWEEP["background sweeper (optional)<br/>periodically scans + removes expired"] -.-> map[("ConcurrentHashMap")]
note["Lazy expiry on get via ATOMIC conditional remove (no check-then-act race).<br/>Optional active sweeper reclaims untouched expired entries."]
This flowchart shows the thread-safe TTL cache. A get operation looks up the entry in a concurrent hash map. If the entry is null, it returns a miss. If the entry exists, it checks whether the absolute expiry time has passed. If the entry is still live, it returns the value. If the entry is expired, it performs an atomic conditional remove - removing the key only if it still maps to this exact expired entry - which avoids a check-then-act race where another thread might have inserted a fresh value. A put operation stores an entry with the value and an absolute expiry time computed as now plus the TTL. Optionally, a background sweeper thread periodically scans the map and removes expired entries that have not been accessed, reclaiming memory that lazy expiration alone would leave in place.
Lazy versus active expiration
The expiration strategy is the key design decision, and a strong answer discusses both:
- Lazy expiration (on access). Entries are only checked and removed when something
gets them (as above). Pros: simple, no background thread, zero overhead when idle. Cons: expired entries that are never accessed again linger forever, consuming memory - a cache with many one-time keys leaks. Lazy alone is fine when keys are usually re-accessed or the keyspace is bounded. - Active expiration (background sweeper). A background thread periodically scans the map and removes expired entries (or uses a priority structure to find them efficiently). Pros: reclaims memory promptly regardless of access patterns. Cons: the sweeper consumes CPU and contends with readers/writers; scanning the whole map periodically is O(n). To make it efficient, use a
DelayQueueor a priority queue ordered by expiry time so the sweeper can pop only the entries that have actually expired (O(log n) per expiry) rather than scanning everything.
The standard production answer is both: lazy expiration on get (so reads never return expired data) plus a background sweeper (so memory is reclaimed even for untouched keys). The lazy check guarantees correctness; the sweeper guarantees memory hygiene. A ScheduledExecutorService running a sweep every few seconds, or a dedicated thread draining a DelayQueue of (expiryTime, key) entries, is the typical implementation.
Important: A thread-safe TTL cache is a
ConcurrentHashMap<K, Entry>whereEntryholds the value and an absolute expiry time (now() + ttl, not the duration).getchecksexpiryTime <= now()and, if expired, uses an atomic conditional remove (map.remove(key, entry)- remove only if still mapped to this entry) to avoid the check-then-act race where a concurrentputof a fresh value would otherwise be clobbered. Expiration strategy is the core trade-off: lazy (check onget; simple but untouched expired entries leak memory) vs active (a background sweeper, ideally over aDelayQueue/priority queue by expiry so it pops only expired entries in O(log n)). The production answer is both - lazy for read correctness, a sweeper for memory hygiene. Extensions: a size cap with LRU eviction (combine with a concurrent linked structure or use a library like Caffeine), and sliding-TTL refresh-on-access. The concurrent map plus atomic conditional remove is the core.
Trade-offs and extensions
Beyond expiration, several design dimensions distinguish a thorough answer. Eviction by size: if the cache must be bounded, add a maximum size and an eviction policy - LRU is standard, but maintaining LRU order concurrently is itself hard (the recency list is a contended structure). Production caches use clever approximations (Caffeine uses a sampled/sketch-based policy, LinkedHashMap with a lock for simpler cases). It's worth noting that combining TTL with LRU is exactly what real caches (Caffeine, Guava) do, and that you'd typically reach for such a library in practice rather than hand-roll it. Granularity of locking: ConcurrentHashMap gives you fine-grained concurrency for free (it locks per-bin/segment internally), which is why it's preferred over a single synchronized map - reads are essentially lock-free and writes contend only on the same bin. Atomic compute methods: ConcurrentHashMap's compute, computeIfAbsent, and merge let you do atomic read-modify-write on a single key, useful for refresh-on-access or atomic insert-if-absent without a separate lock. The overarching design lesson: lean on the concurrent map's atomic primitives for per-key atomicity, choose lazy+active expiration for correctness+hygiene, and recognize that size-bounded eviction is the genuinely hard extension where a library is often the right call.
A worked scenario: the expiry race
Walking through the check-then-act race makes the conditional remove's necessity concrete. Suppose key "session:42" has an entry that just expired, and two threads act concurrently:
Initial: map["session:42"] -> Entry(oldValue, expiry=T) where T <= now() (expired)
Thread A (a get): Thread B (a put):
entryA = map.get(key)
-> Entry(oldValue, T)
see expiryTime <= now()
(decide to remove)
map.put(key, Entry(newValue, now()+ttl))
-> map["session:42"] now maps to Entry(newValue, ...) (FRESH)
-- with UNCONDITIONAL remove: --
map.remove(key)
-> deletes Entry(newValue)! *** newValue LOST ***
-- with CONDITIONAL remove: --
map.remove(key, entryA) # entryA = Entry(oldValue, T)
-> key now maps to Entry(newValue), NOT entryA -> no-op -> newValue PRESERVED
Thread A reads the expired entry and decides to evict it. Before A removes, Thread B writes a fresh value for the same key. With an unconditional map.remove(key), A deletes B's fresh value - silent data loss, and the next reader gets a spurious miss. With the conditional map.remove(key, entryA), A's remove fires only if the key still maps to the exact expired entry A observed; since B replaced it, the remove is a no-op and the fresh value survives. This is the check-then-act race (Module 6) in miniature, and the concurrent map's conditional (CAS-backed) remove is precisely the atomic compound operation that closes it. The same reasoning applies to refresh-on-access: use compute/merge so the read-decide-write is atomic per key.
Connection to real cache systems
This design isn't academic - it's the skeleton of every production cache. Caffeine (the de facto Java caching library) is a ConcurrentHashMap at its core, with absolute expiry times per entry, both lazy expiration (checked on access) and active maintenance (an amortized cleanup that runs during normal operations rather than a dedicated thread), and a sophisticated size-eviction policy (a frequency sketch called TinyLFU rather than strict LRU, because exact LRU's recency list is too contended). Guava's cache is similar. Redis (used as a distributed cache) stores absolute expiry times and uses both lazy expiration (on access) and active expiration (a background cycle that samples random keys with expiry set and evicts the expired ones - a probabilistic sweep that avoids scanning the whole keyspace). The lazy+active combination you'd propose in an interview is exactly what these systems do, which is a strong point to make: "lazy for read correctness, active for memory hygiene - the same approach Redis and Caffeine take." The one place to show humility is size-bounded eviction: real systems use approximations (sampled LRU, TinyLFU, sampled random eviction) precisely because maintaining exact recency order under concurrency is prohibitively contended - so the honest answer is "for production I'd use Caffeine rather than hand-roll the eviction policy," which signals you know where the genuine difficulty lies. Understanding the TTL cache from primitives means you understand what these libraries do under the hood and can reason about their behavior, rather than treating them as black boxes.
Note: The TTL cache and the rate limiter share a deep structural similarity worth internalizing, because the pattern recurs across this whole module: both store per-key state in a concurrent map, both defer work via lazy computation from a stored timestamp (the cache lazily checks expiry; the limiter lazily refills tokens - neither needs a background thread for its core correctness), and both must make compound operations on a single key atomic (the cache's check-expiry-then-remove via conditional remove; the limiter's refill-check-decrement via per-client lock). This trio - concurrent map for structure, lazy timestamp-based computation for efficiency, per-key atomicity for correctness - is the backbone of an enormous class of thread-safe components. When you encounter a new "design a thread-safe X" problem, reach for this template first: what is the per-key state, can the work be done lazily from a timestamp instead of by a background thread, and which compound operations on a single key must be atomic? Answering those three questions usually gets you most of the way to a correct, scalable design. The background-thread option (the cache's sweeper) is then a supplementary concern - added for memory hygiene or promptness, not core correctness - which is exactly the right way to think about active background work: it augments a lazily-correct core rather than being load-bearing for correctness itself.
The interview angle
Interview: "Design a thread-safe cache with TTL" is an extremely common concurrency design question. The expected core: a
ConcurrentHashMap<K, Entry>withEntryholding the value and an absolute expiry time, lazy expiration onget, and an atomic conditional remove to avoid the check-then-act race. Distinguishing points: (1) storing absolute expiry (not duration) and why; (2) catching the check-then-act race on expiry and fixing it with the conditional remove (remove(key, entry)) - this is the concurrency insight interviewers probe; (3) discussing lazy vs active expiration and recommending both (lazy for correctness, aDelayQueue-backed sweeper for memory); (4) whyConcurrentHashMapover asynchronizedmap (fine-grained locking, concurrent reads); (5) the LRU + size-bound extension and that it's the hard part (mention Caffeine/Guava). Follow-ups often push on the sweeper's efficiency (priority queue by expiry) and on combining eviction policies. Catching the expiry race and discussing the lazy/active trade-off are the standout signals.
Quick reference
THREAD-SAFE TTL CACHE: get/put with entries expiring after a time-to-live, thread-safe,
read-concurrent
CORE DESIGN:
map = ConcurrentHashMap<K, Entry>
Entry = { value, expiryTime } # ABSOLUTE time = now()+ttl (not duration)
put(k,v,ttl): map.put(k, Entry(v, now()+ttl))
get(k): e = map.get(k);
if e==null: return null
if e.expiryTime <= now(): map.remove(k, e); return null # ATOMIC conditional remove
return e.value
KEY CONCURRENCY POINTS:
- CHECK-THEN-ACT RACE on expiry: naive "check expired -> remove" can clobber a concurrent
fresh put -> use map.remove(key, entry) (removes only if still THIS entry / CAS)
- ConcurrentHashMap > synchronized map: fine-grained (per-bin) locking, concurrent reads
- atomic compute/computeIfAbsent/merge for per-key read-modify-write
EXPIRATION STRATEGY (the core trade-off):
LAZY (on get): simple, no thread; but untouched expired entries LEAK memory
ACTIVE (sweeper): background thread reclaims memory; use DelayQueue/PQ by expiry
so it pops only expired entries (O(log n)) vs scanning all (O(n))
PRODUCTION: BOTH - lazy for read correctness + sweeper for memory hygiene
EXTENSIONS: size cap + LRU eviction (hard to do concurrently -> Caffeine/Guava);
sliding TTL (refresh-on-access via compute)
The TTL cache introduced lazy-vs-active background work and atomic conditional updates. The next problem - the rate limiter - reuses the lazy-computation idea (lazily refilling tokens based on elapsed time) and adds per-client state and atomic check-and-decrement.