9.7.30 — LRU Cache

"Design a cache that holds 10,000 entries. get and put must both be O(1). When it is full, throw out whatever was used least recently."

A product catalogue service keeps the last 10,000 product pages in memory so it does not have to ask the database for the same shoe five hundred times a minute. Each page is about two kilobytes, so the cache is twenty megabytes, which is fine. The ten-thousand-and-first product arrives and something has to go.

Which one? That is the entire problem, and the reason it is asked in interviews is not the policy. Everybody agrees the answer should be "whichever entry nobody has looked at for the longest". The reason it is asked is that no single data structure can answer it fast, and watching somebody discover that and compose two structures instead is a good use of forty minutes.

1. Why one structure is never enough

Two facts have to be available instantly on every operation.

Where is the entry for key K? A hash map does this in constant time and knows nothing about order. Ask a map which of its ten thousand entries was touched longest ago and it has to look at all of them.

Which entry was used least recently? A list in touch order does this instantly by looking at one end. Ask a list where key K is and it has to walk until it finds it, which is ten thousand steps.

So a map alone makes eviction linear, and a list alone makes lookup linear. Every attempt to fix one with a small addition fails in a way worth knowing:

Store a timestamp on each map entry. Lookup stays fast, and finding the oldest timestamp still means scanning every entry.

Keep a sorted structure of timestamps. Now eviction is fast and every get has to move an entry inside a sorted structure, which is logarithmic rather than constant, and the question asked for constant.

The answer is to keep both structures and have them point at the same objects. The map answers "where", the list answers "which is oldest", and because the map's values are the list's nodes, going from one to the other costs nothing.

Figure 1 — Two structures, one set of nodes. The map gives constant-time lookup and the list gives constant-time reordering. Neither can do the other's job, and neither has to, because they share the objects.

2. The implementation, line by line

class Node<K, V> {                                             // (1)
  prev: Node<K, V> | null = null;
  next: Node<K, V> | null = null;
  constructor(public key: K, public value: V) {}               // (2)
}

class LruCache<K, V> {
  #map = new Map<K, Node<K, V>>();
  #head: Node<K, V>;                                           // (3)
  #tail: Node<K, V>;

  constructor(private capacity: number) {
    this.#head = new Node<K, V>(null as K, null as V);         // (4)
    this.#tail = new Node<K, V>(null as K, null as V);
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }

  get(key: K): V | undefined {
    const node = this.#map.get(key);                           // (5)
    if (!node) return undefined;
    this.#unlink(node);                                        // (6)
    this.#linkAfterHead(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.#map.get(key);
    if (existing) {                                            // (7)
      existing.value = value;
      this.#unlink(existing);
      this.#linkAfterHead(existing);
      return;
    }

    if (this.#map.size >= this.capacity) {                     // (8)
      const victim = this.#tail.prev!;
      this.#unlink(victim);
      this.#map.delete(victim.key);                            // (9)
    }

    const node = new Node(key, value);
    this.#linkAfterHead(node);
    this.#map.set(key, node);
  }

  #unlink(n: Node<K, V>): void {                               // (10)
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
  }

  #linkAfterHead(n: Node<K, V>): void {                        // (11)
    n.prev = this.#head;
    n.next = this.#head.next;
    this.#head.next!.prev = n;
    this.#head.next = n;
  }
}

(1) The node holds both directions. That word doubly is not decoration, and (10) is where it earns itself.

(2) The node stores its key as well as its value, which looks redundant because the map already has the key. It is not, and (9) is why.

(3) and (4) Two permanent nodes that hold no data, one at each end. They never move and never get evicted. Their entire job is described at (11).

(5) A get starts at the map, which takes it straight to the node in constant time regardless of how many entries exist.

(6) Then the node is pulled out of wherever it was in the list and put back at the front. Reading an entry changes the list, which surprises people the first time they see it, and it is the whole mechanism: recency order is maintained by every read paying one constant-time reordering.

(7) Writing a key that already exists is not an insertion. The value is replaced and the node moves to the front, and crucially nothing is evicted, because the number of entries did not change. Treating an overwrite as an insertion evicts an entry for no reason and quietly shrinks the effective cache.

