Cache eviction policies

An eviction policy decides which entry a full cache throws away to make room for a new one. Memory is bounded, so every cache needs one, and the choice matters: in the simulation later on this page, with the same memory and the same requests, the best policy served about 18% more reads from cache than LRU did. The classics are FIFO, LRU and LFU; modern caches add an admission filter so that keys read only once never push out the ones read all day.

Picture it first: the reserve shelf

A college library keeps a reserve shelf by the issue desk with room for 30 books. Fetching a book from the third-floor stacks takes ten minutes; from the shelf, ten seconds. When the shelf is full and a student asks for a book from upstairs, one shelf book must go back. The one shelved longest ago (FIFO)? The one untouched for longest (LRU)? The one borrowed least often this term (LFU)?

In exam week, one student works through a reading list of 40 books, each read once. A librarian who always shelves the latest request fills the shelf with that list and sends the popular textbooks upstairs. A wiser librarian keeps a register of every request, even for books not on the shelf, and shelves a newcomer only if it has been asked for more often than the book it would replace.

Map it back: the shelf is the cache, the stacks the database, sending a book upstairs an eviction, the reading list a scan, and the register the frequency sketch or ghost list behind an admission policy.

Why caches evict, and how that differs from expiry

Once a cache is full, every miss that stores a new entry must push one out. Those are capacity misses, the kind a better policy or more memory reduces (the other kinds are in Caching 101).

The perfect policy exists on paper: Bélády’s MIN evicts the entry whose next use is farthest in the future. It needs the future, so it is only the ceiling in simulations; Caffeine’s benchmarks plot every policy against it. Real policies guess from two signals: recency (read recently, so likely soon) and frequency (read often, so likely again).

Every policy answers two questions: eviction (which resident leaves?) and admission (does the newcomer deserve a slot at all?). Classic policies always admit. The newer ones win mostly by saying no.

Expiry is not eviction

A TTL removes an entry because it may be stale: correctness. Eviction removes a valid entry because space ran out: capacity. A TTL caps an entry’s life; it does not reserve memory. Cloudflare documents the same split for its CDN: freshness is the TTL you configure, while retention depends on popularity and cache size, uses LRU, and is not configurable.

Expired entries don’t vanish on their own, and they count against memory until reclaimed. Redis reclaims them two ways:

• Lazily: a read that finds an expired key deletes it and returns a miss.
• Actively: a background cycle samples keys with a TTL and deletes expired ones, aiming by default to leave no more than about 10% of keys expired but unreclaimed.

Memcached uses a background LRU crawler for the same job. When the hit ratio is low, Redis’s INFO tells you which problem you have: many evicted_keys point at capacity or policy, many expired_keys at TTLs that are too short.

The classic four: FIFO, random, LRU and LFU

FIFO and random

FIFO evicts the oldest insert. A hit changes nothing, so reads never write shared state, which makes FIFO cheap and easy to run lock-free; but it evicts a key read a second ago just because it arrived early. Random needs no ordering at all and behaves much like FIFO: 46.4% against FIFO’s 46.5% in this page’s simulation. It shines in one odd case, loops.

LRU: the default

LRU bets that what was read recently will be read again soon. To make both get and put O(1), combine two structures:

• a hash map from key to list node, for O(1) lookup;
• a doubly linked list in recency order. A hit unlinks the node and relinks it at the front; an eviction removes the node at the back. Each node knows its neighbours, so both are O(1).

Here is the same structure in Python. Interviewers usually want this version rather than a built-in ordered dictionary; sentinel nodes at both ends remove the empty-list special cases.

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                           # key -> Node
        self.head, self.tail = Node(), Node()   # sentinels: head.next is MRU, tail.prev is LRU
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None                         # miss
        self._unlink(node)
        self._push_front(node)                  # now the most recently used
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.map) == self.capacity:
                lru = self.tail.prev            # least recently used
                self._unlink(lru)
                del self.map[lru.key]
            node = Node(key, value)
            self.map[key] = node
        self._push_front(node)

You pay two pointers per entry, which matters when values are tiny, and a write to a shared list on every hit. Memcached’s original LRU moved an item at most once every 60 seconds to limit that locking, and still found scaling beyond 8 worker threads difficult.

MRU is LRU’s mirror image: it evicts the most recently used entry. That sounds perverse, but it is the right answer for loops, as you’ll see shortly.

