LRU / LFU Cache

The big picture#

Everything below expands on these points. Read the core sections top to bottom for the full mental model; the collapsible "Go deeper" box holds the advanced eviction policies (ARC, LIRS, W-TinyLFU) you can skip on a first pass and return to later.

Capacity = 4, the cache is FULL, and a new key X arrives — someone must be evicted. Recent accesses, oldest → newest: C A B D A. The hash map and value storage are identical for both policies; the only thing that differs is the question each one asks.

Start here: the victim-selection problem#

A cache trades memory for speed: keep hot data close by so you don't re-fetch it from a slower source (disk, a database, a network call). Memory is finite, so once the cache is full, every insert needs a victim. The eviction policy is the rule that picks the victim — and a bad rule means cache misses on data you just evicted, which is strictly worse than a smarter rule using the same memory.

There is a known optimal answer, and it is useless in practice. Bélády's algorithm (MIN, or OPT) evicts the entry whose next use is furthest in the future, and provably yields the fewest misses of any policy. The catch: it requires knowing the future. Every real policy is a heuristic that predicts the future from the past — and the two simplest predictions are 'what I used recently I'll use again' (recency → LRU) and 'what I use often I'll keep using' (frequency → LFU).

The reason these heuristics work at all is locality of reference: real access streams are not uniform random. They cluster in time (a key touched now is likely touched again soon — temporal locality) and they are skewed (a small fraction of keys take a large fraction of the accesses — a Zipfian or power-law distribution). A cache only beats random eviction because the workload has structure; the policy is a guess about which kind of structure dominates.

LRU: evict whoever you haven't touched in the longest time#

LRU (Least Recently Used) bets that data accessed recently is likely to be accessed again soon — true for most real workloads, because of temporal locality. The implementation is a doubly-linked list plus a hash map from key to its node: the map gives O(1) lookup, the linked list gives O(1) reordering. The list is kept in recency order — most-recently-used at the head, least-recently-used at the tail — and the tail is always the next victim.

1. GET key: look it up in the map. Miss → done. Hit → unlink its node and relink it at the head (most-recently-used end), then return the value.
2. PUT key=value, key exists: update the node's value, then move it to the head exactly like a GET hit.
3. PUT key=value, key is new and the list is below capacity: create a node, link it at the head, add it to the map.
4. PUT key=value, key is new and the list is at capacity: unlink the tail node (the least-recently-used entry), remove it from the map, then insert the new node at the head and the map.

LFU: evict whoever's been touched the fewest times#

