ch05 · Little’s law

Builds on ch04.

The question

What can you infer about a system from the one relationship that is always true, and what can you not?

Part I ended with a rate: how much work arrives at the busy hour. This chapter turns that rate into a count of requests in flight. It also turns a count of requests in flight back into the time each request spent in the system, queues included. It assumes nothing about how the system works.

The material

The law

The number of requests in a system is the rate they arrive at, times how long each one stays.

  service_seconds:
    kind: derived
    unit: second
    label: service time
    note: >-
      service demand with the core divided out: how long one request
      would take alone
    formula: service_demand * one_request / one_core
  in_flight_unqueued:
    kind: derived
    unit: request
    label: requests in flight, if none waited
    note: >-
      Little's law with the residence time equal to the service
      time: the fewest requests that can be in the system at this
      arrival rate. ch06 replaces the service time with what a
      request actually waits, and this number goes up.
    formula: peak_request_rate * service_seconds

That is the whole of it. One multiplication, and a label that is doing a lot of work. If none waited is the time each request stays as this chapter leaves it: the time a processor spends on it and nothing else. ch06 adds the waiting, and this number goes up.

The law earns a chapter for what it leaves out. It says nothing about how requests arrive: they may be bursty, periodic or adversarial. Nothing about the order they are served in. Nothing about the shape of anything. No queueing model, no exponential anything.

It has one condition. The system is in a steady state over the window you are looking at: as much going out as coming in.

What a request costs, and how busy that makes the fleet

Little’s law needs a rate and a time. ch04 supplied the rate. The time is the first quantity in this book that belongs to the software rather than to the workload:

  service_demand:
    kind: input
    decided: world
    unit: second * core / request
    label: CPU time per request
    note: >-
      Core-seconds of work one request costs, which is not how
      long a request takes. A request that occupies one core for
      twelve milliseconds has a service demand of twelve milliseconds
      whether it returns in twelve milliseconds or in twelve seconds
      — the difference is queueing, and Part II is about that
      difference.

      This is the model's one rate constant and it belongs on
      a rig (ch03). No rig is declared, so it is held here as
      an assumption whose source says what would replace it, rather
      than as a measured node with nothing behind it.
    distribution:
      triangular:
        minimum: 0.008
        likely: 0.012
        maximum: 0.02
    provenance:
      kind: assumption
      source: >-
        held as an assumption because no reference machine is
        declared in rig/machine.yml; `make measure-rig` on a declared
        machine replaces this node with a measured one. Triangular
        *because* it has not been measured: once it is, the shape
        becomes a normal around the measurement, which is a change
        of claim and not only of numbers (ch13)
    range: [0.002, 0.05]
  hosts:
    kind: input
    decided: you
    unit: host
    value: 54
    label: hosts in the fleet
    note: >-
      **The most important node in this model, and the one a spreadsheet
      hides.** Sizing does not produce a fleet; it produces a
      recommendation, and then a person decides. It arrives here,
      in Part II, because a queue needs something to stand in
      front of — but it is decided in ch12, and everything downstream
      of it, every dollar, every watt, every ceiling, is a consequence
      of the number chosen here and not of the number the model
      would recommend in hindsight.

      Deriving it instead would make the ceilings below tautologies:
      a fleet sized to sit under the knee sits under it in every
      sample, and the model would cheerfully report a zero per
      cent chance of queueing. Making it an input is what lets
      the ceilings ask the only question worth asking — *given
      what we actually bought, how often does the world break
      it?*
    provenance:
      kind: assumption
      source: >-
        the sizing decision, taken the way it is usually taken:
        hosts_recommended evaluated at every input's point estimate.
        Change this number and watch the ceilings move — that
        is the exercise of ch12
    range: [4, 200]

Read the note on the first node twice. Service demand is how much of a processor a request costs. It is not how long the request takes. The difference is queueing, and the whole of Part II is about that difference. Service demand also belongs on a reference machine. Nobody has declared one. So the model holds it as an assumption, and its source says what measurement would replace it. It does not pose as a measured constant, because no measurement is behind it (ch03).

The second node is the one a spreadsheet hides. Its note says why it is an input and not a result: the model recommends a fleet, a person decides one, and every ceiling from here on asks what happens to the fleet that was bought.

Multiply the rate by the cost and you have the processors the busy hour keeps busy. Divide by the processors the fleet has and you have how busy it is:

  cores:
    kind: derived
    unit: core
    label: cores in the fleet
    formula: hosts * cores_per_host
  busy_cores:
    kind: derived
    unit: core
    label: cores busy at the busy hour
    note: >-
      Arrival rate times service demand. It is a count of cores
      doing work, it has nothing to do with how many you own,
      and it is the numerator of every utilisation figure below.
    formula: peak_request_rate * service_demand
  utilisation:
    kind: derived
    unit: dimensionless
    formula: busy_cores / cores

Utilisation is that ratio, and it is the number ch06 turns into a waiting time. Nothing here says whether the fleet is too busy. That needs a ceiling, and the file has none yet.

Here is the graph as this chapter leaves it. Click utilisation to see the rate and the cost meeting. Drag hosts in the fleet and watch it move, while nothing yet says how far is too far.

Running the law backwards

Nobody measures residence time. It is the hardest of the three quantities to get at honestly. An application’s own timer starts when the request reaches the application, which is after it has finished queueing, and the queueing is generally most of the answer.

The other two are easy. Every system counts requests. Every system can expose a gauge of how many are in flight: a connection count, a thread-pool depth, a semaphore.

