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

Where a ten-millisecond read waits behind a hundred-millisecond job Worker time in milliseconds AB 010100 Read 1 2 Third read arrives 3Wait: 90 ms 3Wait: 0 ms

Scroll sideways to see the full diagram.

  1. Worker A starts a 100-millisecond read at time zero. Its bar occupies most of the axis.

    Step 1 of 4
  2. Worker B starts the second read at the same time and finishes at 10. Each worker has received one request.

    At time 10, worker A still has its first job and B has just finished. Which can start read three immediately?

    Step 2 of 4
  3. The third read arrives at the red line. Locate the empty worker before choosing where to send it.

    Step 3 of 4
  4. Taking 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.

Back to the main puzzle

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

At time 10, where does round robin send request three?

Right. The first two assignments were A and B.

Not quite. Taking turns does not look at the queue.

What explains a 90-millisecond wait?

Not quite. Its own service time is ten milliseconds.

Right. The request arrived at 10 but A became free at 100.

What does the second policy need to observe?

Right. A completion changes what the next dispatch sees.

Not quite. The experiment counts unfinished requests at dispatch. Re-read that part ↑

Sources

What you now know

Evenly distributed request counts can hide an uneven distribution of work.

Choosing a worker can reduce waiting. What if two reads on that worker ask storage the very same question?