The most surprising truth about cache eviction policies is that the "best" one often depends less on your workload’s theoretical access patterns and more on the practical overhead of tracking those patterns.
Let’s see what happens when we try to cache a stream of user IDs. Imagine a web server that needs to quickly serve user profile data. It can’t possibly hold all user profiles in memory, so it uses a cache. When a request comes in for a user ID that isn’t in the cache, it’s a "cache miss." The server fetches the data from a slower database, puts it in the cache, and then serves the request. If the cache is full when a new item needs to be added, the server has to evict an existing item to make space. The question is, which one?
Here’s a simplified scenario. We have a cache that can hold 3 items.
- Request 1: User ID
101. Cache:[101](Miss) - Request 2: User ID
102. Cache:[101, 102](Miss) - Request 3: User ID
101. Cache:[101, 102](Hit) - We accessed101again. - Request 4: User ID
103. Cache:[101, 102, 103](Miss) - Cache is full, evict something.
Now, the eviction policy kicks in.
LRU (Least Recently Used)
LRU evicts the item that hasn’t been accessed for the longest time.
- Request 1:
101. Cache:[101] - Request 2:
102. Cache:[101, 102] - Request 3:
101. Cache:[102, 101](Order matters:101is now most recent) - Request 4:
103. Cache:[102, 101, 103](Miss). To make space, evict the least recently used. In[102, 101],102was used before101. So,102is evicted. Cache becomes[101, 103].
LRU is popular because it often aligns with temporal locality: if you just used something, you’re likely to use it again soon.
To implement LRU: You typically need a doubly linked list to maintain the access order and a hash map to quickly look up items in the list. When an item is accessed, you move it to the "most recently used" end of the list. When you need to evict, you take an item from the "least recently used" end.
LFU (Least Frequently Used)
LFU evicts the item that has been accessed the fewest times. If there’s a tie, it often falls back to LRU for those tied items.
Let’s track frequencies:
- Request 1:
101(freq: 1). Cache:[101(1)] - Request 2:
102(freq: 1). Cache:[101(1), 102(1)] - Request 3:
101(freq: 2). Cache:[101(2), 102(1)] - Request 4:
103(freq: 1). Cache:[101(2), 102(1), 103(1)](Miss). Cache is full.- Frequencies:
101(2),102(1),103(1). - Least frequent are
102and103(both 1). - If LFU uses LRU as a tie-breaker:
102was accessed before103. So,102is evicted. - Cache becomes
[101(2), 103(1)].
- Frequencies:
LFU aims to keep "hot" items that are popular over longer periods, even if they aren’t accessed right now.
To implement LFU: This is more complex. You often need a min-heap to track frequencies and a way to group items by frequency (e.g., a map of frequency to a doubly linked list of items with that frequency). When an item is accessed, its frequency increases, and it might move between frequency groups. Eviction involves popping from the min-heap.
ARC (Adaptive Replacement Cache)
ARC is more sophisticated. It dynamically adjusts between LRU and LFU-like behavior based on observed cache hits and misses. It maintains two LRU lists: one for items recently accessed (L1) and one for items that were previously in the cache but were evicted (L2). It also tracks "ghost" entries – items that would have been hits if they were still in the cache.
ARC tries to balance keeping recently used items (like LRU) with keeping frequently used items (like LFU). It uses the sizes of L1 and L2, and the rate of hits and misses on ghost entries, to decide whether to prioritize evicting from the "recently used" side or the "frequently used" side. It’s adaptive: if it sees a lot of LRU-like behavior (recent items are often hits), it leans towards LRU. If it sees LFU-like behavior (items accessed many times are still being hit), it leans that way.
To implement ARC: This is significantly more involved. It requires maintaining multiple lists and counters to track the state of L1, L2, ghost lists, and hit/miss rates. The logic for adjusting the cache size between L1 and L2 is the core of its adaptivity.
Which One to Choose?
- LRU: A good default. Simple to implement, low overhead, and works well for many common workloads with strong temporal locality. It’s the go-to for many in-memory caches like Redis (by default, though it has options) or Memcached.
- LFU: Consider if your data has "sticky" popular items that are accessed frequently over long periods, but not necessarily in rapid succession. Think of popular product pages on an e-commerce site. The overhead is higher than LRU.
- ARC: For workloads with unpredictable access patterns or a mix of temporal and frequency-based locality. It’s more complex but can offer superior hit rates in many real-world scenarios where neither pure LRU nor pure LFU excels. It’s often found in more advanced storage systems or specialized caches where maximizing hit rate is paramount and the complexity is justified.
The practical implementation details matter. The overhead of maintaining frequency counts for LFU or the complex state management for ARC can sometimes negate their theoretical benefits if the cache is small or the workload is very simple. For many common web application caching needs, LRU is a robust and efficient choice.
The next concept you’ll grapple with is how to effectively measure your cache’s performance to know if your eviction policy is actually working.