Concurrent LRU — Junior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. Core Concepts
5. Real-World Analogies
6. Mental Models
7. Pros and Cons
8. Use Cases
9. Code Examples
10. Coding Patterns
11. Clean Code
12. Product Use and Features
13. Error Handling
14. Security Considerations
15. Performance Tips
16. Best Practices
17. Edge Cases and Pitfalls
18. Common Mistakes
19. Common Misconceptions
20. Tricky Points
21. Test
22. Tricky Questions
23. Cheat Sheet
24. Self-Assessment Checklist
25. Summary
26. What You Can Build
27. Further Reading
28. Related Topics
29. Diagrams and Visual Aids

Introduction¶

Focus: "What is an LRU cache? Why do I need a linked list AND a map? How do I make it safe for many goroutines at once?"

A cache is a small, fast store that holds recently used data so the next request can skip a slower step — a database query, an HTTP call, a JSON parse, a regex compile. The catch is the word small. A cache has a fixed capacity; once it is full and a new entry arrives, something has to leave. The rule that picks the victim is called the eviction policy. The most famous one is LRU: throw out the least recently used item.

Why "least recently used"? Because of a strong empirical pattern called temporal locality: if you accessed a key now, you are more likely to access it again soon than to ask for a key you have not touched in an hour. LRU encodes that bet directly: every access promotes a key to the "most recently used" position, and only items that have sat idle the longest get pushed out.

For a single goroutine, an LRU is a small puzzle: combine a hash map for O(1) lookup with a doubly-linked list for O(1) recency updates. For many goroutines hitting the same cache at once, it becomes a real concurrency exercise. Two goroutines that both Get the same hot key must not corrupt the linked list while moving the node to the front. Two goroutines that both Set keys while the cache is full must not double-evict or leave dangling map entries.

This file teaches the minimum complete picture a junior Go engineer needs:

• The "map plus doubly-linked list" classical design
• Why concurrent goroutines break the naive version
• How a single sync.Mutex makes it correct (but slow)
• How container/list from the standard library helps
• How to use hashicorp/golang-lru/v2, the de facto Go LRU library, in five lines
• The single most common bug: forgetting to update the map when the list evicts

You do not need to know about sharding, RWMutex trade-offs, lock-free reads, or admission policies yet — those come in the middle, senior, and professional files. This file is about understanding the invariant and writing your first correct concurrent LRU.

After reading this file you will:

• Be able to draw the LRU invariant on paper
• Be able to write a correct single-goroutine LRU in ~80 lines of Go
• Be able to wrap it with one mutex and explain why that is safe
• Be able to drop in hashicorp/golang-lru/v2 for a real project
• Recognise the three or four bugs that turn an LRU into a memory leak or a deadlock

Prerequisites¶

• Required: Go 1.21 or newer. Generics (hashicorp/golang-lru/v2) require 1.18+.
• Required: Comfort with the map[K]V built-in and basic struct types.
• Required: Awareness of pointers. Linked lists are pointer-heavy.
• Required: Familiarity with sync.Mutex — Lock, Unlock, and the defer mu.Unlock() idiom.
• Helpful: A read through the container/list package documentation. The whole package is ~150 lines.
• Helpful: Some exposure to the race detector (go test -race). All concurrent code in this file should be exercised with it.

If you can write a function that takes a *sync.Mutex and a shared map[string]int, locks the mutex, mutates the map, and unlocks the mutex, you have everything you need.

Glossary¶

Core Concepts¶

1. The textbook LRU invariant¶

An LRU cache stores up to capacity entries. Each entry has a key, a value, and an implicit position on a recency timeline. We represent that timeline with a doubly-linked list:

MRU                                            LRU
front                                          back
[k7,v7] <-> [k2,v2] <-> [k9,v9] <-> [k4,v4] <-> [k1,v1]

k7 was used most recently. k1 is the next to die.

We also keep a map:

items map[K]*list.Element // K → pointer to the node in the list

The map answers "where is key K in the list?" in O(1). Without it, Get(k) would have to scan the list.

The invariant is small but absolute:

1. Every key in items corresponds to exactly one element in the list.
2. Every element in the list has its key present in items.
3. The number of entries is len(items) == list.Len() and is ≤ capacity.

If any operation breaks the invariant and then returns, the cache is corrupt and will leak memory or return stale data forever after.

2. The three operations and their effect on the invariant¶

Get(k):

1. Look up k in the map.
2. If absent, return miss. (No change to list.)
3. If present, move the node to the front of the list. (Recency updated.)
4. Return the value.

Set(k, v):

1. If k already exists, update the value and move the node to the front.
2. Otherwise:
3. If the cache is full, remove the back node and delete its key from the map.
4. Push a new node to the front and add the map entry.

Remove(k):

1. Look up k. If absent, no-op.
2. Remove the node from the list and delete the key from the map.

Notice that Get mutates the cache. This is the single most surprising fact for newcomers. It also explains why sync.RWMutex.RLock is not safe for Get — Get is a writer in disguise.

3. Why one goroutine is not enough¶

In a web server, hundreds of goroutines serve requests in parallel. Each may call cache.Get(userID) or cache.Set(userID, profile). If two goroutines both move the same node to the front concurrently, the list's prev/next pointers can crash into each other. The result is a corrupted list (e.g., a cycle), and the next traversal will loop forever or panic with a nil dereference.

The simplest fix is a single sync.Mutex wrapping every public method. This is correct, easy to read, easy to test — and the right starting point. The cost is that only one goroutine at a time enters the cache, no matter how many cores you have. Later levels remove this bottleneck with sharding.

4. Why a doubly-linked list?¶

You might ask: can't I use a slice and move elements around with copy? You can, but moving an element from position i to the front in a slice of n items costs O(n). With n of 100 000 and a billion lookups per day, that becomes the bottleneck.

A doubly-linked list lets you:

• Remove a node from the middle in O(1) (because you have both prev and next already).
• Insert at the front in O(1).
• Insert at the back in O(1).

No other simple data structure gives you all three. (A doubly-ended deque using a ring buffer gives you front/back O(1) but not arbitrary-middle removal.)

5. What container/list provides¶

The standard library has exactly what we need:

type List struct { /* ... */ }
type Element struct { Value any; /* ... */ }

func (l *List) Init() *List
func (l *List) Len() int
func (l *List) PushFront(v any) *Element
func (l *List) PushBack(v any) *Element
func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) Remove(e *Element) any
func (l *List) Front() *Element
func (l *List) Back() *Element

Three operations matter for LRU: PushFront, MoveToFront, and Remove. We stash a custom struct (key + value) in each Element.Value so that during eviction we know which key to delete from the map.

