The chai stall that got famous (load balancing)

The first board of the System Design track: a queue, a row of stalls, and a man at the gate handing out tokens. This lesson is how a real website ended up with all three.

Before you start. You need one idea from One address, a thousand doors: a single address can be answered by machines in many cities, because the network hands you the nearest copy, which is anycast. Everything else here is a queue, some stalls, and a man with tokens.

The stall gets famous, and a bigger stove is the wrong answer

A chai stall on a corner. One stove, one wala, forty cups an hour, and that is plenty, because thirty people come. Then someone posts about it. Now three hundred people come, the queue runs down the street, and the cups still come out at forty an hour.

The obvious answer is a bigger stove. It works for a while, then fails twice over. Stoves have a largest size, so eventually you own the biggest one there is. And a bigger stove is still one stove: the day it cracks, the stall is shut and the queue goes home.

So you do the other thing. Open a second stall beside the first, and a third. Three stoves, three walas, a hundred and twenty cups an hour. The stove stopped being the ceiling, and that buys you the problem this lesson is about: three hundred people are standing in one road, and nobody has told them which stall to walk to.

1994: NCSA had the famous stall, and DNS round robin handed out the doors

This really happened, and the stall was a website.

The National Center for Supercomputing Applications, at the University of Illinois, had written Mosaic, the browser that turned the web into something ordinary people used, and it pointed at NCSA’s own pages. On the main long-distance links of the American internet, the web carried under three percent of traffic in March 1994. A year later it carried nearly twenty percent, more than anything else. NCSA’s machine was the stall on the corner, and the post had gone up.

Eric Dean Katz, Michelle Butler and Robert McGrath wrote up what they did, in a 1994 paper called A Scalable HTTP Server: The NCSA Prototype. They stood up a row of identical machines. Every one could serve every page, because the pages did not live on any of them: they lived on a shared filesystem all the machines read from. Then they went to the phone book of the internet, the name server that turns a site’s name into an address, and told it to hand those addresses out in rotation. Ask for the site and you get the first machine; ask again, the second; again, the third; then back to the first.

That rotation has a name: round robin. Take the next in the list, then the next, then start again at the top. When those name servers, together called DNS, do the rotating, it is DNS round robin, still running today. Here is amazon.com, asked three times in a row:

$ for i in 1 2 3; do dig +short amazon.com | tr '\n' ' '; echo; done
98.87.170.71 98.87.170.74 98.82.161.185
98.87.170.74 98.87.170.71 98.82.161.185
98.87.170.74 98.82.161.185 98.87.170.71

The same three doors, a different one at the front each time, and your browser walks to whichever came first. No machine sits in the middle, and nobody is watching any queue. NCSA added capacity by adding a line to that list.

Stateless: the stalls have to remember nothing

The shared filesystem is the deepest idea on this page.

Rotating people across three stalls only works while the stalls are interchangeable. If your half-paid tab is in the second wala’s head, you must go back to him, and “go to whichever is next” has stopped being safe advice.

So you take the memory out of the stalls. The tab goes into a register on the shelf behind them, where all three walas can reach it. Any wala can now pick up any customer’s tab, and the stalls hold nothing of their own but a stove. A server that keeps nothing of its own between requests is stateless, and NCSA’s machines were stateless because the pages sat on the shared filesystem rather than on any one of them. Stateless makes a stall replaceable, and replaceable is what makes every trick below possible.

1995: the rotation is blind, and a dead door stays on the list

In April 1995 Thomas Brisco wrote the first problem into the public engineering memos the internet is designed in, the RFCs: the rotating answer put the addresses in an order, but the actual load on the machines was never a factor in it. The name server is not standing at the stalls. It cannot see that stall two is halfway through an order of sixty cups while stall three is idle.

The second problem is worse. When a machine dies, the name server does not find out. The address stays in the list, the rotation keeps handing it out, and everyone who gets it walks up to a shuttered stall and waits. Nothing is checking, so nothing ever takes it off.

