Low Level Design: LFU Cache

By /

Core Problem

LFU (Least Frequently Used) is a cache eviction policy that removes the item with the lowest access frequency when capacity is exceeded. The intuition: if an item has been accessed many times historically, it is more likely to be accessed again than an item barely touched.

The fundamental challenge is tie-breaking. When multiple items share the same minimum frequency, which one gets evicted? The standard answer is: evict the least recently used among the tied items. This makes LFU a strict superset of LRU in the tie-breaking case — when all items have frequency 1, LFU behaves identically to LRU.

The design goal is O(1) time for both get and put. A naive implementation using a sorted frequency list would be O(log N). The trick to achieving O(1) is maintaining the right combination of data structures that make the minimum frequency and the eviction target directly accessible at all times.

Data Structures

Three data structures working together enable O(1) for all operations:

key_map: HashMap<key, {value, frequency}> — maps each key to its current value and frequency count. O(1) lookup by key.

freq_map: HashMap<frequency, LinkedHashSet<key>> — maps each frequency to an ordered set of keys at that frequency. The set is ordered by insertion time (recency), so the first element is the least recently used at that frequency. LinkedHashSet gives O(1) add, O(1) remove, and O(1) peek at the oldest element.

min_freq: A single integer tracking the current minimum frequency across all cached keys. This is the direct pointer to the eviction target’s bucket.

class LFUCache:
    capacity: int
    min_freq: int = 0
    key_map:  HashMap<K, (V, int)>
    freq_map: HashMap<int, LinkedHashSet<K>>

All three structures must be kept in sync on every get and put. The invariant: freq_map[min_freq] always contains at least one key (the eviction candidate).

Get Operation

Getting a key increments its frequency and updates both maps:

  1. Look up key in key_map. If absent, return -1.
  2. Retrieve current freq = key_map[key].frequency.
  3. Remove key from freq_map[freq].
  4. If freq == min_freq and freq_map[freq] is now empty: increment min_freq. (The minimum bucket just became empty; the new minimum must be at least freq + 1.)
  5. Add key to freq_map[freq + 1] (appended to tail = most recent position).
  6. Update key_map[key].frequency = freq + 1.
  7. Return value.

Every step is a hashmap or linked set operation — all O(1). The min_freq increment in step 4 is safe because a get always increases frequency by exactly 1; min_freq can only increase by 1 from a get (it can only reset to 1 from a put of a new key).

Put Operation

Put handles three cases:

Key exists: Update value in key_map, then run the same frequency-increment logic as get. The key moves up one frequency bucket.

Key is new, cache not full: Insert into key_map with frequency 1. Insert into freq_map[1]. Set min_freq = 1. (A new key always starts at frequency 1, which is always the new minimum.)

Key is new, cache at capacity:

  1. Identify eviction target: victim = freq_map[min_freq].first() (oldest entry at minimum frequency).
  2. Remove victim from freq_map[min_freq] and from key_map.
  3. Insert new key with frequency 1 into both maps.
  4. Set min_freq = 1.

Setting min_freq = 1 after inserting a new key is always correct — the freshly inserted key has frequency 1, which is the global minimum.

Eviction

The eviction mechanism is the payoff for maintaining min_freq and using LinkedHashSet as the frequency bucket container:

  • Which frequency bucket? freq_map[min_freq] — directly accessible, O(1).
  • Which key within the bucket? .first() on the LinkedHashSet — the least recently inserted key at that frequency, O(1).
  • Removal: LinkedHashSet.remove(first) — O(1) because LinkedHashSet maintains a doubly linked list internally alongside the hash table.

End-to-end eviction is O(1). The correctness guarantee is that min_freq always points to the bucket containing the least frequently used key, and within that bucket the ordering by insertion time gives us LRU tie-breaking for free.

LFU vs LRU

Understanding when to choose LFU over LRU requires knowing the workload characteristics:

LFU advantages:

  • Resists scan pollution: a sequential full-table scan does not evict frequently accessed hot items, because those items have high frequency counts that a one-time scan cannot overcome.
  • Better hit ratio on workloads with stable "popular item" distributions (Zipfian distributions common in databases and web caches).

LFU disadvantages:

  • Frequency pollution: Items popular in the distant past accumulate high counts and resist eviction even after they become irrelevant. LRU naturally forgets old access patterns; LFU does not.
  • Cold start problem: Newly inserted items always start at frequency 1 and are immediately eviction candidates, even if they are about to become very hot. LRU gives new items a fair initial chance.
  • Implementation complexity: LFU requires three data structures vs. LRU’s two.

TinyLFU

TinyLFU is a modern approximation of LFU that addresses the frequency pollution problem while remaining highly space-efficient. It is the eviction policy underlying the Caffeine Java cache library, which is the replacement for Guava Cache in most high-performance Java applications.

