Build an In Memory Cache With Expiry in Go From Scratch

Nearly every service ends up with a map guarded by a mutex that someone calls a cache. It works until the first questions arrive: when do entries go away, what happens when memory grows, what if a hundred requests miss the same key at the same instant. A cache is one of those components that is easy to write badly and takes a surprisingly small amount of code to write well. The result is something worth owning: you can read all of it, test it, and know what it guarantees.

We build a generic cache with per-entry time-to-live, least-recently-used eviction, a background sweeper, a loader that avoids duplicate work, and statistics. It touches mutexes, tickers, the trade-offs in a locked map versus sync.Map and singleflight-style de-duplication, and belongs to the concurrency patterns cluster. Everything ran on Go 1.25.6 on an Apple M1 Max, with only the standard library.

Requirements

• Get(key) returns the value if present and not expired.
• Each entry has a TTL, defaulting to the cache's TTL, and may override it.
• The cache holds at most max entries. When it is full, the least recently used entry is evicted.
• Expired entries are removed even if nobody asks for them again, so memory does not leak.
• GetOrLoad(key, loader) calls the loader on a miss, but only once for concurrent callers of the same key.
• The cache is safe for concurrent use and can be shut down cleanly.
• It reports hits, misses, evictions and expirations.

The data structure

Two structures cooperate. A map[K]*list.Element finds an entry in O(1). A doubly linked list from container/list keeps entries in recency order, with the most recently used at the front. Looking up an entry moves it to the front, and evicting removes from the back. Both operations are O(1) because the map holds pointers into the list.

package main

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

// Stats counts what the cache has done since it was created.
type Stats struct {
	Hits, Misses, Evictions, Expired int64
}

type item[K comparable, V any] struct {
	key     K
	val     V
	expires time.Time // the zero time means the entry never expires
}

func (it *item[K, V]) expired(now time.Time) bool {
	return !it.expires.IsZero() && !now.Before(it.expires)
}

// call tracks one in-flight load so concurrent callers can share its result.
type call[V any] struct {
	wg  sync.WaitGroup
	val V
	err error
}

// Cache is a size-bounded, expiring, concurrency-safe cache.
type Cache[K comparable, V any] struct {
	mu      sync.Mutex
	ttl     time.Duration
	max     int
	items   map[K]*list.Element
	order   *list.List // front is the most recently used
	loading map[K]*call[V]
	stats   Stats

	stop      chan struct{}
	done      chan struct{}
	closeOnce sync.Once
}

// New returns a cache holding at most max entries (0 means unbounded) whose entries live for
// ttl (0 means forever). If sweepEvery is positive, a goroutine removes expired entries in the
// background; call Close to stop it.
func New[K comparable, V any](ttl time.Duration, max int, sweepEvery time.Duration) *Cache[K, V] {
	c := &Cache[K, V]{
		ttl: ttl, max: max,
		items:   map[K]*list.Element{},
		order:   list.New(),
		loading: map[K]*call[V]{},
		stop:    make(chan struct{}),
		done:    make(chan struct{}),
	}
	if sweepEvery > 0 {
		go c.janitor(sweepEvery)
	} else {
		close(c.done)
	}
	return c
}

Notice what the Cache holds and what it does not. It holds one mutex that protects the map, the list, the in-flight table and the stats together. A single lock around both structures is the point: the map and the list must change together, and two locks would invite an order of acquisition problem. We will measure what that costs.

Reading and writing

Get has to do three things atomically: find the entry, check the clock, and update recency. An expired entry is removed on the spot, which is lazy expiration: no background work is needed for correctness, because an expired value can never be returned. The sweeper only exists to free the memory of entries nobody asks for again.

package main

import (
	"container/list"
	"time"
)

// Get returns the value for key if it is present and has not expired.
func (c *Cache[K, V]) Get(key K) (V, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	var zero V
	el, ok := c.items[key]
	if !ok {
		c.stats.Misses++
		return zero, false
	}
	it := el.Value.(*item[K, V])
	if it.expired(time.Now()) {
		c.remove(el)
		c.stats.Expired++
		c.stats.Misses++
		return zero, false
	}
	c.order.MoveToFront(el)
	c.stats.Hits++
	return it.val, true
}

