Redis Key Eviction Strategies and Approximated Implementations

Redis, being an in-memory data store, stores all its keys and values directly in RAM. While this offers unparalleled speed, it also introduces a critical challenge: limited memory. When the allocated RAM for Redis is exhausted, attempting to store new data can lead to Out-Of-Memory (OOM) errors, potentially crashing the Redis process. To prevent such catastrophic failures, Redis employs sophisticated eviction strategies.

The Necessity of Eviction

Imagine a scenario where your Redis instance has a maxmemory limit of 1GB. Once this limit is reached, any new SET operation would typically fail or cause an OOM error. Eviction mechanisms allow Redis to intelligently discard older or less important data to make space for new incoming writes, ensuring the database remains operational and responsive.

Redis allows you to configure a maxmemory parameter, typically in the redis.conf file. When this limit is hit, Redis will trigger its configured eviction strategy to free up space.

Redis Eviction Strategies Explained

Redis offers a variety of eviction policies, each suited for different use cases and access patterns. The choice of strategy significantly impacts cache hit rates and overall system performance.

1. No Eviction

• Policy: When the maxmemory limit is reached, Redis will not evict any keys. Instead, it will simply discard any incoming write operations (e.g., SET commands) that would exceed the memory limit. Read operations (e.g., GET) will continue to work normally for existing keys.
• Use Case: Suitable for scenarios where data integrity is paramount, and you prefer to drop new writes rather than risk losing existing data, or when Redis is used as a primary data store where eviction is not desired.

2. All Keys LRU (Least Recently Used)

• Policy: This strategy evicts the key that has not been accessed for the longest duration. The underlying assumption is that if a key hasn’t been used recently, it’s less likely to be used again soon.
• Implementation: Approximated LRU (Redis 3.0+)
  • Unlike a perfect LRU implementation (which typically requires a doubly linked list and significant memory overhead to track every access), Redis uses an approximated LRU algorithm.
  • Why Approximation? Maintaining an exact LRU would mean extra memory for pointers and data structures for every single key, which is inefficient for a high-performance cache like Redis. Redis prioritizes using memory for data storage rather than metadata management.
  • How it Works (Sampling): Instead of tracking all keys, Redis samples a small, configurable number of keys (e.g., N samples, each containing K keys). From this sample set, it identifies and evicts the key that is least recently used. By taking multiple samples, the chances of finding a good candidate for eviction (close to the actual LRU) are significantly increased.
  • This approach is highly memory-efficient and provides a decent approximation of true LRU behavior.

3. All Keys LFU (Least Frequently Used)

• Policy: This strategy evicts the key that has been accessed the fewest number of times. The idea is that if a key is rarely used, it’s a good candidate for eviction.
• Implementation: Approximated LFU (Redis 4.0+)
  • Similar to LRU, Redis uses an approximated LFU to avoid excessive memory overhead.
  • Why Approximation? Storing a full frequency count (e.g., a 4-byte integer for up to 1 million accesses) for every key would consume substantial memory. For instance, storing 1 million keys would require 4MB just for frequency counters.
  • Morris Counter: Redis employs a probabilistic data structure called a Morris Counter to approximate frequency counts. A Morris Counter uses significantly less memory (e.g., 2-3 bytes instead of 4) to represent large numbers (like 1 million), trading perfect accuracy for extreme space efficiency. This allows Redis to save valuable bytes per key, which can instead be used to store more actual data.
  • LFU Decay Mechanism: To prevent