Cache Invalidation and Eviction: TTLs, Deletes and LRU

"Cache invalidation" gets used for two different problems. Invalidation asks when a cached copy stops being true. Eviction asks what to throw away when the cache is full. They fail differently and are fixed differently, and an interviewer who asks about one is usually checking whether you can tell them apart.

The problem it solves

A cache is a second copy of data whose source of truth lives elsewhere, usually a database. The basic read path, cache-aside and the hit ratio, is covered in caching explained. This article is about the two questions it leaves open:

• Correctness over time. The row changes; the copy does not. How long may a reader see the old value?
• Capacity. When a new key arrives and the cache is full, which existing key loses its place?

The intuition

Invalidation has two tools. A TTL stamps every copy with an expiry. It is cheap and bounds staleness: a copy can be wrong for at most the TTL. It limits wrongness; it does not prevent it. Delete on write makes the code that updates the database also delete the cached key, so the next reader fetches the new value. It takes effect at once, but every write path must know every cache that might hold the key, and it has a race.

The race: a reader misses and reads the old row. Before it stores what it read, a writer updates the row and deletes the key, which is not there yet. Then the reader stores the old value, and nothing removes it until the TTL fires. So delete-on-write always keeps a TTL as a backstop. And writers should delete rather than set the new value, because two writers setting the cache can land in the opposite order to their database writes.

Eviction is a prediction. LRU drops the key untouched for the longest. LFU drops the least often used, which protects steady favourites from a one-off scan, as LFU vs LRU shows. An exact LRU needs a hash map plus a linked list, built in LRU cache from scratch. Redis skips the list. As of October 2026, its LRU policies sample a few keys, five by default via maxmemory-samples, and evict the least recently used of the sample, and its default maxmemory-policy is noeviction: a full cache rejects writes until you choose a policy.

Expiry has its own failure mode. When a popular key expires, every request in flight misses at once and hits the database together, a stampede, and keys loaded together with the same TTL expire together. The fixes: let one request refill a key while the others wait, and add random jitter to TTLs.

Watch it run

The animation opens with the distinction: two problems, one name. A price is loaded once and stored with a five-minute time to live, and readers are served that value while it is still true, with no database at all. Two more keys fill the three-key cache to its memory ceiling. A fourth key arrives and something has to go; under allkeys-lru, whatever went longest untouched. Key 8842 was the least recently read, so it leaves and 5503 takes the slot. Separately, every copy is ageing, and a TTL bounds how long it can be wrong without preventing it. Key 1190 reaches zero, its slot empties, and the next reader will have to fetch. The other strategy is immediate: a price change updates the row and deletes 7731, and the next reader fetches 8.25 and caches it. Immediate, but it couples the writer to every cache that has ever held that key. The last frame is the stampede: a hot key expiring under load sends every waiting request at the database in the same instant, 1,200 a second.

The code

A toy model that enumerates every interleaving of two actors' steps. A cache-aside reader reads the database, then fills the cache; a writer updates the database, then either deletes or sets the cached value. An ordering is stale if the cache ends up holding a value the database no longer has:

from itertools import permutations

def interleavings(*actors):
    """Every order of the actors' steps that keeps each actor's own steps in order."""
    tags = [i for i, steps in enumerate(actors) for _ in steps]
    for order in sorted(set(permutations(tags))):
        pos = [0] * len(actors)
        out = []
        for i in order:
            out.append(actors[i][pos[i]])
            pos[i] += 1
        yield out

def run(order):
    s = {"db": 1, "cache": None, "seen": {}}
    for step in order:
        step(s)
    return s["cache"] is not None and s["cache"] != s["db"]   # True = stale copy

def reader(name):           # cache-aside miss: read the database, then fill the cache
    def read(s): s["seen"][name] = s["db"]
    def fill(s): s["cache"] = s["seen"][name]
    return [read, fill]

def writer(value, on_write):
    def write(s): s["db"] = value
    def touch(s):
        if on_write == "delete":
            s["cache"] = None
        else:
            s["cache"] = value
    return [write, touch]

def stale(*actors):
    runs = [run(o) for o in interleavings(*actors)]
    return sum(runs), len(runs)

