Caching and Redis.

A cache is a notebook of answers you’ve already worked out, kept somewhere fast, so that when the same question comes again you read the answer instead of working it out again.

On the Spark that’s the difference between two seconds of GPU time and about one millisecond for a question your model has already answered. It’s the cheapest speedup there is. It’s also the easiest way to hand someone a wrong answer with total confidence, because the notebook has no idea when its answers stop being true. Every eval you run through a cached server, and every number on your Fireworks scoreboard, depends on getting that second half right.

You’ve met smaller versions of this already: the chip’s own small, fast memory in Why is NumPy 100x faster?, the operating system keeping file contents in memory in What happens when you save a file?, and the GPU reusing work on prompts that start the same way in Paged attention and prefix caching. Here the idea moves up into your own code, in front of the server from Baseline: my Spark vs Fireworks. After this, Nearest neighbors at scale is the machinery behind the “match by meaning” cache you’ll catch lying at the end, and Queues and logs is where “do the work later” becomes a design of its own.

Today

• Explain why keeping a few answers handy works at all: requests repeat, and a handful of popular ones make up most of the traffic. Spot the same trick at every layer, from the chip to your browser.
• Work out in your head how much faster things get for a given share of repeat requests, and say why the typical request gets dramatically faster while the slowest 1% barely change.
• Decide on purpose how long a stored answer may be trusted, name the four standard ways to wire a cache into code, and explain why knowing when a stored answer has gone stale is the hard part.
• Build, with tests, a cache that throws out whatever was used longest ago when it’s full and drops answers once they’re too old.
• Put Redis (a shared, in-memory store) in front of your inference server, measure it under realistic lopsided traffic, cause a pile-up where hundreds of requests redo the same work at once and fix it, and catch a cache that matches questions by meaning returning a wrong answer.

You’ll want the server and benchmark harness from Baseline: my Spark vs Fireworks and the load generator from Waiting vs working; Paged attention and prefix caching is a close cousin that helps but isn’t required. Plan on two evenings: one for the idea and your own cache class, one for Redis, the traffic experiments and the pile-up.

The Problem

Your eval harness runs 500 prompts through the server on the Spark every time someone changes the ranking code. Temperature 0, the same model, the same prompts. Every run, the GPU spends about 40 minutes re-deriving 500 answers it already gave yesterday, word for word.

So you put a dictionary in front of it. Key: the prompt. Value: the answer. The second run takes 4 seconds. You feel like a genius for about a week.

Then the bugs arrive, one at a time.

You swap in a fine-tuned checkpoint and the eval scores don’t move at all. Of course not: the cache is still serving the old model’s answers, because the model wasn’t part of the key. You fix that, and a teammate’s sampling experiment at temperature 0.8 produces exactly one answer per prompt no matter how many times it runs, because temperature wasn’t part of the key either. You move the cache to Redis so the three replicas share it, set every entry to expire after an hour, and at 10:00 every morning, an hour after the 9:00 warm-up job, the GPU queue spikes to hundreds of requests for the same handful of prompts, all at once.

Each of these is a classic, with a name and a known fix. A cache is the cheapest speedup in computing and also the most reliable way to serve something wrong with total confidence. This lesson is about both halves.

The Idea

A cache is a bet

A cachecacheA small, fast store that keeps copies of results from a bigger, slower source, so repeated requests skip the slow part. is a bet that you’ll ask for the same thing again soon. When you win, a hithitA request the cache can answer from its copy. The slow source is never touched., you skip the slow work entirely. When you lose, a missmissA request the cache can’t answer. You pay the full slow cost, plus the small cost of having checked the cache first., you do the slow work, and usually store the result in case it’s asked again.

Why is that bet usually a good one? You met the CPU version in How slow is slow?: programs reuse what they used recently, called temporal localitytemporal localityThe tendency to ask for something again soon after asking for it once. The reason “keep what was used recently” is a good rule.. People do the same. The prompt someone sent a second ago is far more likely to come again than one from last month.

The second reason is stronger, and it’s about popularity, not time. Rank every distinct request by how often it’s asked. In real traffic (web pages, search queries, words in text, songs, API calls, prompts) the counts are wildly lopsided. The most popular item gets asked twice as often as the second, three times as often as the third, and so on. That shape is a Zipf distributionZipf distributionA popularity curve where the k-th most popular item is requested about 1/k^s as often as the most popular one. With s near 1, a few items get a big share of all traffic and a long tail of items is rarely asked., and the exponent s (the skewskewHow lopsided popularity is. s = 0 means every item is equally popular; bigger s means the top items take more of the traffic.) says how lopsided.

Zipf is why small caches work. Here is what I measured on this Mac with a 15-line Python simulation: 10,000 distinct items, 200,000 requests drawn from a Zipf distribution, and an LRU cache (defined properly later) of a given size starting empty.

