BOOK DEEP READ · SRE · CHAPTER 20
Site Reliability Engineering · Ch 20 · Google · 2016
You tap something in an app and the request lands in a datacenter. Inside, maybe a thousand machines are running the exact same program — so which one gets your request? The previous chapter was about which building the request enters. This one is about what happens once it is inside: picking one machine out of a pile of identical machines, and on what basis.
At the supermarket you naturally join the shortest queue. But suppose one cashier's terminal is broken, so every customer is bounced back in a second with "payment failed, next please" — that queue is always the shortest. Everyone piles into it, and nobody gets checked out.
This happens in datacenters every day: pick the machine with the fewest jobs in hand, and the broken one looks permanently idle.
One each, in rotation — sounds perfectly fair. Two problems.
Jobs differ wildly in size. One customer buys a bottle of water, the next wheels up a full trolley. Counting items is not counting work.
Cashiers differ wildly in speed. Machines in the same room are of different vintages, and other programs next door are competing for resources. Same ten customers: one cashier finishes in ten minutes, another takes half an hour.
So one queue always ends up much longer. And you have to staff for the most crowded queue — which means paying for people who sit idle.
One: don't say hello to everyone. A thousand callers times a thousand machines is millions of open lines; both ends pay memory, and each line needs a periodic "are you still alive?". So each caller knows only a few dozen of them. And the picking matters: pick at random and some machines get known by crowds while others get nobody; assigning by rule is what makes every machine known by the same number of callers.
Two: let the machine hold up its own sign. Don't guess how busy it is from outside — have it report its own busyness on the way back, riding along with the reply, costing no extra trip. Whoever reports idle gets more. Of the three approaches, this one works best.
Three: whoever is going off shift puts up a sign first. A machine that is about to restart shouldn't just switch off the lights and walk out — the customers in its hands get dropped. The right move is to post "this lane takes no new customers; those already in line will be served", then leave once the line is empty. The book calls that sign lame duck. Without it, a routine restart means a batch of users see errors on the spot.
The coarse decision was already made at the door (which building); inside there is only one job left: pick one of a pile of identical machines, and the basis for picking must come from the machine itself, not from guesswork outside.
The honest cost: a machine's self-reported busyness describes the little slice of time that just passed — when load spikes suddenly, the caller's information is always half a beat behind.
Load balancing inside a datacenter is a decision the caller makes for itself: first shrink the set of machines you keep in touch with, then let the machines report their own busyness to divide the work, and finally make a departing machine post its "no new customers" sign. The most counter-intuitive part: "fewest jobs in hand" does not mean idlest — it may mean broken.
Want the actual mechanisms, algorithms and diagrams? → switch to the deep read
You think datacenter load balancing means "send the request to whichever backend has the least work in hand" — but "least work in hand" is a contaminated signal: a broken backend that returns errors in a millisecond ranks first by that measure, forever. This chapter is about the three parts of client-side load balancing: subsetting turns the connection count from a multiplication back into an addition, weighted round robin on backend-reported load replaces guessing from outside, and the lame duck state makes a task leave without producing user-visible errors.
This is the second half of the load-balancing pair in Part III, "Practices": Ch19 covers traffic before it reaches the datacenter (DNS, anycast, VIPs), Ch20 covers what happens after it arrives — picking one of a pile of homogeneous backends; Ch21, "Handling Overload", then deals with the share that cannot be distributed at all. Real-world counterparts: the LB policies inside RPC client libraries such as gRPC and Finagle, and what a service-mesh sidecar does.
The ideal takes one sentence: every backend carries an equal share of load and nobody is overloaded. The chapter says up front that this is unreachable in a real datacenter, and lays out three reasons — which are also, exactly, the complete list of reasons simple round robin fails:
What happens if you don't solve it? Two bills.
The capacity bill. The measured order of magnitude the chapter reports: under simple round robin, the busiest task's CPU is roughly twice the least busy one's. Capacity has to be provisioned for the busiest task — which means buying double headroom for the whole service, while p99 is set single-handedly by that one task.
The connection bill. If every client connects to every backend, the count is a multiplication: 10,000 clients × 1,000 backends = 10 million connections. An RPC connection costs a few to a few tens of KB of memory on each end, plus CPU for periodic health checks; at a conservative 10 KB per end, the connections alone are hundreds of GB of memory, paid for nothing.
The Ch19 layer had a device decide for you. This chapter inverts that: there is no middleman — the client's own RPC library computes which backend to use. Why? Intra-datacenter service-to-service traffic dwarfs the traffic arriving from outside, and inserting a proxy into every hop adds a round trip and one more thing that can fail. The cost: the decision rests only on what that client can see — it has no idea how much fifty other clients are sending to the same backend. This limitation is the common root of every compromise in the chapter.
A backend is in one of three states as far as a client is concerned: healthy, refusing connections, lame duck. The first two are self-explanatory. The crudest gate is flow control: the client tracks its own active-request count per backend and, above a limit, treats that backend as unhealthy and stops sending — which catches a backend that is already clogged.
Lame duck catches something else: a planned departure. When a backend task is told to stop, exiting immediately turns the requests in its hands into user-visible errors. Lame duck splits that into steps: the backend broadcasts to all its active clients "stop sending to me, I am still finishing what I have" → clients stop sending new requests → the backend waits for in-flight work to drain → only then does it exit.
For scale: one rolling update of a 1,000-task service is 1,000 departures. Without lame duck, every routine release pours a batch of errors onto users — and those errors are 100% self-inflicted. It requires clients that receive and respect the notice, which makes it an RPC-framework capability; no ops script can retrofit it.
How big should a subset be? The chapter's figure is 20 to 100 tasks. Too large and the connection bill stays; too small and variance grows, plus you have nowhere to go when backends are unavailable — with a subset of 10 of which 2 are restarting, you have lost 20% of your usable capacity while the service as a whole has plenty to spare. The hard part is how to pick that handful.
Random subsetting: each client picks at random. The problem is a lopsided connection distribution — some backends are picked by many clients, some by almost none. The chapter's comparison uses 300 clients, 300 backends, subset of 30, and the skew is pronounced; to flatten it by randomness alone the subset has to grow to about three quarters of all backends, which abandons the point of subsetting.
Deterministic subsetting: group clients into rounds, have every client in a round share one shuffle seeded by the round number, then slice out a contiguous run by the client's index within that round:
subsets per round = total backends / subset size round = client id / subsets per round (integer) seed the shuffle with the round number, shuffle the backend list subset id = client id % subsets per round subset = the run starting at (subset id x subset size)
The property is elegant: every backend is connected to exactly the same number of times, skew reduced to zero; and a restarted client computes the same subset, so no connection churn. The cost is concrete: every client must agree on the order of the backend list and on its own id; and when the list changes the shuffle changes, so subset membership can turn over wholesale — which is precisely where it was later challenged.
Simple round robin: send to each backend in the subset in turn. It fails for the three reasons above, with the busiest task measuring about twice the least busy. Its one virtue is zero signal, zero state, zero configuration.
Least-loaded round robin: the client sends to whichever backend has the fewest active requests by its own count, round-robining among ties. The direction is right — a slow backend accumulates active requests and is automatically sent less. But it has two hard failures, and the first is the line worth memorizing from this chapter:
A broken backend that returns an error in a millisecond for every request has an active-request count of 0 forever — by this measure it is the idlest, so it swallows all new requests.
The fix is plain and inelegant: count recent errors as active requests for a period, so its "active count" is no longer 0. The general lesson: any load signal that only looks at work-in-flight must account for failures separately, or failure becomes attractiveness.
The second failure was noted above: the active-request count is only the client's own share — the same backend may be stuffed full by fifty other clients while looking idle to you.
Weighted round robin: let the backend report for itself — it puts the utilization, query rate and error rate it measured into the RPC response on the way back; the client keeps a moving average per backend and derives weights from it.
Why does this one win? The signal comes from the thing being measured (utilization is measured by the backend itself, far more accurate than counting active requests from outside), it costs no extra probe (it rides the response, marginal cost near zero), and it absorbs machine heterogeneity for free — a machine whose CPU is being stolen by a neighbour reports high utilization by itself, and the client never needs to know why. The cost: it reports an average over the slice of time just past, so the information lags whenever load shifts abruptly; and how error rate folds into the weight is a knob — turn it too far and one blip empties a backend completely.
Table 1 · Three load balancing policies: where the signal comes from, what it catches, what it costs
| Policy | Signal source | Spots slow backends | Spots broken backends | Main cost / failure mode |
|---|---|---|---|---|
| Simple round robin | none | no | no | busiest task's CPU about 2x the least busy; capacity must be sized for it |
| Least-loaded | the client's own active-request count | yes | inverted — it is drawn to them | a backend erroring instantly has 0 active, so it ranks first; and the count is only your own share |
| Weighted round robin | backend-reported utilization / qps / error rate | yes | yes (error rate folded into the weight) | signal lags by one window; the error-rate coefficient needs tuning |
Table 2 · Picking the subset: what each approach costs
| Random | Deterministic | Random + rendezvous hashing | |
|---|---|---|---|
| Connection spread | visibly skewed | perfectly even | approaches even as clients grow |
| Add / remove one backend | doesn't matter | the shuffle changes; subsets can turn over wholesale | each client's list changes at most 1 entry |
| Global coordination | none | required: client ids and backend list order must agree | none |
| Best for | when subsets can be large | stable backend sets with assignable ids | backends that scale up and down often |
To close: the three mechanisms each solve a different dimension and none substitutes for another — subsetting answers "who do I connect to", the LB policy answers "who do I send to", lame duck answers "how do I leave cleanly". If you may keep only one, keep lame duck: the first two affect cost and p99, this one affects the error rate — and the error rate is the part users see directly.
The value of this chapter is that it splits "load balancing" from one noun into three unrelated questions: who to connect to, who to send to, how to leave. Conflate them and you end up at "just use least-connections", which amplifies faults on real backends. The three best interview follow-ups live here too: why simple round robin isn't enough, why "least-loaded" walks straight into a bad node, and why backend self-reporting beats client-side observation.
weighted_round_robin. The reason opens the proposal: gRPC "does not have any first-class support for weighted round robin load balancing", and faking it by feeding round_robin duplicate addresses takes "a lot of machinery". The weight is computed from backend-reported utilization, qps and error rate: weight = qps / (utilization + eps/qps × error_utilization_penalty) — even the patch "error rate must be folded in separately" made it into the formula, which is exactly this chapter's fix for the dead-fish trap. The companion A51 has backends attach the metrics "in the trailing metadata when the corresponding RPC finishes". gRFC A58, "weighted_round_robin LB policy" ↗ · gRFC A51, "Custom Backend Metrics" ↗O(1) algorithm that "selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests" — power of two choices — because this "is nearly as good as an O(N) full scan" and shows "resistance to herding behavior". The chapter says "use least-loaded"; Envoy adds "but don't actually scan them all". Envoy architecture docs, "Load Balancers" ↗1. Datacenter load balancing is client-side: the caller's RPC library picks the backend, with no device in between. The cost is that it only sees its own share of traffic — every compromise in the chapter descends from this.
2. The ideal (equal share for all, nobody overloaded) is unreachable, and the three reasons are exactly why simple round robin fails: requests cost differently, machines are not homogeneous, subsets are small so variance is large. Measured cost: the busiest task's CPU is about twice the least busy one's, and capacity must be sized for it.
3. Connections are a multiplication: 10,000 clients × 1,000 backends = 10 million connections, hundreds of GB of memory at 10 KB per end — hence subsetting, at 20–100 tasks. Picking at random skews visibly (you would need about three quarters of the fleet to even it out, which defeats the point); deterministic subsetting — shuffle seeded by round number, slice by index — connects every backend the same number of times, at the price of globally consistent ids and list order, and wholesale turnover when the list changes.
4. The most counter-intuitive line in the chapter: a broken backend that errors in a millisecond has 0 active requests, so it is the most attractive backend under "least-loaded". The fix is to count recent errors as active requests for a period. Generalized: any signal that only looks at work-in-flight must book failures separately, or failure becomes attractiveness.
5. Weighted round robin wins: the backend puts utilization / qps / error rate into the RPC response, and the client weights by a moving average. The signal comes from the measured party, costs no extra probe, and absorbs machine heterogeneity; the cost is a one-window lag.
6. Lame duck splits departure in two: broadcast "stop sending to me", drain in-flight, then exit. One rolling update of a 1,000-task service is 1,000 departures — without it, every routine release pours errors onto users. It has to be a framework capability.
7. Landings and revisions: gRPC made weighted round robin first-class (weighted_round_robin + ORCA), with the error-rate discount written into the weight formula; Envoy concedes nobody really does an O(N) full scan and uses power-of-two-choices instead; and deterministic subsetting was replaced by random subsetting with rendezvous hashing.