Multi-Level Caches and Hot Keys

Stagefront is an event ticketing service that exists only in this course, where a stadium show goes on sale at exactly 10:00 and two hundred thousand people press the same button in the same minute. On Thursday 17 September 2026 a forty thousand seat show went on sale and, by every measure the business cares about, the sale worked. The seats went in eighty seconds, which is lesson 017's figure and the number the company is built on. Nothing paged. No error rate moved.

The complaints arrived anyway, and they were all one complaint wearing different clothes: the seat map took half a second to appear, and the seat I clicked was already taken.

An engineer spent most of the following week looking in the wrong place. The twenty checkout boxes lesson 006 counted sat at the 75% CPU that lesson measured for the on-sale minute, which is what an on-sale looks like rather than what a bug looks like. Postgres was quiet, because lesson 008 established that the seat map is cached with a ten second TTL and the database builds it six times a minute rather than two hundred thousand. The cache node holding that map looked fine too, on every graph there was: its operations a second peaked at a few thousand against a ceiling in the hundreds of thousands, and its CPU never left the low twenties.

On the Thursday after, somebody did one multiplication instead of reading a dashboard.

Two hundred thousand people inside a minute is 3,333 requests a second, which lesson 017 measured. Every one of them loads the seat map. The map is forty thousand seats, and even at a stingy twenty five bytes a seat, a status and a price band in a compact array with the seat labels implied by position, that is a megabyte. The honest JSON a browser actually wants is two or three times bigger. Take the megabyte, because the answer survives the stingy version.

    3,333 requests/sec  x  1 MB  =  3,333 MB/sec
                                 =  26.7 gigabits/sec
    the node's network card       =  10 gigabits/sec

Nearly three times the wire, offered to one network card, by one key. Nothing upstream was shaping those arrivals either: lesson 021 confirmed Stagefront has built neither a limiter nor a waiting room, so all 3,333 reach the boxes and every box reads the map.

That is also where the half second came from, and the card is only half of it. Ten gigabits at a megabyte a response serves about 1,250 a second while 3,333 arrive, so the card sets throughput. Lesson 002's busy room sets the wait, and here you run it backwards: concurrency over throughput, so half a second against 1,250 a second means about six hundred requests were in flight waiting on that one card. The fleet's workers are the only reason it stopped at six hundred. Everybody past them is refused by a box with no free worker.

There was no graph of any of it. Commands a second, CPU, memory: the three graphs every cache ships with, and not one of them in the unit the failure was in.

The bill is in bytes, and the unit is why you cannot see it

A hot key is a single key whose read rate alone is enough to overload the one node that holds it. It is a different failure from lesson 008's stampede, and the two get confused constantly. A stampede is many requests all missing at once and all going to the origin; it is about the origin, it happens when the entry is absent, and lesson 046's single flight, one rebuild shared by everybody waiting on it, fixes it. A hot key is many requests all hitting, and the thing that breaks is the cache itself. Single flight does nothing here, because nothing is being rebuilt. The cache is doing exactly what it was installed to do, nearly three times more than it can.

The bill has two halves and they are charged at wildly different rates. Dispatching a GET costs Redis single digit microseconds of CPU. At 3,333 a second that is under two percent of its one command loop. Copying the value out costs memory bandwidth, and lesson 002 put a megabyte from memory at nearer fifty microseconds today: 3,333 of those is 167 milliseconds of copying every second, about a sixth of a core. Add them and the busiest minute of Stagefront's year shows up as roughly a fifth of one CPU, which is the low twenties the engineer kept staring at and deciding was fine.

They were right. It was fine. The CPU was never the thing.

A hot key is priced in bytes, not in operations. Rate times value size is the only number that matters, and it is the one number a cache's default dashboard does not have. Lesson 007's two hundred byte session and this megabyte cost the node a factor of five thousand apart at the same request rate. Before you cache anything you expect to be popular, multiply its size by the rate you expect and compare the product to a network card. It takes ten seconds and it is the check nobody does.

One key is one slot, and one slot is one node

Lesson 031 spent a whole lesson on how a cluster spreads keys. A ring hashes the key and walks clockwise to the first owner. Redis Cluster, which lesson 031 contrasted with the ring, defines 16,384 fixed hash slots, maps a key to a slot with CRC16 modulo 16,384, and keeps an editable map from slot to node so an operator can move a hot slot by hand.