print(stale(reader("r"), writer(2, "delete")))                    # (1, 6)
print(stale(writer(2, "update"), writer(3, "update")))            # (2, 6)
print(stale(writer(2, "delete"), writer(3, "delete")))            # (0, 6)

One of the six orderings of a reader and a deleting writer leaves a stale copy: read, write, delete, fill. Two writers that set the cache go wrong in two of six; two writers that delete never do. Next, why TTLs need jitter. Ten thousand keys loaded in the same second with a 300-second TTL, then the worst second of expiries without and with ±10% jitter:

import random
from collections import Counter, OrderedDict

def misses_per_second(n_keys, ttl, jitter, rng):
    expiries = Counter(int(ttl * (1 + rng.uniform(-jitter, jitter))) for _ in range(n_keys))
    return max(expiries.values())

rng = random.Random(34)
print(misses_per_second(10000, 300, 0.0, rng), misses_per_second(10000, 300, 0.1, rng))   # 10000 192

Finally, eviction: exact LRU against sampling five candidates per eviction, on 50,000 skewed requests and a 200-key cache. Then a brute-force check on 500 seeded traces against a plain list that moves each used key to the back; sampling every key must reproduce exact LRU:

def hit_ratio(trace, capacity, sample, rng):
    """sample=None: exact LRU. Otherwise evict the oldest of `sample` random keys."""
    last_used, hits = OrderedDict(), 0
    for t, key in enumerate(trace):
        if key in last_used:
            hits += 1
        elif len(last_used) == capacity:
            if sample is None:
                victim = next(iter(last_used))                 # exact: the true oldest
            else:
                pool = rng.sample(list(last_used), min(sample, capacity))
                victim = min(pool, key=last_used.get)          # oldest in the sample
            del last_used[victim]
        last_used[key] = t
        last_used.move_to_end(key)
    return hits / len(trace)

rng = random.Random(34)
keys = range(2000)
trace = rng.choices(keys, weights=[1 / (k + 1) for k in keys], k=50000)
print(round(hit_ratio(trace, 200, None, rng), 3), round(hit_ratio(trace, 200, 5, rng), 3))   # 0.613 0.608

def brute_lru(trace, capacity):
    order, hits = [], 0
    for key in trace:
        if key in order:
            hits += 1
            order.remove(key)
        elif len(order) == capacity:
            order.pop(0)
        order.append(key)
    return hits / len(trace)

ok = True
for _ in range(500):
    cap = rng.randint(1, 6)
    t = [rng.randrange(10) for _ in range(rng.randint(1, 80))]
    exact = brute_lru(t, cap)
    ok &= hit_ratio(t, cap, None, rng) == exact
    ok &= hit_ratio(t, cap, cap, rng) == exact            # sampling every key is exact LRU
print(ok)                                                  # True

Sampling five keys costs half a point of hit ratio here and needs no linked list, which is the trade Redis makes.

The complexity

• TTL: O(1) per key; staleness is bounded by the TTL, not removed.
• Delete on write: O(1) per cache per write, plus the work of knowing which caches hold the key.
• Exact LRU: O(1) per access with a hash map and a doubly linked list, two pointers per key.
• Sampled LRU: O(s) per eviction for s samples, no per-key list.

Where it goes wrong

• Setting instead of deleting on write. Concurrent writers can leave the older value cached.
• No TTL behind delete-on-write. The race, or one forgotten write path, makes a stale value permanent.
• Identical TTLs on bulk loads. Everything expires in the same second.
• Leaving the eviction policy at its default. In Redis, writes then fail when memory is full.

When it shows up in interviews

As a follow-up to any design with a cache: "how do you keep the cache consistent with the database?", "what happens when it is full?" and "what happens when a hot key expires?". The same ideas reappear at the edge in how a CDN works.

How to say it in an interview

"Invalidation and eviction are different problems. Every key gets a TTL, which bounds staleness, and write paths delete the key rather than set it. Deleting has a race where a slow reader puts back the old value, so the TTL stays as a backstop. TTLs get jitter, and refills of hot keys are coalesced to avoid a stampede. For eviction I would start with LRU, Redis's sampled version is good enough, and switch to LFU if scans push out steady favourites."