Eviction Strategies in Detail: LRU, LFU, Random

1. Why Redis approximates instead of evicting exactly

An exact eviction strategy would mean Redis maintains a sorted data structure for every single key that always keeps the least recently or least frequently used candidate at the top. With millions of keys, such a structure, for example a doubly linked list with a pointer per key, would cause significant additional memory cost and force an expensive resort on every access. Redis therefore deliberately forgoes exactness and implements every eviction strategy as a statistical approximation.

For comparison: an exact LRU list would need at least two extra pointers per key, typically 16 bytes on 64-bit systems. At a hundred million keys that adds up to 1.6 gigabytes of pure bookkeeping overhead, just to track the exact order of accesses, memory that could otherwise hold actual payload data.

This design decision is not a compromise born of convenience but a deliberate trade-off between memory overhead, CPU cost and practical hit quality. Studies and internal benchmarks from the Redis developers show that a well-configured approximated eviction strategy under realistic access patterns performs only marginally worse than an exact implementation, while requiring a fraction of the memory. Understanding the mechanics behind this approximation lets you tune the parameters to your own access pattern instead of relying on defaults.

The three eviction strategy families available in Redis, LRU, LFU and random, differ fundamentally in what metadata is maintained per key and how that metadata is used during selection. The following sections walk through each of these three mechanics down to the implementation level, because only that understanding explains why an eviction strategy works well for one workload and disappoints for the next.

Another reason for the deliberate approximation lies in the architecture of the event loop: Redis processes commands fundamentally single-threaded, so any extra compute time for a more complex eviction strategy directly raises the latency of every other waiting client. A strategy that is theoretically optimal but practically too expensive hurts overall performance more than it saves through better eviction decisions.

2. The LRU sampling algorithm in detail

The approximated LRU eviction strategy works with a candidate pool of fixed size, controlled via maxmemory-samples. On every eviction, Redis draws as many random keys as configured in maxmemory-samples, compares their idle time and removes the candidate with the longest inactivity from this small sample. Since Redis 3.0, a persistent pool is additionally maintained across multiple eviction rounds: instead of starting from scratch each round, good candidates from previous samples are kept in the pool and compared against new samples. This significantly improves the approximation to true LRU without needing to increase the sample size.

The pool mechanism works as follows: on every eviction, new random keys are drawn and compared against the candidates already in the pool, which are sorted by idle time. The worst candidates fall out of the pool, the best ones remain for the next round. This eviction strategy therefore converges toward true LRU behavior over multiple eviction cycles, even though only a small sample is considered per individual round. With a sample of 5, Redis reaches, according to its own benchmarks, a hit quality that is only a few percentage points below exact LRU.

The pool size itself is internally capped at 16 entries and cannot be tuned through its own configuration option, it is a fixed implementation detail of the eviction strategy. That means even with a very high maxmemory-samples value, no more than 16 candidates are ever held in the pool at once, which keeps the memory overhead of this optimization constant and negligible regardless of sample size.

# redis.conf: sampling parameters of the eviction strategy
maxmemory-policy allkeys-lru
maxmemory-samples 5

# Higher sample size increases accuracy of the eviction strategy,
# but costs more CPU per eviction decision
redis-cli CONFIG SET maxmemory-samples 10

# Approximation vs. exact LRU (internal Redis benchmarks, rough figures):
# samples=3  → about 92% match with exact LRU
# samples=5  → about 96% match (default)
# samples=10 → about 99% match
#
# Rule of thumb: raise samples only in small increments and
# observe at least one representative load period each time

3. The idle time timestamp: how "last used" is stored

Every Redis object header contains a 24-bit field that is interpreted either as an LRU timestamp or as an LFU counter, depending on the active eviction strategy. In LRU mode, this field stores a minute-precision time relative to an internal reference point that is periodically updated to avoid bit overflow. On every read or write access to a key, Redis updates this field to the current time, which practically costs nothing extra because no separate data structure access is required.

The OBJECT IDLETIME command exposes this internal timestamp for diagnostic purposes and returns the number of seconds since the last access. This metric is especially valuable for checking, before switching the eviction strategy, which keys have actually been inactive for a long time. Important: OBJECT IDLETIME only works as long as no LFU policy is active, because the field is otherwise interpreted as a frequency counter and no longer contains meaningful time information.

Because the resolution is minute-precision rather than second-precision, the field is not suited for high-precision latency measurements, only for a rough classification of whether a key has been inactive for minutes, hours or days. For the eviction strategy this granularity is entirely sufficient, because what matters is the relative ordering of candidates within the sample, not the exact second-level difference between them.

# Check idle time of individual keys before switching policy
redis-cli OBJECT IDLETIME session:user:8842
# (integer) 340