LFU (Least Frequently Used) bets on a different signal: total access count, not recency. A key accessed 100 times an hour ago is, by this policy, more valuable than one accessed once a second ago — the opposite call LRU would make. The naive way to find the least-frequent key is to scan all entries for the minimum count, which is O(n). The O(1) construction (Pai et al.'s design) avoids the scan with three structures: a key→value map, a key→frequency map, and a map from frequency→an ordered list of keys at that frequency, plus a single minFreq pointer that always names the lowest occupied bucket.

1. GET key (hit) or PUT on an existing key: look up its current frequency f, remove it from bucket[f], push it to the front of bucket[f+1], and record its new frequency as f+1.
2. If bucket[f] is now empty and f was minFreq, bump minFreq to f+1 — the old floor frequency no longer has any keys.
3. PUT a new key when below capacity: insert it at the front of bucket[1], and reset minFreq to 1 — a fresh key is always the new floor.
4. PUT a new key at capacity: evict the back (least-recently-used, as a tie-break) entry of bucket[minFreq], remove it from all maps, then insert the new key as above.

Cost: time, and the memory tax of pointers#

Both policies hit the design goal: every operation is O(1) on average. The 'on average' is the hash map's amortized cost (constant expected, with rare rehashes); the list and bucket manipulations are worst-case O(1) because they only ever touch a fixed number of pointers. That is the whole point — the per-request cost does not grow as the cache fills, so the cache stays fast at ten entries or ten million.

The cost that's easy to forget is memory. A doubly-linked list node carries two pointers — 16 bytes on a 64-bit machine — on top of the key, the value, and the hash-map entry that points at the node. For small values (think a cache of 8-byte integers keyed by 8-byte integers) the bookkeeping can dwarf the data it's tracking. LFU is heavier still: every entry also needs a frequency counter and membership in a per-frequency list, and the frequency→bucket map is extra structure on top. This memory tax is precisely why production systems often choose approximate policies (next section): a few sampled keys or a single reference bit per entry buys most of LRU's hit rate at a fraction of the per-entry overhead.

Beyond the textbook two: cheaper and smarter policies#

LRU and LFU are the policies you implement in an interview, but they are rarely what runs in production unmodified. Real systems either approximate LRU to cut its overhead, or hybridize recency and frequency to beat both. The lightweight options:

• FIFO (first-in-first-out) — evict the oldest inserted entry, ignoring use entirely. A plain queue, no reordering on access, almost zero metadata. Cheap but blind: it throws out hot data just because it has been resident a while, and it can even exhibit Bélády's anomaly (more cache → more misses).
• Random — evict a uniformly random entry. No ordering metadata at all. Surprisingly competitive on skewed workloads and trivially concurrent (no list to lock), which is why it shows up as allkeys-random in Redis and inside some CPU caches.
• CLOCK / Second-Chance — an approximate LRU. Entries sit in a circular buffer, each with a one-bit reference flag set on access. A 'hand' sweeps the circle; if it lands on an entry with the bit set, it clears the bit and moves on (a second chance), otherwise it evicts. One bit per entry instead of two pointers, no per-access list surgery — the classic OS page-replacement policy.
• Segmented LRU (SLRU) — split the cache into a probationary segment and a protected segment. New entries enter probation; a second hit promotes them to protected. A one-time scan only ever pollutes probation, so the protected working set survives. Memcached's modern LRU is a segmented HOT/WARM/COLD variant of this idea.

The recency bet vs the frequency bet#

LRU and LFU are two answers to the same question — 'which past signal best predicts the future?' — and each is right exactly when its assumption holds. LRU assumes recency dominates: the thing you touched most recently is the thing you'll touch next. That holds for working-set workloads with strong temporal locality (a user's current session, the pages of the file you're scrolling). LFU assumes popularity dominates: a small set of items is durably hot and the rest is noise. That holds for skewed, long-lived distributions (the top trending videos, a handful of celebrity profiles, hot product pages).

The sharpest practical axis between them is scan resistance. A scan — reading a large set of items exactly once — is the adversary that separates the policies. LRU has zero scan resistance: every scanned item looks maximally recent, so the scan marches your real working set out the tail. LFU resists scans naturally, because scanned items only ever reach frequency 1 and are evicted before they can displace genuinely hot keys. This single property is why almost every 'serious' policy (2Q, ARC, LIRS, segmented LRU, W-TinyLFU) blends in a frequency or second-chance signal: pure recency is too easily fooled.

How each one fails in production#

Knowing the textbook policy is half the job; knowing how it breaks is what an interviewer (and a 3 a.m. page) actually cares about.

• LRU cache pollution from a bulk scan — a backup job, an analytics query, or a crawler reads every row once. Each read looks 'most recent,' so LRU promotes all of it and evicts the genuinely hot working set. The moment the scan ends, your hit rate craters because the data people actually want has been flushed. This is the single most common LRU outage and the reason scan resistance matters.
• LFU stale-hot keys (no aging) — a product that went viral last month keeps a sky-high count and refuses to leave, squatting on capacity long after traffic moved on. New genuinely-hot keys can't accumulate enough count to displace it. The fix is frequency decay; the bug is shipping textbook LFU without it.
• LFU new-key starvation — a brand-new key enters at frequency 1, the lowest possible, so it's first in line for eviction. In a busy cache it can be evicted before it ever gets a second hit, meaning a rising-but-not-yet-popular item never gets a fair chance. (W-TinyLFU's admission window exists specifically to give newcomers a probation period.)
• Cold start — right after a restart or deploy the cache is empty, so every request misses and stampedes the backing store. Neither policy helps here; this is about cache warming and request coalescing, not eviction, but it's the failure people most often blame on 'the cache.'

