Side by side
| Dimension | LRU | LFU |
|---|---|---|
| Eviction signal | LRU: oldest last access | LFU: lowest access count or frequency estimate |
| Best workload fit | Recent working set predicts reuse | Repeatedly popular keys predict reuse |
| Popularity shifts | Old entries fall out as new ones arrive | Old winners can linger without aging |
| One-time scans | Can evict the useful working set | Can protect established high-frequency entries |
| Exact implementation | Hash map plus doubly linked list | Hash map plus frequency buckets and tie-breaking lists |
| Operation complexity | Expected O(1) lookup and update | Expected O(1) possible with frequency buckets |
| Metadata and coordination | Recency links; hits update shared ordering | Frequency state; hits update counters or buckets |
| Freshness guarantees | None; needs TTL or invalidation separately | None; needs TTL or invalidation separately |
The differences that matter
LRU tracks when a key was last accessed, not how many times it was accessed. A key read once just now outranks a key read thousands of times yesterday. LFU reverses that priority when yesterday's accumulated count remains higher.
A scan larger than the cache can replace an LRU cache's entire working set if every miss is admitted. LFU can preserve frequently accessed entries while one-off entries compete for the remaining space. This is not complete scan immunity: admission rules, initial counts, and ties still matter.
Raw LFU counts retain history for too long when demand shifts. Decay, periodic aging, or windowed frequency estimates let formerly popular keys lose protection. LRU needs no frequency-aging mechanism, although a scan or burst can still displace useful data.
Both policies can support expected O(1) operations, but that does not make their runtime costs identical. Exact LFU needs more bookkeeping than a basic LRU list, and both mutate metadata on hits. At high concurrency, sampled eviction or approximate counters can reduce coordination costs at the expense of exact policy behavior.
Eviction decides what to discard under memory pressure; admission decides whether a fetched item should enter the cache. Pairing recency with frequency-based admission can avoid choosing a purely LRU or purely LFU design. Neither policy addresses stale values, tenant isolation, or a hot key overwhelming one shard.
Choose LRU when
- Recent browsing, document access, or session activity defines the working set, and older activity quickly loses relevance.
- You need a straightforward baseline with predictable bookkeeping before workload measurements justify more complexity.
- Popularity changes frequently, and you do not want to tune frequency aging.
- You are implementing an exact in-process cache with a hash map and linked list, and scan pollution is not a dominant concern.
Choose LFU when
- A repeatedly accessed hot set remains useful across long intervals between individual accesses.
- One-off reads or scans would otherwise displace frequently reused entries.
- Request traces show frequency predicts reuse better than recency for the target cache size.
- You can support aging or decay, define tie-breaking, and accept the metadata and implementation costs.
A worked example
A catalog scan competes with hot product reads
Assume a cache holds 10,000 equal-sized product records. A stable set of 8,000 products receives repeated reads, then a background job requests 50,000 distinct cold products once each. If every miss is admitted and hot reads pause during the scan, LRU ends with the last 10,000 scanned products, displacing the hot set. LFU can retain the hot records if their counts exceed those of the scanned records. Now suppose shoppers switch to a different product category. Raw LFU may keep yesterday's winners too long, so add frequency aging or evaluate frequency-based admission. Replay both phases before choosing; the scan alone does not establish which policy performs better overall.
In the interview
- Start with the workload assumption: stable hot set, changing working set, or scans. Say which behavior makes your chosen eviction signal useful.
- State the capacity model. Equal-sized entries make key-count examples reasonable; variable-sized objects require a byte budget and may need multiple evictions per insertion.
- For LRU, explain the hash map and doubly linked list. For LFU, explain frequency buckets, tracking the minimum frequency, and an LRU tie-break within a bucket.
- Expect follow-ups about concurrency and distribution. Keep eviction metadata local to each cache node or shard rather than introducing a global ordering service.
- Propose replaying representative request traces at a fixed memory budget. Compare hit rate, origin load, tail latency, and metadata overhead, including behavior after a popularity shift.
Common mistakes
- Claiming LFU is always better because popular keys matter, without addressing changing popularity or stale frequency counts.
- Claiming LFU must take O(log n). A heap-based implementation can, but frequency buckets can support expected O(1) operations.
- Treating eviction as cache invalidation. Frequently or recently accessed entries can still contain stale data.
- Ignoring admission and object size, then assuming the policy with the highest request hit rate must also minimize backend cost.
Where it comes up
Interview questions where choosing between LRU and LFU comes up.
- Design a distributed cacheEviction policy directly affects memory use, per-node bookkeeping, and which entries survive capacity pressure.
- Design a URL shortener like BitlyRedirect caches must balance repeatedly popular short codes against newly popular links and one-off requests.
- Design a video streaming service like YouTubeMedia caching requires comparing stable popularity with recent demand while accounting for object sizes and origin-fetch cost.
- Design Wikipedia or NotionPage caches face recurring popular documents, bursts around newly edited pages, and freshness requirements separate from eviction.
Questions people ask
What is the difference between LRU and LFU?
LRU means least recently used and evicts the entry whose last access is oldest. LFU means least frequently used and evicts the entry with the lowest access count or frequency estimate. LFU implementations often use recency to break frequency ties.
Is LRU or LFU better for caching?
Neither is universally better. LRU fits workloads where recent access predicts reuse, while LFU fits workloads with a repeatedly accessed hot set. Evaluate scans, popularity changes, object sizes, and implementation overhead against representative traffic.
Can LRU and LFU both run in O(1) time?
Yes, under standard hash-map assumptions. Exact LRU uses a hash map and doubly linked list; exact LFU can use frequency buckets with linked lists and a tracked minimum frequency. Aging, expiration, byte-based capacity, and concurrency introduce additional work that the basic complexity claim does not capture.