So divide. The residence time that comes out is the true one, including every queue the request sat in on the way. Problem 5.2 is that division.

What the fleet says

Source — web_service_littles_law-reference · every input on a slider

Look at the shape rather than at the numbers. The width is not Little’s law’s doing. One multiplication passes an ordinary spread straight through, and a product of two narrow things would be narrow. The width comes from what is being multiplied: a busy hour five years out, which ch04 gave a band, and a time per request nobody has measured on this software. The graph shows where each of them came from:

Two things are missing from that picture, and both arrive in the next chapter. The time each request stays is its service time, so nothing here waits. And the utilisation in the table has nothing to judge it against: the model can say how busy the fleet is, and cannot yet say whether that is too busy. ch06 supplies the waiting and the verdict together, because they are the same fact.

Three things the law lets you catch

A latency that is not the latency. Measure in-flight requests and arrival rate, divide, and compare against what your service reports. If the two disagree, the gap is queueing that happens before your timer starts: a connection backlog, a load balancer, a thread pool. Nothing in the application can see that gap. The user waits through it all the same.

A capacity claim that cannot be true. A system claiming to serve some rate with some concurrency is claiming a residence time. If that residence time is below its own service time, somebody has made an arithmetic error, and the law finds it in one line.

A queue nobody declared. If in-flight requests grow while the arrival rate is flat, residence time is growing. Something downstream has slowed, and the queue in front of it is absorbing the difference. It will keep doing that silently until it cannot.

What the law will not do

It will not tell you why residence time is what it is. It relates three numbers and has no opinion about which of them is causing the others.

A law that assumes nothing has no mechanism in it, and a chapter about it has less to say than the ones that buy one.

What this cannot tell you

Anything about a system that is not in a steady state. The one condition, and the one people forget. During an incident, which is when somebody reaches for the law, arrivals exceed departures and the queue is growing. Then “how many are in the system” is not a stable quantity for the law to be about. Applied to a five-minute window in the middle of a pile-up, it produces a number that describes nothing.

Which of the three quantities moved. If in-flight requests doubled, the law says the product of the other two doubled. It cannot say which, and the two have completely different remedies.

What the average is hiding. The law is about averages, and a queue’s average hides both of the states it is averaging over. A system with a handful of requests in flight on average can spend most of its time empty and the rest badly backed up. The average describes neither.

Anything about the tail. It relates means. A residence time inferred this way is a mean, and it says nothing about the 99th percentile, which is the number anybody cares about during an incident.

Problems

Three, in tests/littles_law/. The first two have tests. The last does not, and says why.

5.1 — The law. One multiplication, checked against the model’s own node: the one ch06 adds, with the waiting in it, so that the check covers the time a request stays rather than the time it is being served. Checked at the point estimate first, then across every future the model drew.

def concurrency(
    arrival_rate: float | np.ndarray, residence_time: float | np.ndarray
) -> float | np.ndarray:
    """Problem 5.1 - the law itself.

    ``arrival_rate`` is requests per second. ``residence_time`` is how long each one stays, in
    seconds, from arriving to leaving - queueing included. Return how many are in the system at
    any moment. The test hands both as single numbers and then as arrays holding every future
    the model drew, so write it as arithmetic that works on either.

    One multiplication. The test checks it against the web service model's own node, which is
    the law written as a formula, at the point estimate and then across every future.

    Worth knowing what you are *not* assuming. Nothing about how requests arrive, nothing about
    the order they are served in, nothing about the shape of anything. Only that the system
    is in a steady state - as much going out as coming in, over the window you are looking at.
    That is why this is the one relationship in Part II that is always true.
    """
    raise NotImplementedError("problem 5.1")

5.2 — The law backwards. Infer residence time from in-flight requests and arrival rate, the two things every system already exposes. Then decide what to return when nothing is arriving. That decision is a judgement, not arithmetic.

def residence_from_observation(
    in_flight: float | np.ndarray, arrival_rate: float | np.ndarray
) -> float | np.ndarray:
    """Problem 5.2 - the law backwards, which is how it is actually used.

    You almost never know residence time. You know how many requests are in flight, because a
    connection count or a thread-pool gauge is trivial to expose, and you know the arrival rate,
    because everybody counts requests.

    Return the residence time those two imply, in seconds.

    This is the useful direction and it is why the law is worth knowing. A latency you cannot
    measure directly falls out of two numbers you already have - and it is the *true* latency,
    including every queue the request sat in on the way, which is generally not what an
    application's own timer reports.

    Then decide what to return when nothing is arriving. With no arrivals there is no residence
    time to infer: raise, or return an infinity, but not a number somebody could put in a slide.
    """
    raise NotImplementedError("problem 5.2")

5.3 — Your own steady state. No test: the measurement is of your queue, and nothing here can see it.

Pick a queue you run: a request tier, a job pipeline, anything with work arriving and leaving. Measure two of the three quantities over a window: how fast work arrives, how much is in flight, how long a unit takes. Infer the third, then measure it too.

Watch the chapter’s first limit. The law holds in a steady state, and your window almost certainly was not one. If the inferred and measured values disagree, you have not found an error in arithmetic that has been true since 1961. You have found out that arrivals and departures did not balance over your window, which is worth more than the number was.

A good answer states the window, the three values, and the gap between inferred and measured. If there is no gap at all, check whether your window was long enough to contain a busy period.

Where to go next

Little’s original proof [Little (1961)] is five pages, and worth reading for how little it assumes.

ch06 buys a mechanism. It costs assumptions, and it explains the shape of the distribution above.