Week 3: Scalability Fundamentals

1. Vertical vs. Horizontal Scaling & Statelessness

Vertical scaling ("scaling up") means making a single machine more powerful — more CPU, more RAM, faster disks. It's the simplest possible response to load: no architecture changes, no distributed systems problems. But it has a hard ceiling — there's a largest instance size a cloud provider sells — and the cost curve is rarely linear: doubling a machine's specs often costs more than double, and a single powerful machine is still a single point of failure. Horizontal scaling ("scaling out") means adding more machines rather than making one machine bigger. It has no hard ceiling, and a pool of many smaller machines survives the loss of any one of them — but only if the system is built to support it.

That "built to support it" condition comes down to statelessness. A stateless app server keeps no request-specific data in its own memory between requests — session data, in-progress uploads, anything a later request from the same user might need is stored externally (a database, a distributed cache like Redis), not on the instance that happened to handle the first request. This matters because a load balancer distributing requests across a horizontally scaled pool cannot guarantee the same server handles every request from the same user. A stateful service that stores a user's session only in local memory forces "sticky sessions" — pinning a user to one specific server — which reintroduces a single point of failure per user and undermines the whole point of having a pool.

Stateful (session stored in-process):
  Request 1 (login)      -> Server A (creates session in local memory)
  Request 2 (view cart)  -> Server B (no idea who this user is!)
  Fix attempt: "sticky sessions" pin this user to Server A forever
  Problem: if Server A dies, this user's session is gone

Stateless (session stored externally, e.g. Redis):
  Request 1 (login)      -> Server A -> writes session to Redis
  Request 2 (view cart)  -> Server B -> reads session from Redis
  Any server can handle any request; any server can be lost or
  added without affecting where a user's session data lives

This is why "make the service stateless" is one of the first moves in almost any scaling discussion: it's what makes horizontal scaling actually work, rather than just adding servers that can't share load correctly.

2. Load Balancing Algorithms

A load balancer needs a rule for picking which server gets the next request. Three algorithms come up repeatedly in interviews, each suited to a different situation.

Round robin cycles through the server pool in fixed order, sending each successive request to the next server. It's simple and requires no state about server load — but it assumes every request costs roughly the same amount of work, which is often false.

Servers: [A, B, C]
Request 1 -> A     Request 4 -> A
Request 2 -> B     Request 5 -> B
Request 3 -> C     Request 6 -> C

Problem case: if request 1 is a slow report-generation call
that ties up Server A for 10 seconds, round robin keeps sending
Server A a new request every 3rd turn regardless -- it has no
idea Server A is still busy.

Least connections tracks how many active (in-flight) connections each server currently has, and routes each new request to whichever server has the fewest. This adapts naturally when request costs vary — a server stuck on a few slow requests simply stops receiving new ones until it catches up — at the cost of the load balancer having to maintain live connection counts per server.

Servers with active connection counts: A=1, B=0, C=0
(Server A is mid-way through the slow report request)

Request 2 -> B (0 connections, tied for fewest)
Request 3 -> C (0 connections, tied for fewest)
Request 4 -> whichever of B/C currently has fewer active
             connections -- NOT A, until A's count drops

Consistent hashing solves a different problem: routing requests (or keys) to servers in a way that stays stable when the pool of servers itself changes size. Servers and keys are both hashed onto positions on a conceptual ring (0 to a large maximum value); a key is assigned to the first server found walking clockwise from the key's position. When a server is added or removed, only the keys between it and the next server on the ring need to move — not the entire keyspace.

Ring positions (0-100), servers placed by hash(server_id):
  Server A @ 10    Server B @ 40    Server C @ 75

Key "user:42" hashes to 55 -> walk clockwise -> lands on
Server C (first server at or after position 55)

Now add Server D @ 60:
  Key "user:42" (still at 55) -> now lands on Server D instead
  Only keys between 40 and 60 (previously C's territory) move.
  Keys elsewhere on the ring are completely unaffected.

Compare to plain hash % N routing: adding one server changes N,
which reshuffles almost every key's assigned server -- the whole
reason consistent hashing exists.

In practice, consistent hashing implementations add many virtual nodes per physical server scattered around the ring, which spreads load more evenly than one hash position per server could. This exact ring idea reappears in Week 5 when sharding a database across nodes — it's the same problem (minimize data movement when the number of nodes changes) applied one layer down.

3. Failure Modes: Thundering Herd & Hot Partitions/Hot Keys

Thundering herd happens when a large number of clients or processes all act at the same instant in response to the same trigger, overwhelming a shared resource that could have handled the same total load spread over time. The classic example: a popular cache key expires, and the next instant, thousands of concurrent requests all miss the cache simultaneously and all hit the database at once trying to recompute the same value — a spike the database was never sized for, caused entirely by synchronized timing rather than by any real increase in traffic.

Without mitigation:
  T=0:    10,000 req/sec hitting a hot cached key, all cache hits
  T=60s:  key's TTL expires
  T=60.001s: next ~10,000 requests ALL miss the cache and ALL
             query the database at once for the same key

Mitigation 1 -- jittered TTLs:
  Instead of a fixed 60s TTL, use 60s +/- random(0, 10)s so
  requests recompute at slightly different times, not all at once

Mitigation 2 -- request coalescing / locking:
  First request that misses acquires a lock and recomputes;
  concurrent requests for the same key wait on that lock and
  reuse its result instead of each hitting the database themselves

Hot partitions (also called hot keys) are the opposite kind of imbalance: instead of load spiking everywhere at once, load concentrates on one specific shard or cache key far beyond what the others receive — a celebrity account's posts, a viral product listing, a single Black Friday deal — even though the overall system-wide average load looks perfectly healthy. Because sharding and consistent hashing assign a key to exactly one owning node, an unusually popular key can overload that single node while every other node in the same cluster sits nearly idle.

100 shards, evenly distributed traffic assumption:
  average load per shard ~ total_qps / 100

Reality with a hot key (one viral post's shard):
  99 shards: ~1x average load each (healthy)
  1 shard (owns the viral post): ~10x average load
  -> that single shard becomes the bottleneck and can fail or
     throttle, even though 99% of the cluster has capacity to spare

Mitigations:
  - Key splitting: replicate/shard the hot key's data across
    several nodes and merge results (fan-out reads)
  - Add a lightweight local cache in front of the hot key so
    most reads never reach the owning shard at all
  - Randomize/salt the hot key into several sub-keys distributed
    across nodes, reassembling on read

4. Hands-on Exercise

5. Knowledge Check

Four quick questions. Expand each to check your answer.