Part 4: "The Memory Limit" — Eviction Policies and Approximated LRU

Story Opening

Maya, the Staff Engineer at GlobalMart, watched the Grafana dashboards with a growing sense of dread. The Redis cluster, which had performed flawlessly during the Black Friday traffic spike and survived a simulated power outage, was now facing a slow, inevitable death.

The memory usage graph for the primary Redis instance was a perfectly straight line pointing upwards. It had crossed 80% capacity, then 85%, then 90%. GlobalMart was caching everything: product catalogs, user sessions, shopping carts, and the real-time leaderboard. But they weren’t expiring anything. The cache was acting like a persistent database, accumulating data endlessly.

At 95% capacity, the Linux operating system started aggressively swapping memory pages to the disk swap file to free up physical RAM. The moment this happened, Redis’s sub-millisecond latency vanished. Requests that took 1ms were now taking 100ms, then 500ms, as the CPU thrashed trying to read memory from the slow SSD swap space.

Finally, at 100% capacity, the Linux OOM (Out Of Memory) killer stepped in. It identified the Redis process as the memory hog and summarily terminated it. The cluster went down, the Cache Stampede hit the PostgreSQL database, and the site ground to a halt.

Maya realized she had treated Redis like an infinite bucket. She needed to teach it how to forget. She needed to configure a hard memory limit and implement an intelligent eviction policy to automatically remove old data when the bucket got full.

Conceptual Deep-Dive

Memory management in Redis is fundamentally different from a traditional database. A relational database stores data on disk and uses RAM merely as a buffer pool. When the buffer is full, it simply writes the oldest pages back to disk.

Redis is the RAM. When the RAM is full, it cannot simply “write to disk” (unless you use the deprecated Virtual Memory feature, which is a terrible idea). It must either reject new writes or delete existing data.

The maxmemory Directive

The first step in memory management is telling Redis exactly how much RAM it is allowed to use. This is done via the maxmemory directive in redis.conf.

# Set a hard limit of 10 Gigabytes
maxmemory 10gb

Crucially, as Maya learned in Part 3, you should never set maxmemory to 100% of your physical RAM. You must leave headroom (typically 20-30%) for the operating system, network buffers, and most importantly, the Copy-on-Write (CoW) memory spikes that occur during background RDB saves or AOF rewrites. If you have 16GB of physical RAM, a safe maxmemory setting is around 10GB or 11GB.

Eviction Policies: How to Forget

Once Redis hits the maxmemory limit, its behavior is dictated by the maxmemory-policy configuration.

There are several policies available, but they generally fall into three categories:

1. No Eviction (noeviction): The default policy. When memory is full, Redis simply returns an error (OOM command not allowed) for any command that would increase memory usage (like SET, INCR, LPUSH). Reads (GET) continue to work. This is only suitable if you are using Redis purely as a primary database where data loss is unacceptable, but it will eventually break your application.
2. Volatile Eviction (volatile-*): These policies only evict keys that have an explicit expiration time (TTL) set via the EXPIRE command. If a key has no TTL, it will never be evicted.
   • volatile-lru: Evict the least recently used keys among those with an expiration set.
   • volatile-ttl: Evict the keys with the shortest remaining time-to-live.
   • volatile-random: Evict random keys among those with an expiration set.
3. Allkeys Eviction (allkeys-*): These policies will evict any key, regardless of whether it has a TTL set. This is the most common configuration when using Redis purely as a cache.
   • allkeys-lru: Evict the least recently used keys across the entire dataset.
   • allkeys-random: Evict random keys across the entire dataset.

For GlobalMart’s caching layer, Maya knew allkeys-lru was the correct choice. If the cache was full, it should automatically delete the products that users hadn’t viewed recently to make room for new ones.

The Ingenious Approximated LRU Algorithm

How does a database implement an LRU (Least Recently Used) cache efficiently?

The textbook computer science implementation uses a Doubly Linked List combined with a Hash Map. Every time you access a key, you move its node to the head of the linked list ($O(1)$). When the cache is full, you delete the node at the tail of the linked list ($O(1)$).

However, Redis does not use a linked list for its LRU implementation.

Why? Because adding two 64-bit pointers (prev and next) to every single key in a database containing 100 million keys would consume an enormous amount of memory—completely defeating the purpose of an in-memory store. Furthermore, constantly updating pointers on every single read operation would cause massive memory fragmentation and CPU cache invalidation.

