DSA & System Design
BackendMedium35 min

Design an LRU Cache (LLD)

A hash map plus a doubly linked list gives O(1) get and put. The design questions are the swappable eviction policy and why even a read needs the lock.

Related:Design a Parking Lot (LLD)Caching Explain it back
Say it in 30 seconds
  • O(1)get and put, with a map and a list
  • 1 lockguards reads too, since a hit reorders
  • N stripesindependent caches to cut lock contention
Show what to say

“I'd use a hash map for O(1) lookup and a doubly linked list for the order of use, so get and put are both O(1). The eviction order sits behind a small policy interface only if LFU or FIFO is likely. One lock guards everything, because a hit reorders the list, so a read is also a write.”

Trade-offs

  • Policy interface vs inline LRU: swappable rules, at the cost of one more layer when only LRU is asked for.
  • One lock vs striping: exact LRU and simple code, against contention that grows with the number of cores.
  • Lazy expiry vs a sweeper: no extra thread, but dead entries hold memory until someone reads them.

Bring it up before they ask

A put of a key that already exists must replace and refresh it without evicting, or a full cache throws away a good entry for nothing.

0 of 0 sections ticked
30-second answer

A hash map finds an entry in O(1), and a doubly linked list remembers the order of use in O(1), so get and put both cost O(1). Put the order behind an policy only if a second rule is likely, and guard everything with one lock, because even a read changes the order.

Functional

  • get(key) and put(key, value) with a fixed capacity
  • When full, a new key evicts the least recently used one
  • Reading or replacing a key makes it the most recent
  • Optional time to live (TTL) per entry or per cache
  • delete(key) and a size
  • Listeners hear every removal and its reason
  • Hit, miss and eviction counters

Non-functional

  • get and put in O(1)
  • Safe when many threads call it at once
  • Never above capacity, even for a moment
  • Policy can change without editing the cache
  • Deterministic tests: the clock is injected

Out of scope

  • A distributed cache (an HLD follow-up)
  • Persistence to disk
  • Loading values on a miss (a follow-up)

A low-level design (LLD) question that is mostly a data-structure question. Get the structure right, then show how the design bends.

New to this? Read Swap behaviour first, and see the hash-map-plus-list trick in the LRU Cache problem.

Clarifying questions and interface

Read more · 266 words
  • Is it generic over keys and values, and how big is the capacity?
  • Only , or must the rule be swappable (LFU, FIFO)?
  • Do entries expire? Is the per or per entry?
  • Many threads, or one? Are reads far more common than writes?
  • Does a miss load from somewhere, or does the caller handle it?
CallReturnsNotes
get(key)Value, or a missA hit makes the key the newest
put(key, value, ttl?)NothingA new key on a full cache evicts first
delete(key)true if it existedAlso frees the slot
sizeCount of live entriesNever above capacity
onRemove(listener)Called with key, value and why: evicted, expired or deleted

What it remembers

  • entries: key → value and deadline.
  • The policy's own order. For LRU, a doubly linked list with a node per key, plus a map from key to node.
  • stats: hits, misses, .

Two structures describe the same keys. Every operation must update both, or a key is evicted twice or never.

Build the design in stages

Step through: a map with a limit, then the order as a policy, then other policies, then time and the lock, then observers.

Read more · 150 words

Green marks what the latest stage added.

Patterns, and when to skip them. Strategy is the one worth drawing: the asks policy.victim() and never knows if the answer came from a list or a counter. Observer gives metrics and a place to hook in. Skip both if the interviewer said "just ".

Skip the rest. A CacheFactory, a CacheBuilder for three options, or a singleton cache add nothing here. Take the capacity in the constructor.

Stage 1 of 5

A map with a limit

A cache is a map that refuses to grow past its capacity. Each entry carries its value and, later, a deadline.

LRU cache class diagramCache owns the entries and guards them with one lock. It never decides who to evict: it asks an EvictionPolicy, which keeps its own order (LruPolicy with a doubly linked list, FifoPolicy, or LfuPolicy). Time arrives through a Clock, and listeners hear every removal.Cachecapacity: intentries: Map<key, Entry>ttl: msget(key)put(key, value, ttl?)delete(key)onRemove(listener)EntryvalueexpiresAt0..capacity

