Cache Eviction Policies: LRU vs LFU and Sizing a Cache

A TTL removes entries that have outlived their freshness. But what happens when the cache is full and nothing has expired yet? New data needs space, and the eviction policy decides which existing entry to sacrifice. A good policy keeps the entries most likely to be read again, which directly determines the hit rate; a bad one evicts entries that will be needed soon, turning cache writes into wasted work.

Why eviction matters

Memory is finite and expensive. A Redis instance with 16 GB of RAM holds roughly 100–200 million small key-value pairs, depending on value size. Once it's at capacity, every new entry must evict an old one, and whether the evicted entry was useful (causing a future miss) or dead weight (never read again) depends entirely on the policy.

LRU: least recently used

LRU evicts the entry that hasn't been accessed for the longest time. Its bet: what was used recently will be used again soon, and what has sat untouched is probably cold.

LRU suits workloads with temporal locality, where recent activity predicts near-future activity: web sessions, user profiles, page content. Someone browsing a category will probably revisit the same products within minutes.

Weakness: scan pollution. A one-time scan over many keys pushes out the hot entries. A batch job that reads 50,000 user records once fills the cache with entries nobody will read again, the hit rate drops, and it only recovers as normal traffic re-caches the hot set.

How an LRU cache works

A classic LRU cache combines a hash map (key → node) with a doubly linked list ordered by recency. Every access moves the node to the front; eviction removes from the back. Both operations are O(1).

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.items = capacity, OrderedDict()

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)          # mark as most recently used
        return self.items[key]

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # evict the least recently used

Redis approximates LRU (allkeys-lru or volatile-lru). Keeping every key in a perfectly ordered list would cost too much memory, so Redis samples a few keys and evicts the least recently used among them, trading a little accuracy for very low overhead. Note that Redis defaults to `noeviction`: you must set maxmemory and an eviction policy, or writes start failing when memory is full.

LFU: least frequently used

LFU evicts the entry with the fewest accesses. It counts reads per entry and removes the lowest count. Its bet: entries read many times are important; rarely read ones are disposable.

LFU resists scan pollution: a batch job that reads 50,000 keys once gives each a count of 1, while the hot entries with counts of 500+ stay safe.

Weakness: cold start. A newly cached entry starts with a count of 1. If the cache is full of high-count entries, the newcomer is evicted at once, even if it's about to become the most popular key. Some implementations add frequency decay: counts shrink over time, so entries that were popular long ago but are cold now gradually lose their protection.

Redis implements LFU with a logarithmic counter and a decay factor (lfu-log-factor and lfu-decay-time). Because the counter is logarithmic it saturates quickly (the difference between 100 and 1,000 accesses is small), so old entries can't become permanently immune.

Other policies

Production caches approximate these for efficiency. Memcached uses a segmented LRU per slab class. Caffeine (Java) uses W-TinyLFU: a small admission window plus a frequency sketch decides whether a new item is worth admitting at all, which protects against one-off scans (see count-min sketch).

Choosing a policy

For most web applications LRU is the safer default. Switch to LFU when you see scan pollution (the hit rate drops during batch operations) or when a small set of keys gets most of the traffic.

Memory math: sizing the cache

Too small and the cache evicts constantly with a low hit rate; too large and you pay for unused RAM. Start from the working set: the number of distinct keys accessed within one TTL window.

1. Estimate the hot keys. If the app serves 10,000 unique product pages an hour and the TTL is 15 minutes, the working set is about 2,500 keys (a quarter-hour of unique accesses).
2. Estimate the entry size. Key + value + Redis per-key overhead (~70–100 bytes). A product page entry: key product:v1:detail:12345 ≈ 30 bytes, value (serialized JSON) ≈ 2 KB, overhead ≈ 80 bytes, total ≈ 2.1 KB.
3. Multiply and add headroom. 2,500 × 2.1 KB ≈ 5.3 MB; add 20–30% for fragmentation and spikes ≈ 7 MB.

The same arithmetic scales: 1 million unique keys at 2 KB each is about 2 GB, so allocate roughly 2.5–3 GB.

The 80/20 heuristic. Many read-heavy workloads are skewed (Zipf-like): roughly 20% of keys get 80% of the traffic. Confirm the skew from your access logs before relying on it, but if it holds, caching only the hot 20% captures most of the benefit: with 10 million keys in total, caching the hottest 2 million may give a 90%+ hit rate. The cache can be far smaller than the dataset.

In practice, measure the hit-rate-versus-memory curve: the hit rate climbs steeply, then flattens, and the knee of the curve is the efficient size. See back-of-the-envelope estimation.

Monitoring eviction health

• Hit rate: the share of reads served from the cache. Below about 90% on a well-tuned cache suggests the working set doesn't fit; consistently above 99% may mean you're paying for memory you don't need.
• Eviction rate: evictions per second. A steady rate at max memory is normal for a full cache. A spike usually lines up with batch jobs or traffic bursts that are pushing out hot entries.

High evictions with a falling hit rate: add memory or switch policy (often LRU → LFU). Rare evictions with a hit rate always above 99%: the cache is probably over-provisioned. See cache monitoring.

Choose what happens when the cache is full. Redis's noeviction makes writes fail; for a cache you almost always want an eviction policy, while for a Redis used as a primary store you want alerts long before memory runs out.

TTL and eviction together

Use TTLs to bound staleness and eviction to bound memory. Add jitter to TTLs (for example 10 minutes ± 10%) so keys written together don't all expire together. See cache invalidation. When one machine can't hold the working set at all, shard the cache across nodes: see distributed caching.