These are the notes for System Design episode 7. Last episode, a load balancer spread our traffic across many servers. But all of them still ask one database the same questions, again and again. Here you invent the fix that makes almost every fast app fast: the cache. We measure a cache hit vs a cache miss, see why memory is so fast (latency numbers), why hit rate decides everything, what to do when the cache fills up (eviction, LRU), and how to fight stale data (TTL, invalidation). Every Python demo below is self-contained and runs as-is; the outputs shown are real (Python 3.13). The demos that use time.sleep vary by a few milliseconds per run, so your numbers will be close but not identical.
The six problems
| Problem | What it teaches |
|---|---|
| Same question, 40 times | The database bottleneck |
| Keep it ready | Cache, hit and miss |
| Why memory is so fast | Latency numbers |
| How often does it help? | Hit rate |
| The cache fills up | Eviction, LRU |
| The price changed | Stale data, TTL |
Problem 1: same question, 40 times (the database bottleneck)
Lunch rush at ChaiNow. 40 people open the menu at once, and every menu needs the same answer: how much is a masala chai? So the servers ask the database 40 times: the exact same question, and the exact same answer. Our servers can scale out, but the database is one shared thing, and it becomes the bottleneck: the one slow part that slows everything down.
Demo 1: no cache
import time
def db_get_price(item): # the database: about 50 ms per query
time.sleep(0.05)
return {"masala chai": 20, "samosa": 15}[item]
start = time.perf_counter()
for user in range(40): # 40 users open the same menu
db_get_price("masala chai")
total = (time.perf_counter() - start) * 1000
print(f"40 requests -> 40 database queries, {total:.0f} ms")
Output (timing varies slightly):
40 requests -> 40 database queries, 2008 ms
time.sleep(0.05)pretends to be a database query that takes 50 ms.time.perf_counter()is a precise clock for measuring elapsed time.- 40 queries, about 2 seconds of database work, for one answer that never changed.
- The obvious fix is a bigger database. But remember episode 5: scaling up has a ceiling, and it's still one machine. Look closely: the problem isn't that the database is slow. We keep asking it the same question.
Problem 2: keep it ready (the cache)
| At the chai stall | In your system |
|---|---|
| A kettle of ready chai: made once, poured 40 times | Cache: a saved copy of an answer, kept close, so you don't redo the work |
| Chai in the kettle: pour it, 5 seconds | Cache hit: the answer is already in the cache (fast path) |
| Kettle is empty: brew a fresh batch | Cache miss: ask the database, and save the answer for next time (slow path, once) |
Demo 2: with a cache
import time
def db_get_price(item): # the database: about 50 ms per query
time.sleep(0.05)
return {"masala chai": 20, "samosa": 15}[item]
cache, hits, misses = {}, 0, 0
def get_price(item):
global hits, misses
if item in cache: # cache hit: answer from memory
hits += 1
return cache[item]
misses += 1 # cache miss: ask the database once
cache[item] = db_get_price(item)
return cache[item]
start = time.perf_counter()
for user in range(40): get_price("masala chai")
total = (time.perf_counter() - start) * 1000
print(f"40 requests -> {misses} database query, {total:.0f} ms")
print(f"hits: {hits}, misses: {misses}")
Output (timing varies slightly):
40 requests -> 1 database query, 50 ms
hits: 39, misses: 1
- The cache is just a dictionary.
get_pricelooks there first: if the item is there, that's a hit, returned straight from memory. If not, that's a miss: ask the database once and save the answer. cache, hits, misses = {}, 0, 0sets up an empty cache and two counters in one line;global hits, misseslets the function change those counters.- One database query instead of 40. About 50 ms instead of 2 seconds. The first user paid the full price; the other 39 got it almost free. You just invented the cache!
Problem 3: why memory is so fast (latency numbers)
From Latency Numbers Every Programmer Should Know (Jeff Dean, originally Peter Norvig):
| Fetching data from... | About |
|---|---|
| L1 cache (inside the CPU) | 0.5 nanoseconds |
| Main memory (RAM) | 100 nanoseconds |
| SSD, random 4 KB read | 150 microseconds (150,000 ns) |
| Round trip inside the same data centre | 500 microseconds (500,000 ns) |
| Spinning disk seek | 10 milliseconds (10,000,000 ns) |
| California → Netherlands → California | 150 milliseconds |
- A random SSD read takes 1,500 times longer than a memory read (150,000 ÷ 100).
- So a cache wins twice: it's in memory, and it's close. That's why tools like Redis, "an open-source, in-memory data structure store", say "typical operations complete in under one millisecond".
(Units: 1 millisecond = 1,000 microseconds = 1,000,000 nanoseconds.)
Problem 4: how often does it help? (hit rate)
A cache only helps when it hits. The average time per request is:
average = hit rate × cache time + miss rate × database time
Demo 3: hit rate decides everything
# average time = hit rate x cache time + miss rate x database time
CACHE_MS, DB_MS = 1, 50
for hit_rate in [0.0, 0.5, 0.9, 0.99]:
avg = hit_rate * CACHE_MS + (1 - hit_rate) * DB_MS
print(f"hit rate {hit_rate:>4.0%} -> average {avg:5.2f} ms")
Output:
hit rate 0% -> average 50.00 ms
hit rate 50% -> average 25.50 ms
hit rate 90% -> average 5.90 ms
hit rate 99% -> average 1.49 ms
1 - hit_rateis the miss rate.:>4.0%prints a fraction like 0.9 as a percentage (90%), right-aligned in 4 characters.- No hits: 50 ms. Half hits: about 25. 90%: about 6. 99%: about 1.5 ms.
- From 90% to 99% the average drops by about four times (5.90 → 1.49). The hit rate is the single most important number for a cache.
- It's also why caches work so well in real life: a few popular items, like the top of a menu, get most of the requests.
Problem 5: the cache fills up (eviction, LRU)
If caching is great, why not cache everything, every item anyone ever asked for? Because memory is small and expensive compared to a database's disk. The cache grows and grows, to millions of items. When the episode ran a "cache everything" loop with six million items on a machine limited to 400 MB of memory, Python stopped with MemoryError (see Common mistakes below). A cache has to have a size limit. And when it's full, something has to go. But what?
| In your kitchen | In your cache |
|---|---|
| A small counter: room for only a few jars (salt, chilli, haldi); the rest stays in the storeroom | Cache size limit: maxsize, room for N items |
| Counter is full: one jar must go back | Eviction: remove an item to make room |
| The jar unused the longest goes back to the storeroom | LRU (least recently used): the item untouched for the longest goes first |
The Python docs: an LRU cache "works best when the most recent calls are the best predictors of upcoming calls".
Demo 4: functools.lru_cache
from functools import lru_cache
PRICES = {"chai": 20, "samosa": 15, "vada pav": 25, "poha": 30}
@lru_cache(maxsize=3) # keep only the 3 most recently used
def get_price(item):
print(f" database query for {item}")
return PRICES[item]
for item in ["chai", "samosa", "vada pav", "chai", "poha", "samosa"]:
print(item, "->", get_price(item))
print(get_price.cache_info())
Output:
database query for chai
chai -> 20
database query for samosa
samosa -> 15
database query for vada pav
vada pav -> 25
chai -> 20
database query for poha
poha -> 30
database query for samosa
samosa -> 15
CacheInfo(hits=1, misses=5, maxsize=3, currsize=3)
@lru_cache(maxsize=3)is a decorator: it wrapsget_pricewith an LRU cache that "saves up to the maxsize most recent calls" (if you write plain@lru_cache, the defaultmaxsizeis 128). Theprintinside only runs on a real "database" call, so everydatabase queryline is a miss.- Chai, samosa and vada pav are misses and fill the cache. Then chai again: no database line. That's a hit.
- Poha arrives and the cache is full. Who is evicted? Not chai, we just used it. Samosa, the least recently used. So when samosa comes back, it's a miss again.
cache_info()confirms: 1 hit, 5 misses, 3 items stored.- A cache is always a trade: more room means more hits, but more memory.
Problem 6: the price changed (stale data)
Demo 5: the cache never finds out
database = {"masala chai": 20}
cache = {}
def get_price(item):
if item not in cache:
cache[item] = database[item]
return cache[item]
print("price:", get_price("masala chai"))
database["masala chai"] = 25 # the owner raises the price
print("price:", get_price("masala chai"), "<- still the old price!")
Output:
price: 20
price: 20 <- still the old price!
- The database says 25, but the cache still answers 20.
- This is stale data: a cached copy that no longer matches the real data. Here it's 5 rupees. For a bank balance or a train seat, it's a real bug.
- Why? A copy doesn't know when the original changes.
The milk packet, again
| In real life | In your cache |
|---|---|
| "Use within 2 days", printed on the packet (episode 3) | TTL (time to live): each copy expires on its own after N seconds |
| "Prices changed!": the owner tells every stall to throw out the old list | Invalidation: delete the cached copy on purpose because the data changed |
| Shorter date = fresher, but more trips to the shop | The trade-off: a shorter TTL means fresher data, but more misses |
Demo 6: TTL
database = {"masala chai": 20}
cache = {} # item -> (price, saved_at)
TTL = 60 # seconds a cached price stays valid
def get_price(item, now):
if item in cache:
price, saved_at = cache[item]
if now - saved_at < TTL:
return price, "hit"
cache[item] = (database[item], now) # missing or expired: refresh
return cache[item][0], "miss"
print("t=0 ", get_price("masala chai", now=0))
database["masala chai"] = 25 # price changes at t=10
print("t=30 ", get_price("masala chai", now=30))
print("t=61 ", get_price("masala chai", now=61))
Output:
t=0 (20, 'miss')
t=30 (20, 'hit')
t=61 (25, 'miss')
- Each cached price is saved with the time it was saved. If the copy is younger than the TTL, it's a hit; if it's missing or too old, we refresh it from the database. (We pass
nowin by hand so the demo doesn't have to wait a minute.) - At 0: a miss, 20. At 30: a hit, still 20, so it was stale for a while. At 61: the copy expired, so a miss, and we get the new price, 25.
- TTL puts a limit on how stale data can get. For a menu, a minute of old prices is fine. For a bank balance, you'd invalidate the moment it changes.
"There are only two hard things in Computer Science: cache invalidation and naming things." (Phil Karlton)
You use caches all day
| Where | What it keeps |
|---|---|
| Browser cache | Images and files you already downloaded |
| CDN | Copies of files in cities near you (its own episode later) |
| App server memory | Like our dictionary and lru_cache |
| Shared cache | Redis, used by all servers at once |
| Inside the database | Hot rows kept in RAM |
| Inside the CPU | L1 cache: about 0.5 ns |
The whole chain
- Same question 40 times → the database bottleneck
- Keep a copy close → cache (hit / miss)
- Why it's fast → memory ≈ 100 ns, and close by
- When it helps → hit rate
- Cache fills up → size limit, eviction, LRU
- Old price → stale data → TTL, invalidation
Common mistakes (and the real errors)
| Mistake | Code | Error | Fix |
|---|---|---|---|
| A cache with no size limit eats all the RAM | cache[item_id] = data # for every item, forever |
MemoryError |
Set a limit: lru_cache(maxsize=...), or a TTL |
| Cache keys must be hashable; a list can change | @lru_cache on def total(items), then total(["chai"]) |
TypeError: unhashable type: 'list' |
Pass a tuple instead: total(("chai",)) |
| Reading the cache directly on a miss | price = cache["poha"] # never cached |
KeyError: 'poha' |
A miss isn't an error: check if item in cache, else ask the database |
The MemoryError, reproduced with a 400 MB memory limit (in a Linux shell: ulimit -v 400000, then python3 main.py):
cache = {}
for item_id in range(6_000_000): # cache everything, forever
cache[item_id] = "masala chai, 20 rupees"
print("cached", len(cache), "items")
Traceback (most recent call last):
File "main.py", line 3, in <module>
cache[item_id] = "masala chai, 20 rupees"
~~~~~^^^^^^^^^
MemoryError
Without the limit, on a machine with enough memory, the same program prints cached 6000000 items. Real servers have far more memory than 400 MB, but real caches can also hold far more than six million items: without a limit, they will fill it eventually.
The TypeError in full:
from functools import lru_cache
@lru_cache
def total(items):
return len(items)
total(["chai"])
Traceback (most recent call last):
File "main.py", line 7, in <module>
total(["chai"])
~~~~~^^^^^^^^^^
TypeError: unhashable type: 'list'
lru_cache uses your arguments as the dictionary key, and a list can change, so it can't be a key.
Misconceptions
- "The database is slow, so buy a bigger one." Often the real problem is asking it the same question again and again.
- "A cache always makes things fast." Only when it hits. At a 0% hit rate it just adds work; the hit rate decides how much it helps.
- "Cache everything." Memory is small and costly. Without a size limit, you get
MemoryError. - "A cache miss is an error." A miss is normal: ask the database and save the answer.
- "Cached data is always correct." A copy doesn't know when the original changes. Use a TTL, and invalidate when data changes.
- "LRU throws out the oldest item." It throws out the item used least recently. An old item you just used again stays.
Mini project: a cache with LRU, TTL and invalidation
A tiny cache class that combines the whole episode: hits and misses, a size limit with LRU eviction, a TTL, invalidation on a price change, and the hit rate. OrderedDict remembers the order of its keys; move_to_end marks an item as just used, and popitem(last=False) removes the least recently used one.
# a tiny cache with a size limit (LRU), a TTL, invalidation and hit/miss stats
from collections import OrderedDict
database = {"chai": 20, "samosa": 15, "vada pav": 25, "poha": 30}
class Cache:
def __init__(self, maxsize, ttl):
self.maxsize, self.ttl = maxsize, ttl
self.data = OrderedDict() # item -> (price, saved_at); least recently used first
self.hits = self.misses = 0
def get(self, item, now):
if item in self.data:
price, saved_at = self.data[item]
if now - saved_at < self.ttl:
self.hits += 1
self.data.move_to_end(item) # just used: now the most recent
return price, "hit"
self.misses += 1
note = "miss"
self.data[item] = (database[item], now) # missing or expired: refresh
self.data.move_to_end(item)
if len(self.data) > self.maxsize:
evicted, _ = self.data.popitem(last=False) # drop the least recently used
note += f", evicted {evicted}"
return self.data[item][0], note
def invalidate(self, item):
self.data.pop(item, None)
cache = Cache(maxsize=3, ttl=60)
orders = ["chai", "samosa", "chai", "vada pav", "chai", "poha", "chai", "samosa"]
for now, item in enumerate(orders):
price, note = cache.get(item, now)
print(f"t={now:<3} {item:<9} {price} {note}")
database["chai"] = 25 # the owner raises the price...
cache.invalidate("chai") # ...and throws out the old copy
price, note = cache.get("chai", 8)
print(f"t=8 chai {price} {note}")
price, note = cache.get("chai", 80) # 72 seconds old: past the TTL
print(f"t=80 chai {price} {note}")
total = cache.hits + cache.misses
print(f"hits {cache.hits}, misses {cache.misses}, hit rate {cache.hits / total:.0%}")
Output:
t=0 chai 20 miss
t=1 samosa 15 miss
t=2 chai 20 hit
t=3 vada pav 25 miss
t=4 chai 20 hit
t=5 poha 30 miss, evicted samosa
t=6 chai 20 hit
t=7 samosa 15 miss, evicted vada pav
t=8 chai 25 miss
t=80 chai 25 miss
hits 3, misses 7, hit rate 30%
- Chai is ordered often, so it keeps being "recently used" and is never evicted. Samosa and vada pav, used less, are evicted in turn.
- At t=8 the price changed and we invalidated chai, so the customer gets the fresh price 25 straight away (no waiting for the TTL).
- At t=80 chai's copy is 72 seconds old, past the 60-second TTL, so it's refreshed.
- Only 10 requests and 4 different items, so the hit rate is low. With many users asking for a few popular items, it climbs.
Practice
- In Demo 4 (LRU), change
maxsizeto 2. Predict the number of misses, then run it. - In Demo 2, make each user ask for both masala chai and samosa. How many database queries now?
- In Demo 6, set
TTL = 20. What prints att=30? - With
CACHE_MS = 1andDB_MS = 50, what is the average time at an 80% and a 95% hit rate? - Fix Demo 5 with invalidation: add a
set_pricefunction that updates the database and throws out the cached copy. - What would you never cache, or cache only for a very short time? Why?
Solutions and hints
1. Prediction: with room for only 2, chai is evicted by vada pav before it comes back, so there are no hits at all: 6 misses.
from functools import lru_cache
PRICES = {"chai": 20, "samosa": 15, "vada pav": 25, "poha": 30}
@lru_cache(maxsize=2) # keep only the 2 most recently used
def get_price(item):
print(f" database query for {item}")
return PRICES[item]
for item in ["chai", "samosa", "vada pav", "chai", "poha", "samosa"]:
print(item, "->", get_price(item))
print(get_price.cache_info())
database query for chai
chai -> 20
database query for samosa
samosa -> 15
database query for vada pav
vada pav -> 25
database query for chai
chai -> 20
database query for poha
poha -> 30
database query for samosa
samosa -> 15
CacheInfo(hits=0, misses=6, maxsize=2, currsize=2)
One slot less, and the hit rate drops from 1 in 6 to zero. Size matters.
2. Add get_price("samosa") inside the loop:
import time
def db_get_price(item): # the database: about 50 ms per query
time.sleep(0.05)
return {"masala chai": 20, "samosa": 15}[item]
cache = {}
hits = misses = 0
def get_price(item):
global hits, misses
if item in cache: # cache hit: answer from memory
hits += 1
return cache[item]
misses += 1 # cache miss: ask the database once
cache[item] = db_get_price(item)
return cache[item]
start = time.perf_counter()
for user in range(40):
get_price("masala chai")
get_price("samosa")
total = (time.perf_counter() - start) * 1000
print(f"80 requests -> {misses} database queries, {total:.0f} ms")
print(f"hits: {hits}, misses: {misses}")
Output (timing varies slightly):
80 requests -> 2 database queries, 100 ms
hits: 78, misses: 2
One miss per different item, then hits.
3. Change the line to TTL = 20 # seconds a cached price stays valid:
t=0 (20, 'miss')
t=30 (25, 'miss')
t=61 (25, 'miss')
At t=30 the copy is 30 seconds old, past the 20-second TTL, so it's refreshed and shows the new price 25. Fresher data, but more misses (now every request is a miss).
4.
CACHE_MS, DB_MS = 1, 50
for hit_rate in [0.8, 0.95]:
avg = hit_rate * CACHE_MS + (1 - hit_rate) * DB_MS
print(f"hit rate {hit_rate:>4.0%} -> average {avg:5.2f} ms")
hit rate 80% -> average 10.80 ms
hit rate 95% -> average 3.45 ms
5.
database = {"masala chai": 20}
cache = {}
def get_price(item):
if item not in cache:
cache[item] = database[item]
return cache[item]
def set_price(item, price):
database[item] = price
cache.pop(item, None) # invalidate: throw the old copy away
print("price:", get_price("masala chai"))
set_price("masala chai", 25) # the owner raises the price
print("price:", get_price("masala chai"), "<- fresh")
price: 20
price: 25 <- fresh
The next read is a miss, so it fetches the new price. The catch: every place that changes the data must remember to invalidate. That is why cache invalidation is called hard.
6. Good answers: data that must always be exactly right at this moment, like a bank balance or how many train seats are left (stale = a real bug); data that is different for every request, so it would never hit; secrets, like passwords. Explain the trade-off between freshness and hit rate.
Quick quiz
An LRU cache with maxsize = 2:
get("chai")
get("samosa")
get("chai")
get("poha") # cache is full
# Which item is evicted?
- A. chai
- B. samosa
- C. poha
- D. Nothing
Answer
B, samosa. Chai was used most recently, so samosa is the least recently used item and makes room for poha.
Interview questions
- What is a cache? What is a cache hit, and a cache miss?
- Why is reading from memory so much faster than from an SSD, a disk, or another machine? Roughly how much faster?
- What is the hit rate, and how does it change the average response time? (Work it out: 90% vs 99% with 1 ms cache and 50 ms database.)
- Why does a cache need a size limit? What is eviction? Explain LRU.
- What is stale data? How do TTL and invalidation fight it? What is the trade-off of a short TTL?
- Where do caches live in a typical system? (Browser, CDN, app server memory, a shared cache like Redis, the database, the CPU.)
- What kinds of data should you not cache, or cache only briefly?
Glossary
| Term | Meaning |
|---|---|
| Database | A program that stores data safely and answers questions (queries) about it |
| Query | One question asked to a database, like "price of masala chai?" |
| Bottleneck | The one slowest part that limits the whole system |
| Cache | A saved copy of an answer, kept close and fast, so you don't redo the work |
| Cache hit | The answer was found in the cache |
| Cache miss | The answer wasn't in the cache, so you ask the real source and usually save it |
| Hit rate / miss rate | The share of requests that are hits / misses (they add up to 100%) |
| Latency | Time for one request or one fetch (episode 4) |
| ns / µs / ms | Nanosecond (a billionth of a second) / microsecond (a millionth) / millisecond (a thousandth) |
| RAM (main memory) | Fast, temporary storage the computer works from; emptied when power goes |
| SSD | A storage drive with no moving parts; much faster than a spinning disk, much slower than RAM |
| Spinning disk / disk seek | An older drive with a rotating platter / the time to move its arm to the right spot |
| L1 cache | The tiny, fastest memory inside the CPU itself |
| Data centre | A building full of servers |
| Round trip | A message going to another machine and the reply coming back |
| Redis | An open-source, in-memory data store, used as a database, cache or message broker |
| Shared cache | One cache that all your servers use at once, like Redis |
| CDN (content delivery network) | Copies of files kept in cities near users (its own episode later) |
| Browser cache | Files your browser keeps so it doesn't download them again |
| Hot rows | Database rows that are used very often, so the database keeps them in RAM |
Size limit / maxsize |
The most items a cache may hold |
| Eviction | Removing an item from a full cache to make room |
| LRU (least recently used) | An eviction rule: remove the item that hasn't been used for the longest time |
functools.lru_cache |
Python's built-in LRU cache for a function's results; default maxsize is 128 |
Decorator (@...) |
A line above a function that wraps it with extra behaviour, like caching |
cache_info() |
Shows an lru_cache's hits, misses, maxsize and current size (currsize) |
| Stale data | A cached copy that no longer matches the real data |
| TTL (time to live) | How long a cached copy stays valid before it expires |
| Expire | When a cached copy becomes too old to use and must be fetched again |
| Invalidation | Deleting a cached copy on purpose because the real data changed |
| Hashable | A value that can be a dictionary key because it can't change (a tuple yes, a list no) |
| Tuple | Like a list, but it can't be changed after it's made: ("chai",) |
MemoryError |
Python's error when it can't get more memory |
TypeError / KeyError |
Python errors for a wrong type (e.g. a list as a key) / a dictionary key that isn't there |
ulimit -v |
A Linux shell command that limits how much memory a program may use (in KB) |
OrderedDict |
A dictionary that remembers the order of its keys; move_to_end and popitem(last=False) make LRU easy |
time.sleep / time.perf_counter |
Pause the program / a precise clock for measuring elapsed time |
global |
Lets a function change a variable defined outside it |
Summary
- When everyone asks the same question, the database becomes the bottleneck. Don't ask it again: keep a copy close.
- A cache is a saved copy of an answer. A hit is found in the cache; a miss asks the database and saves the answer. 40 queries (~2 s) became 1 query (~50 ms).
- It's fast because memory is fast and close: RAM ~100 ns vs SSD ~150 µs vs disk seek ~10 ms.
- The hit rate decides how much a cache helps: 90% → ~5.9 ms, 99% → ~1.5 ms.
- A cache needs a size limit; when full, evict the least recently used item (LRU).
- Copies go stale. A TTL limits how stale they can get; invalidation throws a copy out the moment the data changes.
Next episode: today our cache filled itself on a miss. But when you write new data, who updates the cache, and when? Cache strategies: cache-aside, write-through, write-back, and what happens when a popular item expires.