LFU: counting instead of remembering

LFU keeps a use count per entry and evicts the smallest. If popularity were fixed and every request independent, LFU would be the best online policy (the ARC paper cites the proofs). A naive LFU needs a heap, so O(log n) per access, but an O(1) design exists: buckets of keys per count, each an LRU list, so a hit moves a key to the next bucket. Three problems remain:

• Old popularity never fades. Yesterday’s IPL highlight keeps a count in the millions and squats in the cache. You need aging: halve all counts now and then, or decay them with time as Redis does.
• Newcomers are born doomed. A new key starts at count 1, the first thing evicted. Redis starts new keys at 5 so they get a chance.
• Counts die with eviction. An LFU that only counts resident keys forgets everything about keys it just dropped. Remembering all keys is expensive, which is why TinyLFU uses a compact sketch.

A worked trace

Run one short sequence through FIFO, LRU and LFU with room for three keys. LFU breaks ties by evicting the less recently used key.

LRU beats FIFO at step 7 because it kept A when D arrived. LFU pulls ahead at step 8: for E, LRU evicts B (last read at step 5) while LFU evicts D, read only once. B and A then hit at steps 9 and 11, so LFU finishes with 6 hits to LRU’s 4 and FIFO’s 3.

Flip the workload and the ranking flips. If requests after step 12 moved to C, D, E and F for good, LFU would cling to A and B on their old counts while LRU adapted within three misses. That is the recency-versus-frequency trade-off in miniature.

Where LRU breaks: scans, loops and one-hit wonders

Scans

A scan reads many keys once each: a nightly export, a search-engine crawler, a cache warm-up script, a report over every order this month. Under LRU each scanned key enters at the front, and a scan longer than the cache pushes every hot key out. A policy is scan-resistant if one-time reads pass through without flushing entries that are used repeatedly; the ARC paper uses that definition.

PostgreSQL shows the practical fix. A large sequential scan does not use the normal replacement path; it borrows a private 256 KB ring of buffers and recycles it, so reading a huge table can’t flush the shared buffer cache.

Loops

A loop reads the same N keys in order, again and again, with a cache smaller than N: a report that walks 1,000 rows every run with room for 900. LRU always evicts exactly the key that is needed next, so it never hits. Simulating that loop for 200 passes gives LRU 0%, FIFO 0%, random 81%, MRU 90% hits. MRU wins because it keeps 899 rows fixed and churns one slot. That is why the Redis docs suggest allkeys-random for keys read in a repeating cycle.

One-hit wonders

Most keys that enter a cache are never read again before they leave. The S3-FIFO study measured this on 6,594 production traces: across a whole trace the median share of keys requested only once was 26%, but in a stretch covering 10% of the unique keys, roughly what a cache of that size sees between evictions, it was 72%. LRU gives each of those keys a full ride from front to back, using space a reused key could have had. The fix is quick demotion: let newcomers prove themselves in a small area first.

Recency or frequency?

A news feed or live IPL scores reward recency: what’s hot now is cold in hours. A sale catalogue, static assets and user profiles reward frequency: the same items stay popular for days. Most real traces mix both, which is why the policies below track both.

CLOCK, SLRU, 2Q, ARC and LIRS

CLOCK, or second chance

Put entries in a circle, each with a reference bit. A hit just sets the bit. To evict, a “hand” sweeps the circle: an entry with its bit set gets the bit cleared and a second chance; the first entry found with a clear bit is evicted. Nothing moves on a hit, so there is no list to lock. It approximates LRU cheaply, and operating systems use variants of it for page replacement.

PostgreSQL’s buffer pool uses a clock sweep with a small counter instead of a bit: each use increments a buffer’s usage count up to 5, and the passing hand decrements it, so a page must go unused for several sweeps before it can be replaced.

SLRU

Segmented LRU splits the cache into a probation segment and a protected segment, each an LRU list. New keys enter probation; a second hit promotes a key to protected; when protected overflows, its oldest key drops back into probation rather than out of the cache. Scanned keys never get a second hit, so they only churn probation.

2Q

2Q puts first-time keys in a small FIFO queue, A1in. When they fall out, only their key is remembered in a ghost queue, A1out; a key requested again while in A1out goes into the main LRU, Am. It is O(1), but leaves two sizes to tune, and the ARC paper shows the best values depend on the workload.

