Cache Eviction Policies

1The core idea#

A cache keeps a subset of your data in fast memory, and that subset is tiny on purpose.

• RAM is expensive and finite. Your dataset is not.
• At any moment the cache holds maybe 1% of the keys that exist.
• When a new item needs a slot and there is no room, something has to leave.
• The rule that picks the victim is the eviction policy.

The mental model I use: a cache is a bet.

• Every key you keep is a bet that someone asks for it again soon.
• Eviction is folding the bets least likely to pay off.
• A good policy is one whose guesses line up with your real traffic. That is the entire game.

Two numbers drive every decision here.

• Hit rate. The fraction of reads served from cache. Going from 90% to 95% cuts database load roughly in half, because you just halved the misses.
• Cost per eviction decision. The policy runs on every access or insert. If it is slow or needs a lock, it becomes the bottleneck it was meant to prevent.

Why half a percent of hit rate is worth a sprint. Put real numbers on it. You serve 100,000 reads/second, each miss is a 5 ms database read, and the database sustains 20,000 reads/second before latency spikes.

• 90% hit rate: 10,000 misses/second. Half capacity. Fine.
• 80% hit rate: 20,000 misses/second. Pinned at the ceiling, and the next bump takes you down.
• 95% hit rate: 5,000 misses/second. You just bought 4x headroom.

2How it works#

Walk the common policies, cheapest to smartest.

• FIFO (first in, first out). Evict whatever you inserted earliest, ignoring usage. A plain queue. Dead simple, but a hot item that happens to be old gets tossed. Rarely the right default.
• LRU (least recently used). Evict the item untouched the longest. The workhorse. The bet is "recently used means likely to be used again," which holds for a huge amount of real traffic.
• LFU (least frequently used). Evict the item accessed the fewest times. The bet shifts from "recent" to "popular." Great when some keys stay genuinely hot and you do not want a burst of one-off reads to push them out.
• TTL (time to live). Not a replacement, a companion. Each entry gets an expiry, then it is stale and removed (lazily on access or by a background sweep). TTL is about freshness, not capacity. You almost always run it alongside LRU or LFU.
• Random. Evict a random entry. Weaker than LRU on most workloads, but it needs zero bookkeeping and no locks, so it scales beautifully. Memcached's slab design leans on this reasoning.

The classic LRU implementation is worth knowing cold.

• A hash map plus a doubly linked list.
• The map gives O(1) lookup.
• The list keeps items in recency order.
• On every access, move the touched node to the front. Evict from the back.

Here is the read path, showing where eviction fits.

And the shape of the system the cache sits inside.

3A worked example: four keys, two slots#

The fastest way to feel the difference between policies is to run the same tiny trace through each. The cache holds exactly 2 entries. The access sequence is:

A  B  A  C  A  B

LRU. Order runs least recent to most recent.

• Result: 2 hits out of 6.
• B gets evicted at step 4 and we pay for it when B returns at step 6.

LFU. Order runs by access count. Ties broken by recency.

• Result: also 2 hits on this trace.
• The behavior differs though: A is pinned the whole time because its count keeps climbing.

Why run the trace by hand in the room.

• It shows you understand the policy is a prediction about the future built from the past.
• Different pasts favor different policies.
• Do this on a whiteboard in 60 seconds and you are already past most candidates.

4Trade-offs#

Every policy trades three things against each other: hit quality, bookkeeping cost, and resistance to bad traffic.

The big one people miss: LRU gets wrecked by scans.

• A report job reads a million rows once, in order.
• Each read is a miss, each miss inserts, and every insert counts as most-recently-used.
• The scan shoves out all your genuinely hot keys.
• Hit rate craters for minutes until the hot set reloads.
• LFU does not have this problem: one-off reads never build frequency, so they get evicted first. That single scenario is the cleanest reason to reach for LFU or a hybrid.

Put the scan in numbers.

• Normal traffic sits at a 94% hit rate.
• A nightly job scans 500,000 rows into a cache holding 200,000 entries.
• Under LRU the scan overwrites the entire hot set two and a half times over.
• Right after the job, hit rate falls to near 0% and climbs back over the next few minutes.
• At 5 ms per extra miss and 50,000 reads/second during recovery, that is a multi-minute database spike you did not plan for, every single night.

But LFU has its own trap: stale popularity.

• A key hammered last Tuesday has a sky-high count.
• It has not been touched since, yet its count keeps it pinned while fresher items get evicted.
• The fix is aging or decay: periodically halve all counts, or use a windowed count, so old popularity fades.
• Plain LFU with no decay is usually a mistake.

This is why modern caches ship hybrids.

• LRU-K tracks the last K access times, not just the last one, so a single touch does not instantly promote a scan item.
• TinyLFU (used by Caffeine and parts of Redis thinking) keeps a tiny approximate frequency sketch and admits a new item only if it looks more popular than the one it would evict. LFU-like hit rates at LRU-like cost.