Cache owns the entries and guards them with one lock. It never decides who to evict: it asks an EvictionPolicy, which keeps its own order (LruPolicy with a doubly linked list, FifoPolicy, or LfuPolicy). Time arrives through a Clock, and listeners hear every removal.

  • ◆ composition (owns)
  • ◇ aggregation
  • △ inheritance / implements (dashed)
  • → association · ⇢ dependency

Watch it run: get and put

Press keys and watch the oldest fall off the back.

Read more · 47 words

Read an old key just before the fills, and it survives.

Pick a branch on the diagram: hit, expired and miss for get.

Interactive

LRU cache

Every access moves a key to the front. When the cache is full, the key at the back (least recently used) is evicted.

← most recentevicted next →
Hits
0
Misses
0
Hit ratio
– (of 0 gets)
Evictions
0

Empty cache. Press a key to get it (a miss loads it), or switch to set. Order, most → least recent: empty.

Press Play to watch it run · 5 steps

A get takes the lock, looks the key up, and checks its deadline. A live entry is moved to the front of the order before the value is returned. An expired entry is removed on the spot, and a missing key only counts as a miss.

get(key) from the caller to the policyA get takes the lock, looks the key up, and checks its deadline. A live entry is moved to the front of the order before the value is returned. An expired entry is removed on the spot, and a missing key only counts as a miss.get('a')lock taken: even a read changes the orderlookup('a')alt [hit]value, expiresAt 5000now 4200 is before 5000: still aliveonAccess('a'): move to frontvalue
  • Client
  • Service
  • Database
  • Worker
Text description
  1. Caller → Cache: get('a')
  2. Cache → Entries map: lookup('a')
  3. Entries map replies to Cache: value, expiresAt 5000
  4. Cache → LruPolicy: onAccess('a'): move to front
  5. Cache replies to Caller: value

Thread safety

A map plus a list is not safe under two threads.

Read more · 181 words

Two writers can corrupt the list. And a reader is a writer too: a hit relinks the node.

  • One lock around get and put is the right first answer. It is correct and cheap while the work inside is a few pointer moves.
  • Lock striping: hash the key to one of N small , each with its own lock. Reads on different stripes never wait. The cost is that becomes approximate across stripes.
  • Read buffering: record hits in a queue and replay them in batches, as high-end caches do. Fast, but harder to reason about.
  • Listeners run after the lock is released, or a slow one blocks every caller and a re-entrant one .

Step-by-step answer

Five moves: clarify (policy, , threads, loading on a miss), pick the structure (a map for lookup, a list for order), write get and put (hit, replace, , insert), split out the policy (only if a second rule is likely), then add safety and time (one lock, an injected clock).

Read more · 197 words

For put, pick a branch: new key on a full , new key with room, and a known key.

  1. Why not just a map, or just a list?

    A map alone cannot say which key is oldest. A list alone makes lookup O(n). Together each fixes the other.

  2. Sentinels remove the edge cases

    A dummy head and tail mean every real node has a neighbour on both sides, so unlink and push-front never test for null.

  3. Put evicts before it inserts

    Evict first, so the cache is never over capacity, and only for a new key.

    put(key, value) {
  if (this.entries.has(key)) { /* replace, then onAccess */ return; }
  if (this.entries.size >= this.capacity) this.#remove(this.policy.victim(), 'evicted');
  this.entries.set(key, { value });
  this.policy.onInsert(key);
}

  4. Time is injected

    Expiry checks now() on read (lazy). Tests move a fake clock instead of sleeping. A background sweep can come later.

  5. Tests

    A model check against a simple ordered map over thousands of random operations catches list bugs that hand-picked cases miss.

Press Play to watch it run · 8 steps

A put of a known key only replaces the value and refreshes the order. A put of a new key on a full cache first asks the policy for a victim, removes it, and tells the listeners, then inserts the new entry as the most recent.