redis-cli OBJECT IDLETIME product:catalog:1123
# (integer) 4

# Only valid as long as no LFU policy is active
redis-cli CONFIG GET maxmemory-policy

4. The LFU counter: probabilistic growth instead of linear counting

For the LFU eviction strategy, Redis reuses the same 24-bit field but interprets the upper 8 bits as a probabilistic counter following the Morris counter principle. A linear 8-bit counter would saturate at 255 and could no longer distinguish extremely popular keys from moderately popular ones. The probabilistic approach solves this problem: the probability that an access actually increments the counter decreases with the current counter value according to a logarithmic formula, controlled via lfu-log-factor.

Concretely, this means that at a low counter value, almost every access increments it, while at a high counter value only a small fraction of accesses still increment it further. As a result, the 8-bit counter can effectively represent access counts in the millions without overflowing. This eviction strategy is therefore memory-neutral compared to LRU, since no additional byte per key is needed, but it delivers a qualitatively different signal: frequency over the entire lifetime of the key instead of just the most recent access time.

# redis.conf: fine-tuning LFU counter behavior
maxmemory-policy allkeys-lfu
lfu-log-factor 10    # higher = slower counter growth at high values

# Check the LFU counter of a key (0-255)
redis-cli OBJECT FREQ product:catalog:8842
# (integer) 189

# lfu-log-factor reference table (approximate accesses until counter=255):
# factor=0  → about 100,000 accesses
# factor=10 → about 1,000,000,000 accesses (default)
# factor=100 → several orders of magnitude more, very coarse resolution below

5. LFU decay: how old popularity fades away

Without a countermeasure, a key that was once extremely popular would keep its high counter value permanently, even if it is no longer requested at all. This exact problem is solved by the decay mechanism, a fixed part of the LFU eviction strategy. Through the lfu-decay-time parameter, Redis defines how many minutes of inactivity are needed before a key's counter is reduced by one point on the next access, before the regular counting logic kicks in.

Decay is applied lazily: Redis does not run a background process that periodically lowers all counters, but instead computes, on the next access to a key, how much time has passed since the last access, and reduces the counter proportionally before the actual access is counted. An lfu-decay-time of 1 (the default) means the counter drops by one point per minute of inactivity. A value of 0 disables decay entirely, which can make sense for very stable access patterns without seasonal fluctuations, but in most cases leads to an eviction strategy that overvalues old popularity.

For seasonal workloads, such as a shop with a pronounced holiday season, a moderate decay value matters especially, because otherwise the same product keys that dominated in December would still be considered popular in January, even though the actual access pattern has long since shifted. An overly aggressive decay value, on the other hand, makes the eviction strategy react too strongly to short-term fluctuations, approaching the effect of pure LRU again.

6. Random eviction: when uniform distribution is genuinely enough

Random as an eviction strategy sounds like giving up on any intelligence, but it is in certain, clearly definable situations actually the most efficient choice. When access probability is roughly evenly distributed across all keys, for example a large cache for evenly polled sensor data or randomly distributed hashes with no discernible popularity pattern, LRU or LFU statistically deliver no better result than a random selection. The reason: both strategies try to detect and exploit a pattern in access behavior. If no pattern exists, there is nothing to detect, and the extra sampling effort of LRU or LFU becomes pure waste.

In practice, random as an eviction strategy pays off especially at very high write throughput, when even the small CPU overhead of LRU sampling contributes noticeably to overall load. A benchmarking approach for the decision: run redis-cli --intrinsic-latency before and after switching the policy and compare the hit rate over a representative period. If no measurable difference in hit rate shows up between allkeys-lru and allkeys-random, switch to the simpler and cheaper eviction strategy.

Another argument for random arises with very small objects of nearly identical size, such as counters or flags, where the value of a single key rarely differs much from its neighbors anyway. In such cases, the potential hit-rate gain from LRU or LFU is usually too small to justify the extra sampling effort, especially when thousands of these keys need to be evicted per second.

# Enable random eviction and compare against LRU
redis-cli CONFIG SET maxmemory-policy allkeys-random
redis-cli --intrinsic-latency 5

redis-cli CONFIG SET maxmemory-policy allkeys-lru
redis-cli --intrinsic-latency 5

# Compare hit rates of both variants via INFO stats
redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"

7. Sampling pool size: CPU cost against accuracy

The choice of maxmemory-samples is the central lever for trading accuracy of the LRU or LFU eviction strategy against CPU consumption. Every increase of the sample size means more random accesses to the internal hash table per eviction decision, which contributes noticeably to CPU load at high eviction rates. The default value of 5 is a good compromise for most workloads, because the persistent pool mechanism from section 2 already closes most of the accuracy gap to exact LRU.

