Cache Eviction Policies

A cache is almost always smaller than the data it could possibly hold — that's often why it's fast, since keeping everything in a small, high-speed memory tier is what makes lookups quick in the first place. Once it's full, adding a new entry means something else has to leave. An eviction policy is the rule that decides what to remove, and which rule you pick has a direct, measurable effect on hit rate.

LRU: Least Recently Used

Evict whichever entry hasn't been accessed for the longest time. The intuition is temporal locality — data accessed recently is disproportionately likely to be accessed again soon (a user who just viewed a product page is likely to view it again in the next few minutes), so keeping recently-touched entries and evicting stale ones is usually a good bet.

System Design Lab

LRU is implemented efficiently with a hash map (for O(1) lookup) paired with a doubly linked list (for O(1) reordering to the front on access and O(1) eviction from the back) — a detail worth knowing since "design an LRU cache" is itself a common interview question independent of the system design context.

LFU: Least Frequently Used

Evict whichever entry has been accessed the fewest total times, rather than the longest time since its last access. This handles a case LRU gets wrong: a genuinely popular item that happens to not have been touched in the last few minutes shouldn't necessarily lose to an item that was only ever accessed once, moments ago, just because that one access is more recent. The tradeoff is that LFU needs to track and maintain a count per entry (more bookkeeping than LRU's simpler recency ordering), and it can struggle to "forget" an item that was popular in the past but has since stopped being relevant, unless counts are explicitly decayed over time.

FIFO: First In, First Out

Evict whichever entry was added earliest, regardless of how often or recently it's been accessed. It's the simplest policy to implement — a plain queue — but ignores access patterns entirely, so it can evict a heavily-used entry just because it happened to be cached first. Rarely the right choice when access patterns are known to be uneven, but a reasonable, low-overhead default when they aren't, or when implementation simplicity matters more than hit rate.

Comparing the policies

Policy	Evicts	Overhead	Weak point
LRU	Least recently accessed	Low (hash map + linked list)	A briefly-idle-but-popular item can get evicted
LFU	Least frequently accessed	Higher (per-entry counters)	Old popularity can linger without decay
FIFO	Oldest inserted	Lowest (a queue)	Ignores access pattern entirely
TTL-based	Whatever expired	Low (a timestamp check)	Not access-aware at all — purely time-based

Most production caches (Redis included) default to LRU, or an approximation of it, precisely because it's cheap to maintain and its intuition — favor what's been touched recently — holds up well across most real workloads without needing per-entry counters.

The failure mode worth naming: cache stampede

Eviction policies decide what leaves the cache; they don't decide what happens when many clients simultaneously request something that just got evicted (or that's expiring via TTL). If a popular key expires and a flood of concurrent requests all miss at once, all of them can fall through to the database simultaneously — a cache stampede (also called a "thundering herd") that can overwhelm the very system the cache was protecting. The standard mitigations are worth naming together: having only the first miss actually query the source while other concurrent requests wait on that result ("request coalescing"), or staggering TTLs with a small random jitter so many entries don't expire at the exact same instant.

Why this matters in an interview

Naming LRU as the default and being ready to explain why it's the default (temporal locality, cheap to implement) is table stakes; a stronger answer goes further and names cache stampede as the specific failure mode that eviction and TTL policies create, and how the design mitigates it — that's the detail that distinguishes "I've used a cache" from "I understand what a cache does under load."

LRU vs. LFU eviction: pros and cons

LRU

• ✓Cheap to implement and maintain — O(1) access and eviction
• ✓Matches the common case well: recently used data tends to be used again
• ✓No per-entry counters or decay logic to tune

LFU

• ✕Needs a frequency counter maintained per entry, adding overhead
• ✕Requires an explicit decay mechanism, or old popularity lingers indefinitely
• ✕More complex to reason about and tune correctly than a simple recency list

Further Reading

• Redis Docs — Eviction policies — a concrete reference for how a widely used real cache implements and configures these policies.
• Wikipedia — Cache replacement policies — a broad survey covering LRU, LFU, FIFO, and several more advanced variants.