Cache eviction
How a full cache picks the entry to drop: the one idle longest (LRU), the one hit least (LFU), the one expiring soonest, or one at random. Each policy bets on an access pattern; a strong answer names the bet.
What it is
Eviction is what a cache does when it has reached its memory limit and a new entry needs room: it chooses an existing entry and drops it. That's a different event from expiry, where an entry's lifetime runs out, whether to bound how stale it may get or to clear data no one needs anymore (see Cache invalidation and TTLs). Expiry is driven by time; eviction is driven by capacity, and the policy that picks the victim decides how much of the cache's hit rate survives being full.
The ideal policy, Bélády's algorithm, drops the entry whose next use is farthest in the future. It needs knowledge of future requests, which a general-purpose system doesn't have, so recency- and frequency-based policies predict reuse from past accesses instead, while random, FIFO and expiry-based replacement don't try to predict reuse at all. Recency-based policies (LRU and its relatives 2Q and LRU/K) bet that a recently used entry will be used again soon. Frequency-based policies (LFU) count how often an entry is needed and drop the rarely needed ones first. Adaptive policies such as ARC shift between the two as the workload changes.
| Policy | Drops | Bets that | Breaks when |
|---|---|---|---|
LRU | The entry unused for the longest time | Recent use predicts reuse | A scan touches many entries once and flushes the working set |
LFU | The entry with the lowest hit count | Past popularity predicts reuse | Popularity shifts and old favorites hold their counts; a decay is needed |
FIFO | The oldest inserted entry | Insertion order predicts reuse | A long-lived hot entry is dropped on schedule |
Random | Any entry | Nothing; no tracking cost | A hot entry is as likely to go as a cold one |
Nearest expiry | The entry whose TTL ends soonest | Short TTLs mark less valuable data | Entries without a TTL can't be chosen |
Adaptive (ARC, W-TinyLFU) | Decided by recency and frequency together | The mix changes over time | More metadata and more code to reason about |
How Redis does it. The current Redis Open Source documentation describes its LRU as an approximation: on each eviction it samples a small number of keys at random and drops the one idle longest, and since Redis 3.0 it keeps a pool of good candidates between evictions, which brings the result close to exact LRU. The sample count is the maxmemory-samples setting; the documentation shows it at 5 and says raising it to 10 approximates true LRU more closely at some extra CPU. Exact LRU would cost extra memory per key, which is why it approximates. Redis 4.0 added LFU, implemented as a Morris counter, a probabilistic counter that fits in a few bits per key, paired with a decay period so a key that was popular last week stops counting as popular. The defaults lfu-log-factor 10 and lfu-decay-time 1 saturate the counter near a million hits and decay it once a minute.
How Memcached does it. Memcached carves memory into slab classes by item size, and each class has its own LRU; a page assigned to a class stays there, so the server behaves like many small caches. When a class has no free chunk and no free page can be assigned to it, it checks the last few items at the tail of that LRU for one that has already expired and reuses it, and evicts a live item when none has. Its segmented LRU splits each list into HOT, WARM and COLD: new items enter HOT and are not bumped there; an item counts as active after two hits; active items move to WARM, inactive ones to COLD, and evictions come from the tail of COLD. The stated goal is to protect active items from a scan: an item read once drifts from HOT through COLD and out without displacing anything in WARM.
Admission, not just eviction. Caffeine uses Window TinyLFU: a frequency sketch estimates how much each entry has been used in the past, and TinyLFU uses that estimate to decide whether a new entry deserves a place in the main space at all. A small window ahead of the main space holds entries that show recency bursts, which the frequency test would otherwise reject, and the split between window and main space is tuned by a hill-climbing search. The sketch is a 4-bit count-min sketch costing about 8 bytes per entry, and the policy keeps no record of evicted keys, which ARC and LIRS do.
When to use it
LRU by default, when a small share of the keys gets most of the reads. allkeys-lru fits that shape and is a sound choice when nothing argues for another policy. The allkeys-* variants also cost less memory than the volatile-* ones, since they don't need an expire value on each key.
LFU with decay when the hot set is stable and something periodically reads a lot of cold data: a nightly export, a crawler, a backfill. Under LRU that pass refreshes each key it touches and pushes the hot set out; under LFU the scanned keys carry a low frequency estimate, so the sampling favors them as victims and the hot set tends to stay. The decay matters because without it a key that was hot last month keeps its count and stays. Memcached's segmented LRU gets a similar effect from a different mechanism, since an item needs a second hit before it moves into the protected WARM segment.
volatile-* policies when one Redis instance holds both cache entries and keys you must keep: give the cache entries a TTL and just those become candidates. If no key carries an expire, these policies behave like noeviction, so a cache that forgets to set TTLs will start refusing writes. volatile-ttl fits when the TTL you set already encodes how much a key is worth.
When not to
Keep noeviction when the instance holds data you can't recompute: sessions, rate-limit counters, a work queue. Under this policy Redis stops saving new values at the memory limit and answers commands that would need more memory with an error instead of dropping a key. A loud failed write beats a silently dropped session. Our advice: put such data on its own instance and let the cache instance evict freely.
Skip the tracking when access is close to uniform or the cache is small: random or FIFO replacement costs nothing per hit, and recency metadata buys little when no key is much hotter than another. Redis approximates LRU rather than track it exactly because the exact version costs memory; a tiny in-process cache can take that reasoning one step further.
Don't tune the policy when the cache is simply too small. A cache that evicts on most writes is often below its working set (unless those writes are one-use items), and a smarter policy may claw back some hit rate or none at all, depending on how much reuse the traffic has. Size the memory limit from the working set first, then pick the policy. And eviction is not a fix for stale data: under LRU or LFU a wrong value that is read often tends to stay. That problem belongs to invalidation and TTLs, not to the eviction policy.
Compared
| Policy | Per-entry cost | Choose it when | The simpler option wins when |
|---|---|---|---|
LRU (approximated) | A last-access timestamp; Redis samples instead of keeping a list | A small subset of keys is much hotter than the rest | Access is uniform: random replacement does as well with no bookkeeping |
LFU with decay | A few bits of counter plus a decay clock | Scans or batch reads would otherwise flush the hot set | The hot set changes faster than the decay follows: LRU adapts in one pass |
Segmented LRU (Memcached) | Two activity bits; items bumped in the background | Many reads, scan protection, and low lock contention matter | A single small LRU is enough and the extra segments are hard to reason about |
Admission filter (W-TinyLFU) | A frequency sketch, about 8 bytes per entry in Caffeine | You want near-optimal hit rate from an in-process cache | The cache is a shared server whose policy you pick from a list, not implement |
Nearest expiry | Nothing beyond the TTL already stored | Your TTLs already rank how valuable each key is | Keys have no TTL: nothing qualifies and writes fail |
No eviction | None | Losing a key silently is worse than a failed write | The data is a pure cache and a refused write just adds latency |
In a picture
How to say it in an interview
The common mistake
Quiz
Questions that use this
Related
Sources
- Redis Open Source documentation: Key eviction
- Redis source: sample redis.conf (unstable branch), memory management section
- redis-doc: Key eviction (reference/eviction/index.md)
- Memcached wiki: UserInternals
- Memcached source: doc/new_lru.txt
- Memcached blog: Replacing the cache replacement algorithm in memcached (modern LRU)
- Caffeine wiki: Efficiency
- Wikipedia: Cache replacement policies