ch07 · When adding servers stops helping

Builds on ch06.

The question

How far does a system scale, and how would you find out from the three measurements you have?

ch06 ended with a fleet too close to its margin and an obvious remedy: buy more machines. This chapter is about how much less that buys than the arithmetic promises. It is also about the count past which each new machine takes capacity away.

The material

Two costs, and only one of them is famous

Machines do not add up, and there are two separate reasons.

Contention. Some fraction of the work cannot be done in parallel: a lock, a single writer, a shared queue, a coordinator. That fraction takes a fixed share of every machine you add, so the cost grows with the count of machines, and the curve flattens. This is the famous one: Amdahl’s argument, and the ceiling it implies.

Crosstalk. Machines have to agree with each other. Every new one has to be told about all the others, so the cost grows with the number of pairs, not the number of machines.

Crosstalk does something contention never does. Contention flattens the curve. Crosstalk turns it over. Past some count, the next machine costs more in agreement than it brings in work, and the total goes down.

Both terms together are the universal scalability law [Gunther (2008)]:

  achievable_throughput:
    kind: derived
    unit: request/second
    label: throughput the fleet can actually reach
    note: >-
      The universal scalability law. One host's throughput times
      the count, divided by what contention and crosstalk take
      back. With crosstalk at zero it is Amdahl's ceiling; with
      both at zero it is the straight line above.
    formula: linear_throughput / (1 + contention * (host_count - 1) + crosstalk * host_count * (host_count - 1))

The curve, against the straight line

The dashed line is what a budget assumes. The solid one is what the machines do. They separate almost immediately. The dashed line leaves the top of the figure while the real curve is still climbing slowly, and then the real curve stops climbing.

Source — scaling-curve · sizing.evaluate

Read the last column: what each machine is worth. It falls the whole way down. By the peak, a machine contributes a fraction of what the first one did. Every machine after that contributes less than nothing.

The last row checks the peak twice. One figure comes from sweeping the model, the other from its two coefficients. The calculations are independent, and they agree. That agreement is why the closed form in problem 7.3 is worth having.

What doubling buys

Source — web_service-reference and web_service-twice_the_hosts · every input on a slider

Twice the hosts. Read down.

Utilisation halves, exactly as arithmetic says it should. Time spent queueing falls to about a quarter, because ch06’s division is not linear, and in this direction the non-linearity runs in your favour. The share of futures over the knee falls by more still.

Throughput goes up by about a third, for a doubling of the fleet. Efficiency falls by about a third at the same time. That is the same fact, counted from the other end.

So doubling a fleet is an excellent way to fix latency and a poor way to buy capacity. Those are different purchases. They are usually conflated, and the model tells them apart.

Both are in the graph, and so is the peak. Drag crosstalk and watch the peak move while the fleet you have stays where it is.

The utilisation you were quoted was optimistic

ch06 had no scaling term, so its utilisation was the work arriving divided by what the machines could do if each of them worked alone. They do not work alone. Some of their capacity is spent on each other, and the honest utilisation is the arriving work divided by what the fleet can deliver.

The model carries both numbers, side by side, on purpose:

  utilisation_including_coordination:
    kind: derived
    unit: dimensionless
    label: utilisation, counting coordination
    note: >-
      The same fleet's utilisation, worked out from what it can
      actually deliver rather than from what one host could deliver
      alone. It is higher than the row above, always, and the
      gap is the work the hosts are doing on each other's behalf.
    formula: peak_request_rate / achievable_throughput

At the reference point the two differ by half again. The queueing view is not wrong. It is optimistic, by a factor nobody notices until they measure the fleet at two sizes and find the second one disappointing.

Measuring the fleet at more than one size is also how the coefficients get fitted.

Fitting the coefficients from what you have

Three unknowns, so three measurements determine them exactly. You will usually have three: one machine on a bench, the fleet you are running, and the fleet you were running before you grew it. That is not much data, and it is what exists.

Problem 7.2 is the algebra. Do it by hand once. Rearranging the law into a straight line shows why three points are the minimum, and why they must be at different counts. Two measurements at the same size determine nothing at all.

Then notice what you have done. You have extended a two-parameter curve out to hundreds of machines from three points clustered at the low end, and you are about to spend money on the extrapolation. The coefficients in this book’s model are assumptions, and they say so in their provenance. The shape is the claim. The position of the peak is a guess.

What this cannot tell you

Where your peak is. The coefficients here are assumptions, and the peak follows from them. The model’s own interval on the peak spans more than a factor of three. Fitting the coefficients from three measurements gives numbers with the same problem and a false air of precision. What transfers is that a peak exists, and that it is a property of the software.

Whether the coefficients are stable. They are fitted from a system doing one kind of work at one size. A different workload mix has a different serial fraction. A version that adds a coordination round has different crosstalk. A curve fitted last year describes last year’s software.

