Introduction

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.

Spread the Jobs

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">Seven jobs of different sizes, three servers. Click a job to move it to the next server. The bars show each server's load — minimize the <b>busiest</b> one (the makespan).</p>
<div id="servers" class="servers"></div>
<div class="meter">Busiest server: <b id="make" class="make">0</b><span id="status" class="status"></span></div>
<div class="btns">
  <button id="lpt" type="button">LPT (greedy)</button>
  <button id="opt" type="button">Optimal</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Load balancing = multiprocessor scheduling (NP-hard). Minimize the makespan
    // (busiest server). LPT (largest-first greedy) is a 4/3-approximation; Optimal
    // brute-forces the minimum. Here LPT gives 12, the true optimum is 11.
const M = 3;
const SIZES = [7, 6, 5, 4, 4, 3, 3];
const COL = ['#2a9d8f', '#457b9d', '#6d597a', '#e76f51', '#b9770e', '#0a7d33', '#c0392b'];
let assign = SIZES.map((_, i) => i % M); // initial round-robin

function loads() { const l = new Array(M).fill(0); SIZES.forEach((s, i) => l[assign[i]] += s); return l; }

let OPT = Infinity;
(function () { const l = new Array(M).fill(0); (function rec(i) { if (i === SIZES.length) { OPT = Math.min(OPT, Math.max(...l)); return; } for (let s = 0; s < M; s++) { l[s] += SIZES[i]; if (l[s] < OPT) rec(i + 1); l[s] -= SIZES[i]; } })(0); })();

function render() {
  const l = loads(), maxL = Math.max(...l, 1);
  document.getElementById('servers').innerHTML = Array.from({ length: M }, (_, s) => {
    const jobs = SIZES.map((sz, i) => ({ sz, i })).filter(j => assign[j.i] === s);
    return fmt('<div class="srv"><h4>Server %s%%v%</h4><div class="load">%v2%</div><div class="stack" data-s="%s%">%map%</div></div>', { s: s, v: 1, v2: l[s], map: jobs.map(j => '<div class="job" data-i="' + j.i + '" style="background:' + COL[j.i] + ';height:' + (j.sz * 7 + 8) + 'px;line-height:' + (j.sz * 7 + 4) + 'px">' + j.sz + '</div>').join('') });
  }).join('');
  document.querySelectorAll('.job').forEach(el => el.addEventListener('click', () => { const i = +el.dataset.i; assign[i] = (assign[i] + 1) % M; render(); }));
  const mk = Math.max(...l);
  document.getElementById('make').textContent = mk;
  const st = document.getElementById('status');
  if (mk <= OPT) { st.style.color = '#0a7d33'; st.textContent = fmt('✓ optimal balance! (%OPT%)', { OPT: OPT }); }
  else { st.style.color = '#b9770e'; st.textContent = fmt('optimum is %OPT% — %v% over', { OPT: OPT, v: mk - OPT }); }
}

function lpt() {
  const order = SIZES.map((s, i) => i).sort((a, b) => SIZES[b] - SIZES[a]);
  const l = new Array(M).fill(0); const a = SIZES.slice().fill(0);
  for (const i of order) { let m = 0; for (let s = 1; s < M; s++) if (l[s] < l[m]) m = s; a[i] = m; l[m] += SIZES[i]; }
  assign = a; render();
}
function optimal() {
  const l = new Array(M).fill(0); let best = Infinity, bestA = null; const a = new Array(SIZES.length).fill(0);
  (function rec(i) { if (i === SIZES.length) { const mk = Math.max(...l); if (mk < best) { best = mk; bestA = a.slice(); } return; } for (let s = 0; s < M; s++) { a[i] = s; l[s] += SIZES[i]; if (l[s] < best) rec(i + 1); l[s] -= SIZES[i]; } })(0);
  assign = bestA; render();
}

document.getElementById('lpt').addEventListener('click', lpt);
document.getElementById('opt').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { assign = SIZES.map((_, i) => i % M); render(); });
render();
Result
Console

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.

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/load-balancing/Content licensed under CC BY-NC 4.0.