The order slip rail (queues & the utilization cliff)

The stall, the wire over the stove, and the chart that ruins most people’s intuition about spare capacity. The video walks the same story with the slips moving: the order slip rail.

Before you start. You need one idea from The chai stall that got famous (load balancing): when a single stall could not keep up, you put several stalls behind one counter and shared the crowd between them. This lesson is about the problem that appears inside one stall, and the only maths is a number divided by one minus that number.

1909: Copenhagen, and the man asked how many wires to buy

In 1908 a Danish engineer named Agner Krarup Erlang, born on the first day of 1878, joined the Copenhagen Telephone Company and was handed a question no opinion could settle.

When you picked up a telephone in Copenhagen, an operator connected your line to a physical wire running across town. There were only so many wires, and if every one was in use you got nothing. So how many should the company buy? Too few and half the city hears a busy tone. Too many and the money is buried in idle copper.

The obvious answer is to count how many calls overlap on an average afternoon and buy that many wires. Erlang’s 1909 paper, “The Theory of Probabilities and Telephone Conversations”, is the discovery that this answer is badly wrong, for the least mathematical reason in this lesson. Calls do not arrive politely spaced out. They bunch. Your wires sit idle for a minute, then six people call at once.

Hold that thought.

Back at the stall: the counter freezes behind the stove

The stall is famous now: one person takes orders, another works the stove.

A customer asks for three cups. The order-taker calls it through, then stands there: the cook is two orders behind and there is nowhere to put the new one. Behind that customer eleven people wait, none of them served. Nobody is cooking slower; the counter has simply stopped.

That is the fast thing chained to the slow thing. The order-taker handles a customer every four seconds and the stove takes ninety. Call those ninety seconds one cooking time: every wait in this lesson is counted in them. Chained together, the counter runs at the speed of the stove.

The wire over the stove: a queue, and work that happens later (asynchronous)

Every busy stall in India owns the fix, for forty rupees: a wire strung above the stove. The order-taker writes each order on a paper slip, clips it to the wire, hands over a numbered token and says next. The cook pulls slips off at whatever pace the stove allows.

The order-taker never waits for the cook again. A rush of twelve becomes twelve slips inside a minute. The rush did not shrink, it got stored.

That wire is a queue: work written down and held in the middle, so the end that makes work and the end that does it need not run at the same speed.

flowchart LR
  C["counter<br/>one order every 4s"] -->|"clip a slip"| Q["the queue<br/>slips 41, 42, 43…"]
  Q -->|"pull when free"| K["stove<br/>one cup every 90s"]
  C -.->|"token, walk away"| U["customer, outside,<br/>not blocking anyone"]

The token is the other half of the idea. The tea is not ready when the customer walks away; it is promised. Work accepted now and finished later, with a receipt in the meantime, is asynchronous work, and every “your order has been placed” email is a token with a slip on a wire behind it.

Erlang’s bad news: utilisation, and why 95% busy is not “room to spare”

It feels like you bought capacity. You did not. The wire holds slips, it does not cook. If orders arrive for fifty cups an hour and the stove makes forty, the wire grows all day and every token is a longer lie. A queue smooths bursts; it cannot fix a stove slower than the day.

The number that governs everything is the fraction of the time your stove is busy. Call it utilisation. Erlang’s bad news is what waiting does as that fraction climbs. The numbers below are the output of a simulation, two hundred thousand orders pushed through one stove, with each wait counted in cooking times:

Read the shape, not the digits. Half busy to 80% costs three cooking times; 95% to 99% costs a hundred and thirty. The curve does not rise, it takes off, and it takes off in exactly the region every manager wants to run in. “We’re only 95% busy, we have headroom” is the most expensive sentence in this lesson: customers already wait twenty cooking times, and you are one busload from meltdown.

The reason is Erlang’s bunching. At half busy there are gaps between customers, and a gap is where a bunch drains away. Push utilisation up and you are spending the gaps. At 99% there is no gap left, so every bunch lands on the last one’s leftovers and nothing catches up. Idle time is not waste, it is the shock absorber, and a manager who recovers it has taken the suspension out of the car to save weight.

The dropped slip: at-least-once, and why cooking it twice must be safe

