LRU Cache

The 30-second version

A CacheCacheA small, fast store of answers you already computed or fetched, so the next request for the same thing skips the slow work. The hard part is knowing when a cached answer is out of date. is a small, fast store of answers you already fetched, so the next request for the same thing skips the slow work (a database query, a network call, a big calculation). Memory is limited, so every real cache needs a size limit. And a size limit forces a question: when it's full, what do you throw out?

The rule this whole topic is about is called the cache's eviction policyEviction policyThe rule a cache uses to decide what to throw out when it's full — least recently used (LRU), least frequently used (LFU), oldest first (FIFO), or random.. LRU is the most famous one because it's simple and it matches how programs and people actually behave: what you used recently, you'll probably use again soon.

Try it. The cache below has room for 3 keys. The left end is the most recently used; the right end is next in line to be thrown out.

What's in this topic

1. Why caches evict, and how much a few percent of hit rateHit rateThe share of lookups a cache can answer by itself. 90% hit rate = 9 of every 10 requests are found in the cache; the other 1 (a miss) has to go to the slow source. is worth (§02–03).
2. How to build an LRU cache where every operation takes the same tiny amount of time, no matter how big the cache is: a Hash mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets. plus a Doubly linked listDoubly linked listA linked list where each node points both to the next node and to the previous one. Because a node knows both neighbours, you can cut it out or insert it anywhere in a constant number of steps — no searching. (§04–05).
3. Working code in Go and JavaScript, with tests, and the bugs everyone writes the first time (§06–08).
4. Production: expiry times, memory limits, many threads at once, and the traffic patterns where LRU falls over and what real systems use instead (§09–12).

Hits, misses, and why 99% beats 90% by 4×

Every lookup has two possible outcomes:

• Hit: the answer is already in the cache. Fast.
• Miss: it isn't. You go to the slow source (say, a database), wait for the answer, store it in the cache for next time, and return it. The extra time a miss costs is called the miss penaltyMiss penaltyThe extra time a cache miss costs: the trip to the slow source (database, disk, network) plus storing the answer in the cache..

The hit rateHit rateThe share of lookups a cache can answer by itself. 90% hit rate = 9 of every 10 requests are found in the cache; the other 1 (a miss) has to go to the slow source. is hits ÷ all lookups. 90% means 9 of every 10 requests are hits.

A worked example

Say a cache lookup takes 1 ms and a database query takes 50 ms. A miss pays both: 1 ms to check the cache, then 50 ms for the database, so 51 ms.

Going from 90% to 99% sounds like a small step — "nine more percent". But the average drops from 6.0 ms to 1.5 ms (4× faster), and the database gets 10× fewer queries. Look at the 90% row: the 10% of misses cost 5.1 of the 6.0 ms. The misses dominate.

So what decides the hit rate?

Three things, roughly in order of importance:

1. The traffic. If a few keys get most of the requests (a few viral posts, today's prices), even a small cache catches most of them. If every request asks for something different, no cache helps.
2. The size. More room means fewer evictions. But memory costs money, so the size is always a trade-off.
3. The eviction policyEviction policyThe rule a cache uses to decide what to throw out when it's full — least recently used (LRU), least frequently used (LFU), oldest first (FIFO), or random. — which entry to throw out when full. With the same size and the same traffic, a better policy keeps the entries that will be asked for again. That's the next section.

Who gets thrown out? FIFO, LRU, LFU, random

When the cache is full and a new key arrives, the Eviction policyEviction policyThe rule a cache uses to decide what to throw out when it's full — least recently used (LRU), least frequently used (LFU), oldest first (FIFO), or random. picks a victim. The perfect policy would throw out the entry that won't be needed for the longest time — but that needs knowing the future. Every real policy uses the past to guess.

Watch them disagree

Ten requests, a cache of 3, three policies side by side. Users ask for A and B a lot at first, then switch to D and E. Step through and watch who each policy throws out.

Three lessons from ten requests:

• FIFO ignores use. Arriving first is all that counts, so the popular A was thrown out at step 6.
• LRU follows interest. When traffic moved to D and E, LRU let A go and kept up.
• LFU remembers too much. A and B built up high counts early, so LFU kept them even after nobody wanted them — and the newcomers D and E kept pushing each other out.

Why recency is a good guess

Programs and people repeat themselves over short stretches of time. You open the same few files all afternoon; a news site's front page gets hammered for an hour; a loop reads the same variables a million times. This pattern is called temporal localityTemporal localityIf a program used some data recently, it will probably use it again soon (like a loop counter or a hot config). Caches exploit it by keeping recently used lines around.: if something was used recently, it will probably be used again soon.

LRU bets directly on temporal locality. Your CPU makes the same bet in hardware — its caches evict roughly the least recently used chunk of memory (a Cache lineCache lineThe chunk of memory (usually 64 bytes) that a CPU core copies into its own fast cache. When two cores write to the same cache line, it has to bounce between them, which is slow.) (see CPU Caches: locality). That's why LRU is the default answer: it's simple, it adapts when interest moves, and it's usually close to the best simple policy. §11 shows the traffic where it isn't.

The classic design: hash map + doubly linked list

Every LRU cache supports two operations:

• get(key) — return the value if present, and mark it as just used.
• put(key, value) — store it as just used; if the cache is full, first evict the least recently used entry.

The goal is to make both O(1)Big-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles.: the same small amount of work whether the cache holds 10 entries or 10 million. (If Big-O is new, Big-O explains it; here, "O(1)" means "doesn't grow" and "O(n)" means "grows in step with the number of entries".)

Two obvious designs, and why they're slow

Attempt 1: a map plus a "last used" timestamp. Keep map[key] → {value, lastUsed}. Get is fast: look it up, update the timestamp. But eviction must find the oldest timestamp, and a map has no order, so you check every entry: O(n).

Attempt 2: an ArrayArrayItems stored one after another in a single block of memory, so item i is found by simple arithmetic in O(1). Go has fixed arrays and growable slices; JS arrays are growable. kept in recency order. Keep the keys in a list, most recent first. Eviction is easy: drop the last one. But a get must first find the key (scan the list) and then move it to the front, shifting everything in between: O(n) again.

At 1,000 entries the slow operation is 1,000 steps; at a million entries it's a million — on every eviction or get. A cache is supposed to be the fast part of your system, so that's a non-starter.

The trick: use both, and link them

Look at what each attempt was good at. The map finds a key instantly. The ordered list knows who's oldest. The problem is that the list is slow to find an entry and slow to move one.

The fix has two parts:

1. The map stores a pointer to the entry's place in the list, not just the value. Finding is now a map lookup.
2. The list is a Doubly linked listDoubly linked listA linked list where each node points both to the next node and to the previous one. Because a node knows both neighbours, you can cut it out or insert it anywhere in a constant number of steps — no searching.. Each nodeNode (list node)One item of a linked list: a small object holding the data plus pointers to its neighbours. In an LRU cache a node holds a key, a value, prev and next. holds a key and value plus a PointerPointer (*T, &v)A value that holds the memory address of another value instead of a copy of it. In Go, &v takes v's address and *T is the type “pointer to T”; changes made through a pointer are seen by everyone holding it. JS objects behave like this automatically. to the next node and to the previous one. Because a node knows both neighbours, you can cut it out and re-insert it at the front by rewriting a handful of pointers — no shifting, no searching.

The list is the recency orderRecency orderThe cache entries lined up by when they were last used: most recently used at the front, least recently used at the back. LRU evicts from the back.: the front is the most recently used, the back is the next to be evicted. The HEAD and TAIL boxes are dummy nodes that hold no data; they just make the code simpler (§08 explains why).

Step through it

Here's the core of the code in Go (the full version is in §06). unlink(n) cuts node n out by pointing its two neighbours at each other; pushFront(n) splices n in right after HEAD.

1func (c *Cache) Get(key string) (int, bool) {
2    n, ok := c.items[key]     // 1. map: key → node
3    if !ok {
4        return 0, false
5    }
6    c.unlink(n)               // 2. cut n out of the list
7    c.pushFront(n)            // 3. put n right after HEAD
8    return n.val, true
9}
10 
11func (c *Cache) Put(key string, val int) {
12    // (updating an existing key: see §06)
13    if len(c.items) == c.cap {
14        lru := c.tail.prev    // 4. the node just before TAIL
15        c.unlink(lru)
16        delete(c.items, lru.key) // 5. forget it in the map too
17    }
18    n := &node{key: key, val: val}
19    c.items[key] = n
20    c.pushFront(n)
21}

Try it: get, put, evict

This is the full version of the cache from §01. The left panel is the hash map (no order, just "key → its node"); the right panel is the doubly linked list in recency orderRecency orderThe cache entries lined up by when they were last used: most recently used at the front, least recently used at the back. LRU evicts from the back..

Things to try

1. The basic eviction. put A, B, C. Then get(A). Then put(D). B is evicted, not A — because the get moved A to the front.
2. Get is a write. Do get(B) on a cache holding A, B, C and watch the list. Nothing was stored, but the order changed. Remember this; it matters a lot for threads (§10).
3. Put on an existing key. With A, B, C cached, put(A) again. The value changes and A moves to the front, but nothing is evicted — the cache didn't grow.
4. Replay the traces. Each button feeds a recorded list of requests — an access traceAccess traceA recorded list of which keys were requested, in order (e.g. A B C A D …). Replaying the same trace against different caches is how you compare policies fairly. — through the cache: for every key, a get, and a put if it missed. "loop of 4" scores 0%. Can you see why before reading §11?

Go: container/list, then generics

Version 1: container/list + map

package main

import (
	"container/list"
	"fmt"
)

type entry struct {
	key   string // ← stored so eviction knows which map entry to delete
	value int
}

type LRU struct {
	cap   int
	ll    *list.List               // front = most recently used
	items map[string]*list.Element // key → node in ll
}

func New(capacity int) *LRU {
	return &LRU{cap: capacity, ll: list.New(), items: make(map[string]*list.Element)}
}

func (c *LRU) Get(key string) (int, bool) {
	el, ok := c.items[key]
	if !ok {
		return 0, false // miss
	}
	c.ll.MoveToFront(el) // ← a read is also a "use"
	return el.Value.(*entry).value, true
}

func (c *LRU) Put(key string, value int) {
	if el, ok := c.items[key]; ok {
		el.Value.(*entry).value = value // ← update in place, don't insert twice
		c.ll.MoveToFront(el)
		return
	}
	if c.ll.Len() == c.cap {
		oldest := c.ll.Back()
		c.ll.Remove(oldest)
		delete(c.items, oldest.Value.(*entry).key) // ← forget it in the map too
	}
	c.items[key] = c.ll.PushFront(&entry{key, value})
}

func main() {
	c := New(2)
	c.Put("a", 1)
	c.Put("b", 2)
	fmt.Println(c.Get("a")) // a becomes most recent
	c.Put("c", 3)           // full → evicts b
	fmt.Println(c.Get("b"))
}

$ go run .
1 true
0 false

This version is fine for many programs, but the type assertions are noise and any hides mistakes from the compiler. Let's write our own list.

Version 2: generic, with sentinel nodes

package lru

type node[K comparable, V any] struct {
	key        K
	val        V
	prev, next *node[K, V]
}

// Cache is a fixed-size LRU cache. Not safe for concurrent use (see §10).
type Cache[K comparable, V any] struct {
	cap   int
	items map[K]*node[K, V]
	head  node[K, V] // sentinel: head.next is the most recently used
	tail  node[K, V] // sentinel: tail.prev is the least recently used
}

func New[K comparable, V any](capacity int) *Cache[K, V] {
	if capacity < 1 {
		panic("lru: capacity must be at least 1")
	}
	c := &Cache[K, V]{cap: capacity, items: make(map[K]*node[K, V], capacity)}
	c.head.next = &c.tail // empty list: the two sentinels point at each other
	c.tail.prev = &c.head
	return c
}

func (c *Cache[K, V]) unlink(n *node[K, V]) {
	n.prev.next = n.next
	n.next.prev = n.prev
}

func (c *Cache[K, V]) pushFront(n *node[K, V]) {
	n.prev = &c.head
	n.next = c.head.next
	c.head.next.prev = n
	c.head.next = n
}

func (c *Cache[K, V]) Get(key K) (V, bool) {
	n, ok := c.items[key]
	if !ok {
		var zero V // ← the "empty" value of whatever type V is
		return zero, false
	}
	c.unlink(n)
	c.pushFront(n)
	return n.val, true
}

func (c *Cache[K, V]) Put(key K, val V) {
	if n, ok := c.items[key]; ok {
		n.val = val
		c.unlink(n)
		c.pushFront(n)
		return
	}
	if len(c.items) == c.cap {
		lru := c.tail.prev
		c.unlink(lru)
		delete(c.items, lru.key)
	}
	n := &node[K, V]{key: key, val: val}
	c.items[key] = n
	c.pushFront(n)
}

func (c *Cache[K, V]) Len() int { return len(c.items) }

// Keys returns keys from most to least recently used.
func (c *Cache[K, V]) Keys() []K {
	ks := make([]K, 0, len(c.items))
	for n := c.head.next; n != &c.tail; n = n.next {
		ks = append(ks, n.key)
	}
	return ks
}

Tests, and a trace you can read

package lru

import (
	"fmt"
	"slices"
	"testing"
)

func TestEvictsLeastRecentlyUsed(t *testing.T) {
	c := New[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Get("a")    // a is now most recent
	c.Put("c", 3) // evicts b, not a
	if _, ok := c.Get("b"); ok {
		t.Fatal("b should have been evicted")
	}
	if got := c.Keys(); !slices.Equal(got, []string{"c", "a"}) {
		t.Fatalf("order = %v, want [c a]", got)
	}
}

func TestPutExistingUpdatesAndRefreshes(t *testing.T) {
	c := New[string, int](2)
	c.Put("a", 1)
	c.Put("b", 2)
	c.Put("a", 10) // update, not insert: must not evict anything
	c.Put("c", 3)  // evicts b (a was refreshed)
	if v, _ := c.Get("a"); v != 10 {
		t.Fatalf("a = %d, want 10", v)
	}
	if c.Len() != 2 {
		t.Fatalf("len = %d, want 2", c.Len())
	}
}

func Example() {
	c := New[string, int](3)
	for _, k := range []string{"a", "b", "c", "a", "d", "b"} {
		if _, ok := c.Get(k); ok {
			fmt.Printf("get %s: hit   %v\n", k, c.Keys())
		} else {
			c.Put(k, len(k))
			fmt.Printf("get %s: miss  %v\n", k, c.Keys())
		}
	}
	// Output:
	// get a: miss  [a]
	// get b: miss  [b a]
	// get c: miss  [c b a]
	// get a: hit   [a c b]
	// get d: miss  [d a c]
	// get b: miss  [b d a]
}

$ go mod init example.com/lru   # once, in the folder that contains ./lru (lru.go, lru_test.go)
$ go test -v ./lru
=== RUN   TestEvictsLeastRecentlyUsed
--- PASS: TestEvictsLeastRecentlyUsed (0.00s)
=== RUN   TestPutExistingUpdatesAndRefreshes
--- PASS: TestPutExistingUpdatesAndRefreshes (0.00s)
=== RUN   Example
--- PASS: Example (0.00s)
PASS

How fast is it?

Strictly, Go map operations are O(1) Amortized costAmortized costThe average cost per operation over a long sequence, when most operations are cheap and a rare one is expensive — e.g. appending to a slice is O(1) amortized even though an occasional append copies everything. — occasionally the map grows and copies itself — but make(map[K]V, capacity) sizes the map up front, and an LRU cache never holds more than capacity entries, so the expensive growth step is rare. (Big-O covers amortized cost; Hash Maps covers how Go's map works.)

JavaScript: the Map trick, and when it breaks

Version 1: the Map trick

A Map iterates its keys in insertion order: the first key you added comes out first. That's already a recency list if we keep it up to date:

• Most recent = last. On every use, delete the key and set it again, which re-inserts it at the end.
• Least recent = first. To evict, take the first key: map.keys().next().value.

export class LRUCache {
  #cap;
  #map = new Map(); // iteration order = insertion order: first key = least recent

  constructor(capacity) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.#cap = capacity;
  }

  get(key) {
    if (!this.#map.has(key)) return undefined; // miss
    const value = this.#map.get(key);
    this.#map.delete(key);                     // ← delete + set moves the key
    this.#map.set(key, value);                 //   to the end (= most recent)
    return value;
  }

  put(key, value) {
    if (this.#map.has(key)) this.#map.delete(key);
    else if (this.#map.size === this.#cap) {
      const oldest = this.#map.keys().next().value; // first key = least recent
      this.#map.delete(oldest);
    }
    this.#map.set(key, value);
  }

  keys() { return [...this.#map.keys()].reverse(); } // most → least recent
}

Why delete before set? Because set on an existing key only updates the value; the key keeps its old position:

const m = new Map([["x", 1], ["y", 2]]);
m.set("x", 99);
console.log([...m.keys()]); // → [ 'x', 'y' ]   x did NOT move

Forget the delete and your "LRU" quietly becomes FIFO.

Version 2: an explicit doubly linked list

The same design as the Go version, with two sentinelSentinel nodeA dummy node that holds no data and permanently sits at the start (head) or end (tail) of a linked list. Because every real node always has a neighbour on both sides, the code never needs “is this the first/last node?” checks. nodes:

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

export class LRUCache {
  #cap;
  #map = new Map();             // key → Node
  #head = new Node(null, null); // sentinel: #head.next = most recent
  #tail = new Node(null, null); // sentinel: #tail.prev = least recent

  constructor(capacity) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.#cap = capacity;
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }

  #unlink(n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }

  #pushFront(n) {
    n.prev = this.#head;
    n.next = this.#head.next;
    this.#head.next.prev = n;
    this.#head.next = n;
  }

  get(key) {
    const n = this.#map.get(key);
    if (!n) return undefined;
    this.#unlink(n);
    this.#pushFront(n);
    return n.value;
  }

  put(key, value) {
    let n = this.#map.get(key);
    if (n) {
      n.value = value;         // existing key: update…
      this.#unlink(n);         // …and move (below)
    } else {
      if (this.#map.size === this.#cap) {
        const lru = this.#tail.prev;
        this.#unlink(lru);
        this.#map.delete(lru.key);
      }
      n = new Node(key, value);
      this.#map.set(key, n);
    }
    this.#pushFront(n);
  }

  keys() {
    const out = [];
    for (let n = this.#head.next; n !== this.#tail; n = n.next) out.push(n.key);
    return out;
  }
}

#unlink and #pushFront are private methods — same # rule as private fields.

Tests with node:test

import { test } from "node:test";
import assert from "node:assert/strict";
import { LRUCache } from "./map-lru.mjs"; // or ./list-lru.mjs — same behaviour

test("evicts the least recently used key", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.get("a");    // a is now most recent
  c.put("c", 3); // evicts b
  assert.equal(c.get("b"), undefined);
  assert.deepEqual(c.keys(), ["c", "a"]);
});

test("put on an existing key updates and refreshes", () => {
  const c = new LRUCache(2);
  c.put("a", 1);
  c.put("b", 2);
  c.put("a", 10);
  c.put("c", 3); // evicts b, not a
  assert.equal(c.get("a"), 10);
  assert.equal(c.get("b"), undefined);
});

$ node --test lru.test.mjs
✔ evicts the least recently used key (1.19324ms)
✔ put on an existing key updates and refreshes (0.206731ms)
ℹ tests 2
ℹ suites 0
ℹ pass 2
ℹ fail 0
…

The surprise: evicting from a big Map gets slow

Both versions are "O(1)" on paper. We measured them anyway on a 4-core Linux VM (Node 22, whose JavaScript engine is V8V8The JavaScript engine (the part that actually executes JS) inside Chrome and Node.js. 12.4) — first just the eviction step of the Map trick, at three sizes:

// evict the first (oldest) key, insert a new one — 1,000,000 times
m.delete(m.keys().next().value);
m.set(next++, 1);

That's growing in step with the size — O(n), not O(1). The likely reason is how V8 stores a Map: deleting an entry leaves a hole in an internal table that is only cleaned up when the table is rebuilt, and finding "the first key" walks past every hole at the front. Evicting from the front makes exactly those holes. (That's our reading of the behaviour, not a documented guarantee; other engines and future versions may differ.)

Then the whole cache, 2 million lookups with a put on every miss, capacity 10,000:

Rule of thumb: the Map trick is perfect for small caches (a few hundred entries) and interview answers. For a large cache that evicts often, use the linked list — or a well-tested library such as the lru-cache package on npm.

Sentinel nodes and the classic bugs

Sentinel nodes: no more special cases

Without sentinels, the first node's prev and the last node's next are nil. Then every list operation needs extra checks: "is this node the head? the tail? the only node? is the list empty?" Each check is a chance for a nil-pointer crash.

A sentinel nodeSentinel nodeA dummy node that holds no data and permanently sits at the start (head) or end (tail) of a linked list. Because every real node always has a neighbour on both sides, the code never needs “is this the first/last node?” checks. is a dummy node that holds no data and never moves. Put one permanently at each end:

Now every real node always has a real node on both sides — at worst, a sentinel. So unlink is always the same two lines and pushFront always the same four, and "the least recently used node" is simply tail.prev. The cost: two extra nodes per cache, and loops must stop at the sentinel (n != &c.tail) instead of at nil.

func (c *Cache) unlink(n *node) {
	if n.prev != nil {
		n.prev.next = n.next
	} else {
		c.first = n.next // n was the first node
	}
	if n.next != nil {
		n.next.prev = n.prev
	} else {
		c.last = n.prev // n was the last node
	}
}

func (c *Cache) unlink(n *node) {
	n.prev.next = n.next
	n.next.prev = n.prev
}
// head and tail are dummies, so
// n.prev and n.next are never nil.

The five classic bugs

v, ok := c.Get("a")
fmt.Println("ghost:", v, ok, "list:", c.ll.Len(), "map:", len(c.items))
// ghost: 1 true list: 2 map: 3

func (c *LRU) Get(key string) (int, bool) {
	if el, ok := c.items[key]; ok {
		return el.Value.(*entry).value, true // never moves
	}
	return 0, false
}

func (c *LRU) Get(key string) (int, bool) {
	if el, ok := c.items[key]; ok {
		c.ll.MoveToFront(el) // ← a read is a use
		return el.Value.(*entry).value, true
	}
	return 0, false
}

1func (c *LRU) Put(key string, value int) {
2    // BUG: missing "if key is already cached { update; return }"
3    if c.ll.Len() == c.cap {
4        oldest := c.ll.Back()
5        c.ll.Remove(oldest)
6        delete(c.items, oldest.Value.(*entry).key)
7    }
8    c.items[key] = c.ll.PushFront(&entry{key, value})
9}

c.Put("a", 1)
c.Put("a", 2) // BUG: a second node for "a"
c.Put("b", 3) // list full (2 nodes) → evicts the OLD "a" node, deleting "a" from the map
fmt.Println(c.ll.Len(), len(c.items))
fmt.Println(c.Get("a"))

2 1
0 false

panic: runtime error: invalid memory address or nil pointer dereference
container/list.(*List).Remove(...)

c := New[string, []string](100)
c.Put("user:42:roles", []string{"admin"})

roles, _ := c.Get("user:42:roles")
roles[0] = "guest" // meant as a local tweak…
fmt.Println(c.Get("user:42:roles"))
// [guest] true   ← the cache changed for everyone

Expiry times and memory limits

Why LRU alone isn't enough

Picture a cached user profile. The user changes their name in the database, but the profile is popular, so LRU keeps it at the front of the list — forever. Your cache will serve the old name until the entry happens to be evicted, which for a popular key might be never.

A TTLTTL (cache)Time to live: how long an entry may be served before it counts as expired. After that, a lookup treats it as a miss even though it's still sitting in memory. (time to live) puts an upper bound on that: "serve this answer for at most 30 seconds, then fetch it again". It doesn't make the cache correct — for 30 seconds it can still be stale — but it makes the staleness bounded. Keeping caches in sync with the database properly (invalidation) is a bigger topic; see Caching Strategies.

Lazy expiry: check when asked

The simplest way to implement a TTL is lazy expiryLazy expiryChecking whether an entry has expired only when someone asks for it (and deleting it then), instead of running a timer for every entry. Cheap, but expired entries can sit in memory until they're asked for or evicted.: store an expires time in each entry, and check it in Get. No timers, no background goroutines.

type entry struct {
	key     string
	value   string
	expires time.Time
}

type TTLCache struct {
	cap   int
	ttl   time.Duration
	now   func() time.Time // ← injectable, so tests can fake time
	ll    *list.List
	items map[string]*list.Element
}

func (c *TTLCache) Get(key string) (string, bool) {
	el, ok := c.items[key]
	if !ok {
		return "", false
	}
	e := el.Value.(*entry)
	if c.now().After(e.expires) { // ← lazy expiry: checked only when asked
		c.ll.Remove(el)
		delete(c.items, key)
		return "", false // expired counts as a miss
	}
	c.ll.MoveToFront(el)
	return e.value, true
}

func (c *TTLCache) Put(key, value string) {
	exp := c.now().Add(c.ttl)
	if el, ok := c.items[key]; ok {
		e := el.Value.(*entry)
		e.value, e.expires = value, exp // a fresh write gets a fresh TTL
		c.ll.MoveToFront(el)
		return
	}
	// … evict the back if full, exactly as in §06 …
	c.items[key] = c.ll.PushFront(&entry{key, value, exp})
}

clock := time.Date(2026, 1, 1, 12, 0, 0, 0, time.UTC)
c := NewTTL(100, 30*time.Second)
c.now = func() time.Time { return clock } // fake clock

c.Put("user:42", "Ada")
fmt.Println(c.Get("user:42"))
clock = clock.Add(31 * time.Second)
fmt.Println(c.Get("user:42"))

$ go run .
Ada true
 false

(The second line starts with a space: Println prints the empty string, a space, then false.)

The catch with lazy expiry: an expired entry that nobody asks for again stays in memory until LRU happens to evict it. In a cache with a fixed capacity that's harmless — it just takes up a slot, and since nobody uses it, it drifts to the back and gets evicted soon. If you need expired entries gone promptly (to free big values), add a periodic sweep: every few seconds, walk from the back of the list and remove expired entries. Redis does a mix of both: lazy checks on access plus a background job that samples keys with TTLs.

Limit bytes, not entries

"1,000 entries" is a strange limit when one entry is a 20-byte string and another is a 2 MB image. What you actually care about is memory. A size-aware cacheSize-aware (weighted) cacheA cache whose limit is total bytes (or some other cost) instead of number of entries. Each entry reports its size; it evicts until the total fits again. gives each entry a cost (usually its size in bytes) and evicts from the back until the total fits:

// entry here is struct{ key string; val []byte }
func (c *SizedCache) Put(key string, val []byte) {
	// (existing-key case omitted)
	c.used += len(val)
	c.items[key] = c.ll.PushFront(&entry{key, val})
	for c.used > c.maxBytes && c.ll.Len() > 1 { // ← may evict several entries
		oldest := c.ll.Back()
		e := oldest.Value.(*entry)
		c.ll.Remove(oldest)
		delete(c.items, e.key)
		c.used -= len(e.val)
	}
}

Two details: one big Put can evict many small entries (a loop, not an if), and you should refuse values larger than the whole cache instead of evicting everything for them. Popular libraries offer this as a "weigher" or a maxSize plus a sizeCalculation callback.

Weak references: not a substitute

A Weak referenceWeak referenceA reference that lets you reach an object without keeping it alive. If only weak references remain, the GC may collect the object and the weak reference then gives you nothing. lets you point at an object without keeping it alive; once nothing else uses it, the garbage collectorGarbage collector (GC)Part of the language runtime that automatically frees memory nobody can reach anymore. Anything still referenced — like a stuck goroutine — is never freed. may free it. JavaScript has WeakRef, and Go 1.24 added the weak package (weak.Make(ptr), then .Value()). It's tempting to build a "cache that frees itself under memory pressure" from them.

Don't, for an LRU cache. The GC decides when entries disappear, not your policy: an entry can vanish a millisecond after you stored it, or survive for hours, depending on when collections happen. Your hit rate becomes unpredictable and hard to reason about. Weak references are good for something narrower — "if this object is still alive somewhere, reuse it" (deduplicating identical objects, say) — not for "keep the N most useful answers".

Many goroutines: locks, shards, and a surprising benchmark

The caches from §06–09 are not safe to use from several goroutines at once. Two goroutines calling Get at the same moment both rewrite head.next and their neighbours' pointers; interleave those six writes badly and the list ends up with a loop or a lost node. In Go that's a Data raceData raceTwo threads or goroutines access the same memory, at least one of them writes, and nothing orders the two accesses (no lock, channel or atomic between them). The result is unpredictable.; see Race Conditions. (JavaScript code runs on one thread, so a JS cache doesn't need this section unless you share it between workers.)

The simple fix: one mutex

type SafeCache[K comparable, V any] struct {
	mu sync.Mutex
	c  *Cache[K, V] // the generic cache from §06
}

func NewSafe[K comparable, V any](capacity int) *SafeCache[K, V] {
	return &SafeCache[K, V]{c: New[K, V](capacity)}
}

func (s *SafeCache[K, V]) Get(key K) (V, bool) {
	s.mu.Lock() // ← not RLock: Get moves the node, which is a write
	defer s.mu.Unlock()
	return s.c.Get(key)
}

func (s *SafeCache[K, V]) Put(key K, val V) {
	s.mu.Lock()
	defer s.mu.Unlock()
	s.c.Put(key, val)
}

A LockLock (mutex)A “do not disturb” sign for a piece of data: only the task holding the lock may touch it; others wait their turn. (sync.Mutex) lets one goroutine at a time inside; defer s.mu.Unlock() releases it when the function returns, even on a panic. Locks: sync.Mutex covers this in depth.

Sharding: many small caches

With one lock, goroutines queue up — that's Lock contentionLock contentionSeveral tasks wanting the same lock at the same moment, so all but one must wait. Under heavy contention, adding CPU cores doesn't make the program faster.. The standard fix is shardingSharding (lock striping)Splitting one big structure into N independent pieces, each with its own lock. A key's piece is chosen by turning the key into a number (hashing it) and taking it modulo N.: split the cache into N independent small caches, each with its own lock, and pick one by hashing the key.

type Sharded[K comparable, V any] struct {
	seed   maphash.Seed
	shards []*SafeCache[K, V]
}

func NewSharded[K comparable, V any](capacity, n int) *Sharded[K, V] {
	s := &Sharded[K, V]{seed: maphash.MakeSeed()}
	per := max(1, (capacity+n-1)/n) // round up; never 0 (New panics on 0)
	for range n {
		s.shards = append(s.shards, NewSafe[K, V](per))
	}
	return s
}

func (s *Sharded[K, V]) shard(key K) *SafeCache[K, V] {
	h := maphash.Comparable(s.seed, key) // ← hash any comparable key (Go 1.24+)
	return s.shards[h%uint64(len(s.shards))]
}

func (s *Sharded[K, V]) Get(key K) (V, bool) { return s.shard(key).Get(key) }
func (s *Sharded[K, V]) Put(key K, val V)    { s.shard(key).Put(key, val) }

Two trade-offs. Each shard evicts on its own, so the cache as a whole is only approximately LRU: shard 3 may evict a key that's newer than the oldest key in shard 1. And one very popular key (a Hot key / hot spotHot key / hot spotA single key (or a narrow range) that gets far more traffic than the rest, like a celebrity's profile. Because one key always lives on one shard, that shard overloads while the others idle.) still lives in exactly one shard, so all its traffic still queues on one lock.

What we measured

We benchmarked these on a 4-core Linux cloud VM with Go 1.24, using b.RunParallel, which runs the same loop on several goroutines at once. The workload: 20,000 keys, all already cached, so every call is a Get hit. "ns/op" here is wall-clock time per operation for the whole machine — if 4 goroutines worked perfectly in parallel, the 4-goroutine number would be a quarter of the 1-goroutine number. Medians of 5 runs; lower is better. The VM is noisy (the one-lock, 4-goroutine runs ranged from 87 to 157 ns/op), so read the table as rough shapes, not exact numbers.

And from an earlier run with the same setup:

Adding cores made the single-lock cache slower: goroutines spent their time waiting for the lock and passing it around. That's expected. The surprise is the second row: sharding didn't help for small values, even though each shard has its own lock.

The reason is the other thing every Get touches: the list. A hit writes to the node, its neighbours and the sentinel — memory that another core touched a moment ago. Each core keeps its own copy of recently used memory, and when one core writes, the hardware must pull that memory away from the others before anyone else can use it (Cache coherenceCache coherenceThe hardware protocol that keeps every core's private cache consistent, so two cores never keep different values for the same address forever. It's automatic, but it costs time when cores write to the same cache line.; see CPU Caches: coherence). That transfer costs far more than the lock does.

"But each shard has its own lock and its own list — why would they bounce?" Because every core uses every shard. Each of the 4 goroutines asks for random keys, so it hits all 16 shards in turn. When core 2 locks shard 7, the last core to touch shard 7's mutex, sentinel and nodes was most likely core 1, 3 or 4, so that memory has to move over first. Sharding means two goroutines rarely wait for the same lock at the same moment; it does nothing about the memory moving. Sharding removes waiting for the lock; it doesn't remove memory bouncing between cores.

There's a second, smaller effect. Each SafeCache is a 16-byte object, and memory moves between cores in 64-byte cache linesCache lineThe chunk of memory (usually 64 bytes) that a CPU core copies into its own fast cache. When two cores write to the same cache line, it has to bounce between them, which is slow., so about four shards' mutexes can share one line. Locking shard 1 then also pulls shard 2's mutex away from whoever was using it. That's False sharingFalse sharingTwo cores update two different variables that happen to sit in the same cache line, so the line bounces between them as if they shared one variable. (CPU Caches: false sharing). The third row of the table pads each shard so its mutex has its own lines. In our runs that barely moved the needle, so the main problem here is the first effect.

The second table shows both effects. When the lock is held longer (copying a 512-byte value), lock waiting dominates and sharding wins clearly. When hits stop rewriting the list (CLOCK, §11, mostly just reads a bit), even small values scale better.

Beyond LRU: scans, LFU, W-TinyLFU and CLOCK

LRU's weak spot: the scan

A scanScan (cache)A burst of requests for many different keys, each asked for only once — a report reading every row, a crawler, a backup. Under plain LRU each new key pushes out a useful one. is a burst of requests for many different keys, each asked for once: a nightly report reading every customer, a search-engine crawler walking every page. To LRU, each scanned key is "the most recently used thing" and goes to the front. If the scan has more keys than the cache has slots, it pushes every popular entry out the back. After the scan, the cache is full of keys nobody will ask for again, and the popular ones all miss.

The fix is to be scan-resistantScan-resistantA cache policy that doesn't let a one-time scan push out the entries that are used again and again — usually by making a new key prove itself (a second hit) before it can displace older favourites.. The simplest version is segmented LRUSegmented LRU (SLRU)LRU split into two parts: new keys enter a small “probation” area; only a second hit promotes a key into the larger “protected” area. A one-time scan churns probation and leaves protected alone.: split the cache into a small probation area and a large protected area. New keys enter probation. Only a second hit promotes a key into protected. A scan's keys are each used once, so they only churn through probation; protected stays untouched.

The same idea with different details shows up again and again: 2Q2QA 1994 scan-resistant policy: new keys go into a small FIFO queue first, and only keys requested again move into the main LRU list. The idea is close to segmented LRU. (1994) uses a small FIFO for first-timers; ARCARC (Adaptive Replacement Cache)A policy from IBM researchers (2003) that keeps one LRU list for keys seen once and one for keys seen twice or more, plus “ghost” lists of recently evicted keys, and shifts space between the two lists depending on which ghosts get asked for again. (2003) keeps "seen once" and "seen twice+" lists and resizes them automatically using ghost entriesGhost entryA remembered key without its value — “this was in the cache recently and got evicted”. If a ghost key is requested again, the policy learns it evicted the wrong thing. — keys it evicted recently, remembered without their values. If a ghost is requested again, ARC learns it gave that list too little room. The Linux kernel's page cache has a similar shape: an "inactive" list for pages touched once and an "active" list for pages touched again.

Frequency, done carefully: W-TinyLFU

LFULFU (least frequently used)An eviction policy that counts how often each entry is used and throws out the one with the smallest count. Good at keeping long-term favourites; slow to forget things that used to be popular. fixes scans differently: a scanned key has a count of 1, so it never beats a popular entry. But §03 showed LFU's problem — it clings to what used to be popular — and counting every key costs memory.

W-TinyLFUW-TinyLFUThe policy behind Java's Caffeine cache: a tiny LRU “window” for brand-new keys, a segmented-LRU main area, and an admission check using approximate request counts (a count-min sketch) that also remembers keys that aren't cached., the policy in Java's Caffeine library, combines the ideas:

1. A tiny LRU window (about 1% of the space) where every new key lands, so a brand-new key gets a chance.
2. A segmented-LRU main area for the rest.
3. An admissionAdmission policyA rule that decides whether a new key is allowed into the cache at all. LRU admits everything; TinyLFU only admits a newcomer if it's been asked for more often than the entry it would replace. check between them. When a key leaves the window, it only enters the main area if it's been requested more often than the main area's next victim. Otherwise the newcomer is dropped.

The request counts live in a Count-min sketchCount-min sketchA small, fixed-size table of counters that estimates how often each key was seen, without storing the keys. Several hash functions pick counters; you take the smallest. It can overestimate, never underestimate. — a small table of 4-bit counters that estimates "how often have I seen this key?", including keys that aren't cached. All counters are halved periodically, so old popularity fades. In Go, ristretto (by Dgraph) uses TinyLFU-style admission with sampled eviction, and newer libraries such as otter follow Caffeine's design more closely — check each library's docs for current details.

Now compare all of them. Each workload is replayed through each policy:

What to notice:

• Skewed trafficSkewed (Zipf-like) trafficTraffic where a few keys get most of the requests and a long tail of keys is rarely asked for — like a handful of viral posts among millions. Most real cache traffic looks like this, which is why small caches work at all. (50 slots): LFU and W-TinyLFU beat LRU clearly (~48% vs ~36%). With a long tail of rare keys, frequency is a better signal than one recent use. FIFO and random trail.
• Hot set + scans: switch to 20 slots. Scan resistance pays off: LRU ~45%, W-TinyLFU ~53%. At 50 slots the gap is small (82.6% vs 86.7%), because the 50 hot keys fit and refill quickly after each scan.
• Loop (50 slots): 120 keys in a loop. LRU, FIFO and LFU all score 0% — each key is evicted just before it comes round again. Random eviction gets ~12% by luck; W-TinyLFU's admission check refuses to churn and gets ~39%.
• Shifting (50 slots): LFU collapses (~29%): the old favourites' counts keep them cached after nobody wants them. LRU adapts; W-TinyLFU adapts and filters.

CLOCK: LRU without the list

Every LRU hit moves a node to the front, which means writing shared memory (§10). For something as hot as an operating system's memory pages — touched billions of times per second — that's far too expensive. Operating systems use an approximation instead: the CLOCK algorithmCLOCK algorithmA cheap approximation of LRU: entries sit in a circle, each with a “used recently” bit. A hit just sets the bit. To evict, a hand sweeps round the circle: a set bit is cleared (a second chance), the first clear bit is evicted..

Entries sit in a circle of slots, each with one Reference bitReference bitA single yes/no flag per entry meaning “used since the CLOCK hand last passed here”. For memory pages, the CPU sets it in hardware whenever the page is touched.. A hit just sets the bit to 1. To evict, a "hand" sweeps around the circle: a slot with bit 1 gets a second chance (the bit is cleared, the hand moves on); the first slot with bit 0 is evicted.

type slot[K comparable, V any] struct {
	key K
	val V
	ref bool // "used since the hand last passed?"
}

type Clock[K comparable, V any] struct {
	slots []slot[K, V] // fixed-size ring
	index map[K]int    // key → position in slots
	hand  int          // next slot to consider for eviction
}

func (c *Clock[K, V]) Get(key K) (V, bool) {
	i, ok := c.index[key]
	if !ok {
		var zero V
		return zero, false
	}
	if !c.slots[i].ref {
		c.slots[i].ref = true // ← the only write on a hit, and usually skipped
		// (still a write: shared between goroutines it needs the lock or an atomic.Bool)
	}
	return c.slots[i].val, true
}

// Put, when full: sweep until a slot with ref == false, then replace it.
//	for c.slots[c.hand].ref {
//		c.slots[c.hand].ref = false // second chance
//		c.hand = (c.hand + 1) % len(c.slots)
//	}

A hit costs one map lookup and, at most, setting one bit — no pointers move. Eviction is O(1) Amortized costAmortized costThe average cost per operation over a long sequence, when most operations are cheap and a rare one is expensive — e.g. appending to a slice is O(1) amortized even though an occasional append copies everything.: one sweep may clear many bits, but every bit it clears was set by an earlier hit, so the total sweeping work never exceeds the number of hits plus evictions. CLOCK also uses a plain slice instead of a linked list, so there are no per-entry nodes to allocate.

Where you'll find it (in some form):

• Operating systems. Memory is managed in 4 KB pages, and the CPU sets an "accessed" bit in the Page tablePage table (and pages)Memory is handled in chunks called pages (usually 4 KB). A page table is the per-process lookup table that says “virtual page X lives at physical RAM spot Y”. The CPU consults it on every memory access. whenever a page is touched — a hardware reference bit, for free. The kernel's page reclaim scans those bits to decide which pages to drop from the Page cachePage cacheThe kernel's cache of file contents in RAM. Every normal file read and write goes through it, and mmap maps its pages straight into your process. Free RAM fills up with it, which is fine: it's dropped when memory is needed. or move to SwapSwapDisk space the OS uses as overflow for RAM: rarely used memory pages are written out to make room. Reading them back is thousands of times slower than RAM, so heavy swapping makes everything crawl. (Virtual Memory). Linux's design is more elaborate (active/inactive lists, and an optional multi-generational LRU since 6.1), but the reference-bit sweep is the core idea.
• PostgreSQL's buffer cache uses "clock sweep" with a small usage counter (up to 5) per buffer instead of a single bit.

Staff-level: LRU caches in production

What an entry really costs

We measured 1 million entries in Go 1.24 on a 4-core Linux VM (keys like "user:1000042" created beforehand, so only the cache's own memory is counted; values are int64, 8 bytes):

So the LRU bookkeeping roughly doubles a bare map, before counting the key's characters or the value itself. Where it goes: each node holds the key (a 16-byte string header), the value (8) and two pointers (16) — 40 bytes, rounded up to 48 by Go's allocator — and the map stores the key again plus a pointer to the node, with some spare room. container/list adds a separate small entry object per item.

For small values that overhead dominates: a cache of a million 8-byte values uses ~100 MB of bookkeeping for 8 MB of data. And every pointer in it is something the garbage collectorGarbage collector (GC)Part of the language runtime that automatically frees memory nobody can reach anymore. Anything still referenced — like a stuck goroutine — is never freed. has to trace; a large pointer-heavy cache makes every GC cycle longer (Garbage Collection). That's why some high-volume Go caches store entries in big byte slices instead of nodes.

Redis: approximate LRU by sampling

RedisRedisA popular in-memory data server: a fast key–value store and cache that also offers counters, sorted sets, pub/sub channels and streams (an append-only log for messages). is often used as a shared LRU cache: set maxmemory 2gb and maxmemory-policy allkeys-lru, and Redis evicts when memory runs out. But it doesn't keep a linked list — that would cost two pointers per key across millions of keys. Instead (as Redis's docs describe it), each key stores a small "last accessed" timestamp, and to evict Redis samples a handful of random keys (maxmemory-samples, default 5) and evicts the oldest of those, keeping a small pool of good candidates between rounds.

That's approximate LRUApproximate LRUAny policy that usually evicts something old without tracking the exact order — CLOCK, or Redis picking a few random keys and evicting the oldest of them. Much cheaper, almost as good.: it won't always pick the oldest key, but with 5–10 samples it's close, and it costs no extra memory per key. Other policies to know (check your version's docs): allkeys-lfu (Redis 4.0+, a decaying frequency counter), the volatile-* variants that only evict keys with a TTL, and noeviction — the default in open-source Redis — which rejects writes when memory is full. A Redis "cache" left on noeviction starts failing writes the day it fills up.

Watch the hit rate

You can't tune what you don't measure. Every cache should export at least three countersCounter (metric)A metric that only ever goes up: total requests, total rejections. Dashboards usually show how fast it grows (per second).: hits, misses, evictions. Dashboards then show:

• Hit rate = hits ÷ (hits + misses). Alert on a sudden drop: a deploy that changed key formats, a new traffic pattern, a scan.
• Evictions per second. High evictions with a low hit rate means the cache is too small for the working setWorking set (of a cache)The keys being actively requested right now. If they all fit in the cache, the hit rate is high; if the cache is smaller, entries keep evicting each other. — the set of keys in active use.
• Miss latency, as a HistogramHistogram (metric)A metric that records how many measurements fell into each range (0–10 ms, 10–50 ms, …), so you can later compute percentiles like p50 and p99.. This is what users feel on a miss.

type stats struct{ hits, misses, evictions atomic.Int64 }

// SafeCache from §10, with one more field: stats stats

func (s *SafeCache[K, V]) Get(key K) (V, bool) {
	s.mu.Lock()
	v, ok := s.c.Get(key)
	s.mu.Unlock()
	if ok {
		s.stats.hits.Add(1) // ← export these as metrics
	} else {
		s.stats.misses.Add(1)
	}
	return v, ok
}

A cheap trick for sizing: briefly run a second, bigger "shadow" cache that holds only keys (no values) on a sample of traffic, and compare hit rates. If doubling the size would raise the hit rate from 85% to 95%, misses drop from 15% to 5% of requests: two-thirds of the misses gone, so 3× fewer database queries.

The cache that makes p99 worse

A cache makes the average much better. It can make the slowest requests — the p99p99 (99th percentile)The value that 99% of measurements are below — i.e. how bad the slowest 1% is. Averages hide slow outliers; p99 shows them. — no better at all, and occasionally much worse.

First, the arithmetic. With a 95% hit rate, 5% of requests are misses. The p99 is the time that 99% of requests beat, which lands inside the misses. So your p99 is your miss latency: the cache did nothing for it. Only above a 99% hit rate does the p99 start to fall.

Second, misses arrive together. A hot key's TTL expires; every request in the next 50 ms misses and queries the database for the same row. A deploy restarts all servers with a cold cacheCold cacheA cache that is empty or nearly empty (just started, just flushed), so almost every request misses until it fills up again. A warm cache already holds the popular entries.; for a few minutes almost everything misses. That's a miss stormMiss stormMany requests missing the cache at the same moment — after a restart, a flush, or the expiry of a hot key — so they all hit the slow source together. A form of thundering herd. — a form of Thundering herdThundering herdMany clients hitting a server at the same moment — e.g. all retrying together right after an outage — which knocks it over again.:

The database was sized for the 1–5% of traffic that normally misses. A miss storm can send it 20× that, it slows down, misses take longer, more requests pile up — and the latency spike outlasts the event that caused it. The standard mitigations, each covered in Caching Strategies:

• Coalesce identical misses — only one request loads the key, the rest wait for its answer (Go's singleflightsingleflightA Go package (golang.org/x/sync/singleflight, not the standard library) that merges identical calls made at the same time: only one actually runs, and every caller gets its result. package, golang.org/x/sync/singleflight, does this).
• Jitter TTLs (§09) so keys don't expire together.
• Serve slightly stale data while one request refreshes it in the background.
• Warm the cache before a new server takes full traffic.

var cache = map[string]*User{} // "cache"

Check yourself

Predict the answer before you click. Q1 is §04–06, Q2 is §10, Q3 is §11, Q4 is §07, Q5 is §08 and Q6 is §02.

c := New[string, int](2)
c.Put("a", 1)
c.Put("b", 2)
c.Get("a")
c.Put("c", 3)
_, okA := c.Get("a")
_, okB := c.Get("b")
fmt.Println(okA, okB)

const m = new Map([["a", 1], ["b", 2], ["c", 3]]);
m.set("a", 10);
m.delete("b");
m.set("b", 20);
console.log([...m.keys()].join(","));

if c.ll.Len() == c.cap {
    oldest := c.ll.Back()
    c.ll.Remove(oldest)
    // forgot: delete(c.items, oldest.Value.(*entry).key)
}

Cheat sheet