(8) Eviction happens before the insertion, not after, so the cache never briefly holds capacity + 1 entries. With large values that momentary overshoot is a real memory spike, and it is free to avoid.

(9) Here is why the node carries its key. The victim was found by walking the list (tail.prev is the least recently used node), but it also has to be removed from the map, and a map is keyed by key. Without the key on the node there is no way to get from "this is the node to evict" to "this is the map entry to delete" without scanning the map, which would make eviction linear and undo the entire design.

(10) Unlinking is two assignments: the node before it now points to the node after it, and vice versa. This is only possible in constant time because the node knows its predecessor. In a singly linked list, to unlink a node you must first find the node before it, and the only way to do that is to walk from the head, which is O(n). That is the whole argument for doubly linked, and it is the single most commonly asked follow-up on this problem.

(11) Linking after the head is four assignments and works identically whether the list is empty, has one entry, or has ten thousand. That is what the sentinels bought.

On the sentinels, because it is the detail interviewers notice. Without them, #unlink needs to check whether the node is the head (then the head pointer moves), whether it is the tail (then the tail pointer moves), and whether it was the only node (then both become null). #linkAfterHead needs to check whether the list is empty. That is four branches, and every one of them is a place a bug lives, because they are exactly the cases nobody exercises by hand. With two permanent nodes that can never be removed, every real node is always in the middle, so prev and next are never null and the branches do not exist. It is not a micro-optimisation; it is deleting the part of the code where the bugs are.

3. The shortcut that already exists, and why you build it anyway

JavaScript's Map remembers insertion order, and it exposes the oldest key cheaply. So an LRU cache is about eight lines:

class TinyLru<K, V> {
  #m = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.#m.has(key)) return undefined;
    const v = this.#m.get(key)!;
    this.#m.delete(key);                       // (1)
    this.#m.set(key, v);                       // moves it to the newest position
    return v;
  }

  put(key: K, value: V): void {
    this.#m.delete(key);                       // (2)
    this.#m.set(key, value);
    if (this.#m.size > this.capacity)
      this.#m.delete(this.#m.keys().next().value);   // (3) oldest key
  }
}

(1) Deleting and re-inserting moves a key to the end of the insertion order, which is exactly "touch it".

(2) The delete before the set matters for the same reason: setting an existing key does not move it in the order, so without the delete an entry that is read constantly still ages out.

(3) keys().next().value is the oldest key, in constant time.

This works, it is what you should ship in a Node service, and you should say so out loud. Then build the real one anyway, for three honest reasons rather than because the interview demands ceremony. Most languages have no ordered hash map, so this trick does not travel. The next section adds per-entry data (an expiry time, a size in bytes) that has to live on a node. And the follow-up question is almost always LFU, which needs the same node-and-list machinery arranged differently, so the version with nodes is the one you can extend when asked.

4. Expiry and eviction are two different things

An interviewer who adds "entries should expire after five minutes" is usually checking whether you know these are separate mechanisms with separate reasons.

Eviction is about space. The cache is full and something must go. It happens whether or not the data is still correct.

Expiry is about truth. The cached copy of a product page is five minutes old and the price may have changed. It happens whether or not the cache is full.

A cache needs both, and confusing them produces a cache that either serves stale prices forever or evicts things that were perfectly good.

type Entry<V> = { value: V; expiresAt: number };

get(key: K, now: number): V | undefined {
  const node = this.#map.get(key);
  if (!node) return undefined;

  if (node.value.expiresAt <= now) {           // (1)
    this.#unlink(node);
    this.#map.delete(node.key);
    return undefined;                          // (2)
  }

  this.#unlink(node);
  this.#linkAfterHead(node);
  return node.value.value;
}

(1) Expiry is checked at read time, and an expired entry is removed and reported as a miss.

(2) Returning undefined rather than the stale value means the caller reloads, which is what "expired" should mean.

