Amdahl's Law

Pradeep P
3 days ago
3 min read

Series: Modern System Design · Layer 1 — The building blocks

Layer 1 · Post 18 of 21

← Previous: Little's Law → Next: Consistent Hashing

Layer 1 — The building blocks · Post 91 of 119

Speedup is limited by the part of the work you cannot parallelize.

What you'll learn

The serial-fraction formula, without pretending you will compute it in production
Why "just add more machines" stops helping
How this applies to request paths, not only CPU cores

The idea in one minute

Amdahl's Law (Gene Amdahl, 1967): if a fraction s of the work is serial (must happen in order, on one place), and you speed up the rest with N parallel workers, the overall speedup is at most

1 / (s + (1 − s) / N)

As N → ∞, speedup → 1/s. If 10% of the request is serial, you will never get more than 10×, no matter how many shards you add.

Request:  [ serial 10% ][ parallel 90% ................ ]
More boxes help this half. They do not shrink the serial 10%.

Post 3 (horizontal vs vertical scaling) is the product version of this. Amdahl is why the product version has a ceiling.

Why it matters

Distributed systems are full of serial bottlenecks: a single primary, a global lock, a coordinator, a "load all rows then fan out," a user-facing request that must wait for the slowest of 50 backends (Tail at Scale, later).

Interviews: they want you to find the serial part before you draw 50 boxes. "We'll shard" is not an answer if the hot path is one user ID or one leader.

How it works

Identify s. In a web request, s is everything that cannot overlap: auth against one session store with a lock, a single-row update on an unsharded key, a 2PC coordinator, a GPU that runs one model load at a time.

N is not "number of servers." N is how much you can actually overlap that parallel slice. Eight app servers in front of one Postgres primary is N ≈ 1 for writes.

Universal Scalability Law (USL) is Amdahl plus crosstalk: as you add nodes, they spend more time coordinating. Speedup can go down. Consensus, cross-shard transactions, and chatty RPCs are crosstalk.

Gustafson's Law is the optimistic twin: if you grow the problem (more users, more data) as you add machines, the serial part can be a smaller fraction of a bigger job. Batch analytics often looks like Gustafson. A single user's HTTP request often looks like Amdahl.

A simple example

A search request:

Auth: 5 ms (one session store)
Fan-out to 20 index shards: 40 ms if parallel
Merge + rank on the coordinator: 20 ms
Write a metric: 5 ms on the critical path

The parallel piece is (2). The serial pieces are 1, 3, 4 — 30 ms that more shards do not touch.

If (2) was 200 ms on one shard and you split to 20, you might cut that toward 40 ms. You still pay 30 ms. Adding a 21st shard does almost nothing. To go faster you must shrink merge, move metrics off the path, or cache auth — attack s.

A worse version: all queries for tenant=acme hit one shard. Then N is 1 for that tenant no matter how many machines you bought. That is hot keys (Post 94).

Common mistakes

Horizontal scaling as a personality. More replicas of a service that all wait on one lock is vertical scaling with extra YAML.

Parallelizing the wrong 90%. Speeding up a background job does not help the user-visible serial handshake.

Ignoring coordination cost. Two-phase commit, global secondary indexes, and "query all shards" add s and crosstalk as you grow N.

Using Amdahl to refuse all scaling. If s is 1% and you are at N=2, you still have a lot of room. Measure. Then hunt the serial 1% when returns flatten.

How this shows up in real systems

Single-primary databases: write speedup capped by one writer (unless you shard or go multi-primary with a conflict story).
MapReduce / Spark: reducers and a driver; too few reduce keys and you wait on one task.
GPU inference: batching helps throughput (Little's Law); one huge model load is serial for that replica.
Kubernetes control plane: many workers, one etcd cluster. Scale the API server; etcd is closer to s.

Recap

Speedup is bounded by the serial fraction. Infinite machines cannot erase it.
Find s on the user path before you add boxes.
Next: a hashing trick that at least keeps resharding from becoming a serial nightmare — consistent hashing.