allkeys-lru vs allkeys-lfu for high-churn workloads

Question

Eviction Policy Trade-offs
When Redis reaches its maxmemory limit, the choice of eviction policy determines which data is purged to accommodate new writes. For workloads where memory is the primary binding constraint, two primary documented approaches exist for the entire keyspace: allkeys-lru and allkeys-lfu.

Recency vs Frequency
The allkeys-lru policy is designed for patterns where the most recently accessed data is the most likely to be reused. Conversely, allkeys-lfu (introduced in Redis 4.0) targets workloads with a stable "hot set" that must be protected from being flushed by a sudden burst of one-off keys that would otherwise appear "recent" to an LRU algorithm.

Sampling and CPU Overhead
Redis implements these policies approximately by sampling a subset of keys defined by maxmemory-samples. Increasing this value improves the accuracy of the eviction candidate but increases CPU utilization during write operations under memory pressure.

Given a workload with a mix of long-term hot keys and high-frequency short-lived keys:

How should the lfu-decay-time be calibrated to prevent legacy hot keys from blocking new high-frequency data?
  At what threshold does the CPU cost of increasing maxmemory-samples outweigh the gain in cache hit ratio?

Tasadduq Burney · Answer

Answer
For a workload that mixes long‑term hot keys with a burst of short‑lived, high‑frequency keys, the eviction policy that best protects the hot set while admitting the new traffic is allkeys‑lfu (available from Redis 4.0).
Calibrating lfu‑decay‑time
The LFU counter ages according to lfu‑decay‑time. To let legacy hot keys yield to new high‑frequency entries, set the decay time so that a key’s counter drops significantly during its typical idle period.

Measure or estimate the average idle duration of your legacy hot keys (the time between two successive accesses when the key is not being used).
  Choose lfu‑decay‑time ≈ ½ × that idle duration. For example, if hot keys are idle for about 2 minutes, start with 60 seconds.
  Deploy the setting, then monitor INFO fields keyspace_hits, keyspace_misses and evicted_keys. If the hit ratio for new traffic rises without a noticeable increase in misses for the hot set, the decay time is appropriate.
  If hot keys are being evicted too quickly, increase the decay time; if they persist and block new entries, decrease it further.

Missing diagnostic detail: What is the typical idle period of your legacy hot keys? Knowing this lets you pick a decay time that matches the workload; without it you may over‑ or under‑age the counters.
Setting maxmemory‑samples
Redis approximates LRU/LFU by sampling maxmemory‑samples keys on each write that triggers eviction. Accuracy improves with more samples, but each extra sample adds CPU work.

Begin with the default maxmemory‑samples 10.
  Run a short benchmark (e.g., redis‑benchmark -t set,get) that reproduces your churn rate and record the hit ratio and CPU usage (used_cpu_sys + used_cpu_user from INFO).
  Increase the sample count in steps of 5 (10 → 15 → 20) and repeat the benchmark.
  Plot hit ratio versus CPU %; the point where the hit‑ratio curve flattens while CPU continues to rise marks the practical threshold. In most community‑edition workloads this occurs around 10‑15 samples.
  If your CPU budget is tight, stay at the lowest sample count that still yields an acceptable hit ratio (often 5‑10). If you have spare CPU and need the highest possible hit ratio, you can go up to 15‑20, but expect diminishing returns beyond that.

These steps give you a concrete, repeatable way to tune both parameters without guesswork.

allkeys-lru vs allkeys-lfu for high-churn workloads

Eviction Policy Trade-offs

Recency vs Frequency

Sampling and CPU Overhead

1 answer

Answer

Calibrating lfu‑decay‑time

Setting maxmemory‑samples

Your perspective belongs here.

0 question comments