Concurrent Cache Design And Eviction

What's being tested

This topic tests whether you can design a bounded, low-latency data structure while preserving clear concurrency semantics, correct eviction behavior, and predictable failure modes. The interviewer is probing beyond “use a hash map plus LRU”: they want synchronization boundaries, complexity analysis, capacity accounting, and a plan for contention, expiration, invalidation, and cache misses. This matters for a Software Engineer because a cache often sits directly on a critical request path, where a race or lock convoy can become a broad availability or latency incident.

Core knowledge

• A basic LRU cache combines a hash map for key lookup with a doubly linked list for recency ordering: Get, Put, promotion, and eviction are all $O(1)$ time and $O(N)$ space. Updating recency makes reads mutating operations.

• Define linearizability before choosing locks: each Get, Put, delete, or eviction should appear to take effect at one instant. Decide whether stale reads are acceptable; strict recency and strict capacity usually require stronger synchronization than eventual cache metadata.

• A single mutex around the map and list is the simplest correct design, but all readers and writers serialize. It can be appropriate for modest traffic, while high-contention workloads usually need sharding or finer-grained synchronization.

• Lock striping partitions keys across $S$ shards, each with its own map, list, lock, and capacity. Operations remain expected $O(1)$, but global LRU becomes approximate unless cross-shard coordination is added; per-shard limits can waste capacity under skew.

• A concurrent read-write lock is not automatically better: LRU promotion means a Get writes metadata, so it often cannot use a shared read lock. Separate immutable values from recency bookkeeping only when the weaker consistency is explicitly acceptable.

• Capacity must have a precise unit: entries, bytes, weighted cost, or a mixture. For weighted entries, evict until $\text{current\_weight} \le \text{max\_weight}$, and handle an item whose weight alone exceeds the limit deterministically—usually reject or avoid caching it.

• TTL expiration and recency eviction solve different problems. Lazy expiration checks timestamps on access and avoids a timer per entry; proactive expiration requires a heap, timing wheel, or janitor thread and introduces shutdown, scan, and synchronization concerns.

• Avoid cache stampedes when many callers miss simultaneously. A per-key single-flight mechanism lets one caller load the value while others await the same result; bound loader time, propagate errors, and decide whether failures are cached.

• Eviction policy affects hit rate, not just implementation complexity. LRU favors temporal locality; LFU can preserve historically hot keys; TinyLFU-style admission resists one-time scans but requires frequency metadata and more complex aging.

• Distinguish cache state transitions: absent, loading, present, expired, invalidated, and failed. If deletion races with an in-flight load, use a generation/version token or invalidate-after-load rule so an old result cannot resurrect deleted data.

• Instrument behavior with hit_rate, miss rate, eviction count and reason, load latency, entry count, resident weight, lock-wait time, and p50/p99 operation latency. A high hit rate can still hide unacceptable tail latency caused by contention or serialization.

• State the consistency and failure contract explicitly: whether values may be stale, whether eviction is best effort, whether Get can invoke user code, and what happens when the cache is full, the loader fails, or the process restarts.

Worked example — Concurrent Cache Design And Eviction

Start by clarifying the API, maximum size, whether size means entries or bytes, whether values may be stale, required Get/Put latency, and whether exact global LRU is mandatory. I would assume a process-local cache with concurrent callers, bounded weighted capacity, optional TTL, and a best-effort eviction policy unless the interviewer specifies otherwise. I would organize the design around four pillars: the hash-map/list representation, synchronization and linearizability, eviction and expiration semantics, and stampede protection plus observability. The simplest baseline is one mutex protecting both the map and LRU list, giving expected $O(1)$ operations and an easy correctness argument. If contention is demonstrated, I would move to sharded caches, explicitly accepting approximate global recency or adding a more expensive global admission mechanism. I would ensure loaders execute outside the shard lock, while a per-key in-flight record prevents duplicate loads and a version check prevents stale results from repopulating an invalidated key. The key tradeoff is exact global LRU versus scalable concurrency: exact ordering requires coordination across shards, while approximate per-shard eviction is usually cheaper and more robust. If I had more time, I would specify benchmark workloads, lock-contention tests, eviction-race tests, memory accounting, and shutdown behavior for TTL workers.

A second angle — TTL, invalidation, and cache stampede

A cache for configuration or authorization data frames the problem differently from a pure hot-object cache: correctness may depend more on bounded staleness than on maximizing hit rate. The design should combine TTL with explicit invalidation, and it should define what happens during an upstream outage after an entry expires. Single-flight loading prevents a synchronized expiration from overwhelming the backing service, while jittered TTLs reduce synchronized refreshes across processes. The interviewer may also probe whether an invalidation racing with refresh can be lost; versioned entries or invalidate-after-load semantics provide a concrete answer.

Common pitfalls

Pitfall: Treating Get as read-only and protecting it with a shared read lock while it updates LRU metadata creates races or inconsistent list pointers. Either serialize promotion correctly or state that recency is approximate and use a separate safe mechanism.

Pitfall: Saying “use LRU” without defining capacity, expiration, and concurrent miss behavior leaves the important contract unspecified. A stronger answer names the state transitions, lock scope, oversized-entry policy, and whether duplicate loads are coalesced.

Pitfall: Overengineering immediately with lock-free lists, custom atomics, or exact global ranking obscures the correctness baseline. Start with a single-lock implementation, identify measured bottlenecks, then justify sharding or approximate policies with workload assumptions.

Connections

An interviewer may pivot to consistent hashing for a distributed cache, cache-aside versus write-through invalidation, or single-flight request coalescing. They may also connect eviction to memory allocators, backpressure, observability, and tail-latency debugging.

Further reading

• “The Adaptive Replacement Cache” — foundational work on balancing recency and frequency under changing workloads.

• “TinyLFU: A Highly Efficient Cache Admission Policy” — explains admission control that improves hit rate under scan-heavy traffic.

• Go sync/singleflight documentation — concrete reference for suppressing duplicate concurrent loads.