Why not a timer per entry? Ten thousand entries means ten thousand timers, each one an object the runtime has to track and fire. On a cache with a lot of turnover, the runtime spends more effort managing timers than the cache saves, and in Node those timers all sit on the event loop, so a burst of expiries becomes latency for real requests. Checking at read time costs one comparison on an operation that was happening anyway. The full picture of what timers cost the event loop is in 3.8.1.

The one gap in lazy expiry, which you should name yourself: an entry that expires and is then never read again sits in the cache forever, holding memory and a slot. In a size-bounded cache that is usually acceptable, because it will eventually reach the tail and be evicted anyway. Where it is not acceptable, the fix is a slow background sweep that samples a few entries at a time rather than scanning everything, which is exactly what Redis does with its expired keys. Lazy expiry plus occasional sampling is the shipped answer; either alone has a hole.

5. The stampede, which is the failure this cache causes

A single product page is requested two hundred times a second. Its cache entry expires. Now two hundred requests miss at the same moment, and two hundred identical database queries launch within a few milliseconds of each other.

The cache did not fail. The cache caused it. This is often called the dogpile, and it is worse than having no cache at that instant, because with no cache the load would have been steady rather than arriving as a spike precisely when the entry was hottest.

class LoadingCache<K, V> {
  #cache: LruCache<K, Entry<V>>;
  #inFlight = new Map<K, Promise<V>>();                       // (1)

