Handbooks / System Design / Chapter 2

Caching

7 pages · ~5 min✓ Reviewed

Builds on Scalability and Load Balancing. Next up: Databases, Replication and Sharding.

System DesignPage 1

Cache Layers Mental Model

1. What a Cache Is

Cache = small fast copy of slow data
Hit: skips the origin. Miss: full cost, then fills the cache
Hit ratio = hits / (hits + misses)

2. Layers Outward to Inward

Clientbrowser
CDNedge
Applocal or Redis
Databasebuffer pool

Layer	Controlled by	Note
Client	`Cache-Control`, `ETag`	closest to user
CDN	`s-maxage`, `Vary`	static/public; cuts latency, origin load
App: in-process	local memory	fast, per-instance, inconsistent
App: Redis/Memcached	shared cache	shared, one network hop
Database	buffer pool, query cache	last line of defense

3. Client Headers

text

Cache-Control: max-age=60
Cache-Control: private, no-store
ETag: "v7"  ->  If-None-Match: "v7"
HTTP/1.1 304 Not Modified

revalidation: 304 means reuse your copy

no-store: never cache. no-cache: cache, but revalidate first
private: browser only, not shared caches

Remember

Each layer outward is faster but staler

System DesignPage 2

Read and Write Caching Patterns

1. Read path: cache-aside

Cache-aside (lazy loading): the app owns the logic
Read cache, on miss read DB, then write cache
Only requested data is cached
Most common pattern

python

def get(k):
    v = cache.get(k)
    if v is None:
        v = db.get(k)
        cache.set(k, v, ttl=300)
    return v

pseudo-code: miss fills the cache

2. Write patterns

Pattern	Write goes to	Trade-off
Write-through	cache + DB, synchronously	Never stale for written keys; slower writes; may cache unread data
Write-back	cache; DB flushed async in batches	Fastest writes; data lost if cache dies before flush
Write-around	DB only, skips cache	No pollution from write-once data; next read is a miss

Writeapp
Cacheacked at once
Batch flushasync
DBloss window

Pick

Read-heavy default: cache-aside. Consistency: write-through. Write throughput: write-back, accepting loss risk.

System DesignPage 3

Eviction Policies

1. When and Who

Eviction runs when the cache is full to free space
The policy decides the victim

2. LRU, LFU, TTL

Policy	Evicts	Weak spot
LRU	least recently used	scan of one-off keys
LFU	least frequently used	old once-popular keys
TTL	expired entries	ignores free space

LRU: O(1) with hash map + doubly linked list
LRU: default for recency-skewed workloads
LFU: protects hot keys, needs frequency aging
TTL: bounds staleness, so combine with LRU/LFU

3. Redis Example

text

maxmemory 2gb
maxmemory-policy allkeys-lru

Policy	Behaviour when full
`allkeys-lru`	evicts any key, LRU first
`volatile-*`	evicts only keys with a TTL
`noeviction`	writes return errors

TTL is not a space policy

A TTL alone does not free space when the cache fills. Pair it with LRU or LFU.

System DesignPage 4

Invalidation Strategies

1. What Invalidation Is

Invalidation = deciding when a cached copy is no longer valid
The hardest part of caching
TTL expiry: simplest, tolerates bounded staleness
Pick the TTL from how stale the data may be

2. Delete on Write

DB update
cache.delete
Next read misses
Refill

python

db.update(key, value)
cache.delete(key)

delete, do not set

Prefer delete over set
Racing writers can leave a stale value behind with set

3. Versions and CDN Purge

Method	How	Best for
Versioned key or URL	`user:42:v7`, `app.3f9a.js`: new version = new key, no purge	CDN, client assets
CDN purge	By URL or tag / surrogate key	Dynamic content

Purge is not instant

Propagation takes time. Pair a purge with a short s-maxage for dynamic content.

System DesignPage 5

Thundering Herd and Common Mistakes

1. Cache Stampede

1Hot key expires
2Many requests miss
3All hit the DB
4DB overloaded

2. Fixes and Penetration

Request coalescing: per-key lock or single-flight, one rebuilds, others wait or serve stale
TTL jitter spreads expiry so keys do not die together: ttl = base + random
Also pre-warm or refresh early, before expiry

python

import random
ttl = 300 + random.randint(0, 60)
cache.set(k, v, ttl=ttl)

call-site fragment: 300 to 360 s

Penetration: repeated misses for keys that do not exist bypass the cache
Fix: cache a null with a short TTL
Or put a Bloom filter in front to reject unknown keys

3. Common Mistakes

Mistake	Consequence	Fix
No TTL or size limit	Stale data, memory grows forever	TTL plus eviction limit
Per-user data in shared CDN	One user sees another's data	`private` or `Vary`

Remember

Every key needs a TTL (with jitter) and every cache needs a size limit.

System DesignPage 6

Caching Cheat Sheet

1. Layers and Write Patterns

Clientbrowser
CDNedge
Applocal or Redis
Databasebuffer pool

Cache as close to the user as correctness allows
Each layer outward is faster but staler

Pattern	Pick for	Catch
Cache-aside	read-heavy default	first read misses
Write-through	consistency	slower writes
Write-back	write throughput	loss if cache dies

2. Eviction and Invalidation

Need	Pick
Eviction	LRU default; LFU for stable hot sets
Bound staleness	TTL always
Dynamic data	TTL plus delete on write
Static assets	version keys, `app.3f9a.js`

3. Stampede Defense

Single-flight lock: one request rebuilds, others wait
TTL jitter: base plus random, no shared expiry
Serve stale while revalidating
Null caching for missing keys, short TTL

Delete, do not set

After the DB update, delete the key. A set can race and store a stale value.

System DesignPage 7

Check yourself

Writers A and B update key k. Order: A writes DB, B writes DB, B sets cache, A sets cache. What do DB and cache hold?

DB holds B's value, cache holds A's, so it is stale until the TTL.
Fix: delete the key after the DB write; the next read refills it.

5,000 hot keys are cached at startup with ttl=300. What happens at 300 s?

All expire together, so the misses hit the DB at once: a stampede.
Fix: TTL jitter (base + random) and a single-flight lock per key.

Redis is full with volatile-lru, but no key has a TTL. What does a write do?

It fails with an error.
volatile-* evicts only keys with a TTL, so there is no victim, same as noeviction.

Cache-aside looks up user -1, which is not in the DB. Why does every request hit the DB?

Nothing is found, so nothing is cached and each request misses.
Fix: cache a null with a short TTL, or use a Bloom filter.