Read the s = 1.0 column. A cache holding 1% of the items answers 39% of requests. One holding 10% answers two thirds. Then read the uniform column: with no skew, a cache holding 10% of items answers 10% of requests, and caching is almost pointless. The workload decides whether a cache helps, not the cache. Before you build one, look at how often your requests actually repeat.

One idea, many layers

You have already met caches several times in this curriculum without the word always being in the title. They are the same idea at different sizes and distances.

The CPU caches from Why is NumPy 100x faster? copy RAM. The kernel’s page cache from What happens when you save a file? copies the SSD. A Python dict or functools.lru_cache copies the result of a function. Redis copies the result of a database query or a model call, and is shared by every server process. A CDNCDNContent delivery network. Thousands of servers spread around the world that keep copies of your files (and sometimes API responses) close to users, so most requests never cross an ocean. copies your web server’s responses, near the user. The browser copies them on the user’s own disk. And on the GPU, the KV cache and prefix cache copy attention keys and values that would otherwise be recomputed.

Every layer faces the same four questions, and the rest of this lesson is about them:

1. What is the key? What exactly must match for a stored answer to count as the answer to this request?
2. How long is a copy allowed to be trusted? (TTL, invalidation.)
3. When it’s full, what leaves? (Eviction.)
4. What happens on a miss, especially many misses at once? (Stampedes.)

What changes between layers is who answers them. The CPU answers them in silicon, the kernel in C, the CDN with HTTP headers you send. At the application layer, which is today’s layer, you answer them, in code, and you get them wrong in the ways from the Problem.

The arithmetic

Every request either hits or misses. If a fraction h of requests hit (the hit ratehit rateThe fraction of requests answered from the cache. 1 minus the hit rate is the miss rate.), the average cost is:

effective latency = h · t_hit + (1 − h) · t_miss

Plug in your server. A hit through Redis costs about 1 ms. A miss costs about 2,000 ms of GPU time for a short answer.

Look at the jump from 90% to 99%. Nine more points of hit rate, ten times faster. That’s because the misses dominate the sum: t_miss is 2,000 times t_hit, so the average is basically the miss rate times the miss cost. Think in miss rate, not hit rate. Going from 10% misses to 1% misses is a 10x improvement; going from 90% hits to 99% hits sounds like a rounding error.

Two more consequences of the same formula. A cache whose hit costs almost as much as a miss is useless at any hit rate (caching a 2 ms database query behind a 1 ms Redis round trip saves you at most half). And a cache with a terrible hit rate makes things slower, because every miss also pays the lookup.

Four ways to wire it in

Where does the cache sit relative to your code and the slow source? There are four standard answers, and the names come up in every system-design conversation.

cache-asidecache-asideThe application checks the cache, and on a miss reads the source itself and stores the result. The cache is a passive key-value store. The most common pattern. is what you’ll build today, and what most code using Redis does: get, and if nothing came back, compute and set. The cache knows nothing about where values come from. Pros: simple, the cache can be any key-value store, and if the cache dies your code still works (slowly). Cons: every caller has to remember the dance, and a miss costs three steps.

read-throughread-throughThe cache itself knows how to load a missing value (you give it a loader function). Callers only ever ask the cache. moves the loader into the cache. functools.lru_cache is read-through: you call the function, the decorator checks its table and calls the real function on a miss. CDNs are read-through: on a miss the edge fetches from your origin. The win is that loading logic lives in one place, which is also the natural place to make sure only one caller loads a given key at a time (more on that soon).

Those two are about reads. Writes raise a sharper question: when the data changes, who updates the cache?

write-throughwrite-throughEvery write updates the cache and the source together, and only then reports success. Reads after a write see the new value. keeps them in step: slower writes, fresh reads. write-behindwrite-behindThe cache accepts the write and reports success immediately, then writes to the source later, often in batches. Also called write-back. makes writes fast and lumps them together, at the price that a crash can lose writes the caller already thought were saved. Your CPU’s caches are write-back, and so is the page cache: in What happens when you save a file? you saw that write() returns long before the bytes reach the SSD, which is exactly why fsync exists.

For LLM responses there are no “writes” in the usual sense: the source (the model) never changes an answer behind your back; only you change the model. So cache-aside with a careful key is the right shape. The write patterns matter the moment you cache something users can edit.

How long to trust a copy: TTLs

A copy is a snapshot. The source may change after you took it, and the cache has no way of noticing. The bluntest, most reliable answer is to give every entry an expiry date: a TTLTTLTime to live. How long a cache entry may be served after it was stored. After that it counts as missing, and the next request refetches it.. In Redis, SET key value EX 3600 stores a value that disappears an hour later.

A TTL is a promise about staleness: “this answer is at most an hour out of date.” Choosing it is a business question wearing a technical costume. Ask three things:

1. How wrong can the answer be, and for how long, before someone is hurt? A stock price: seconds. A product description: an hour. A user’s permissions after being fired: zero, which means TTL alone is the wrong tool.
2. How often does the source actually change? Data that changes once a day gains nothing from a 10-second TTL except more misses.
3. What does a miss cost? If a miss is a 2 ms query, short TTLs are cheap. If it’s 2 seconds of GPU, every expiry is expensive, and you want long TTLs plus some other way to handle changes.