// Set stores val under key with the cache's default TTL.
func (c *Cache[K, V]) Set(key K, val V) { c.SetTTL(key, val, c.ttl) }

// SetTTL stores val under key with a specific TTL (0 means no expiry).
func (c *Cache[K, V]) SetTTL(key K, val V, ttl time.Duration) {
	c.mu.Lock()
	defer c.mu.Unlock()
	var expires time.Time
	if ttl > 0 {
		expires = time.Now().Add(ttl)
	}
	if el, ok := c.items[key]; ok { // update in place
		it := el.Value.(*item[K, V])
		it.val, it.expires = val, expires
		c.order.MoveToFront(el)
		return
	}
	c.items[key] = c.order.PushFront(&item[K, V]{key: key, val: val, expires: expires})
	if c.max > 0 && c.order.Len() > c.max {
		c.remove(c.order.Back()) // least recently used
		c.stats.Evictions++
	}
}

// Delete removes key if present.
func (c *Cache[K, V]) Delete(key K) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if el, ok := c.items[key]; ok {
		c.remove(el)
	}
}

// Len reports the number of entries, including any expired ones the sweeper has not reached.
func (c *Cache[K, V]) Len() int {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.order.Len()
}

// Stats returns a snapshot of the counters.
func (c *Cache[K, V]) Stats() Stats {
	c.mu.Lock()
	defer c.mu.Unlock()
	return c.stats
}

// remove deletes an element from both structures. The caller holds c.mu.
func (c *Cache[K, V]) remove(el *list.Element) {
	it := c.order.Remove(el).(*item[K, V])
	delete(c.items, it.key)
}

An eviction on Set removes c.order.Back(), the entry that has gone longest without being read or written. One subtlety: an expired but unswept entry still occupies a slot and could be the one evicted instead of a live one further up the list. The sweeper reduces that, and a stricter variant would check the back of the list for expired entries first. In practice with a sweeper running, it rarely matters.

The sweeper

Without a sweeper, an entry that is never read again lives forever, which is a leak that looks like growth. The sweeper wakes on a ticker and removes expired entries. The temptation is to scan everything; with a million entries that holds the lock for tens of milliseconds and stalls every reader. The compromise is to inspect only a bounded number of entries per tick. Ranging over a Go map starts at a random position, so successive sweeps cover different parts of the map, and an entry that sits there expired is found within a few ticks:

package main

import "time"

const sweepBatch = 500 // entries inspected per tick, so the lock is never held for long

func (c *Cache[K, V]) janitor(every time.Duration) {
	defer close(c.done)
	t := time.NewTicker(every)
	defer t.Stop()
	for {
		select {
		case <-t.C:
			c.sweep()
		case <-c.stop:
			return
		}
	}
}

func (c *Cache[K, V]) sweep() {
	c.mu.Lock()
	defer c.mu.Unlock()
	now := time.Now()
	checked := 0
	for _, el := range c.items {
		if checked++; checked > sweepBatch {
			break
		}
		if el.Value.(*item[K, V]).expired(now) {
			c.remove(el)
			c.stats.Expired++
		}
	}
}

// Close stops the sweeper and waits for it to exit. The cache remains usable but unswept.
func (c *Cache[K, V]) Close() {
	c.closeOnce.Do(func() { close(c.stop) })
	<-c.done
}

Deleting from a map while ranging over it is allowed in Go, which is why remove inside the loop is safe. This approach is the one Redis documents for its own expiry: sample a bounded set of keys with TTLs, delete the expired ones, repeat if many were expired. It trades exactness (an expired entry may linger for a few ticks) for bounded pause time. Close follows the lifecycle rule for any component that owns a goroutine: stop it and wait for it to exit (starting and stopping goroutines).

One load for a hundred misses

A cache protects something expensive, and the worst moment for the cache is when a popular entry expires: a hundred requests all miss at once and a hundred of them hit the database for the same row. This is the cache stampede, or thundering herd. GetOrLoad avoids it by tracking in-flight loads: the first caller for a key runs the loader, and everyone else who arrives meanwhile waits for its result.