And your machine keeps the answer. The list arrives with a time to live, a counter saying how long you may reuse it, and until it runs out every click you make goes to the door that came first in your copy. DNS is not spreading requests. It spreads callers, once each, then walks away.

Late 1995: the man at the gate, drawn in a meeting at Netscape

By then Netscape’s site was one of the busiest on the web, running exactly that arrangement.

In late 1995 John Mayes, of a company called Network Translation, sat down with Robert Andrews, Netscape’s webmaster. Andrews described his machines: round robin DNS in front, some very busy, others doing almost nothing. Then he told Mayes there were probably ten customers in the world with this problem.

Mayes drew a box: servers on one side, the internet on the other, everything passing through the middle. Cisco bought his company, and the box shipped in April 1996 as the LocalDirector, the first of its kind. F5’s BIG-IP arrived a year later, and the ten customers turned out to be everybody.

That box is a load balancer, and at the chai stall it is a man at the gate with a book of tokens. Every customer reaches him first and he writes a token saying which stall. Standing there, he sees the one thing the name server never could: the lines.

flowchart LR
    U[you] -->|"1 - which address?"| D["DNS: a list of doors, rotated"]
    D -->|"2 - nearest copy of that address"| A["anycast: same address, every city"]
    A -->|"3 - which stall?"| LB["the load balancer: the man at the gate"]
    LB --> S1[stall 1]
    LB --> S2[stall 2]
    LB --> S3[stall 3]
    S1 & S2 & S3 --> R[(the register on the shelf)]

Each step narrows the choice; only the last can see a queue.

Counting the lines: the slowest customers wait 2.8 seconds instead of 7.4

The man at the gate can still work blind: next stall, next stall, next stall. That is round robin again, one step closer to the stoves. When every order is the same size it is perfect and costs nothing, because blindness is free when there is nothing to see.

Orders are not the same size. Two customers in a hundred want sixty cups for an office, and round robin sends the next person straight to the stall grinding through one of those, because it never looks. The other rule is to look: count the lines, send the next customer to the shortest.

The lab on this board runs that with eight stalls and sixteen hundred customers. The slowest one customer in a hundred waited 7.4 seconds under next-in-turn and 2.8 seconds under shortest-line. That unluckiest slice is what engineers call the tail. Same stalls, same work, same whales; the only change was that somebody looked before pointing. The longest line went from 47 people deep to 6. Move the dial yourself: the load balancer.

The health check: the gate notices a stall has died

Here is what the man at the gate does that a name server cannot. He asks. Every couple of seconds he puts a question to each stall that only a working stall can answer: are you up? A stall that does not answer comes off his list. That probe is a health check, and it is why a load balancer is a reliability device before a speed one. A stove cracks, and the queue never finds out.

“Never finds out” has a window, and the window is how often he asks. In the lab, one of the eight stalls is killed two thirds of the way through the run. Probing every 2 seconds, 15 customers were sent to the dead stall, across 1.9 seconds. Under DNS round robin with a ten-second counter, 55 were stranded across 11.6 seconds, because nothing probes and the dead door sits in every caller’s copy until their counter runs out.

Sticky sessions, and why a deploy logs everyone out

One convenience undoes all of it. It is tempting to let the man at the gate remember you and send you to your usual wala. He writes it on your token, and your tab goes back to living in that wala’s head. That is a sticky session, and it is how a site keeps your logged-in session in one server’s memory and still has it there on your next click.

Then that wala goes home, and your tab went home with him. The health check pulls the dead stall out within one probe, which is the fast part working exactly as designed, and it cannot carry that stall’s memory across to the survivors. You reach a stall that has never heard of you, and from outside that reads as “you have been logged out”. It happens to every logged-in user of a sticky site the moment a deploy, a push of new code, restarts the servers.

Pinning a customer to one wala like that is also called affinity, and affinity is a smell. Statelessness is the cure: put the session in the register behind the stalls, and any stall can pick up any tab. The bill is one trip to the register per request, and that register is now the busiest thing in the shop. Which is the next lesson, The slate next to the stove (caching).

