Cache Eviction Policies Explained

Why Eviction is Necessary

A cache's primary limitation is its size. Since it operates in RAM, which is much more expensive than disk storage, we must impose a memory limit. In Redis, this is done using the maxmemory configuration directive.

Once this limit is reached, the cache must make a choice every time a new item needs to be added: which existing item should be removed? The goal of an eviction policy is to make an intelligent guess about which item is the least likely to be needed in the near future. A good policy maximizes the cache hit ratio (the percentage of requests served from the cache), while a poor one can lead to "cache thrashing," where useful items are constantly being evicted and re-fetched.

Let's start by looking at some of the most common policies.

Proactive Expiration: Time-To-Live (TTL)

Before we even get to eviction due to full memory, there's a simpler mechanism: Time-To-Live (TTL). This isn't an eviction policy in the same sense as LRU or LFU, but rather a property you can set on a key.

When you add a key to the cache, you can specify a timeout. Redis will automatically delete the key after that duration has passed.

• Use Case: This is perfect for data that has a known, limited lifespan. For example, a user's session token that should be valid for 30 minutes, or the results of a weather query that you know will be stale in an hour.

TTL is a form of proactive expiration. However, when the cache fills up with keys that haven't expired yet, we still need a policy to decide which one to evict. One such policy, volatile-ttl, specifically targets keys with an expiration set, choosing to evict the one with the shortest remaining time to live.

Now, let's explore the more dynamic, usage-based eviction policies.

1. Least Recently Used (LRU)

Concept: When the cache is full, evict the item that was accessed the longest time ago.

The intuition is straightforward: if an item hasn't been used recently, it's less likely to be used in the near future. This is based on the principle of temporal locality.

The Ideal LRU Implementation

From a computer science perspective, a perfect LRU cache is a classic data structures problem. To achieve the required performance constraints—constant time O(1) for both get and put operations—it is typically implemented with two data structures working together:

1. A Hash Map (or Dictionary): This stores the key and a pointer to a node in a linked list. This gives us O(1) lookups.
2. A Doubly Linked List: This list maintains the order of recency. Every time an item is accessed (read or written), its corresponding node is moved to the "front" of the list (Most Recently Used). When an eviction is needed, the node at the "tail" of the list is removed (Least Recently Used). The doubly-linked nature allows for O(1) removal and re-insertion of nodes.

To see this in action, the following video provides an excellent, detailed walkthrough of implementing an LRU cache from scratch.

LRU in the Real World: Redis's Approximation

Implementing a true LRU cache as described above has a significant memory overhead; every key needs to be stored in the hash map and as a node in the linked list. For a system like Redis, designed for extreme performance and memory efficiency, this is too costly.

Instead, Redis uses an approximated LRU algorithm. Rather than maintaining a perfect ordering of all keys, it does the following:

1. When eviction is needed, it takes a small, random sample of keys (the sample size is configurable via maxmemory-samples).
2. It finds the key within that sample that has been idle the longest (the least recently used one).
3. It evicts that key.

This probabilistic approach is surprisingly effective and provides a close-enough approximation to true LRU without the memory overhead.

You can read more about this in the official Redis documentation.

2. Least Frequently Used (LFU)

Concept: When the cache is full, evict the item that has been accessed the fewest number of times.

The intuition here is different from LRU. LFU assumes that an item's historical popularity is a better predictor of future use than its recency.

LRU vs. LFU: The Critical Difference

Consider this scenario:

1. You have a very popular item, A, that is accessed 100 times per minute.
2. Your cache is full of popular items like A.
3. A one-off script runs and accesses thousands of new, unique items (X, Y, Z, ...) just once.

• Under LRU: The new items (X, Y, Z) are the most recently used. To make space for them, LRU would start evicting popular, "hot" items like A. Your cache hit rate would plummet as it gets polluted with "one-hit wonders."
• Under LFU: The new items have a frequency of 1. The popular item A has a very high frequency. LFU would recognize that A is more valuable and would refuse to evict it to make room for the low-frequency newcomers.

LFU protects popular items from being flushed out by bursts of traffic to less important items.

LFU in the Real World: Count-Min Sketch

Just like true LRU, a true LFU implementation is impractical at scale. It would require a hash map and a balanced tree or heap to store every key and its exact access count, which is memory-intensive and computationally expensive to keep sorted.

To solve this, modern LFU implementations (including Redis's) use a probabilistic data structure. One of the most famous is the Count-Min Sketch.

This clever structure allows you to get an estimated frequency for millions of items using a tiny, fixed amount of memory. It works by using multiple hash functions to map an item to several counters in a grid, and it provides a guarantee that the estimated frequency is never less than the true frequency. This is perfect for LFU, as we only need a good relative comparison of frequencies to make an eviction decision.

Redis's LFU implementation is an approximation that combines a probabilistic counter (a Morris counter, similar in spirit to a Count-Min Sketch) with a decay mechanism, so that access counts decrease over time. This allows the algorithm to adapt to changing access patterns.

Redis Policies: allkeys vs. volatile

Now let's bring it all together with a practical look at how Redis presents these options. You'll notice Redis policies have prefixes like allkeys- and volatile-.

As the video and Redis docs explain, the difference is:

• allkeys-lru or allkeys-lfu: The eviction policy considers all keys in the cache as candidates for eviction.
• volatile-lru or volatile-lfu: The policy only considers keys that have a TTL set. Keys without a TTL are never evicted.

This distinction allows you to use a single Redis instance for two purposes: as a pure data store for persistent keys (no TTL) and as a cache for transient data (with TTL).

Summary of Policies and When to Use Them

Here is a summary of the common policies available in Redis:

Conclusion

We've now seen that a cache is more than just a simple key-value store. The eviction policy is its brain, constantly making decisions to optimize the use of limited memory.

Key Takeaways:

• Caches have finite memory, so an eviction policy is needed to decide which items to remove when the cache is full.
• TTL (Time-To-Live) is a simple mechanism to expire data after a set duration.
• LRU (Least Recently Used) evicts the item that has been idle the longest. It's a great general-purpose policy.
• LFU (Least Frequently Used) evicts the item with the lowest access count, protecting popular items from being flushed by scan-like traffic.
• Real-world systems like Redis use probabilistic approximations of LRU and LFU to achieve high performance and memory efficiency.
• The choice of policy is critical and depends entirely on your application's data access patterns.

Preview of the Next Lesson

Eviction handles the problem of a full cache. But what about a different problem: what happens when data in our primary database is updated or deleted? The copy in our cache is now stale. If we don't do anything, our application will serve incorrect, outdated information until the cached item eventually expires or is evicted.

In our next lesson, we will tackle this challenge by exploring cache invalidation strategies. We'll discuss how to actively keep your cache fresh and consistent with your source of truth.