package main

// GetOrLoad returns the cached value for key, or calls load to produce it. Concurrent callers
// asking for the same missing key share a single call to load.
func (c *Cache[K, V]) GetOrLoad(key K, load func() (V, error)) (V, error) {
	if v, ok := c.Get(key); ok {
		return v, nil
	}

	c.mu.Lock()
	if inflight, ok := c.loading[key]; ok { // someone is already loading it
		c.mu.Unlock()
		inflight.wg.Wait()
		return inflight.val, inflight.err
	}
	cl := &call[V]{}
	cl.wg.Add(1)
	c.loading[key] = cl
	c.mu.Unlock()

	defer func() { // runs even if load panics, so waiters are never stuck
		c.mu.Lock()
		delete(c.loading, key)
		c.mu.Unlock()
		cl.wg.Done()
	}()

	cl.val, cl.err = load()
	if cl.err == nil {
		c.Set(key, cl.val)
	}
	return cl.val, cl.err
}

Errors are shared with the waiters but not cached, so the next call after a failure tries again. That is a choice; some systems cache failures briefly to protect a struggling backend, which is the same idea as a circuit breaker. The golang.org/x/sync/singleflight package implements the same de-duplication with a more complete API and panic handling (the singleflight article); building it here shows what it does.

Using it

The demo exercises the behavior in real time with short TTLs: expiry, per-entry TTL, LRU eviction, the loader under concurrent misses, and the stats:

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

func main() {
	c := New[string, int](100*time.Millisecond, 3, 20*time.Millisecond)
	defer c.Close()

	c.Set("a", 1)
	c.Set("b", 2)
	c.Set("c", 3)
	c.Get("a") // a is now the most recently used; b is the least
	c.Set("d", 4)
	_, hasB := c.Get("b")
	_, hasA := c.Get("a")
	fmt.Println("after adding d to a full cache: b present =", hasB, ", a present =", hasA)

	c.SetTTL("short", 9, 30*time.Millisecond)
	time.Sleep(60 * time.Millisecond)
	_, ok := c.Get("short")
	fmt.Println("entry with a 30 ms TTL after 60 ms:", ok)

	time.Sleep(120 * time.Millisecond) // let the sweeper clear the rest without any Get
	fmt.Println("entries left after the default TTL, with no reads:", c.Len())

	var loads atomic.Int32
	var wg sync.WaitGroup
	for range 50 {
		wg.Go(func() {
			c.GetOrLoad("expensive", func() (int, error) {
				loads.Add(1)
				time.Sleep(30 * time.Millisecond) // the slow database call
				return 42, nil
			})
		})
	}
	wg.Wait()
	fmt.Println("loader calls for 50 concurrent misses of one key:", loads.Load())

	s := c.Stats()
	fmt.Printf("stats: hits=%d misses=%d evictions=%d expired=%d\n", s.Hits, s.Misses, s.Evictions, s.Expired)
}

after adding d to a full cache: b present = false , a present = true
entry with a 30 ms TTL after 60 ms: false
entries left after the default TTL, with no reads: 0
loader calls for 50 concurrent misses of one key: 1
stats: hits=2 misses=52 evictions=2 expired=3