Count-Min Sketch: Instead of storing an exact frequency counter per key, TinyLFU uses a Count-Min Sketch — a probabilistic data structure that estimates frequency with a small, fixed-size array of hash counters. Space is O(1) relative to cache size (a few KB regardless of cache capacity), with a small overcount error bounded by the sketch dimensions.

Frequency decay (aging): TinyLFU periodically halves all counters in the sketch (a "reset" operation triggered every N insertions). This aging mechanism is what LFU lacks: old frequency counts decay over time, preventing historical pollution.

Window TinyLFU architecture: Caffeine uses a three-region design — a small window cache (1% of capacity, LRU eviction), a probationary segment, and a protected segment. New items enter the window cache. Items evicted from the window cache compete against the probationary tail using TinyLFU: the candidate with higher estimated frequency wins admission to the main cache. This gives new items a fair trial period before frequency-based eviction applies.

Benchmarks show Caffeine’s Window TinyLFU achieving 20-40% better hit ratios than pure LRU on realistic database and web workloads.

Applications

Database buffer pool: InnoDB’s buffer pool uses a variant of LRU with a "young" and "old" sublist — structurally similar to segmented LRU. Pages accessed multiple times are promoted to the young end, approximating LFU behavior to resist full-table scan pollution.

CPU instruction cache: Hardware cache replacement policies in modern CPUs often use pseudo-LRU or frequency-based policies for L1/L2 instruction caches, where the access pattern is highly repetitive (loops) and frequency is a strong predictor of future access.

CDN edge cache: CDN edge nodes use frequency-based eviction to retain the most-requested content at the edge. A video that has been requested 10,000 times today should not be evicted to make room for a video requested once, regardless of recency.

In-memory recommendation caches: Systems serving personalized recommendations cache pre-computed recommendation lists for users. LFU naturally retains active users’ recommendation caches while evicting caches for users who haven’t returned — exactly the right behavior for a user-keyed cache.

{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “What is the core data structure of an O(1) LFU cache?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Three hash maps: key_to_val mapping keys to values, key_to_freq mapping keys to access frequencies, and freq_to_keys mapping each frequency to an ordered set of keys at that frequency. A min_freq variable tracks the current minimum frequency for O(1) eviction.” } }, { “@type”: “Question”, “name”: “How does LFU handle frequency ties on eviction?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Within the same frequency bucket, eviction is LRU — the least recently used key among those with minimum frequency is evicted. The ordered set at each frequency is maintained as an insertion-order set (LinkedHashSet in Java) or doubly-linked list.” } }, { “@type”: “Question”, “name”: “What is TinyLFU?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “TinyLFU is a cache admission policy that uses a Count-Min Sketch to approximate access frequency with very low memory overhead. Caffeine (Java) uses TinyLFU as the admission filter in front of a main W-TinyLFU cache, achieving near-optimal hit rates with O(1) per-operation cost.” } }, { “@type”: “Question”, “name”: “When should you choose LFU over LRU?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Choose LFU when access patterns are skewed and some items are consistently more popular than others. LFU resists cache pollution from one-time large scans. LRU is preferable when workloads exhibit recency bias — recently accessed items are likely to be accessed again soon.” } }, { “@type”: “Question”, “name”: “How does Caffeine implement its cache eviction policy?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Caffeine uses Window TinyLFU (W-TinyLFU): a small admission window (LRU) feeds into a protected main cache (LFU approximated by a frequency sketch). Items graduate from the window to main cache only if their estimated frequency exceeds the eviction candidate’s frequency. This balances burst traffic (recency) with long-term popularity (frequency).” } } ] }

What is the core data structure of an O(1) LFU cache?

Three hash maps: key_to_val mapping keys to values, key_to_freq mapping keys to access frequencies, and freq_to_keys mapping each frequency to an ordered set of keys at that frequency. A min_freq variable tracks the current minimum frequency for O(1) eviction.

How does LFU handle frequency ties on eviction?

Within the same frequency bucket, eviction is LRU — the least recently used key among those with minimum frequency is evicted. The ordered set at each frequency is maintained as an insertion-order set (LinkedHashSet in Java) or doubly-linked list.

What is TinyLFU?

TinyLFU is a cache admission policy that uses a Count-Min Sketch to approximate access frequency with very low memory overhead. Caffeine (Java) uses TinyLFU as the admission filter in front of a main W-TinyLFU cache, achieving near-optimal hit rates with O(1) per-operation cost.

When should you choose LFU over LRU?

Choose LFU when access patterns are skewed and some items are consistently more popular than others. LFU resists cache pollution from one-time large scans. LRU is preferable when workloads exhibit recency bias — recently accessed items are likely to be accessed again soon.

How does Caffeine implement its cache eviction policy?

Caffeine uses Window TinyLFU (W-TinyLFU): a small admission window (LRU) feeds into a protected main cache (LFU approximated by a frequency sketch). Items graduate from the window to main cache only if their estimated frequency exceeds the eviction candidate’s frequency. This balances burst traffic (recency) with long-term popularity (frequency).

Scroll to Top