Sharing the Load

A website gets a flood of requests. Behind it sit several servers, and the requests must be spread among them. If one server gets swamped while others sit idle, that server slows to a crawl and users feel it. The goal is to share the work so the busiest server finishes as soon as possible.

The simple instinct is round-robin: hand jobs out one by one, taking turns. It's fair by count — but jobs aren't the same size. A few heavy requests landing on the same server can overload it even while the count looks even.

That's load balancing, and in its core form — distribute jobs to minimize the maximum load (the makespan) — it's a cousin of scheduling and bin packing, and it's NP-hard. But here's the good news that keeps systems running: simple rules get provably close to perfect balance.

Try it. You have jobs of different sizes and three servers. Click a job to move it to the next server. The bars show each server's load; the number you're minimizing is the busiest server's load (the makespan).

<p class="hint">{{hint}}</p>
<div id="servers" class="servers"></div>
<div class="meter">{{busiest_label}} <b id="make" class="make">0</b><span id="status" class="status"></span></div>
<div class="btns">
  <button id="lpt" type="button">{{btn_lpt}}</button>
  <button id="opt" type="button">{{btn_opt}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.servers { display: grid; grid-template-columns: repeat(3, 1fr); gap: .6rem; }
.srv { background: #f6f8fa; border: 1px solid #e6e9ee; border-radius: 10px; padding: .5rem; }
.srv h4 { margin: 0 0 .2rem; font: 700 12px system-ui; color: #1d3557; text-align: center; }
.load { text-align: center; font: 800 14px ui-monospace, monospace; color: #457b9d; margin-bottom: .4rem; }
.stack { display: flex; flex-direction: column-reverse; gap: 3px; min-height: 40px; }
.job { color: #fff; border-radius: 5px; text-align: center; font: 800 12px ui-monospace, monospace; cursor: pointer; padding: 2px 0; }
.meter { margin: .8rem 0 .6rem; font-size: 1.05rem; }
.make { font-family: ui-monospace, monospace; color: #c0392b; }
.status { margin-left: .6rem; font: 700 .9rem system-ui; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Try to even them out by hand, then press LPT (a smart greedy: place the biggest jobs first) and Optimal (the true best). Notice that even LPT — very good in practice — can miss the optimum here by a little. That small gap is the NP-hardness, and chasing it perfectly is the hard part.

Load balancing is the friendly kind of hard — NP-hard, but beautifully approximable:

• Checking is easy. Add up each server's assigned jobs and take the largest.
• It's NP-hard. Minimizing the makespan over identical machines is multiprocessor scheduling, a classic NP-hard problem (it even contains the partition problem). Brute force tries exponentially many assignments.
• Greedy is a 2-approximation. Just put each job on the least-loaded server (list scheduling). The result is never more than twice the optimal makespan — a guarantee with almost no effort.
• LPT is even better. Sort jobs largest first, then place each on the least-loaded server. This Longest-Processing-Time rule is a 4/3-approximation — within about 33% of optimal, usually much closer.
• Online and randomized. When jobs arrive over time, you can't see the future; the elegant power of two choices (pick the lesser-loaded of two random servers) keeps things remarkably balanced.

So while finding the perfect balance is hard, getting almost perfect is cheap and reliable — exactly why load balancers can keep up with the firehose of the internet.

Load balancing is one of the most load-bearing ideas in computing:

• Web and app servers: spreading requests so no instance is overwhelmed — the front door of nearly every site.
• Cloud computing: distributing workloads across machines and data centers.
• CDNs: routing users to the best, least-loaded edge server.
• Databases: sharding and balancing queries across replicas.
• Parallel and distributed computing: splitting big jobs evenly across cores or nodes.

Every time a popular site survives a traffic spike, a load balancer is quietly solving an NP-hard problem well enough, fast enough, to keep you from noticing.

Load balancing is NP-hardness you barely notice, precisely because we've learned to live with it so gracefully. Perfectly minimizing the busiest server is intractable, but a one-line greedy rule lands within a factor of two, and sorting big-jobs-first gets you within a third. For a system that just needs to not fall over, that's more than enough.

It's a fitting note as this collection winds down: a problem that is genuinely hard, genuinely everywhere, and genuinely handled — not by conquering the worst case, but by getting close, cheaply, every second. The internet stays up not because we solved an NP-hard problem perfectly, but because we found a way to lose to it by almost nothing.