ARC

ARC (Megiddo and Modha, 2003) keeps two LRU lists: T1 for keys seen once recently and T2 for keys seen at least twice. It also keeps two ghost lists, B1 and B2, holding only the keys recently evicted from each, so it tracks twice as many keys as it caches. A hit in B1 means “I evicted a recent key too soon”, so ARC grows T1’s target size; a hit in B2 grows T2’s. The split tunes itself to the workload, every operation is O(1), and a scan only churns T1.

On the paper’s SPC1-like benchmark, which mixes long sequential scans with random reads, a 4 GB cache reached 9.19% hits under LRU and 20.00% under ARC. The catch is legal rather than technical: as Caffeine’s documentation notes, ARC is patented by IBM.

LIRS

LIRS protects blocks reused at short intervals, measured as the number of distinct keys touched between a block’s last two accesses. It handles loops well, but it is complex and keeps history for keys no longer cached.

Admission first: TinyLFU, W-TinyLFU and S3-FIFO

TinyLFU

TinyLFU (Einziger, Friedman and Manes) adds a gate in front of any cache. When a new key would evict a victim, compare their estimated frequencies and admit the newcomer only if it is more popular; otherwise drop the newcomer. That needs a frequency for every recently seen key, including keys not in the cache, so TinyLFU stores approximate counts in a count-min-style sketch:

• Small counters: Caffeine’s sketch uses 4-bit counters and costs about 8 bytes per cache entry overall.
• Aging by reset: after W additions (the sample size), every counter is halved, so old popularity fades.
• A doorkeeper: a Bloom filter absorbs first-time keys, so one-hit wonders never take counter space.

W-TinyLFU

Pure TinyLFU rejects bursts: a key that suddenly gets hot has no history yet and loses every comparison. W-TinyLFU, Caffeine’s policy, fixes that with a small window LRU that admits everyone; only the window’s victims face the filter. The main area is an SLRU, 80% protected and 20% probation, and the candidate fights the probation victim. The paper started with a 1% window; Caffeine now sizes the window with hill climbing, growing it when recency pays and shrinking it when frequency does.

S3-FIFO

S3-FIFO (Yang et al., SOSP 2023) gets the same effect from three plain FIFO queues:

• S, a small queue with 10% of the space, takes new keys.
• M, the main queue, has the other 90%.
• G, a ghost queue, stores only keys, as many as M holds.

A hit increments a 2-bit counter capped at 3, and nothing moves. When S is full, its oldest key moves to M if it was hit at least twice while in S; otherwise it is evicted and its key goes to G. A miss on a key found in G goes straight to M. When M is full, its oldest key is reinserted with its counter reduced by one if the counter is above zero, and evicted otherwise.

Across 14 trace collections it had the lowest mean miss ratio on 10. Because a hit touches only two bits, its prototype in CacheLib delivered 6× the throughput of an optimised LRU at 16 threads.

Policies side by side

In practice: on the JVM, Caffeine gives you W-TinyLFU for free; with many threads or flash storage, FIFO-family designs (CLOCK, S3-FIFO) avoid a lock on every hit; in Redis, pick a maxmemory-policy from the next section.

Eviction in Redis, Memcached and CDNs

Redis at maxmemory

Redis has no memory limit by default on 64-bit systems (maxmemory 0), and the default policy is noeviction. With a limit set, Redis evicts under the chosen policy whenever a command adds data and usage is over the limit; one very large write can overshoot it briefly. Replication and AOF buffers don’t count towards the limit, so leave headroom below physical RAM.

The current docs list ten policies: noeviction; allkeys- or volatile- followed by lru, lfu, lrm or random; and volatile-ttl. The volatile- versions only consider keys that have a TTL. LRM, added in Redis 8.6, ranks keys by their last write and ignores reads.

How Redis approximates LRU

A linked list would cost two pointers per key, so Redis doesn’t keep one. Each object has a 24-bit field holding a coarse last-access clock. To evict, Redis samples maxmemory-samples random keys (default 5), feeds them into a pool of the best 16 candidates kept across evictions, and evicts the best one in the pool.

The approximation is good because a bad pick is unlikely: the chance that all five samples land among the hotter half of the keys is 0.5⁵ ≈ 3%. The config file describes 10 samples as very close to true LRU at more CPU, 3 as faster but not very accurate, and 64 as the maximum. You can change it at runtime with CONFIG SET maxmemory-samples 10 and watch the hit ratio.