type entry[K comparable, V any] struct {
    key K
    val V
}

container/list itself is not safe for concurrent use — the docs say so explicitly. We must add our own locking.

Real-World Analogies¶

The librarian's returns trolley¶

Picture a librarian with a small returns trolley that holds 20 books. When a reader brings back a book, the librarian puts it on the front of the trolley. Whenever a reader asks for a book that is already on the trolley, the librarian takes it off, hands it over, and puts it back on the front — because it has just been used. When the trolley is full and a new book arrives, the librarian takes the book at the back of the trolley (the one untouched the longest) and reshelves it.

The hash map is the librarian's mental index: "I know that book X is on the trolley." The trolley itself is the doubly-linked list. The librarian is the mutex — only one move happens at a time.

The kitchen prep station¶

A line cook keeps a small tray of "currently active" ingredients at the front of the station. Each time an ingredient is needed, it gets touched and pushed forward. The ingredient at the back of the tray is the next to be put back in the walk-in fridge. The cook never works on two orders at the same instant on the same tray — that is the mutex.

The phone's recent-calls list¶

Your phone shows recent calls newest first. If you call someone who is already in the list, they jump to the top. If the list is capped at 100 entries, the oldest one falls off. That is LRU.

Mental Models¶

Model 1 — Two views of the same data¶

The map and the list are two views of the same set of entries. The map view answers "is X here, and where?" in O(1). The list view answers "who is newest?" and "who is oldest?" in O(1). Every operation must update both views or the invariant breaks.

The mental trap is to think of them as two separate structures. They are not. They are one structure with two indices. Touch one, you must touch the other.

Model 2 — The mutex is a one-lane bridge¶

All cache operations cross a one-lane bridge. Only one car at a time. When traffic is light this is fine; when traffic is heavy you get a queue. Sharding (covered at middle level) is "build more bridges." Lock-free reads (covered at senior level) are "let cars go around the bridge in special cases."

Model 3 — Get is a write in disguise¶

In a typical data structure, Read and Write are clearly separated and an RWMutex helps. In an LRU, Get mutates the recency list, so it is a writer. Forgetting this turns "performance optimisation" into a data race.

Model 4 — The cache is allowed to be wrong, briefly¶

A cache is a probabilistic speedup, not a source of truth. If two goroutines Set the same key with different values, one wins and one loses, and that is fine — the database is the source of truth. This relaxed contract is why caches can use weaker synchronisation than, say, a database index.

Pros and Cons¶

Pros¶

• Sub-microsecond latency. A pointer chase through a small linked list beats almost every other lookup form.
• Bounded memory. Unlike an unbounded map, an LRU cache will not eat your heap.
• Excellent for "hot-set" workloads. When a small fraction of keys gets most of the traffic, hit rates above 90% are routine.
• Simple correctness story. A single mutex makes a textbook LRU trivially safe.
• Well-supported libraries. hashicorp/golang-lru/v2 covers most production needs in five lines.

Cons¶

• Every Get is a write. RWMutex does not help the way it does for read-mostly data structures.
• Single mutex is a hotspot. Under heavy load, all cores serialise on it.
• Linked-list nodes pressure the GC. Every Set allocates an Element and an entry value.
• Scan-unfriendly. A one-time scan of N+1 cold keys will evict your entire hot set. LRU has no defence against this; smarter policies (LFU, TinyLFU) do.
• Doubly-linked list cache misses. Pointer-chasing through random-allocated nodes is L1-unfriendly compared to array-based structures.

Use Cases¶

LRU cache is the right first answer when you have:

• A read-heavy workload with a hot set. User profiles, product metadata, session lookups, JWT-to-user mappings.
• Expensive recomputation. Compiled regexes, parsed templates, marshalled protobufs.
• Bounded scratch space. Recent computation results in a workflow engine.
• Application-level fronting of a database. Especially when the DB has predictable latency and rare changes per key.

It is not the right answer for:

• Unbounded streaming workloads where every key is fresh — you will evict useful entries and add overhead.
• Strict consistency requirements where stale values cannot be served — use a write-through cache or no cache.
• Workloads with no temporal locality — you will hit the LRU end almost every time. Use LFU or W-TinyLFU.
• Caches larger than RAM — use a persistent store like Redis, not an in-process LRU.

A few concrete stories¶

Story 1 — The session cache that became a hot mutex. A startup added an LRU session cache to their auth service. Hit-rate was 99%, latency dropped 10x — for a week. Then traffic doubled and pprof showed 40% of CPU in runtime.lock2. The single mutex on the cache had become the bottleneck. Sharding to 64 stripes (middle file) fixed it overnight.

Story 2 — The DNS resolver that leaked. A team built a DNS cache: domain → IPs. They forgot to add a TTL and the eviction was purely LRU. A scan of a public DNS resolver list (~30 K names in one request) evicted the company's own hot domains. The next 10 minutes were a 10x spike in DNS lookups. They added per-entry TTL and a separate cache for trusted-vs-untrusted domains.

Story 3 — The compiled-regex cache that boosted throughput 4x. A log-parser had 50 regexes that all callers shared. Every parse was compiling fresh. An LRU of size 64 (over-provisioned by 14) brought parse time from 1.2 ms to 280 µs.

Story 4 — The cache that had to be perfectly consistent. A trading engine wanted to cache the per-account margin. They reached for an LRU. Then they realised stale margins could let an account over-borrow. They removed the cache and routed straight to the source of truth with a connection pool instead. Right answer: no cache.

The pattern across these stories is the same. An LRU is exactly right when it is right. When it isn't, it is the wrong default — and you must know the failure modes (mutex contention, scan-eviction, inconsistency) to recognise the misfit.

Code Examples¶

Example 1 — A minimal single-goroutine LRU¶

This version is not safe for concurrent use. We start here so the structure is clear; then we add the mutex.

package lru

import "container/list"

type entry[K comparable, V any] struct {
    key K
    val V
}

type LRU[K comparable, V any] struct {
    capacity int
    items    map[K]*list.Element
    order    *list.List
}

func New[K comparable, V any](capacity int) *LRU[K, V] {
    if capacity <= 0 {
        panic("lru: capacity must be positive")
    }
    return &LRU[K, V]{
        capacity: capacity,
        items:    make(map[K]*list.Element, capacity),
        order:    list.New(),
    }
}

func (c *LRU[K, V]) Get(k K) (V, bool) {
    if e, ok := c.items[k]; ok {
        c.order.MoveToFront(e)
        return e.Value.(*entry[K, V]).val, true
    }
    var zero V
    return zero, false
}

