System Design · Lesson 3 of 18
Scaling and Caching
Load balancers, horizontal scaling, caches, CDNs and consistent hashing.
- Intermediate
- 50 min read
- 7 objectives
Before this lessonLesson 2: Every Term, Explained
What you will learn
- Choose vertical or horizontal scaling per tier
- Make services stateless and balance them at L4 or L7
- Compare load-balancing algorithms and health checks
- Use forward and reverse proxies, CDNs and redundancy
- Pick cache patterns, eviction and invalidation strategies
- Prevent stampedes and hot keys, and do the hit-ratio maths
- Autoscale without falling behind the peak
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
Almost every system design answer, whatever the product, has the same spine: a load balancer in front of a fleet of stateless servers, a cache in front of the database, and a CDN in front of everything static. This lesson takes that spine apart piece by piece. For each piece you get what it is, the options, the numbers, runnable code that shows the behaviour, and the wrong answers interviewers hear most often.
The two halves reinforce each other. Scaling (load balancers, stateless services, proxies, redundancy, autoscaling) lets you add machines. Caching (patterns, eviction, invalidation, stampedes, hot keys, CDNs) lets each machine — and especially the database behind them — do far less work. A good design uses caching first, because a request you do not have to serve is cheaper than any server you can add.
static + cacheable GETs"] CDN --> LB["L7 load balancer
redundant pair or managed"] LB --> A1["App 1
stateless + L1 cache"] LB --> A2["App 2
stateless + L1 cache"] LB --> A3["App N
stateless + L1 cache"] A1 --> RC[("Redis cluster
L2 shared cache")] A2 --> RC A3 --> RC A1 --> DB[("Primary DB")] A2 --> RR[("Read replicas")] A3 --> RR A1 --> OS[("Object storage")] OS --> CDN
Every tier absorbs load for the one behind it. The CDN takes static bytes, the in-process L1 and Redis L2 take repeated reads, replicas take the rest of the reads, and the primary is left with writes.
Vertical versus horizontal scaling
Vertical scaling (scaling up) means a bigger machine: more cores, more RAM, faster disks. Horizontal scaling (scaling out) means more machines sharing the work. Both are legitimate; the skill is knowing when each one is right.
| Vertical (scale up) | Horizontal (scale out) | |
|---|---|---|
| How | Resize to a larger instance | Add instances behind a load balancer; partition data |
| Code changes | None | Services must be stateless; data must be partitionable |
| Ceiling | The biggest machine you can buy (hundreds of cores, a few TB of RAM) | Practically none for stateless tiers |
| Cost curve | Linear, then steep at the top end | Roughly linear, plus coordination overhead |
| Failure | One box = one point of failure | Losing one box loses 1/N of capacity |
| Resize | Usually a restart or failover | Add or remove instances live |
| Best for | Relational primaries, early-stage products, anything with heavy joins or transactions | Web and API tiers, caches, workers, anything read-heavy |
Worked example. A Postgres primary at 70% CPU on 8 cores. Moving to 32 cores takes a planned failover to a bigger replica — minutes of work — and buys roughly 4x headroom with zero code changes. Sharding the same database takes months and makes every cross-shard query and transaction harder. So the right sequence is: scale the database up first, add read replicas for reads, and shard only when the largest sensible machine is not enough. The API tier in front of it is the opposite: it should scale out from day one, because making it stateless costs almost nothing and buys you both capacity and fault tolerance.
The common wrong answer is treating these as a philosophy ("horizontal is always better"). The right answer is per tier: scale out what is stateless and cheap to split; scale up what is stateful and expensive to split, until you cannot.
Stateless services — the precondition for scaling out
A service is stateless when any instance can serve any request, because nothing a later request needs is kept only in one instance's memory or local disk. That is what lets a load balancer send each request anywhere, lets autoscaling add and remove instances freely, and lets a crashed instance be replaced without anyone noticing.
State does not disappear; it moves somewhere shared and durable:
| State | Wrong place | Right place |
|---|---|---|
| Login session | In-memory session map on one server | Signed token (JWT) the client carries, or a session store in Redis |
| Uploaded files | The server's local disk | Object storage (S3, GCS), referenced by key |
| Shopping cart, drafts | Process memory | Database or Redis with a TTL |
| Background jobs | An in-process thread or timer | A queue with durable messages (see queues and APIs) |
| WebSocket connections | Unavoidably on one server | A dedicated, sticky connection tier; route messages via pub/sub |
Worked example — the bug that appears at instance two. A single-server app stores sessions in memory and works perfectly. The team adds a second instance behind a round-robin load balancer. Now every other request lands on the server that has never seen the user, and users are randomly logged out. The quick fix is sticky sessions (the load balancer pins a user to one server by cookie). It works, but it is a trap: load becomes uneven, a deploy or crash logs out everyone on that box, and autoscaling in cannot remove a server without evicting its users. The real fix is moving the session into Redis or a signed token — after which stickiness is unnecessary.
A local in-process cache is still fine on a stateless server, as long as it is only a copy of data that lives elsewhere — losing it costs a cache miss, not correctness.
Load balancers
A load balancer (LB) spreads incoming requests across a pool of servers, stops sending traffic to servers that are unhealthy, and gives clients one stable address while the pool behind it changes. In a real system you find them in three places: between users and the web tier, between the web tier and internal services, and between services and data tiers (a proxy in front of database replicas, or client-side balancing in a database driver).
Where balancing happens
- DNS / global balancing: GeoDNS or anycast sends users to the nearest healthy region. Coarse — DNS answers are cached by clients for their TTL, so failover takes as long as the TTL.
- Network load balancer (layer 4) inside a region.
- Application load balancer or reverse proxy (layer 7) in front of services.
- Client-side balancing: a service mesh sidecar or gRPC client that knows every backend and picks one itself — no extra hop, used heavily for service-to-service calls.
Layer 4 versus layer 7
| Layer 4 (transport) | Layer 7 (application) | |
|---|---|---|
| Sees | IP addresses, ports, TCP/UDP connections | Full HTTP: path, host, headers, cookies, body |
| Can route by | Connection 5-tuple only | /api vs /static, host name, header, user cohort for canaries |
| TLS | Passes it through (or terminates, on some products) | Terminates it, so it can read the request |
| Extras | Very little — that is the point | Retries, rate limiting, auth, compression, caching, request rewriting |
| Cost | Millions of connections per box, microseconds of added latency | More CPU per request, sub-millisecond to a few ms of added latency |
| Balances | Per connection — one long-lived connection always goes to one server | Per request — even across one HTTP/2 or gRPC connection |
| Use for | Raw TCP (databases, MQTT, game servers), extreme throughput, in front of L7 fleets | Web and API traffic, microservice routing, anything needing smart routing |
The last-but-one row is the subtle one. gRPC and HTTP/2 multiplex many requests over one long-lived connection. Behind an L4 balancer, each client connection is pinned to one server, so a handful of busy clients can overload one backend while others sit idle. Balancing gRPC properly needs L7 or client-side balancing.
Balancing algorithms
- Round robin: next server in turn. Perfect when servers are identical and requests cost the same; bad when some requests are 20x more expensive than others.
- Weighted round robin: servers get turns in proportion to a weight — a 16-core box gets twice the share of an 8-core one. Also used to shift 5% of traffic to a canary.
- Least connections: send to the server with the fewest in-flight requests. Adapts automatically to uneven request cost and long-lived connections.
- Least response time: fewest connections weighted by recent latency — steers away from a server that is slow because of a noisy neighbour or GC pause.
- Least bandwidth: the server currently moving the fewest Mbit/s — useful for large downloads and streaming.
- Power of two choices: pick two servers at random and send to the less loaded one. Nearly as good as least connections, without every balancer needing a perfect global view — the default in several modern proxies.
- IP hash / consistent hashing: the same client or key always maps to the same server. Needed when the backend holds per-key state (a cache shard, a chat connection); consistent hashing keeps the mapping stable when servers join or leave.
Worked example. Four servers; 90% of requests are cheap (20 ms) and 10% are heavy reports (400 ms); each extra in-flight request on a box slows it a little. The simulation below compares round robin with least connections, then shows why a cache tier needs consistent hashing rather than hash(key) % N:
import bisect, hashlib, heapq, random
# ---------- Part 1: round robin vs least connections under uneven request cost ----------
random.seed(7)
# 2,000 requests, one every 5 ms. 90% are quick (20 ms); 10% are heavy reports (400 ms).
requests = [(i * 5, 400 if random.random() < 0.10 else 20) for i in range(2_000)]
def simulate(pick, servers=4):
active = [[] for _ in range(servers)] # per-server heap of finish times
peak = [0] * servers
waits = []
rr = 0
for arrive, cost in requests:
for h in active: # drop connections that have finished
while h and h[0] <= arrive:
heapq.heappop(h)
s, rr = pick(active, rr)
# crude queueing: each extra in-flight request on the box adds 15% to this one
latency = cost * (1 + 0.15 * len(active[s]))
heapq.heappush(active[s], arrive + latency)
peak[s] = max(peak[s], len(active[s]))
waits.append(latency)
waits.sort()
return peak, waits[len(waits) // 2], waits[int(len(waits) * 0.99)]
def round_robin(active, rr):
return rr % len(active), rr + 1
def least_connections(active, rr):
return min(range(len(active)), key=lambda i: len(active[i])), rr
for name, algo in (("round robin", round_robin), ("least connections", least_connections)):
peak, p50, p99 = simulate(algo)
print(f"{name:<18} peak in-flight per server {peak} p50 {p50:.0f} ms p99 {p99:.0f} ms")
# ---------- Part 2: what moves when a server is added ----------
def h(s):
return int(hashlib.md5(s.encode()).hexdigest(), 16)
class Ring:
def __init__(self, nodes, vnodes=100):
self.points = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
self.hashes = [p for p, _ in self.points]
def node_for(self, key):
i = bisect.bisect(self.hashes, h(key)) % len(self.points)
return self.points[i][1]
keys = [f"user:{i}" for i in range(20_000)]
old_nodes, new_nodes = ["s1", "s2", "s3", "s4"], ["s1", "s2", "s3", "s4", "s5"]
moved_mod = sum(h(k) % 4 != h(k) % 5 for k in keys)
r_old, r_new = Ring(old_nodes), Ring(new_nodes)
moved_ring = sum(r_old.node_for(k) != r_new.node_for(k) for k in keys)
print(f"\nadd a 5th server: hash % N moves {moved_mod / len(keys):.0%} of keys, "
f"consistent hashing moves {moved_ring / len(keys):.0%} (ideal 20%)")
load = {n: 0 for n in new_nodes}
for k in keys:
load[r_new.node_for(k)] += 1
print("ring load per server:", {n: f"{c / len(keys):.0%}" for n, c in load.items()})round robin peak in-flight per server [12, 8, 10, 12] p50 32 ms p99 880 ms
least connections peak in-flight per server [7, 7, 6, 6] p50 32 ms p99 700 ms
add a 5th server: hash % N moves 79% of keys, consistent hashing moves 17% (ideal 20%)
ring load per server: {'s1': '21%', 's2': '19%', 's3': '22%', 's4': '21%', 's5': '17%'}
Round robin blindly gives the next request to a server that may already be chewing on three heavy reports, so its busiest server peaks at almost twice the in-flight load of least connections, and the p99 is noticeably worse. Least connections sees the pile-up and routes around it. For the key-to-server mapping, hash % N moves about 80% of keys when you go from four to five servers — for a cache that means an 80% miss storm hitting the database at once. Consistent hashing with 100 virtual nodes per server moves close to the ideal 1/5 and keeps the load within a few percent of even. (Consistent hashing is built step by step in the key-value store lesson.)
Health checks
An LB is only as good as its view of which backends are alive. Two kinds of check work together:
- Active checks: the LB calls
GET /healthzevery few seconds. A good endpoint checks what the instance needs to serve traffic (it can reach its cache and database pool) but is cheap and does not cascade — if the database is down for everyone, failing every instance's health check just turns a partial outage into a total one. - Passive checks (outlier detection): the LB watches real traffic and ejects a backend that returns a burst of 5xx errors or timeouts, then retries it after a back-off.
- Liveness versus readiness: liveness means "the process is not wedged; restart me if this fails". Readiness means "send me traffic". A starting instance warming its cache is live but not ready. Mixing the two up causes restart loops.
- Hysteresis: require several consecutive failures to eject and several successes to readmit, so a single slow probe does not flap a healthy server in and out.
# Health checks with hysteresis: fall after 3 failures, rise after 2 successes.
# Without it, one slow GC pause removes a healthy server and a flapping one keeps rejoining.
class Backend:
def __init__(self, name, fall=3, rise=2):
self.name, self.fall, self.rise = name, fall, rise
self.healthy, self.fails, self.oks = True, 0, 0
def observe(self, ok):
if ok:
self.oks, self.fails = self.oks + 1, 0
if not self.healthy and self.oks >= self.rise:
self.healthy = True
return "back IN rotation"
else:
self.fails, self.oks = self.fails + 1, 0
if self.healthy and self.fails >= self.fall:
self.healthy = False
return "OUT of rotation"
return ""
b = Backend("app-3")
# probe every 5 s: one blip, then a real outage, then recovery
probes = [1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
for t, ok in enumerate(probes):
event = b.observe(bool(ok))
print(f"t={t * 5:>3}s probe {'ok ' if ok else 'FAIL'} healthy={b.healthy!s:<5} {event}".rstrip())t= 0s probe ok healthy=True t= 5s probe ok healthy=True t= 10s probe FAIL healthy=True t= 15s probe ok healthy=True t= 20s probe ok healthy=True t= 25s probe FAIL healthy=True t= 30s probe FAIL healthy=True t= 35s probe FAIL healthy=False OUT of rotation t= 40s probe FAIL healthy=False t= 45s probe ok healthy=False t= 50s probe FAIL healthy=False t= 55s probe ok healthy=False t= 60s probe ok healthy=True back IN rotation t= 65s probe ok healthy=True
The single failed probe at 10 s is ignored; the real outage is detected at 35 s after three failures in a row; the brief recovery at 45 s is not trusted until two consecutive successes at 60 s. With 5-second probes and a fall threshold of 3, detection takes up to 15 seconds — that number is your minimum blast window, and it is worth quoting. For deploys, pair health checks with connection draining: mark an instance not-ready, let in-flight requests finish (say, 30 seconds), then stop it.
Redundant load balancers
A single load balancer is a single point of failure in front of a fleet you made redundant. Standard fixes:
- Active–passive pair: two LBs share a floating virtual IP using a heartbeat protocol such as VRRP (keepalived). If the active one stops heartbeating, the passive one claims the IP within a second or two.
- Active–active: several LBs all serve traffic, with DNS returning multiple addresses, or routers spreading packets over them with anycast and ECMP. Losing one reduces capacity rather than causing an outage.
- Managed load balancers (cloud ALB/NLB, Cloud Load Balancing) are internally redundant across zones. In an interview, "a managed, multi-AZ load balancer" is an acceptable answer — as long as you know what it is doing for you.
Proxies — forward and reverse
A proxy is a server that sits between a client and a destination and forwards requests on someone's behalf. The difference between the two kinds is whose behalf.
| Forward proxy | Reverse proxy | |
|---|---|---|
| Acts for | The clients | The servers |
| Who configures it | The client side (a company network, a browser setting) | The service owner |
| Who is hidden | The client's identity from the internet | The backend topology from clients |
| Typical jobs | Egress filtering and policy, shared caching of downloads, logging, anonymity, controlled outbound access from a private network | TLS termination, load balancing, caching, compression, routing, rate limiting, auth, request buffering against slow clients |
| Examples | Corporate web proxy, Squid, an egress gateway for outbound API calls | Nginx, HAProxy, Envoy, an API gateway, a CDN |
Forward proxies come in a few flavours worth being able to name: an open proxy accepts anyone on the internet (a common abuse vector); an anonymous proxy identifies itself as a proxy but hides the client's IP; a transparent proxy hides nothing — it passes the client's IP along in a header such as X-Forwarded-For — and is mainly used for caching and filtering, often without the client configuring anything.
In a system design, the reverse proxy is the one you draw. A single Nginx or Envoy layer often does the job of load balancer, TLS terminator, static file server, response cache and rate limiter at once. An API gateway is a reverse proxy specialised for APIs (auth, quotas, request validation, versioned routing); a service mesh sidecar is a reverse and forward proxy running next to every service instance, handling retries, timeouts, mutual TLS and client-side load balancing for service-to-service calls.
Worked example — collapsing requests at the proxy. A reverse proxy can cache a popular response and serve it to every client for a few seconds. With request collapsing enabled (Nginx proxy_cache_lock, Varnish does it by default), 5,000 simultaneous requests for the same uncached URL send exactly one request to the backend; the rest wait for that response. That is the same stampede protection covered later in this lesson, applied at the edge.
Redundancy and replication
Redundancy is keeping more than one copy of a critical component so that losing one does not take the system down. Replication is the mechanism that keeps redundant copies of data in step. Together they are how you remove single points of failure.
- Active–active: every copy serves traffic (stateless app instances, multi-leader or leaderless stores). Capacity and failover in one; conflict handling needed for data.
- Active–passive: one copy serves; a standby takes over on failure (a database primary with a hot standby). Simple and consistent, but the standby's capacity sits idle, and failover takes seconds to minutes.
- N+1 and N+2: provision enough to carry peak load with one (or two) instances or zones lost. With three zones, each must be able to take 50% of peak so any two survive the loss of the third.
- Spread across failure domains: replicas on different racks, zones and, for disaster recovery, regions. Two replicas on the same host are not redundant.
Replication itself — synchronous versus asynchronous, leader–follower, quorum reads and writes, replication lag — is covered in depth in the databases lesson.
Caching — where caches live
Caches exploit locality of reference: data read recently, or read often, is likely to be read again. Real workloads are heavily skewed — a small fraction of products, profiles or URLs gets most of the traffic — so a cache holding a small slice of the data can serve most of the requests. Caches sit at every layer:
| Layer | What it holds | Latency | Scope |
|---|---|---|---|
| Browser / mobile app | Static assets, API responses per Cache-Control / ETag | 0 ms (no network) | One user |
| CDN edge | Images, JS/CSS, video segments, cacheable public GETs | 5–30 ms from the user | Everyone near that edge |
| Reverse proxy | Rendered pages, API responses | <1 ms from the app | One datacenter |
| In-process (L1) | Hot config, feature flags, the hottest objects | ~100 ns–10 µs | One process |
| Distributed cache (L2) | Sessions, objects, query results, computed feeds | 0.2–1 ms | All app servers |
| Database buffer pool | Hot pages and indexes | Inside the query time | That database |
Local, global and distributed caches. A cache on each app server is fastest, but once there are many servers and the load balancer spreads requests randomly, each server's cache warms separately and holds its own copy — hit ratios drop and memory is duplicated N times. The two ways out: a global cache (one shared cache all servers talk to — simple, but a bottleneck and single point of failure at scale), or a distributed cache (Redis Cluster, a Memcached pool) where keys are partitioned across nodes by consistent hashing, so capacity grows by adding nodes. Most production systems use both: a small in-process L1 for the hottest keys in front of a distributed L2.
CDNs — push versus pull
A content delivery network is a globally distributed cache: hundreds of edge locations, each close to users, serving bytes that would otherwise cross an ocean. A user in Mumbai fetching an image from a server in Virginia pays roughly 200 ms per round trip; from a Mumbai edge, 10 ms. The CDN also absorbs the bandwidth — often more than 90% of a consumer product's bytes — and soaks up traffic spikes and some kinds of DDoS.
| Pull CDN | Push CDN | |
|---|---|---|
| How content arrives | On the first request, the edge fetches from your origin and caches it | You upload content to the CDN ahead of time |
| First request | A miss: slow, and it hits the origin | Always a hit |
| Freshness | Controlled by TTLs (Cache-Control) and purges | You re-upload when content changes |
| Storage cost | Only what users actually request | Everything you push, whether requested or not |
| Operational effort | Low — point the CDN at the origin | Higher — a publishing pipeline |
| Best for | Websites, images, API GETs, long-tail content with unpredictable popularity | Large files with known demand: game patches, app releases, a video premiere |
Practical rules: version static asset URLs (app.3f9c2e.js) and give them a one-year TTL — a new deploy is a new URL, so you never need to purge. Give HTML and API responses short TTLs (seconds to minutes) or stale-while-revalidate. Use an origin shield (a mid-tier cache) so a miss at 300 edges becomes one request to your origin, not 300. If you are not ready for a CDN yet, serve static files from a separate hostname such as static.example.com — switching that hostname to a CDN later is a DNS change.
Cache read and write patterns
A cache pattern answers two questions: who loads data into the cache on a read, and what happens to the cache on a write. The five you should know:
| Pattern | Read path | Write path | Strength | Weakness | Use for |
|---|---|---|---|---|---|
| Cache-aside (lazy loading) | App checks cache; on a miss reads DB and fills cache | App writes DB, then deletes the cache key | Simple; cache holds only what is read; cache outage degrades to DB reads | First read after a write is a miss; stale window if invalidation fails | The default for most read-heavy data |
| Read-through | App asks the cache; the cache library loads from DB on a miss | Usually combined with write-through or invalidation | Loading logic lives in one place | Needs a cache layer that supports loaders | When a caching library or provider does it for you |
| Write-through | Reads hit a warm cache | Write cache and DB synchronously, then acknowledge | Cache is never stale for keys written through it | Every write pays both latencies; caches data that may never be read | Data read soon after writing: profiles, settings |
| Write-behind (write-back) | Reads hit the cache | Write cache, acknowledge, flush to DB later in batches | Very fast writes; coalesces many updates into one | Data loss if the cache dies before flushing; complex ordering | Counters, view counts, metrics — where losing a few seconds is acceptable |
| Write-around | Cache-aside on reads | Write DB only; skip (and invalidate) the cache | Does not flood the cache with write-once data | Reading just-written data is a miss | Logs, bulk imports, large objects rarely re-read |
Worked example. The same workload — read a key, update a hot counter ten times, read it again, write one more key, then the cache node crashes — run through each pattern:
# Five caching patterns against the same tiny workload, with a crash at the end.
class DB:
def __init__(self):
self.rows, self.reads, self.writes = {"a": 1, "b": 2}, 0, 0
def get(self, k):
self.reads += 1
return self.rows.get(k)
def put(self, k, v):
self.writes += 1
self.rows[k] = v
class Store:
def __init__(self, pattern):
self.pattern, self.db, self.cache, self.dirty = pattern, DB(), {}, {}
def read(self, k):
if k in self.cache:
return self.cache[k]
# cache-aside: the APP loads and fills. read-through: the CACHE LIBRARY does
# the same thing on the app's behalf - identical data flow, different owner.
v = self.db.get(k)
self.cache[k] = v
return v
def write(self, k, v):
if self.pattern in ("cache-aside", "read-through"):
self.db.put(k, v)
self.cache.pop(k, None) # invalidate; next read refills
elif self.pattern == "write-through":
self.db.put(k, v) # both, synchronously, before returning
self.cache[k] = v
elif self.pattern == "write-behind":
self.cache[k] = v # ack immediately...
self.dirty[k] = v # ...flush to the DB later, coalesced
elif self.pattern == "write-around":
self.db.put(k, v) # DB only; do not pollute the cache
self.cache.pop(k, None)
def flush(self):
for k, v in self.dirty.items():
self.db.put(k, v)
self.dirty.clear()
def crash(self):
self.cache.clear()
lost = len(self.dirty)
self.dirty.clear() # un-flushed writes are gone
return lost
print(f"{'pattern':<14}{'DB writes':>10}{'DB reads':>10}{'lost on crash':>15}")
for p in ("cache-aside", "read-through", "write-through", "write-behind", "write-around"):
s = Store(p)
s.read("a")
for i in range(10): # a hot counter updated 10 times
s.write("a", i)
s.read("a")
if p == "write-behind":
s.flush() # periodic flush: 10 updates -> 1 DB write
s.write("b", 99) # one more write, then the node dies
lost = s.crash()
print(f"{p:<14}{s.db.writes:>10}{s.db.reads:>10}{lost:>15}")pattern DB writes DB reads lost on crash cache-aside 11 2 0 read-through 11 2 0 write-through 11 1 0 write-behind 1 1 1 write-around 11 2 0
Cache-aside and read-through behave identically here — the difference is only who owns the loading code. Write-through avoids the second DB read because the cache already holds the new value. Write-behind turns ten counter updates into one database write (the reason it exists) and then loses the write that had not been flushed when the node died (the reason it is dangerous). If you choose write-behind in an interview, say what happens on a crash and why the data can tolerate it.
Delete on write, do not set on write
With cache-aside, a common instinct is to write the new value into the cache after updating the database. Under concurrency this can leave the cache permanently wrong:
# Why "update the DB, then DELETE the cache key" beats "update the DB, then SET the cache".
# Two writers race. We replay the same unlucky interleaving against both policies.
def run(policy):
db, cache = {"price": 100}, {}
# Writer A sets 120, writer B sets 130. B's DB write lands last (so DB = 130),
# but A's cache step happens after B's cache step - a slow network, a GC pause.
db["price"] = 120 # A: DB write
db["price"] = 130 # B: DB write
if policy == "set":
cache["price"] = 130 # B: cache step
cache["price"] = 120 # A: cache step (late)
else:
cache.pop("price", None) # B: delete
cache.pop("price", None) # A: delete (late) - harmless, still gone
value = cache.get("price")
if value is None: # next reader misses and refills from DB
value = cache["price"] = db["price"]
return db["price"], value
for policy in ("set", "delete"):
db_value, served = run(policy)
verdict = "consistent" if db_value == served else "STALE until TTL expires"
print(f"{policy:>6} on write: DB={db_value} cache serves {served} -> {verdict}")set on write: DB=130 cache serves 120 -> STALE until TTL expires delete on write: DB=130 cache serves 130 -> consistent
Two writers update the database in one order and the cache in the other, so "set" leaves the older value cached until the TTL expires. "Delete" is order-independent: whatever happens, the next reader refills from the database. Delete-on-write still has a narrower race — a reader fetches the old row, a writer updates and deletes, then the slow reader writes the old value back — which is why production systems add a TTL as a safety net, and at very high scale use leases (the cache hands out a token on a miss and rejects a fill whose token was invalidated by a later delete) or versioned values (only store a value if its version is newer than what is cached).
Eviction policies
A cache is smaller than the data behind it, so when it is full something must go. The eviction policy decides what.
- LRU (least recently used): evict what has not been touched for the longest. The default nearly everywhere; cheap to implement in O(1) with a hash map and a linked list. Weakness: a one-off scan of many cold keys flushes the hot set.
- LFU (least frequently used): evict what has been used the fewest times. Resists scans, but items that were popular last week can linger; practical versions decay counts over time.
- FIFO: evict the oldest insertion regardless of use. Simple, and surprisingly competitive in modern designs that pair it with a small admission filter.
- LIFO / MRU: evict the newest or most recently used. Sounds wrong, but is correct for cyclic scans larger than the cache, where the item just used is the one needed furthest in the future.
- Random: evict any key. No bookkeeping, and not far behind LRU for many skewed workloads.
- TTL-based: expire by age, independent of memory pressure. Almost always combined with one of the above.
In practice: Redis offers allkeys-lru, allkeys-lfu, volatile-ttl and random variants, implemented approximately by sampling a few keys rather than keeping a perfect order. Caffeine (Java) and several CDNs use W-TinyLFU, which admits a new item only if it is estimated to be more popular than the one it would evict. Here is an O(1) LRU and an O(1) LFU, run against a workload with a hot set of 80 keys and a nightly job that reads 300 cold keys once:
from collections import OrderedDict, defaultdict
import random
class LRUCache:
"""O(1) get/put: an ordered dict is a hash map + doubly linked list."""
def __init__(self, capacity):
self.cap, self.data = capacity, OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key) # now the most recently used
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False) # evict the least recently used
class LFUCache:
"""O(1) LFU: buckets of keys per frequency, plus the current minimum frequency.
Ties inside a bucket are broken by recency (oldest evicted first)."""
def __init__(self, capacity):
self.cap, self.vals, self.freq = capacity, {}, {}
self.buckets = defaultdict(OrderedDict)
self.min_freq = 0
def _touch(self, key):
f = self.freq[key]
del self.buckets[f][key]
if not self.buckets[f] and self.min_freq == f:
self.min_freq = f + 1
self.freq[key] = f + 1
self.buckets[f + 1][key] = None
def get(self, key):
if key not in self.vals:
return None
self._touch(key)
return self.vals[key]
def put(self, key, value):
if key in self.vals:
self.vals[key] = value
self._touch(key)
return
if len(self.vals) >= self.cap:
victim, _ = self.buckets[self.min_freq].popitem(last=False)
del self.vals[victim], self.freq[victim]
self.vals[key], self.freq[key] = value, 1
self.buckets[1][key] = None
self.min_freq = 1
def run(cache, trace):
hits = []
for key in trace:
hit = cache.get(key) is not None
if not hit:
cache.put(key, f"value-of-{key}") # cache-aside fill on miss
hits.append(hit)
return hits
random.seed(42)
hot = [f"hot:{i}" for i in range(80)] # 80 popular product pages
before = [random.choice(hot) for _ in range(2_000)]
scan = [f"report:{i}" for i in range(300)] # a nightly job reads 300 cold rows once
after = [random.choice(hot) for _ in range(200)]
trace = before + scan + after
for name, cls in (("LRU", LRUCache), ("LFU", LFUCache)):
hits = run(cls(100), trace) # room for 100 keys
warm = sum(hits[1_000:2_000]) / 1_000
post = sum(hits[-200:]) / 200
print(f"{name}: hit ratio when warm {warm:.0%} | first 200 requests after the scan {post:.0%}")LRU: hit ratio when warm 100% | first 200 requests after the scan 64% LFU: hit ratio when warm 100% | first 200 requests after the scan 100%
Both caches hold the hot set perfectly in steady state. The one-off scan pushes every hot key out of the LRU cache, so the next stretch of real traffic suffers a burst of misses that land on the database. The LFU cache keeps the hot keys, because the scan keys each have a count of one and evict each other. When a workload mixes a hot set with occasional scans — analytics jobs, crawlers, backfills — frequency-aware eviction (or simply routing the scan around the cache, which is write-around applied to reads) is the fix.
Invalidation strategies
Keeping the cache in step with the source of truth is the hard part of caching. Strategies, roughly from simplest to strongest:
- TTL only: accept staleness up to the TTL. Perfect for data that is fine a minute old (a feed, a product listing).
- Explicit delete on write: the writer deletes the key after committing. Tight freshness, but every write path must remember to do it, including admin tools and batch jobs.
- Versioned keys: put a version in the key (
menu:123:v42) and bump the version on change. No delete needed; old entries simply age out. Excellent for documents and CDN URLs. - Change data capture: a pipeline tails the database's replication log and deletes or updates cache keys for every changed row. Catches writes from every code path, at the cost of a second of lag and another moving part.
- Pub/sub broadcast: for in-process L1 caches on many servers, publish "key X changed" and every server drops its copy.
- Write-through: the cache is updated as part of the write itself.
Always keep a TTL even when you invalidate explicitly — it bounds the damage of any invalidation you miss. And invalidate after the database commit, never before, or a reader can refill the old value in between.
Thundering herd and cache stampede
A stampede happens when a popular key expires (or the cache restarts) and every concurrent request misses at once, all querying the database for the same thing. With 2,000 reads a second on one key and a 400 ms query, a naive cache-aside sends 800 identical queries per expiry — often enough to push a database that was fine a second ago into overload, which slows the query, which widens the window, which lets in more requests. Four fixes, often combined:
- Request coalescing (single-flight / mutex): the first miss takes a short lock (
SET lock:key 1 NX EX 5) and recomputes; others wait briefly and re-read, or are served the stale value. - Serve stale while revalidating: keep the old value past its soft expiry and refresh it in the background; readers never wait.
- Probabilistic early expiration: each reader, as expiry approaches, has a small and growing chance of volunteering to refresh early — so one reader refreshes before the key goes cold, with no lock at all.
- Jittered TTLs: add ±10–20% randomness to TTLs so keys written at the same moment (after a deploy or a cache flush) do not all expire in the same second.
import math, random
from collections import Counter
random.seed(1)
QPS = 2_000 # reads per second on ONE hot key
TTL = 60.0 # seconds
RECOMPUTE = 0.4 # seconds the DB query takes (the "delta")
def naive(duration=180):
"""Every request that misses queries the DB until someone refills the key."""
expires, refill_at, db_calls = 0.0, None, 0
for i in range(int(duration * QPS)):
now = i / QPS
if refill_at is not None and now >= refill_at:
expires, refill_at = refill_at + TTL, None
if now >= expires: # miss
db_calls += 1
if refill_at is None:
refill_at = now + RECOMPUTE
return db_calls
def coalesced(duration=180):
"""Single-flight: the first miss takes a lock and recomputes; others wait for it."""
expires, in_flight_until, db_calls, waited = 0.0, None, 0, 0
for i in range(int(duration * QPS)):
now = i / QPS
if in_flight_until is not None and now >= in_flight_until:
expires, in_flight_until = in_flight_until + TTL, None
if now >= expires:
waited += 1 # this reader blocks on the refill
if in_flight_until is None:
db_calls += 1 # only the lock holder hits the DB
in_flight_until = now + RECOMPUTE
return db_calls, waited
def xfetch(duration=180, beta=1.0):
"""Probabilistic early expiry: each reader may volunteer to refresh BEFORE expiry.
The closer to expiry, the likelier. The key never actually goes cold."""
expires, db_calls, early, misses, refreshing_until = 0.0, 0, 0, 0, None
for i in range(int(duration * QPS)):
now = i / QPS
if refreshing_until is not None and now >= refreshing_until:
expires, refreshing_until = refreshing_until + TTL, None
if now >= expires:
misses += 1
if refreshing_until is None:
db_calls += 1
refreshing_until = now + RECOMPUTE
continue
# -ln(U) is exponential with mean 1, so the early-refresh window scales with delta
if refreshing_until is None and now - RECOMPUTE * beta * math.log(random.random()) >= expires:
db_calls += 1
early += 1
refreshing_until = now + RECOMPUTE # old value keeps being served meanwhile
return db_calls, early, misses
print(f"one hot key, {QPS} reads/s, TTL {TTL:.0f}s, recompute {RECOMPUTE}s, 3 minutes:")
print(f" naive cache-aside : {naive():>5} DB queries")
calls, waited = coalesced()
print(f" request coalescing: {calls:>5} DB queries, but {waited:,} reads waited on a refill")
calls, early, misses = xfetch()
print(f" probabilistic early expiry: {calls} DB queries ({early} early), "
f"{misses} reads saw a cold key (the very first fill)")
# ---- Jitter: 10,000 keys all written at deploy time with the same TTL ----
def peak_refills_per_second(jitter):
expiries = Counter()
for _ in range(10_000):
ttl = 300 * (1 + random.uniform(-jitter, jitter))
expiries[int(ttl)] += 1
return max(expiries.values())
print(f"\n10,000 keys cached at the same moment, TTL 300s:")
for j in (0.0, 0.1, 0.2):
print(f" jitter +/-{j:.0%}: worst second sees {peak_refills_per_second(j):>6,} expiries")one hot key, 2000 reads/s, TTL 60s, recompute 0.4s, 3 minutes: naive cache-aside : 2400 DB queries request coalescing: 3 DB queries, but 2,400 reads waited on a refill probabilistic early expiry: 4 DB queries (3 early), 800 reads saw a cold key (the very first fill) 10,000 keys cached at the same moment, TTL 300s: jitter +/-0%: worst second sees 10,000 expiries jitter +/-10%: worst second sees 196 expiries jitter +/-20%: worst second sees 105 expiries
Read the output carefully, because it shows the trade-off between the fixes. Coalescing cuts database queries from 2,400 to 3 — but every reader that arrived during a refill still waited 400 ms, which shows up as a latency spike every minute. Probabilistic early expiry also makes a handful of queries, and after the first cold fill no reader ever sees an expired key, because someone always refreshed shortly before expiry. Jitter solves a different problem — many keys expiring together — flattening a 10,000-query second into about a hundred per second. In an interview, name the problem precisely ("one hot key" versus "many keys at once") and pick the matching fix.
Hot keys
Consistent hashing spreads keys evenly, but traffic is not spread evenly across keys. A celebrity's profile, a viral post or a flash-sale product can draw 100,000 reads a second — more than one cache node can serve — and all of it lands on the one node that owns the key.
- Detect them: sample keys at the client or proxy and track the top-k by rate (Redis has
--hotkeysfor LFU mode; most teams build a sampled counter). - In-process L1 cache: cache the hottest keys for 1–5 seconds in every app server. A thousand servers each asking once per second is 1,000 reads/s instead of 100,000.
- Key replication: store copies under
product:42#0…product:42#7and have readers pick a suffix at random, so eight nodes share the load. Writes must update or delete all copies. - Split hot write keys: a like counter taking 50,000 increments a second becomes 16 sub-counters incremented at random and summed on read.
- Push it to the edge: if the response is public, a CDN with even a 1-second TTL absorbs almost all of it.
Cache hit ratio — the arithmetic that matters
Hit ratio is the fraction of reads served from the cache. The intuitive view — "90% is good, 99% is a bit better" — badly understates the difference, because what the database feels is the miss ratio:
import math
# ---- Hit ratio: small changes at the top end are huge for the database ----
reads = 50_000 # reads/s at peak
cache_ms, db_ms = 0.5, 8.0
print(f"{'hit ratio':>9} | {'avg latency':>11} | {'DB reads/s':>10}")
for h in (0.80, 0.90, 0.95, 0.99, 0.999):
avg = h * cache_ms + (1 - h) * (cache_ms + db_ms) # a miss pays for both
print(f"{h:>9.1%} | {avg:>8.2f} ms | {reads * (1 - h):>10,.0f}")
# ---- Multi-tier: each tier sees only the misses of the tier above it ----
tiers = [("in-process (L1)", 0.60, 0.01), ("Redis (L2)", 0.90, 0.5), ("database", 1.0, 8.0)]
remaining, total, reached_db = 1.0, 0.0, 0.0
print()
for name, hit, ms in tiers:
reached_db = remaining
served = remaining * hit
total += remaining * ms # everyone who reaches a tier pays its latency
print(f"{name:<16} sees {remaining:>6.1%} of reads, serves {served:>6.1%}")
remaining -= served
print(f"combined cache hit ratio {1 - reached_db:.0%}, average read latency {total:.2f} ms")hit ratio | avg latency | DB reads/s
80.0% | 2.10 ms | 10,000
90.0% | 1.30 ms | 5,000
95.0% | 0.90 ms | 2,500
99.0% | 0.58 ms | 500
99.9% | 0.51 ms | 50
in-process (L1) sees 100.0% of reads, serves 60.0%
Redis (L2) sees 40.0% of reads, serves 36.0%
database sees 4.0% of reads, serves 4.0%
combined cache hit ratio 96%, average read latency 0.53 ms
Going from 90% to 99% looks like a 9-point improvement; for the database it is a 10x drop in load, from 5,000 reads/s to 500. That is often the difference between needing to shard and not. The same arithmetic warns you about a cache outage: at 99% the database is sized for 500 reads/s, so losing the cache sends it 100x its normal load. Plan for that — cache clusters with replicas, a circuit breaker that sheds load rather than letting every request fall through, and warm-up before a new cache node takes traffic.
The second half shows multi-tier caching: each tier only sees the misses of the tier above. A modest 60% L1 in front of a 90% L2 gives a combined 96% hit ratio, and the average read is dominated by the tiny in-process cost. To improve hit ratio: cache larger, more reusable units (a whole rendered card, not five rows), normalise cache keys (sort query parameters, drop tracking parameters), make TTLs as long as freshness allows, and size memory to the working set — the hot data, not the whole dataset.
Autoscaling
Autoscaling adds and removes instances automatically as load changes, so you pay for the capacity you need rather than for the yearly peak all year. Three flavours:
- Reactive (target tracking): keep a metric near a target — "average CPU at 60%", "200 in-flight requests per instance", "queue depth under 1,000". The scaler adds instances when the metric is above target and removes them when below.
- Scheduled: scale up before a known peak — 11:30 for lunch, 18:30 for dinner, the hour before a product launch.
- Predictive: forecast from historical patterns and scale ahead of the curve.
The catch with reactive scaling is lag: detecting the rise, launching an instance, booting it, warming it and passing health checks takes minutes. A dinner rush that rises faster than that overwhelms the fleet before help arrives:
import math
PER_INSTANCE = 800 # QPS one instance serves at 100% CPU
TARGET = 0.6 # scale to keep average utilisation near 60%
BOOT_MIN = 4 # minutes from "launch" to "passing health checks"
def desired(qps, min_n=3):
return max(min_n, math.ceil(qps / (PER_INSTANCE * TARGET)))
# Steady-state sizing across a day
for hour, qps in ((4, 1_200), (9, 6_000), (13, 14_000), (20, 22_000)):
print(f"{hour:02d}:00 {qps:>6,} QPS -> {desired(qps):>2} instances")
# A dinner rush: 6k -> 22k QPS in 8 minutes. Reactive scaling vs a scheduled pre-scale.
traffic = [6_000] * 3 + [6_000 + 2_000 * m for m in range(1, 9)] + [22_000] * 9
def run(prescale_to=0):
ready, pending, overloaded = desired(traffic[0]), [], 0
ready = max(ready, prescale_to)
for minute, qps in enumerate(traffic):
ready += sum(n for t, n in pending if t == minute) # instances finish booting
pending = [(t, n) for t, n in pending if t > minute]
util = qps / (ready * PER_INSTANCE)
if util > 1.0:
overloaded += 1 # requests queue / time out
want = desired(qps) - ready - sum(n for _, n in pending)
if want > 0:
pending.append((minute + BOOT_MIN, want)) # the scaler reacts now...
return overloaded, ready # ...but help arrives later
print()
for label, pre in (("reactive only", 0), ("pre-scaled to 40", 40)):
over, final = run(pre)
print(f"{label:<17}: {over} minutes above 100% utilisation, {final} instances at the end")04:00 1,200 QPS -> 3 instances 09:00 6,000 QPS -> 13 instances 13:00 14,000 QPS -> 30 instances 20:00 22,000 QPS -> 46 instances reactive only : 4 minutes above 100% utilisation, 46 instances at the end pre-scaled to 40 : 0 minutes above 100% utilisation, 46 instances at the end
Both runs end at the same 46 instances, but the reactive-only fleet spends four minutes above 100% utilisation — timeouts and errors — because instances launched at minute 4 are not ready until minute 8. Pre-scaling to 40 before the rush avoids it entirely. Other rules that separate a working autoscaler from a dangerous one:
- Target 50–70% utilisation, not 90%. The headroom absorbs a spike while new instances boot, and latency climbs steeply as utilisation approaches 100%.
- Scale out fast, scale in slowly, with a cool-down, so noisy metrics do not cause flapping.
- Pick a metric that tracks the bottleneck. CPU is wrong for an I/O-bound service; request concurrency or queue depth is usually better. Scale workers on queue age.
- Keep a floor of at least one instance per zone (three here), so a zone loss never leaves zero capacity.
- Autoscaling the stateless tier moves the bottleneck to whatever is stateful: 46 instances each holding 20 database connections is 920 connections. Plan for a connection pooler (PgBouncer) and caches before you scale the fleet.
- Shorten boot time: prebaked images, warm pools of stopped instances, and lazy cache warm-up.
Common mistakes
- Caching before measuring. Add a cache because the numbers say reads dominate and the data tolerates staleness — and state the TTL and invalidation plan in the same breath.
- No plan for a cold or dead cache. At a 99% hit ratio, the database is sized for 1% of reads. Say what happens when the cache goes away.
- Caching data that must be exact. Account balances, stock counts at checkout and permissions need a read from the source of truth at the moment of decision; caching them for display is fine.
- Sticky sessions as the scaling strategy. They hide state instead of removing it.
- Forgetting the balancer is a single point of failure, or that health checks that depend on a shared database can fail the whole fleet at once.
hash % Nfor cache sharding. Adding a node becomes a mass miss event; use consistent hashing.- Identical TTLs for everything written at once, followed by a synchronised expiry storm.
- "Just autoscale". Autoscaling has minutes of lag and moves the bottleneck to the database; it complements capacity planning, it does not replace it.
Practice
# Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
