LFU Resident-Frequency Cache

LFU Resident-Frequency Cache Theory

The Least Frequently Used (LFU) cache policy tracks the frequency of access for each resident item in the cache. When the cache reaches capacity and a new item must be inserted, the item with the minimum frequency count is evicted.

Worked Example

Let's trace a Mixed stream A, B, A, C, A, B, D through an LFU cache with capacity 2.

A (Miss): Cache = [A:1].
B (Miss): Cache = [A:1, B:1].
A (Hit): Cache = [A:2, B:1].
C (Miss): Minimum count is B (1). Evict B. Cache = [A:2, C:1].
A (Hit): Cache = [A:3, C:1].
B (Miss): Minimum count is C (1). Evict C. Cache = [A:3, B:1].
D (Miss): Minimum count is B (1). Evict B. Cache = [A:3, D:1].

After this stream, the resident keys are A,D with counts A:3, D:1. Hits = 2, Misses = 5, Evictions = 3.

Interactive Experiment

You can test different streams and compare policies in the interactive module.

Set the Stream to Mixed.
Set the Capacity to 2.
Set the Policy to LFU and observe the Hits and Evictions.
Change the Policy to LRU and compare how recency affects the resident keys compared to frequency.

Limitations

True LFU maintains counts only while an item is resident in the cache; an evicted item loses its count and restarts at 1 if re-inserted. This small-scale exact LFU differs from probabilistic counters or lifetime frequency tracking systems like those in Redis. Furthermore, in LFU ties (multiple items having the same lowest frequency count) need a tie-breaking rule; here, we use Least Recently Used access time, then alphabetical order.

References

For more context on caching strategies and processor memory architecture, see the MIT Computer System Architecture lecture notes:https://csg.csail.mit.edu/6.5900/Lectures/L03handout.pdf

LFU Resident-Frequency Cache