Caching Explained: Cache-Aside, Hit Ratio, TTL and Stale Data

"Add a cache" is the most common move in a system design interview, and the one most often made without thought. A cache can cut read latency from tens of milliseconds to one and take most of the load off a database. It can also add memory cost and a class of bugs where users see data that is no longer true, while barely helping. The difference comes down to one number, the hit ratio, and one question: how stale is acceptable?

The problem it solves

Some work is expensive and repeated: a database query, a call to another service, a rendered page. Doing it again for every request wastes latency and backend capacity.

A cache stores the result of that work somewhere faster and closer, usually in memory, keyed by the request. A hit is served from the cache; a miss does the real work and usually stores the result for next time. Caches appear at every layer: the browser, a CDN, an in-memory store such as Redis in front of the database, and the application process itself.

The intuition

The most common way to wire it is cache-aside, also called lazy loading:

1. Look the key up in the cache.
2. On a hit, return the cached value.
3. On a miss, read from the database, store the value in the cache, then return it.

The application owns the logic and the cache is a plain key-value store. Only data someone asked for is cached, and a cache outage degrades to "every request is a miss". Write-through, which updates the cache on every write, trades write cost for fresher reads.

Whether any of this pays off depends on the access pattern. Real demand is rarely uniform: a small set of popular items takes a large share of requests. When that holds, a cache that fits a small fraction of the data answers most of the requests. When every request asks for something different, nothing is ever reused, and the cache costs memory while hitting almost never. The expected latency makes it concrete: with hit ratio h, a 1 ms hit and an 85 ms miss, the average is h × 1 + (1 - h) × 85.

The price of a cache is staleness. A cache is a second copy of the truth, and copies drift. When the row changes, the cached value is wrong until something removes or refreshes it. Two tools bound the damage:

• A TTL (time to live): every entry expires after a fixed time, which caps how stale a value can be.
• Invalidation on write: the code that updates the database also deletes the cached key, so the next read misses and fetches the new value.

A full cache must also evict something, typically the least recently used entry, as in an LRU cache.

Watch it run

The animation starts from the definition: a cache keeps the result of expensive work near whoever keeps asking. A request arrives for user:42, and the cache is checked first. Nothing is stored under that key: a miss. So the real work happens, and the value is fetched from the database. On the way back, it is stored under the request's key, then returned to the caller: eighty-four milliseconds, paid once. The same key is asked for again, and this time the cache answers. Demand is nowhere near uniform, so a tiny tray answers nearly every request: 92 hits in 100. Then every request asks for something different; nothing repeats, so nothing is reused. Nine hits in a hundred is not a cache, it is memory cost plus a stale-data bug, so measure it. The last frame is the warning: a cache is a second copy of the truth. The row changed, and the cached copy has not.

The code

A toy model, not a real cache server: a pretend database where every read costs 84 ms, and a cache-aside wrapper with LRU eviction and a TTL on a fake clock. The first call misses and pays 85 ms including the cache check; the second hits:

from collections import OrderedDict

class ToyDB:
    """Toy model of a slow database: every read costs 84 ms of pretend time."""
    def __init__(self, rows):
        self.rows, self.reads = dict(rows), 0

    def read(self, key):
        self.reads += 1
        return self.rows.get(key), 84

class ToyCache:
    """Toy model of cache-aside with LRU eviction and a TTL, not a real cache server."""
    def __init__(self, db, capacity, ttl):
        self.db, self.capacity, self.ttl = db, capacity, ttl
        self.store = OrderedDict()                   # key -> (value, expires_at)
        self.now, self.hits, self.misses = 0, 0, 0

    def get(self, key):
        entry = self.store.get(key)
        if entry is not None and entry[1] > self.now:
            self.store.move_to_end(key)              # most recently used
            self.hits += 1
            return entry[0], 1                       # a hit costs 1 ms
        self.misses += 1
        value, cost = self.db.read(key)              # the real work
        self.store[key] = (value, self.now + self.ttl)   # store it on the way back
        self.store.move_to_end(key)
        if len(self.store) > self.capacity:
            self.store.popitem(last=False)           # evict the least recently used
        return value, cost + 1

    def invalidate(self, key):
        self.store.pop(key, None)

db = ToyDB({"user:42": 4.50, "user:7": 9.99})
cache = ToyCache(db, capacity=2, ttl=60)
print(cache.get("user:42"))          # (4.5, 85)
print(cache.get("user:42"))          # (4.5, 1)
print(cache.hits, cache.misses, db.reads)    # 1 1 1

