The Key Eviction Sampling Algorithm: How Redis Really Chooses Under maxmemory

1. Why Redis does not maintain an exact LRU list

A classic, exact LRU implementation needs a doubly linked list where every access to an entry moves it to the end of the list, plus a hash map for fast lookup of each entry's list position. That structure delivers exact results, but costs extra memory per access for the linking as well as extra compute time for constantly reordering, even for plain read accesses that have nothing to do with the actual eviction process.

Redis deliberately forgoes this exact structure because the memory overhead would be substantial across millions of keys, especially in software whose central selling point is keeping memory usage per stored value as low as possible. Instead, Redis stores only a compact access metadata field per key, either a timestamp for LRU approximation or a counter for LFU approximation, directly inside the object header that already exists anyway, without any additional list structure.

2. How the sampling algorithm works in practice

When Redis needs to remove a key under maxmemory pressure, it randomly picks a configurable number of keys from the database, five by default. From this small sample, it determines the one key that best fits removal according to the active eviction policy: under an LRU policy, the key with the oldest stored access timestamp; under an LFU policy, the key with the lowest access counter. Exactly that one key is then actually removed.

If removing a single key is not enough to get back under the configured memory limit, Redis repeats the whole process: draw a new sample, determine the worst candidate, remove it, and check whether enough memory has been freed. This cycle continues until memory usage drops back below maxmemory, which under heavy write pressure can happen several times per incoming write command.

# Simplified sketch of the sampling algorithm (pseudocode)
def evict_one_key(db, policy, sample_size):
    candidates = db.random_sample(sample_size)
    if policy == "lru":
        worst = min(candidates, key=lambda k: k.last_access)
    elif policy == "lfu":
        worst = min(candidates, key=lambda k: k.access_counter)
    db.remove(worst)
    return worst

3. Why an approximation is good enough for the use case

At first glance, a random sample looks like a crude approximation that frequently picks the wrong key. In practice, however, the statistical quality of the approximation turns out to be surprisingly good even at small sample sizes, because eviction is not a one-off event but a repeated process: even if a single sample happens not to contain the globally oldest key, across many successive eviction cycles the process still statistically favors removing older keys over newer ones.

The key insight is that eviction rarely needs a perfect ranking, only a tendency: rarely used data should be more likely to go than frequently used data. For cache workloads, where what matters is a good ratio of hit rate to memory usage rather than a mathematically exact order, the approximated sampling approach delivers results in practice that are nearly identical to an exact implementation, at a fraction of the memory and compute cost.

4. maxmemory-samples: trading accuracy against CPU cost

The maxmemory-samples configuration option determines how many keys are drawn as candidates per eviction cycle. The default value of five represents a deliberate trade-off that offers a good balance between hit quality and compute cost for most workloads. A larger sample increases the probability of actually finding the genuinely least recently used key, but costs more CPU time per eviction cycle, since more candidates need to be examined and compared.

Under very high write load close to the maxmemory limit, this extra CPU cost from a large sample size can become noticeable, since eviction cycles then trigger very frequently. A sample size chosen too small saves CPU time but increases the risk that frequently used keys get removed by mistake, because the sample happens to contain only relatively recent candidates and the actually oldest key in the dataset never gets drawn at all.

# Check the current value
redis-cli CONFIG GET maxmemory-samples
# maxmemory-samples: 5

# Increase for higher accuracy (costs more CPU per eviction)
redis-cli CONFIG SET maxmemory-samples 10

# Set permanently in redis.conf
maxmemory-samples 10

5. Sampling under LRU policies compared to LFU policies

Under the LRU-based policies volatile-lru and allkeys-lru, sampling relies on a 24-bit timestamp that gets updated every time the key is accessed. Due to the limited bit width, this is already technically an approximation of the actual access time, on top of the sample-based approximation, but in practice it is entirely accurate enough for eviction decisions, since only the relative order within a sample matters, not the exact absolute time.

Under the LFU-based policies volatile-lfu and allkeys-lfu, instead of a timestamp, an 8-bit access counter is maintained that grows via a probabilistic increment algorithm and can also decay over time, controlled through the lfu-log-factor and lfu-decay-time parameters. The sampling principle itself stays identical to LRU: the key with the lowest counter value gets removed from the sample, only the underlying metric differs, frequency of access rather than recency.

6. Sampling scope: volatile- versus allkeys- policies

Another often overlooked aspect concerns the pool the sample is actually drawn from. Under the volatile variants of the policies, such as volatile-lru or volatile-lfu, Redis draws the random sample exclusively from keys that have a TTL set at all. Keys without an expiration time are fundamentally exempt from eviction in this mode, no matter how long they have gone unused.

Under the allkeys variants, on the other hand, the sample pool covers every key in the database, regardless of whether a TTL is set or not. This distinction has direct practical consequences for sample quality: in a database where only a small fraction of keys carry a TTL, the effective selection pool under volatile policies is correspondingly smaller, which increases the probability of repeatedly drawing similar keys into the sample compared to an allkeys policy on the same database.

7. Practical consequence for choosing the sample size

For the vast majority of production Redis installations, the default value of five is a sensible starting point that independent benchmarks already show reaches a hit quality close to an exact LRU implementation. Raising it to ten delivers a measurably better approximation at a moderately increased CPU cost and suits workloads where eviction accuracy takes higher priority than the last possible bit of CPU savings, for example a highly valuable, expensive-to-rebuild cache.

Reducing it below the default, on the other hand, only makes sense in rare cases, for example extremely CPU-constrained environments with a very high eviction frequency, where every saved millisecond counts and a somewhat less accurate eviction decision is acceptable. In a Magento context, where Redis often serves as a full page cache with many entries of varying value, a moderate increase to eight or ten is often a good compromise to less frequently and mistakenly remove especially valuable, expensive-to-recompute pages.

# Roughly estimate hit quality: watch the eviction counter
redis-cli INFO stats | grep evicted_keys

# After raising maxmemory-samples, compare again whether
# the ratio of cache hits to recomputations improves
redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"

8. Limits of the sampling approach

The sampling approach hits a practical limit when the database contains very few keys eligible for eviction at all, for example under volatile policies with only a handful of keys carrying a TTL. In that case, the sample inevitably approaches the total population, and the approximation effectively becomes an exact selection, since almost no random variance remains. For very large databases with millions of eligible keys, on the other hand, a certain amount of statistical noise persists even with a raised sample size.

It is also important that a larger sample size does not change the fundamental nature of the method: it remains an approximation, not an exact computation. Anyone who genuinely needs exact LRU eviction has to move to a different architecture, for example a custom, application-managed access structure, since Redis itself cannot offer that guarantee by design, regardless of how high maxmemory-samples is set.

9. Practical conclusion: treat sample size as a tuning knob, not an emergency fix

The sampling-based eviction algorithm is a deliberate design choice that lets Redis offer LRU- and LFU-like behavior with minimal memory overhead per key, instead of maintaining an exact but expensive data structure. For the vast majority of cache workloads, this approximation is practically indistinguishable from an exact implementation, as long as the sample size is not chosen unnecessarily small.

Anyone adjusting the sample size should treat it as a deliberate trade-off between hit quality and CPU cost and observe its effect through metrics such as evicted_keys and the ratio of keyspace_hits to keyspace_misses, rather than raising the value blindly. In most cases, the default value of five remains the right choice, and a moderate increase to eight or ten is the obvious next step whenever hit quality genuinely needs to improve measurably.

10. Summary

11. FAQ: Eviction Sampling