Concurrent TTL Caches — Middle Level¶

Table of Contents¶

1. Where We Left Off
2. Why a Heap?
3. Designing the Expiration Heap
4. Implementing the Heap-Backed Cache
5. Handling Updates: Stale Heap Entries
6. Switching to sync.Map for Reads
7. Combining sync.Map with a Heap
8. Batched Sweeps
9. Time-Budgeted Sweeps
10. Jittered TTL
11. Thundering Herds in Detail
12. singleflight to the Rescue
13. Negative Caching
14. Stale-While-Revalidate
15. Refresh-Ahead
16. Eviction Policies Overview
17. Implementing a Bounded TTL Cache
18. Choosing Between ristretto, bigcache, and freecache
19. Observability: Hits, Misses, and Latency Histograms
20. Distributed Caches Briefly Considered
21. Cache Warming Strategies
22. Cache Stampede Patterns Beyond Single-Flight
23. Testing at the Middle Level
24. Common Mid-Level Mistakes
25. Worked Example: API Gateway Cache
26. Worked Example: Token Validation Cache
27. Cheat Sheet
28. Self-Assessment Checklist
29. Summary
30. Further Reading

Where We Left Off¶

At the junior level we built a TTL cache with:

• map[string]entry protected by sync.RWMutex
• A single sweep goroutine that walked the whole map every interval
• Per-entry TTLs, hit/miss counters, clean shutdown

That cache has clear limits. Three of them dominate at the middle level:

1. The sweeper is O(N). Walking a million entries while holding the write lock stalls every reader.
2. Hot keys cause thundering herds. When a popular key expires and 1,000 goroutines simultaneously miss, every one of them calls the upstream — 999 calls more than necessary.
3. There is no size bound. Memory grows with the working set; an attacker (or a misconfigured client) can drive it to OOM.

This file fixes the first two. The third — bounded size with intelligent eviction — is mostly the senior file's territory, but we introduce it here through ristretto, bigcache, and freecache.

By the end of this file you will be able to:

• Design and implement a heap-backed TTL cache where sweeps are O(log N) amortised per expiration, not O(N) per tick
• Combine sync.Map with a heap and explain the trade-offs
• Add jitter to TTLs to flatten herds and explain why it works
• Use golang.org/x/sync/singleflight to coalesce concurrent misses
• Choose between ristretto, bigcache, and freecache based on workload shape
• Implement stale-while-revalidate and refresh-ahead patterns
• Add Prometheus-style metrics to a cache for observability

Why a Heap?¶

In the junior cache, the sweeper visits every entry — alive or dead — on every tick. That is wasteful when most entries are alive. A smarter sweeper should know which entry expires next and wake up only when needed.

The classic data structure for "smallest priority next" is a min-heap, indexed by expiration time. Insertion and removal are O(log N). The minimum (next expiring entry) is at the root — O(1) to inspect.

The strategy:

• Each cache entry, when inserted, also pushes a {expiresAt, key} pair onto the heap.
• The sweeper does NOT use a fixed interval. It blocks on a timer set to the root's expiration time.
• When the timer fires, the sweeper pops everything from the heap whose expiration is now in the past.
• It then resets the timer to the new root.

The result: sweeps cost O(k log N) where k is the number of entries that expired since the last sweep — almost always tiny. The cache stops doing work between expirations.

A complication: when a Set overwrites an entry, the old heap entry becomes stale (it points to a (key, oldExpiresAt) that is no longer in the cache). We have two ways to handle this — lazy stale dropping or index-based removal — discussed below.

Designing the Expiration Heap¶

A container/heap-backed structure:

package cache

import (
    "container/heap"
    "time"
)

type heapItem struct {
    key       string
    expiresAt time.Time
    index     int
}

type expirationHeap []*heapItem

func (h expirationHeap) Len() int { return len(h) }
func (h expirationHeap) Less(i, j int) bool {
    return h[i].expiresAt.Before(h[j].expiresAt)
}
func (h expirationHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
    h[i].index = i
    h[j].index = j
}
func (h *expirationHeap) Push(x any) {
    item := x.(*heapItem)
    item.index = len(*h)
    *h = append(*h, item)
}
func (h *expirationHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index = -1
    *h = old[:n-1]
    return item
}

This is the standard container/heap boilerplate. The index field on each item lets us remove an arbitrary item from the heap in O(log N) via heap.Remove. That capability is essential for handling Delete and Set correctly — without it, the heap fills with dead entries.

Implementing the Heap-Backed Cache¶

Now we wire the map and the heap together:

package cache

import (
    "container/heap"
    "sync"
    "time"
)

type entry struct {
    value     string
    expiresAt time.Time
    heapIdx   *heapItem // back-pointer for O(log N) removal
}

type HeapCache struct {
    mu     sync.Mutex
    data   map[string]entry
    heap   expirationHeap

    timer    *time.Timer
    stop     chan struct{}
    stopOnce sync.Once
    done     chan struct{}
}

func NewHeapCache() *HeapCache {
    c := &HeapCache{
        data: make(map[string]entry),
        heap: expirationHeap{},
        stop: make(chan struct{}),
        done: make(chan struct{}),
    }
    heap.Init(&c.heap)
    c.timer = time.NewTimer(time.Hour) // arbitrary far future
    if !c.timer.Stop() {
        <-c.timer.C
    }
    go func() {
        defer close(c.done)
        c.run()
    }()
    return c
}

