Real-World ScenariosTopic 3 of 18

ProblemMediumAsked Often

In-Memory Cache with TTL Invalidation

In one line

Thread-safe cache where each entry expires after T seconds. Core decisions: lazy expiry vs background sweep; ConcurrentHashMap vs RWLock; cache-stampede prevention via single-flight. Tests understanding of expiration semantics + concurrency together.

The problem

Build an in-memory cache where:

get(key) returns the cached value if not expired; else loads and caches it.
Each entry expires after T seconds.
Thread-safe with high concurrency.
Resilient to cache stampede (many concurrent misses for the same key shouldn't all hit the upstream).

Note

What this tests in interviews Three concurrent-thinking decisions: storage primitive (CHM vs RWLock), expiry strategy (lazy vs active), stampede prevention (single-flight). Each has tradeoffs; senior candidates name them, junior candidates pick one and miss the others.

The decision matrix

Tip

Three knobs to discuss

Storage: ConcurrentHashMap if Java; sync.Map for write-once-read-many in Go; sharded dict + RLock in Python.
Expiry: lazy (check on read) for correctness; active (background sweep) for memory.
Stampede: single-flight library, or per-key lock + double-checked init.

What real production caches do

Caffeine (Java): window TinyLFU eviction, optional TTL, computeIfAbsent for stampede.
Guava Cache (Java): same shape, older.
Ristretto (Go): TinyLFU + sampling for cost-aware eviction.
functools.lru_cache (Python): no TTL out of the box; cachetools.TTLCache adds it.

Warning

What junior solutions miss "I'll use a HashMap with synchronized methods." Works for low concurrency but kills throughput at scale. Use the concurrent collection. And forgetting stampede protection, under load, a single hot key expiring can DDOS the database.

The 30-second extension

Important

If asked "how would this be made distributed?" Same questions, harder answers: storage = Redis cluster; expiry = TTL via Redis EXPIRE; stampede = locks via Redis SETNX. Single-flight at the application layer becomes "is anyone else computing this key?", usually a per-key Redis lock with timeout.

Implementations

ConcurrentHashMap + computeIfAbsent (single-flight)

computeIfAbsent atomically: looks up key, if missing computes the value, installs it. Other concurrent calls for the same key block on the lock for that bin, only one computation per key. Lazy expiry: on read, check the entry's deadline; if expired, recompute.

 1  import java.util.concurrent.ConcurrentHashMap;
 2  import java.util.function.Function;
 3  
 4  class TtlCache<K, V> {
 5      private record Entry<V>(V value, long expiresAt) {}
 6      private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
 7      private final long ttlMs;
 8      private final Function<K, V> loader;
 9  
10      public TtlCache(long ttlMs, Function<K, V> loader) {
11          this.ttlMs = ttlMs;
12          this.loader = loader;
13      }
14  
15      public V get(K key) {
16          long now = System.currentTimeMillis();
17          Entry<V> entry = map.compute(key, (k, e) -> {
18              if (e != null && e.expiresAt > now) return e;
19              return new Entry<>(loader.apply(k), now + ttlMs);
20          });
21          return entry.value;
22      }
23  }

Background sweeper (active expiry)

A scheduled task scans entries periodically and removes expired ones. Bounds memory growth even if rarely-read keys would otherwise sit forever. Pair with lazy expiry for best results.

 1  class TtlCacheWithSweep<K, V> {
 2      private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
 3      // ... loader, ttlMs ...
 4  
 5      public TtlCacheWithSweep() {
 6          ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(r -> {
 7              Thread t = new Thread(r, "ttl-sweeper");
 8              t.setDaemon(true);
 9              return t;
10          });
11          scheduler.scheduleAtFixedRate(this::sweep, 1, 1, TimeUnit.SECONDS);
12      }
13  
14      private void sweep() {
15          long now = System.currentTimeMillis();
16          map.entrySet().removeIf(e -> e.getValue().expiresAt() <= now);
17      }
18  }

Key points

•Two expiry strategies: lazy (check on read) vs active sweep (background timer)
•ConcurrentHashMap (Java) / sync.Map (Go) / dict + RLock (Python) for storage
•Cache stampede: when key expires, many concurrent reads all try to recompute → use single-flight
•Hot-key contention: shard the cache by key hash for high throughput

Follow-up questions

▸Lazy vs active sweep, pick one?

Use both. Lazy expiry on reads gives correctness. Active sweep bounds memory for keys rarely read. Without active sweep, keys never read again sit forever, memory leak. Without lazy, stale data is served between sweep cycles.

▸What's cache stampede and how is it prevented?

When a hot key expires and 100 concurrent reads all see 'expired' and all try to recompute simultaneously, hammering the upstream. Single-flight: only one recomputation per key; others wait for it. Java's `computeIfAbsent`, Go's `singleflight`, hand-rolled per-key locks in Python.

▸How would this scale to 1M ops/sec?

Sharding. Split the cache into N partitions by key hash; each has its own lock and map. ConcurrentHashMap (Java) does this internally with ~16 bins; for Go/Python, do it explicitly. Separate single-flight group per shard.

▸What about negative caching?

Cache 'not found' with a shorter TTL. Otherwise every miss for a non-existent key hammers the loader. Production caches usually have separate hit/miss TTLs.

In-Memory Cache with TTL Invalidation

In one line

The problem

Build an in-memory cache where:

get(key) returns the cached value if not expired; else loads and caches it.
Each entry expires after T seconds.
Thread-safe with high concurrency.
Resilient to cache stampede (many concurrent misses for the same key shouldn't all hit the upstream).

Note

The decision matrix

Tip

Three knobs to discuss

Storage: ConcurrentHashMap if Java; sync.Map for write-once-read-many in Go; sharded dict + RLock in Python.
Expiry: lazy (check on read) for correctness; active (background sweep) for memory.
Stampede: single-flight library, or per-key lock + double-checked init.

What real production caches do

Caffeine (Java): window TinyLFU eviction, optional TTL, computeIfAbsent for stampede.
Guava Cache (Java): same shape, older.
Ristretto (Go): TinyLFU + sampling for cost-aware eviction.
functools.lru_cache (Python): no TTL out of the box; cachetools.TTLCache adds it.

Warning

The 30-second extension

Important

Implementations

ConcurrentHashMap + computeIfAbsent (single-flight)

 1  import java.util.concurrent.ConcurrentHashMap;
 2  import java.util.function.Function;
 3  
 4  class TtlCache<K, V> {
 5      private record Entry<V>(V value, long expiresAt) {}
 6      private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
 7      private final long ttlMs;
 8      private final Function<K, V> loader;
 9  
10      public TtlCache(long ttlMs, Function<K, V> loader) {
11          this.ttlMs = ttlMs;
12          this.loader = loader;
13      }
14  
15      public V get(K key) {
16          long now = System.currentTimeMillis();
17          Entry<V> entry = map.compute(key, (k, e) -> {
18              if (e != null && e.expiresAt > now) return e;
19              return new Entry<>(loader.apply(k), now + ttlMs);
20          });
21          return entry.value;
22      }
23  }

Background sweeper (active expiry)

A scheduled task scans entries periodically and removes expired ones. Bounds memory growth even if rarely-read keys would otherwise sit forever. Pair with lazy expiry for best results.

 1  class TtlCacheWithSweep<K, V> {
 2      private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();
 3      // ... loader, ttlMs ...
 4  
 5      public TtlCacheWithSweep() {
 6          ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(r -> {
 7              Thread t = new Thread(r, "ttl-sweeper");
 8              t.setDaemon(true);
 9              return t;
10          });
11          scheduler.scheduleAtFixedRate(this::sweep, 1, 1, TimeUnit.SECONDS);
12      }
13  
14      private void sweep() {
15          long now = System.currentTimeMillis();
16          map.entrySet().removeIf(e -> e.getValue().expiresAt() <= now);
17      }
18  }

Key points

•Two expiry strategies: lazy (check on read) vs active sweep (background timer)
•ConcurrentHashMap (Java) / sync.Map (Go) / dict + RLock (Python) for storage
•Cache stampede: when key expires, many concurrent reads all try to recompute → use single-flight
•Hot-key contention: shard the cache by key hash for high throughput

Follow-up questions

▸Lazy vs active sweep, pick one?

▸What's cache stampede and how is it prevented?

▸How would this scale to 1M ops/sec?

▸What about negative caching?

Cache 'not found' with a shorter TTL. Otherwise every miss for a non-existent key hammers the loader. Production caches usually have separate hit/miss TTLs.

In-Memory Cache with TTL Invalidation

The problem

The decision matrix

What real production caches do

The 30-second extension

Implementations

Key points

Follow-up questions

Related reading

In-Memory Cache with TTL Invalidation

The problem

The decision matrix

What real production caches do

The 30-second extension

Implementations

Key points

Follow-up questions

Related reading