How LFU works
Least Frequently Used tracks how many times each entry has been accessed. When the cache is full, it evicts the entry with the lowest access count. The assumption is that popular items will stay popular.
LFU versus LRU
- LRU uses recency, the time since last access.
- LFU uses frequency, the total number of accesses.
LFU resists a single scan better than LRU, because one access to many new keys does not make them frequent. It keeps stable hot keys longer.
The aging problem
A naive LFU never forgets old counts. A key that was hugely popular yesterday but cold today keeps a high count and resists eviction. Real systems add aging or decay, lowering counts over time, so the policy tracks current popularity rather than lifetime totals.
Cost
Maintaining frequency counts and finding the minimum efficiently needs extra structures, such as buckets grouped by frequency, making LFU heavier than LRU.
Key idea
LFU evicts the least frequently accessed entry and needs aging to avoid clinging to keys that were once but are no longer popular.