How Redis approximates LFU

The same 24 bits are split into a 16-bit timestamp in minutes and an 8-bit logarithmic counter, which tops out at 255. New keys start at 5. On each access the counter rises only with probability 1 / ((counter − 5) × lfu-log-factor + 1), so at counter 15 with the default factor of 10 that is 1 ÷ (10 × 10 + 1) ≈ 1%. With the defaults, 100 hits give about 10, 1,000 give 18, 100,000 give 142, and about a million saturate at 255.

Decay handles fading popularity: when a sampled key is checked, its counter drops by one for every lfu-decay-time minutes (default 1) since its last decrement. OBJECT FREQ key shows a key’s counter. Raise lfu-log-factor to tell apart very hot keys; raise lfu-decay-time if yesterday’s favourites should linger, as in a stable product catalogue.

Memcached: segmented LRU per slab class

Memcached keeps one LRU per slab class (items grouped by size). Since 1.5.0 each is split into HOT (probation for new items), WARM (an item must be hit twice to get in, which shields it from scans) and COLD (where evictions happen), plus an optional TEMP for very short TTLs. A hit in COLD queues an asynchronous move to WARM, so readers never wait on an LRU lock, and a background LRU maintainer thread keeps the segments in balance. It is SLRU in practice.

CDN and HTTP caches

At a CDN edge you rarely choose the policy. Cloudflare documents LRU at its edge, with retention you cannot configure. So a one-year max-age promises the copy stays fresh for a year, not that the edge keeps it: a rarely requested file can be evicted from a PoP within days, sending the next request back to your origin. Tiered caching and an origin shield, covered in content delivery network, soften this.

Measure it: hit-ratio curves and a simulation

Policies differ by workload, so the honest answer to “which is best?” is “on our trace, at our cache size, this one”. A miss-ratio curve plots miss ratio against cache size, one curve per policy. Read three things off it: where your current size sits, where the curve flattens (more memory stops helping), and the horizontal gap between two policies, which is memory you could save. To build one, replay a sample of real (hashed) keys through a simulator at several sizes, with Bélády’s MIN as the ceiling. LRU is a stack algorithm: a bigger LRU cache always holds everything a smaller one would, so one pass gives its whole curve.

This page’s simulation does that on a synthetic trace: 100,000 keys with Zipf popularity (α = 1.0), 1,000,000 user reads, and a cache of 1,000 keys (1%). Its W-TinyLFU is simplified: a fixed 1% window, no hill climbing, no doorkeeper. Two variants stress the policies: a batch job that adds one never-repeated key after every four user reads, and a popularity shift in which the hot set is reshuffled halfway through.

What the runs showed, and only that:

• On the steady trace, S3-FIFO served 59.8 ÷ 50.6 ≈ 1.18× as many reads as LRU, the 18% from the opening paragraph, and every practical policy stayed 6 or more points below Bélády.
• The scan cut LRU’s user-read hit ratio from 50.6% to 47.3% and FIFO’s from 46.5% to 43.0%; LFU, S3-FIFO and W-TinyLFU moved by 0.2 points or less.
• The shift was LFU’s undoing: keys that were popular in the first half kept their counts and blocked the new favourites.

Repeating the steady run at several cache sizes gives points on the hit-ratio curve:

Read it sideways: S3-FIFO with 1,000 entries beat LRU with 2,000, and with 2,000 it fell only a point short of LRU with 5,000. The gaps narrow as the cache grows, because a big enough cache holds the hot set under any policy.

Cheat sheet

How to say it in the interview

“Once the cache is full, every miss evicts something, so the policy is a bet on what won’t be read again. My default is LRU: a hash map to find the node and a doubly linked list in recency order, O(1) for get and put. I’d watch for two failure modes. Scans and one-hit wonders flood LRU and push out the hot set, so for a catalogue-style workload I’d use something with admission, like W-TinyLFU in Caffeine, or LFU with decay in Redis. And frequency without aging clings to yesterday’s favourites, so for feeds I stay with recency. In Redis I’d set maxmemory with allkeys-lru, use noeviction only when Redis is the system of record, and check the hit ratio and evicted keys before tuning further.”

