When the cache fills up: eviction

Eviction: choosing what to forget

A cache lives in RAM, and RAM is the most expensive storage you run: a cache holds gigabytes while the database holds terabytes. So a real cache is always too small for the data, and once it is full, storing anything new means deleting something old. That deletion is eviction, and the rule for picking the victim is the eviction policy. Every production Redis runs with a policy configured, and a bad choice quietly wrecks the hit rate you learned to treasure in lesson 3-1, with no error anywhere to see.

The default policy nearly everywhere is LRU, least recently used: evict the entry that has gone unread the longest. The justification is a measured property of real traffic, not a hunch: data accessed a moment ago is far more likely to be accessed again soon (engineers call this temporal locality), so the entry idle longest is the safest one to sacrifice.

The pleasant consequence: an LRU cache automatically keeps whatever is currently popular, with no configuration telling it what popular means.

LRU with room for two entries

On a hit the entry is re-inserted, moving it to the back of the line, and on a miss with a full cache the front of the line is evicted.

capacity = 2
cache = {}

def get_or_load(key):
    if key in cache:
        cache[key] = cache.pop(key)
        print("hit:", key, "| cache now:", list(cache))
        return
    if len(cache) >= capacity:
        oldest = next(iter(cache))
        del cache[oldest]
        print("evict:", oldest)
    cache[key] = True
    print("miss:", key, "| cache now:", list(cache))

for key in ["a", "b", "a", "c", "b"]:
    get_or_load(key)

Output

miss: a | cache now: ['a']
miss: b | cache now: ['a', 'b']
hit: a | cache now: ['b', 'a']
evict: b
miss: c | cache now: ['a', 'c']
evict: a
miss: b | cache now: ['c', 'b']

The hit on a saved it from eviction, since touching an entry moves it to the safe end of the line, and that is the whole idea of LRU. Without that hit, a would have been the victim when c arrived.

cache[key] = cache.pop(key) is the recency update, and it works because Python dicts remember insertion order. Removing and re-adding sends the key to the end, which makes the dict itself the ordering structure.

next(iter(cache)) reads the first key without removing it, which is the least recently used entry by that same ordering. Real implementations use a linked list plus a hash map to get the same behavior in constant time.

Watch the third output line to see the reordering happen, where the cache goes from ['a', 'b'] to ['b', 'a']. Nothing was added or removed, and only the priority changed.

A capacity of 2 exaggerates everything and makes the mechanism visible. A real Redis holds millions of entries and does exactly this, so the eviction decisions are the same and simply invisible at that scale.

Counting hits, misses, and evictions

The same policy at capacity 3, over a request pattern that defeats it.

capacity = 3
cache = {}
hits = 0
misses = 0
evictions = 0
requests = ["u1", "u2", "u3", "u1", "u4", "u2", "u5", "u1"]

for key in requests:
    if key in cache:
        hits += 1
        cache[key] = cache.pop(key)
    else:
        misses += 1
        if len(cache) >= capacity:
            oldest = next(iter(cache))
            del cache[oldest]
            evictions += 1
        cache[key] = True

print("hits:", hits)
print("misses:", misses)
print("evictions:", evictions)

Output

hits: 1
misses: 7
evictions: 4

Only one hit in eight requests, because this access pattern cycles through more keys than the cache can hold, so entries keep dying before their reuse. Five distinct keys competing for three slots means most of them are gone by the time they come around again.

Compare that to lesson 3-2, where the same kind of sequence gave a 57% hit rate with an unbounded cache. The requests did repeat, and the cache was too small to be holding the repeats when they arrived.

Four evictions against one hit is the diagnostic signature. A cache doing far more evicting than hitting is not helping, it is spending memory and CPU to produce misses, and the next block names that condition.

Note that the code is identical to a well-behaved LRU cache, which is the uncomfortable part. Nothing here is a bug, so no error appears anywhere, and the only symptom is a hit rate that never improves.

When eviction is the bug

Watch one number alongside hit rate: the eviction rate. If entries are routinely evicted before anyone reads them a second time, the cache is smaller than its working set, the set of data traffic actually touches in a window of time. The symptom is a hit rate that stays low no matter how correct the code is, exactly like the 1-hit run you just simulated. The fixes, in order of preference: cache smaller values (store IDs, not whole rendered objects), stop caching low-value data, or pay for more RAM.

One more production trap ties this unit together. If a popular, slow-to-compute entry is evicted (or expires), every concurrent request misses at once and stampedes the database recomputing the same value. Teams call it a cache stampede, and the standard cure is to let only one request recompute while the others briefly wait for its result instead of piling on.

Why a 10,000-entry cache fails against a million keys

Because the working set is 100 times the cache size, so most entries are evicted before their next use.

With evenly spread traffic over a million keys, a 10,000-entry cache evicts almost everything before its second use. Each key gets roughly 1% of a chance to still be resident when it comes back, so paying for the cache buys nearly nothing.

The evenly spread part is what does the damage. Uniform access is the worst possible pattern for a cache, because it means no key is more valuable to keep than any other, and LRU's bet on temporal locality has nothing to work with.

Caches shine when traffic is skewed, with a few keys getting most requests, which real traffic usually is. Lesson 5-2's hot keys are the extreme case of the same property, where skew becomes a problem instead of a gift.

When traffic is uniform and huge, shrink what you store, grow the cache, or accept that this data should not be cached. The third option is a real answer, and recognizing it saves both money and the false confidence of a cache that is not working.