What to do about it. The law says where scaling stops paying. It has nothing to say about which lock to remove, and removing the lock changes the coefficients in a way only another measurement can establish.

Anything about failure. Every figure above is a healthy fleet. Machines coordinating while one of them is unreachable behave differently and worse, and this model has no term for it. ch11 is where that gets a margin rather than a model.

Whether the fleet is even the constraint. The whole chapter assumes throughput is what you are buying. If the system is bounded by something else, a database, a licence or a single-threaded step, the curve above describes a queue in front of the real problem.

Problems

Four, in tests/when_adding_servers_stops_helping/. The first three have tests. The last does not, and says why.

7.1 — Write the law. Two terms in the denominator, behaving differently. The tests check that contention alone flattens the curve and that crosstalk alone turns it over, so the two cannot stand in for each other.

def throughput(
    hosts: np.ndarray | float, one_host: float, contention: float, crosstalk: float
) -> np.ndarray:
    """Problem 7.1 - the scalability law, written out.

    ``one_host`` is what a single machine achieves alone. ``contention`` is the fraction of the
    work that cannot be done in parallel. ``crosstalk`` is the cost of machines having to agree
    with each other. Return the throughput of ``hosts`` machines.

    Two terms in the denominator and they behave differently, which is the whole of the chapter:

    * contention costs a fixed share of every machine you add - it grows with the *count*, and it
      flattens the curve;
    * crosstalk is machines coordinating with each other, so it grows with the number of *pairs* -
      and it is what makes the curve turn over and come back down.

    With crosstalk at zero you have Amdahl's ceiling: the curve flattens and stays flat. With both
    at zero you have the straight line nobody has ever measured.

    The test checks it against the sweep the book publishes, so it has to be the model's formula
    and not one that happens to be close near the middle.
    """
    raise NotImplementedError("problem 7.1")

7.2 — Fit it from three measurements. Rearrange the law until it is linear, then solve. Write the rearrangement down before you code it.

7.3 — Find the peak. Differentiate and set to zero. It comes out as a square root, and it says the peak belongs to the software rather than to the budget. Handle zero crosstalk honestly: there is no peak, and a large number is not the same answer.

Both are checked by one file, because the peak is what the fit is for:

def fit(measurements: list[tuple[float, float]]) -> tuple[float, float, float]:
    """Problem 7.2 - the two coefficients, from measurements somebody could actually take.

    ``measurements`` is a list of ``(hosts, throughput)`` pairs. You will usually have three: one
    machine, the fleet you have, and the fleet you had before you grew it. That is not much
    data and it is what exists.

    Return ``(one_host, contention, crosstalk)``.

    Three unknowns, so three measurements determine them exactly - solve, do not optimise. With
    the one-machine measurement in hand, ``one_host`` falls straight out, and the remaining two
    come from two linear equations once you rearrange the law to put the denominator on the other
    side. Write the rearrangement down before you code it; it is the part worth understanding.

    Then notice what you have done. You have fitted a two-parameter curve, extending to hundreds
    of machines, from three points clustered at the low end. ch07 says what that is worth.
    """
    raise NotImplementedError("problem 7.2")

def peak_hosts(contention: float, crosstalk: float) -> float:
    """Problem 7.3 - where adding machines stops helping.

    Return the host count at which throughput is greatest, from the two coefficients alone.

    Differentiate your answer to 7.1 with respect to the host count and set it to zero. It comes
    out as a square root and it is worth the five minutes: it says the peak is a property of the
    *software* - of how much it serialises and how much it coordinates - and that no budget moves
    it.

    Handle zero crosstalk. With no coordination cost the curve never turns over, and the honest
    answer is that there is no peak: raise, or return an infinity. A large number is not the
    same answer.
    """
    raise NotImplementedError("problem 7.3")

7.4 — The time adding machines did not help. No test: the measurements are your fleet’s, and this repository has none of them.

Somewhere in your organisation there is a tier that got a bigger fleet and did not get proportionally faster. Find its throughput at two fleet sizes, and a single machine’s on a bench if anyone ever ran one. Those are the three measurements the chapter says everyone has. Run problem 7.2 on them and write down where the peak comes out.

Then write down which of this chapter’s two costs the numbers point at: contention for something shared, or the cost of machines agreeing with each other. If the fit says neither, you have found a third mechanism, which is more interesting than the chapter.

A good answer names the tier, the fleet sizes and their throughputs, the peak the fit implies, and why you would not spend money on that peak. If you cannot find throughput at two sizes, that is an answer too. It means nobody measured throughput per host when the fleet grew, and the next growth is the chance to.

Where to go next

Gunther’s paper [Gunther (2008)] derives the law from a queueing argument rather than by fitting a curve to data. Read it if the crosstalk term has so far felt like a free parameter.

ch08 is what this chapter and the last one have in common: a point where the chain of multiplications stops describing the system, and no care over the inputs would have warned you.