Every one of those mechanisms is a function of the key. Same key, same node, forever, which is the property the whole design exists to provide. Adding nodes does nothing. Rebalancing does nothing. Moving the slot moves the problem to another machine intact, and lesson 031's line about pinning a hot slot is true of a slot holding ten thousand warm keys and useless for one holding a single scorching key.

Sharding spreads keys, and a hot key is one key. There is no partitioning scheme that divides one key across two machines, because the key is the input to the division.

Redis Cluster even ships a tool for defeating the spread on purpose, and you want its name before you meet it in somebody else's code. A hash tag is a substring in braces: write seatmap:{show91}:blocks and only show91 is hashed, so every key carrying that tag lands on one slot, which is how multi-key commands work in a cluster. Teams reach for it to make a transaction possible and gather their busiest keys onto one node by hand.

Three ways to cool a key, and a cheap one nobody tries

You cannot divide the key, so you divide something else, and the moves differ in which clock gets the extra staleness.

Start with compression. A megabyte of seat statuses is the most compressible data in the building: forty thousand records drawn from a handful of statuses and a handful of price bands. Gzip it and a tenth is a conservative guess, so the value is a hundred kilobytes and 26.7 gigabits becomes 2.7, which fits the card with room to spare. The cost is CPU, and look where it lands. The cache compresses once per rebuild, six times a minute; the twenty boxes decompress 167 times a second each, about half a core apiece at gzip's couple of hundred megabytes a second. You have not made the work smaller. You have moved it off one shared network card and onto twenty CPUs, and twenty is a number you can buy more of.

Hold on to that, because it is what every fix below has in common.

Replicate the key. Write the map under ten names, seatmap:show91:0 through :9, and have each client pick one at random. Ten keys hash to ten slots and land on up to ten nodes, so each carries 333 requests a second and 333 megabytes a second, comfortably inside a card. The memory cost is ten megabytes for a fact you already had, which is nothing, and the write cost is sixty writes of a megabyte a minute, which is also nothing.

The cost is that you now have ten independently aged copies. A reader who refreshes twice and lands on replica 3 then replica 7 can watch the seat map go backwards in time by up to the full TTL: seats they saw taken reappear as free. Lesson 023 defined monotonic reads as a property of a reader's own read history, and this breaks it inside a single cache, which is a place nobody thinks to look for it. For Stagefront that is confusing and not a bug, because lesson 008 settled that clicking a seat does not buy it and only the database says yes. Point the same trick at an account balance or an unread count and you have built a value that oscillates. Lesson 031's variance argument bites here as well: nothing makes ten keys land on ten nodes, three sharing one is ordinary luck, and the slot map is the only place to fix it, which means hand-placing ten keys forever.

Split the key. Cut the map by block: twelve blocks, twelve keys, eighty three kilobytes each, up to twelve slots. The bytes fall by twelve before the spread even helps.

The honest version of this fix is not a caching change at all. A customer looking at block 112 never needed the other eleven blocks, so splitting the key is really splitting the screen: a tiny overview holding twelve per-block counts, then one block fetched when they pick one. The cheapest fix for a hot key is quite often a change to what you send rather than to where you keep it, and it is the one engineers skip because it belongs to somebody else's ticket.

What splitting costs is that the pieces no longer agree. The twelve blocks came from twelve different moments, so "4,112 seats left" summed across them is a number that was never true at any instant. Lesson 044 called this out for object listings, where a paginated walk is twelve hundred correct answers to twelve hundred slightly different questions; a split cache value is the same shape indoors. A Redis Cluster client cannot even fetch them in one call, because a multi-key command whose keys live in different slots is refused with CROSSSLOT.

The level in front of it

That last row is the one to reach for first.

Lesson 008 drew the four places a copy can sit, in the process, in a shared store, at the edge and in the browser, and priced the distance between them as a list of choices. Lesson 030 is where two of them turn out to be live at once, in one row of its table, and nobody has yet asked what a stack of them promises as a whole. Put a small dictionary inside each checkout box, in front of the shared cache, and the arithmetic stops being about request rate.

