Imagine the home page of a shopping site shows the same "Top 20 deals" to every visitor. Ten thousand people open it every second. Should the server run the same heavy database query ten thousand times a second, producing the same answer each time? Obviously not. It should compute the answer once, keep it somewhere fast, and hand out that saved copy.
That is caching, and it is the single most effective performance technique in system design. In Back-of-the-Envelope Estimation we saw that reading from memory is roughly 100 to 1,000 times faster than an SSD random read and that most real systems are read-heavy. In Content Delivery Networks (CDN) we saw one kind of cache at the network edge. In this chapter we look at caching in general: where caches live, how to measure them, how big a difference they make, and the classic problems they bring.
A cache is a small, fast storage layer that keeps copies of data that are expensive to fetch or compute, so that future requests for the same data can be served faster.
┌─────────────┐ hit (fast, ~1 ms)
Request ───→ │ Cache │ ─────────────────────→ Response
└─────┬───────┘
│ miss
▼
┌─────────────┐ slow (~20-100 ms)
│ Database │ ───→ result is stored in the cache, then returned
└─────────────┘
Why Caching Works
A cache is small, yet it answers most requests. That only works because real-world access patterns are far from uniform.
Temporal locality: data used recently is likely to be used again soon (a trending video, a logged-in user's profile).
Skewed popularity: a small fraction of items gets most of the traffic. This is often called the 80/20 rule (about 20% of items get about 80% of requests). Many real workloads are even more skewed.
Read-heavy workloads: data is written once and read many times, so one expensive computation can serve thousands of reads.
If every request asked for a different, random item, a cache would barely help. Caching is a bet on popularity and repetition, and on most systems that bet pays off handsomely.
Where Caches Live
Caches exist at almost every layer between the user and the disk. A single page load may pass through several.
Layer | Example | What it stores |
|---|---|---|
Client (browser / app) | Browser HTTP cache, mobile app storage | Images, scripts, API responses for one user |
CDN / edge | Edge servers in PoPs | Static files and public responses |
Reverse proxy / gateway | Nginx, Varnish, API gateway cache | Whole HTTP responses |
Application (in-process) | A hash map inside the server, Caffeine (Java), | Hot objects, config, computed results |
Distributed cache | Redis, Memcached, Valkey | Shared objects, sessions, counters, query results |
Database | Buffer pool (InnoDB), shared buffers (PostgreSQL) | Recently used data and index pages in RAM |
Operating system | Page cache | Recently read file blocks |
Hardware | CPU L1/L2/L3 caches | Recently used memory lines |
In system design interviews, "add a cache" usually means a distributed cache like Redis between the application servers and the database, but it is good to mention the other layers too.
Measuring a Cache: Hit Ratio and Effective Time
Hit ratio (h) = cache hits ÷ total requests. Miss ratio = 1 − h.
The average time per request, called the effective access time, depends on the hit ratio. If a miss first checks the cache and then goes to the database:
Effective time = h × T_cache + (1 − h) × (T_cache + T_db)
= T_cache + (1 − h) × T_db
(Some textbook and GATE problems assume the cache and the slow store are accessed in parallel, so a miss costs only T_db. Read the question to see which model it uses.)
Worked example. Cache lookup = 1 ms, database query = 20 ms.
No cache : 20 ms
h = 90% : 1 + 0.10 × 20 = 3.0 ms
h = 99% : 1 + 0.01 × 20 = 1.2 ms
What h gives an average of 1.5 ms?
1 + (1 − h) × 20 = 1.5 → (1 − h) = 0.025 → h = 97.5%
Now look at the database load, which is often more important than latency. With 10,000 requests per second:
h = 90% → misses = 10,000 × 0.10 = 1,000 queries/s reach the database
h = 99% → misses = 10,000 × 0.01 = 100 queries/s reach the database
Think in misses, not hits. Moving from 90% to 99% hit ratio sounds like a 9% improvement, but it cuts database traffic by 10 times.
This also means a cache quietly becomes load-bearing. If the database is sized for 100 queries/s because the cache absorbs the rest, then a cache failure sends 10,000 queries/s to it and it collapses. Plan for that, as we will see under "cache avalanche" below.
A Cache in Action
The program below puts a simple TTL cache in front of a "slow database" (each query sleeps 50 ms). The workload is skewed: 80% of requests go to 20 hot products. The second part shows what happens when 20 requests for the same missing key arrive at the same moment, with and without a lock.
import random
import threading
import time
class SlowDatabase:
def __init__(self):
self.calls = 0
self.lock = threading.Lock()
def get_product(self, pid):
with self.lock:
self.calls += 1
time.sleep(0.05) # pretend the query takes 50 ms
return {"id": pid, "name": f"Product {pid}"}
class TTLCache:
def __init__(self, ttl):
self.ttl = ttl
self.data = {} # key -> (value, expires_at)
self.hits = self.misses = 0
def get(self, key):
item = self.data.get(key)
if item and item[1] > time.monotonic():
self.hits += 1
return item[0]
self.misses += 1
return None
def set(self, key, value):
self.data[key] = (value, time.monotonic() + self.ttl)
# ---------- Part 1: hit ratio with a skewed (80/20-like) workload ----------
db = SlowDatabase()
cache = TTLCache(ttl=60)
rng = random.Random(42)
def get_product(pid):
value = cache.get(pid)
if value is None:
value = db.get_product(pid)
cache.set(pid, value)
return value
for _ in range(1000):
# 80% of requests go to 20 "hot" products, 20% to 980 others
pid = rng.randint(1, 20) if rng.random() < 0.8 else rng.randint(21, 1000)
get_product(pid)
total = cache.hits + cache.misses
print(f"Requests: {total}, hits: {cache.hits}, misses: {cache.misses}, "
f"hit ratio: {cache.hits / total:.1%}, DB calls: {db.calls}")
print(f"DB time with cache : {db.calls * 0.05:.1f} s")
print(f"DB time without cache: {total * 0.05:.1f} s")
# ---------- Part 2: cache stampede on one hot key ----------
def stampede(use_lock):
db2 = SlowDatabase()
c = TTLCache(ttl=60)
key_lock = threading.Lock()
barrier = threading.Barrier(20)
def handler():
barrier.wait() # all 20 requests arrive together
v = c.get("home")
if v is not None:
return
if use_lock:
with key_lock: # only one thread rebuilds
if c.get("home") is None: # check again inside the lock
c.set("home", db2.get_product("home"))
else:
c.set("home", db2.get_product("home"))
threads = [threading.Thread(target=handler) for _ in range(20)]
for t in threads:
t.start()
for t in threads:
t.join()
return db2.calls
print("Stampede, no lock : DB calls =", stampede(False))
print("Stampede, with lock: DB calls =", stampede(True))
Output:
Requests: 1000, hits: 802, misses: 198, hit ratio: 80.2%, DB calls: 198
DB time with cache : 9.9 s
DB time without cache: 50.0 s
Stampede, no lock : DB calls = 20
Stampede, with lock: DB calls = 1
The cache cut database work by about 80% (198 calls instead of 1,000). The pattern used in get_product (check the cache, on a miss load from the database and store the result) is the most common caching pattern; its name and its alternatives are the subject of the next chapter, Cache Strategies & Eviction Policies. The second part previews the stampede problem discussed below.
What to Cache (and What Not To)
Good candidates | Poor candidates |
|---|---|
Read often, changed rarely (product details, user profiles) | Changes on almost every request (live stock count during a flash sale) |
Expensive to compute (aggregations, rendered pages, ML results) | Cheap to fetch anyway (a primary-key lookup on a tiny table) |
Shared by many users (home page, trending list) | Rarely requested twice (one-time reports) |
Tolerates slight staleness (like counts, view counts) | Must always be exact (account balance before a payment) |
The key question is always: how stale can this data be? A like count that is 30 seconds old is fine. A bank balance that is 30 seconds old can cause real damage.
Expiry with TTL
Every cached item should usually have a TTL (time to live), after which it expires and is reloaded on the next request.
Short TTL (seconds): fresher data, more misses, more database load.
Long TTL (hours/days): fewer misses, but stale data stays around longer.
TTL is also a safety net: even if your code forgets to invalidate an entry when data changes, the wrong value disappears eventually. In Redis, a TTL is set with commands like SET key value EX 300 (expire in 300 seconds).
Local Cache vs Distributed Cache
Local (in-process) caches Distributed cache
┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐
│ App 1 │ │ App 2 │ │ App 1 │ │ App 2 │
│ [cache 1] │ │ [cache 2] │ └─────┬──────┘ └─────┬──────┘
└────────────┘ └────────────┘ └──────┬───────┘
each server has its own copy ┌──────┴──────┐
│ Redis nodes │ one shared copy
└─────────────┘
Feature | Local (in-process) | Distributed (Redis, Memcached) |
|---|---|---|
Speed | Fastest: no network (nanoseconds to microseconds) | Network round trip (often well under a millisecond in the same data centre) |
Size | Limited by one server's RAM | Scales by adding nodes |
Consistency between servers | Each server may hold a different version | All servers see the same entry |
Survives app restart/deploy | No, starts cold | Yes |
Extra infrastructure | None | A cluster to run and monitor |
Large systems often use both: a tiny local cache with a very short TTL for the hottest keys, in front of a distributed cache, in front of the database.
Redis vs Memcached
Feature | Redis | Memcached |
|---|---|---|
Data model | Rich: strings, hashes, lists, sets, sorted sets, streams and more | Simple key → value (byte strings) |
Persistence | Optional (RDB snapshots, AOF log) | None: pure in-memory cache |
Replication and clustering | Built-in replication; Redis Cluster shards keys over 16,384 hash slots | No built-in replication; clients spread keys across servers (usually by consistent hashing) |
Threading | Commands execute on one main thread (optional I/O threads help with networking) | Multi-threaded |
Extra features | Atomic counters, pub/sub, Lua scripts, transactions, geospatial | Minimal by design |
Typical use | Cache plus sessions, leaderboards, rate limit counters, queues | Large, simple object caches |
A note on licensing, since it comes up in discussions: in 2024 Redis moved away from its BSD licence, and the community created Valkey, a BSD-licensed fork hosted by the Linux Foundation. From Redis 8 the open-source edition can also be used under the AGPLv3. For system design purposes, Redis and Valkey behave the same way.
Designing Cache Keys
A cache key must uniquely identify the data, including everything the result depends on.
product:1042 → product details
product:1042:lang=hi → same product, Hindi text (language changes the result!)
user:77:feed:page=1 → first page of user 77's feed
search:v3:q=laptop:sort=price → search results, schema version v3
Use a clear namespace prefix (
product:,user:).Include a version (
v3) so that changing the format of cached values never mixes old and new formats. Bumping the version is also a cheap way to invalidate everything of one type.Forgetting a parameter (like language or currency) causes one user's result to be served to another.
The Classic Caching Problems
"There are only two hard things in Computer Science: cache invalidation and naming things." (a well-known quote attributed to Phil Karlton)
1. Stale Data and Invalidation
When the database changes, the cached copy is now wrong. You must either delete or update the cached entry when data changes, or accept staleness up to the TTL. With multiple servers, local caches and replicas, guaranteeing that no one ever sees stale data is very hard, which is why most systems settle for "eventually fresh" plus a TTL. The detailed write patterns are in Cache Strategies & Eviction Policies.
2. Cache Stampede (Thundering Herd)
A very hot key expires. In the next few milliseconds, hundreds of requests miss at once and all of them query the database for the same value, as the demo showed (20 database calls for one key). On a popular key this can knock over the database.
Fixes:
Locking / request coalescing ("single flight"): only one request rebuilds the value; the others wait for it or briefly use the old value.
Serve stale while refreshing: keep the expired value and refresh it in the background (the same idea as HTTP
stale-while-revalidate).Early (probabilistic) refresh: refresh popular keys a little before they expire, with some randomness so not every server does it at once.
3. Cache Penetration
Requests for keys that do not exist (for example product id −1, or an attacker trying random IDs) always miss the cache and always hit the database, because there is nothing to cache.
Fixes:
Negative caching: cache "not found" too, with a short TTL.
Bloom filter: a compact probabilistic set of all valid keys. If it says "definitely not present", reject the request without touching the database. (Bloom filters can give false positives but never false negatives.)
Input validation and rate limiting (see Rate Limiting).
4. Cache Avalanche
A large number of keys expire at the same time (for example, all loaded at startup with the same 1-hour TTL), or the cache cluster itself goes down. The database suddenly receives the full traffic.
Fixes:
TTL jitter: use TTL = base + random(0, few minutes), so expiries spread out.
Highly available cache: replicas and automatic failover.
Protect the database: circuit breakers, rate limits and graceful degradation (serve partial or default content).
Warm the cache before sending full traffic to a new or restarted cache cluster.
5. Hot Keys
One key (a celebrity's profile, a live cricket score) gets so much traffic that the single cache node holding it is overloaded, even though the cluster as a whole is idle.
Fixes: add a small local cache on each app server for that key, or store several copies under different keys (score:1, score:2, ... chosen at random) so they land on different nodes.
Problem | Cause | Main fixes |
|---|---|---|
Stampede | One hot key expires, many concurrent misses | Lock / single flight, serve stale, early refresh |
Penetration | Requests for non-existent keys | Negative caching, Bloom filter, validation |
Avalanche | Many keys expire together, or cache down | TTL jitter, HA cache, DB protection, warm-up |
Hot key | One key overloads one node | Local cache, key replication |
Stale data | DB changed, cache did not | Invalidate on write, TTL safety net |
Advantages and Disadvantages of Caching
Advantages | Disadvantages |
|---|---|
Much lower latency for hits | Stale data and invalidation complexity |
Large reduction in database load | Extra infrastructure to run, monitor and pay for |
Absorbs traffic spikes | The system can come to depend on it (cache down = DB overload) |
Cheaper than scaling the database | Memory is limited, so something must be evicted |
Common Mistakes
Caching without a TTL. Any invalidation bug then lives forever.
Caching data that must be exact, like balances or inventory at checkout, without a strategy to keep it correct.
Treating the cache as the database. A pure cache can lose data at any time (eviction, restart). The source of truth must be elsewhere.
Missing parameters in the key, leading to one user seeing another user's data.
Same TTL for millions of keys loaded together, causing an avalanche.
Measuring only hit ratio. Watch the miss rate in absolute numbers (queries/s reaching the database) and the latency of misses.
Interview Questions
1. Cache lookup takes 2 ms and a database query takes 40 ms. On a miss, the cache is checked first. What is the average time at a 95% hit ratio?
Effective time = T_cache + (1 − h) × T_db = 2 + 0.05 × 40 = 2 + 2 = 4 ms (compared with 40 ms without a cache).
2. What is a cache stampede and how do you prevent it?
When a popular key expires, many concurrent requests miss and all hit the database for the same value. Prevent it by letting only one request rebuild the value (a lock or single-flight), serving the stale value while refreshing in the background, or refreshing hot keys slightly before they expire.
3. How would you stop requests for non-existent IDs from hammering the database?
Cache negative results ("not found") with a short TTL, and/or keep a Bloom filter of valid IDs to reject impossible keys before any database query. Validate inputs and rate limit abusive clients.
4. Local cache or distributed cache: which would you use?
A local cache is fastest and needs no infrastructure but is small, per-server and can be inconsistent across servers. A distributed cache is shared, larger and survives deployments but adds a network hop. Often both: a small, short-TTL local cache for the hottest keys in front of Redis.
5. Why can raising the hit ratio from 95% to 99% matter so much?
Because the database sees the misses. Misses drop from 5% to 1% of traffic, a 5 times reduction in database load, even though the hit ratio only rose by 4 percentage points.
6. Give two differences between Redis and Memcached.
Redis supports rich data structures (hashes, sorted sets, streams), optional persistence and built-in replication/clustering; Memcached is a simple multi-threaded key-value cache with no persistence or built-in replication.
Summary
A cache keeps copies of expensive data in fast storage. It works because access patterns are skewed and repetitive.
Caches exist at every layer: browser, CDN, proxy, application, distributed cache, database, OS and CPU.
Effective time = T_cache + (1 − h) × T_db. Database load is proportional to the miss ratio.
Use TTLs as a safety net; choose them by asking "how stale can this be?"
Local caches are fastest; distributed caches (Redis, Memcached, Valkey) are shared and scalable.
Know the classic problems: stale data, stampede, penetration, avalanche and hot keys, and their fixes.
A cache turns "compute it every time" into "compute it once". The hard part is knowing when the saved answer is no longer true.