Caching Strategies

Cache-aside, TTLs and eviction

With cache-aside, the application reads from the cache, falls back to the database on a miss and stores the result with a TTL; on writes it updates the database and deletes or updates the cache entry. Write-through writes to both synchronously; write-back writes to the cache and flushes later (fast but riskier). Eviction policies such as LRU keep popular items. Real workloads are skewed, so a small cache can absorb a large share of reads. Watch for stampedes on popular keys and stale data.

LRU hit ratio on a skewed workload, run

I ran this with Python 3.12.3 using only the standard library; inputs are fixed or seeded, so the output is reproducible. With 200,000 requests following a Zipf-like popularity, caching just 1% of items serves about half of all reads, and 20% serves about 78%.

# LRU cache hit ratio on a skewed (Zipf-like) workload
import random
from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.cap, self.data = capacity, OrderedDict()
        self.hits = self.misses = 0
    def get(self, key, load):
        if key in self.data:
            self.data.move_to_end(key); self.hits += 1
            return self.data[key]
        self.misses += 1
        value = self.data[key] = load(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)          # evict least recently used
        return value

rng = random.Random(7)
items = 100_000
weights = [1 / (i + 1) for i in range(items)]   # item 0 is most popular
requests = rng.choices(range(items), weights=weights, k=200_000)

for cap in (1_000, 5_000, 20_000):
    c = LRU(cap)
    for key in requests:
        c.get(key, lambda k: f"row {k}")
    print(f"cache {cap:>6,} items ({cap / items:4.0%} of data): hit ratio {c.hits / len(requests):.1%}")

Output:

cache  1,000 items (  1% of data): hit ratio 50.6%
cache  5,000 items (  5% of data): hit ratio 66.1%
cache 20,000 items ( 20% of data): hit ratio 78.3%

Say how you invalidate

Interviewers often ask how cached data stays fresh; have an answer (TTL plus delete on write, or events).

Quick check: In cache-aside, what happens on a cache miss?

• The cache queries the database by itself and blocks writes
• The request fails
• The app reads from the database and stores the result in the cache
• The database is bypassed