func (c *HeapCache) SetWithTTL(key, value string, ttl time.Duration) {
    expiresAt := time.Now().Add(ttl)
    c.mu.Lock()
    defer c.mu.Unlock()

    // Remove any existing heap entry for this key.
    if old, ok := c.data[key]; ok && old.heapIdx != nil {
        heap.Remove(&c.heap, old.heapIdx.index)
    }

    item := &heapItem{key: key, expiresAt: expiresAt}
    heap.Push(&c.heap, item)
    c.data[key] = entry{value: value, expiresAt: expiresAt, heapIdx: item}

    c.rescheduleLocked()
}

func (c *HeapCache) Get(key string) (string, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.data[key]
    if !ok || time.Now().After(e.expiresAt) {
        return "", false
    }
    return e.value, true
}

func (c *HeapCache) Delete(key string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.data[key]; ok {
        if e.heapIdx != nil {
            heap.Remove(&c.heap, e.heapIdx.index)
        }
        delete(c.data, key)
    }
    c.rescheduleLocked()
}

func (c *HeapCache) rescheduleLocked() {
    if !c.timer.Stop() {
        select {
        case <-c.timer.C:
        default:
        }
    }
    if len(c.heap) == 0 {
        return
    }
    delay := time.Until(c.heap[0].expiresAt)
    if delay < 0 {
        delay = 0
    }
    c.timer.Reset(delay)
}

func (c *HeapCache) run() {
    for {
        select {
        case <-c.timer.C:
            c.evictExpired()
        case <-c.stop:
            return
        }
    }
}

func (c *HeapCache) evictExpired() {
    now := time.Now()
    c.mu.Lock()
    defer c.mu.Unlock()
    for len(c.heap) > 0 && !c.heap[0].expiresAt.After(now) {
        item := heap.Pop(&c.heap).(*heapItem)
        if e, ok := c.data[item.key]; ok && e.heapIdx == item {
            delete(c.data, item.key)
        }
        // else: stale heap entry (key was overwritten or deleted) — skip.
    }
    c.rescheduleLocked()
}

func (c *HeapCache) Close() {
    c.stopOnce.Do(func() { close(c.stop) })
    <-c.done
}

Notice the back-pointer (heapIdx) and the e.heapIdx == item identity check. Together they make the heap entry a canonical reference: if an entry's heapIdx no longer matches the item we just popped, the item is stale and we ignore it.

We also use a Mutex (not RWMutex) because every operation now mutates either the heap or the map. There is no read-only path worth speeding up.

Handling Updates: Stale Heap Entries¶

Strategy A (above): canonical heap entry. Each cache entry stores a back-pointer to its heap item. On overwrite or delete, we explicitly heap.Remove the old item. The heap stays compact.

Strategy B: lazy stale dropping. We never remove old heap items on overwrite. Instead, when the sweeper pops an item, it checks whether the cache entry still references this exact item — and skips otherwise. The heap is allowed to grow with stale entries.

// Strategy B set: do not remove old heap entries
func (c *Cache) Set(k, v string) {
    expiresAt := time.Now().Add(c.ttl)
    item := &heapItem{key: k, expiresAt: expiresAt}
    c.mu.Lock()
    heap.Push(&c.heap, item)
    c.data[k] = entry{value: v, expiresAt: expiresAt, heapIdx: item}
    c.mu.Unlock()
    // No removal of any old heap entry.
}

// Strategy B sweep: skip items that are no longer the canonical
func (c *Cache) evictExpired() {
    now := time.Now()
    c.mu.Lock()
    defer c.mu.Unlock()
    for len(c.heap) > 0 && !c.heap[0].expiresAt.After(now) {
        item := heap.Pop(&c.heap).(*heapItem)
        if e, ok := c.data[item.key]; ok && e.heapIdx == item && !time.Now().Before(e.expiresAt) {
            delete(c.data, item.key)
        }
    }
}

Strategy B has two implementation costs:

• The heap may grow large (one stale entry per Set that updates an existing key).
• The sweeper does work for each stale entry it encounters.

But it avoids the O(log N) overhead of heap.Remove on every Set. For workloads where keys are mostly read and rarely overwritten, strategy B is faster overall. For workloads with frequent updates, strategy A wins.

Choose deliberately, document the choice in the code.

Switching to sync.Map for Reads¶

sync.Map is Go's purpose-built concurrent map. Internally it has a read map served lock-free and a dirty map for fresh writes. The lock-free read path is faster than RWMutex.RLock for high-concurrency lookups.

For a TTL cache where reads vastly outnumber writes (typical 95/5 split), sync.Map can beat map + RWMutex by 2–3× on reads. The catch: writes are slower, and iteration (Range) is awkward and only loosely consistent.

The minimum sync.Map-backed TTL cache:

package cache

import (
    "sync"
    "time"
)

type syncMapEntry struct {
    value     string
    expiresAt time.Time
}

type SyncMapCache struct {
    data sync.Map // string -> syncMapEntry
    ttl  time.Duration
}

func (c *SyncMapCache) Set(key, value string) {
    c.data.Store(key, syncMapEntry{
        value:     value,
        expiresAt: time.Now().Add(c.ttl),
    })
}

func (c *SyncMapCache) Get(key string) (string, bool) {
    v, ok := c.data.Load(key)
    if !ok {
        return "", false
    }
    e := v.(syncMapEntry)
    if time.Now().After(e.expiresAt) {
        c.data.Delete(key) // safe; sync.Map handles concurrent delete
        return "", false
    }
    return e.value, true
}

func (c *SyncMapCache) Delete(key string) {
    c.data.Delete(key)
}

What we lost: efficient sweep. sync.Map.Range is allowed to skip newly-added keys, may visit deleted keys, and provides no progress guarantees. Walking sync.Map for sweeping is slower than walking a plain map, and you cannot iterate while holding "the" lock because there is no single lock.

