01 / The idea
Was this answered a moment ago?
A café prints short links on everything: menu on the tables, wifi by the till, hours on the door. Each scan asks the link service
where a slug points, and the answer lives in a store: a database, somewhere slower than memory.
Most scans ask about a link someone asked about recently. Keeping those answers in memory skips
the store.
Memory is not free, so the cache holds a fixed number of links. When it is full and a new
answer arrives, something goes. Least recently used is the rule: forget the
link that has gone longest without a scan, on the bet that what was used recently will be
used again soon. Python’s functools.lru_cache keeps “up to the maxsize most
recent calls,” 128 by default. OpenLayers keeps map tiles in an LRUCache. Redis can evict keys the same way when it runs out of memory.
An LRU cache is two structures you have already met, kept in step. A hash map finds a link’s entry without searching. A doubly linked list keeps the entries in order of use, so moving one to the front and dropping one from the back never shifts the rest. The Linked list lesson ended on exactly this composition. Here it gets a job.
02 / Name the rule
Find it in the map. Move it in the list. Evict from the back.
The cache has a capacity, three in the story. The list runs from the most recently used entry at the front to the least recently used at the back, and the map points from each slug to its entry in that list.
A hit finds the slug in the map, returns its URL, and moves its entry to the front. A miss asks the store, then puts the answer in the map and at the front of the list. If the cache was already full, the entry at the back is evicted first: unlinked from the list and deleted from the map. Invalidating a link removes it from both, so the next scan reads the store.
The invariant: the map and the list hold exactly the same entries, never more than the capacity, and the list order is the order of last use. A hit only reorders the list; every operation that adds or removes an entry changes both structures. Break that, and the map points at an entry the list has dropped, or the list evicts a link the map still hands out.
Why is there a sentinel?No empty-list special cases
The list is a ring around one extra entry that holds no link, the sentinel. Its next pointer is the most recent entry and its previous pointer is the least recent. In an empty cache, both point back at the sentinel itself.
That makes every change the same shape. Unlinking any entry writes two fields: its
previous neighbor’s next, and its next neighbor’s previous. Linking at the front writes
four: the entry’s own two, the old front’s previous, and the sentinel’s next. There is no
“is this the head?” or “was the list empty?” branch, which is where hand-written linked
lists usually break. CPython’s lru_cache uses the same circular list with a root
entry.
03 / Follow one operation
A hit, an eviction, and a menu that changed.
The cache starts with three links. wifi was scanned first, then hours, then menu, so menu is at the front and wifi at the back. Then someone scans wifi, someone scans the survey link on a receipt, and the café moves its menu to a summer page.
Before you watch, predict which link survey pushes out. wifi was cached first. Is it the one that goes? The animation replays each recorded lookup and link change. Try it lets you scan links, change them in the store, and invalidate them yourself.
Find it in the map, move it in the list.
Scan a link to look it up.
Map · slug → entry, in no useful order
hoursmenuwifi
List · most recent first
- most recent menu /menu/spring
- hours /hours
- least recent wifi /wifi
3 of 3 cached · 0 link fields written in this call
Three links cached, most recent first.
Scans of wifi, hours, and menu each missed, so the store answered and the cache kept the result. menu was scanned last, so it is at the front, and wifi, the first, is at the back.
Reduced motion: choose a scene to see its completed state.
Read this scene
Scans of wifi, hours, and menu each missed, so the store answered and the cache kept the result. menu was scanned last, so it is at the front, and wifi, the first, is at the back.
Scans of wifi, hours, and menu each missed, so the store answered and the cache kept the result. menu was scanned last, so it is at the front, and wifi, the first, is at the back.
Cached, most recent first: menu, hours, wifi.
Watch restarts when you return. Step through keeps your selected step. Try it starts a fresh cache each time you open it.
04 / Read the shape
The cache orders entries. The resolver decides what may be cached.
Basic form is the LRU cache alone: get, peek, set, delete, the sentinel
ring, and eviction. In the wild wraps it in RedirectCache,
which owns the link service’s rules. A malformed slug is refused before any lookup. A slug
the store does not have is not cached, because a flood of made-up slugs would otherwise push
real links out. And a link its owner changes is invalidated, because the cache has no way to
notice on its own.
peek reads without counting as a use. That matters more than it looks: a dashboard
that lists the cached links must not reorder them by looking.
An LRU cache of strings: a map from key to entry, and a doubly linked ring of entries around a sentinel. A hit moves to the front, a new key goes in at the front, and a full cache evicts the entry just before the sentinel. The optional trace records every lookup and link change.
const MAX_CAPACITY = 2 ** 31 - 1;
export type Step = {
kind: 'hit' | 'miss' | 'update' | 'insert' | 'evict' | 'unlink' | 'front' | 'remove';
key: string;
/** Link fields written: 2 to take an entry out of the list, 4 to link one at the front. */
links: number;
};
type Entry = { key: string; value: string; prev: Entry; next: Entry };
// Two structures kept in step. A hash map finds an entry by key; a doubly linked list
// keeps entries in recency order. The list is a ring around a sentinel: sentinel.next
// is the most recent entry and sentinel.prev the least recent, so an empty list and
// both ends need no special cases.
export class LRUCache {
readonly capacity: number;
#entries = new Map<string, Entry>();
#sentinel: Entry;
#steps: Step[] = [];
#capture: boolean;
constructor(capacity: number, trace = false) {
if (!Number.isInteger(capacity) || capacity < 1 || capacity > MAX_CAPACITY)
throw new RangeError('capacity must be an integer from 1 to 2147483647');
this.capacity = capacity;
const sentinel = { key: '', value: '' } as Entry;
sentinel.prev = sentinel;
sentinel.next = sentinel;
this.#sentinel = sentinel;
this.#capture = trace;
}
get size(): number {
return this.#entries.size;
}
// A hit becomes the most recent entry. A miss changes nothing.
get(key: string): string | undefined {
this.#steps = [];
const entry = this.#entries.get(key);
if (!entry) {
this.#record('miss', key, 0);
return undefined;
}
this.#record('hit', key, 0);
this.#moveToFront(entry);
return entry.value;
}
// Read a value without counting it as a use.
peek(key: string): string | undefined {
return this.#entries.get(key)?.value;
}
// Store a value as the most recent entry. Returns the key evicted to make room, or null.
set(key: string, value: string): string | null {
this.#steps = [];
const existing = this.#entries.get(key);
if (existing) {
existing.value = value;
this.#record('update', key, 0);
this.#moveToFront(existing);
return null;
}
let evicted: string | null = null;
if (this.#entries.size === this.capacity) {
const oldest = this.#sentinel.prev;
this.#unlink(oldest);
this.#entries.delete(oldest.key);
this.#record('evict', oldest.key, 2);
evicted = oldest.key;
}
const entry = { key, value } as Entry;
this.#entries.set(key, entry);
this.#record('insert', key, 0);
this.#linkFront(entry);
this.#record('front', key, 4);
return evicted;
}
delete(key: string): boolean {
this.#steps = [];
const entry = this.#entries.get(key);
if (!entry) {
this.#record('miss', key, 0);
return false;
}
this.#unlink(entry);
this.#entries.delete(key);
this.#record('remove', key, 2);
return true;
}
// Most recent first.
keys(): string[] {
const keys: string[] = [];
for (let entry = this.#sentinel.next; entry !== this.#sentinel; entry = entry.next)
keys.push(entry.key);
return keys;
}
trace(): Step[] {
return this.#steps.map((step) => ({ ...step }));
}
#moveToFront(entry: Entry): void {
if (this.#sentinel.next === entry) return;
this.#unlink(entry);
this.#record('unlink', entry.key, 2);
this.#linkFront(entry);
this.#record('front', entry.key, 4);
}
#unlink(entry: Entry): void {
entry.prev.next = entry.next;
entry.next.prev = entry.prev;
}
#linkFront(entry: Entry): void {
entry.prev = this.#sentinel;
entry.next = this.#sentinel.next;
this.#sentinel.next.prev = entry;
this.#sentinel.next = entry;
}
#record(kind: Step['kind'], key: string, links: number): void {
if (this.#capture) this.#steps.push({ kind, key, links });
}
}const maxCapacity = 1<<31 - 1
type Step struct {
Kind string `json:"kind"`
Key string `json:"key"`
// Links counts link fields written: 2 to take an entry out of the list, 4 to
// link one at the front.
Links int `json:"links"`
}
type entry struct {
key, value string
prev, next *entry
}
// LRUCache keeps two structures in step. A map finds an entry by key; a doubly
// linked list keeps entries in recency order. The list is a ring around a sentinel:
// sentinel.next is the most recent entry and sentinel.prev the least recent, so an
// empty list and both ends need no special cases. Use it through its pointer; a
// copy would still point at the original's sentinel.
type LRUCache struct {
capacity int
entries map[string]*entry
sentinel entry
steps []Step
capture bool
}
func NewLRUCache(capacity int, trace bool) (*LRUCache, error) {
if capacity < 1 || capacity > maxCapacity {
return nil, errors.New("capacity must be an integer from 1 to 2147483647")
}
c := &LRUCache{capacity: capacity, entries: map[string]*entry{}, capture: trace}
c.sentinel.prev = &c.sentinel
c.sentinel.next = &c.sentinel
return c, nil
}
func (c *LRUCache) Capacity() int { return c.capacity }
func (c *LRUCache) Len() int { return len(c.entries) }
// Get makes a hit the most recent entry. A miss changes nothing.
func (c *LRUCache) Get(key string) (string, bool) {
c.steps = nil
e, ok := c.entries[key]
if !ok {
c.record("miss", key, 0)
return "", false
}
c.record("hit", key, 0)
c.moveToFront(e)
return e.value, true
}
// Peek reads a value without counting it as a use.
func (c *LRUCache) Peek(key string) (string, bool) {
if e, ok := c.entries[key]; ok {
return e.value, true
}
return "", false
}
// Set stores a value as the most recent entry. It returns the key evicted to make
// room, if any.
func (c *LRUCache) Set(key, value string) (evicted string, ok bool) {
c.steps = nil
if e, found := c.entries[key]; found {
e.value = value
c.record("update", key, 0)
c.moveToFront(e)
return "", false
}
if len(c.entries) == c.capacity {
oldest := c.sentinel.prev
c.unlink(oldest)
delete(c.entries, oldest.key)
c.record("evict", oldest.key, 2)
evicted, ok = oldest.key, true
}
e := &entry{key: key, value: value}
c.entries[key] = e
c.record("insert", key, 0)
c.linkFront(e)
c.record("front", key, 4)
return evicted, ok
}
func (c *LRUCache) Delete(key string) bool {
c.steps = nil
e, ok := c.entries[key]
if !ok {
c.record("miss", key, 0)
return false
}
c.unlink(e)
delete(c.entries, key)
c.record("remove", key, 2)
return true
}
// Keys returns the keys, most recent first.
func (c *LRUCache) Keys() []string {
keys := make([]string, 0, len(c.entries))
for e := c.sentinel.next; e != &c.sentinel; e = e.next {
keys = append(keys, e.key)
}
return keys
}
func (c *LRUCache) Trace() []Step { return append([]Step{}, c.steps...) }
func (c *LRUCache) moveToFront(e *entry) {
if c.sentinel.next == e {
return
}
c.unlink(e)
c.record("unlink", e.key, 2)
c.linkFront(e)
c.record("front", e.key, 4)
}
func (c *LRUCache) unlink(e *entry) {
e.prev.next = e.next
e.next.prev = e.prev
}
func (c *LRUCache) linkFront(e *entry) {
e.prev = &c.sentinel
e.next = c.sentinel.next
c.sentinel.next.prev = e
c.sentinel.next = e
}
func (c *LRUCache) record(kind, key string, links int) {
if c.capture {
c.steps = append(c.steps, Step{kind, key, links})
}
}Reading the TypeScriptPrivate fields and a typed ring
Entries are plain objects with prev and next. The sentinel is
created with a type assertion and then pointed at itself, so the type can promise that
every link is an entry, never null.
The index is a built-in Map. get returns undefined for a miss, which is why an empty-string URL is still a hit: the
check is !== undefined, not truthiness.
Reading the GoA sentinel inside the struct
The sentinel is a field of LRUCache, and entries point at its address. That
is safe because the cache is only used through the pointer NewLRUCache returns. A copied struct would still point at the original’s sentinel.
Get and Peek return a value and an ok flag, and Set returns the evicted key with its own flag, so an empty key or value is never
confused with “nothing.” The cache is not safe for concurrent use; a server would put a mutex
around it.
What would I normally use in application code?A few lines of Map, or a well-worn package
In TypeScript, a Map is nearly an LRU cache already. It iterates in insertion
order, so its first key is the least recent. The catch is in the specification: set on a key the map already has updates the value in place and keeps its
position. A use has to delete the key and set it again. For
more, the lru-cache package
limits by count with max, by size with maxSize and sizeCalculation, and can add a ttl.
In Go, github.com/hashicorp/golang-lru/v2 offers lru.New[K, V](size); its simplelru package is the
unsynchronized core. The lru package in groupcache, built for dl.google.com, is
a map beside container/list, the same two structures as this lesson.
05 / Try a decision
When does the new menu appear?
Invalidation is easy to forget, especially when the cache usually seems to fix itself through eviction. Decide how long a forgotten one lasts before the feedback tells you.
06 / Follow the cost
Every call is constant work. The hit rate is what capacity buys.
Here is every operation at a glance, with n links cached. None of them depends on how many links there are, apart from listing them.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Scan a cached link (hit) | O(1) average | O(1) | One map lookup, then at most six link fields: two to unlink the entry, four to link it at the front. The rest of the list is not touched. |
| Scan an uncached link (miss) | O(1) average, plus one store lookup | O(1) | The store is the slow part the cache exists to avoid. Caching the answer is a map insert and four link fields. |
| Evict the least recently used | O(1) | O(1) | It is always the entry just before the sentinel: two link fields and a map delete, with no search. |
| Invalidate a link | O(1) average | O(1) | One map lookup, two link fields, one map delete. |
| Check a slug of k characters | O(k) | O(1) | Hashing and comparing the slug in the map also reads its characters; k is at most 32. |
| List the cached links | O(n) | O(n) | Walks the list from the front, so the order is most recent first. |
| Hold n links, up to the capacity | — | O(n) | Each link costs a map entry and a list entry with two links, on top of its slug and URL. The limit counts links, not bytes. |
In the animation, wifi’s hit wrote six link fields, survey’s miss wrote six more, two to evict hours and four to link survey, and invalidating menu wrote two. With a million links cached, those numbers would be the same.
Constant work per call says nothing about whether the cache helps. That depends on how often a scan finds its link already cached, the hit rate, and on the pattern of requests. To see the shape, this lesson’s model replayed 200,000 requests over 10,000 links whose popularity follows a Zipf distribution, where the second most popular link gets half the traffic of the first and the tenth gets a tenth. That is a common modeling assumption, not measured link traffic.
Caching 10 links answered 13.2% of requests from memory, 100 links 39.3%, and 1,000 links 67.6%. Each tenfold increase in memory added only 26 to 28 percentage points. First in, first out, which evicts the oldest insertion regardless of use, scored 11.5%, 34.4%, and 63.2% on the same requests. Bélády’s algorithm, which evicts the link whose next request is furthest in the future and so needs to see the future, sets the ceiling: 33.2%, 58.3%, and 81.4%. No real cache can reach it, but it shows how much a cleverer policy could gain.
LRU also adapts. When the model reshuffled which links were popular halfway through, a 100-link cache answered 39.0% of the second half from memory, close to the 39.3% of a run whose popular set never moved. Nothing had to be told the popular set had moved; old favorites stopped being used and fell to the back.
07 / Give it a real job
Size it, invalidate it, and know which copy you are clearing.
In a real service, the resolver sits in front of the database, and every place that edits or
deletes a link calls invalidate after the write succeeds. Capacity comes from memory
and measurement: the count of links, or a byte budget if URLs vary a lot in length, chosen by
watching the hit rate rather than guessed.
What the resolver leaves out is a decision too. It is one cache in one process. Run the service on several servers and each has its own copy, so an invalidation has to reach all of them, or entries need a time limit that bounds how long a missed one lasts. It is not safe for concurrent requests without a lock. And it caches forever while a link stays popular, which is exactly why the exercise’s menu stayed stale.
Build UIs?See the LRU caches already under your pages, and the day you keep one yourself.
Where it already is in your components
Pan an OpenLayers map away and back, and the tiles reappear without new requests: its
canvas tile layer keeps them in an LRUCache with a size limit, dropping the
least recently used tile when it needs room. The Linked list lesson built the same kind of tile cache
by hand.
Not every cache you use is an LRU cache, and the difference shows up in behavior. TanStack
Query, for example, removes a query’s data once nothing has used it for its gcTime, five minutes by default: a limit in time, not in count. Knowing which
rule a cache follows tells you whether a burst of new data can push out what you still
need.
When you have to own it
Picture a search box over a person’s projects. They type, backspace, and type again, and
every query they return to is a request you already answered. Keep recent result lists in
memory, keyed by query, with a limit, so a long session cannot hold every list ever
fetched. A Map with delete-then-set is enough.
Then it gets real. The key must include everything that changes the answer, such as an “include archived” toggle, not just the text. Creating or renaming a project can change any result list, so forget them all rather than guessing which. And never keep the cache in a module-level variable in an app where people sign in and out: the next person on the same browser would see the last person’s results. Scope it to the signed-in account.
Search results kept in a Map with a limit of 50. A query seen a moment ago answers from memory with no request, and a changed query cancels the one in flight.
import { useEffect, useState } from 'react';
type Project = { id: string; name: string };
// Recent search results, least recent first. A Map iterates in insertion order, and
// set() on a key it already has keeps that key's place, so a use is delete then set.
const results = new Map<string, Project[]>();
const LIMIT = 50;
function recall(query: string) {
const hit = results.get(query);
if (hit) {
results.delete(query);
results.set(query, hit);
}
return hit;
}
function remember(query: string, projects: Project[]) {
results.delete(query);
results.set(query, projects);
if (results.size > LIMIT) results.delete(results.keys().next().value!);
}
export function useSearch(query: string) {
const [found, setFound] = useState<{ query: string; projects: Project[] } | null>(null);
useEffect(() => {
// Backspacing to a query seen a moment ago answers from memory, with no request.
if (recall(query)) return;
const controller = new AbortController();
fetch(`/api/projects?q=${encodeURIComponent(query)}`, { signal: controller.signal })
.then((response) => response.json() as Promise<Project[]>)
.then((projects) => {
remember(query, projects);
setFound({ query, projects });
})
.catch(() => {}); // aborted: the query changed first
return () => controller.abort();
}, [query]);
// Read the cache during render so a hit shows on the same render, not one later.
return results.get(query) ?? (found?.query === query ? found.projects : null);
}
08 / Make the call
Ask what predicts the next request.
Reach for an LRU cache when recent use predicts the next use, memory is limited, and a miss can always fall back to the source. Links, tiles, rendered pages, parsed files, and query results usually fit.
Look elsewhere when the question changes. A small, fixed set of keys: a plain hash map with no eviction. Answers that go out of date on a schedule: a time limit, alone or beside the capacity. Popularity that stays put for a long time: least frequently used keeps the long-term favorites that a burst of new keys would push out of an LRU cache. Many threads hitting the cache at once: policies such as SIEVE avoid changing a shared list on every hit, which a strict LRU cache must do. And only the latest few items in arrival order, with no reordering on use: a ring buffer.
09 / Take the idea with you
Explain it without saying “LRU.”
“I keep a few answers in memory, in order of when they were last used. A lookup table finds an answer straight away, and using it moves it to the front of the line. When there is no room, the one at the back goes. When a real answer changes, I throw my copy away.” That describes the mechanism. The name is what you call it in a review.
Before moving on, explain three things without the name: why survey evicted hours and not wifi, why a hit writes six link fields no matter how big the cache is, and why the busiest link can stay stale the longest. Then find a cache in your own code and check what limits it: a count, a size, a time, or nothing at all.
Connections to follow nextRelated lessons
- Hash map is the half that finds an entry without searching.
- Linked list is the half that moves an entry you already hold, and ended by building a tile cache like this one.
- Ring buffer also forgets the oldest item, but by arrival, not by use.