The hit ratio under two access patterns, 20,000 requests over 5,000 items. With skewed demand, where the item of rank r is asked for in proportion to 1 / r, a 50-entry cache answers 35% of requests and a 500-entry cache 65%. With uniform demand, 50 entries answer 1%. Then the average latency at three hit ratios:

import random

def hit_ratio(keys, capacity=50):
    c = ToyCache(ToyDB({k: k for k in set(keys)}), capacity, ttl=10**9)
    for k in keys:
        c.get(k)
    return round(100 * c.hits / len(keys))

random.seed(23)
catalogue = range(5000)
weights = [1 / (rank + 1) for rank in catalogue]     # a few items asked for far more than the rest
skewed = random.choices(catalogue, weights=weights, k=20000)
uniform = random.choices(catalogue, k=20000)
print(hit_ratio(skewed), hit_ratio(skewed, 500), hit_ratio(uniform))   # 35 65 1

for h in (0.92, 0.35, 0.09):
    print(h, round(h * 1 + (1 - h) * 85, 1), "ms on average")
# 0.92 7.7 ms on average
# 0.35 55.6 ms on average
# 0.09 77.4 ms on average

Staleness and its two fixes. After the row changes, the cache keeps serving the old price until the TTL runs out; deleting the key on write makes the next read fetch the new value at once:

db = ToyDB({"price:9": 4.50})
cache = ToyCache(db, capacity=10, ttl=30)
cache.get("price:9")
db.rows["price:9"] = 5.25                            # the row changes; the copy does not
print(cache.get("price:9")[0])                       # 4.5   stale
cache.now += 31                                      # the TTL runs out
print(cache.get("price:9")[0])                       # 5.25
db.rows["price:9"] = 6.00
cache.invalidate("price:9")                          # write path deletes the cached copy
print(cache.get("price:9")[0])                       # 6.0

The cache checked against a brute-force model, a plain list of (key, value, expires) entries in recency order, on 1,000 seeded random runs of reads, writes, invalidations and clock jumps: every value, every cost and the hit count must agree:

random.seed(23)
ok = True
for _ in range(1000):
    cap, ttl = random.randint(1, 5), random.randint(1, 20)
    rows = {k: random.randint(0, 99) for k in range(8)}
    cache = ToyCache(ToyDB(rows), cap, ttl)
    ref, clock, hits = [], 0, 0                      # brute force: a list of (key, value, expires)
    for _ in range(random.randint(1, 60)):
        op = random.random()
        if op < 0.15:
            step = random.randint(1, 10)
            cache.now += step
            clock += step
        elif op < 0.25:
            k = random.randrange(8)
            cache.db.rows[k] = random.randint(0, 99)
            if random.random() < 0.5:
                cache.invalidate(k)
                ref = [e for e in ref if e[0] != k]
        else:
            k = random.randrange(8)
            value, cost = cache.get(k)
            live = [e for e in ref if e[0] == k and e[2] > clock]
            ref = [e for e in ref if e[0] != k]
            if live:
                hits += 1
                ref.append(live[0])
                ok &= (value, cost) == (live[0][1], 1)
            else:
                ok &= (value, cost) == (cache.db.rows[k], 85)
                ref.append((k, cache.db.rows[k], clock + ttl))
                ref = ref[-cap:]                     # oldest use falls off the front
    ok &= cache.hits == hits
print(ok)                                            # True

The complexity

• Lookup and insert: O(1) on average for a hash-based cache with LRU order.
• Latency: h × hit cost + (1 - h) × miss cost; the hit ratio matters far more than the cache's own speed.
• Staleness: at most the TTL, and usually far less with invalidation on every write path.

Where it goes wrong

• Caching without measuring. A low hit ratio means memory cost plus stale data, and little saved.
• Forgetting a write path. One code path that updates the database without invalidating leaves stale values until the TTL.
• No TTL at all. A missed invalidation then lasts forever.
• A stampede on a hot key. When a popular entry expires, many requests miss at once and all hit the database; letting one request refill the key while the others wait avoids it.

When it shows up in interviews

It shows up in almost every system design question as the answer to "reads are too slow" or "the database is overloaded", from a URL shortener to a distributed cache with consistent hashing. The follow-ups are about eviction, covered in LFU vs LRU, and about caching at the edge, covered in CloudFront caching.

How to say it in an interview

"Reads dominate and a small set of keys is requested far more than the rest, so I put a cache-aside layer in front of the database: look up the key, on a miss read the database and store the result. The hit ratio decides whether it is worth it, so I measure it. The cost is staleness, so every entry gets a TTL, and every write path deletes the key so the next read fetches the new value. Memory is bounded with LRU eviction, and for very hot keys I make sure only one request refills an expired entry."