Hot Key and Stampede Effect

Every measurement in the previous lessons ran in a single sequence: one request takes a miss, goes to the origin, stores the entry, and the next request gets a hit. This sequence assumes requests wait for one another. A real server does not.

The library system’s most-read key is the Central branch’s stock count. When that entry drops, every request arriving in the time between the drop and the new entry being stored takes a miss, and every single one of them goes to the origin. This behavior is called a cache stampede, and its result is this: the origin sees its highest load, on the key it is protected the most, at exactly the moment the cache goes empty. This lesson measures the behavior and compares three countermeasures.

A Hundred Requests Arriving at Once

In the measurement setup, origin access is an asynchronous call: the query and the round trip together take 30 milliseconds. What gets counted is not the duration but the number of calls reaching the origin.

// stampede.mjs — the moment a hot key's entry drops, 100 requests arrive at once
import { setTimeout as wait } from "node:timers/promises";

const DELAY = 30;                                  // origin access: query + round trip
const counter = { origin: 0 };
async function produceFromOrigin(key) {            // branch stock count: an expensive aggregate query
  counter.origin += 1;
  await wait(DELAY);
  return { key, on_shelf: 137 };
}

const KEY = "library:s1:g1:tbranch-1:stock";
const REQUESTS = 100;

async function run(name, setup) {
  counter.origin = 0;
  const m = { pending: 0, stale: 0 };
  const read = setup(m);
  const t = performance.now();
  await Promise.all(Array.from({ length: REQUESTS }, () => read(KEY)));
  const duration = performance.now() - t;
  return `${name.padEnd(28)}${String(counter.origin).padStart(15)}${String(m.pending).padStart(20)}` +
    `${String(m.stale).padStart(18)}${(String(Math.round(duration / 10) * 10) + " ms").padStart(12)}`;
}

// 1) Plain cache-aside: no entry exists, everyone goes to the origin.
const plain = (m) => {
  const box = new Map();
  return async (a) => {
    if (box.has(a)) return box.get(a);
    m.pending += 1;
    const d = await produceFromOrigin(a);
    box.set(a, d);
    return d;
  };
};

// 2) Single-flight: one production for the same key; the rest wait on the same promise.
const singleFlight = (m) => {
  const box = new Map();
  const flight = new Map();
  return async (a) => {
    if (box.has(a)) return box.get(a);
    m.pending += 1;
    if (!flight.has(a)) {
      flight.set(a, produceFromOrigin(a).then((d) => { box.set(a, d); flight.delete(a); return d; }));
    }
    return flight.get(a);
  };
};

// 3) Stale-while-revalidate: an expired entry is returned immediately, the refresh starts in the background.
const staleWhileRevalidate = (m) => {
  const box = new Map([[KEY, { value: { key: KEY, on_shelf: 131 }, fresh: false }]]);
  const flight = new Map();
  return async (a) => {
    const entry = box.get(a);
    if (entry && !entry.fresh && !flight.has(a)) {     // start the refresh, do not wait
      flight.set(a, produceFromOrigin(a).then((d) => { box.set(a, { value: d, fresh: true }); flight.delete(a); }));
    }
    if (entry) { if (!entry.fresh) m.stale += 1; return entry.value; }
    m.pending += 1;
    return produceFromOrigin(a);
  };
};

console.log(["strategy", "origin calls", "pending requests", "stale responses", "duration~"]
  .map((h, i) => (i === 0 ? h.padEnd(28) : h.padStart([0, 15, 20, 18, 12][i]))).join(""));
console.log(await run("plain", plain));
console.log(await run("single-flight", singleFlight));
console.log(await run("stale-while-revalidate", staleWhileRevalidate));

strategy                       origin calls    pending requests   stale responses   duration~
plain                                   100                 100                 0       30 ms
single-flight                             1                 100                 0       30 ms
stale-while-revalidate                    1                   0               100        0 ms

The duration column is rounded to ten milliseconds and is machine-dependent; the first three columns are not.

In the plain setup, a hundred requests produced a hundred origin calls. The code is not wrong: every request checked the cache, did not find the entry, and went to the origin. The flaw lies in the gap between the miss and the entry being stored. This gap lasts as long as the origin access, and every request arriving during that time restarts the same work. The size of the load is set by how fast requests arrive: on an endpoint receiving a thousand requests per second, a 30-millisecond gap means thirty concurrent queries.

The single-flight lock brought the origin calls down to one. The setup is simple: before production starts, the key is written to a flight table, and later requests wait on the same promise. All hundred requests still waited — after all, the data was not there yet — but the origin saw a single query. This is the direct fix for the stampede effect.

Stale-while-revalidate trades differently. An expired entry is not deleted; when a request arrives, the old value is returned immediately and the refresh starts in the background. The pending-request count dropped to zero, and in exchange, a hundred responses carried stale data. The same pattern introduced client-side in the Caching Strategies lesson of the Frontend Quality course makes the same trade on the server side: staleness instead of waiting.

The choice between the three rows depends on the data. A branch’s stock count can be a few seconds out of date; there, stale-while-revalidate is the best choice. The eligibility check performed during a loan cannot work with stale data; there, single-flight is used.

The scope of the flight table is also a separate decision. An in-process table only protects that one instance; if four application instances are running, four calls reach the origin instead of one. To bring the origin down to strictly one call, the lock must be kept in a shared store; this raises correctness while adding one network round trip to every miss.