For your LLM cache, the answer to (2) is “never, until you change the model or the prompt template”. So the right TTL is long (days), and the thing that actually keeps answers correct is the key, not the clock. The TTL is there to bound memory and to clean up keys no one will ever ask for again.

Two refinements you’ll use. Jitter: instead of exactly 3,600 seconds, use 3,600 plus or minus a random 10%. Otherwise everything you stored in one burst (a warm-up job, a deploy) expires in one burst, which is the 10:00 spike from the Problem. Negative caching: also cache “not found” answers, briefly. If a missing user ID is requested 1,000 times a second, without a negative entry every one of those is a miss that hits the database.

Invalidation, the hard part

The alternative to waiting for a TTL is to remove or update the copy the moment the source changes: invalidationinvalidationRemoving or updating a cached copy because the source data changed. The hard part is doing it at the right moment, everywhere the copy lives, without races.. With cache-aside, the usual recipe is: write to the database, then delete the cache key. The next read misses and fetches the fresh value. It sounds airtight. It isn’t.

Invalidation is also hard because you have to know every key a change affects. A user renames themselves: which cached pages, search results and recommendation lists contain the old name? The usual escape is to not invalidate at all. Make the version part of the key instead: answer:v3:<hash>. When the data or the code changes, bump to v4. Old keys are simply never asked for again, and the TTL (or LRU) quietly clears them out. You trade memory for correctness, which is almost always the right trade. For your LLM cache this is the whole strategy: the model, its weights revision and the prompt template version go into the key, so changing any of them changes every key.

When it’s full: eviction

RAM is finite. When the cache is full and a new entry arrives, something has to leave. Choosing what is evictionevictionRemoving an entry to make room for a new one, because the cache is full. Not the same as expiry: an evicted entry may still have been valid., and the rule is the eviction policyeviction policyThe rule that picks which entry to evict. LRU, LFU, FIFO and random are the common ones.. The ideal rule would evict the entry that will be needed furthest in the future (Bélády’s optimal algorithm, 1966), which you can’t know. Every real policy is a guess about the future from the past.

• LRULRULeast recently used. When full, evict the entry whose last use is oldest. Bets that what was used recently will be used again soon. bets on recency. Cheap, adapts quickly when popularity shifts, and the default nearly everywhere. Its classic weakness: one big scan (a batch job reading 100,000 keys once each) pushes out every hot entry, because each scanned key is “recently used” for a moment.
• LFULFULeast frequently used. When full, evict the entry that has been used the fewest times. Bets on popularity rather than recency. bets on frequency. Resists scans (a key used once never outranks a key used a thousand times), but is slow to forget: yesterday’s viral prompt keeps its huge count. Practical LFUs let counts decay over time.
• ARCARCAdaptive Replacement Cache (Megiddo and Modha, IBM, 2003). Keeps a recency list and a frequency list, plus “ghost” lists of recently evicted keys, and shifts space between the two lists depending on which ghosts get asked for again. keeps both kinds of evidence and tunes the balance by watching its own mistakes. Used in ZFS. Modern designs in the same spirit (W-TinyLFU in Java’s Caffeine library) admit a new entry only if it looks more popular than the one it would push out.
• FIFO and random sound naive and are often within a few points of LRU on real traffic, with less bookkeeping. Redis itself doesn’t run exact LRU: it samples a handful of keys and evicts the oldest among them.

Try all of this before reading on. The figure runs an LRU cache over 200 keys whose popularity follows Zipf (key 1 is the most popular). Watch the stream, then move the sliders. The bottom chart re-runs 3,000 requests at every cache size and draws the hit-rate curve, next to the “ideal” dashed line of a cache that magically holds exactly the most popular keys.

Things to notice:

• The curve bends early. At skew 1.0 the first 20 slots give you most of the win. Doubling a cache that’s already on the flat part buys little, which is why cache sizing is a question for the curve, not for your gut.
• LRU sits below the ideal line, for two reasons. Every distinct key costs one compulsory misscompulsory missThe first request for a key always misses, no matter how big the cache. Also called a cold miss. on a cold start. And LRU keeps some unpopular keys that happened to be asked for recently, wasting slots. That gap is what LFU and ARC fight over.
• A TTL lowers the whole curve. Even key 1, asked for constantly, gets thrown out every TTL and costs a miss. That’s the price of the staleness bound, and the reason hot keys deserve special care when they expire.

Building LRU: a hash map and a doubly linked list

You need two operations, get and set, both in constant time, and the ability to find the least recently used entry instantly. No single data structure does all three.

A hash map (a Python dict) finds any key in O(1) but has no idea of order. A list knows order, but finding a key in it is O(n). The trick is to use both and make them point at each other.

Each node stores its key, its value, its expiry time, and two pointers: prev and next. The map stores key → node. Then:

• get(k): look up the node in the map. Missing: miss. Expired: unlink it, delete it from the map, miss. Otherwise unlink it from where it is and relink it right after HEAD. Return the value.
• set(k, v): if the key exists, update the node and move it to the front. Otherwise create a node, put it at the front, add it to the map, and if the map is now over capacity, take the node just before TAIL, unlink it, and delete its key from the map.

Why doubly linked? To unlink a node from the middle of the list you need to change its predecessor’s next, and with only forward pointers, finding the predecessor is a walk from HEAD. The prev pointer makes unlinking O(1). And why does each node store its own key? Because at eviction time you start from the node (just before TAIL) and need to delete the matching map entry.

Notice how TTL fits in: it’s checked lazily, at get time. An expired entry that nobody asks for just sits there until LRU pushes it out. That’s exactly what Redis does too, plus a background sweep. collections.OrderedDict is this same structure, written in C, with move_to_end and popitem(last=False); it’s what the prefix cache used. Today you build it by hand once, so it’s never magic again. Expect your version to be a few times slower than a plain dict lookup: on this Mac a hand-written Python get took about 0.15 µs against 0.03 µs for dict.get. Both are a rounding error next to a 1 ms network round trip.

Many misses at once: the stampede

Here’s the 10:00 spike. A hot key, say the answer to the prompt your whole team’s dashboard sends, is being read 200 times a second. All of those are hits. Its TTL runs out. For the next two seconds, while the first miss is being recomputed on the GPU, every request for that key misses too, because the value isn’t back yet. Each of them sends its own copy of the same request to the model.

This is a cache stampedecache stampedeMany requests miss on the same key at the same moment (usually right after it expires) and all recompute it at once, flooding the backend with identical work. Also called a thundering herd or dog-piling.. On a web stack it can knock over a database. On your server it’s worse in a specific way: the GPU lock serialises requests, so 400 identical misses means the 400th waits for 400 full generations, even though the answer was ready after the first.

The fixes, from simplest to most thorough:

• request coalescingrequest coalescingWhen several requests for the same key miss at once, only the first one does the work; the rest wait for its result and share it. Go’s standard library calls this singleflight.. Keep a table of “in-flight” keys. A miss first checks it: if someone’s already computing this key, wait for their result instead of starting another. In one asyncio process this is a dict from key to asyncio.Future, about ten lines. It only works within one process, though; three replicas still make three calls.
• A lock in the shared cache. Across processes or machines, the first miss takes a lock with SET lock:<key> <id> NX PX 10000 (set only if it doesn’t exist, expire in 10 seconds, so a crashed holder can’t block everyone forever). Whoever wins recomputes. Losers wait briefly and re-check the cache. More moving parts, but it works across the whole fleet.
• Jittered TTLs. Doesn’t stop one hot key’s stampede, but stops many keys from expiring together, which is what turns small stampedes into one big one.
• stale-while-revalidatestale-while-revalidateWhen an entry expires, keep serving the old copy for a while and refresh it in the background. Users get a slightly stale answer instantly instead of all waiting for a fresh one. Named after an HTTP Cache-Control extension (RFC 5861).. Store a “soft” expiry earlier than the real one. After the soft expiry, the first reader triggers one background refresh and everyone, including that reader, keeps getting the old value until the new one lands. Nobody waits. The cost is serving answers a bit past their TTL, which you’ve already decided is acceptable if you’re caching at all.
• Probabilistic early refresh. Each reader, as an entry nears expiry, recomputes early with a small probability that grows as the deadline approaches, so one reader almost always refreshes before the cliff. The “XFetch” paper below shows how to pick the probability.

You’ll build coalescing and the lock, and see each one’s limit.

Redis, in one sitting

RedisRedisAn in-memory data structure server: a separate program that holds keys mapped to strings, hashes, lists, sets, sorted sets and more, in RAM, and answers commands over a TCP connection. Used as a cache, a queue, a rate limiter, a session store. is a program you run next to your servers. You connect over TCP and send short text commands: SET k v EX 60, GET k, INCR counter, ZADD leaderboard 42 alice. It keeps everything in RAM, so a command is usually a few microseconds of work, and the round trip over the network or loopback dominates (roughly 0.1 ms on one machine; measure it in the Build).

Four things make it what it is.

It’s single-threaded where it matters. Redis executes commands one at a time on one thread, with an event loopevent loopA single loop that runs ready work one piece at a time and, when nothing is ready, sleeps until the OS reports that some socket or timer is ready. just like the one you built in Waiting vs working: it asks the kernel (epoll on Linux) which client sockets have commands waiting, runs each command to completion, writes the reply, repeat. Since Redis 6, extra threads can help read and write sockets, but command execution stays on one thread. Two big consequences. Every command is atomicatomicHappens all at once or not at all, with nothing else interleaved. No other client can see a half-done INCR. for free: INCR can’t race with another INCR, because nothing runs at the same time. And one slow command (KEYS * on ten million keys, a huge SORT) blocks every other client, exactly like a blocking call in an async def. Redis is fast because each command is tiny, not because it does many at once.

