kacerrandClaude Fable 5
7219eb5a23
Includes solved 02-worker-pool and 09-safe-counter (mutex, atomic, sharded). Co-Authored-By: Claude Fable 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01GbnJj9ZqEx9nUvzkjdwfMq
49 lines
2.4 KiB
Markdown
49 lines
2.4 KiB
Markdown
# 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.
|