LFU Cache: Implementation and Use Cases

Hello! Welcome back to our module on implementing core data structures.

In the previous lessons, we built an LRU cache from the ground up and then compared it to a simpler version using collections.OrderedDict. We concluded that while OrderedDict is great for production simplicity, the from-scratch implementation is essential for demonstrating deep data structure knowledge in an interview. The core principle of LRU is recency: it assumes that recently accessed items are likely to be accessed again soon.

Today, we'll tackle a more complex caching policy: Least Frequently Used (LFU). This policy operates on a different assumption: the total number of times an item has been accessed (its frequency) is the best predictor of its future use, regardless of when it was last accessed. This seemingly small change in requirements leads to a significant increase in implementation complexity.

Our learning outcome is to implement an LFU cache and articulate the scenarios where it is more suitable than an LRU cache. This will test your ability to work with composite data structures and to reason about system design trade-offs, both crucial skills for a role at Anthropic.

1. When to Use LFU vs. LRU

Before diving into code, it's critical to understand the "why." A caching policy is a solution to a specific access pattern. Choosing the wrong one can hurt performance.

• LRU (Least Recently Used) excels with temporal locality. It's perfect for workloads where access patterns are bursty or sequential, like processing a stream of recent events or browsing a news feed. Its weakness is "scan resistance": a one-time full scan of a dataset can flush out valuable, older items from the cache.
• LFU (Least Frequently Used) excels with stable popularity. It's designed for workloads with a highly skewed access distribution, where a small subset of items accounts for the vast majority of hits over the long term.

Imagine a system like AWS Bedrock serving model metadata. A popular model like claude-3-opus-20240229 might be queried constantly throughout the day. Even if there's a 30-minute period where other, less common models are accessed (a "scan"), you wouldn't want Claude 3's metadata to be evicted. LFU would keep it cached due to its high overall access count, whereas LRU might evict it in favor of the more recently accessed, but less popular, models.

To solidify this concept, let's watch a brief clip from a system design discussion.

However, LFU has a key weakness: cache pollution. An item that was once extremely popular but is no longer relevant can remain in the cache for a long time, displacing newer, more relevant items. This is often called the "stickiness" problem. We'll revisit this when discussing trade-offs.

2. The Challenge: Designing an O(1) LFU Cache

The formal problem statement is as follows:

• Design and implement a data structure for a Least Frequently Used (LFU) cache.
• It must support get(key) and put(key, value) operations.
• When the cache reaches capacity, a put operation must evict the least frequently used item.
• If there's a tie (multiple items have the same lowest frequency), the least recently used item among them should be evicted.
• Both get and put must have an average time complexity of O(1).

The O(1) constraint and the tie-breaker rule make this significantly harder than the LRU cache. A simple hash map and a single doubly linked list won't work because we need to track both frequency and recency. A naive approach using a min-heap to track frequencies would result in O(log N) operations, which doesn't meet the requirement.

To achieve O(1), we need a more sophisticated, composite data structure.

3. The O(1) LFU Architecture

The standard solution involves combining two hash maps and multiple doubly linked lists. The core idea is to group items by their access frequency.

1. key_to_node (dict): A primary hash map that maps a key to its corresponding Node in the cache. This provides O(1) lookup for any item. The Node itself will store its key, value, and freq (frequency).

2. freq_to_list (dict): A second hash map that maps a frequency count (e.g., 5) to a doubly linked list containing all items that have been accessed exactly that many times.

   • This is the "list of lists" concept. freq_to_list[5] is a DLL of all items with frequency 5. freq_to_list[1] is a DLL for all items with frequency 1.
   • Within each frequency-specific DLL, we maintain an LRU policy. New items are added to the head, and eviction candidates are taken from the tail. This elegantly handles the tie-breaker rule.

3. min_freq (int): An integer variable that tracks the lowest frequency currently present in the cache. This is a critical optimization that allows us to find the list of eviction candidates in O(1) time, without having to iterate through the freq_to_list map.

To see how these pieces fit together, let's watch a detailed explanation of the architecture.

4. Implementing the LFU Cache

Now, let's translate this architecture into production-quality Python code. We'll build this incrementally, starting with our helper classes and then the main LFUCache orchestrator. The following article provides a very clean and well-documented implementation that we will use as our reference.

Let's break down the implementation from the article.

Helper Classes: Node and DoublyLinkedList