The conclusion most engineers reach: sync.Map is excellent for the read path but a poor fit for sweeping. The natural composition is "use sync.Map for reads, drive eviction through an external structure (a heap) that the sweeper owns."

Combining sync.Map with a Heap¶

The hybrid layout:

+---------------------+        +-----------------------+
|  sync.Map           |        |  expirationHeap       |
|  (key -> entry)     |        |  (priority queue of   |
|  served lock-free   |        |   expiration items)   |
+---------------------+        +-----------------------+
        ^                                 ^
        |                                 |
        | Reads / Writes / Deletes        | Sweeper only
        |                                 |
   application code                  sweeper goroutine

Reads go to sync.Map. Writes go to both (insert into sync.Map, push onto heap). The sweeper pops items from the heap whose expiresAt has passed, verifies via sync.Map.Load that the entry is still the latest (matching expiration), and Deletes if so.

Sketch:

type entry struct {
    value     string
    expiresAt time.Time
}

type HybridCache struct {
    data sync.Map
    heap *minHeap     // protected by heapMu
    heapMu sync.Mutex

    timer *time.Timer
    stop  chan struct{}
}

func (c *HybridCache) Set(key, value string, ttl time.Duration) {
    e := entry{value: value, expiresAt: time.Now().Add(ttl)}
    c.data.Store(key, e)

    c.heapMu.Lock()
    c.heap.push(&heapItem{key: key, expiresAt: e.expiresAt})
    c.rescheduleLocked()
    c.heapMu.Unlock()
}

func (c *HybridCache) Get(key string) (string, bool) {
    v, ok := c.data.Load(key)
    if !ok {
        return "", false
    }
    e := v.(entry)
    if time.Now().After(e.expiresAt) {
        return "", false
    }
    return e.value, true
}

func (c *HybridCache) evict() {
    now := time.Now()
    c.heapMu.Lock()
    defer c.heapMu.Unlock()
    for c.heap.len() > 0 && !c.heap.peek().expiresAt.After(now) {
        item := c.heap.pop()
        if v, ok := c.data.Load(item.key); ok {
            e := v.(entry)
            // Only delete if the heap item matches the current entry's expiration.
            if e.expiresAt.Equal(item.expiresAt) {
                c.data.Delete(item.key)
            }
        }
    }
    c.rescheduleLocked()
}

Trade-offs:

• Hot path (Get) is lock-free. Excellent throughput.
• Set now takes a mutex (for the heap) on every call. Worse than the pure sync.Map approach.
• The heap grows on every Set, even when overwriting; stale entries are dropped lazily by the sweeper.

For workloads with ~10:1 read:write, the hybrid wins clearly. For write-heavy workloads, the heap mutex starts to dominate; a sharded heap or per-shard cache (senior level) becomes necessary.

Batched Sweeps¶

A complementary technique: instead of holding the lock for one long sweep that visits every entry, do many short sweeps that release the lock between batches.

func (c *Cache) batchedSweep(batchSize int) {
    for {
        now := time.Now()
        c.mu.Lock()
        evicted := 0
        // Snapshot up to batchSize keys to check this round.
        snapshot := make([]string, 0, batchSize)
        for k := range c.data {
            snapshot = append(snapshot, k)
            if len(snapshot) >= batchSize {
                break
            }
        }
        for _, k := range snapshot {
            if e, ok := c.data[k]; ok && now.After(e.expiresAt) {
                delete(c.data, k)
                evicted++
            }
        }
        done := evicted == 0 // crude termination
        c.mu.Unlock()
        if done {
            return
        }
        // Let other goroutines breathe before the next batch.
        runtime.Gosched()
    }
}

This is a deliberate trade: total wall-clock time of the sweep increases (more lock acquire/release cycles), but the maximum lock-held duration drops. p99 of reader latency improves dramatically.

A subtlety: ranging over a Go map gives keys in randomised order, so successive batches do not consistently cover the entire map. To guarantee full coverage you must keep a per-sweep iterator state. For a cache built on a heap, this problem disappears — the heap itself imposes order and the sweeper visits items in expiration order.

Time-Budgeted Sweeps¶

A variant of batched sweeps: limit by time, not count.

func (c *Cache) sweepWithBudget(budget time.Duration) {
    deadline := time.Now().Add(budget)
    for time.Now().Before(deadline) {
        c.mu.Lock()
        progress := false
        for k, e := range c.data {
            if time.Now().After(e.expiresAt) {
                delete(c.data, k)
                progress = true
            }
            if time.Now().After(deadline) {
                break
            }
        }
        c.mu.Unlock()
        if !progress {
            return
        }
        runtime.Gosched()
    }
}

This produces a sweeper that "does its best in N milliseconds and then yields." Useful when you have a hard p99 latency budget — the sweeper provably cannot stall any reader for more than the budget plus one operation.

The cost: very large caches may grow arrears (the sweeper cannot keep up). Pair with metrics to detect "sweeper-falling-behind" so you can alert.

Jittered TTL¶

A perfectly synchronised cache is a bad cache. When you insert 100,000 entries at the same instant with the same TTL, they all expire in the same instant. The next reader for any of them triggers a miss; if your service is busy, dozens or hundreds of expirations land in the same microsecond and the upstream is hit by a wave.

The fix: add a small random offset to each TTL.

import "math/rand/v2"

func (c *Cache) Set(key, value string) {
    jitter := time.Duration(rand.Int64N(int64(c.jitterMax)))
    expiresAt := time.Now().Add(c.ttl + jitter)
    // ...
}