put(key, value) when the cache is fullA put of a known key only replaces the value and refreshes the order. A put of a new key on a full cache first asks the policy for a victim, removes it, and tells the listeners, then inserts the new entry as the most recent.put('d', 4)lock taken, capacity 3, entries a, b, calt [new key, full]victim()'b' (the back of the list)remove('b')onRemove('b')set('d', 4)onInsert('d'): to the frontlock releasedremoved('b', 2, evicted)
  • Client
  • Service
  • Worker
  • Database
  • Pub/Sub
Text description
  1. Caller → Cache: put('d', 4)
  2. Cache → LruPolicy: victim()
  3. LruPolicy replies to Cache: 'b' (the back of the list)
  4. Cache → Entries map: remove('b')
  5. Cache → LruPolicy: onRemove('b')
  6. Cache → Entries map: set('d', 4)
  7. Cache → LruPolicy: onInsert('d'): to the front
  8. Cache sends (async) to Listener: removed('b', 2, evicted)

Implementation and code it yourself

The same design in JavaScript, Java or Python. Java and Python add a real lock and run listeners after releasing it.

Read more · 99 words
  • victim() reads the back of the list. It does not remove it, so the stays in charge of removal.
  • A hit never extends a ; only put sets a deadline.

Try the Eviction Cache exercise: one class, three policies chosen by name, and ties that the tests check.

// Strategy: the cache owns the data, the policy owns the order. A policy answers one question: who goes next?
class Node {
  constructor(key) { this.key = key; this.prev = null; this.next = null; }
}

export class LruPolicy {
  constructor() {
    this.nodes = new Map();                       // key -> node, so any key is found in O(1)
    this.head = new Node(null);                   // sentinels: the ends need no null checks
    this.tail = new Node(null);
    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.next = this.head.next; n.prev = this.head;
    this.head.next.prev = n; this.head.next = n;
  }

  onInsert(key) { const n = new Node(key); this.nodes.set(key, n); this.#pushFront(n); }
  onAccess(key) { const n = this.nodes.get(key); this.#unlink(n); this.#pushFront(n); }  // newest to the front
  onRemove(key) { this.#unlink(this.nodes.get(key)); this.nodes.delete(key); }
  victim() { return this.tail.prev === this.head ? undefined : this.tail.prev.key; }      // the back is the oldest
}

export class FifoPolicy {
  constructor() { this.order = new Set(); }       // a Set remembers insertion order
  onInsert(key) { this.order.add(key); }
  onAccess() {}                                   // reads do not change who is next
  onRemove(key) { this.order.delete(key); }
  victim() { return this.order.values().next().value; }
}

Failure modes and trade-offs

Read more · 178 words
What breaksEffectMitigation
Map and list disagreeA key evicted twice, or neverUpdate both in one method, test against a model
Evict-then-check on updateA good entry thrown awayCheck for the key first
Slow listener under the lockEvery caller stallsNotify after unlocking
Expired entries fill the cacheLive keys get evictedSweep, or prefer expired victims
One hot keyAll threads queue on one lockStripe the cache, or shield it with a tiny front cache

Trade-offs

ChoiceProsCons
Hand-built list vs built-in ordered mapShows the structure; any languageMore code to get wrong
One lock vs stripingExact LRU, simpleContention under many cores
Lazy expiry vs sweeperNo extra threadDead entries use memory until read
Policy interface vs inline LRUSwappableAn extra layer for one rule

Follow-up questions

How would you add LFU?

A new LfuPolicy with the same four methods. Keep a count per key and buckets of keys per count. Break ties by recency. The does not change.

How do you load a value on a miss without a stampede?

Add getOrLoad(key, loader) that remembers one in-flight load per key, so ten callers share one load. Never run the loader while holding the cache lock.

How would you make reads scale across cores?

Stripe the keys over N caches, or buffer hits and apply them in batches. Say that you trade exact order for .

How would this become a distributed cache?

with , so each node holds its own LRU. That is the HLD version of the same idea.

How do you size it by bytes instead of entries?

Give each entry a weight, track the total, and until the new entry fits. The loop is the only change.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. Why does a thread-safe LRU cache need an exclusive lock even for get()?

Patterns behind this

The coding patterns this design is built on. Practise them and the design questions get easier.