Adding d to a full cache of three evicted b, not a, because reading a had just made it the most recently used. The entry with the 30 ms override is gone after 60 ms, and after the default TTL passes the sweeper has emptied the cache without a single read touching it. Fifty goroutines missing the same key made exactly one call to the loader. The stats add up what happened: two hits (both reads of a), 52 misses (50 of them the loader callers' first lookups), two evictions and three expirations.

Tests with virtual time

TTL behavior is the textbook case for testing/synctest: the interesting durations are minutes and hours, and the cache calls time.Now directly. Inside a bubble, an hour is instant, and the janitor's ticker runs on the bubble's clock:

package main

import (
	"sync"
	"sync/atomic"
	"testing"
	"testing/synctest"
	"time"
)

func TestEntryExpiresLazily(t *testing.T) {
	synctest.Test(t, func(t *testing.T) {
		c := New[string, string](time.Hour, 0, 0)
		c.Set("k", "v")
		time.Sleep(59 * time.Minute)
		if _, ok := c.Get("k"); !ok {
			t.Fatal("entry expired after 59 minutes")
		}
		time.Sleep(2 * time.Minute)
		if _, ok := c.Get("k"); ok {
			t.Fatal("entry still present after 61 minutes")
		}
	})
}

func TestSweeperRemovesUnreadEntries(t *testing.T) {
	synctest.Test(t, func(t *testing.T) {
		c := New[int, int](time.Minute, 0, 10*time.Second)
		defer c.Close()
		for i := range 100 {
			c.Set(i, i)
		}
		time.Sleep(90 * time.Second) // past the TTL, several sweeps later
		synctest.Wait()
		if n := c.Len(); n != 0 {
			t.Fatalf("%d entries left; the sweeper should have removed them", n)
		}
	})
}

func TestLeastRecentlyUsedIsEvicted(t *testing.T) {
	c := New[string, int](0, 2, 0)
	c.Set("a", 1)
	c.Set("b", 2)
	c.Get("a")
	c.Set("c", 3) // evicts b
	if _, ok := c.Get("b"); ok {
		t.Fatal("b should have been evicted")
	}
	if _, ok := c.Get("a"); !ok {
		t.Fatal("a was evicted although it was recently used")
	}
	if got := c.Stats().Evictions; got != 1 {
		t.Fatalf("evictions = %d, want 1", got)
	}
}

func TestConcurrentMissesLoadOnce(t *testing.T) {
	c := New[string, int](0, 0, 0)
	var loads atomic.Int32
	release := make(chan struct{})
	var wg sync.WaitGroup
	for range 20 {
		wg.Go(func() {
			c.GetOrLoad("k", func() (int, error) {
				loads.Add(1)
				<-release // hold the load open so the others pile up behind it
				return 1, nil
			})
		})
	}
	time.Sleep(20 * time.Millisecond) // let the waiters arrive
	close(release)
	wg.Wait()
	if loads.Load() != 1 {
		t.Fatalf("loader ran %d times, want 1", loads.Load())
	}
}

=== RUN   TestEntryExpiresLazily
--- PASS: TestEntryExpiresLazily (0.00s)
=== RUN   TestSweeperRemovesUnreadEntries
--- PASS: TestSweeperRemovesUnreadEntries (0.00s)
=== RUN   TestLeastRecentlyUsedIsEvicted
--- PASS: TestLeastRecentlyUsedIsEvicted (0.00s)
=== RUN   TestConcurrentMissesLoadOnce
--- PASS: TestConcurrentMissesLoadOnce (0.02s)
PASS
ok  	example.test/lab	1.291s

The two synctest tests would take over an hour of wall-clock time without it, and run in about a millisecond with it. The last test is a gate: the loader blocks on release so that the other nineteen callers are guaranteed to be waiting behind the first before it finishes (forcing an interleaving); the short real sleep only lets them arrive, and the assertion is on the count, which cannot be too low. Under -race all four pass.

What it costs

One mutex protects everything, which is simple and has a price under contention. This benchmark reads a hot key from ten goroutines and measures time per Get:

package main

import "testing"

func BenchmarkGetParallel(b *testing.B) {
	c := New[int, int](0, 1024, 0)
	for i := range 1024 {
		c.Set(i, i)
	}
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			c.Get(i & 1023)
			i++
		}
	})
}

func BenchmarkGetSingle(b *testing.B) {
	c := New[int, int](0, 1024, 0)
	for i := range 1024 {
		c.Set(i, i)
	}
	for i := 0; b.Loop(); i++ {
		c.Get(i & 1023)
	}
}

goos: darwin
goarch: arm64
pkg: example.test/lab
cpu: Apple M1 Max
BenchmarkGetParallel-10    	 5023712	       229.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkGetSingle-10      	23534352	        51.69 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	example.test/lab	2.859s

