CoursesSystem design from first principles to design review
Puzzle 15 · 16 of 19
Why does an idle worker watch a request wait?
Route four reads and measure time spent waiting behind earlier work.
All puzzles in this course
The problem
The capacity estimate counted requests in flight across the whole service. Now split that work between two workers serving the same map. Each can run one request at a time. The first read takes 100 milliseconds. The next three take 10 each. After ten milliseconds one worker is idle. Why might the next arrival still wait ninety milliseconds?
See it
Scroll sideways to see the full diagram.
Worker A starts a 100-millisecond read at time zero. Its bar occupies most of the axis.
Step 1 of 4Worker B starts the second read at the same time and finishes at 10. Each worker has received one request.
Step 2 of 4The third read arrives at the red line. Locate the empty worker before choosing where to send it.
Step 3 of 4Taking turns sends read three to A. Its bar can start only after read one finishes.Counting unfinished work sends read three to B. Its bar begins as soon as it arrives.
Step 4 of 4
The building block
A load balancer receives requests and picks a healthy worker for each. Round robin means taking turns: A, B, A, B. Imagine two supermarket checkouts where one shopper arrives with a full cart. Sending every other shopper to that checkout distributes shoppers evenly, yet someone with one item may wait behind the full cart.
In this experiment the dispatcher knows which requests have finished. A second policy picks the worker with the fewest outstanding requests and breaks ties in favor of A. At time 10, B has just finished its first read. A still has 90 milliseconds of work. The policy can see that difference without knowing how long the new request will take.
Run both routing policies
Each input pair gives arrival time and service time in milliseconds. A worker starts a request when both the request and the worker are ready. An earlier completion at exactly the arrival time frees that worker before dispatch. Before pressing Run scenario, predict request three's worker, start and finish. Run the scenario and check the third row. Now switch policies and make a second prediction.
const busy = finishTimes.map(times => times.filter(t => t > arrival).length);
let worker = index % 2;
if (policy === 'fewest outstanding') worker = busy[0] <= busy[1] ? 0 : 1;
Read the complete runnable code
function routeRequests(policy, requests) {
const finishTimes = [[], []];
return requests.map(([arrival, duration], index) => {
const busy = finishTimes.map(times => times.filter(t => t > arrival).length);
let worker = index % 2;
if (policy === 'fewest outstanding') worker = busy[0] <= busy[1] ? 0 : 1;
const lastFinish = finishTimes[worker].at(-1) ?? 0;
const start = Math.max(arrival, lastFinish);
const finish = start + duration;
finishTimes[worker].push(finish);
return { request: index + 1, worker: ['A', 'B'][worker],
arrival, start, finish, waiting: start - arrival };
});
}With round robin, request three arrives at 10, starts on A at 100 and finishes at 110. With the second policy it starts on B at 10 and finishes at 20. Neither worker became faster. Only the queue in front of that request changed.
Go deeperWhich count can the balancer see?
A network connection can carry several requests at once. A balancer that counts open connections observes something different from the outstanding request count in this experiment. If A has one connection carrying 100 concurrent reads and B has two carrying one read each, a least-connections policy can choose A. Decide what your actual proxy measures before treating its setting as a solution.
Which observation would help you check the setting?
Compare per-worker active requests, connection counts and waiting times under the same burst.
Try it
Select the equal-jobs scenario. Only the first read's duration changes, from 100 to 10 milliseconds. Predict the third request's waiting time under round robin, then run the code.
Compare your result
Both workers finish at 10. The difference in waiting time disappears. Next ask what happens when every worker waits on the same overloaded database. Routing alone cannot increase that database's capacity.
Check yourself
Sources
- NGINX · Load balancing methods — “least number of active connections”
What you now know
Evenly distributed request counts can hide an uneven distribution of work.
Answer every question above correctly to unlock the next puzzle.
Choosing a worker can reduce waiting. What if two reads on that worker ask storage the very same question?
Something wrong or unclear on this page? Tell me: a puzzle that didn't click is a bug in the puzzle.