Instead, Redis uses a brilliant, probabilistic Approximated LRU algorithm.

Here is how it works:

1. The LRU Clock: Redis maintains a global 24-bit clock that ticks roughly every second.
2. The Key Timestamp: Every Redis object (the value associated with a key) contains a 24-bit field in its header. When a key is accessed (read or written), Redis copies the current value of the global LRU clock into this field.
3. The Eviction Pool: When Redis hits the maxmemory limit and needs to evict a key, it doesn’t scan the entire database. Instead, it randomly samples a small number of keys (dictated by the maxmemory-samples configuration, default is 5).
4. The Approximation: It calculates the “idle time” for each of the 5 sampled keys by comparing their timestamp to the global clock. It then evicts the key with the longest idle time among those 5 samples.

By sampling just 5 keys, Redis achieves an eviction pattern that is statistically very close to a true LRU, but uses zero extra memory for pointers and requires minimal CPU overhead. If you increase maxmemory-samples to 10, the approximation becomes even closer to true LRU, at the cost of slightly more CPU cycles during eviction.

Technical Explanation

Maya decided to implement the allkeys-lru policy for the general product cache, but she realized a critical flaw. The shopping carts (Part 3) and the real-time leaderboard (Part 2) were stored in the same Redis instance as the ephemeral product cache.

If she used allkeys-lru, Redis might decide to evict an active shopping cart or a crucial leaderboard entry just because it hadn’t been accessed in the last 10 minutes, prioritizing a highly viewed but easily re-fetchable product page.

This is a classic architectural anti-pattern: mixing persistent data (carts) with ephemeral data (cache) in the same eviction pool.

She had two choices:

1. Split the instances: Run two separate Redis servers. One for the cache (allkeys-lru, no persistence) and one for the carts/leaderboard (noeviction, mixed persistence). This is the best practice for large-scale enterprise architectures.
2. Use volatile-lru: Keep them in the same instance, but change the policy to volatile-lru. Then, ensure that only the ephemeral cache keys have a TTL set. The carts and leaderboard keys would have no TTL, making them immune to eviction.

Given the infrastructure constraints at GlobalMart, she chose the second option.

Step-by-Step Hands-On

Maya updated the redis.conf and the Spring Boot application to implement the volatile-lru strategy.

Step 1: Configuring Eviction in redis.conf

# Set the hard memory limit (e.g., 10GB on a 16GB machine)
maxmemory 10gb

# Evict the least recently used keys among those with an expiration set
maxmemory-policy volatile-lru

# Increase samples for a better LRU approximation (default is 5)
maxmemory-samples 10

Step 2: Setting TTLs in Spring Boot Cache

To make volatile-lru work, Maya had to ensure that every product cached by Spring Boot had an explicit Time-To-Live (TTL). Keys without a TTL would never be evicted, eventually causing an OOM error if they filled the 10GB limit.

Spring Boot’s @EnableCaching doesn’t provide a way to set TTLs per-cache out of the box. Maya had to customize the RedisCacheManager.

import org.springframework.cache.annotation.EnableCaching;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.cache.RedisCacheConfiguration;
import org.springframework.data.redis.cache.RedisCacheManager;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.serializer.GenericJackson2JsonRedisSerializer;
import org.springframework.data.redis.serializer.RedisSerializationContext;

import java.time.Duration;
import java.util.HashMap;
import java.util.Map;

@Configuration
@EnableCaching
public class CacheConfig {