Now break something. The cook pulls slip 41, turns to the stove and drops it in the fire. If taking a slip removed it from the wire, that order no longer exists anywhere and a customer is outside holding a token for tea nobody is making. That failure is the worst kind: silent.

So a real rail does not remove a slip when a cook takes it. It turns the slip face down for a few minutes. If the cook says done, the slip is thrown away. If the minutes pass with no word, it turns face up again and any cook can take it.

Nothing is lost. The price is a slip cooked twice, by a cook who finished the tea then dropped dead before saying done. That bargain is called at-least-once, and almost every queue offers it, so the work must be safe to repeat. Two cups when one was ordered costs you a cup. Charging a card twice costs you a customer (Charged Twice (idempotency & exactly-once)).

When the rail is full: backpressure, the kind machine that says no

A wedding party arrives and orders two hundred cups. Slips are clipped over slips. A customer asks for one chai, and the tempting answer is to take it, because nothing appears to break. But that token is a promise of tea in three hours, handed to someone who would have walked to the stall across the road. You have not served them. You have collected them.

The honest answer is the one a good stall gives: kitchen full, come back at five. Refusing work you cannot do, the moment you know it, is backpressure, and it is a kindness, not a failure. The customer gets a true answer early, and everyone holding a token gets the wait they were promised.

This is why a wire with no limit is dangerous. It never says no, so overload never surfaces as a refusal. It surfaces later and all at once: a stall face down in the street with a thousand tokens outstanding and no record of what they were for.

1993 and 2011: MQSeries made the rail a product, Kafka made it a log

IBM launched MQSeries in December 1993. For a decade it was how a payment left one bank’s mainframe, the one big central computer it ran everything on, and reached another without either being awake at the same moment.

The second act was at LinkedIn, where Jay Kreps, Neha Narkhede and Jun Rao built Kafka and open-sourced it in June 2011. Their change is small to describe and large to live with: reading a slip does not take it off the wire. A second cook, or the same cook after a crash, reads the same slips again from wherever they left off, so nothing is lost and two readers can work one wire. The kitchen, the accountant and the cup-counter all read the same order at their own pace. The rail is now a ledger, a record every clerk can read back from the start, which is The Ledger Everyone Reads (event-driven & the log).

You now know

• A queue is work written down and held in the middle, so the fast end stops waiting on the slow end.
• Work accepted now and done later is asynchronous, and the token is the promise that it will happen.
• Utilisation is the fraction of the time your worker is busy, and the wait takes off as it nears 100%.
• Queues smooth bursts but do not create capacity, and the idle gaps are what drain the bunching.
• A dropped slip must come back, so delivery is at-least-once, so the work must be safe to do twice.
• A full rail should refuse out loud. That is backpressure; an unlimited queue is the version that lies.

Stop here if you want. What follows is the same rail in numbers, plus the machinery a real broker adds underneath it.

Second read: the fraction behind the cliff

The table above came from one simulation. The same curve has a closed form, and for a single stove taking orders at random it is one fraction:

wait / cooking time = rho / (1 - rho)

In English: the extra wait, counted in cooking times, is utilisation divided by idle time.

Where it comes from. Call L the average number of slips ahead of a new arrival. The stove is busy a fraction rho of the time, so an arrival finds it busy with probability rho, and the rail it then sees looks like the rail any arrival sees: L slips plus the one cooking. In English: the slips you queue behind are everyone who arrived during your own wait, plus the one being cooked. So L = rho × (L + 1), giving L = rho / (1 − rho), and each slip costs one cooking time. The denominator is the idle fraction, and the cliff is that denominator going to zero. The fraction is exact only for random arrivals and random cooking times: a kitchen whose cups all take the same time waits about half as long, a burstier one longer, and every version keeps the cliff.

Move the dial yourself in the order slip rail, driven by src/lib/queue-lab.mjs. A rail capped at 40 starts refusing at 98% busy, 48 slips waiting.

The formula gives 99× at 99% busy where the board’s chart reads 150.8×. The gap is real, not rounding: that last point came from one finite run, and near saturation the tail lands well above the mean. Treat 99× as the mean, 150× as a thing that happened once.