You now know

• A bigger stove runs out twice: there is a largest one, and it is still a single thing that can die.
• More stalls is the answer, and it creates the real question: who tells each customer where to go.
• DNS round robin rotates a list of addresses. It cannot see a queue and it cannot see a corpse.
• Stateless means a server keeps nothing of its own, the only reason one server can stand in for another.
• A load balancer picks a server per request and can count the lines: 2.8 seconds at the tail against round robin’s 7.4.
• Its health check pulls a dead server out within one probe interval, usually the bigger reason to have one. Sticky sessions undo that, and are why a deploy logs everyone out.

Stop here if you want. What follows is the same stall in numbers, for when you want the rules compared properly. The video walks the story with the tokens moving: the chai stall that got famous.

Second read: the rules, measured

Two places the man can stand. He can read the envelope and never open the letter, or he can open it. Reading the envelope is L4, the transport layer: route on the address and port it arrived at, fast and cheap, and blind to what was asked for, so it cannot send /images anywhere in particular. Opening the letter is L7, the application layer: route by path (/images to the image servers), header or cookie, terminate TLS (The whisper code (how a call goes private)), compress and cache, at the cost of work per request. Most modern balancers are L7 (NGINX, Envoy, ALB); L4 (HAProxy, AWS NLB) is chosen when raw throughput beats smarts.

The rules, properly named. Round robin and weighted round robin rotate, weights letting a beefier server take more; simple, and load-blind. Least connections (and least response time) sends the next request to the server with the fewest in flight, the “shortest line” of the story. IP hash and consistent hashing hash the client to a server, so it keeps landing on the same one without a cookie, and Splitting the ledger (sharding)‘s ring means adding a server reshuffles a slice rather than everyone. One caution: IP hash hashes the address, not the person, so an office or a mobile carrier lands thousands of people on one stall.

What the four rules cost

The lab is the chai stall with a dial on it: eight stalls, 1,600 customers, the pool held at 80% busy, and one dial making two customers in a hundred cost from one to sixty times the rest. The work offered never changes as the dial moves, only its shape. p99 is the wait the slowest one-in-a-hundred customer saw, in milliseconds. Every number in the table is the lab’s own simulation, not a measurement of any real balancer: the stall count, the load and the whales were chosen to make the rules pull apart, so read the order of the rows, not the milliseconds.

The top-left tie at 84 is why a benchmark that “proves” the rules are the same usually has identical requests.

Bottom row, 9,000-plus everywhere, including the column where all orders are equal. The client-skew run shows why: 24 callers spread evenly across the eight stalls, 7 to 9 each, but the requests they sent ranged from 85 on the quietest stall to 303 on the busiest, because one caller sent 425 and another 16. Balancing callers is not balancing work.

Why asking two is almost as good as asking everyone. Least-connections needs every stall’s queue before every decision: eight questions per customer here, and in a real fleet a cache of state that goes stale. Sample two at random and take the quieter, and you land at 2,932 against 2,773 with a quarter of the questions. One pick hits the busiest of eight stalls one time in eight; two picks hit it only when both were it, 1/8 × 1/8 = 1/64, turning 12.5% into 1.6%. A third pick reaches 1/512, and at a thousand stalls 1/1000 becomes 1/1,000,000. This is the power of two choices, which NGINX’s random two least_conn and Envoy’s least-request policy implement.

The failure window, in one trace

sequenceDiagram
    participant C as customer
    participant LB as the balancer
    participant S2 as stall 2
    participant S3 as stall 3
    LB->>S3: probe /health
    S3-->>LB: 200 ok
    Note over S3: stall 3 dies
    C->>LB: request
    LB->>S3: forward (still in rotation)
    S3--xLB: no answer, times out
    LB-->>C: 502, or a retry to stall 2
    LB->>S3: probe /health (2 s later)
    S3--xLB: no answer
    Note over LB: stall 3 marked down, out of rotation
    C->>LB: next request
    LB->>S2: forward
    S2-->>C: 200