    @Bean
    public RedisCacheManager cacheManager(RedisConnectionFactory connectionFactory) {

        // 1. Define the default configuration (fallback)
        RedisCacheConfiguration defaultConfig = RedisCacheConfiguration.defaultCacheConfig()
                .entryTtl(Duration.ofMinutes(60)) // Default TTL is 1 hour
                .serializeValuesWith(RedisSerializationContext.SerializationPair.fromSerializer(new GenericJackson2JsonRedisSerializer()));

        // 2. Define specific TTLs for different caches
        Map<String, RedisCacheConfiguration> cacheConfigurations = new HashMap<>();

        // Highly volatile product cache: TTL 10 minutes
        cacheConfigurations.put("products", RedisCacheConfiguration.defaultCacheConfig()
                .entryTtl(Duration.ofMinutes(10))
                .serializeValuesWith(RedisSerializationContext.SerializationPair.fromSerializer(new GenericJackson2JsonRedisSerializer())));

        // Less volatile category cache: TTL 24 hours
        cacheConfigurations.put("categories", RedisCacheConfiguration.defaultCacheConfig()
                .entryTtl(Duration.ofHours(24))
                .serializeValuesWith(RedisSerializationContext.SerializationPair.fromSerializer(new GenericJackson2JsonRedisSerializer())));

        // 3. Build the CacheManager
        return RedisCacheManager.builder(connectionFactory)
                .cacheDefaults(defaultConfig)
                .withInitialCacheConfigurations(cacheConfigurations)
                .build();
    }
}

Now, when the ProductService (from Part 1) executes the @Cacheable(value = "products") annotation, Spring Data Redis automatically appends the EXPIRE command, setting the TTL to 10 minutes.

Step 3: Protecting the Shopping Carts

Because the shopping carts were managed manually using the RedisTemplate (not @Cacheable), Maya simply ensured she never called the .expire() method on cart keys.

// The cart key has no TTL. Under volatile-lru, it will NEVER be evicted.
// It is safe from the memory limit purge.
cartRedisTemplate.opsForValue().set("cart:user123", shoppingCart);

Debugging/Troubleshooting Tips

• The Eviction CPU Spike: When Redis hits maxmemory, every single write command forces Redis to pause, sample keys, and delete them before executing the write. If your application sends a massive burst of writes to a full cache, the CPU will spike as it scrambles to evict data fast enough, increasing latency. Solution: Monitor the evicted_keys metric in the INFO stats command. If it’s constantly high, your maxmemory is too low for your working set, or your TTLs are too long.
• The Lazy Expiration Trap: Redis does not actively scan the entire database every second to delete expired keys (that would burn CPU). It uses two methods:
  1. Passive: When you try to access a key, it checks the TTL and deletes it if expired.
  2. Active: A background task samples random keys with TTLs and deletes the expired ones. If you create millions of keys with short TTLs and never access them again, the active task might not keep up, and memory will remain high until maxmemory forces an eviction.
• Memory Fragmentation: Deleting many small keys can cause memory fragmentation, where the OS reports high memory usage, but Redis reports low usage. Use the INFO memory command and check the mem_fragmentation_ratio. If it’s high (>1.5), consider restarting the instance or using the MEMORY PURGE command (Redis 4.0+).

Key Takeaways

• Hard Limits: Always configure maxmemory to protect the OS from swapping or OOM kills, leaving 20-30% headroom for CoW spikes.
• Approximated LRU: Redis avoids the massive memory overhead of linked lists by using a probabilistic, clock-based sampling algorithm to approximate LRU behavior.
• Eviction Policies: Choose allkeys-lru for pure caches, or volatile-lru if you mix persistent data (no TTL) with ephemeral data (with TTL).
• Separation of Concerns: The ultimate best practice is to run separate Redis instances for cache (eviction enabled) and persistent state (eviction disabled).

Story Closing + Teaser

With volatile-lru configured and Spring Boot explicitly setting TTLs on the product cache, the memory graph stabilized. It hit 10GB and flattened out perfectly. Redis was seamlessly evicting the least recently viewed products to make room for new ones, while the shopping carts and the leaderboard remained safely untouched.

GlobalMart’s architecture was now fast, durable, and memory-efficient. However, it was still a single point of failure. The entire e-commerce platform relied on a single Redis instance (or a primary with a passive replica). If that single machine’s CPU maxed out, or its network interface saturated, the entire site would suffer.

Maya knew that true enterprise architecture requires horizontal scaling. She needed to distribute the load across multiple machines. She needed to explore the complexities of Master-Replica replication, the automatic failover of Redis Sentinel, and the decentralized hash-slot architecture of Redis Cluster. That journey into distributed systems awaited in the next chapter.

References

[1] Redis LRU Cache Documentation. https://redis.io/docs/latest/operate/oss_and_stack/management/optimization/memory-optimization/ [2] Spring Data Redis Caching. https://docs.spring.io/spring-data/redis/reference/redis/redis-cache.html