# Caching Strategies

## 1. Why Cache at All

A cache keeps a copy of data somewhere **faster or closer** than its source of truth, so repeated reads skip the slow path.

| Operation | Typical latency |
|---|---|
| L1 CPU cache | ~1 ns |
| in-process memory (a `Map`) | ~100 ns |
| Redis on the same network | ~0.2–1 ms |
| indexed PostgreSQL query | ~1–10 ms |
| cross-region HTTP call | ~100–300 ms |

Caching trades **freshness** and **memory** for **latency** and **load reduction**. Every caching decision is really three questions: *where* does the copy live, *what* gets cached, and *when* does it stop being valid (`05-cache_invalidation/`, `07-ttl/`).

## 2. Where: The Cache Layers

```
browser cache → CDN edge → reverse proxy → application (in-process) → shared cache (Redis) → DB buffer pool → disk
     closest to the user                                                                  closest to the data
```

| Layer | Holds | Shared by | Invalidated by |
|---|---|---|---|
| Browser (HTTP cache) | responses, assets | one user | `Cache-Control`, `ETag` |
| CDN | public responses, static files | all users in a region | TTL, purge API |
| In-process (LRU `Map`) | hot objects | one app instance | TTL, local eviction |
| Shared cache (Redis/Memcached) | objects, query results, sessions | all instances | TTL, explicit delete |
| DB buffer pool | data pages | all queries | the database itself |

The closer to the user, the bigger the win — and the harder invalidation gets (you can't delete something from a million browsers).

**Two-level caching** combines a tiny in-process L1 (microseconds, per instance) with a shared L2 (Redis): L1 absorbs the very hottest keys, L2 keeps instances consistent with each other. The cost: L1 copies on different instances can disagree until they expire, so keep L1 TTLs short.

## 3. What to Cache

Good candidates share three traits — **read often, change rarely, expensive to compute**:

- rendered fragments, product/catalog data, configuration, feature flags
- results of expensive aggregations ("top 10 products this week")
- remote API responses (exchange rates, geolocation)
- session data and rate-limit counters (here the cache is *the* store — see `01-redis/`)

Poor candidates: data that must be perfectly fresh (account balances at checkout), data that's unique per request (search queries with a long tail of distinct inputs — low hit ratio), and anything cheaper to compute than to fetch and deserialize.

**Cache key design** matters as much as what you cache:

```
product:{id}:v3                      # versioned: bump v3 → v4 to invalidate everything after a format change
user:{userId}:feed:page:{n}
search:{sha1(normalizedQuery)}       # normalize first: "Shoes " and "shoes" should share a key
tenant:{tenantId}:settings           # tenant prefix: never serve one tenant's data to another
```

## 4. Reading Patterns, Briefly

- **Cache-aside (lazy loading)**: the application checks the cache, on a miss reads the DB and populates the cache. The default choice.
- **Read-through**: the cache library itself loads from the DB on a miss; the app only talks to the cache.
- **Refresh-ahead**: popular keys are refreshed *before* they expire, so users never see a miss.

Write patterns (write-through, write-behind, write-around) and their consistency trade-offs are the subject of `06-cache_aside_write_through_write_behind/`.

## 5. Eviction Policies

A cache is bounded. When it's full, something must go:

| Policy | Evicts | Good when | Weakness |
|---|---|---|---|
| **LRU** (least recently used) | the key untouched the longest | recency predicts reuse (most workloads) | a one-off scan of many keys flushes the hot set |
| **LFU** (least frequently used) | the key with the fewest hits | stable popularity (top products) | slow to adapt when popularity shifts; needs decay |
| **FIFO** | the oldest inserted | simple, predictable | ignores usage entirely |
| **TTL-based** | expired keys first | data with natural freshness limits | not a capacity policy on its own |
| **Random** | a random key | very cheap, surprisingly OK | unpredictable |

Redis exposes these via `maxmemory-policy` (`allkeys-lru`, `allkeys-lfu`, `volatile-ttl`, ...); Memcached uses LRU per slab class (`02-memcached/`).

## 6. Measuring: Hit Ratio Is the Number

```
hit ratio = hits / (hits + misses)
effective latency ≈ hit_ratio × cache_latency + (1 − hit_ratio) × (cache_latency + db_latency)
```

With a 1 ms cache and a 20 ms DB: 50% hits → ~11 ms average; 90% → ~3 ms; 99% → ~1.2 ms. The last few percent matter enormously — and so does what the misses cost the *database*: at 99% hits, the DB sees 1% of traffic; drop to 90% and DB load goes up **10×**. That's why a cache restart (cold cache) can take a database down: suddenly 100% of traffic is misses.

Watch: hit ratio per key prefix, eviction rate (evictions with a low hit ratio = cache too small), memory, and p99 latency of the cache itself.

## Under the Hood: How an O(1) LRU Works

An LRU cache needs two operations to be O(1): *look up by key* and *find/move the least-recently-used entry*. The classic structure combines a **hash map** with a **doubly linked list**:

```
map:  key → node
list: [MRU] ⇄ node ⇄ node ⇄ node ⇄ [LRU]
get(k):  node = map[k]; unlink(node); pushFront(node)        O(1)
set(k):  if full: evict list.tail, delete map[tail.key]       O(1)
         insert node at front, map[k] = node
```

In JavaScript, a `Map` already iterates in **insertion order**, so "delete then re-set" moves a key to the end, and `map.keys().next().value` is the oldest — a compact LRU with no explicit list.

Redis does **not** keep a global linked list (it would cost memory per key and lock contention). Instead each object stores a 24-bit LRU clock, and on eviction Redis **samples** `maxmemory-samples` random keys (default 5) and evicts the best candidate among them, keeping a small pool of good candidates between rounds. Approximate LRU with 10 samples is nearly indistinguishable from true LRU in practice, at a fraction of the cost. Redis's LFU mode reuses the same 24 bits as an 8-bit **logarithmic counter** plus a decay timestamp, so frequency estimates fade as keys cool down.

![Requests check the closest layer first: browser, CDN, in-process L1, shared Redis L2, then the database; each hit returns early and each layer trades freshness for latency](diagrams/01-cache-layers.svg)

## Common Pitfalls

1. **Caching without measuring hit ratio** — a 20% hit-ratio cache adds latency and complexity for little benefit.
2. **Unbounded in-process caches** — a `Map` that only grows is a memory leak with extra steps.
3. **Keys that ignore tenant/user/locale** — serving one user's data to another is a security incident, not a cache bug.
4. **Caching errors or empty results forever** — a transient DB failure becomes a long outage. Cache negative results only with short TTLs.
5. **Cold-start stampede** — deploying with an empty cache sends 100% of traffic to the DB; warm critical keys or ramp traffic.
6. **Large values** — multi-MB values monopolize network and (in Redis) the single thread; cache smaller pieces.

## Quick Reference

| Decision | Default |
|---|---|
| read pattern | cache-aside |
| shared store | Redis |
| eviction | LRU (`allkeys-lru`) unless popularity is very stable (LFU) |
| key format | `entity:{id}:v{n}`, tenant/locale included when relevant |
| freshness | TTL on every key + explicit invalidation on writes |
| health metric | hit ratio + eviction rate |