Specialty · System designLesson 2 of 5Free to read

Caching · System Design

How do you make a slow database feel fast?

Why you need it

Reading from memory is far faster than asking a database over the network, and most apps read the same popular things again and again. A cache keeps recent answers close at hand. It's the single most common speed-up in system design, and also a classic source of bugs: show a stale price once and users notice.

The intuition

Cache-aside, the usual pattern:

look in the cache; if it's there, that's a hit, return it
otherwise it's a miss: read the database, put the answer in the cache, return it

The hit rate (hits / lookups) tells you how much the cache helps.

Memory is limited, so when the cache is full something must go. LRU (least recently used) evicts the item that hasn't been touched for the longest time, betting that recent items will be wanted again. In Python an OrderedDict does this neatly: move_to_end(key) on every use, popitem(last=False) to drop the oldest.

Data changes, so the cache can go stale:

on a write, delete the cached copy so the next read fetches the new value
and give entries a TTL (time to live) so anything you missed expires anyway

Definition

Cache

A fast, small store of recent answers placed in front of a slower one.

Hit rate

The share of lookups answered by the cache.

LRU eviction

When full, remove the item used least recently.

Invalidation

Removing or updating cached data after the source changes.

Examples

Cache-aside

Try it yourself

Five lookups, only two trips to the database.

db = {1: 20, 2: 35}
cache = {}
db_reads = 0

def get_price(item):
    global db_reads
    if item in cache:
        return cache[item]
    db_reads += 1
    cache[item] = db[item]
    return cache[item]

for item in [1, 1, 2, 1, 2]:
    get_price(item)
print("database reads:", db_reads)
print("hit rate:", (5 - db_reads) / 5)

Output

database reads: 2
hit rate: 0.6

Step by step

L7A hit: no database work at all.
L9A miss: count the trip to the database.
L10Keep the answer for next time.
L163 of the 5 lookups were hits.hit rate: 0.6

LRU with OrderedDict

Try it yourself

Capacity 2: using a key protects it; the stale one is evicted.

from collections import OrderedDict

cache = OrderedDict()
cache["a"] = 1
cache["b"] = 2
cache.move_to_end("a")
cache["c"] = 3
if len(cache) > 2:
    cache.popitem(last=False)
print(list(cache))

Output

['a', 'c']

Step by step

L6a was just used, so it moves to the newest end. The order is now b, a.
L9Over capacity: drop from the oldest end, which is b.
L10a survived because it was used recently.['a', 'c']

Common mistakes

Never invalidating

If writes don't touch the cache, readers see old data until restart. Delete the cached copy on every write.

Caching everything forever

Without a size limit and TTL the cache grows until memory runs out. Bound it and let entries expire.

A stampede on a popular key

When a hot entry expires, thousands of requests miss at once and all hit the database. Let one request refill it while others wait or use the old value.

Quick quiz

1. What does this print?

from collections import OrderedDict

cache = OrderedDict()
for key in ["x", "y", "x", "z"]:
    if key in cache:
        cache.move_to_end(key)
    else:
        cache[key] = True
        if len(cache) > 2:
            cache.popitem(last=False)
print(list(cache))

A
```
['x', 'z']
```
B
```
['y', 'z']
```
C
```
['x', 'y']
```

Show the answer

Answer: A

After using x again the order is y, x; adding z evicts y.

2. A price changes in the database, but the site keeps showing the old one. What's the most likely fix?

ADelete the cached copy whenever the price is written
BMake the cache bigger
CRead from the cache twice

Show the answer

Answer: A

The cache was never invalidated, so it still holds the old value.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictHits and misses
Type exactly what this prints.
ModifyThe stale price
set_price updates the database but leaves the old price in the cache, so get_price keeps returning it. Make set_price invalidate the cached copy.
WriteSimulate an LRU cache
Write lru_hits(capacity, requests) that returns how many of the requests are cache hits, for an LRU cache that holds capacity keys and starts empty.
```
lru_hits(2, ["a", "b", "a", "c", "b", "a"])   # 1
lru_hits(3, ["a", "b", "a", "c", "b", "a"])   # 3
```

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Cache	缓存	A fast store of recent answers in front of a slower one.
Hit rate	命中率	Hits divided by lookups.
LRU	最近最少使用	Evict the least recently used item first.
TTL	存活时间	How long a cached entry stays valid.