It stores data structures, not just strings. hashRedis hashA Redis value that is itself a small map of field → value, like a Python dict stored under one key.es, lists (queues), sets, sorted setsorted setA set where each member has a score, kept ordered by score. Leaderboards, priority queues, sliding-window rate limiters.s, streams (append-only logs), plus counters, bitmaps and HyperLogLog (approximate counting of distinct items). That’s why it’s used for far more than caching: the rate limiter you built could live in Redis and be shared by every replica.

It expires and evicts. Any key can carry a TTL. Expired keys are removed lazily (when someone touches one) and by a background job that samples keys with TTLs several times a second. When memory hits the maxmemory limit, maxmemory-policy decides what happens. The default, noeviction, refuses new writes with an error, which is right for a database and wrong for a cache. For a cache you set allkeys-lru or allkeys-lfu. Redis’s LRU is approximate: it samples a few keys (5 by default) and evicts the best candidate among them, which in practice is close to true LRU and saves two pointers per key.

It can survive a restart, if you ask. Two persistencepersistenceSaving in-memory data to disk so it survives a restart. Redis offers snapshots (RDB), an append-only log (AOF), both, or neither. options, both built on things you’ve seen. RDB snapshots: Redis calls fork(); the child process writes the whole dataset to a file while the parent keeps serving, and the kernel’s copy-on-write from Virtual memory means they share memory pages until the parent modifies one. A crash loses everything since the last snapshot. AOF: every write command is appended to a log, and appendfsync (always, everysec, or no) decides how often it’s fsynced, the same durability-for-speed trade from What happens when you save a file?. For a pure cache, you can turn persistence off: losing a cache costs time, not data. That’s the property to protect. A cache must be safe to lose. If deleting your Redis loses something that exists nowhere else, it’s a database, and should be treated as one.

A note on the name: in 2024 Redis changed to a more restrictive license, and the Linux Foundation forked the last open-source version as Valkey, which major clouds now offer; Redis later added an AGPL option. For your purposes they speak the same protocol and the same commands. Check the current state if it matters for work.

Caching LLM responses

Now the case you actually care about. Two very different caches go by the name “prompt caching”, so first, a separation.

The prefix cache reuses the KV cache for the shared beginning of prompts, inside the GPU. The model still runs and still generates every output token; it just skips recomputing attention for tokens it has seen. It’s exact by construction and works for partially matching prompts.

A response cache sits in front of the server and skips the model entirely. It returns the stored text of a previous answer. That’s thousands of times cheaper on a hit, and it only works when the whole request matches. The question that decides whether it’s correct is the one from the top of the lesson: what is the key?

Exact-match caching. The key is a hash of everything that can change the output. Not the prompt. Everything:

• the model ID and its revision (weights hash, checkpoint path, or a version you bump),
• the chat template or prompt-template version, and any system prompt your server adds,
• all of messages, in order, and any tools or response format,
• every sampling parameter: temperature, top_p, top_k, max_tokens, stop, seed, penalties.

Turn that into a canonical string (JSON with sorted keys and no whitespace, so the same request always gives the same bytes) and hash it with SHA-256: llm:v1: plus 64 hex characters. On this Mac, hashing a request with a 2,000-character prompt took about 5 µs. Free.

Why so paranoid? Every field you leave out is a bug from the Problem. Leave out max_tokens, and a request for 16 tokens gets served a stored 512-token answer (or worse, the reverse: a truncated answer for someone who wanted the whole thing). Leave out the model revision, and you evaluate the old model forever.

A few more rules for the response cache:

• Only store complete, successful answers. Not errors, not timeouts, not a stream that broke because the client hung up halfway. Check finish_reason.
• Streaming still works. On a hit, replay the stored text as SSE events, so clients don’t need to know. Time to first token on a hit becomes a millisecond, which will look wonderful on your scoreboard and mean nothing about the model. Label cached runs separately.
• Mind privacy. If one user’s conversation contains their own data, a shared cache keyed only on the text can only return that answer to someone who sent exactly the same text, which is fine. The danger comes with the next idea.

Semantic caching. Exact match misses “What’s the capital of France?” when the cached prompt was “what is the capital of france”. A semantic cachesemantic cacheA cache that matches requests by meaning instead of exact bytes: embed the prompt, find the most similar cached prompt, and if the similarity is above a threshold, return its answer. embeds each prompt into a vector (an embeddingembeddingA list of numbers (a vector) produced by a model so that texts with similar meaning land close together. Closeness is usually measured by cosine similarity., the same machinery as your bi-encoder retrieval work), searches the cached prompts for the nearest one (with the tools from Nearest neighbors at scale), and returns its answer if the cosine similaritycosine similarityA score from -1 to 1 for how closely two vectors point the same way. 1 means identical direction. Most sentence embeddings of real text score between about 0 and 1. is above a threshold like 0.9.