What one extra percentage point costs, by where you stand:

adding one point of utilisation, from -> to, wait multiplier:
  50% -> 51%: 1.00 ->  1.04  (+0.04 cooking times)
  80% -> 81%: 4.00 ->  4.26  (+0.26 cooking times)
  90% -> 91%: 9.00 -> 10.11  (+1.11 cooking times)
  95% -> 96%: 19.00 -> 24.00  (+5.00 cooking times)
  98% -> 99%: 49.00 -> 99.00  (+50.00 cooking times)

The same point of load costs 0.04 cooking times at 50% and 50 at 98%, a factor of 1,225. Utilisation targets are not a matter of taste, and the traffic that kills you is never the traffic that doubled: a service at 98% needs one more customer than yesterday.

What the wedding party costs. Two hundred slips do not clear at the full service rate, because ordinary customers keep arriving throughout. The rail drains at the surplus rate, so clearing takes 200 ÷ (1 − rho): 400 cooking times at half busy, 20,000 at 99%. At one second a cup that last customer waits five and a half hours, and the rail lost nothing.

Little’s Law makes it exact. In 1961 John Little published a proof of L = λ · W, in the journal Operations Research: the number of items in a stable system equals the arrival rate times the average time each spends in it. A shop takes 30 customers an hour and each stays 20 minutes, so ten are inside at any moment. That is bookkeeping, not queueing theory, which is why you cannot cheat: once λ passes the service rate there is no steady state, and the backlog grows without bound.

Second read: what a real broker does with a slip

The thing holding the slips is the broker, the counter putting them on is the producer, the kitchen pulling them off is the consumer, and the broker trusts neither end.

• The slip is hidden, not deleted. A consumer pulls a message and the broker makes it invisible for a visibility timeout, deleting it only when the consumer acknowledges success. No ack before the timeout expires and it reappears for someone else. That is at-least-once delivery, and why consumers must be idempotent (Charged Twice (idempotency & exactly-once)).
• Poison messages need an exit. A message that always crashes its consumer loops forever, so after N failures the broker moves it to a dead-letter queue, a side rail for inspection, rather than block the line.
• Backpressure is a menu. Load-shedding drops the lowest-value requests (503). Throttling caps intake per client (The bouncer at the door (rate limiting)). A bounded queue rejects when full instead of hiding overload until memory dies. A circuit breaker stops trying after repeated downstream failures, so you fail fast instead of piling work onto a dying kitchen.

sequenceDiagram
  autonumber
  participant P as Counter, the producer
  participant Q as The rail, the broker
  participant W as Kitchen, the consumer
  P->>Q: enqueue slip 41
  Q-->>P: token, customer walks away
  W->>Q: pull slip 41
  Q->>Q: hide it for the visibility timeout, do not delete
  W--xQ: cook crashes, no ack
  Q->>Q: timeout expires, slip 41 becomes visible again
  W->>Q: pull slip 41 again, cook it, ack
  Q->>Q: now delete it. at least once, so cooking twice must be harmless
  P->>Q: enqueue slip 42, rail is at its cap
  Q-->>P: rejected, kitchen full, come back at five

Try it

1. Run the lab’s own module. From the site repo, no dependencies:

$ node --input-type=module -e '
import { waitMultiplier, meanQueueLength, burstDuration } from "./src/lib/queue-lab.mjs";
for (const r of [0.5,0.8,0.9,0.95,0.98,0.99])
  console.log((r*100).toFixed(0)+"% busy:",
    waitMultiplier(r).toFixed(1)+"x wait,",
    meanQueueLength(r).toFixed(1)+" slips waiting,",
    burstDuration(r,200).toFixed(0)+" cooking times to clear a party of 200");
'

2. Move the dial in the lab (the order slip rail): set utilisation to 80% and drop the wedding party, then 95% and drop the same party. Same rail, four times the drain. Then raise it one point at a time from 90% and watch the drain time stop moving in proportion.

Go deeper

• AWS Builders’ Library - avoiding insurmountable queue backlogs
• Little’s Law
• Agner Krarup Erlang
• SQS visibility timeout & dead-letter queues

Retrieval practice

10 questions. Answer each one before you open it.