LRU vs LFU

The decision

A cache has a fixed size. When it is full and a new entry arrives, the cache must remove one entry. This is eviction, and the rule that picks the entry is the eviction policy. LRU (least recently used) removes the entry that was used longest ago. LFU (least frequently used) keeps a count of reads for each entry and removes the entry with the lowest count. The choice decides how many reads reach the database.

Choose LRU when

• Popularity moves over time. News, trending items and recent orders are hot today and cold next week.
• You have no strong reason to prefer another rule. The Redis documentation calls LRU a good default when a small part of the data gets most of the reads.
• Scans are rare, or you can keep scan reads out of the cache.

Choose LFU when

• A stable set of items stays popular for weeks, such as the top products of a shop.
• Jobs sometimes read many different entries once, such as a report over old orders. These scans must not push out the popular entries.
• You can tune count decay, so that old popularity fades. Without decay, LFU holds on to old favourites.

The numbers that change the answer

Worked example 1 (Assumption: a tiny cache). The cache holds 4 entries. A, B and C each have a count of 10, and A was used longest ago. A scan reads X1, X2, X3, X4 and X5 once each. Then the app reads A, B and C.

• LRU: X1 takes the free slot. Each next X pushes out the oldest entry. After X1 to X5 the cache holds X2, X3, X4 and X5 (X1 left last). A, B and C all miss. Result: 0 hits in 8 reads.
• LFU: X1 fills the free slot with count 1. Each next X removes the previous X, because it has the lowest count. A, B and C stay. Result: 3 hits in 8 reads.

Worked example 2 (Assumption: a shop). There are 1,000,000 products. One entry is 2 KB. There are 2,000 reads per second. 50,000 popular products get 90% of the reads. The database takes 1,000 missed reads per second.

• Working set = 50,000 x 2 KB = 100,000 KB = 100 MB. With 20% room (our choice), the cache is 120 MB.
• Hit rate with the working set in cache: 90%. Database reads = 2,000 x 0.10 = 200 per second, which is 20% of its limit.
• A nightly scan reads 100,000 other products. Assumption: it finishes in 10 seconds, faster than popular products are read again. It flushes an LRU cache of 60,000 entries (120 MB).
• Right after it, up to 0.90 x 2,000 = 1,800 more reads per second miss. With the usual 200, the database sees up to 2,000 per second. That is 2,000 / 1,000 = 200% of its limit, until the cache refills.
• LFU keeps the popular entries. The scan entries have count 1 and remove each other.
• More memory helps little. 200 MB gives a 90.5% hit rate in this model, only 0.5 points above 100 MB.
• 2 GB holds all 1,000,000 products. That is 20 times the memory for 10 more points.

What breaks with each choice

• LRU breaks on scans. A scan makes one-time entries look "recent". Fix: read scan data without putting it in the cache, or use LFU.
• LFU breaks when taste changes. Old favourites keep high counts, and a new hot item starts with a low count. Fix: count decay. Redis lowers counters over time, by default every 1 minute (see Sources).
• Both break when the cache is smaller than the working set. In example 2, a 50 MB cache holds only half of the popular products and the database sees 110% load. Fix: size the cache first, then compare policies.

What it costs

• Switching policy is a setting change in many caches (check yours). Testing is the work: replay one day of read logs against both rules. Assumption: 2 to 3 engineer-days.
• Memory has less and less effect after the working set fits, so buy size only until the hit rate stops rising.

How each level answers

SDE-1: LRU removes the entry used longest ago. LFU removes the entry used the fewest times. Both are ways to choose what to remove when the cache is full.

SDE-2: I start with LRU, because it adapts fast when popularity moves. I switch to LFU if a scan or a report keeps flushing the popular entries.

Senior: I size first: 50,000 popular products x 2 KB is 100 MB, so I plan 120 MB. A fast scan of 100,000 entries could add 1,800 reads per second to the 200 the database already gets. It takes only 1,000. The fallback is LFU with decay, or keeping scan reads out of the cache. I compare hit rates using replayed logs, not guesses.

Staff: The cost is database load against cache memory. I ask what hit rate the database can survive, and size for that number, not for a perfect rate. The cache team owns the policy. I change one cache node first. I compare its hit rate, evictions per second and p99 (the time within which 99 of 100 requests finish) latency with the others. The choice was right if the hit rate holds through a scan and a sale day.

Say it in the interview

"I size the cache to the working set first: 50,000 hot products at 2 KB is 100 MB, which gives a 90% hit rate. I use LRU by default, because popularity moves. If a nightly scan flushes the hot entries and the database sees up to 2,000 reads per second against a limit of 1,000, I switch to LFU with decay."

Common mistakes

• Debating the policy before sizing the cache. A cache smaller than the working set fails with any rule.
• Saying "LFU is always better". New hot items start with a low count and can be removed first, and old favourites never leave, so LFU needs decay.
• Forgetting that eviction and TTL are different. A TTL removes an entry because it is old. Eviction removes an entry because memory is full.

Sources

• Redis, key eviction (policies, LRU as a default, sampled LRU, LFU decay every 1 minute by default): https://redis.io/docs/latest/develop/reference/eviction/ (opens in a new tab) (checked 26 Oct 2026).
• All sizes, rates and the database limit are assumptions made for teaching. The hit rates are calculated from them and assume the cache keeps the most-read entries.