It raises hit rate on paraphrases. It also returns wrong answers, confidently, and you can see why from your ranking work: an embedding model is trained so that texts about the same thing land close together. I checked a few pairs with all-MiniLM-L6-v2, a popular small embedding model. “Is ibuprofen safe during pregnancy?” vs “Is ibuprofen unsafe during pregnancy?”: 0.979. “Convert 5 miles to km” vs “Convert 5 km to miles”: 0.987. “What is 2+2?” vs “What is 2+3?”: 0.887. Meanwhile real paraphrases like “What is the capital of France?” vs “France’s capital city?” scored 0.918, and “How many kilometers is 5 miles?” only 0.825 against the miles-to-km prompt. Topic similarity is not answer equivalence. Your cross-encoder exists precisely because bi-encoder similarity is a rough signal.

Use semantic caching only where a near-miss answer is harmless (FAQ bots with fixed answers, say), keep the threshold high, scope it per user or per tenant (otherwise a near match can hand one customer’s answer to another), and measure the false-hit rate on real traffic before trusting it. Exact match is boring and correct. You’ll find a failure yourself in the Build.

Build It

All of this goes in a new folder next to your inference project:

inference/
  server_naive.py        # from the baseline lesson, unchanged
  bench.py               # from the baseline lesson
  cache/
    lru.py               # Task 1: LRU + TTL, by hand
    test_lru.py
    keys.py              # Task 2: the cache key
    proxy.py             # Task 2: cache-aside proxy in front of the server
    make_zipf.py         # Task 3: workload generator
    stampede.py          # Task 4
    semantic.py          # Task 5

docker run -d --name redis -p 6379:6379 redis:7 \
  redis-server --save "" --appendonly no --maxmemory 512mb --maxmemory-policy allkeys-lru
pip install redis httpx fastapi uvicorn pytest
docker exec -it redis redis-cli ping                     # PONG
docker exec -it redis redis-cli SET hello world EX 10
docker exec -it redis redis-cli TTL hello                # counts down from 10
docker exec -it redis redis-benchmark -q -t get,set -n 100000

# cache/lru.py
import time
from typing import Any, Callable, Hashable

class _Node:
    __slots__ = ("key", "value", "expires_at", "prev", "next")
    ...

class LRUCache:
    def __init__(self, capacity: int, default_ttl: float | None = None,
                 clock: Callable[[], float] = time.monotonic):
        """capacity >= 1. default_ttl in seconds, None = never expires.
        Set up the map and two sentinel nodes (head, tail) linked to each other.
        Counters: hits, misses, evictions, expirations."""
        ...

    def _unlink(self, node: _Node) -> None: ...
    def _push_front(self, node: _Node) -> None: ...

    def get(self, key: Hashable, default: Any = None) -> Any:
        """Miss -> default. Expired -> remove, count, default. Hit -> move to front."""
        ...

    def set(self, key: Hashable, value: Any, ttl: float | None = None) -> None:
        """Insert or overwrite at the front. ttl overrides default_ttl.
        Over capacity -> evict the node just before tail."""
        ...

    def __len__(self) -> int: ...

# cache/test_lru.py
from lru import LRUCache

class FakeClock:
    def __init__(self): self.t = 0.0
    def __call__(self): return self.t

def test_evicts_least_recently_used():
    c = LRUCache(2)
    c.set("a", 1); c.set("b", 2)
    assert c.get("a") == 1          # a is now most recent
    c.set("c", 3)                   # so b is evicted, not a
    assert c.get("b") is None and c.get("a") == 1 and c.get("c") == 3

def test_ttl_expires():
    clk = FakeClock()
    c = LRUCache(10, default_ttl=5, clock=clk)
    c.set("a", 1)
    clk.t = 4.9; assert c.get("a") == 1
    clk.t = 5.0; assert c.get("a") is None
    assert len(c) == 0              # expired entries are actually removed

# cache/keys.py
import hashlib, json

KEY_VERSION = "v1"          # bump when the response format or template changes

def cache_key(body: dict, model_revision: str) -> str:
    """Return 'llm:{KEY_VERSION}:<sha256 hex>' for a chat request body.
    Include everything that changes the output: model + revision, messages,
    every sampling parameter (fill in defaults so a missing field and its
    default value give the same key), max_tokens, stop, seed, tools.
    Exclude things that don't: stream, request ids, user agent.
    Canonicalise with json.dumps(..., sort_keys=True, separators=(",", ":"))."""
    ...

def cacheable(body: dict) -> bool:
    """Your policy from the temperature Predict. Start with: temperature == 0
    or a seed is given."""
    ...

# cache/proxy.py (scaffolding)
import json, os
import httpx, redis.asyncio as aioredis
from fastapi import FastAPI, Request
from fastapi.responses import StreamingResponse
from keys import cache_key, cacheable