  async getOrLoad(key: K, load: () => Promise<V>, ttlMs: number): Promise<V> {
    const hit = this.#cache.get(key, Date.now());
    if (hit !== undefined) return hit;                        // (2)

    const pending = this.#inFlight.get(key);
    if (pending) return pending;                              // (3)

    const p = load()
      .then(v => {
        this.#cache.put(key, { value: v, expiresAt: Date.now() + ttlMs });
        return v;
      })
      .finally(() => { this.#inFlight.delete(key); });        // (4)

    this.#inFlight.set(key, p);                               // (5)
    return p;
  }
}

(1) A second map, holding the promise of a load that is currently running. It is not a cache of values; it is a record of work in progress.

(2) A fresh hit returns immediately and touches nothing else.

(3) A miss looks for a load already running for this key. If one is running, this caller returns the same promise rather than starting a second load. Two hundred concurrent misses become one database query and a hundred and ninety-nine callers awaiting the same result. Everybody gets the right answer at the same moment and the database sees one query.

(4) The finally is the line that must not be forgotten. If the load fails and the entry is not removed from the in-flight map, every future request for that key returns the same rejected promise forever, and the key is permanently broken with no way to recover except restarting the process. A failed load has to leave no trace, so the next caller tries again. This is the same "release it in finally, on every path" rule that governs locks and pooled connections in 9.5.2.

(5) The promise is registered before it is returned, so a caller arriving one microsecond later finds it.

This works in a single process and only in a single process, and saying so is the difference between an answer and a complete one. Eight processes on one machine means eight in-flight maps, so a hot key expiring produces eight loads rather than two hundred. That is usually a good enough improvement to accept. Where it is not, the deduplication has to move to the shared cache, and the mechanism there is a short-lived marker that one process wins the right to set, with the others waiting briefly and re-reading. That is 10.14.2's territory, and the shape is the same conditional claim as everywhere else in this part.

Two related moves worth naming because they cost almost nothing. Serving the stale value while refreshing in the background means nobody ever waits for a reload of a popular key, at the cost of a few seconds of staleness. And caching the absence of a value, with a short expiry, stops a stream of requests for a product that does not exist from hitting the database every single time, which is the shape of a cheap denial-of-service against any cache that only stores hits.

6. Counting entries is the wrong bound

"10,000 entries" is convenient and it is not what runs out. Memory does. A cache of 10,000 product pages averaging two kilobytes is twenty megabytes, and one product with three hundred reviews embedded might be four megabytes on its own. Sixty of those and the cache is a quarter of a gigabyte while its counter cheerfully reports 60 entries out of 10,000.

The repair is to bound by weight rather than count:

put(key: K, value: V, weight: number): void {
  // ... replace-existing path adjusts totalWeight by the difference
  while (this.#totalWeight + weight > this.maxWeight && this.#map.size > 0)  // (1)
    this.#evictTail();

  // ... insert, then this.#totalWeight += weight
}

(1) A while rather than an if, because one large entry may require evicting several small ones. This is the only structural change: everything else about the list and the map is identical.

The weight of an entry is an estimate, and it should be a cheap one. Serialised length is usually close enough, and computing an exact object size on every insertion costs more than the mistake it prevents. A rough bound that is actually enforced beats an exact bound that is too expensive to compute.

7. LFU, which is the follow-up

"What if I want to keep the entries used most often rather than most recently?" is asked because the naive answer to it is a sorted structure, which is logarithmic, and there is a constant-time arrangement.

Keep the same idea and add one level. Each entry knows how many times it has been used. All entries with the same use count live together in their own recency list. A separate map goes from a use count to that list, and one number remembers the smallest count currently present.

Reading an entry removes it from its current count's list and adds it to the front of the list for count + 1. If its old list is now empty and that count was the smallest, the smallest count goes up by one. All constant time.

Evicting takes the tail of the list for the smallest count, which is the least-used entry and, among those tied, the least recently used. Constant time.

The point of showing this is not the code; it is that the structure is the same trick applied twice. A map for lookup, lists for order, and one extra pointer to avoid a search. Recognising that is worth more than memorising the arrangement.

And LFU is not simply better, which is the part worth saying. The two policies fail in opposite ways, and knowing both failures is what lets you choose.

LRU is destroyed by a scan. A nightly job that reads every product once touches ten thousand keys that will never be read again, and each one evicts something genuinely hot. The cache wakes up empty. Real systems defend against this by only promoting an entry to the main cache on its second access, so single-touch scans pass through without displacing anything.

LFU is destroyed by yesterday's popularity. An item that was accessed fifty thousand times during a sale keeps a huge count forever and never leaves, while today's actually-popular item cannot accumulate enough uses to beat it. The defence is to decay counts over time, or to count uses only within a recent window, which turns LFU into something that has to forget.

8. Where you have already used this

Every one of these is the machinery above with different names, and recognising them is what turns configuration into understanding.

Redis's maxmemory-policy allkeys-lru is this policy, approximated. Redis does not maintain a full recency list, because the pointers would cost more memory than they save. It samples a handful of random keys and evicts the least recently used among them, which is nearly as good and dramatically cheaper. That trade is worth remembering: at large scale, an approximation of LRU usually beats exact LRU, because the bookkeeping is the expensive part.

Your operating system decides which memory page to swap out with the same question, and it uses an approximation too, because tracking exact recency for every page in a system would cost more than the paging it saves.

A processor's cache decides which line to discard on every miss, in hardware, in a couple of nanoseconds, which is why it uses a policy simple enough to build out of gates.

The pattern across all three is the same: exact LRU is the model everybody reasons with, and at scale everybody ships an approximation of it, because maintaining perfect order costs more than the imperfection does.

9. What the interviewer will push on

"Why do you need two structures?" They are checking whether you can state what each one cannot do. A map has no order, so eviction would scan; a list has no lookup, so get would walk. The tell is whether you also dismiss the near-misses: a timestamp on each map entry still needs a scan to find the minimum, and a sorted structure makes get logarithmic when the question said constant.

"Why doubly linked?" Because unlinking a node needs the node before it, and in a singly linked list the only way to find that is to walk from the head, which is linear. This is the single most common follow-up and it has a one-sentence answer, so an unclear one is very visible.

"What are the two dummy nodes for?" They remove four branches: node-is-head, node-is-tail, node-is-only, list-is-empty. Every real node is always in the middle, so prev and next are never null. Say it as deleting the code where the bugs live rather than as a tidiness preference.

"Why does the node store its key when the map already has it?" Because eviction finds the victim through the list and must delete it from the map, and the map is keyed by key. Without it, eviction has to scan the map, and the design's whole promise is gone. Candidates who cannot answer this usually wrote the code from memory.

"A popular key expires and two hundred requests miss at once." They want the stampede and its fix: a map of in-flight promises so the first miss loads and the rest await the same promise. Then the two follow-ups that separate a real answer. The cleanup must be in finally, or a failed load wedges the key permanently. And the deduplication is per process, so eight workers still produce eight loads.

"Ten thousand entries — is that the right bound?" Usually not. Entry sizes vary by orders of magnitude, so bound by weight and evict in a while loop, since one big entry may displace several small ones. The estimate should be cheap, because a rough bound that is enforced beats an exact one that is too slow to compute.

"Would LFU be better?" Neither is better; they fail oppositely. A nightly scan empties an LRU cache, and the defence is promoting on the second access. A sale gives an LFU entry a count it never loses, and the defence is decaying counts. Answering with the two failure modes rather than with a preference is what shows you have run one of these.

The thing to volunteer that nobody asks for: at real scale, nobody ships exact LRU. Redis samples a few random keys and evicts the least recently used among them, and operating systems approximate too, because maintaining perfect recency order costs more memory and time than the imperfection costs in hit rate. Knowing that the structure you just built is the model rather than the implementation used in production is the observation that signals you have configured one of these rather than only studied it.

Recall

• A map cannot order and a list cannot find. Keep both, and let the map's values be the list's nodes so crossing between them is free.
• Timestamps in the map still need a scan; a sorted structure makes get logarithmic. Neither near-miss meets the constant-time requirement.
• Head is most recent, tail is the victim. Every read moves its node to the head, so recency is maintained one constant-time move at a time.
• Doubly linked because unlinking needs the predecessor, and finding it in a singly linked list is a walk from the head.
• Two sentinel nodes delete four branches: is-head, is-tail, only-node, empty-list. Every real node is always in the middle.
• The node stores its key because eviction finds the victim through the list and must delete it from the map.
• Overwriting an existing key evicts nothing — the size did not change. Evict before inserting, so the cache never overshoots.
• JavaScript's Map keeps insertion order, so delete plus set is a working LRU in eight lines. Say it, then build the real one for per-entry data, other languages, and the LFU follow-up.
• Expiry is about truth; eviction is about space. Different reasons, both needed.
• Expire lazily at read time. A timer per entry costs more than the cache saves and puts a burst of expiries on the event loop. Add a sampling sweep for entries that are never read again.
• The stampede: a hot key expires and every concurrent miss loads it. Fix with a map of in-flight promises, cleaned up in finally or the key wedges forever on a failed load.
• In-flight deduplication is per process. Eight workers means eight loads, not one.
• Bound by weight, not entry count, and evict in a while loop because one large entry may displace several small ones.
• LFU is a map plus per-count lists plus a smallest-count pointer, still constant time.
• LRU dies to a scan; LFU dies to yesterday's popularity. Promote on second access; decay counts.
• Production approximates. Redis samples random keys rather than maintaining exact order, because the bookkeeping costs more than the imperfection.

Self-test: Why is a timestamp in the map not enough? Why doubly, why sentinels, why the key on the node? What happens on put of an existing key? Why is expiry lazy? What breaks if the in-flight cleanup is not in finally? Name each policy's failure mode.

Quiz Bank

FoundationalBuild an LRU cache with O(1) get and put, and justify every structural decision.

Two facts must be instant on every operation, and no single structure gives both.

Where is key K? A hash map, constant time, and it knows nothing about order. Which entry is least recently used? A list in touch order, constant time at one end, and finding a specific key means walking it.

The near-misses fail too, and dismissing them is part of the answer. A timestamp stored on each map entry keeps lookup fast and still requires scanning every entry to find the minimum. A sorted structure over timestamps makes eviction fast and makes every get a logarithmic reordering, when the requirement said constant.

So keep both, and make the map's values be the list's nodes. Crossing from one structure to the other then costs nothing.

get(key: K): V | undefined {
  const node = this.#map.get(key);
  if (!node) return undefined;
  this.#unlink(node);
  this.#linkAfterHead(node);
  return node.value;
}

The map takes you straight to the node, and the node is moved to the front of the list. A read modifies the list, and that is the mechanism: recency order stays correct because every access pays one constant-time reordering.

put(key: K, value: V): void {
  const existing = this.#map.get(key);
  if (existing) {
    existing.value = value;
    this.#unlink(existing); this.#linkAfterHead(existing);
    return;
  }
  if (this.#map.size >= this.capacity) {
    const victim = this.#tail.prev!;
    this.#unlink(victim);
    this.#map.delete(victim.key);
  }
  const node = new Node(key, value);
  this.#linkAfterHead(node);
  this.#map.set(key, node);
}

Overwriting an existing key is not an insertion. The count did not change, so nothing is evicted. Treating it as an insertion silently shrinks the usable cache by evicting an innocent entry on every update.

Eviction happens before insertion, so the cache never momentarily holds capacity + 1 entries. With multi-megabyte values that overshoot is a real memory spike and it costs nothing to avoid.

The three details that get asked about, each with its reason.

Doubly linked. Unlinking a node in constant time requires knowing the node before it, so its predecessor's next can be repointed. A singly linked list has to walk from the head to find that predecessor, which is O(n), and the whole design collapses.

Sentinels. Two permanent nodes at the ends, holding no data and never removed. Without them, #unlink must handle node-is-head, node-is-tail and node-is-the-only-node, and #linkAfterHead must handle the empty list. That is four branches covering exactly the cases nobody tests by hand. With sentinels, every real node is always in the middle, prev and next are never null, and the branches do not exist. This is deleting the part of the code where the bugs live, not a tidiness preference.

The key on the node. Eviction finds the victim through the list (tail.prev), and must also remove it from the map, which is keyed by key. Without the key on the node, that means scanning the map, which makes eviction linear and undoes everything.

Complexity: get and put are constant time, and space is proportional to capacity.

And the shortcut, stated honestly. JavaScript's Map preserves insertion order, so delete then set moves a key to the newest position and keys().next().value gives the oldest. That is a working LRU in eight lines and is what I would ship in a Node service. I build the node version anyway because most languages have no ordered hash map, because per-entry data like an expiry time needs somewhere to live, and because the LFU follow-up needs exactly this machinery rearranged.

AppliedAdd expiry and stampede protection. Name the production problem each one prevents and what breaks if you get it wrong.

First, separate the two things that are being conflated. Eviction is about space: the cache is full and something must go, regardless of whether the data is still correct. Expiry is about truth: this copy is five minutes old and the price may have changed, regardless of whether the cache is full. A cache needs both, and mixing them produces one that either serves stale prices forever or throws away perfectly good entries.

Expiry is checked at read time:

if (node.value.expiresAt <= now) {
  this.#unlink(node);
  this.#map.delete(node.key);
  return undefined;
}

Why not a timer per entry? Ten thousand entries means ten thousand timers the runtime must track and fire, and in Node they all sit on the event loop, so a burst of expiries becomes latency for real requests. The runtime ends up spending more managing timers than the cache saves. A comparison at read time rides along on an operation that was already happening.

The gap in lazy expiry, named before it is found: an entry that expires and is never read again occupies memory forever. In a size-bounded cache it will eventually reach the tail and be evicted anyway, so this is usually fine. Where it is not, a slow background sweep that samples a few entries at a time closes it, which is what Redis does. Lazy plus sampling is the complete answer; either alone has a hole.

Now the stampede, which is a problem the cache itself creates. A product page requested two hundred times a second has its entry expire. Two hundred requests miss simultaneously and fire two hundred identical database queries within a few milliseconds. The load spike arrives exactly when the key was hottest, which is worse than having had no cache at all in that instant.

async getOrLoad(key: K, load: () => Promise<V>, ttlMs: number): Promise<V> {
  const hit = this.#cache.get(key, Date.now());
  if (hit !== undefined) return hit;

  const pending = this.#inFlight.get(key);
  if (pending) return pending;

  const p = load()
    .then(v => { this.#cache.put(key, { value: v, expiresAt: Date.now() + ttlMs }); return v; })
    .finally(() => { this.#inFlight.delete(key); });

  this.#inFlight.set(key, p);
  return p;
}

The second map holds work in progress, not values. The first miss starts the load and registers its promise. Every miss arriving while that load runs gets the same promise back, so two hundred concurrent misses become one query and a hundred and ninety-nine callers awaiting one result. They all receive it at the same moment.

The finally is the line that must not be missed, and here is exactly what breaks without it. If the load rejects and the in-flight entry is left behind, every future request for that key gets handed the same rejected promise, forever. The key is permanently broken and the only recovery is restarting the process. A failed load must leave no trace so the next caller can try again. This is the same rule that governs releasing a lock or returning a pooled connection in 9.5.2: release on every path, including the ones you did not plan for.

The promise is registered before it is returned, so a caller arriving a microsecond later finds it rather than starting a second load.

And the honest limit: this deduplicates within one process only. Eight worker processes have eight in-flight maps, so a hot key expiring produces eight loads rather than two hundred. That is usually a good enough improvement to accept and move on. Where it is not, the deduplication moves to the shared cache, where one process wins the right to set a short-lived marker and the others wait briefly and re-read. The mechanism there is the same conditional claim used everywhere else in this part, and the design is in 10.14.2.

Two cheap additions worth naming. Serving the stale value while refreshing in the background means nobody ever waits for a popular key to reload, at the cost of a few seconds of staleness. And caching the fact that something does not exist, with a short expiry, stops repeated requests for a missing product from reaching the database every time, which is otherwise a very cheap way for someone to bypass your cache entirely.

InterviewYour cache holds 10,000 entries and the process still runs out of memory. What went wrong and how do you fix it?

The bound counted the wrong thing. Entry count is convenient and memory is what actually runs out, and the two are only related if entries are roughly the same size, which they never are.

Concretely: a product page averages two kilobytes, so 10,000 entries is twenty megabytes, which is what was budgeted. One product with three hundred reviews embedded in its payload is four megabytes on its own. Sixty of those in the cache is a quarter of a gigabyte, and the counter reports 60 out of 10,000, well under capacity, with nothing to alert on. The cache is not misbehaving. It is enforcing a limit that has no relationship to the resource being exhausted.

The fix is to bound by weight:

while (this.#totalWeight + weight > this.maxWeight && this.#map.size > 0)
  this.#evictTail();

A while, not an if, because one four-megabyte entry may need to displace two thousand small ones to fit. An if evicts one entry and inserts anyway, which means the bound is exceeded on exactly the insertions where it mattered.

Everything else is unchanged. The list, the map, the sentinels and the recency ordering are all identical, and the running total is adjusted on insert, evict, and on the replace path, where it moves by the difference between the old and new weights rather than by the new weight.

How the weight is measured, and why the estimate should be rough. Serialised length is close enough for almost everything. Computing a precise in-memory size means walking every object graph on every insertion, which costs more time than the memory it saves, and the number is still approximate because of how runtimes lay out objects. A rough bound that is actually enforced is worth far more than an exact bound too expensive to compute, and being able to say that rather than reaching for precision is the point of the question.

Two related causes worth checking before blaming the bound, because in real incidents it is often one of these.

The values are being mutated after insertion. A cached object that a caller holds a reference to and appends to grows without the cache knowing, so the recorded weight becomes fiction. The defence is storing something the caller cannot grow, which usually means storing a serialised copy or freezing it.

Something else is keyed by the same thing and unbounded. A cache with a proper bound sitting next to a map of pending loads, or a map of metrics per key, that nobody bounded. The in-flight map in the previous answer is exactly this shape, and it is safe only because entries are removed in finally. A version that forgot the cleanup is both a wedged key and a memory leak.

And the general rule the question is really about: every unbounded collection keyed by something a user controls is a memory leak waiting for enough traffic. The cache had a bound and it was the wrong quantity, which is the same failure wearing a more respectable outfit.

StaffTake this cache to a service with eight worker processes and a shared cache tier. What survives, what changes, and what do you refuse to do?

What survives is the structure and the reasoning. The map-plus-list arrangement, the recency ordering, weight-based bounds, lazy expiry and in-flight deduplication are all still exactly right inside each process. What changes is that there are now nine caches (eight local ones and one shared) and the interesting design work is in what each is for.

The local cache in each worker is for latency, and it should be small and short-lived. A lookup in it costs nanoseconds; a lookup in the shared tier costs a network round trip of perhaps half a millisecond. For a value read hundreds of times a second, keeping it locally for a few seconds removes almost all of those round trips.

Its cost is staleness multiplied by eight. When a product price changes, there are eight independent copies that will each expire on their own schedule, so for a few seconds different users see different prices depending on which worker served them. That is the trade to state explicitly: local caching buys latency and pays in inconsistency across workers, and the price is bounded by the local expiry time. Keeping local entries to a few seconds keeps the inconsistency to a few seconds.

The shared tier is for load, protecting the database from every worker independently reloading the same data. It holds more, holds it longer, and is the layer that actually determines hit rate.

Invalidation is where this gets genuinely hard and where I would be careful. Deleting a key from the shared tier does nothing to the eight local copies. There are three honest options and I would pick the first.

Keep local expiry short and accept the window. Simple, no machinery, and the staleness has a stated ceiling. For prices and product descriptions this is almost always right.

Broadcast invalidations to the workers. Correct much faster, and it adds a message path that can fail silently, which produces a worker serving stale data with nothing indicating it. If it is built, it needs the local expiry as a backstop anyway, so it is an optimisation on top of the first option rather than a replacement for it.

Do not cache locally at all. Correct and gives up the latency win. Right for anything where a few seconds of staleness is genuinely unacceptable, which is much rarer than people claim.

In-flight deduplication needs saying again because it changes shape. Locally it turns two hundred misses into one load per worker, so eight workers produce eight loads. Across the fleet, the mechanism has to move to the shared tier: one process wins the right to set a short-lived marker and does the load, and the others wait a moment and re-read. That is the same conditional claim as everywhere else in this part, and it is worth noting that the marker needs its own expiry, because a process that dies mid-load must not lock a key out permanently.

What I would refuse: building an exact distributed LRU. Maintaining a single global recency order across nine caches means every read anywhere updates shared state, which turns every cache hit into a network write. That is slower than not caching. The shared tier should use whatever approximate policy it already has, and this is where the observation from section 8 pays off: Redis samples a handful of random keys and evicts the least recently used among them precisely because maintaining exact order costs more than the imperfection. Reaching for exactness here would be rebuilding, badly, something that was deliberately approximated for good reasons.

What I would measure. Hit rate at each layer separately, because a local layer with a 3% hit rate is pure overhead and should be removed. Load rate at the origin, because that is what the cache exists to reduce and it is the only number that proves it works. In-flight deduplication saves, since a sudden drop means something changed the expiry pattern. And the age distribution of served entries, because that is what turns "how stale can this be" from an argument into a number.

Flashcards

FlashWhy two structures

A map has no order, so eviction would scan; a list has no lookup, so get would walk. Keep both, and let the map's values be the list's nodes. Timestamps in the map still need a scan; a sorted structure makes get logarithmic.

FlashDoubly, sentinels, key-on-node

Doubly, because unlinking needs the predecessor and finding it in a singly linked list is a walk. Sentinels, because they delete the is-head, is-tail, only-node and empty-list branches. The key on the node, because eviction finds the victim in the list and must delete it from the map.

FlashExpiry versus eviction

Expiry is about truth (the copy may be wrong now); eviction is about space (something must go). Both are needed. Expire lazily at read time and add a sampling sweep, because a timer per entry costs more than the cache saves.

FlashThe stampede

A hot key expires and every concurrent miss loads it. A map of in-flight promises turns N misses into one load. Clean it in finally, or a failed load wedges the key forever. It deduplicates per process only.

FlashBound by weight

Entry count is not what runs out. Bound by bytes, evict in a while loop because one big entry may displace many small ones, and use a cheap estimate — an enforced rough bound beats an exact one that is too slow.

FlashLRU versus LFU

LRU is emptied by a scan that touches every key once; defend by promoting on the second access. LFU keeps yesterday's champion forever; defend by decaying counts. Production approximates both, because exact order costs more than the imperfection.

Next: 9.7.6 — the load balancer, where the thing being handed out is a request and the hard part is noticing that a server has stopped deserving them.