Expirations Landing on the Same Moment

The second form of the stampede effect does not show up in a single key, but in a set of keys loaded at the same time. When an application instance restarts, or a generation counter is incremented, hundreds of keys enter the cache in the same step. If they are all given the same lifetime, they all drop in the same step.

// hot-key.mjs — simultaneous expiry, and a hot key piling onto a single node
import { createHash } from "node:crypto";

const digest = (m) => parseInt(createHash("sha256").update(m).digest("hex").slice(0, 8), 16);

console.log("--- 200 keys loaded at the same step, lifetime=100");
for (const [name, lifetime] of [["fixed lifetime", () => 100], ["jittered lifetime", (a) => 100 + (digest(a) % 40)]]) {
  const perStep = new Map();
  for (let i = 1; i <= 200; i++) {
    const key = `library:s1:g1:tbranch-1:book:${i}`;
    const step = lifetime(key);
    perStep.set(step, (perStep.get(step) ?? 0) + 1);
  }
  const highest = Math.max(...perStep.values());
  console.log(`${name.padEnd(18)} expiry steps=${perStep.size}  highest miss in a single step=${highest}`);
}

console.log("--- 4-shard shared cache, 60% of requests on a single key");
const HOT = "library:s1:g1:tbranch-1:stock";
const requests = Array.from({ length: 1000 }, (_, i) =>
  i % 10 < 6 ? HOT : `library:s1:g1:tbranch-${(i % 3) + 2}:book:${i % 40}`);

function distribution(transform) {
  const shard = [0, 0, 0, 0];
  for (const [i, a] of requests.entries()) shard[digest(transform(a, i)) % 4] += 1;
  return shard;
}
const print = (name, b) => console.log(`${name.padEnd(22)}${b.map((n) => String(n).padStart(8)).join("")}` +
  `   busiest shard=%${((Math.max(...b) / 1000) * 100).toFixed(0)}`);

print("single key", distribution((a) => a));
print("split into 4 copies", distribution((a, i) => (a === HOT ? `${a}.${i % 4}` : a)));
print("split into 8 copies", distribution((a, i) => (a === HOT ? `${a}.${i % 8}` : a)));

--- 200 keys loaded at the same step, lifetime=100
fixed lifetime     expiry steps=1  highest miss in a single step=200
jittered lifetime  expiry steps=40  highest miss in a single step=9
--- 4-shard shared cache, 60% of requests on a single key
single key                 102     684     108     106   busiest shard=%68
split into 4 copies        102     234     408     256   busiest shard=%41
split into 8 copies        102     309     333     256   busiest shard=%33

With a fixed lifetime, all two hundred keys dropped in a single step. Once a small deviation derived from the key was added to the lifetime, expirations spread across forty steps, and the highest miss count in any single step fell to 9. It matters that the deviation is derived from the key: if a random number were used instead, the same key would drop at a different time on different instances, and the behavior would become unreproducible.

The Hot Key Itself

The second half of the output measures a separate problem. When a shared cache is split across multiple nodes, a key lands on a shard according to its digest. If 60% of requests target a single key, that key’s shard sees 68% of requests; the remaining three shards sit idle. Increasing the number of shards does not fix this distribution, because the problem is not too few keys — it is the weight of a single key.

The fix is to replicate the key: the hot key is split into a fixed number of copies, and a request is routed to one of them. With four copies, the busiest shard fell from 68% to 41%; with eight, to 33%. The distribution is not even — the digest function does not spread the copies evenly across shards — but the pile-up is broken.

Replication costs two things. The same value is stored multiple times, and invalidation must now evict not a single key but every copy. Second, because the number of copies is fixed, the generation counter from the previous lesson does its job here too: when the generation is incremented, every copy becomes unreachable in a single move.

The third and cheapest countermeasure for a hot key is keeping a short-lived local copy inside the application instance. This is the server link of the layer chain measured in the first lesson: a local entry lasting a few seconds, sitting in front of the shared cache, cuts off most of the network round trips going to the hot key.

Summary

• When a hot key’s entry drops, every request arriving in the gap between the miss and the entry being stored goes to the origin: a hundred concurrent requests produced a hundred origin calls.
• A single-flight lock brings production for the same key down to one; a hundred requests still waited, but the origin saw a single query. If the lock lives in-process, the protection weakens by the number of instances.
• Stale-while-revalidate brings the pending-request count to zero and returns stale responses in exchange; the choice depends on the data’s tolerance for staleness.
• Two hundred keys loaded at the same time dropped in a single step with a fixed lifetime; once a deviation derived from the key was added to the lifetime, the highest miss count in a single step fell from 200 to 9.
• In a shared cache split into shards, a single hot key loaded one shard with 68% of requests; once the key was split into eight copies, the busiest shard fell to 33%.

Next Step

Up to this lesson, every cache was set up inside the application, and every decision was made in code. Once the response is sent to the client, the caching decision is no longer in the code’s hands: the browser, the shared caches in between, and the edge layer look only at what is written in the response’s headers. This is the only way to talk to the layer called “uncontrollable” in the first lesson, and it has its own vocabulary — which response can be stored, how fresh it counts as, how to tell whether a stored copy is still valid without asking the origin. The next lesson builds this vocabulary against an HTTP server with real requests.