Welcome back! In our previous lessons, we've explored different strategies for populating and updating a cache, such as cache-aside, read-through, and write-back. These patterns answer the questions of when and how to put data into the cache. Now, we'll address the inevitable follow-up question: what happens when the cache is full?
Cache memory is a finite and expensive resource. To make room for new data, we must discard existing data. The set of rules that governs this process is called a cache eviction policy. This lesson focuses on comparing the most common memory eviction policies—LRU, LFU, and FIFO—and understanding how to choose the right one for different data access patterns. Mastering this is a fundamental skill for designing high-performance systems and a frequent topic in system design interviews.
1. The Need for Eviction: Why We Can't Keep Everything
The core trade-off of caching is using a small amount of fast, expensive memory to avoid accessing a large amount of slow, cheaper storage (like a database on disk). Because the cache is limited in size, we need an intelligent strategy for deciding what to remove when it fills up. A poor eviction policy can be counterproductive, leading to a low cache hit ratio and negating the benefits of having a cache in the first place.
Caching in System Design Interviews w/ Meta Staff Engineer
The video "Caching in System Design Interviews" provides a concise introduction to why eviction policies are necessary.
Watch the initial segment on cache eviction policies. The key takeaway is that memory is limited, so we need a strategy for deciding what data is most valuable to keep.
2. A Tour of Eviction Policies
There are many eviction policies, each optimizing for a different definition of "valuable" data. We will focus on the three most foundational ones: FIFO, LRU, and LFU. The image below provides a great high-level overview of these and other policies.
First-In, First-Out (FIFO)
This is the simplest eviction policy. As the name suggests, it evicts items in the same order they were added. Think of it as a queue: the first item to enter the cache is the first to leave when space is needed.
- Mechanism: The cache keeps track of the insertion order of all items. When an eviction is needed, the oldest item is removed.
- Pros: Very simple to implement and has minimal computational overhead.
- Cons: Its primary weakness is that it completely ignores how frequently or recently an item has been accessed. A very popular item that was loaded early will be evicted before a brand new, rarely-accessed item. This often leads to poor cache hit ratios in real-world applications.
Caching in System Design Interviews w/ Meta Staff Engineer
Let's return to the "Caching in System Design Interviews" video for a quick summary of FIFO.
Watch the brief explanation of First In, First Out. Note the key point: "It's dead simple, and it's rarely the right choice in a system design interview."
Due to its limitations, you will rarely choose FIFO for a high-performance application cache, but it's essential to know what it is and why more sophisticated policies are usually preferred.
Least Recently Used (LRU)
LRU is one of the most popular and effective eviction policies. It operates on the principle of temporal locality, which assumes that data accessed recently is likely to be accessed again soon. Therefore, if you need to make space, you should discard the data that has been sitting unused for the longest time.
- Mechanism: The cache tracks the last access time for each item. When an item is accessed (read or written), it's marked as the "most recently used." When eviction is needed, the "least recently used" item is removed. This is commonly implemented using a combination of a hash map (for fast lookups) and a doubly linked list (to easily move items and track recency).
- Pros: Adapts well to changing access patterns and is effective for many real-world workloads where user behavior is dynamic. It is often the default choice.
- Cons: Can perform poorly with certain access patterns, such as a full table scan of a dataset larger than the cache. This action can flush out all the "hot" items and replace them with "cold," single-use items.
Cache Replacement Policies - MRU, LRU, Pseudo-LRU, & LFU
The video "Cache Replacement Policies" from Neso Academy provides an excellent, detailed walkthrough of how LRU works.
Watch the first part of the LRU explanation from the conceptual overview. Follow the example of block requests and see how the list of "most" to "least" recently used items is updated on every access and eviction. You don't need to dive into the age-bit implementation that follows unless you are curious about low-level hardware details.
Least Frequently Used (LFU)
While LRU prioritizes recency, LFU prioritizes popularity. It operates on the assumption that data that has been accessed many times in the past is likely to be valuable and should be kept in the cache.
- Mechanism: The cache maintains a usage counter for each item. Every time an item is accessed, its counter is incremented. When eviction is needed, the item with the lowest frequency count is removed.
- Pros: Retains popular items very effectively, even if they are not accessed for a while. This is ideal for workloads where some data is inherently more popular than other data (e.g., best-selling products, viral articles).
- Cons:
- New Item Problem: New items start with a count of 1 and are vulnerable to being evicted quickly, even if they are about to become popular.
- Cache Pollution: Items that were once popular but are no longer relevant can remain in the cache for a long time, a problem known as cache pollution. Modern LFU implementations often include a "decay" mechanism to gradually lower the count of unused items to mitigate this.
Cache Replacement Policies - MRU, LRU, Pseudo-LRU, & LFU
The Neso Academy video also provides a clear example of LFU.
Watch the section explaining the LFU policy. Pay close attention to how the frequency count is updated on each hit and how ties (items with the same frequency) are broken, which is often done using a FIFO or LRU rule.
3. Making the Choice: LRU vs. LFU
The decision between LRU and LFU is a classic trade-off in system design. It hinges on understanding the access patterns of your data.
LFU vs. LRU: How to choose the right cache eviction policy
This article from Redis provides an excellent, in-depth comparison of LFU and LRU, complete with real-world scenarios.
Read through the article to solidify your understanding. Start with the comparison table. Then, read the sections that define LFU and LRU, noting the pros and cons listed for each. Finally, focus on the section How to know which policy is right for you. This part connects the theoretical policies to concrete application workloads, which is exactly what's required in a system design interview.
The general guidance can be summarized in this flowchart:
Summary of When to Use Each:
-
Use LRU (Least Recently Used) when:
- Recent access is the best predictor of future access.
- Workloads are dynamic and access patterns shift frequently.
- Examples: User session data, real-time analytics dashboards, personalized content feeds.
-
Use LFU (Least Frequently Used) when:
- Access patterns are stable and skewed (some items are vastly more popular than others).
- Historical popularity is more important than recency.
- Examples: Caching popular products on an e-commerce site, frequently accessed API endpoints, system configuration data.
4. From Theory to Code: An Implementation View
Since you have experience with Go and software architecture, it's valuable to see how these policies can be implemented in a modular way. A common approach is to use the Strategy design pattern, where the cache is configured with a specific eviction policy that conforms to a shared interface.
Golang LLD: Design a Cache System (LRU, LFU, FIFO) | Aashish Koshti
This blog post demonstrates how to design a cache system in Go with pluggable eviction policies.
First, look at the EvictionPolicy interface definition. This defines a contract that any eviction policy (LRU, LFU, etc.) must follow. Next, review the LRU implementation. Notice how it uses Go's built-in list.List (a doubly linked list) to efficiently move accessed elements to the front. Finally, examine the Put method logic. See how, when the cache is full (c.capacity <= len(c.storage)), it calls c.evictionpolicy.Evict() to remove an item. This single line shows the power of the design: the main cache logic doesn't need to know how eviction works, only that it can ask the configured policy to do it.
This design makes the system flexible. You could start with an LRU policy and, after analyzing production metrics, swap it out for an LFU policy by simply providing a different implementation of the EvictionPolicy interface, without changing the core cache logic.
Conclusion
In this lesson, we dissected the critical role of cache eviction policies in managing a finite resource. You learned how to compare the fundamental trade-offs between FIFO, LRU, and LFU, and how to select the appropriate policy based on the data access patterns of your application.
Key Takeaways:
- Eviction is necessary because cache memory is limited and expensive. The goal is to maximize the cache hit ratio by keeping the most valuable data.
- FIFO is simple but often ineffective as it ignores access patterns.
- LRU is the common default, prioritizing recency. It excels in dynamic workloads where what's new is what's important.
- LFU prioritizes popularity, making it ideal for stable workloads with a clear distinction between "hot" and "cold" data.
- The choice of policy is not arbitrary; it's a design decision that must be justified by analyzing your application's specific workload. Starting with LRU and monitoring its performance is a sound and common strategy.
In our next lesson, we will tackle another crucial aspect of scaling a caching layer: consistent hashing. Now that we know how to manage items within a single cache instance, we'll learn how to distribute data across a cluster of cache servers in a way that is resilient to nodes being added or removed.