Caching

  • Lesson 7 of 40
  • 14 min
  • Beginner
  • 13 steps

If your database answers the same question a thousand times a day, keep the answer in memory. Quick to set up, tricky to keep up to date.

p95 latency
25 ms
Hit rate
95%
DB usage
6%
20,000 usersApp serverApp serverCachein memoryCacheDatabase90 %p95 ≈ 450 ms90 %the same rows, nonstopWhat gets read (example)1 % of products~50 % of reads10 % of products~85 % of readsthe rest~15 %hit ≈ 1 msmiss: read and store a copy20 %6 %Average read timehit≈ 1 msdatabase≈ 20 ms80 % hits0.8×1 + 0.2×20 = 4.8 ms95 % hits0.95×1 + 0.05×20 ≈ 2 msprice: 59price: 49 · stalecustomers see 49price: 59key deleted · TTL 60 scustomers see 59memory fullLRU: unused the longestproduct:182 s agoproduct:3059 s agoproduct:775 min agoproduct:40214 h ago · leaveshome page · expired2000 identical queries100 %home page refreshed early1 read per key6 %nothing to store0 rows found95 %"not found" · TTL 30 s6 %Bloom filter (10M IDs ≈ 12 MB)does product:90000001 exist?"definitely not"404, no queries"maybe"cache, then DBfalse positives≈ 1 %6 %Where a read can stopbrowser≈ 0 msone per userCDN~10–30 msclose to the userprocess memory≈ 0 msone per servershared cache≈ 1 msall serversdatabase≈ 20 msthe sourcerough timingshit ≈ 1 ms6 %
  • request
  • response
  • cache miss
  • waiting in queue

Step 1 of 13

Problem

Every read reaches the database

Your online shop is growing. Whenever someone opens a product page, the server asks the database the same thing: name, price, images. The database is already 90 % busy.

Queries start waiting their turn and p95 climbs to about 450 ms. The figures in this lesson are an example scenario.

Step 2 of 13

Concept

The same rows, over and over

Look at what is being queried and you will see a few popular products take most of the reads. The database repeats the same work thousands of times a minute.

Data that is read often and changes rarely is the ideal candidate for keeping a copy somewhere faster.

Step 3 of 13

Solution

An in-memory cache in front of the database

Put an in-memory key-value store next to the server. Before going to the database, the server looks there: if it finds the key (a hit), it answers in about 1 ms.

If the key is missing (a miss), it reads the database, answers, and stores a copy in the cache for next time. That flow is called cache-aside.

What changed

  • In-memory cache
  • 8 out of 10 reads come from the cache
  • DB usage: 90 % → 20 %

Step 4 of 13

Technique

It all depends on the hit rate

The hit rate is the share of reads the cache resolves. Since a miss costs about 20 times more than a hit, a few points change the outcome a lot.

Going from 80 % to 95 %, the average read time drops from 4.8 ms to about 2 ms, and the database gets 5 reads out of 100 instead of 20: a quarter.

What changed

  • Hits: 80 % → 95 %
  • DB usage: 20 % → 6 %

Step 5 of 13

Problem

The price changes, the cache never hears about it

Someone on the team raises a product from 49 to 59. The database already holds 59, but the cache keeps its copy with 49, and that is what customers keep seeing.

A cache is a second copy of the data. The hard part is not storing it but keeping it from falling behind.

What changed

  • Database: price 49 → 59
  • The cache still says 49

Step 6 of 13

Solution

Delete on write and set an expiry date

When data changes, the server writes it to the database and then deletes the key from the cache. The next read misses and brings back the new value.

In case that delete ever fails, every entry carries a TTL (time to live): after that period it disappears on its own. With 60 s, stale data lasts one minute at most.

Why delete instead of overwriting? If two writes cross, the slower one can leave the old value in the cache. Deleting has no such risk: the next read loads whatever is in the database.

What changed

  • Every write deletes its key
  • 60 s TTL
  • Customers see 59

Step 7 of 13

Trade-off

Memory cannot hold everything

Memory costs more than disk, so the cache has a fixed size. When it is full, something has to leave to make room for new entries.

The most common policy is LRU: the entry that has gone unused the longest leaves. Popular items stay and rare ones rotate.

The LFU alternative removes the entry read the fewest times. It copes better with a burst of one-off reads that, under LRU, could push out the long-time favourites.

What changed

  • Cache full
  • The longest-unused entry leaves
  • Hits: 94 % → 93 %

Step 8 of 13

Problem

The most requested key expires

The shop home page is the star key: about 2000 reads per second, close to 40 % of all of them. Its TTL runs out and, at that instant, all those reads miss at once.

Each one goes to the database to compute exactly the same answer. The database jumps from 6 % to 100 % and p95 shoots up. This is a cache stampede (*thundering herd*).

What changed

  • The home page key expires
  • 2000 identical misses at once
  • Hits: 95 % → 55 %

Step 9 of 13

Solution

A single trip to the database

Group the requests (request coalescing): the first miss takes a short lock and queries the database; the rest wait a few milliseconds and get that same result.

Add two habits: refresh hot keys a little before they expire, and add random variation (jitter) to the TTL so many keys do not expire together.

What changed

  • One read per expired key
  • Early refresh and TTL jitter
  • DB usage: 100 % → 6 %

Step 10 of 13

Problem

Lookups for things that do not exist

A bot crawls the shop making up IDs: product 90000001, 90000002, 90000003… None is in the cache, all go to the database and none returns rows, so there is nothing to store.

In this example the bot sends as many requests as all customers combined. The cache stops none of them: the database goes from 6 % to 95 %. This is called cache penetration.

What changed

  • Requests for made-up IDs
  • Hits: 95 % → 48 %
  • DB usage: 6 % → 95 %

Step 11 of 13

Solution

Store the "does not exist" too

First defence: negative caching. Store the "not found" answer with a short TTL, for example 30 s. If someone repeats the same fake ID, the cache answers.

But the bot never repeats itself. For that, the server keeps a Bloom filter in memory with every real ID: a bit structure that answers "definitely not there" or "may be there". Whatever definitely does not exist gets a 404 without touching the cache or the database.

What changed

  • "Not found" cached with a 30 s TTL
  • Bloom filter in front of the cache
  • DB usage: 95 % → 6 %

Step 12 of 13

Concept

There are caches all along the way

The cache you set up is one of several. A read can be resolved in the browser, in a CDN, in the process memory itself, in a shared cache or in the database memory.

The closer the copy is to the user, the faster and cheaper the answer, and the harder it is to invalidate when the data changes.

Step 13 of 13

Summary

Summary

Cache what is read often and changes rarely.

Cache-aside: look in the cache; on a miss, read the database and store the copy.

The hit rate decides the speed and the load that reaches the database.

Assume there will be stale data: delete on write, set a TTL and evict with LRU or LFU.

Protect hot keys: a single read, early refresh and TTL jitter.

Store the "does not exist" and filter impossible IDs with a Bloom filter.

You will learn

  • Spot repeated reads worth caching
  • Apply the cache-aside pattern
  • Work out the effect of the hit rate
  • Invalidate, expire with a TTL and evict entries
  • Prevent stampedes on the most requested keys
  • Stop lookups for keys that do not exist
  • Place the cache layers between user and data