Policies side by side#

Read the table as a progression: the top rows are cheap and dumb, the bottom rows are heavier and smarter. ARC and W-TinyLFU win because they carry both signals at once and adapt the balance; the price is more moving parts. For an interview, being able to place LRU and LFU on this spectrum — and name what the smarter policies add (adaptivity, aging, scan resistance) — is worth more than a flawless re-derivation of either.

Where these policies actually run#

Eviction policy is one of those primitives you've been relying on for years without naming. A tour of where the choices land:

• Redis — exposes the policy as the maxmemory-policy config: noeviction, allkeys-lru, allkeys-lfu, allkeys-random, and the volatile-* variants (lru / lfu / random / ttl) that only evict keys with a TTL set. Crucially, Redis's LRU and LFU are both approximate — it samples a handful of keys (default 5) and evicts the best of the sample rather than maintaining a true global order, trading a little accuracy for a lot of memory. Its LFU uses an 8-bit Morris counter (probabilistic increment) plus a configurable decay period so counts age.
• Memcached — historically a straightforward LRU; since 1.5 it runs a segmented LRU with HOT, WARM, and COLD sub-LRUs and a background crawler, specifically to get scan resistance and reclaim expired items without walking the whole cache.
• Caffeine (Java) — the reference W-TinyLFU implementation, and the default caching library across much of the JVM ecosystem (Spring, Cassandra's key cache, and more). It is the practical proof that an adaptive frequency sketch beats LRU/LFU/ARC on real traces while staying highly concurrent.
• The OS page cache — Linux keeps two LRU lists (active and inactive), an approximation of segmented LRU / 2Q, to decide which file-backed pages to reclaim under memory pressure. Older and simpler kernels used CLOCK. The whole 'why is my RAM full of cache' phenomenon is this policy at work.
• CPU caches — set-associative L1/L2/L3 caches can't afford true LRU in hardware (too many bits, too much logic per line), so they use pseudo-LRU (a tiny tree of bits approximating LRU) or even random replacement within a set. The same recency intuition, squeezed into a few gates per cache line.

Common questions & gotchas#

In an interview#

Lead with the O(1) constraint — it's what forces the specific data structures. For LRU: hash map + doubly-linked list, full stop. For LFU: hash map for value, hash map for frequency, and a frequency→keys structure (each bucket an LRU list) with a minFreq pointer so you never have to scan for the minimum. If you can explain why minFreq only ever increments or resets to one, you've shown you understand why the whole thing is O(1).

Be ready to justify the choice with the workload, not in the abstract: LRU for general-purpose caching where recent access predicts future access (most HTTP/DB caches, session data); LFU when some keys are durably hotter than others regardless of when they were last touched (a small set of celebrity profiles, trending content). Then name the failure modes unprompted — LRU's scan pollution, LFU's stale-hot keys without aging — because naming the weakness is what separates 'memorized the data structure' from 'understands caching.'

If the conversation goes deeper, drop one real-world anchor: Redis approximates both with sampling; Memcached uses segmented LRU; ZFS uses ARC; Caffeine uses W-TinyLFU — adaptive policies that carry recency and frequency at once. You don't need to implement them, just to know they exist and what they fix. Then open the simulator: PUT past capacity and watch the eviction; for LFU, GET one key repeatedly so it's no longer the coldest, then PUT a new key and confirm a different key — not the one you favored — gets evicted.

References & further reading#