Redis Cache Eviction Policies

Hello! Welcome back to our course on designing high-load distributed systems.

In our previous lessons, we built a scalable and highly available Redis deployment using Redis Sentinel for failover and Redis Cluster for horizontal sharding. We now have a robust architecture for our in-memory data store. However, since Redis stores data in memory, we must manage this finite resource carefully. This leads to a critical question: what happens when a Redis node runs out of memory?

This lesson will address that exact problem. The learning outcome is to configure cache eviction policies in Redis: LRU, LFU, and TTL-based. We will explore how Redis manages memory limits and the different strategies it can use to automatically remove data when those limits are reached. Understanding these policies is crucial for tuning the performance and behavior of Redis as a cache in a high-load environment.

1. Setting Memory Limits: The `maxmemory` Directive

The foundation of Redis's eviction system is the maxmemory configuration directive. This setting defines a hard memory usage limit for a Redis instance.

maxmemory <bytes>: You can set this in your redis.conf file or dynamically using the CONFIG SET maxmemory <bytes> command. For example, maxmemory 2gb.

When the memory used by Redis reaches this limit, it triggers the configured eviction policy.

What if no eviction policy is set?
By default, the policy is noeviction. In this mode, when the maxmemory limit is reached, Redis will stop accepting commands that could increase memory usage (like SET, LPUSH, HSET) and will return an error. Read-only commands (like GET, LPOP, HGET) will continue to work. This behavior is suitable when you are using Redis as a primary database and cannot afford to lose any data due to eviction. However, when using Redis as a cache, this would effectively render the cache unwritable, so an eviction policy is essential.

2. Overview of Eviction Policies

Redis provides several policies to choose from, which you configure using the maxmemory-policy directive. They can be broadly categorized into two groups: policies that evict from any key (allkeys-*) and policies that only consider keys with an expiration (TTL) set (volatile-*).

Policy	Description
`noeviction`	(Default) Returns errors on write commands when `maxmemory` is reached.
`allkeys-lru`	Evicts the least recently used (LRU) keys from the entire keyspace.
`allkeys-lfu`	Evicts the least frequently used (LFU) keys from the entire keyspace.
`allkeys-random`	Evicts random keys from the entire keyspace.
`volatile-lru`	Evicts the least recently used keys from those that have an `expire` set.
`volatile-lfu`	Evicts the least frequently used keys from those that have an `expire` set.
`volatile-random`	Evicts random keys from those that have an `expire` set.
`volatile-ttl`	Evicts keys with an `expire` set, prioritizing those with the shortest time-to-live (TTL).

The choice between allkeys and volatile policies depends on your use case. If your Redis instance is purely a cache, allkeys-lru or allkeys-lfu are common choices. If you use the same instance to store both cached data (with TTLs) and persistent data (without TTLs), a volatile-* policy allows you to protect your persistent data from eviction.

3. Deep Dive: LRU vs. LFU

The most sophisticated and commonly used policies are LRU and LFU. Understanding their mechanics and trade-offs is key to effective cache tuning.

LRU: Least Recently Used

The allkeys-lru and volatile-lru policies evict keys that have not been accessed for the longest time. This is a classic caching algorithm based on the assumption that data accessed recently is likely to be accessed again soon.

Approximated LRU
An exact LRU implementation would require storing an access timestamp for every key, which is memory-intensive. Redis employs a clever optimization: an approximated LRU.

Instead of tracking all keys, Redis maintains a small, random sample of keys (the sample size is configurable via maxmemory-samples, default is 5).
When eviction is needed, it finds the key with the oldest access time within that sample and evicts it.
Each key object in Redis has a 24-bit field that stores a timestamp of its last access time.

This approximation is highly efficient in terms of memory and CPU, and its performance is very close to that of a true LRU. You can increase maxmemory-samples for a more accurate LRU at the cost of more CPU usage per eviction.

Weakness of LRU:
LRU is vulnerable to "scan-bursts." Imagine a batch job that reads a large number of items from the database, populating them in the cache. These items, though accessed only once, are now "recently used." This can cause the cache to evict older, but more valuable, items that are accessed frequently over time.

LFU: Least Frequently Used

The allkeys-lfu and volatile-lfu policies were introduced to address the weakness of LRU. They evict keys that are accessed the fewest number of times.

LFU Implementation Details
Like LRU, an exact LFU implementation (storing a counter for every key) would be too costly. Redis's LFU implementation is also probabilistic and highly optimized:

Frequency Counter: The 24-bit LRU field is repurposed. 16 bits store the last access time (in minutes), and 8 bits store a logarithmic frequency counter. This counter is a Morris counter, a probabilistic data structure that increments a counter with a decreasing probability. This allows it to represent a wide range of frequencies (from 0 to millions) using only 8 bits.
Decay Factor: To ensure that keys that were popular long ago but are no longer used can eventually be evicted, the frequency counter is decayed over time. You can control the decay rate with the lfu-decay-time setting (in minutes).

LFU is more robust against scan-bursts. A key accessed once by a batch job will have a low frequency count and will be a prime candidate for eviction, while a key accessed consistently over time will have a high frequency and be protected.

You can inspect a key's "idleness" (for LRU) or "frequency" (for LFU) using these commands:

OBJECT IDLETIME <key>: Returns the number of seconds since the key was last accessed (used for LRU).
OBJECT FREQ <key>: Returns the access frequency count (used for LFU).

4. TTL-Based Eviction

The volatile-ttl policy offers a different logic. It only considers keys with an expiration set and evicts the one that is closest to expiring.

This can be useful if your cache is filled with items that have varying, but known, lifetimes. The logic is to free up memory by removing data that would have expired soon anyway. It's generally less sophisticated than LRU or LFU for optimizing cache hit rates but can be effective and predictable in certain scenarios.

5. Configuration and a Practical Scenario

Let's apply this to a scenario relevant to your background in high-load payment systems.

Scenario:
Imagine a service that handles international payments. It needs to cache two types of data in Redis:

User Session Data: Short-lived, frequently accessed while a user is active. TTL of 15 minutes. Key format: session:{user_id}.
FX Rates: Long-lived, updated every hour, but accessed extremely frequently by nearly every transaction. Key format: fx:{currency_pair} (e.g., fx:usd-eur).

Configuration Dilemma:

If we use allkeys-lru, a sudden influx of thousands of new user sessions could create a "scan-burst" effect. These new session keys, being very recent, could push a critical (but slightly less recently accessed) FX rate key out of the cache, causing latency spikes as the service falls back to the database for FX rates.
If we use allkeys-lfu, the FX rate keys would quickly attain a very high frequency count, making them almost immune to eviction. The session keys would have much lower frequency counts, making them the first to be evicted when memory is tight. This is a much better fit for optimizing the performance of the core transaction flow.

An Alternative with volatile-*:
A more explicit design would be to separate cache candidates from protected data.

Set a 15-minute TTL on all session:* keys.
Do not set a TTL on the fx:* keys.
Configure maxmemory-policy volatile-lfu.

Now, Redis will only consider the session keys for eviction. The FX rate keys are completely protected. This approach gives you granular control, ensuring that your most critical, long-lived data is never evicted, while still allowing the cache to manage memory for transient data.

To configure this in redis.conf:

# Set max memory to 4 gigabytes
maxmemory 4gb

# Use the LFU policy on keys with an expire set
maxmemory-policy volatile-lfu

# Optional: Tune LFU decay time (e.g., decay counters for keys not accessed in 5 minutes)
# lfu-decay-time 5

You can monitor the effectiveness of your policy by checking the evicted_keys and keyspace_hits/keyspace_misses metrics from the INFO STATS command. A high number of evicted_keys is normal under memory pressure, but a falling hit rate may indicate your policy is not optimal for your workload.

Conclusion

In this lesson, we've dissected Redis's memory management and eviction mechanisms, which are fundamental to operating Redis as a reliable, high-performance cache.

Key Takeaways:

Eviction is triggered by maxmemory. Without it, Redis may consume all available system memory.
Eviction policies are configured via maxmemory-policy. The default, noeviction, protects data but can block writes.
LRU (Least Recently Used) is a good general-purpose policy but is vulnerable to access bursts that can pollute the cache.
LFU (Least Frequently Used) is more robust, as it prioritizes keeping frequently accessed items regardless of recentness, making it ideal for many high-load workloads.
Redis uses approximated, memory-efficient versions of LRU and LFU.
volatile-* policies provide a powerful way to use a single Redis instance for both pure caching (keys with TTL) and as a simple data store (keys without TTL).

Preview of the Next Lesson:

Now that we understand how to manage data within Redis, our next step is to manage the flow of data into Redis from a primary database. In the next lesson, we will implement the cache-aside pattern for synchronizing Redis with a primary data store. This is one of the most common and fundamental patterns for using a cache in a distributed system.