LFU Cache (Least Frequently Used)

“Designing an LFU Cache is the ultimate exercise in composite data structures, it forces you to synchronize multiple hash maps and linked lists to achieve O(1) performance for a complex priority problem.”

TL;DR

LFU Cache evicts the least frequently used key, with LRU as the tiebreaker. Achieve O(1) get and put by combining a key-to-node hash map, a frequency-to-doubly-linked-list map, and a min_freq tracker. On access, promote nodes to higher frequency tiers. On eviction, pop from the tail of the min_freq list. It builds directly on the LRU Cache design, and production caches such as Caffeine use approximate frequency counting (W-TinyLFU) instead of exact counts; see advanced caching for ML systems for the system-level view.

1. Introduction: The Evolution of Caching

In the world of high-performance computing, memory is your most precious resource. Whether you are building a web server, a database engine, or a machine learning inference pipeline, you will eventually hit the “Memory Wall.” You cannot fit everything in RAM. You must choose what to keep and what to discard.

This choice is governed by Cache Replacement Policies.

• The FIFO Approach (Queue): Discard what came in first. Simple, but often wrong because old data can be popular.
• The LRU Approach (Least Recently Used): Discard what hasn’t been used for the longest time. This works well for “Temporal Locality”, if you used it recently, you’ll likely use it again soon.
• The LFU Approach (Least Frequently Used): Discard what is used least often. This is superior for items that have long-term popularity but might be accessed sporadically.

The LFU Cache is one of the more demanding data structures to implement with O(1) operations. Unlike LRU, which needs a single list, LFU needs either a heap or a dynamic collection of lists. This post covers why it is hard, how to solve it with a “Frequency-Tiered Doubly Linked List” (a linked list of linked lists), and what production caches do instead of exact LFU.

1.1 Why This Problem Matters

• System Design Interview Staple: It tests your ability to combine data structures and keep them in sync.
• Real-world Relevance: Frequency-aware eviction is common in practice. Redis offers allkeys-lfu and volatile-lfu eviction policies (with an approximate counter), and Caffeine’s W-TinyLFU policy is frequency-based.
• Invariants: It is a clean exercise in maintaining invariants across several containers, which is where most real cache bugs live.

---

2. The Problem Statement

Implement the LFUCache class:

• LFUCache(int capacity): Initializes the object with the capacity of the data structure.
• int get(int key): Returns the value of the key if it exists in the cache. Otherwise, returns -1.
• void put(int key, int value): Updates the value of the key if present, or inserts it if not.
  • If the cache reaches its capacity, it must invalidate and remove the least frequently used key.
  • If there is a tie (multiple keys with the same frequency), the least recently used (LRU) key among them must be removed.

Constraint: Both get and put must run in O(1) average time.

---

3. Why LFU is Hard: The O(1) Trap

If you’ve solved the LRU Cache, you know that a Hash Map combined with a Doubly Linked List (DLL) gives you O(1) because moving a node to the head of the list is a constant-time pointer operation.

In LFU, we have two axes of priority:

1. Frequency: How many times was the key accessed?
2. Recency: If frequencies are tied, which was used longest ago?

The Naive (and Slow) Approach

You could use a Min-Heap where each node stores (frequency, last_access_time, value).

• get(key): O(log N) to update the heap.
• put(key): O(log N) to insert/evict. For a cache on the hot path of every request, an O(log N) heap update per access adds up, and the problem statement asks for O(1). We need the constant-time behavior of a hash table.

---

4. The Data Structure Design: The Frequency-Tiered DLL

To solve LFU in O(1), we must avoid sorting. Instead, we use a linked list of linked lists.

4.1 The Three Core Components

1. key_to_node (Hash Map): Maps the key to a Node object. Each node stores its value and its current frequency.
2. freq_to_list (Hash Map): Maps each frequency (an integer) to a Doubly Linked List. All keys in freq_to_list[5] have been accessed exactly 5 times.
3. min_freq (Global Variable): Tracks the minimum frequency currently present in the cache. This is our “shortcut” to find the eviction candidate instantly.

4.2 The “Promotion” Flow

When a key is accessed:

1. Identify its current frequency F.
2. Remove it from the freq_to_list[F].
3. If freq_to_list[F] is now empty and F was the min_freq, increment min_freq.
4. Move the key to freq_to_list[F+1].
5. Update its internal frequency counter to F+1.

Step 3 is safe because the promoted key itself now sits at frequency F+1, so F+1 is guaranteed to be the new minimum.

---

5. Implementation in Python

We first define a Node and a DoublyLinkedList helper.

