Files

T

History

kacerrandClaude Fable 5 b290957fc9 05-lru-cache: implement mutex-guarded LRU over container/list

map[string]*list.Element + doubly linked list; Get/Put move hits to the
front, Put evicts from the back when at capacity, and every method
(including Len) takes the mutex.

Add TestLenRacesWithPut, which calls Len concurrently with a writer —
the existing test only read Len after wg.Wait(), so an unsynchronized
Len would never trip the race detector there.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_012MpK9niZm4jcs3mAJbxMfi

2026-09-02 09:34:08 +02:00

main_test.go

05-lru-cache: implement mutex-guarded LRU over container/list

2026-09-02 09:34:08 +02:00

main.go

05-lru-cache: implement mutex-guarded LRU over container/list

2026-09-02 09:34:08 +02:00

README.md

Initial commit: Go SRE interview exercises

2026-08-28 22:18:09 +02:00

README.md

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.