UPSTREAM = os.environ.get("UPSTREAM", "http://127.0.0.1:8000")
MODEL_REVISION = os.environ.get("MODEL_REVISION", "base")
TTL = int(os.environ.get("CACHE_TTL", str(3 * 24 * 3600)))

app = FastAPI()
r = aioredis.Redis(host=os.environ.get("REDIS_HOST", "127.0.0.1"), port=6379)
client = httpx.AsyncClient(timeout=None)

async def replay(lines: list[str]):
    """Yield stored SSE lines exactly as the server sent them."""
    for line in lines:
        yield line + "\n\n"

async def forward(body: dict, collected: list[str]):
    """Stream from upstream to the client, appending each 'data: ...' line to collected."""
    async with client.stream("POST", f"{UPSTREAM}/v1/chat/completions", json=body) as resp:
        async for line in resp.aiter_lines():
            if line.startswith("data:"):
                collected.append(line)
                yield line + "\n\n"

@app.post("/v1/chat/completions")
async def chat(req: Request):
    body = await req.json()
    # 1. not cacheable -> just forward (header x-cache: bypass)
    # 2. key = cache_key(...); stored = await r.get(key)
    #    hit  -> StreamingResponse(replay(json.loads(stored)), headers={"x-cache": "hit"})
    # 3. miss -> stream forward(...) to the client; when the stream ends, if the last
    #    chunk had a finish_reason and you saw "data: [DONE]", store the lines with
    #    await r.set(key, json.dumps(lines), ex=TTL)   (add jitter!)
    #    headers={"x-cache": "miss"}
    # 4. if Redis is down or slow (wrap calls in a short timeout), treat it as a miss
    #    and serve from upstream anyway. A cache outage must not be a site outage.
    ...

# cache/make_zipf.py: N distinct prompts, R requests, popularity ~ 1/rank^s
import json, random, sys
N, R, S, SEED = 500, 1000, 1.0, 0
rng = random.Random(SEED)
topics = ["sorting", "TCP", "Redis", "the GIL", "B-trees", "attention", "LoRA", "DNS",
          "mmap", "consistent hashing"]
prompts = [f"In two sentences, explain {topics[i % 10]} to a new engineer. (variant {i})"
           for i in range(N)]
weights = [1 / (k + 1) ** S for k in range(N)]
with open(sys.argv[1] if len(sys.argv) > 1 else "zipf.jsonl", "w") as f:
    for idx in rng.choices(range(N), weights=weights, k=R):
        f.write(json.dumps({"id": idx, "messages": [{"role": "user", "content": prompts[idx]}],
                            "max_tokens": 32, "temperature": 0}) + "\n")

# cache/stampede.py
# 1. send one request for the hot prompt (fills the cache), with CACHE_TTL=5 on the proxy
# 2. sleep 5.5 s so it expires
# 3. fire 200 concurrent identical requests with asyncio.gather + httpx
# 4. print: upstream calls during the burst (from /stats), p50 and max latency

Measure

Redis itself. From Task 0:

Expect tens of thousands to a couple hundred thousand requests per second without pipelining, several times more with it, and a single Python round trip on the order of 0.1-0.3 ms. The gap between the first two rows is the round trip: Redis does far more commands per second than one connection can feed it one at a time. That’s the latency vs bandwidth distinction again.

Hit rate vs cache size. 500 distinct prompts, 1,000 requests, s = 1.0:

For reference, my simulation of this exact setup, but with 2,000 requests instead of 1,000 (seed 0), gave LRU hit rates of 0.24, 0.39, 0.52, 0.64, 0.78 and 0.81. With 1,000 requests, yours will be a bit lower, because compulsory misses are a bigger share of a shorter run. Look at the last row: even a cache big enough for every prompt can’t beat 1 minus (distinct prompts seen / requests). In my 2,000-request run 373 distinct prompts appeared, so the ceiling was 1 − 373/2,000 = 0.81. Your measured hit rate should match the simulation within a couple of points; at concurrency 4 the order of arrivals shifts slightly. If it doesn’t match, your key function is wrong (two requests that should share a key don’t).

Latency.

What you should see: p50 collapses to milliseconds once the hit rate passes 50%, and p99 stays at miss latency, as the p50/p99 Predict said. Two things to check in your numbers. First, the mean should roughly match the formula, but misses with the cache on are faster than without it: at concurrency 4 behind the GPU lock, a miss waits behind other misses, and with half the requests answered from cache, the queue is shorter. Caching helps the misses indirectly by taking load off the bottleneck. Second, the Redis hit p50 should be a millisecond or two higher than the local LRU’s, which is the network round trip plus the Python client, and almost always worth it for a cache shared by every replica.

Stampede.

