Amdahl and Gustafson Bounds in Capacity Models

Adding a replica is supposed to add capacity in proportion. It rarely does, and the shortfall is not a mystery: some part of every request passes through a resource that exists once. A lock, a sequence generator, a shared database row, a network link, or a coordination round trip serializes the work that touches it, and the serialized part sets a ceiling that the parallel part can approach but never pass. Amdahl’s formulation of that ceiling is the reason capacity plans should be written against a measured scaling curve rather than a linear extrapolation of a load test at small size.

The fixed-workload bound

Let $p$ be the fraction of the work that can proceed in parallel and $1-p$ the fraction that cannot. With $n$ times as much capacity, the time to complete a fixed amount of work becomes

$$T(n) = (1-p)T(1) + \frac{p,T(1)}{n}$$

The speedup $T(1)/T(n)$ approaches $1/(1-p)$ as $n$ grows. If one percent of the work is serial, the ceiling is a hundredfold; if ten percent, tenfold. The bound is not about overhead growing with $n$; it is present even with zero coordination cost, and it is derived purely from the arithmetic of a fixed total divided into a serial and a parallel part.

In capacity terms, the translation is direct. Capacity is inverse time, so the throughput ceiling for a fixed request mix is $1/(1-p)$ times the throughput of one replica, and a fleet sized above that ceiling has replicas that are individually underutilized no matter how many are added. The resource on which the serial fraction sits is the true bottleneck, and it is usually not the resource that monitoring highlights: CPU graphs of the front-end fleet look healthy while the shared database’s connection slots are the thing that sets the ceiling.

The danger of the bound is that $1-p$ is almost never measured directly. It is inferred by fitting a curve to observed scaling, and the fit is unstable because the serial fraction usually grows with $n$ as coordination and contention increase. The measured ceiling is therefore an overestimate of what larger deployments will achieve, not an estimate of the asymptote.

Scaled workload and the Gustafson view

Gustafson’s argument is that the fixed-work problem is the wrong problem for capacity. Adding machines is done to handle more work, not to finish the same work sooner, and the workload grows with the capacity available. If the serial portion stays constant in duration while the parallel portion grows with $n$, the speedup becomes

$$S(n) = n - (1-p’),n = 1 + (n-1)p’$$

where $p’$ is the parallel fraction of the scaled execution. This expression grows linearly without a ceiling, which is a statement that a workload that scales with the fleet can use a fleet of any size.

For capacity planning, both views are needed simultaneously and they answer different questions. Amdahl answers “how much more traffic can this architecture carry with the same per-request work”, and the answer has a ceiling. Gustafson answers “what does scaling buy when work per request also changes with the size of the system”, and the answer is linear only as long as the serial work per unit time does not grow. The serial work does grow in most real systems, because the number of coordination operations per request rises with the number of participants, so the practical curve lies between the two and bends away from linear at the point where coordination stops being amortized.

The reconciliation matters because it explains a common observation: a service that scales to eight replicas and then stops absorbing additional load is not necessarily broken. It may be behaving exactly as a fixed-work model predicts, with a serial fraction around twelve percent. What the model does not tell you is which part is serial, and that diagnosis requires measuring concurrency and waiting time at each candidate shared resource. Little’s Law, as a consistency check, is the tool for that: Little’s Law as a Consistency Check on Load Measurements describes how its violation localizes work that is not being counted where it should be.

Usable scalability as an operational limit

Scalability is typically reported as an efficiency curve: throughput at $n$ replicas divided by $n$ times the throughput at one. Perfect scaling is 1.0 at every $n$. Real curves fall, and the useful operating range is often defined as the point where efficiency drops below a threshold, commonly around 0.7 to 0.8, at which adding a replica returns a diminishing but still material share of its nominal capacity.

The threshold matters less than the shape. Two systems can both reach 0.75 efficiency at sixteen replicas and behave very differently at thirty-two: one continues to decline gently, the other falls off a cliff when a shared resource crosses into saturation and queueing produces the nonlinear latency growth described in Utilization Targets and the Knee of the Latency Curve. Sizing past the cliff is worse than sizing below it, because the system at high replica count not only fails to add throughput, it also adds tail latency as coordination queues lengthen.