func (c *LRU[K, V]) Set(k K, v V) {
    if e, ok := c.items[k]; ok {
        c.order.MoveToFront(e)
        e.Value.(*entry[K, V]).val = v
        return
    }
    if c.order.Len() >= c.capacity {
        back := c.order.Back()
        if back != nil {
            ent := c.order.Remove(back).(*entry[K, V])
            delete(c.items, ent.key)
        }
    }
    ent := &entry[K, V]{key: k, val: v}
    c.items[k] = c.order.PushFront(ent)
}

func (c *LRU[K, V]) Remove(k K) bool {
    if e, ok := c.items[k]; ok {
        c.order.Remove(e)
        delete(c.items, k)
        return true
    }
    return false
}

func (c *LRU[K, V]) Len() int { return c.order.Len() }

Read through it slowly. Notice three details:

1. We store *entry[K, V] in the list — not just the value. We need the key to know what to delete from the map on eviction.
2. Get calls MoveToFront — that is the mutation.
3. Set checks for existing keys before deciding to evict. Updating an existing key never causes an eviction.

Example 2 — Add the mutex¶

package lru

import (
    "container/list"
    "sync"
)

type LRU[K comparable, V any] struct {
    mu       sync.Mutex
    capacity int
    items    map[K]*list.Element
    order    *list.List
}

func New[K comparable, V any](capacity int) *LRU[K, V] {
    if capacity <= 0 {
        panic("lru: capacity must be positive")
    }
    return &LRU[K, V]{
        capacity: capacity,
        items:    make(map[K]*list.Element, capacity),
        order:    list.New(),
    }
}

func (c *LRU[K, V]) Get(k K) (V, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.items[k]; ok {
        c.order.MoveToFront(e)
        return e.Value.(*entry[K, V]).val, true
    }
    var zero V
    return zero, false
}

func (c *LRU[K, V]) Set(k K, v V) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.items[k]; ok {
        c.order.MoveToFront(e)
        e.Value.(*entry[K, V]).val = v
        return
    }
    if c.order.Len() >= c.capacity {
        back := c.order.Back()
        if back != nil {
            ent := c.order.Remove(back).(*entry[K, V])
            delete(c.items, ent.key)
        }
    }
    ent := &entry[K, V]{key: k, val: v}
    c.items[k] = c.order.PushFront(ent)
}

func (c *LRU[K, V]) Remove(k K) bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.items[k]; ok {
        c.order.Remove(e)
        delete(c.items, k)
        return true
    }
    return false
}

func (c *LRU[K, V]) Len() int {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.order.Len()
}

Every public method begins with c.mu.Lock() and defer c.mu.Unlock(). This is correct under any number of goroutines. It is slow under heavy load because only one goroutine is inside the cache at a time, but correctness comes first.

Example 3 — Use hashicorp/golang-lru/v2¶

In a real project you almost never write your own LRU. The de facto library is hashicorp/golang-lru/v2. It is already concurrency-safe, generic, and tuned.

package main

import (
    "fmt"

    lru "github.com/hashicorp/golang-lru/v2"
)

func main() {
    cache, err := lru.New[string, int](128)
    if err != nil {
        panic(err) // only fails on capacity <= 0
    }

    cache.Add("alice", 1)
    cache.Add("bob", 2)

    if v, ok := cache.Get("alice"); ok {
        fmt.Println("alice =", v)
    }
    fmt.Println("len =", cache.Len())
}

The library names the insert method Add, not Set. Otherwise the surface is what you expect: Get, Add, Remove, Len, Purge, Keys.

Example 4 — Eviction callback with golang-lru/v2¶

When an entry is evicted, you often want a hook — close a file handle, decrement a refcount, record a metric.

cache, _ := lru.NewWithEvict[string, *os.File](
    128,
    func(key string, value *os.File) {
        _ = value.Close()
    },
)

The callback runs inside the lock. Do not block, do not panic, do not call back into the cache. Keep it to a non-blocking metric increment or a Close().

Example 5 — A tiny benchmark¶

package lru_test

import (
    "strconv"
    "sync"
    "testing"

    lru "github.com/hashicorp/golang-lru/v2"
)

func BenchmarkParallelGet(b *testing.B) {
    cache, _ := lru.New[string, int](10_000)
    for i := 0; i < 10_000; i++ {
        cache.Add(strconv.Itoa(i), i)
    }
    b.ResetTimer()
    var wg sync.WaitGroup
    workers := 8
    each := b.N / workers
    for w := 0; w < workers; w++ {
        wg.Add(1)
        go func(off int) {
            defer wg.Done()
            for i := 0; i < each; i++ {
                cache.Get(strconv.Itoa((off + i) % 10_000))
            }
        }(w * 10_000)
    }
    wg.Wait()
}

Run with go test -bench . -benchmem. Numbers vary by machine but you should see operation costs in the low hundreds of nanoseconds.

Example 6 — Set-or-Get (the "load or store" pattern)¶

A very common pattern: "if the key is there, return it; otherwise compute and insert."

func GetOrLoad[K comparable, V any](
    c *lru.Cache[K, V],
    key K,
    load func() (V, error),
) (V, error) {
    if v, ok := c.Get(key); ok {
        return v, nil
    }
    v, err := load()
    if err != nil {
        var zero V
        return zero, err
    }
    c.Add(key, v)
    return v, nil
}

This version has a small race: two goroutines may both miss and call load() for the same key. That is acceptable for many workloads (idempotent loaders). When it is not, use singleflight — covered in the middle file.

Example 7 — Peek does not touch recency¶

Sometimes you want to read a value without affecting eviction order — for example, you are dumping the cache to a log for debugging.

if v, ok := cache.Peek("alice"); ok {
    fmt.Println(v)
}

Peek skips MoveToFront. Use it sparingly; the whole point of LRU is that access should affect recency.

Example 8 — Building a thin wrapper around golang-lru/v2¶

Real applications almost never use the cache library directly. They wrap it so that the call site is meaningful and the library is swappable.

package usercache

import (
    "errors"
    "sync/atomic"

    lru "github.com/hashicorp/golang-lru/v2"
)

type User struct {
    ID    string
    Name  string
    Email string
}

type Cache struct {
    inner *lru.Cache[string, *User]
    hits  atomic.Uint64
    miss  atomic.Uint64
}

func New(capacity int) (*Cache, error) {
    if capacity <= 0 {
        return nil, errors.New("capacity must be positive")
    }
    inner, err := lru.New[string, *User](capacity)
    if err != nil {
        return nil, err
    }
    return &Cache{inner: inner}, nil
}