On this machine a lone goroutine paid about 52 ns per hit: the lock, a map lookup, a list move and a clock read. With ten cores hammering the same mutex the cost per operation rose to about 230 ns, more than four times, because Get is a write (it moves the entry to the front of the list), so an RWMutex would not help. That is the price of strict LRU: every read mutates shared state. If this becomes a bottleneck, the remedies are known. Shard the cache by key hash into N independent caches (sharded maps), approximate recency with a cheaper scheme such as a clock algorithm or sampling, or only promote an entry if it has not been promoted recently. Measure before doing any of them; most services never get close to the limit of one mutex.

Choosing TTLs, and expiring together

A TTL is a statement about how stale an answer may be, and the right value comes from the data, not from the cache. A product description can be an hour old; an account balance cannot. Write the staleness budget next to each call site, because a cache with one global TTL is a cache whose callers have stopped thinking.

There is a subtler failure in how entries expire. If a service warms its cache at startup, every entry gets the same expiry, and an hour later they all expire together, which sends a wave of loads to the backend at once. The loader de-duplication helps per key, but a thousand different keys expiring in the same second is a thousand loads. The standard remedy is jitter: add a random amount, ten percent of the TTL is typical, to each entry's lifetime, so expiries spread out. In this cache that is a one-line change inside SetTTL:

if ttl > 0 {
	jitter := time.Duration(rand.Int64N(int64(ttl) / 10)) // up to 10% extra
	expires = time.Now().Add(ttl + jitter)
}

Serving stale data while refreshing

Another common requirement is that readers should never wait for a reload of an entry that is merely old. The pattern is called stale-while-revalidate. Each entry carries two times: a soft expiry, after which the value is stale but servable, and a hard expiry, after which it must not be served. A read of a stale entry returns the old value immediately and starts one background refresh (guarded by the same in-flight table that GetOrLoad uses), so most readers never see the latency of a load, and the entry is fresh again by the time the next reader arrives. It costs a goroutine per refresh and a second timestamp per entry, and for data where a few seconds of staleness is acceptable it removes the latency spike every TTL boundary would otherwise cause. HTTP caches define the same idea in the stale-while-revalidate directive of RFC 5861.

What not to cache

Caches are easy to add and hard to remove, and the usual regrets are about what went into them. Do not cache values that are cheap to compute: a lookup that costs a microsecond is slower with a mutex and a map in front of it. Do not cache anything whose staleness is a correctness bug, such as permissions or balances, unless invalidation is solid. Do not cache errors by accident, as with a cached empty result that came from a transient failure. And do not let the cache become the only copy of anything; it is allowed to forget at any moment, by design.

Correctness also depends on what callers do with the values. A cache hands out whatever it stored. If the value is a pointer or a slice and a caller modifies it, every other caller sees the change, and the cache's lock does not protect the pointee. Either store immutable values, return copies, or document that values must not be modified.

Observability

A cache you cannot see into is a cache you will distrust during an incident. The Stats struct already counts hits, misses, evictions and expirations; export them as metrics and graph the hit ratio, hits / (hits + misses), over time. A falling ratio after a deploy usually means keys changed shape (a new parameter in the key) or the working set outgrew max; a ratio near zero means the cache is not doing its job and is costing you a lock for nothing. Evictions rising while expirations stay flat says the cache is too small for the traffic, and the fix is a bigger bound rather than a longer TTL. Add the current Len as a gauge, and log or count the loader's errors separately, because those are the symptom of the backend that the cache was supposed to protect.

Choices I would revisit

Memory, not entries. A bound on the count assumes entries are similar in size. If values vary from 100 bytes to 10 MB, bound the total size and evict until under it, with a weight function.

Time source. The cache reads time.Now for every operation. For tests I prefer synctest; for code that must run under a controlled clock, inject one (fake clocks).

Negative caching. Caching "not found" for a short time protects the backend from repeated misses on keys that do not exist, at the cost of staleness when they appear.

Use a library when you need more. Production-grade caches (ristretto, otter, golang-lru) add admission policies, sharding and metrics. The point of writing this version is to understand them, not to avoid them. The container/list documentation describes the structure used here, and the Redis documentation on key eviction is an excellent description of the same trade-offs at larger scale.