Every request sent to stall 3 between “dies” and “marked down” is stranded, and that gap is the 15 requests over 1.9 s from the story. Those two numbers are teaching values too; a real gap is your probe interval times the failures you require before ejecting, so it is set in the balancer’s config, not fixed. Those 15 are the argument for retries: retrying a failed forward elsewhere turns a stranded request into a merely slow one. Health checks come in two kinds, active (probe /health on a timer) and passive (watch live traffic for errors, eject the failing one).

Who balances the balancer? It is now itself a single point of failure. Real setups avoid that with an active-passive pair sharing a floating IP (VRRP or keepalived: the standby grabs the address when the primary dies), DNS and anycast (How a parcel finds any house on earth) pointing at several balancers, or L4 ECMP spreading connections over a fleet.

Stickiness, honestly. If you must pin a user to a server, use a cookie or an IP hash. The better fix is stateless servers with sessions in a shared store (Redis, The Slate, Properly (caching to real depth)).

Try it

dig +short amazon.com     # run it thrice - watch the doors shuffle (DNS round-robin)

Then watch the two rules decide: one customer every 5 ms, three stalls, one order in four a 50 ms whale.

# round robin vs least-connections, with work that actually finishes
import random
random.seed(0)
N, GAP = 3, 5.0                                   # 3 stalls, one customer every 5 ms
costs = [random.choice([1, 1, 1, 50]) for _ in range(300)]   # mostly cheap, one in four a whale

def run(choose):
    finish = [[] for _ in range(N)]               # finish times of work queued at each stall
    waits, longest_queue = [], 0
    for i, c in enumerate(costs):
        t = i * GAP
        for q in finish: q[:] = [f for f in q if f > t]   # forget work that is done
        s = choose(i, finish)
        start = max(t, finish[s][-1] if finish[s] else t)
        finish[s].append(start + c)
        waits.append(start + c - t)
        longest_queue = max(longest_queue, len(finish[s]))
    waits.sort()
    return waits[len(waits)//2], waits[int(len(waits)*0.99)], longest_queue

rr = run(lambda i, q: i % N)                       # next in turn, ignores the queues
lc = run(lambda i, q: min(range(N), key=lambda s: len(q[s])))   # shortest line
print("round robin       p50 %4d ms  p99 %4d ms  longest queue %d" % rr)
print("least connections p50 %4d ms  p99 %4d ms  longest queue %d" % lc)

$ python3 lb2.py
round robin       p50   43 ms  p99  141 ms  longest queue 12
least connections p50    3 ms  p99  139 ms  longest queue 8

Read p50 first: 43 ms under round robin, 3 ms under shortest-line. Then read p99 and notice it barely moved. The slowest customers are the whales, and no rule makes a 50 ms order take less; what the balancer fixes is who gets stuck behind one.

Go deeper

• Katz, Butler & McGrath - A Scalable HTTP Server (1994)
• RFC 1794 - DNS Support for Load Balancing
• Cisco LocalDirector
• Cloudflare - What is load balancing?
• The 12-Factor App - processes (statelessness)
• NGINX - load balancing methods
• Google’s Maglev paper, how the balancer itself scales without becoming the next single stove.

Related

• The slate next to the stove (caching) - the shared register is the next bottleneck, and the slate is the fix
• The order slip rail (queues & the utilization cliff) - what a queue does to waiting time as a stall nears fully busy, the number behind every p99 above
• Load Balancing & DNS (the operator's half) - the DevOps board the lab lives on: DNS picks the endpoint, the balancer picks the instance
• One address, a thousand doors - the same address answered from every city, the step before the gate
• Splitting the ledger (sharding) - the consistent-hashing ring that IP hash grows into
• real systems - L7 routing per path, splitting traffic across services

Retrieval practice

10 questions. Answer each one before you open it.