func (c *Cache) Get(id string) (*User, bool) {
    u, ok := c.inner.Get(id)
    if ok {
        c.hits.Add(1)
    } else {
        c.miss.Add(1)
    }
    return u, ok
}

func (c *Cache) Set(id string, u *User) {
    c.inner.Add(id, u)
}

func (c *Cache) Stats() (hits, misses uint64) {
    return c.hits.Load(), c.miss.Load()
}

The wrapper does four useful things at once: (1) gives the cache a domain name (Cache inside package usercache), (2) hides the library type so swapping is one file change, (3) tracks hit/miss metrics, (4) validates capacity.

Example 9 — Counting evictions¶

hashicorp/golang-lru/v2 exposes an eviction callback. A very common use is just a counter.

package usercache

import (
    "sync/atomic"

    lru "github.com/hashicorp/golang-lru/v2"
)

type Cache struct {
    inner    *lru.Cache[string, *User]
    evicted  atomic.Uint64
}

func New(capacity int) (*Cache, error) {
    c := &Cache{}
    inner, err := lru.NewWithEvict[string, *User](capacity, func(_ string, _ *User) {
        c.evicted.Add(1)
    })
    if err != nil {
        return nil, err
    }
    c.inner = inner
    return c, nil
}

If evicted grows fast, your capacity is too small for the working set — a clear, measurable signal for tuning.

Example 10 — A test that demonstrates eviction order¶

It is worth writing one test that exercises the recency rules so future contributors do not break them.

func TestRecencyPromotion(t *testing.T) {
    c, _ := lru.New[string, int](3)
    c.Add("a", 1)
    c.Add("b", 2)
    c.Add("c", 3)
    // Touch "a" so it becomes MRU.
    if _, ok := c.Get("a"); !ok {
        t.Fatal("a should be present")
    }
    // Insert "d" — "b" should be evicted because it is now the LRU end.
    c.Add("d", 4)
    if _, ok := c.Get("b"); ok {
        t.Fatal("b should have been evicted")
    }
    if _, ok := c.Get("a"); !ok {
        t.Fatal("a should still be present (was just touched)")
    }
}

If that test ever fails, someone has either reordered the operations or swapped the policy. Both deserve a code review conversation.

Example 11 — singleflight to deduplicate misses¶

Two goroutines that miss the same key both call the expensive loader. For an idempotent loader this is wasteful but correct. For a non-idempotent loader (or a loader that hits a rate-limited downstream), it is wrong.

package usercache

import (
    "golang.org/x/sync/singleflight"
    lru "github.com/hashicorp/golang-lru/v2"
)

type Cache struct {
    inner *lru.Cache[string, *User]
    sf    singleflight.Group
}

func (c *Cache) GetOrLoad(id string, load func() (*User, error)) (*User, error) {
    if u, ok := c.inner.Get(id); ok {
        return u, nil
    }
    v, err, _ := c.sf.Do(id, func() (interface{}, error) {
        u, err := load()
        if err != nil {
            return nil, err
        }
        c.inner.Add(id, u)
        return u, nil
    })
    if err != nil {
        return nil, err
    }
    return v.(*User), nil
}

singleflight makes sure that concurrent callers for the same id share one in-flight load(). Each gets the same result. We cover this pattern more deeply in the middle file.

Example 12 — Contains for "is this hot?"¶

if cache.Contains("user:12345") {
    metrics.HotKeyHits.Inc()
}

Contains is like Peek — it does not promote recency. Use it for diagnostics, not application logic.

Example 13 — Cache.Resize to grow on demand¶

cache, _ := lru.New[string, int](128)
// later, under high traffic:
cache.Resize(1024)

Resize adjusts capacity. Growing is free; shrinking evicts the surplus. Use a metric (current size, evictions/min) to decide when to grow.

Example 14 — Storing immutable values¶

A cached struct can be read by many goroutines simultaneously. If you mutate it, you race. The cleanest fix is to never mutate cached values. Treat them as immutable.

// Good: build the new value outside the cache, then Add.
u := *(cached)        // copy
u.Email = newEmail    // mutate the copy
cache.Add(id, &u)     // replace the entry

The map now holds a different pointer, and any goroutine still reading the old *User is safe.

Example 15 — A loader-aware wrapper that handles errors¶

type Loader[K comparable, V any] func(K) (V, error)

type LoadingCache[K comparable, V any] struct {
    inner *lru.Cache[K, V]
    load  Loader[K, V]
}

func NewLoading[K comparable, V any](capacity int, load Loader[K, V]) (*LoadingCache[K, V], error) {
    inner, err := lru.New[K, V](capacity)
    if err != nil {
        return nil, err
    }
    return &LoadingCache[K, V]{inner: inner, load: load}, nil
}

func (c *LoadingCache[K, V]) Get(k K) (V, error) {
    if v, ok := c.inner.Get(k); ok {
        return v, nil
    }
    v, err := c.load(k)
    if err != nil {
        var zero V
        return zero, err
    }
    c.inner.Add(k, v)
    return v, nil
}

A loader-aware cache is a very common pattern. The only thing missing here is deduplication of concurrent misses for the same key — that is what singleflight adds.

Example 16 — Closing files when the cache evicts¶

fileCache, _ := lru.NewWithEvict[string, *os.File](
    32,
    func(_ string, f *os.File) {
        _ = f.Close()
    },
)

A useful idiom for bounded handle pools. The cache guarantees at most 32 open files; least-recently-used files close automatically.

Example 17 — Combining LRU with a TTL¶

A pure LRU never expires entries. If your data has a freshness deadline (e.g., 60 seconds), wrap the value with its insertion time.

type ttlEntry[V any] struct {
    val      V
    expireAt time.Time
}

type TTLCache[K comparable, V any] struct {
    inner *lru.Cache[K, ttlEntry[V]]
    ttl   time.Duration
}

func (c *TTLCache[K, V]) Get(k K) (V, bool) {
    e, ok := c.inner.Get(k)
    if !ok {
        var zero V
        return zero, false
    }
    if time.Now().After(e.expireAt) {
        c.inner.Remove(k)
        var zero V
        return zero, false
    }
    return e.val, true
}

func (c *TTLCache[K, V]) Set(k K, v V) {
    c.inner.Add(k, ttlEntry[V]{val: v, expireAt: time.Now().Add(c.ttl)})
}

A more sophisticated TTL design lives in the TTL-caches subsection; this snippet is the minimum useful combination.

Example 18 — Logging eviction rates, not events¶

var evictCount atomic.Uint64

cache, _ := lru.NewWithEvict[string, int](128, func(_ string, _ int) {
    evictCount.Add(1)
})