Here is the full comparison.

5Where it is used#

Real systems make this concrete, and naming them shows you have operated caches, not just read about them.

• Redis picks per instance: allkeys-lru, allkeys-lfu, volatile-ttl, noeviction, and more. The volatile-* variants evict only keys that have a TTL set, a neat way to protect keys you marked permanent. Redis LRU and LFU are both approximate, sampled from a handful of random keys, because perfect ordering across millions of keys is not worth the cost.
• Memcached uses a segmented LRU inside fixed-size slab classes. It leans on simplicity and raw throughput over a perfect hit rate.
• CPU and OS page caches use LRU approximations (clock, second-chance) because true LRU needs a timestamp update on every access, too expensive at that layer.
• CDNs lean on LRU and TTL together: a video segment expires by TTL for freshness, and cold segments fall out by LRU to make room for whatever is trending.

When the policy actually matters.

• You need an explicit policy when the cache is memory-bound (it fills up) and traffic is skewed or scan-prone.
• If the working set fits comfortably, eviction barely runs and the policy hardly matters.
• Saying "if the working set fits, I would not over-engineer the policy" is a valid and mature thing to say in an interview.

6Common pitfalls and gotchas#

• Treating TTL as an eviction policy. TTL controls freshness, not capacity. A cache full of unexpired keys still needs a capacity policy. You need both.
• Forgetting the thundering herd on expiry. 10,000 keys sharing one TTL expire in the same second and stampede the database with misses. Add jitter: randomize each TTL by plus or minus 10% so expirations spread out.
• Assuming LRU is scan-proof. It is the opposite. Batch jobs and full-table reads will flush your hot set. Know this before the interviewer points it out.
• Perfect LRU at scale. A globally accurate linked list means every read mutates shared state and needs a lock, and under heavy concurrency that lock becomes the bottleneck. Sampled policies exist precisely to avoid this.
• LFU with no decay. Yesterday's hot key hogs memory forever. Always age the counts.
• Ignoring item size. Most policies assume uniform cost. A 2 MB value and a 200 byte value are not the same bet, so evicting by count alone is crude. Size-aware or cost-aware eviction matters for CDN and object caches.
• No noeviction plan. Set Redis to noeviction and when it fills, writes start failing. Sometimes that is what you want (a cache you treat as a source of truth), but know you chose it.

7How it shows up in interviews#

Interviewers rarely ask "define LRU." They set up a scenario and watch whether your policy survives it.

Probe one: "Your hit rate drops from 94% to 60% every night at 2am. Why?"

• Weak answer: "Maybe the cache restarted or ran out of memory. I would check the logs and add RAM." This guesses at symptoms, treats the time pattern as a coincidence, and reaches for hardware. It tells me you do not know how LRU interacts with scans.
• Strong answer: "The 2am timing points to a scheduled job. A nightly batch reads a large one-time set, and under LRU every read inserts as most-recently-used and evicts my hot set. Hit rate recovers over a few minutes as live traffic reloads. Fix it by not caching scan reads at all (bypass the cache for the reporting path), or move to an admission policy like TinyLFU so one-off reads never get admitted over popular keys, or LRU-K so a single touch does not promote them." Same facts, but it names the mechanism, ties it to the time signal, and gives three ranked fixes.

Probe two: "A few very popular products, a long tail. Which policy?"

• Weak answer: "LRU, it is the standard." No read of the traffic shape, no mention of the hot set, no cost awareness.
• Strong answer: "The hot set is small and stable, so I want frequency, not just recency. LFU or TinyLFU pins the popular products and lets the long tail churn. I would add count decay so a one-day flash sale does not pin a product forever, and I would be honest that LFU costs me per-key counters and a min-frequency structure. If the popular set is tiny enough to fit outright, I would just pin it and skip the clever policy." It picks, defends the pick against the traffic, and prices the cost.

What separates a staff-level answer.

• You tie the policy to the access pattern, not to what is fashionable. "Recency-biased traffic, so LRU. Scan risk from the reporting job, so I would isolate those reads or move to TinyLFU."
• You bring up hit rate as the real metric and reason about what a few points mean for database load: a drop from 95% to 90% doubles your misses.
• You mention approximation on purpose. "I would use sampled LRU like Redis does, exact ordering is not worth the lock contention" signals operational experience.
• You pair TTL with a capacity policy without being reminded, and you add jitter to avoid synchronized expiry.
• You admit the boring truth when it fits: if the working set fits in memory, the policy choice is close to irrelevant and you would not spend budget on it.

The job is not naming the policy. It is picking one for the traffic in front of you, and defending the pick.

For a full worked example, see the related System Design Question walkthrough on designing a read-heavy product cache, where eviction policy, TTL jitter, and hit-rate targets all come together.