A typical jitter is 10% of the TTL: for ttl=60s, jitter is 0–6 s. Entries inserted at t=0 expire scattered between t=60 and t=66 instead of all at t=60.

Why does this work? Because the work the upstream does during a herd is dominated by the coincidence of misses. Spreading misses out by 6 seconds reduces the peak rate of upstream calls by roughly a factor of peakRate / 6s — orders of magnitude in practice.

The cost of jitter is tiny — at most 10% extra staleness for the average entry. For most applications this is invisible.

Direction of jitter. You can add jitter to the high side (longer life) or the low side (shorter life). Adding to the high side is conservative — entries live at least as long as the nominal TTL. Adding to the low side means entries may expire early, but you can use it to randomise refreshes without changing the cache's "freshness guarantee." Pick based on which property matters more.

Thundering Herds in Detail¶

Let us look at the herd mechanism carefully because it is the most consequential subtle failure mode in caching.

The setup:

• Hot key K is cached. TTL = 60 s.
• At time t, the entry expires.
• At time t, 5,000 requests for K arrive concurrently.

In the junior cache, every request:

1. Calls Get("K") — miss.
2. Calls upstream — which takes 50 ms.
3. Calls Set("K", v).

Steps 1 and 3 are fast. Step 2 is what hurts. With 5,000 concurrent step-2 calls, the upstream sees 5,000× its normal QPS and probably falls over. Worst case: the upstream's threads get tied up, latency explodes, and every downstream service that depends on it degrades.

This is "thundering herd," "stampede," "dog-pile," "cache stampede" — all the same phenomenon. Three classes of fix:

1. Singleflight. Only one in-flight request per key; others wait for its result.
2. Refresh-ahead. Refresh hot keys before they expire so misses never happen for them.
3. Stale-while-revalidate. Serve a stale value while a single goroutine refreshes in the background.

Each has its place. Singleflight is the universal first defence.

singleflight to the Rescue¶

golang.org/x/sync/singleflight is a small package — about 200 lines — that solves exactly this problem. It exposes one type, Group, with one main method:

func (g *Group) Do(key string, fn func() (interface{}, error)) (v interface{}, err error, shared bool)

Semantics: if multiple goroutines call Do with the same key simultaneously, only the first goroutine actually executes fn. The others block until fn returns and receive the same result.

Integration with a TTL cache:

package cache

import (
    "sync"
    "time"

    "golang.org/x/sync/singleflight"
)

type LoaderCache struct {
    mu    sync.RWMutex
    data  map[string]entry
    ttl   time.Duration
    group singleflight.Group
    load  func(key string) (string, error)
}

type entry struct {
    value     string
    expiresAt time.Time
}

func (c *LoaderCache) Get(key string) (string, error) {
    c.mu.RLock()
    e, ok := c.data[key]
    c.mu.RUnlock()
    if ok && time.Now().Before(e.expiresAt) {
        return e.value, nil
    }

    v, err, _ := c.group.Do(key, func() (interface{}, error) {
        // Re-check under singleflight in case another goroutine just filled it.
        c.mu.RLock()
        e, ok := c.data[key]
        c.mu.RUnlock()
        if ok && time.Now().Before(e.expiresAt) {
            return e.value, nil
        }
        val, err := c.load(key)
        if err != nil {
            return "", err
        }
        c.mu.Lock()
        c.data[key] = entry{value: val, expiresAt: time.Now().Add(c.ttl)}
        c.mu.Unlock()
        return val, nil
    })
    if err != nil {
        return "", err
    }
    return v.(string), nil
}

Now if 5,000 goroutines simultaneously miss on K, only one calls load. The other 4,999 wait inside Do and receive the loaded value when it returns. Upstream QPS for K drops from 5,000 to 1.

The cost is small:

• An extra map (singleflight.Group's internal calls map).
• A goroutine-yield per waiting goroutine.
• Slight bookkeeping inside Do.

Edge case: load panics. Do recovers the panic and re-panics in the caller's goroutine. All waiting goroutines receive the same panic. You may want to wrap your load in defensive code.

Edge case: load returns an error. All waiting goroutines receive that same error. Decision: do you cache the error (negative caching) or let the next reader retry? Discussed below.

Edge case: stale results. If load takes 5 s and 5,000 readers are waiting, the result they receive is up to 5 s "old" by the time they see it. For most caching purposes this is fine; for time-sensitive operations, beware.

Forget(key). Do keeps the call alive until it returns. If you want to cancel an in-flight call for a key (because, say, you just received a Delete), call Forget(key). Subsequent calls will start a fresh Do instead of joining the old one.

Negative Caching¶

What happens when load returns "not found" or another well-defined error? Three options:

1. Do not cache. Every miss re-calls load. If the key really does not exist, every reader pays the full cost.
2. Cache the absence. Store a sentinel "miss" entry with a (usually shorter) TTL. Readers see the sentinel and return "not found" without calling load.
3. Cache the error. Same as 2, but distinguish "not found" from "load failed."

Option 2 is the typical choice for DNS-like lookups: cache successes for successTTL (e.g. 60 s) and absences for negativeTTL (e.g. 5 s). The shorter negative TTL guards against "the key was just created elsewhere and I'm caching a no for too long."

Sketch:

type entry struct {
    value     string
    found     bool
    expiresAt time.Time
}

func (c *Cache) Get(k string) (string, bool, error) {
    c.mu.RLock()
    e, ok := c.data[k]
    c.mu.RUnlock()
    if ok && time.Now().Before(e.expiresAt) {
        return e.value, e.found, nil
    }
    v, found, err := c.load(k) // load returns ("", false, nil) for "not found"
    if err != nil {
        return "", false, err
    }
    ttl := c.successTTL
    if !found {
        ttl = c.negativeTTL
    }
    c.mu.Lock()
    c.data[k] = entry{value: v, found: found, expiresAt: time.Now().Add(ttl)}
    c.mu.Unlock()
    return v, found, nil
}

Negative caching especially helps when an attacker can probe for non-existent keys: without it, every probe is a full upstream call.

Stale-While-Revalidate¶

A pattern borrowed from HTTP caching (RFC 5861). The cache serves the stale value to readers while spawning a background refresh. Readers never see a miss; the cache transitions from "fresh" → "stale, serving but refreshing" → "fresh" in the background.

Sketch:

type entry struct {
    value      string
    freshUntil time.Time
    staleUntil time.Time
    refreshing atomic.Bool
}

func (c *Cache) Get(k string) (string, bool) {
    c.mu.RLock()
    e, ok := c.data[k]
    c.mu.RUnlock()
    if !ok || time.Now().After(e.staleUntil) {
        return "", false // genuine miss
    }
    if time.Now().After(e.freshUntil) {
        // Stale — serve but trigger background refresh.
        if e.refreshing.CompareAndSwap(false, true) {
            go c.refresh(k)
        }
    }
    return e.value, true
}

func (c *Cache) refresh(k string) {
    defer func() {
        c.mu.Lock()
        if e, ok := c.data[k]; ok {
            e.refreshing.Store(false)
            c.data[k] = e
        }
        c.mu.Unlock()
    }()
    v, err := c.load(k)
    if err != nil {
        return // keep serving stale
    }
    c.mu.Lock()
    now := time.Now()
    c.data[k] = entry{
        value:      v,
        freshUntil: now.Add(c.freshTTL),
        staleUntil: now.Add(c.freshTTL + c.staleWindow),
    }
    c.mu.Unlock()
}

The reader's worst-case latency is now O(map lookup), never O(upstream call). The cost: callers may see data up to freshTTL + staleWindow old when the upstream is slow.

Variant: combine with singleflight to ensure only one background refresh per key. Without it, CompareAndSwap already prevents concurrent refreshes for a key, but you still spawn a fresh goroutine per stale read.

Deep Dive: SWR Edge Cases¶

Stale-while-revalidate sounds simple but has interesting edge cases.

Edge 1: refresh fails. What if loader errors during background refresh? We must decide:

• Keep serving stale forever? Eventually wrong.
• Stop serving stale immediately? Forces a synchronous reload on next reader.
• Extend stale window briefly, retry? Most robust.

Typical: extend the stale window for a small "grace period" (e.g. 10 s) and try again. After N failed attempts, evict.

Edge 2: refresh storms. If 1,000 readers see the same stale entry within microseconds, the refreshing.CompareAndSwap ensures only one wins the right to refresh. Good. But the other 999 returns are happening concurrently with one in-flight refresh — fine.

Edge 3: refresh completes after invalidation. Reader B calls Invalidate(k) while goroutine A is mid-refresh. When A returns, it overwrites the just-invalidated entry. Solutions:

• Check inside the refresh callback whether the key is still wanted.
• Use a generation counter; refresh only commits if its generation matches.

Edge 4: client cancellation. If the request that triggered the stale-read is cancelled, the refresh goroutine still runs to completion. This is generally desired (the next request benefits) but can hide bugs in tests.

These are not deal-breakers — SWR is a hugely valuable pattern — but you must think about each before shipping.

Refresh-Ahead¶

A more proactive pattern. The cache schedules a background refresh some fraction (say, 80%) of the way through each TTL.

func (c *Cache) Set(k, v string) {
    expiresAt := time.Now().Add(c.ttl)
    refreshAt := time.Now().Add(time.Duration(float64(c.ttl) * 0.8))
    c.mu.Lock()
    c.data[k] = entry{value: v, expiresAt: expiresAt}
    c.mu.Unlock()
    time.AfterFunc(time.Until(refreshAt), func() {
        if !c.stillNeeded(k) {
            return
        }
        if v, err := c.load(k); err == nil {
            c.Set(k, v)
        }
    })
}

Pros: hot keys are kept warm; misses are rare even at TTL boundaries.

Cons: every Set spawns a timer. For 1M entries, you have 1M pending timers. The Go runtime handles them efficiently (single heap), but the memory adds up. Better: refresh only keys with recent read activity.

Refresh-ahead is most appealing when the working set is small and the upstream is reliable.

Deep Dive: Refresh-Ahead vs Soft TTL¶

Some literature calls "refresh-ahead" by the alias "soft TTL." The pattern:

• Each entry has a soft TTL (refreshAt) and a hard TTL (expiresAt).
• Reads before refreshAt: just return. No background work.
• Reads between refreshAt and expiresAt: serve the value AND schedule a background refresh.
• Reads after expiresAt: synchronous refresh (miss).

The combined behaviour:

• Hot keys are refreshed in the background and never miss synchronously.
• Cold keys (read once, then forgotten) miss on the first read after expiresAt but waste no background work.

Implementation is essentially SWR + per-read trigger:

func (c *Cache) Get(k string) (string, bool) {
    c.mu.RLock()
    e, ok := c.data[k]
    c.mu.RUnlock()
    if !ok || time.Now().After(e.hardExpiresAt) {
        return "", false
    }
    if time.Now().After(e.softExpiresAt) {
        if e.refreshing.CompareAndSwap(false, true) {
            go c.refresh(k)
        }
    }
    return e.value, true
}

A reasonable choice of softExpiresAt is ~70-80% of the way through the hard TTL. Tune by measuring how often readers fall into the "synchronous miss" path.

Eviction Policies Overview¶

So far our cache has no size bound. Real production caches do. The standard policies:

• LRU (Least Recently Used). Evict the entry that has not been accessed for the longest time. Implementation: doubly-linked list + map.
• LFU (Least Frequently Used). Evict the entry with the lowest access count. Implementation: priority queue + map.
• FIFO (First In, First Out). Evict the oldest entry by insertion order. Simplest.
• Random. Evict a uniformly-random entry. Surprisingly competitive in many workloads.
• TinyLFU. Probabilistic admission with frequency sketches. Used by ristretto. State-of-the-art for many workloads.

For TTL caches, eviction kicks in when the cache hits its size cap before entries naturally expire. Without size bounds, eviction is only ever driven by TTL.

The classic "TTL + LRU" combination — exemplified by hashicorp/golang-lru/v2/expirable — is the dominant choice in production Go services because:

• TTL handles the "data went stale" problem.
• LRU handles the "data has not been used in a while" problem.
• Together they bound both staleness and size.

Detailed eviction policies are the subject of the next subsection (LRU concurrent caches). Here we cover only the bare minimum needed to bound a TTL cache's size.

Implementing a Bounded TTL Cache¶

The simplest bound is "cap entry count and drop randomly when over." It is not the most efficient eviction policy but it is dead simple:

func (c *Cache) Set(k, v string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if _, ok := c.data[k]; !ok && len(c.data) >= c.maxEntries {
        // Drop one random entry.
        for randomKey := range c.data {
            delete(c.data, randomKey)
            break
        }
    }
    c.data[k] = entry{value: v, expiresAt: time.Now().Add(c.ttl)}
}

Map iteration order in Go is randomised, so for k := range c.data { delete; break } actually drops a random entry — no extra randomness needed.

Better policies require auxiliary data structures (linked list for LRU; heap or sketch for LFU). For production-quality bounded caches, prefer a library like ristretto or hashicorp/golang-lru that has thought through the trade-offs.

Choosing Between ristretto, bigcache, and freecache¶

Three of the most popular high-performance Go caches. They make very different trade-offs.

ristretto¶

import "github.com/dgraph-io/ristretto"

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 1e7,     // number of keys to track frequency of (10× cache size)
    MaxCost:     1 << 30, // maximum cost of cache (1 GB)
    BufferItems: 64,      // number of keys per Get buffer
})
if err != nil {
    log.Fatal(err)
}
cache.SetWithTTL("k", "v", 1, time.Minute) // (key, value, cost, ttl)
cache.Wait()
v, ok := cache.Get("k")