go func() {
    t := time.NewTicker(time.Minute)
    defer t.Stop()
    var last uint64
    for range t.C {
        cur := evictCount.Load()
        log.Printf("evictions/min=%d total=%d", cur-last, cur)
        last = cur
    }
}()

A rate-per-minute log line is friendlier to log volume than a per-eviction WARN.

Coding Patterns¶

Pattern 1 — Always defer the unlock¶

c.mu.Lock()
defer c.mu.Unlock()
// ... critical section ...

Never Lock without defer Unlock unless you have a specific reason and a single exit. The first time you return early without unlocking, you create a deadlock that survives until process restart.

Pattern 2 — Keep the critical section short¶

Inside the lock, do only the cache work. Anywhere you can compute outside the lock, do so:

// BAD: expensive serialisation inside the lock
func (c *LRU[K, V]) SetSerialised(k K, v interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()
    b, _ := json.Marshal(v) // slow! holds the lock
    c.setRaw(k, b)
}

// GOOD: serialise first, then lock
func (c *LRU[K, V]) SetSerialised(k K, v interface{}) {
    b, _ := json.Marshal(v)
    c.mu.Lock()
    defer c.mu.Unlock()
    c.setRaw(k, b)
}

Pattern 3 — One struct field per logical role¶

Keep the four fields visible and named:

type LRU[K comparable, V any] struct {
    mu       sync.Mutex          // protects items and order
    capacity int                 // immutable after New
    items    map[K]*list.Element // K -> node
    order    *list.List          // recency
}

Comments next to each field communicate the invariant. Future readers will thank you.

Pattern 4 — Validate capacity in New¶

A capacity of zero or negative is a programmer error, not a runtime condition. Panic (or return an error if your API style prefers).

func New[K comparable, V any](capacity int) *LRU[K, V] {
    if capacity <= 0 {
        panic("lru: capacity must be positive")
    }
    // ...
}

hashicorp/golang-lru/v2.New returns an error in this case — both styles are fine.

Pattern 5 — Use Peek for housekeeping, Get for application logic¶

// In a metrics dump:
for _, k := range cache.Keys() {
    if v, ok := cache.Peek(k); ok {
        export(k, v)
    }
}

// In user-facing code:
if v, ok := cache.Get(userID); ok {
    return v
}

Peek keeps the eviction order honest. Get updates recency, which is exactly what you want when the application touches a key.

Pattern 6 — Never store values you have not validated¶

// BAD
cache.Add(input, parse(input)) // parse may have returned the zero value silently

// GOOD
v, err := parse(input)
if err != nil {
    return err
}
cache.Add(input, v)

A cache holding silently-broken values is a cache that propagates failures forever.

Pattern 7 — Use the cache only as a fast path, never the only path¶

func (s *Service) GetUser(ctx context.Context, id string) (*User, error) {
    if u, ok := s.cache.Get(id); ok {
        return u, nil // fast path
    }
    u, err := s.db.GetUser(ctx, id) // slow path
    if err != nil {
        return nil, err
    }
    s.cache.Add(id, u)
    return u, nil
}

If the cache is the only path, a cache restart loses data. The database (or whatever the source of truth is) must always be reachable.

Pattern 8 — Document the staleness contract¶

// Get returns the cached user. The result may be up to 5 minutes stale.
// Callers that require fresh data must bypass this cache.
func (c *Cache) Get(id string) (*User, bool) { /* ... */ }

Stale-by-design is fine, but only if callers know. The doc comment is the contract.

Clean Code¶

• Name the cache after what it caches, not after the type. userCache is better than lruCache. The implementation can change; the role does not.
• Hide the library type behind an interface in package code. Then you can swap golang-lru for ristretto without touching call sites.

type UserCache interface {
    Get(id string) (*User, bool)
    Set(id string, u *User)
    Remove(id string)
}

• Keep capacity as a configuration value, not a constant in the code. Operators want to tune it.
• Log evictions only at a sample rate, not on every event, or the log will become the bottleneck.
• Never expose the underlying *list.Element to callers. The element is an implementation detail and exposing it leaks the linked-list contract.

Product Use and Features¶

LRU caches show up in almost every back-end Go service. A few real examples:

• HTTP middleware that caches JWT-to-user lookups for 30 seconds so the auth path does not hit the database every request.
• Image proxy that caches the resized output of (url, width, height) so the second request is served from memory.
• Feature-flag client that caches (flag, userID) evaluations so a hot flag is checked thousands of times per second without re-evaluating the rules.
• DNS resolver that caches (domain → A records) for the TTL.
• Config service that caches recently used config blobs so a sudden burst of pod restarts does not flood the upstream.
• Compiled-regex cache in a log-processing pipeline so each rule is compiled only once.

In every case the cache is a bounded fronting layer. The source of truth lives elsewhere.

Error Handling¶

The cache itself does not produce errors at the operation level — Get returns (V, bool) and Set returns nothing. Errors come from the loader that feeds the cache.

The two patterns:

Pattern A — Negative caching¶

v, err := loadFromDB(k)
if err != nil {
    cache.Add(k, sentinelError) // cache the absence
    return zero, err
}
cache.Add(k, v)

Cache the error too, so a hot key that does not exist does not hammer the database. Use a shorter TTL for negative entries (covered in TTL section).

Pattern B — Bypass the cache on error¶

v, err := loadFromDB(k)
if err != nil {
    return zero, err // do not insert anything
}
cache.Add(k, v)

Simpler. The risk is repeated database load for missing keys.

Pick A or B per use case; do not mix.

Errors during eviction callbacks¶

If your eviction callback can fail (e.g., Close returns an error), do not panic. Log and continue. The cache cannot know what to do with your error, and panicking inside the lock will tear down the program.

lru.NewWithEvict[string, *os.File](128, func(k string, f *os.File) {
    if err := f.Close(); err != nil {
        log.Printf("lru evict: close %s: %v", k, err)
    }
})

Security Considerations¶

A cache is a side channel. Treat it accordingly.

• Do not cache secrets in process memory longer than needed. Tokens, API keys, decrypted PII. If you must, document the lifetime and capacity.
• Cache poisoning. If untrusted input becomes a cache key (e.g., the requested URL), a malicious actor can fill your cache with junk and evict the hot set. Bound key length, validate input, and consider a separate cache for trusted vs untrusted keys.
• Timing channels. Cache hits are faster than misses. An attacker can probe to learn what is hot. For user-data caches, this can leak which users were recently active. For most internal services this is acceptable; for cryptographic operations it is not — use constant-time operations.
• Memory exhaustion. If capacity is a configuration value taken from untrusted input, an attacker can set it to MaxInt and OOM the process. Bound it.

