Caching

A cache keeps a copy of data somewhere faster so the slow place is asked less often. It is the cheapest big win in most read-heavy designs, and the source of some of the worst outages.

Crux: cache what is read often and changes rarely, say exactly how it stays fresh, and make sure the system survives when the cache is empty.

Why a cache helps

Two gains, and it is worth saying both.

• Speed. Memory is far faster than a network call to a database (see the latency figure in the estimation lesson).
• Less load. Every hit is a query the database never sees.

Arithmetic with the link shortener (all inputs are assumptions): peak is 12,000 reads per second. A hit costs 1 ms, a miss costs 1 ms for the failed lookup plus 10 ms at the database.

hit rate 90%:  database sees 12,000 × 0.10 = 1,200 reads/s
               average = 0.9×1 + 0.1×11 = 2.0 ms
hit rate 99%:  database sees 12,000 × 0.01 =   120 reads/s
               average = 0.99×1 + 0.01×11 = 1.1 ms

Going from 90% to 99% cuts database load by ten times. The hit rate is the number that matters, so always ask what yours will be.

A cache works because access is skewed: a small part of the data gets most of the reads. If every item is read once, a cache does nothing but add a hop.

Where caches live

Cache at several levels. Each is closer to the user and harder to control.

• Browser and client. Free and fastest, but you cannot reach in to remove a stale entry. Controlled by response headers (Cache-Control).
• CDN. Copies near the user. Good for static files and for responses that are the same for everyone.
• In-process (local) cache. A map inside each app server. No network hop, but each server holds its own copy, so copies disagree and memory is multiplied by the server count.
• In-process (local) cache, when it fits. Best for a small set of hot values that rarely change (feature flags, a currency table, config). Not a substitute for a shared cache: with ten servers you hold ten copies that update at different moments.
• Distributed cache. A shared service such as Redis or Memcached. One copy, one network hop (about half a millisecond in a datacenter), shared by all servers.
• The database's own cache. The engine already keeps hot pages in memory. A bigger machine with more memory is a cache you did not have to write.

Default for a product design: a distributed cache between the app servers and the database, plus a CDN for static media.

Read strategies

Cache-aside (lazy loading) is the default. The app owns the logic.

• Only data that is asked for gets cached, so memory is not wasted.
• A cache failure does not stop reads: they fall through to the database, slower.
• The first read of anything is a miss, and the cache can hold old data until it expires.

Read-through puts the same logic inside the cache layer: the app asks the cache, and the cache fetches from the database on a miss. Cleaner for the app, but it needs a cache product that supports it.

Write strategies

• Write-through. Write to the cache and the database together, and acknowledge when both are done. The cache is always fresh. Writes are slower, and you may cache data nobody reads. It also has a dual-write problem: two systems are updated one after the other, so a crash between them leaves them disagreeing. Many caches (Redis among them, as far as we know, but check the version) do not write to your database for you, so write-through means your own code or a layer in front doing both.
• Write-around. Write only to the database. The cache fills on the next read. Good when data is written often and read rarely. The first read after a write is a miss.
• Write-back (write-behind). Write to the cache and acknowledge at once. Flush to the database later, in batches. It has the fastest writes. If the cache dies before the flush, the data is lost, so use it only where loss is acceptable (a view counter, say) or the cache is itself durable.

For most read-heavy designs: cache-aside for reads and delete the entry on write.

Eviction and freshness

Memory is finite, so entries must leave.

• LRU (least recently used) removes what has gone unread the longest. A good default.
• LFU (least frequently used) removes what is read least often. Better when a few items stay popular for a long time.
• FIFO removes the oldest entry, ignoring use. Simple, rarely best.
• TTL (time to live) removes an entry after a fixed time. It also bounds how stale a value can be, and that is its main job.

Staleness is the real difficulty. Three ways to keep a cache honest, from simplest:

• Expire by TTL. Accept data that is up to N seconds old. Say what N is and why that is fine.
• Delete on write. When the source changes, delete the cache key. The next read refills it.
• Version the key (user:7:v12). A new version is a new key, so old entries just age out.

A subtle race: a reader misses, reads the old value from the database, a writer updates the database and deletes the key, then the reader stores the old value. The cache now holds stale data until the TTL. A TTL is your safety net for exactly this case, so always set one.

Failure modes

• Stampede (thundering herd). A hot key expires and thousands of requests miss at once, all hitting the database. Remedies: let one request refill while the others wait (a lock or request coalescing), refresh early before the TTL ends, and add jitter (random extra seconds) to TTLs so keys do not all expire together.
• Hot key. One key gets so much traffic that its cache node is the bottleneck. Remedies: a short-lived in-process copy in front, several copies of the key under different names (reads pick one at random), cache replicas for that key, or rate limiting the key as a last resort.
• Cache penetration. Requests for keys that do not exist always miss and always hit the database. Remedy: cache the "not found" answer for a short time, or put a Bloom filter (a compact set that can say "definitely absent") in front.
• Cold start and cache loss. An empty cache sends the whole load to the database at once. Size the database for the miss load, warm the cache before taking traffic, or add replicas of the cache.
• Cache down. Reads fall through to the database. If it cannot take that, add a circuit breaker or shed load rather than letting every request wait on a dead cache, and run the cache with replicas.
• Cache as the only copy. Never. It is a copy, and the source of truth must be somewhere else.

Sizing: how much to cache

Use the numbers from earlier. Assume (from the estimation lesson) 1.2 billion links a year at about 200 B per record, so 240 GB a year.

Everything:      1.2 B × 200 B = 240 GB
Hot 20% (assume): 240 GB × 0.20 = 48 GB

Caching only the hot fifth takes about 48 GB, which fits in the memory of one large machine or a few small cache nodes. If a cache entry carries 2× overhead for keys and bookkeeping (an assumption: check your cache), plan for about 100 GB. Compare that with the 12,000 reads per second at peak: a single Redis node is commonly said to handle on the order of 100,000 simple operations per second (a rough figure, see the numbers lesson), so memory, not throughput, sets the size.

When and how to bring a cache into a design

Add one only after you can name a problem: reads far above writes, an expensive query, a database near its CPU limit, or a latency target the database cannot meet. Show the numbers first.

• 1. Name the bottleneck (12,000 reads per second against a database that handles about 2,000, as an assumption).
• 2. Choose what to cache: the key, the value, the size, and how long it may be stale.
• 3. Pick the pattern: cache-aside with a distributed cache unless a reason says otherwise.
• 4. Set eviction and TTL.
• 5. Answer the downsides: how it is kept fresh, what happens when it is empty or down, and what stops a stampede.

Pick the one or two problems that apply and say them well. Reciting all of them shows a list, not judgement.

Common mistakes

• "I'll add a cache" with no statement of what is cached, the key, the TTL or the hit rate.
• Caching data that is read once.
• No TTL, so a missed delete is stale forever.
• Caching user-specific data under a shared key, which leaks one user's data to another. Include the user in the key, or do not cache it.
• Designing for the warm cache and not the cold one.
• Using write-back for data you cannot afford to lose.
• Caching without first showing a real bottleneck, or caching data that is cheap to fetch or changes constantly.
• Treating an in-process cache as if it were shared.
• Expecting cache warming to stop a stampede when keys are deleted on every write (a deleted key is cold again).
• Writing through to cache and database with no plan for the crash between them.

Check yourself

• What does a 99% hit rate do to database load compared with 90%?
• Name three levels where a cache can live and one weakness of each.
• Why is cache-aside the default, and what does it do when the cache is down?
• When is write-back acceptable, and when is it not?
• What is a stampede, and what are two ways to prevent it?
• Why must every cache entry have a TTL, even if you delete on write?