def fit_speedup(counts, throughputs):
    # Amdahl: T(n) ~= (1-p) + p/n  (in units of single-replica time)
    # Throughput(n) = 1/T(n) times baseline, so p is recovered by least squares.
    import statistics
    pts = [(1 / t, 1.0 / n) for n, t in zip(counts, throughputs)]
    mean_x = statistics.mean(x for x, _ in pts)
    mean_y = statistics.mean(y for _, y in pts)
    cov = sum((x - mean_x) * (y - mean_y) for x, y in pts)
    var = sum((x - mean_x) ** 2 for x, _ in pts)
    p = cov / var if var else 0.0
    serial = max(0.0, 1.0 - p)
    return {"parallel_fraction": p, "ceiling_multiplier": 1 / serial if serial else float("inf")}

The fit is a diagnostic, not a prediction. Its value is that it converts a table of numbers into two parameters whose plausibility can be judged: a serial fraction of two percent corresponds to a specific, findable serialization path, while a serial fraction of thirty percent suggests that the scaling test itself was contaminated by a per-request startup cost that does not exist in production.

Serial resources and their disguise

The serial fraction of a request takes several forms, and the two most misleading are those that appear parallel but are not.

A shared cache under a global lock serializes all lookups, however many front-end replicas exist, and its capacity is one core’s worth of hash-table operations. Sharding it removes the bound but changes the hit rate, because a request now has to know which shard to ask; the trade is capacity for either routing state or cache misses, and the point of the shard count is to be chosen from the measured contention rather than from symmetry.

An append-only log with a single writer serializes all writes in the system, and its capacity is set by the rate of sequential append, which is high but finite. Readers scale; the writer does not. Any architecture whose durable state is a single log therefore has a throughput ceiling equal to the log’s append rate, and the only remaining question is whether the ceiling is far enough above forecast demand to be irrelevant during the plan’s lifetime.

A more subtle form is the fan-out operation. A request that must ask fifteen services has a latency governed by the slowest of the fifteen, and the effective capacity of the caller is set by the tails of all of them rather than by its own capacity. This is not serialization in the strict sense; it is a variance amplifier, and it is why pool sizing for fan-out callers follows different rules than for peer-to-peer ones.

The fourth form is the one capacity plans most often miss: the shared resource that is not in the request path at all, such as the deployment system, the configuration service, or the DNS resolver. These do not appear in a per-request scaling model, but they bound how fast the fleet can grow, which turns into a provisioning-lag term in the plan. The lag arithmetic is in Provisioning Lag and the Reaction Time of a Fleet.

Coordination cost and the series that diverges

Both laws treat the serial fraction as a constant. The reason a measured scaling curve bends more sharply than either law predicts is that coordination work is a function of the participant count, so the serial term grows with $n$ rather than staying fixed. If every replica must exchange a message with every other replica, the coordination work per unit time grows as $n^2$ while the useful work grows as $n$, and a model with a growing serial fraction has a maximum rather than an asymptote: throughput rises, peaks, and then declines as coordination work displaces useful work.

Gossip protocols and tree-structured aggregation reduce the exponent to $n \log n$ or $n$, which moves the peak out and makes the curve flatter, and they do so at the cost of extra latency per coordination round. The design choice is thus between a system that scales further with more latency and one that scales less far with less. Where the capacity plan needs the former, the plan must also account for the added latency per request, since the utilization target is derived from a latency objective that the coordination round consumes.

Leases, leader election, and distributed locks sit at the worst end of this trade, because each acquisition is a round of coordination whose cost grows with the number of contenders and whose failure mode at high contention is a storm of retries. A system whose write path takes a distributed lock per request has a serial fraction that is itself load-dependent, and no fixed parameter fit will describe it. The honest model for such a system is the measured curve, extended only as far as the measurements go.

The practical consequence is a rule about how far a scaling test should be extrapolated. A fit is meaningful across the range in which the coordination structure does not change. Crossing the point where replicas stop being able to reach all peers directly, or where the coordinator’s own capacity becomes the constraint, invalidates the fit even though the arithmetic still produces a number.

What the bounds justify

The models justify one concrete practice: never extrapolate capacity linearly from a scaling test without fitting the curve and finding the bending point. They justify a second: report the scaling efficiency of every tier, because the tier with the lowest efficiency determines where the next doubling stops paying. And they justify a third that is easy to forget: the serial fraction is a property of the request path and the shared state, both of which change with architectural decisions, so a ceiling measured last quarter is not a ceiling for the current design.

What the models cannot do is tell you how far to scale. They describe what happens at a given count, not what count is needed, and the needed count comes from demand forecasting and the headroom arithmetic that converts demand into replicas. The value of the bound is that it caps the answer: if demand growth requires more than the ceiling allows, the capacity plan must include an architectural change, and no amount of additional hardware will substitute for it.