The mutex itself is not a security primitive — do not rely on it to protect secrets.

Performance Tips¶

• Pick a power-of-two capacity (1024, 8192, 16384). Sharding logic later will use bitmasks.
• Pre-allocate the map with make(map[K]V, capacity). Avoids growth rehashes.
• Avoid huge value types stored by value — they balloon the map and copy on every assignment. Use pointers for values larger than ~64 bytes.
• Use generics, not interface{}. interface{} forces every value to allocate and incurs type-assertion cost on every Get.
• Do not hold the lock across I/O. Lock-Marshal-Unlock-Write, not Lock-Marshal-Write-Unlock.
• Reuse Elements where possible. Advanced trick — covered at senior level.
• Measure before sharding. A single-mutex LRU is often fast enough up to ~100 K ops/sec. Sharding matters above that.
• Treat Purge as a maintenance operation, not a hot-path call. It walks the list.
• Prefer pointer keys for large strings. A 200-byte key copied on every Get is more expensive than the actual lookup.
• Set a runtime.GC() budget if you cache pointer-heavy values. Linked-list nodes are garbage-collected one by one when the cache shrinks; large bursts can stress the GC.
• Profile with pprof before assuming a bottleneck. The mutex contention profile (runtime.SetMutexProfileFraction(1)) tells you exactly how long goroutines wait at Lock.

A quick benchmark to know your numbers¶

func BenchmarkSingleMutexLRU(b *testing.B) {
    c, _ := lru.New[int, int](1 << 14)
    for i := 0; i < 1<<14; i++ {
        c.Add(i, i)
    }
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        i := 0
        for pb.Next() {
            c.Get(i & (1<<14 - 1))
            i++
        }
    })
}

On a modern laptop this typically reports something like 200–400 ns/op single-thread, climbing toward 1500 ns/op under 16 parallel goroutines — the contention cost is visible. Sharding (middle file) brings it back down.

Best Practices¶

1. Make capacity explicit, validated, and configurable.
2. Always run tests with -race. Concurrency bugs are not visible without it.
3. Wrap the cache in an interface at the package boundary. You will switch implementations more than once.
4. Add a metric for hit-rate, eviction count, and size. Without those numbers the cache is a black box.
5. Use hashicorp/golang-lru/v2 unless you have a specific reason not to.
6. Document the eviction policy in the type name — LRUCache, LFUCache, TTLCache. A future reader should not have to guess.
7. Make the cache private to a package, with constructor and methods that mediate access. Exposing the type-parameterised struct invites misuse.
8. Keep eviction callbacks tiny and panic-free. They run inside the lock.
9. Prefer pointer values for cached items larger than ~64 bytes. Reduces copying.
10. Add an integration test that runs your service with -race for at least a minute under realistic load.
11. Pre-warm the cache at startup with the known top-N keys if the cold-start hit-rate matters.
12. Re-evaluate cache effectiveness quarterly. Working sets change as traffic patterns change.
13. Use shorter TTLs for security-sensitive data even when LRU would normally hold them longer.
14. Never log the cached value, only the key, to avoid leaking PII.

Edge Cases and Pitfalls¶

• Zero capacity. The cache stores nothing and Get always misses. Validate in New.
• Set(k, sameValue) after a Get(k). Both promote recency. Make sure your test does not assume the value is unchanged.
• Set(k, nil) where V is a pointer type. The cache stores nil and Get returns (nil, true). That true matters — it differs from "not in cache."
• Remove(k) followed immediately by Get(k) — must return miss, not the old value.
• A goroutine panics inside an eviction callback — kills the process. Wrap callbacks in defer recover() if they can panic.
• Len() is racy if read without the lock. Always lock around it.
• The cache outlives the data it caches. If the loader returns mutable structs, you may mutate cached values from outside. Defensive copy, or store immutable types.
• A Set that updates an existing key does not count as an eviction. Eviction-driven metrics will under-report churn if you confuse update with insert.
• Setting a key whose value is a large struct copies the entire struct on the way in and on the way out — pointers avoid both copies.
• Calling Keys() while another goroutine is mutating the cache is safe in hashicorp/golang-lru/v2 (it locks), but the returned slice is a snapshot. Treat it as immediately stale.
• Add returns a bool in some libraries indicating whether an eviction occurred. Different libraries name this differently. Read the docs of your specific version.
• Negative capacity from a typo (-1). hashicorp/golang-lru/v2.New returns an error; your home-grown version should panic or return error. Never silently treat it as zero.
• A long key (e.g., a 64 KB URL). The map will store the full key in the hash table; a million of these will OOM you. Truncate or hash long keys before use.
• An eviction callback that takes 5 ms stalls the whole cache for 5 ms on each insert at full capacity. Keep callbacks micro-fast.
• Using the cache from a finalizer — bad idea. Finalizers run in a separate goroutine; they may run after the cache is gone. Do not couple lifetimes.

Common Mistakes¶

Mistake 1 — Using sync.RWMutex for an LRU¶

// WRONG
func (c *LRU[K, V]) Get(k K) (V, bool) {
    c.mu.RLock()
    defer c.mu.RUnlock()
    if e, ok := c.items[k]; ok {
        c.order.MoveToFront(e) // RACE: this is a write!
        return e.Value.(*entry[K, V]).val, true
    }
    var zero V
    return zero, false
}

Get mutates c.order. Multiple readers will corrupt the list.

Fix. Either use sync.Mutex, or split into Get (write lock) and Peek (read lock).

Mistake 2 — Forgetting to delete the map entry on eviction¶

// WRONG
if c.order.Len() >= c.capacity {
    c.order.Remove(c.order.Back()) // map still has the key!
}

The map keeps growing. Subsequent Gets of an "evicted" key return a stale *list.Element pointing to a freed node — you crash on MoveToFront.

Fix. Always pair order.Remove with delete(items, key).

Mistake 3 — Eviction callback that calls back into the cache¶

cache, _ := lru.NewWithEvict[string, int](128, func(k string, v int) {
    cache.Add(k, v) // DEADLOCK
})

The eviction runs while the cache lock is held. Re-entering the cache deadlocks.

Fix. Push work to a separate goroutine, or restructure so the callback only does non-cache work.

Mistake 4 — Capturing the loop variable in a benchmark¶

for i := 0; i < N; i++ {
    go func() {
        cache.Get(keys[i]) // shared i!
    }()
}

Classic. Pass i as a parameter. (On Go 1.22+ this happens to work, but be explicit.)

Mistake 5 — Treating the cache as durable¶

cache.Add(orderID, paidStatus) // process restarts → lost