Each of the twenty boxes fetches the map once per its own TTL, one dictionary to a box. That is the whole formula: fetches a second equals caches divided by the local TTL. Count caches and not boxes, so four processes to a box multiplies it by four. A two second local TTL makes it ten fetches a second, ten megabytes, eighty megabits. From 26.7 gigabits to eighty megabits for two lines of code.

Now look at what a longer local TTL buys, because this is where the interesting shape is.

local TTL   fetches/sec   bytes/sec    reduction
   0 s         3,333       3,333 MB         1x
   2 s            10          10 MB       333x
  10 s             2           2 MB     1,667x

The first two seconds buy a factor of 333. Going from two seconds to ten buys five times more and costs eight additional seconds of lying to customers about which seats are free. The saving is one over the TTL, so it is nearly all collected immediately, while the staleness you pay is linear and never stops accruing. In a stack, the level nearest the reader wants the shortest TTL it can afford, which is the opposite of the instinct that says a cache closer to the user should hold things longer.

Ten seconds plus two is twelve seconds of worst case staleness on a map lesson 009 already defended at ten. Lesson 023 put a number on one second of staleness at that minute: a smaller stadium selling out mid flood hands 3,333 people a page that is wrong about the show. Two more seconds of a sold seat looking free is two more seconds of clicks that fail, and a failed click is a worse morning than a seat you were never offered. Which is why you spend two and not ten. The curve hands you almost the whole saving at the only price you can defend.

Why Marlow should not build one

Now run the same proposal at Marlow Books, a four person online bookshop that exists only in this course, where the book page is the busiest read in the building. Same two lines, same shape, and it ought to be the same win.

It is not, and the reason is the most useful thing here.

Lesson 008's rule was that a cache's real output is the load it takes off the origin, which lives on the other side of the subtraction. Point it at a level rather than at a cache. A local hit is a Redis request that did not happen, not a Postgres read that did not happen, because a local miss falls through to the shared cache exactly as before and the hit rate against the database does not move by a hair. The output of a level is load removed from the level below it. Marlow's level below is a Redis serving the 384 page requests a second lesson 008 derived from lesson 006's Christmas mix, twelve kilobytes each, which is four and a half megabytes a second. It has never been a bottleneck, and nothing you take off it is worth having.

A level is worth its staleness only when the level below it is the bottleneck. A hot key is what makes a cache node the bottleneck, which is why the fix and the failure arrive together: the condition that creates the problem is the condition that makes the cheapest fix enormous.

The staleness is also worse than it looks.

Lesson 030 counted the copies of every fact the shop depends on, and a rendered book page already had ten: one Redis shell on a one day expiry, and nine edge copies on ten minutes each. Lesson 005's second box and lesson 006's four application processes per box make eight processes, so an in-process level takes that page from ten copies of one fact to eighteen.

Then add up the clocks, and notice that they add rather than compete. An edge misses, fetches from Redis, and gets a shell a second short of a full day old. It starts its own ten minutes on that. So the page's real correctness bound is twenty four hours and ten minutes rather than a day, which is a number no lesson in this course has written down. A local level in front makes it twenty four hours, ten minutes and whatever you chose. TTLs add, unless a level tells the level above it how old the value already is.

That exception is not hypothetical and HTTP has had it for decades. A shared HTTP cache sends an Age header saying how long it has held the response, and the cache downstream subtracts it from the freshness it was granted, so a browser handed a max-age of 600 with an Age of 550 knows it has fifty seconds left and not ten minutes. The levels that speak HTTP solved this before most of us started. A dictionary stamping its own expiry on a value it fetched from Redis has no idea how old that value was on arrival, and will not be told.

Which is the real objection to Marlow's local level, and it is not the eighteen copies. It is that eight of them cannot be deleted. Lesson 046 watched the founder use lesson 009's invalidation path: at 08:31 on 13 October he flushed the cache and, in 046's words, the shop was correct inside a minute. Read that against lesson 030's table. Redis was correct inside a minute. The nine edges carried the wrong author until 08:41, decaying city by city the way lesson 023's wrong price decayed from 09:41 to 09:50, because an edge runs its clock from whenever its own city first asked. Eight local dictionaries are eight more copies with no delete command at all.