For workloads with especially high eviction pressure, for example caches that constantly operate at their memory limit and evict thousands of keys per second, a lower sample size can reduce CPU load without noticeably degrading hit rate, because the pool converges over many rounds anyway. For workloads with rare but especially consequential eviction decisions, for example small, high-value caches, a higher sample size pays off, because total CPU cost stays low while the accuracy of the eviction strategy improves noticeably.

A rule of thumb that has proven useful in practice is to raise the value gradually in small increments and wait through at least one representative load period after each change before making the next adjustment. Jumping, for example, from 5 to 50 in one step makes it hard to attribute the observed effect to the changed sample size versus natural fluctuations in the access pattern.

8. Eviction strategy under cluster conditions

In a Redis cluster, the eviction strategy runs independently per shard. Each node only knows its own memory consumption and the idle times or LFU counters of its own keys, there is no cluster-wide coordination of eviction. This has an important practical consequence: with uneven distribution of hot keys across shards, one node can experience heavy eviction pressure while another node in the same cluster still has plenty of free memory.

This characteristic makes hash-tag-based key distribution and regular monitoring of per-shard memory usage a prerequisite for a functioning eviction strategy in cluster operation. If one shard is consistently loaded more heavily than the others, adjusting maxmemory-samples or lfu-decay-time will not help, only a better distribution of keys or resharding will. Cluster metrics should therefore always be evaluated per node, not only aggregated across the whole cluster.

An additional effect in cluster operation: since each node draws its own sampling population from a smaller key space than a comparable standalone instance holding the same total dataset, the statistical accuracy of the LRU approximation can vary slightly per shard. For very small shards with only a few thousand keys, it is therefore worth testing a higher maxmemory-samples value to compensate for the smaller population.

9. Measuring and tuning: IDLETIME, FREQ and evicted_keys

A single glance at evicted_keys is not enough to objectively evaluate the effectiveness of an eviction strategy. It is more useful to combine eviction rate, hit rate and a spot check on whether the right keys are actually being evicted. OBJECT IDLETIME and OBJECT FREQ enable exactly this spot check: if keys with low idle time or a high frequency counter are regularly being evicted, that points to a problem with the sample size or the policy choice.

A practical diagnostic workflow: before switching the eviction strategy, draw a sample of 50 to 100 keys and log their IDLETIME or FREQ. After the switch, draw the same sample again and compare the distribution. Additionally, capture INFO stats before and after the change to have evicted_keys, keyspace_hits and keyspace_misses for direct comparison. This combination of spot check and aggregate metric provides a much more solid basis than gut feeling alone.

An often overlooked last step: the sample should not be drawn arbitrarily, but deliberately across different key prefixes, because different data categories within the same instance, for example product data versus session data, can show completely different access patterns. A single aggregated hit rate across the whole instance can mask opposing effects between categories.

# Sample-based diagnosis of the active eviction strategy
redis-cli --scan --pattern "product:*" | head -50 | while read -r key; do
  echo "$key: $(redis-cli OBJECT FREQ "$key" 2>/dev/null || redis-cli OBJECT IDLETIME "$key")"
done

# Separate samples per key prefix for differentiated evaluation
for prefix in "product:" "session:" "cart:"; do
  echo "=== $prefix ==="
  redis-cli --scan --pattern "${prefix}*" | head -20 | while read -r key; do
    redis-cli OBJECT FREQ "$key" 2>/dev/null
  done
done

# Capture aggregate comparison metrics
redis-cli INFO stats > before.txt
redis-cli CONFIG SET maxmemory-policy allkeys-lfu
sleep 3600
redis-cli INFO stats > after.txt
diff before.txt after.txt | grep -E "evicted_keys|keyspace_"

10. Summary

Every eviction strategy in Redis is a deliberately approximated, not an exact, implementation, in order to keep memory overhead and CPU cost within bounds. Approximated LRU uses a persistent sampling pool that converges toward true LRU behavior over multiple rounds. LFU uses a probabilistic 8-bit counter with logarithmic growth and time-based decay to represent frequency without overflowing. Random forgoes metadata entirely and has the advantage exactly where no exploitable access pattern exists anyway.

The parameters maxmemory-samples, lfu-log-factor and lfu-decay-time allow fine tuning of every eviction strategy to your own access pattern, but they should be set based on data, not gut feeling. OBJECT IDLETIME and OBJECT FREQ provide the transparency needed to check whether the active eviction strategy is actually evicting the right keys. In cluster operation, this check must happen per shard, because eviction is never coordinated cluster-wide.

In the end, choosing the right eviction strategy is not a one-time decision but an ongoing comparison between the theoretical model and actual access behavior, which can shift over time. Regular sampling and a fixed monitoring interval prevent a once-suitable configuration from silently turning into a misconfiguration.

11. FAQ: Eviction Strategies in Redis