The cache is an in-memory accelerator. It is wiped on restart, on Purge, and on eviction. Never use it as the only place a fact lives.

Mistake 6 — Sharing one cache across two unrelated workloads¶

cache, _ := lru.New[string, any](1024)
cache.Add("user:123", user)
cache.Add("config:billing", cfg)

If config is hot but small, it evicts users. If users are hot, they evict config. Two caches, one per concern.

Mistake 7 — Not setting capacity from operator-visible config¶

A capacity hard-coded in source means a redeploy to tune it. In production you will retune it many times. Make it a flag or env var.

Mistake 8 — Re-using the same lock for two unrelated caches¶

// BAD
var mu sync.Mutex
var userCache = lru.NewWithLock[string, *User](128, &mu)
var sessionCache = lru.NewWithLock[string, *Session](128, &mu)

Two caches that conceptually do not share state now serialise behind one mutex. There is no benefit and a clear cost.

Mistake 9 — Catching panics inside the callback but not in the caller¶

If your eviction callback can panic (e.g., a Close on a nil pointer), recover inside the callback is not enough — the surrounding cache code may already be on the deferred-recover path. Test the callback in isolation with deliberately broken values.

Mistake 10 — Pretending the cache is the database¶

This is the cardinal sin. New engineers write code that mutates a cached object expecting the change to persist. The next eviction destroys the change. Always write to the source first, then update the cache (write-through), or invalidate the cache and let the next read repopulate (write-around).

Mistake 11 — Holding a value pointer beyond its lifetime¶

// BAD
u, _ := cache.Get(id) // u may be evicted while we hold a pointer
go heavyWork(u)        // background goroutine still has the pointer

In Go this is safe — GC keeps the object alive as long as u is reachable — but the cache no longer reflects the same object as the one your goroutine holds. If a later cache.Add(id, newU) replaces it, heavyWork runs against the old state. Document this or copy.

Mistake 12 — Treating eviction as failure¶

cache.Add quietly evicting an old key is expected. Logging at WARN every eviction will fill your logs with normal traffic. Track eviction counts, not eviction events.

Mistake 13 — Forgetting that Get returns (V, bool) not (V, error)¶

v, _ := cache.Get(k) // bool ignored; v is zero on miss
process(v)           // silently processes the zero value

Always check the boolean. A zero value is almost never what you wanted; it is the absence signal.

Mistake 14 — Storing entries with circular references¶

type Node struct {
    Children []*Node
    Parent   *Node
}
cache.Add(id, &Node{...}) // GC will still collect, but cycles slow scans

Cyclic graphs in cached values cost more GC time. If your domain has cycles, either flatten before caching or accept the cost.

Mistake 15 — Calling the cache from inside the cache's own metrics handler¶

If you expose a /metrics endpoint that iterates cache.Keys() and your metrics scrape runs every 10 seconds against a 1M-entry cache, you serialise every scrape against the cache lock. Either snapshot the keys outside the scrape path or expose aggregates only.

Common Misconceptions¶

• "LRU is the best cache policy." No — it is the most famous one. For some workloads (frequency-skewed traffic), LFU or W-TinyLFU produces measurably higher hit rates. Pick the policy after measuring.
• "sync.Map is a faster LRU." No — sync.Map has no eviction at all. It grows forever.
• "An RWMutex always helps read-heavy workloads." Not for LRU. Reads are writes.
• "Eviction happens on a timer." No (unless you build a TTL layer on top). Eviction happens only when an insert finds the cache full.
• "golang-lru is the only choice." It is the most common. dgraph-io/ristretto and vmihailenco/ristretto (TinyLFU) are common alternatives.
• "Bigger capacity is always better." Diminishing returns. A cache twice as big rarely doubles hit-rate; it often gains a few percentage points at twice the memory. Measure.
• "The cache is consistent with the database." It is eventually consistent at best. Anything that requires strict consistency must bypass the cache or use a write-through pattern.

Tricky Points¶

Trick 1 — Get must move before it returns¶

If you read the value, return, and MoveToFront later, two concurrent goroutines may interleave their reads and moves. The textbook order is: lock, look up, move, read value, unlock. Never separate them.

Trick 2 — len(items) vs order.Len()¶

By invariant they are equal. By implementation they are stored in different places. If you ever see them diverge in a debugger, you have a bug.

Trick 3 — Eviction during Set of an existing key¶

You must check for existence before the eviction branch. Otherwise an update can trigger an unnecessary eviction (or, worse, evict the very key you are about to update).

Trick 4 — Set(k, v) then Get(k) should be a hit¶

This sounds obvious. It is not under concurrency if you don't lock both ends. Imagine Set holds the lock, returns, and a concurrent Set(k, w) runs before your Get(k) even starts. Your Get returns w, not v. That is correct — but new engineers often assume "I just wrote it; I will read what I wrote." Document the relaxed ordering.

Trick 5 — Peek does not extend the lifetime¶

If you Peek a key on the LRU end, it stays on the LRU end and is next to die. This is by design but surprises people.

Trick 6 — Purge is O(n)¶

Purge() clears the cache. It walks the list and clears the map. Do not call it in a hot path — it holds the lock for the duration.

Trick 7 — Keys() returns in order, but which order?¶

hashicorp/golang-lru/v2.Keys() returns keys in MRU → LRU order (front to back). Some forks return LRU → MRU. Check the doc comment. A test that asserts order is one way to lock the contract.

Trick 8 — Resize(newCap) evicts¶

If your library has Resize(n) and n < Len(), the cache must evict Len() - n entries on the spot. Each eviction fires the callback. Do not call Resize from inside a callback.

Trick 9 — Closures captured during New outlive the cache¶

func makeCache() *lru.Cache[string, int] {
    closer := openFile()
    c, _ := lru.NewWithEvict[string, int](128, func(_ string, _ int) {
        closer.Close() // captures "closer"
    })
    return c
}

The callback keeps closer alive for as long as the cache exists. If closer holds a 10 MB buffer, that buffer stays around. Be mindful of captures.

Trick 10 — Map iteration order is unstable¶

Go maps iterate in random order. If you implement your own LRU and try to "iterate the map to find the LRU end," you get a different victim every run. That is why we use the list.

Trick 11 — Add may move and update¶

If the key exists, Add(k, newV) updates the value and promotes recency. New engineers sometimes expect Add to be insert-only and write a separate Update. The library merges them deliberately.

Trick 12 — Eviction order under ties¶

If two keys were inserted at the same instant and never touched again, which is evicted first? Whichever was inserted earlier — insertion is the implicit "last touch." But your test cannot rely on instants; use a Get to disambiguate.

Test¶