Internals:

• TinyLFU admission policy with a count-min sketch for frequency estimation.
• Sharded internal storage with low contention.
• Async metadata updates via batched ring buffers (BufferItems).
• Sampled LRU eviction within shards.
• Cost-based bounds (not entry count) — you pay attention to value size rather than just count.

When to use ristretto:

• Read-heavy workloads with diverse keys.
• You want sophisticated admission to keep one-hit-wonders out.
• You can express bounds as memory cost rather than item count.
• You can tolerate eventually-consistent stats and slightly delayed writes.

When not to use it:

• Strict consistency requirements ("a Set must be visible to the next Get" is not guaranteed without Wait()).
• Very small caches where the metadata overhead dominates.
• You need to iterate the cache contents reliably.

bigcache¶

import "github.com/allegro/bigcache/v3"

cache, err := bigcache.New(context.Background(), bigcache.DefaultConfig(10*time.Minute))
if err != nil {
    log.Fatal(err)
}
_ = cache.Set("k", []byte("v"))
v, err := cache.Get("k")

Internals:

• Shards (default 1,024) each protected by its own mutex.
• Each shard holds keys/values in a single contiguous byte slice — a giant ring buffer per shard.
• No per-entry GC overhead because all entries live inside []bytes and the GC sees a single allocation per shard.
• TTL applies cache-wide; entries are evicted FIFO within their shard when the buffer fills.

When to use bigcache:

• Huge caches (hundreds of millions of entries).
• You can serialise values to []byte cheaply.
• GC pause is more concerning than CPU.
• A simple FIFO/TTL policy is acceptable.

When not to use it:

• You need LRU or LFU.
• Values are large pointers/structs (the serialisation cost is bad).
• You need per-entry TTLs.

freecache¶

import "github.com/coocood/freecache"

cache := freecache.NewCache(100 * 1024 * 1024) // 100 MB
_ = cache.Set([]byte("k"), []byte("v"), 60) // ttl in seconds
v, err := cache.Get([]byte("k"))

Internals:

• Fixed-size memory pool divided into 256 segments.
• Each segment is a circular ring of slot tables + data blocks.
• All keys and values live as []byte inside the pool.
• LRU eviction within a segment.
• Zero GC pressure (entire pool is one allocation).

When to use freecache:

• Memory-strict environments (fixed cap, no surprises).
• Very high throughput where every allocation matters.
• Simple key/value semantics.
• Per-entry TTL with seconds-resolution is enough.

Side-by-side¶

For a generic backend service, start with ristretto unless you specifically need the GC properties of bigcache or freecache. The TinyLFU admission policy keeps the cache "smart" without manual tuning, which is the single biggest win.

Observability: Hits, Misses, and Latency Histograms¶

A cache without metrics is a cache you cannot improve. At the middle level, you should expose at least:

• cache_hits_total{cache="name"} — counter
• cache_misses_total{cache="name"} — counter
• cache_evictions_total{cache="name", reason="expired|capacity|explicit"} — counter
• cache_size{cache="name"} — gauge
• cache_get_duration_seconds{cache="name"} — histogram
• cache_load_duration_seconds{cache="name"} — histogram (for loader-based caches)

The reason label on evictions is essential. Knowing that 99% of evictions are TTL-driven versus capacity-driven tells you whether to tune TTL or grow the cache.

A simple Prometheus-style integration:

import (
    "time"

    "github.com/prometheus/client_golang/prometheus"
)

type Metrics struct {
    Hits   prometheus.Counter
    Misses prometheus.Counter
    GetDur prometheus.Histogram
}

func (c *Cache) Get(key string) (string, bool) {
    start := time.Now()
    defer func() {
        c.metrics.GetDur.Observe(time.Since(start).Seconds())
    }()
    // ... existing logic ...
}

Add load metrics on the loader path:

v, err, _ := c.group.Do(key, func() (interface{}, error) {
    loadStart := time.Now()
    val, err := c.load(key)
    c.metrics.LoadDur.Observe(time.Since(loadStart).Seconds())
    return val, err
})

The histogram of LoadDur tells you what your p99 origin call looks like, which directly informs how much singleflight is saving you.

Distributed Caches Briefly Considered¶

In-process caches are great until you scale out. Once you run multiple replicas:

• Each replica caches independently. Hit ratio is replica-local.
• A cold replica (just started, or after deploy) hammers the upstream until its cache warms up.
• Invalidations are hard. Deleting a key on replica A does nothing for replicas B, C, D.

Some patterns to bridge to senior/professional content:

1. Sticky routing. Route requests for the same key to the same replica. The cache becomes effectively global. Cost: load imbalance, complex routing.
2. Two-tier (L1/L2). L1 = in-process cache (fast, small). L2 = Redis or similar (shared, larger). L1 absorbs the hot keys; L2 absorbs the long tail. Discussed at the professional level.
3. Pub/sub invalidation. When a key changes, broadcast a "drop this key" message on a channel that all replicas subscribe to. Each replica drops its local entry.
4. Just use Redis. For many services, the simplest answer.

This middle file does not cover distributed caches in depth — that is the senior file's job. But you should know that the assumption "all reads go through one process" stops holding the moment you autoscale.

Deep Dive: Distributed Pub/Sub Invalidation¶

When you go from 1 replica to N, in-process caches duplicate work. When key K changes on replica A, replicas B, C, D still serve the old value until their TTLs expire.

The fix: a pub/sub channel.

import "github.com/redis/go-redis/v9"

type Cache struct {
    local *LocalCache
    rdb   *redis.Client
}

func (c *Cache) Set(k, v string) {
    c.local.Set(k, v)
    // Tell other replicas to drop their local copy.
    c.rdb.Publish(ctx, "invalidations", k)
}

func (c *Cache) listen() {
    sub := c.rdb.Subscribe(ctx, "invalidations")
    for msg := range sub.Channel() {
        c.local.Delete(msg.Payload)
    }
}

When replica A publishes "K," all other replicas drop their local entry for K. The next read on those replicas misses and refetches the fresh value.

Pitfalls:

• The publishing replica also receives its own message (some pub/sub systems echo). Ignore self-published messages by including a replica ID.
• Message loss: pub/sub does not guarantee delivery. A replica that disconnects misses messages and serves stale data until reconnect. Mitigate with a periodic full resync.
• Ordering: messages may arrive out of order. For idempotent "delete K" messages, this is fine. For more complex invalidations, you need versioning.

This is a senior topic; we mention it here to flesh out the migration story.

Cache Warming Strategies¶

When a replica boots, its cache is empty. The first wave of requests all miss. If your upstream cannot handle the load, you have a cold-start failure mode.

Three strategies:

1. Lazy warming. Do nothing special; the cache fills up as requests arrive. Acceptable if upstream can absorb the burst.
2. Snapshot/restore. Periodically serialise the cache to disk or external storage; on boot, load the snapshot. Cache starts warm. Cost: snapshot management, staleness on restore.
3. Replay warming. On boot, read a list of "always-hot" keys from configuration and prefetch them. The application knows what is hot; cache does not need to discover it.

A practical compromise: lazy warming protected by singleflight. The first request for K after boot will trigger one upstream call; the next 999 requests in the next 50 ms will all wait for that one call. Cold-start damage is reduced to "exactly one upstream call per hot key."

Deep Dive: Cache-Aside vs Read-Through vs Write-Through¶

Three classical caching topologies. Each shapes your TTL cache differently.

Cache-aside¶

The application controls the cache; the cache does not know about the upstream:

v, ok := cache.Get(k)
if !ok {
    v = upstream.Load(k)
    cache.Set(k, v)
}

Pros: simple, no coupling. Cons: stampedes (every caller calls upstream) unless you add singleflight.

Read-through¶

The cache knows how to fetch from the upstream:

v := cache.GetOrLoad(k) // cache calls loader internally

Pros: centralised stampede protection, easier to test. Cons: the cache is now coupled to the storage layer.

All our middle-level examples (LoaderCache, dbcache, dnscache) are read-through. This is the modern best practice.

Write-through¶

Writes go to the cache and the upstream synchronously:

cache.Set(k, v); upstream.Save(k, v)

Or, the cache forwards writes itself. Pros: cache is always consistent. Cons: write latency is upstream latency.

Cousin: write-behind (write to cache immediately, write to upstream asynchronously). Faster writes; risk of data loss on crash.

Most TTL caches are read-only with respect to the upstream — you do not write to a TTL cache and expect persistence. For backend services this is the right model. When you need write-through, consider whether the cache is the right primitive or whether you actually need a database with a cache in front of it.