class Node:
    """A single node representing a cache entry."""
    def __init__(self, key, value):
        self.key = key
        self.val = value
        self.freq = 1
        self.prev = None
        self.next = None

class DoublyLinkedList:
    """A standard DLL with dummy head and tail for easy removal."""
    def __init__(self):
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_to_front(self, node):
        """Adds a node directly after the dummy head (MRU position)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        """Removes a node from its current position in the list."""
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def pop_tail(self):
        """Removes and returns the node just before the dummy tail (LRU position)."""
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

The LFUCache Orchestrator

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        self.key_to_node = {}    # key -> Node
        self.freq_to_list = {}   # freq -> DoublyLinkedList

    def _update_node(self, node):
        """Internal helper to promote a node to a higher frequency tier."""
        old_freq = node.freq
        
        # 1. Remove from current frequency list
        self.freq_to_list[old_freq].remove(node)
        
        # 2. Update global min_freq if necessary
        if self.freq_to_list[old_freq].size == 0 and old_freq == self.min_freq:
            self.min_freq += 1
        
        # 3. Increment node frequency and add to new list
        node.freq += 1
        new_freq = node.freq
        if new_freq not in self.freq_to_list:
            self.freq_to_list[new_freq] = DoublyLinkedList()
        self.freq_to_list[new_freq].add_to_front(node)

    def get(self, key: int) -> int:
        if self.capacity == 0 or key not in self.key_to_node:
            return -1
        
        node = self.key_to_node[key]
        self._update_node(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        if key in self.key_to_node:
            # Case 1: Key exists, update value and promote frequency
            node = self.key_to_node[key]
            node.val = value
            self._update_node(node)
        else:
            # Case 2: New key
            if self.size >= self.capacity:
                # Eviction: Get the list for the current min_freq
                evict_candidate = self.freq_to_list[self.min_freq].pop_tail()
                del self.key_to_node[evict_candidate.key]
                self.size -= 1
            
            # Create and add the new node
            new_node = Node(key, value)
            self.key_to_node[key] = new_node
            
            # For a brand new node, frequency is always 1
            if 1 not in self.freq_to_list:
                self.freq_to_list[1] = DoublyLinkedList()
            self.freq_to_list[1].add_to_front(new_node)
            
            self.min_freq = 1
            self.size += 1

---

6. Implementation Deep Dive: Synchronizing the Maps

The beauty and the danger of this design lie in the synchronization. If you remove a node from a DLL but forget to update key_to_node, you have a Memory Leak. If you update min_freq incorrectly, you will evict the wrong item, leading to a Bypass of the LFU logic.

6.1 The “Dummy” Pattern

Why do we use dummy head and tail nodes in the DLL?

• It eliminates “if-else” checks for node.next is None.
• self.head.next = self.tail at initialization means the code for add_to_front works identically for the first node and the thousandth node.

6.2 The min_freq Reset

When a new key is added, min_freq is always reset to 1. A common mistake is trying to “calculate” whether 1 is really the minimum frequency. It is, by definition, because the new key is a frequency-1 item.

---

7. Comparative Analysis

Operation	LRU (LinkedHashMap)	LFU (Tiered DLL)	LFU (Min-Heap)
Get	O(1)	O(1)	O(log N)
Put	O(1)	O(1)	O(log N)
Eviction	O(1)	O(1)	O(log N)
Space	O(N)	O(N)	O(N)
Implementation effort	Simple	High	Medium

Hidden Constants

While both LRU and Tiered-DLL LFU are O(1), the hidden constant for LFU is higher: every access touches two hash maps and two lists instead of one map and one list.

---

8. Beyond LFU: Adaptive Replacement Cache (ARC)

Is LFU the ultimate policy? No. LFU has a fatal flaw: its memory is “sticky.” If a key was very popular in the morning but is never used again, it can stay in the cache indefinitely because its count is so high.

ARC (Adaptive Replacement Cache), from IBM Research (Megiddo and Modha, 2003), balances recency and frequency instead:

• ARC maintains two lists: one for keys seen once recently (recency) and one for keys seen at least twice (frequency), plus “ghost” lists of recently evicted keys.
• Hits in the ghost lists tell it which side deserved more space, so it continuously adjusts the target size of each list.

ZFS uses ARC for its main memory cache. PostgreSQL shipped ARC briefly in version 8.0 and replaced it soon after, partly over IBM’s patent, and now uses a clock-sweep algorithm.

---

9. Real-World Applications

9.1 Database Buffer Pools

Pure LFU is rare in buffer pools, but the goal of protecting frequently used pages from one-off scans is everywhere. MySQL’s InnoDB, for example, splits its LRU list into “young” and “old” sublists and inserts newly read pages at the midpoint, so a single full table scan cannot flush the hot pages.

9.2 Machine Learning Feature and Embedding Caches

Lookups in feature stores and embedding tables are usually heavily skewed: a small set of popular items, users or entities receives most of the traffic, and that set changes slowly. A frequency-aware policy keeps those entries resident even when a burst of one-off lookups (a batch backfill, a crawler) passes through, which plain LRU would let evict them.

9.3 Speech and Voice Agents

Voice agents repeat themselves: greetings, confirmations and hold messages are synthesized over and over. Caching the synthesized audio for frequent phrases skips TTS inference entirely on a hit, and because the popular phrase set is stable, frequency-aware eviction fits well. See multi-tier speech caching for a full design.

---

10. Interview Strategy

1. Start with LRU: Briefly explain why LRU is insufficient (it ignores long-term popularity).
2. Propose the Tiered Map: Draw a diagram showing freq -> DLL. This is the clearest way to explain O(1) LFU.
3. Explain the Eviction Tie-break: Mention that you use LRU within each frequency tier.
4. Discuss min_freq: Explain how you maintain the shortcut to the least frequent list.

---

11. Edge Cases and Resilience

When implementing LFU in a production environment (not just LeetCode), you face edge cases that break naive implementations.

11.1 The Zero-Capacity Cache

What if capacity is 0?

• Naive code might try to put() and then immediately evict().
• With nothing in the cache, freq_to_list[min_freq] may not exist, and the eviction step crashes.
• Production fix: Always guard with if capacity <= 0: return, as the implementation above does.

11.2 Frequency Overflow and Aging

In a long-running cache, a hot key can be accessed billions of times.

• If your frequency counter is a 32-bit signed integer, it can wrap around to a negative value.
• Impact: The most popular item suddenly looks like the least frequent one and gets evicted.
• Fix: Use 64-bit counters, or cap and age the counts. Redis, for example, stores an 8-bit logarithmic counter per key that saturates and decays over time; aging also fixes the “sticky” problem from Section 8.

11.3 Memory Overhead and Locality

In Python, a Node object is heavy (a full object with a per-instance attribute dictionary). In C++, a struct Node is small.

• Both LRU and LFU nodes carry key, value, prev and next. LFU adds a freq field per node, plus one list header per distinct frequency and a second hash map.
• The extra indirection means more pointer chasing and worse CPU cache locality, which can make LFU slower than LRU in practice even though both are O(1).

---

12. Concurrency: Making LFU Thread-Safe

The implementation above is single-threaded. In a real server, multiple threads will call get and put simultaneously.

12.1 The Global Lock (Coarse-Grained)

The simplest fix is to wrap every method in mutex.lock().

• Pros: Correctness is guaranteed.
• Cons: Contention. Even get mutates the structure (it promotes the node), so reads cannot share a lock, and the lock becomes the bottleneck under heavy concurrency.

12.2 Lock Striping (Fine-Grained)

We can shard the LFU cache.

• Create 16 separate LFUCache instances.
• shard_id = hash(key) % 16.
• Lock only the specific shard.
• Trade-off: The “least frequently used” key is now only local to the shard, not global. You might evict a fairly frequent item in Shard A while Shard B holds cold data. This is usually an acceptable trade-off for throughput, and it is the same idea as the segments in Java 7’s ConcurrentHashMap.

12.3 Buffered Policy Updates

High-performance caches avoid taking the policy lock on every read. Caffeine, for example, records reads into small buffers and applies them to the eviction policy in batches, and it tracks frequency with a compact Count-Min Sketch rather than exact per-key counters. Reads stay fast, and the policy sees nearly the same information slightly later.

---

13. Advanced Variant: Window-TinyLFU

TinyLFU was proposed by Gil Einziger, Roy Friedman and Ben Manes (arXiv 1512.00727, 2015; journal version in ACM Transactions on Storage, 2017). Its windowed variant, W-TinyLFU, is the eviction policy of Caffeine, a widely used Java cache, and Ristretto, a Go cache from Dgraph Labs, uses TinyLFU-style admission.

13.1 The Problem with Standard LFU

LFU is slow to adapt to new trends.

• Old viral content has freq=10,000.
• New breaking news has freq=10.
• The new content is evicted because 10 < 10,000. This is bad.

13.2 The W-TinyLFU Architecture

1. Admission Window: A small LRU region (1% of the capacity by default; Caffeine adapts this size at runtime) acts as a “Doorman.” New items enter here.
2. Main Cache: Segmented into Protected (hot) and Probation (cold) regions.
3. The Contest: When the Window is full, the victim from the Window competes with the victim from the Probation region.
   • We compare their approximate frequencies using a Count-Min Sketch.
   • If the newcomer is more popular than the incumbent, the incumbent is evicted.
   • If the newcomer is weaker, it is the one dropped.
4. Aging: The sketch counters are periodically halved, so old popularity fades and the “sticky” problem goes away.

This “Doorman” approach prevents “One-Hit Wonders” (items accessed once) from polluting the main cache, while the sketch tracks frequency for far more keys than the cache holds, in a small fixed amount of memory.

---

14. Complexity Analysis

Space Complexity

• key_to_node: Stores N nodes. O(N).
• freq_to_list: Stores the same N nodes distributed across lists, plus at most N list headers. O(N).
• Total: O(N).

Time Complexity (Put)

1. Check Hash Map: O(1) average.
2. Create Node: O(1).
3. Link to DLL Head: O(1) (pointer assignment).
4. If Full, Pop Tail: O(1) (pointer assignment).
5. Remove from Map: O(1).
6. Update min_freq: O(1) (assignment).
7. Total: O(1).

Time Complexity (Get)

1. Check Hash Map: O(1).
2. Unlink Node: O(1) (pointer assignment).
3. Link to New List: O(1).
4. Total: O(1).

Why Average vs Worst Case?

Hash map lookups are O(1) on average, not in the worst case. Under pathological collisions a Python dict lookup degrades to O(N), while Java 8+ HashMap falls back to balanced trees in crowded buckets, giving O(log N). Python randomizes string hashing (SipHash) to make such collisions hard to trigger deliberately, so we quote O(1) average time, which is also what the problem asks for.

---

15. Summary of Optimization Patterns

When designing high-performance data structures, we see recurring themes in LFU:

1. Space-Time Tradeoff: We spend extra memory (two maps plus the lists) to replace O(log N) heap operations with O(1) pointer updates.
2. No Sorting: We never sort. Grouping keys into exact-frequency buckets, plus recency order inside each bucket, gives the eviction order for free.
3. Lazy Cleanup: We don’t have to delete empty frequency buckets immediately (unless we want to save space), which keeps operations simple.

---

16. Historical Context: From LFU to TinyLFU

The history of LFU is largely a history of trying to fix its “stickiness” and its cost.

Early theory

Under the independent reference model (each key has a fixed access probability), keeping the most probable keys is optimal, and LFU approximates that by counting. Real workloads drift, and exact counts were expensive to maintain, so LRU and its cheap approximations (such as CLOCK) dominated in practice.

2000s: Scan resistance

Researchers focused on policies that combine recency and frequency and resist one-off scans.

• LIRS (Low Inter-reference Recency Set), by Song Jiang and Xiaodong Zhang (SIGMETRICS 2002), ranks blocks by the distance between their last two accesses rather than by count. An approximation, CLOCK-Pro, was adopted in NetBSD.
• ARC (Adaptive Replacement Cache), from IBM Research (2003), uses “ghost” lists of recently evicted keys to decide whether the recency or the frequency list deserves more space.

2015 onward: Approximate frequency (TinyLFU)

TinyLFU (Einziger, Friedman and Manes) replaced exact per-key counters with a small Count-Min Sketch plus periodic aging, which made frequency-based admission cheap enough for general-purpose caches. W-TinyLFU adds the small LRU window to absorb bursts of new keys. Caffeine (Java) uses it, and Ristretto (Go) uses TinyLFU-style admission.

---

17. The Comprehensive Test Suite

When you write this in an interview code-pad, you need to verify it. Do not just write put(1,1). Write a suite that targets the edge cases.

import unittest

class TestLFUCache(unittest.TestCase):
    def test_basic_functional(self):
        # The standard Example
        lfu = LFUCache(2)
        lfu.put(1, 1)        # State: [1:1]
        lfu.put(2, 2)        # State: [2:1, 1:1]
        self.assertEqual(lfu.get(1), 1) # State: [1:2, 2:1]

        lfu.put(3, 3)        # Evicts 2 (freq 1). State: [3:1, 1:2]
        self.assertEqual(lfu.get(2), -1)
        self.assertEqual(lfu.get(3), 3) # State: [3:2, 1:2]

        lfu.put(4, 4)        # Tie-break. 1 has freq 2, 3 has freq 2.
        # 1 was accessed at step 3. 3 was accessed at step 6.
        # 1 is LRU among freq-2 items. Evict 1.
        self.assertEqual(lfu.get(1), -1)
        self.assertEqual(lfu.get(3), 3) # State: [3:3, 4:1]
        self.assertEqual(lfu.get(4), 4) # State: [4:2, 3:3]

    def test_frequency_promotion(self):
        # Ensure items move up the ladder correctly
        lfu = LFUCache(3)
        lfu.put(1, 10)

        # Access 100 times
        for i in range(100):
            lfu.get(1)

        self.assertEqual(lfu.key_to_node[1].freq, 101)

        # Add new items
        lfu.put(2, 20) # freq 1
        lfu.put(3, 30) # freq 1

        # This insert should NOT evict 1, even though it's old
        lfu.put(4, 40)
        # Cache full (3 items). Candidates: 2 (freq 1), 3 (freq 1). 1 (freq 101).
        # Evict 2 (LRU of freq 1).

        self.assertEqual(lfu.get(2), -1)
        self.assertEqual(lfu.get(1), 10)

    def test_zero_capacity(self):
        lfu = LFUCache(0)
        lfu.put(1, 1)
        self.assertEqual(lfu.get(1), -1)

    def test_update_value_does_not_reset_freq(self):
        lfu = LFUCache(2)
        lfu.put(1, 1)
        lfu.get(1) # freq 2

        lfu.put(1, 100) # update value. freq should be 3 now!
        self.assertEqual(lfu.key_to_node[1].freq, 3)
        self.assertEqual(lfu.get(1), 100)

    def test_tie_breaking(self):
        lfu = LFUCache(2)
        lfu.put(1, 1) # freq 1
        lfu.put(2, 2) # freq 1

        lfu.get(1) # 1 promoted to freq 2
        lfu.get(2) # 2 promoted to freq 2

        # Both freq 2. 1 is LRU because 2 was accessed last.
        lfu.put(3, 3)

        self.assertEqual(lfu.get(1), -1) # 1 should be gone
        self.assertEqual(lfu.get(2), 2)  # 2 should stay

if __name__ == '__main__':
    unittest.main()

17.1 How to Debug LFU Instability

If you implement this and it fails randomly:

1. Check min_freq maintenance: This is the #1 bug. If you remove the last node from the min_freq list, do you definitely increment min_freq?
2. Check Empty List cleanup: Do you delete the DLL from the hash map when it’s empty? It’s not strictly necessary but saves memory.
3. Check Node pointers: When moving a node from List A to List B, do you reset node.prev and node.next? The DoublyLinkedList.add_to_front method overwrites both, but verify it in your own version.

---

18. Conclusion

When designing systems, LFU reminds us that metadata (frequency) is as important as the data itself. Start with the LRU design (hash map plus linked list). Add the frequency dimension. Handle the edge cases. Then remember that production caches usually approximate frequency (W-TinyLFU, Redis’s logarithmic counters) rather than track it exactly.

---

19. Key Takeaways

1. States are Synchronized: Designing complex structures is about maintaining invariants across multiple containers.
2. Frequency vs. Recency: LFU is about the “Volume” of access; LRU is about the “Proximity” of access.
3. Exact LFU is a teaching tool: Real systems age their counts and approximate them, because exact, never-decaying counts make the cache sticky.

---

FAQ

How does LFU Cache achieve O(1) for both get and put?

Three data structures work in concert: a hash map for O(1) key lookup, a frequency-to-DLL map for O(1) node promotion between frequency tiers, and a min_freq variable for O(1) eviction candidate identification. All doubly linked list pointer operations are constant time.

How does LFU break ties when multiple keys have the same frequency?

Within each frequency tier, keys are ordered by recency in a doubly linked list. Most recently accessed keys sit at the front. On eviction, the tail node (least recently used among the least frequent) is removed. This provides LRU behavior as the tiebreaker.

Why does min_freq reset to 1 when inserting a new key?

A newly inserted key has frequency 1 by definition, making it always the minimum possible frequency. Regardless of existing keys’ frequencies, the new key becomes the lowest-frequency candidate, so min_freq is unconditionally set to 1 on every insertion.

What is Window-TinyLFU and why is it better than standard LFU?

Standard LFU is sticky: old popular items accumulate high frequency counts and never get evicted even after becoming irrelevant. Window-TinyLFU adds an LRU admission window and uses a Count-Min Sketch for approximate frequency tracking. New items compete against incumbents based on recent popularity, preventing cache pollution by stale entries.