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.

flowchart LR U[Users] --> DNS[DNS / GeoDNS] DNS --> CDN["CDN edge
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)
HowResize to a larger instanceAdd instances behind a load balancer; partition data
Code changesNoneServices must be stateless; data must be partitionable
CeilingThe biggest machine you can buy (hundreds of cores, a few TB of RAM)Practically none for stateless tiers
Cost curveLinear, then steep at the top endRoughly linear, plus coordination overhead
FailureOne box = one point of failureLosing one box loses 1/N of capacity
ResizeUsually a restart or failoverAdd or remove instances live
Best forRelational primaries, early-stage products, anything with heavy joins or transactionsWeb 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:

StateWrong placeRight place
Login sessionIn-memory session map on one serverSigned token (JWT) the client carries, or a session store in Redis
Uploaded filesThe server's local diskObject storage (S3, GCS), referenced by key
Shopping cart, draftsProcess memoryDatabase or Redis with a TTL
Background jobsAn in-process thread or timerA queue with durable messages (see queues and APIs)
WebSocket connectionsUnavoidably on one serverA 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)
SeesIP addresses, ports, TCP/UDP connectionsFull HTTP: path, host, headers, cookies, body
Can route byConnection 5-tuple only/api vs /static, host name, header, user cohort for canaries
TLSPasses it through (or terminates, on some products)Terminates it, so it can read the request
ExtrasVery little — that is the pointRetries, rate limiting, auth, compression, caching, request rewriting
CostMillions of connections per box, microseconds of added latencyMore CPU per request, sub-millisecond to a few ms of added latency
BalancesPer connection — one long-lived connection always goes to one serverPer request — even across one HTTP/2 or gRPC connection
Use forRaw TCP (databases, MQTT, game servers), extreme throughput, in front of L7 fleetsWeb 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()})
Output
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 /healthz every 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())
Output
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 proxyReverse proxy
Acts forThe clientsThe servers
Who configures itThe client side (a company network, a browser setting)The service owner
Who is hiddenThe client's identity from the internetThe backend topology from clients
Typical jobsEgress filtering and policy, shared caching of downloads, logging, anonymity, controlled outbound access from a private networkTLS termination, load balancing, caching, compression, routing, rate limiting, auth, request buffering against slow clients
ExamplesCorporate web proxy, Squid, an egress gateway for outbound API callsNginx, 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:

LayerWhat it holdsLatencyScope
Browser / mobile appStatic assets, API responses per Cache-Control / ETag0 ms (no network)One user
CDN edgeImages, JS/CSS, video segments, cacheable public GETs5–30 ms from the userEveryone near that edge
Reverse proxyRendered pages, API responses<1 ms from the appOne datacenter
In-process (L1)Hot config, feature flags, the hottest objects~100 ns–10 µsOne process
Distributed cache (L2)Sessions, objects, query results, computed feeds0.2–1 msAll app servers
Database buffer poolHot pages and indexesInside the query timeThat 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 CDNPush CDN
How content arrivesOn the first request, the edge fetches from your origin and caches itYou upload content to the CDN ahead of time
First requestA miss: slow, and it hits the originAlways a hit
FreshnessControlled by TTLs (Cache-Control) and purgesYou re-upload when content changes
Storage costOnly what users actually requestEverything you push, whether requested or not
Operational effortLow — point the CDN at the originHigher — a publishing pipeline
Best forWebsites, images, API GETs, long-tail content with unpredictable popularityLarge 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:

PatternRead pathWrite pathStrengthWeaknessUse for
Cache-aside (lazy loading)App checks cache; on a miss reads DB and fills cacheApp writes DB, then deletes the cache keySimple; cache holds only what is read; cache outage degrades to DB readsFirst read after a write is a miss; stale window if invalidation failsThe default for most read-heavy data
Read-throughApp asks the cache; the cache library loads from DB on a missUsually combined with write-through or invalidationLoading logic lives in one placeNeeds a cache layer that supports loadersWhen a caching library or provider does it for you
Write-throughReads hit a warm cacheWrite cache and DB synchronously, then acknowledgeCache is never stale for keys written through itEvery write pays both latencies; caches data that may never be readData read soon after writing: profiles, settings
Write-behind (write-back)Reads hit the cacheWrite cache, acknowledge, flush to DB later in batchesVery fast writes; coalesces many updates into oneData loss if the cache dies before flushing; complex orderingCounters, view counts, metrics — where losing a few seconds is acceptable
Write-aroundCache-aside on readsWrite DB only; skip (and invalidate) the cacheDoes not flood the cache with write-once dataReading just-written data is a missLogs, 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}")
Output
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}")
Output
   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%}")
Output
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:

  1. TTL only: accept staleness up to the TTL. Perfect for data that is fine a minute old (a feed, a product listing).
  2. 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.
  3. 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.
  4. 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.
  5. Pub/sub broadcast: for in-process L1 caches on many servers, publish "key X changed" and every server drops its copy.
  6. 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")
Output
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 --hotkeys for 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#7 and 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")
Output
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")
Output
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 % N for 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.

Up next · Lesson 4Choosing and Scaling DatabasesSQL vs NoSQL, replication, sharding, CAP and when to denormalize.