Cache Stampede Patterns Beyond Single-Flight¶

Singleflight is a sledgehammer; sometimes you want a scalpel.

Probabilistic early expiration. A fraction of readers treat the entry as "about to expire" and refresh it early. Stagger the refresh across the population to avoid the all-at-once herd.

// Refresh probability grows as we approach expiry.
func shouldRefreshEarly(now, expiresAt time.Time, ttl time.Duration) bool {
    remaining := expiresAt.Sub(now)
    p := 1.0 - float64(remaining)/float64(ttl)
    if p <= 0 {
        return true
    }
    return rand.Float64() < p*0.05 // tune the 0.05
}

The classic implementation is "XFetch" by Vattani et al. (2015) — a small academic paper worth reading.

Lock-then-fetch. Like singleflight but with a hold time: only allow one refresh per key per second, no matter how many readers are waiting. Helps when the upstream itself takes seconds and you do not want multiple refresh attempts in that window.

Two-stage caching. A short-TTL L1 cache "absorbs" rapid bursts; a long-TTL L2 cache provides durability. Reads check L1 first; misses check L2; misses there call upstream. The herd is split between layers and the upstream sees at most one call per L2 TTL window.

Deep Dive: Combining Heap + Singleflight + Jitter¶

Putting the three primary mid-level techniques together looks like this:

package cache

import (
    "container/heap"
    "math/rand/v2"
    "sync"
    "time"

    "golang.org/x/sync/singleflight"
)

type item struct {
    key       string
    expiresAt time.Time
    index     int
}

type expHeap []*item

func (h expHeap) Len() int            { return len(h) }
func (h expHeap) Less(i, j int) bool  { return h[i].expiresAt.Before(h[j].expiresAt) }
func (h expHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i]; h[i].index = i; h[j].index = j }
func (h *expHeap) Push(x any)         { it := x.(*item); it.index = len(*h); *h = append(*h, it) }
func (h *expHeap) Pop() any {
    old := *h; n := len(old); it := old[n-1]; old[n-1] = nil; it.index = -1
    *h = old[:n-1]; return it
}

type entry struct {
    value     string
    expiresAt time.Time
    heapItem  *item
}

type Cache struct {
    mu          sync.Mutex
    data        map[string]entry
    heap        expHeap
    ttl         time.Duration
    jitter      time.Duration
    loader      func(string) (string, error)
    group       singleflight.Group
    timer       *time.Timer
    stop        chan struct{}
    stopOnce    sync.Once
    done        chan struct{}
}

func New(ttl, jitter time.Duration, loader func(string) (string, error)) *Cache {
    c := &Cache{
        data:   make(map[string]entry),
        ttl:    ttl,
        jitter: jitter,
        loader: loader,
        stop:   make(chan struct{}),
        done:   make(chan struct{}),
    }
    heap.Init(&c.heap)
    c.timer = time.NewTimer(time.Hour)
    if !c.timer.Stop() {
        <-c.timer.C
    }
    go func() {
        defer close(c.done)
        c.run()
    }()
    return c
}

func (c *Cache) Get(key string) (string, error) {
    c.mu.Lock()
    e, ok := c.data[key]
    if ok && time.Now().Before(e.expiresAt) {
        c.mu.Unlock()
        return e.value, nil
    }
    c.mu.Unlock()

    v, err, _ := c.group.Do(key, func() (interface{}, error) {
        // Re-check.
        c.mu.Lock()
        e, ok := c.data[key]
        if ok && time.Now().Before(e.expiresAt) {
            c.mu.Unlock()
            return e.value, nil
        }
        c.mu.Unlock()

        val, err := c.loader(key)
        if err != nil {
            return "", err
        }
        c.set(key, val)
        return val, nil
    })
    if err != nil {
        return "", err
    }
    return v.(string), nil
}

func (c *Cache) set(key, value string) {
    jit := time.Duration(0)
    if c.jitter > 0 {
        jit = time.Duration(rand.Int64N(int64(c.jitter)))
    }
    expiresAt := time.Now().Add(c.ttl + jit)
    c.mu.Lock()
    defer c.mu.Unlock()
    if old, ok := c.data[key]; ok && old.heapItem != nil {
        heap.Remove(&c.heap, old.heapItem.index)
    }
    it := &item{key: key, expiresAt: expiresAt}
    heap.Push(&c.heap, it)
    c.data[key] = entry{value: value, expiresAt: expiresAt, heapItem: it}
    c.rescheduleLocked()
}

func (c *Cache) rescheduleLocked() {
    if !c.timer.Stop() {
        select {
        case <-c.timer.C:
        default:
        }
    }
    if len(c.heap) == 0 {
        return
    }
    delay := time.Until(c.heap[0].expiresAt)
    if delay < 0 {
        delay = 0
    }
    c.timer.Reset(delay)
}

func (c *Cache) run() {
    for {
        select {
        case <-c.timer.C:
            c.evictExpired()
        case <-c.stop:
            return
        }
    }
}

func (c *Cache) evictExpired() {
    now := time.Now()
    c.mu.Lock()
    defer c.mu.Unlock()
    for len(c.heap) > 0 && !c.heap[0].expiresAt.After(now) {
        it := heap.Pop(&c.heap).(*item)
        if e, ok := c.data[it.key]; ok && e.heapItem == it {
            delete(c.data, it.key)
        }
    }
    c.rescheduleLocked()
}

func (c *Cache) Close() {
    c.stopOnce.Do(func() { close(c.stop) })
    <-c.done
}