I ran a stripped-down version of this on my Mac (1,000 concurrent asyncio tasks, a 200 ms fake backend): 1,000 backend calls without coalescing, exactly 1 with it, and the same wall time for both, because the fake backend had unlimited parallelism. Your fake upstream doesn’t serialise either, so the latency difference will be small; the call count is the point. Against the real GPU server, which runs one request at a time, those 200 calls would mean the last request waits about 200 × 2 s, nearly 7 minutes, for an answer that was ready after 2 seconds. With 4 workers and in-process coalescing you’ll see 4 calls (one per process), which is the limit of the in-process fix.

Semantic cache.

You should find that the two columns fall together as the threshold rises, and that some trap pairs score higher than some paraphrase pairs. When that happens no threshold separates them, and that’s the finding: similarity measures topic, not whether the answer is the same.

Break It

1. Drop a field from the key. Remove max_tokens from cache_key. Send a prompt with max_tokens: 8, then the same prompt with max_tokens: 256. The second user gets the 8-token answer, from cache, in a millisecond. Now make cache_key ignore model_revision, run a few eval prompts, then restart the server with a different model (any other small instruct model will do) and run them again. Every answer comes back from the old model, and the scores don’t move. This is the most common cache bug in ML infrastructure, and the fix is the version-in-the-key discipline, not a better TTL.

2. Make every key expire at once. Warm the cache with 200 prompts in a burst with a fixed TTL of 60 seconds and no jitter, then send steady traffic over those prompts. At the 60-second mark the hit rate falls off a cliff and the upstream sees a wall of misses. Add ±10% jitter and rerun: the misses spread out over 12 seconds instead of arriving together.

3. Fill Redis with noeviction. Restart Redis with --maxmemory 2mb --maxmemory-policy noeviction and run the workload. Writes start failing with an error like OOM command not allowed when used memory > 'maxmemory'. Does your proxy still serve the request (it should: a failed cache write is not a failed request), or does it return 500? Then switch to allkeys-lru and watch evicted_keys climb in INFO stats instead.

4. Scan through a small LRU. Run a cyclic workload: prompts 1, 2, …, 60, 1, 2, …, 60, with a local LRU capacity of 50. The hit rate is zero. Not low: zero. Each prompt is evicted just before it comes back, because the 50 most recently used are always the 50 you won’t need next. Increase capacity to 60 and it jumps to nearly 100%. It’s the same failure the prefix cache lesson found with round-robin system prompts, and it’s why databases and LFU/ARC-style caches treat one-time scans specially.

Explain It Back

Answer out loud, in plain words, as if in an interview. Then check.

Go Deeper

• Rajesh Nishtala et al., “Scaling Memcache at Facebook”, NSDI 2013. The best real-world account of every problem in this lesson at enormous scale: invalidation across regions, leases to stop stale sets and stampedes, cold clusters, hot keys.
• Redis docs: “Key eviction” and “Redis persistence” (on redis.io). How maxmemory-policy, the sampled LRU and LFU actually work, and the honest trade-offs between RDB and AOF. Short and precise.
• Nimrod Megiddo and Dharmendra S. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache”, FAST 2003. A beautiful paper: how to get the benefits of both LRU and LFU, and adapt between them, in constant time per request.
• Lee Breslau, Pei Cao, Li Fan, Graham Phillips, Scott Shenker, “Web Caching and Zipf-like Distributions: Evidence and Implications”, INFOCOM 1999. The measurement that showed web traffic follows Zipf and derived what that means for hit rate vs cache size.
• Andrea Vattani, Flavio Chierichetti, Keegan Lowenstein, “Optimal Probabilistic Cache Stampede Prevention”, VLDB 2015. The XFetch algorithm: refresh early with a probability that makes the stampede vanish, with a one-line formula.
• Mark Nottingham, RFC 5861: HTTP Cache-Control Extensions for Stale Content, and RFC 9111: HTTP Caching. Where stale-while-revalidate comes from, and the standard every browser and CDN cache follows.
• Go’s singleflight package and Brad Fitzpatrick’s groupcache. About a hundred lines that are the canonical implementation of request coalescing. Read the source.
• GPTCache (zilliztech/GPTCache on GitHub). A popular open-source semantic cache for LLMs. Read how it configures similarity thresholds and evaluation, with your Task 5 results in mind.

Connections

This lesson is the application-level version of ideas you’ve met lower down: How slow is slow? and Why is NumPy 100x faster? (locality, the hardware caches), What happens when you save a file? (the page cache, write-back, fsync, which reappear as Redis AOF), and Virtual memory (the fork and copy-on-write behind Redis snapshots). Redis’s single thread is the event loop from Waiting vs working, and a slow Redis command is the same mistake as a blocking call in an async def.

On the inference side, it sits in front of the prefix cache: one skips the model, the other skips part of the prompt, and both live or die by their key. p99 and load testing explains why the cache barely moves your tail. Load balancers and state is why a shared Redis beats 50 private dicts, and Rate limits and backpressure is the other half of protecting a GPU from a flood: a stampede is a flood you caused yourself. Next in the Data track, Nearest neighbors at scale is the machinery a semantic cache runs on, and Queues and logs is where write-behind’s “do it later” becomes a design of its own.