The Node is slightly different from our LRU version, as it now includes a freq attribute, initialized to 1. The DoublyLinkedList is nearly identical to what we built for our from-scratch LRU cache. It uses dummy head/tail nodes to simplify add_to_front and remove operations and includes a pop_tail method for O(1) LRU eviction.

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):



        # ... implementation is the same as our from-scratch LRU ...
        # (add_to_front, remove, pop_tail)

LFUCache Orchestrator

This class brings all the components together. The logic is intricate, so let's walk through the key operations as described in the video and article.

The core of the logic resides in a helper function, which the article calls _update_node. This function is responsible for "promoting" a node to a higher frequency tier upon access.

_update_node(self, node) logic:

1. Get the node's current frequency, old_freq.
2. Remove the node from the list at self.freq_to_list[old_freq].
3. Crucial check: If the list at old_freq is now empty AND old_freq was the self.min_freq, we must increment self.min_freq. This ensures our eviction shortcut remains valid.
4. Increment the node's frequency: node.freq += 1.
5. Add the node to the front of the list at its new_freq. If this list doesn't exist, create it.

get(self, key) logic:

1. If the key is not in self.key_to_node, return -1.
2. Retrieve the node from self.key_to_node.
3. Call self._update_node(node) to promote it.
4. Return node.val.

put(self, key, value) logic:
This is the most complex part, handling both updates and insertions with eviction.

• Case 1: Key exists.
  1. Retrieve the node from self.key_to_node.
  2. Update its value: node.val = value.
  3. Call self._update_node(node) to promote it.
• Case 2: New key.
  1. Check capacity. If self.size >= self.capacity:
     • Find the list of candidates for eviction: eviction_list = self.freq_to_list[self.min_freq].
     • Pop the LRU item from this list: victim = eviction_list.pop_tail().
     • Remove the victim from self.key_to_node.
     • Decrement self.size.
  2. Create a new_node.
  3. Add it to self.key_to_node.
  4. Add the new_node to the front of the list at frequency 1 (self.freq_to_list[1]). Create the list if it doesn't exist.
  5. Crucial step: Reset self.min_freq = 1. A new item's frequency is always 1, making it the new minimum.
  6. Increment self.size.

The following part of the NeetCode video walks through this implementation logic, which can help clarify how the pieces move.

5. Production-Grade Considerations

Your work on Bedrock's infrastructure highlights the gap between a whiteboard algorithm and a production system. The LFU implementation is a perfect place to discuss this. While our implementation is correct, a real-world system would require more.

• Concurrency: Our current implementation is single-threaded. Making it thread-safe is the topic of our next lesson, but it would involve adding locks. A simple global lock would create high contention. A more advanced approach, like the "lock stripping" used in Java's ConcurrentHashMap, would involve sharding the cache and locking individual shards, trading global LFU accuracy for higher throughput.
• Probabilistic Counting: For massive caches, storing an exact frequency count for every item is memory-intensive. Systems like Redis and high-performance caches often use probabilistic data structures like a Count-Min Sketch. This approximates frequencies using sub-linear space, trading perfect accuracy for huge memory savings. The article "Designing an in-memory LFU cache" (LINK) explores this in detail, and it's a technique worth knowing about for system design discussions.
• Frequency Aging: The "stickiness" problem is real. To solve it, production systems implement frequency aging. For example, all frequency counts might be halved periodically. This allows the system to adapt to changing access patterns, as the impact of old accesses decays over time. The Window-TinyLFU algorithm, used in many modern caches, is an advanced form of this that combines an LRU "window" with an LFU main area to get the best of both worlds.

Conclusion

In this lesson, we've gone deep into one of the most complex standard data structure interview problems. You should now be able to implement an O(1) LFU cache and, just as importantly, articulate its design trade-offs.

Key Takeaways:

• LFU vs. LRU: LFU is for stable, long-term popularity (skewed access), while LRU is for temporal locality (bursty access).
• O(1) Architecture: The solution hinges on a composite data structure: a key_to_node map for direct access, a freq_to_list map to group nodes by frequency, and a min_freq integer for O(1) eviction.
• Tie-Breaking: LRU is used as a tie-breaker within each frequency group by managing each group's nodes in a doubly linked list.
• Complexity: LFU is significantly more complex to implement and has a higher constant-factor overhead than LRU, which is a critical trade-off to consider in a production system.

Next Lesson Preview

We've successfully built a single-threaded LFU cache. However, any real-world service, like the ones you build at AWS, is highly concurrent. In our next lesson, we will implement a thread-safe LFU cache and discuss the increased complexity compared to a thread-safe LRU cache. This will involve a deep dive into locking strategies and their performance implications, connecting directly to your experience with concurrent systems in Rust and preparing you for advanced concurrency questions.