February's move to a shared Redis is what ended the shop's per box caches, and lesson 008 priced the win at two points of hit rate. A local level does not undo that, since the misses still fall through and the fleet stays warm. What it brings back is the eight way disagreement, paid for in staleness instead of in misses.

A level you cannot invalidate is a level whose TTL is your real correctness bound. Choose it as though the delete button does not exist, because for that level it does not.

Eviction picks the victim. Admission asks whether there should be one.

One debt left, and it has been outstanding since lesson 008.

The crawler. Forty distinct ISBNs a second, 24,000 entries in ten minutes, 288 megabytes of pages no human will ask for again, walked through a 256 megabyte cache that holds about 21,000 twelve kilobyte pages. LRU saw a burst of brand new, never aged, apparently wildly popular content and threw out the bestsellers to make room for it. Lesson 008 named the hole and nothing since has closed it.

Everything in that paragraph is a statement about the eviction policy, which answers one question: when there is no room, who leaves. LRU answers by recency, LFU by frequency, and both of them have already conceded the thing that matters, which is that the newcomer is coming in.

An admission policy answers a different question. Does this entry deserve to displace an existing one at all? A cache that can answer no is a cache the crawler cannot get into.

Redis does not have one, and it does have a good partial answer. Since 4.0, released in July 2017, maxmemory-policy accepts allkeys-lfu: every key carries an eight bit counter, incremented probabilistically so it saturates logarithmically rather than running away (lfu-log-factor, default 10), and decayed as the key sits idle (lfu-decay-time, default one minute). A new key starts at 5, a hardcoded constant you cannot configure, deliberately above zero so a newcomer is not evicted the instant it arrives. Eviction samples a handful of candidates rather than scanning, five by default, and discards the lowest counter it finds.

Run the crawler against that. Its entries sit at 5 or 6 forever, because each ISBN is read exactly once. A title the shop is actually selling has been read many times in the last minute and its counter is well clear. So as the crawler's junk accumulates, the sample of five increasingly contains junk, and the crawler starts evicting itself. One configuration line, available for nine years, and 008's week of quiet damage mostly goes away.

Mostly, and the gap is arithmetic. Early on the cache is all shop entries with high counters, so the first crawler entry displaces a long tail title, and so does the second. A sample of five finds junk with probability about twenty two percent once a thousand junk entries are in, sixty five percent at four thousand. It converges, and it spends a few thousand of the shop's entries getting there. LFU eviction makes the junk buy its way in by throwing something out. Admission means it never gets to make the trade.

The real thing exists and most readers already have it in their dependency tree. Caffeine, the Java cache, runs W-TinyLFU, which is three parts. A small admission window, an LRU, about one percent of capacity by default. A frequency sketch, a count-min sketch over recent history whose counters are all halved every so many accesses so it forgets. And a main region run as a segmented LRU, with entries landing in probation and promoted to protected on a second access, protected capped at eighty percent.

The admission decision happens between the window and the main region. An entry falling out of the window does not simply enter; it is compared against the entry the main region would have to evict to take it, and it is admitted only if the sketch says it is the more frequent of the two.

Walk the crawler through one sized like Marlow's, which runs Redis and so has none of this. An ISBN arrives, enters a window of 213 entries, and at forty a second falls out of it about five seconds later. Now it is held up against the main region's victim. The sketch says this key has been seen once; the victim has been seen rather more. The crawler's entry is dropped and the main region's 21,000 entries are never touched at all. Not evicted and refilled. Never disturbed.

The sketch records keys the cache does not hold. It remembers that it has seen this ISBN before even though it refused to store it, which is how a brand new genuinely popular title gets in on its second or third ask while a crawler walking a million keys never does. The trick is remembering the keys you did not keep, and it costs a few bits per counter rather than an entry.

The window matters from the other side of the same idea. Pure LFU starves newcomers, since a new bestseller also starts cold against high incumbents; the window is where it gets read a second time before anybody asks the sketch about it.

Lesson 046 is owed a straight answer about one thing admission does not fix. 046 established that evicting a dirty entry from a write-behind cache is a lost write, and admission does not change that: it refuses newcomers, it does not protect a dirty entry when the pressure is real. What it removes is the class of pressure that was buying nothing, which is much of it in practice and not all. 046's rule stands unamended. Original data does not go in a buffer allowed to discard, and a cleverer policy is not a promise.

