LFU Cache
What it is
LFU means least frequently used. A full cache removes the key with the fewest uses. If several keys have the same count, remove the one used longest ago. A read or an update adds one use. A new key starts at one use.
The core idea
A hash map finds any key right away, the same as in a plain cache. The extra idea in LFU is to also group keys by how many times they were used, so the cache always knows which group holds the coldest keys without checking every key one by one. The cost is extra memory and more bookkeeping than a cache based only on recent use. Old popular keys can stay for a long time, even after the workload changes.
Example
A cache can hold two keys.
- Put key 1, then read key 1. Its count is now 2.
- Put key 2. Its count is 1.
- Put key 3. Key 2 is removed, even though it was added more recently.
Ties work differently. If key 1 and key 2 both sit at count 1 and a third key arrives, whichever of the two was touched longer ago is removed, not whichever was added first.
Where you meet this
- Redis can drop the least frequently used keys when it reaches its memory limit (the
allkeys-lfusetting). It keeps a small counter per key, and by default it lowers the counters every minute, so a key that was popular long ago does not stay forever. (Redis key eviction) - Caffeine, a Java cache library, estimates how often each key was used with a small counting table. It also keeps a small window of recent keys in front, so a brand new key gets a fair chance before its count has grown. (Caffeine efficiency)
- A CDN or an image cache serves the same popular files to many users, so how often a file is asked for says more than when it was last asked for.
When to choose it: popularity stays steady for a long time, like the top products in a shop or the logo on every page.
When not to: popularity moves. A key that was hot yesterday keeps a high count and stays after nobody wants it, while a new key starts at one use and leaves first. Real caches fix this by lowering counts over time (Redis) or by giving new keys a short recency window (Caffeine). The counts in this challenge never drop, to keep the rules simple.
When recent use is the better guess, LRU Cache is simpler and cheaper. The Redis docs suggest allkeys-lru as a good default.
Common bugs
- Using only recency and ignoring the count.
- Updating a value without increasing its count.
- Removing a key when updating an existing key.
- Choosing the wrong key after the last key with a low count is removed.
- Keeping a removed key's old count when it is added again.
Keep it fast
Avoid scanning all keys to choose one to remove. Keeping keys grouped by use count means each read or write does a fixed amount of work, no matter how many keys the cache holds.
Learn more
LRU Cache uses only order of use. Redis LFU documentation explains aging. Aging reduces old counts so past use does not protect a key forever.