# 05 — LRU Cache

The classic "two data structures in a trench coat" problem, and the eviction
policy conversation behind it is genuinely SRE-relevant.

## The shape: map + doubly linked list

- `map[key]*list.Element` → O(1) lookup
- `container/list` (doubly linked) → O(1) move-to-front and remove-from-back

The one detail that separates working from broken: **the list element must
carry the key**, because eviction walks *from the list* (`ll.Back()`) and then
has to delete *from the map* — without the key stored in the entry you can't
close that loop. Every first attempt hits this.

Also know `container/list` is `any`-typed (predates generics) so you type-assert
`el.Value.(*entry)`. Interviewers accept a hand-rolled `prev/next` struct too —
sometimes they prefer it, since `container/list`'s API is obscure enough that
fumbling it looks worse than writing your own 20-liner.

## Why one plain Mutex (and not RWMutex)

Tempting: `RWMutex`, reads in parallel. Broken: **an LRU Get is a write** — it
mutates the recency list. Take the read lock and call `MoveToFront` and you
have a data race on the list pointers. So: plain `Mutex`, or the honest answer
"reads mutate metadata, so RWMutex buys nothing here." Saying that sentence
unprompted is a strong signal. (Sharded locks are the real scaling answer —
16 shards by key hash, like every serious in-process cache.)

## Eviction-policy nerd corner (great interview tangent)

- **LRU's pathology**: sequential scans. One `SELECT *`-style pass through a
  dataset bigger than the cache evicts *everything* useful. This is why Postgres
  ring-buffers large scans and why MySQL's InnoDB inserts new pages at the
  *midpoint* of its LRU, not the head.
- **LRU vs LFU**: LRU adapts fast, forgets fast; LFU remembers popularity,
  ossifies. TinyLFU (used by Caffeine/Ristretto) staples a frequency sketch
  onto an LRU-ish window and beats both.
- **Redis "LRU" is a lie** (an approximation): it samples N random keys and
  evicts the stalest. Precise LRU wasn't worth the memory. `allkeys-lru` vs
  `volatile-ttl` trade-offs are fair game in SRE interviews.

## Standard follow-up: add TTL

Add `expiresAt time.Time` per entry; on Get, if expired → delete, report miss
(lazy expiry). Optional janitor goroutine with a ticker for proactive sweeps —
now you must also add a `Stop()`/context or you've leaked a goroutine+ticker,
which is a lovely full-circle moment with exercise 03's README.