Notice where that lands. Redis has no admission policy and Caffeine does, so the level holding your fleet's whole working set is the dumb one and the level holding a few thousand entries inside one process is the clever one. Backwards from what anybody would design, and it means the local level you added for the hot key arrives with the scan resistance thrown in.

Recap

Sharding spreads keys, and a hot key is one key. A ring, a slot map and a plain remainder are all functions of the key, so the same key returns the same node by design and no rebalancing divides it. Pinning a hot slot, lesson 031's one lever, works on ten thousand warm keys and not on one scorching one.

A hot key is priced in bytes, not in operations. Rate times value size, held against a network card. Stagefront's 3,333 requests a second for a one megabyte map is 26.7 gigabits offered to a ten gigabit card, while the same traffic is under two percent of the node's command loop and a sixth of a core of copying. The three graphs a cache ships with are all in the wrong unit, which is why it took a week to find.

Every fix moves the cost onto something you can buy more of. Compression moves bytes off one card and onto twenty CPUs. Replicating the key spreads one node's load over ten and pays in ten independent ages, which costs lesson 023's monotonic reads inside a single cache. Splitting it buys twelve slots and loses the ability to add the pieces up, which is lesson 044's "a paginated listing is not a snapshot" read indoors. None of them makes the work smaller.

TTLs add, unless a level passes on the age. An edge missing at twenty three hours fifty nine starts its own ten minutes on a value already nearly a day old, so Marlow's book page has a correctness bound of twenty four hours and ten minutes rather than a day. HTTP fixed this with the Age header decades ago; a dictionary in your own process has no equivalent, which is why a level you cannot invalidate is a level whose TTL is your real correctness bound.

A level is worth its staleness only when the level below it is the bottleneck. A local hit removes load from the shared cache, never from the database. Stagefront's cache is offered nearly three times its card, so the level is the whole fix. Marlow's serves four and a half megabytes a second, so the level buys nothing and costs eight copies no delete command reaches.

An eviction policy picks the victim; an admission policy asks whether there should be one. allkeys-lfu gets lesson 008's crawler evicting itself, after converging and after spending a few thousand of the shop's entries. W-TinyLFU refuses it outright, because the trick is remembering the keys you did not keep: a frequency sketch over keys the cache never stored is what tells a one-visit crawler from a new bestseller on its second ask.

Check your understanding

1. A product page's GET rate is 200 a second and its cached value is 400 kilobytes of denormalised JSON. Do the hot key arithmetic, then say which of today's four fixes you would ship first and what you would measure to know it worked.

2. Someone replicates a hot key ten ways and reports the node's bytes out down tenfold. A week later a ticket says a customer's cart total went up and then back down over two refreshes. Explain the mechanism, say whether replication was the wrong fix or the wrong value to use it on, and give the change you would make.

3. A local cache with a sixty second TTL sits in front of a Redis with a five minute TTL, in front of a database. A row is corrected. Give the worst case time before every reader sees the correction, show the working, and say what you would change to halve it at the lowest cost in load.

4. A colleague proposes moving Marlow's book page cache into the application processes to "save the Redis hop", citing lesson 002's half millisecond against lesson 008's two millisecond hit. The arithmetic is right. Say what question they have not asked, and what measurement would make you approve it anyway.

5. You inherit a 64 gigabyte Redis on allkeys-lru serving a product catalogue, plus a nightly export that reads every product once. Hit rate drops every night and recovers by lunchtime. You may ship one change: switching to allkeys-lfu, giving the export its own cache, or having it read the database directly. Pick one and defend it against the other two.

6. Stagefront wants the seat map behind the CDN on a one second s-maxage, pointing out that lesson 022 already priced that trick on the on-sale landing page. Say what it does to the hot key, what it does to today's staleness sum, and the one property of the seat map that decides whether it is allowed.

Next lesson

048 Service Discovery and Configuration. Both halves of today's fix need every box to agree about something: which nodes are in the cluster, which slot sits where, what the local TTL is this week. Lesson 031 left the question of how a few thousand rows get to be identical in every process that routes, including the one that started thirty seconds ago, and 048 is where that gets answered.