Implement an LRU cache. What’s the complexity? A hash map from key to node, plus a doubly linked list with sentinel head and tail. Get: look up the node, unlink it, relink it at the front. Put: update and move to the front, or, if full, unlink the node before the tail, delete its key from the map and insert the new node at the front. Both are O(1) time, with O(capacity) space and two pointers per entry.

When does LRU perform badly? On scans longer than the cache, which flush the hot set; on loops slightly larger than the cache, where it never hits (0% in the 1,000-key loop above, against 90% for MRU); and when most keys are one-hit wonders. It also costs a shared-list write on every hit, which limits multi-threaded throughput.

LRU or LFU for a product catalogue versus a news feed? Catalogue items stay popular for days while nightly jobs touch the long tail, so frequency wins: LFU with decay or W-TinyLFU. A feed’s popularity moves by the hour, so recency wins. If unsure, use an adaptive policy and measure.

How does Redis do LRU without a linked list? It stores a 24-bit last-access clock in each object, samples maxmemory-samples random keys (5 by default) on each eviction, keeps the best candidates in a 16-entry pool, and evicts the one idle longest. Ten samples get very close to true LRU at more CPU.

Where to go next

• Caching 101: hit-ratio math and why a small cache serves most reads.
• Caching strategies: how entries get into the cache in the first place.
• Count-min sketch and HyperLogLog: the structure behind TinyLFU’s frequency estimates.
• Redis: data types, persistence and memory settings around maxmemory.
• Hot keys, cache stampede and invalidation: what happens when one key is far hotter than the rest.
• Distributed caching: eviction per shard, and sizing a cache cluster.
• Content delivery network: edge retention, tiered caching and origin shields.
• Design a distributed cache: put an eviction policy inside a full design.

References and further reading

1. Redis documentation: Key evictionredis.iomaxmemory, every maxmemory-policy including the 8.6 LRM policies, rules of thumb for choosing, sampled LRU, the LFU counter table, and hit-ratio diagnosis with INFO.
2. Redis configuration file (redis.conf), memory management and LFU sectionsgithub.comDefault noeviction, maxmemory-samples (5 default, 10 near true LRU, 64 max), which writes fail at the limit, lazy and active expiry, and the LFU increment formula with its initial value of 5.
3. Random notes on improving the Redis LRU algorithm (Salvatore Sanfilippo)antirez.comWhy Redis has no LRU list, the 24-bit per-key field, the 16-key candidate pool, and the LFU split into a 16-bit decrement time and an 8-bit logarithmic counter.
4. ARC: A Self-Tuning, Low Overhead Replacement Cache (Megiddo and Modha, FAST 2003)usenix.orgRecency and frequency lists with ghost history, self-tuning, scan resistance, LFU and LRU-2 costs, 2Q and LIRS tuning parameters, and the SPC1-like result of 9.19% (LRU) versus 20.00% (ARC).
5. TinyLFU: A Highly Efficient Cache Admission Policy (Einziger, Friedman and Manes, 2015)arxiv.orgAdmission by comparing frequencies, the halving reset, the doorkeeper, SLRU and 2Q descriptions, and W-TinyLFU’s 1% window and 80/20 main cache.
6. Caffeine wiki: Efficiencygithub.comWhy Caffeine uses W-TinyLFU, its 4-bit count-min sketch at about 8 bytes per entry, hill-climbing window sizing, ARC’s patent and LIRS’s complexity.
7. FIFO Queues are All You Need for Cache Eviction (Yang et al., SOSP 2023)jasony.meS3-FIFO’s three queues and pseudo-code, one-hit-wonder ratios (26% whole trace, 72% in short windows), 6,594 traces, and 6× the throughput of optimised LRU at 16 threads.
8. Replacing the cache replacement algorithm in memcached (memcached.org)memcached.orgThe original per-slab-class LRU and its 60-second bump rule, the HOT, WARM, COLD and TEMP segments, the LRU maintainer and the LRU crawler.
9. PostgreSQL buffer manager READMEgithub.comClock-sweep replacement with a capped usage count, and the 256 KB ring buffer that stops sequential scans from flushing shared buffers.
10. Cloudflare Cache documentation: Retention vs Freshness (TTL)developers.cloudflare.comA CDN that evicts by LRU, retention that depends on popularity and is not configurable, and TTL as a separate freshness setting.