The full file is exercised in tasks.md and find-bug.md. A starter test for your own LRU:

package lru_test

import (
    "sync"
    "testing"
)

func TestBasicSetGet(t *testing.T) {
    c := New[string, int](3)
    c.Set("a", 1)
    c.Set("b", 2)
    c.Set("c", 3)
    if v, ok := c.Get("a"); !ok || v != 1 {
        t.Fatalf("want a=1, got %v ok=%v", v, ok)
    }
}

func TestEviction(t *testing.T) {
    c := New[string, int](2)
    c.Set("a", 1)
    c.Set("b", 2)
    c.Set("c", 3) // evicts "a"
    if _, ok := c.Get("a"); ok {
        t.Fatal("a should have been evicted")
    }
    if v, _ := c.Get("c"); v != 3 {
        t.Fatalf("c=%d", v)
    }
}

func TestConcurrentRace(t *testing.T) {
    c := New[int, int](100)
    var wg sync.WaitGroup
    for w := 0; w < 16; w++ {
        wg.Add(1)
        go func(seed int) {
            defer wg.Done()
            for i := 0; i < 10_000; i++ {
                k := (seed + i) % 200
                c.Set(k, i)
                _, _ = c.Get(k)
            }
        }(w)
    }
    wg.Wait()
}

Run with go test -race ./.... If the race detector is silent, your invariants survive contention.

Tricky Questions¶

1. Why doesn't an RWMutex help an LRU? Because Get mutates the recency list.
2. What is the LRU invariant? Keys in the map are exactly the entries in the list, and there are at most capacity of each.
3. Why a doubly-linked list and not a slice? Slice middle-removal is O(n); list middle-removal is O(1).
4. What happens to Get(k) when k was just evicted by another goroutine? It returns miss. There is no half-state because each operation holds the lock.
5. What is the worst-case behaviour of an LRU under a one-time full scan? The hot set is evicted; hit-rate collapses until traffic returns to normal. Scan resistance requires LFU or TinyLFU.
6. Why does hashicorp/golang-lru/v2.New return an error? It validates capacity > 0. The error is the library's way of avoiding a panic in user code.
7. Is cache.Len() safe to call from many goroutines? Yes, because the library locks internally. Your own LRU must too.
8. What is the cost of a Get hit? Map lookup (O(1) average), MoveToFront (O(1)), a pointer dereference, an unlock. A few hundred nanoseconds on modern hardware.
9. What is the cost of a Set that evicts? Two map operations, two list operations, the eviction callback if any, plus the allocation of a new Element. Still O(1) but with a higher constant.
10. What is a "ghost" entry in a cache? An entry the cache remembers seeing but did not keep. Used by 2Q and ARC to detect recency vs frequency. Out of scope at junior level.
11. What is the difference between Add and Set? Add is the hashicorp/golang-lru/v2 name; Set is the name used by some other libraries. Both mean "insert or update."
12. What does Add return? A bool indicating whether an eviction happened to make room. Useful for diagnostics.
13. Can Get panic? Not on its own — only if your value is nil and you dereference it without checking ok.
14. What if the loader returns nil, nil? Your code stores nil. Future Gets return (nil, true). Document whether nil is a legal cached value or use a sentinel.
15. Does Purge reset metrics? No. Purge clears the cache; the hit/miss counters are yours.
16. Why is the eviction callback synchronous? Because the cache must wait for the callback to finish before considering the slot free. Async callbacks would race with the slot reuse.
17. Can two goroutines safely call Add(k, v) and Get(k) for the same k? Yes — the lock serialises them. Which goes first is timing-dependent.
18. What does Resize do? Changes capacity. If the new capacity is smaller than Len, the surplus is evicted immediately, oldest first.
19. Why is container/list documented as "not safe for concurrent use"? Because MoveToFront is multiple pointer writes that must appear atomic; without a lock, concurrent calls can corrupt the list.
20. What happens if I forget the eviction callback? Nothing — the entry is dropped silently. Resources you intended to free will leak.

Cheat Sheet¶

PICK CONCURRENT LRU WHEN:
  * Read-heavy workload, hot subset, bounded memory.
  * In-process speed required (sub-microsecond).
  * You can tolerate eventual consistency with the source.

AVOID WHEN:
  * No locality (every key is fresh).
  * Strict consistency required.
  * Workload bigger than RAM.

INVARIANT:
  len(items) == order.Len()  AND  items keys == order entries  AND  count <= capacity

OPERATIONS:
  Get(k):  if hit, MoveToFront then return value.
  Set(k,v): if exists, update + MoveToFront. else if full, evict Back. PushFront new.
  Remove(k): list.Remove + delete(map,k).

CONCURRENCY:
  sync.Mutex around all ops. RWMutex is WRONG for an LRU's Get.

LIBRARY:
  hashicorp/golang-lru/v2.New[K, V](capacity)
  Methods: Add, Get, Peek, Remove, Len, Purge, Keys.
  NewWithEvict to add a callback (runs under lock — keep it short).

COMMON BUGS:
  Forget to delete map entry on eviction.
  RWMutex used because "Get is a read" (it isn't).
  Eviction callback re-enters the cache (deadlock).
  Capacity hardcoded.

A production checklist before merging the cache PR¶

When you propose adding an in-process cache to a service, the reviewer should be able to tick all of these. Internalising the list saves you a round of comments.

• The cache type is named for its role (UserCache, not LRUCache).
• The implementation is hidden behind an interface (UserCache interface { ... }).
• Capacity is a configuration value, not a constant.
• Capacity is validated; zero or negative is rejected.
• The cache is initialised once per process, not per request.
• There is a metric for hit rate (counter for hits, counter for misses).
• There is a metric for eviction rate.
• There is a metric for current size.
• The eviction callback (if any) is non-blocking and panic-free.
• All public methods that touch the cache are concurrency-safe (you used the library, or you wrote tests with -race).
• You have a test for basic Set/Get/Eviction.
• You have a test that runs under -race with at least 8 goroutines.
• You documented the staleness contract in a doc comment.
• You documented the cache invalidation path (or stated explicitly that there is none).
• You used singleflight if concurrent misses must not fan out.
• You have a runbook entry for "cache hit-rate dropped" troubleshooting.

A reviewer who sees this list addressed will approve fast. A reviewer who sees half of it missing will ask all the questions.

Observability deep dive¶

A cache without metrics is a black box. The minimum useful set is four counters and one gauge:

var (
    cacheHits      atomic.Uint64
    cacheMisses    atomic.Uint64
    cacheEvictions atomic.Uint64
    cacheUpdates   atomic.Uint64
    cacheSize      atomic.Int64
)