# Caching Strategies — System Design Interview Prep

Source: https://www.skillbyai.com/en/system-design-interview/b-cache

> Hit ratios and invalidation.

## 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%.

```python
# 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).

**Quiz:** In cache-aside, what happens on a cache miss?

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

*Answer:* The app reads from the database and stores the result in the cache. The application manages the cache.