Patterns in CS System Design - Cat · Code

Add machines, add cores, add people—how much faster does it actually get? Amdahl's law gives you the ceiling, the Karp–Flatt metric helps you diagnose bottlenecks from your load-test data, and the USL explains why performance drops after you scale past a certain point. Pair those with Little's law and queueing theory, and capacity planning stops being guesswork and becomes something you can actually calculate.

Every law in this article comes with an interactive chart or calculator. All the numbers are editable, and the tables recalculate as you go.

1. Amdahl's Law: Total Time Is the Sum of Its Parts

Speeding up one part only helps so much, because the parts you don't speed up hold the whole thing back. Take single-core total time as 1, with a parallelizable fraction $p$ and a serial fraction $1 - p$ :

The serial part stays put: $1 - p$
The parallel part is split across $N$ cores: $p / N$

T(N) = (1 - p) + \frac{p}{N}, \qquad S(N) = \frac{1}{(1 - p) + p / N}

As $N \to \infty$ , $S \to 1 / (1 - p)$ : with 10% serial, the speedup ceiling is 10×.

Generalizing to multiple parts

Each part can have its own speedup factor. The overall speedup is:

S = \frac{1}{\sum_i f_i / s_i}

$f_i$ is the fraction of time spent in part $i$ , and $s_i$ is its speedup factor. Take a single request:

Stage	Share of time	Speedup after optimization	Time after optimization
Parse request	20%	unchanged	0.20
Query database	50%	add cache, 5×	0.10
Render result	30%	parallelize, 3×	0.10
Total	100%		0.40

Overall speedup = 1 / 0.40 = 2.5×. Even if you made "parse request" infinitely fast, total time would only drop from 0.40 to 0.20. In the calculator below, change each stage's share and speedup factor (drag to the far right for infinitely fast) and watch how the overall speedup and the last column's ceiling change:

Amdahl calculator: which stage should you optimize?

Tip

You can work out which stage to optimize directly: look at how much time each stage takes, then at how much it can be sped up. The last column tells you "if this stage were pushed to the limit, how much faster could the whole thing get"—a more reliable guide than intuition.

2. The Karp–Flatt Metric: Back Out the Serial Fraction from Measured Data

In real projects $p$ is usually unknown. Measure the speedup $S$ , back out the "measured serial fraction" $e$ , then watch how $e$ changes with $N$ to tell which kind of bottleneck you have.

e = \frac{1/S - 1/N}{1 - 1/N}

N	Case A: measured S	A's e	Case B: measured S	B's e
8	5.0×	0.086	5.0×	0.086
16	7.0×	0.086	6.0×	0.111
32	8.8×	0.085	5.5×	0.155

e stays constant (Case A): the bottleneck is fixed serial code, consistent with the Amdahl model. Find that serial logic and shorten it.
e grows with N (Case B): the bottleneck is coordination overhead—lock contention, cache coherence, cross-node communication. Adding more cores actually hurts; the USL in the next section explains it.

Plug your own load-test results into the table below and it will compute e for each N and give you a verdict:

Karp–Flatt: diagnose bottlenecks from measured speedup

Case B also shows something else: $p$ is not a constant. Synchronization overhead makes the effective $p$ drop as $N$ grows, while larger data volumes usually push the parallel fraction up. So extrapolating 32-core performance from a single-machine $p$ is often wrong—measure at each $N$ .

3. The USL: Why Performance Drops After You Add Machines

Amdahl's curve only flattens out. The Universal Scalability Law (USL), proposed by Neil Gunther, adds one more term. As long as the coherence cost $\beta > 0$ , the throughput curve has a peak:

C(N) = \frac{N}{1 + \alpha (N - 1) + \beta N (N - 1)}

α (contention): queueing for a shared resource, such as a global lock or a single primary database. This is the serial part in Amdahl's law.
β (coherence): the cost of nodes synchronizing state with each other, growing as $N^2$ .

The node count at the peak:

N^* = \sqrt{(1 - \alpha) / \beta}

With α = 0.05 and β = 0.001, the peak is around 31 nodes. Drag the sliders below to see how α and β each change the curve:

USL vs. Amdahl: throughput as a function of node count