Sharing Servers Don't Mind the Giant
Round Robin Can't See the Giant ended on a limit I hadn't tested. Every server there worked through its jobs one at a time, first come first served, so a single giant job blocked everything queued behind it. Real servers often don't work that way. A CPU or a web server slices its time among everything it's holding, so a small job that arrives behind a giant still gets its share right away. I guessed that would shrink the gap between policies. I measured it, and it does more than that: with sharing servers, the size spread stops mattering at all for most of the policies I tried.
The setup
Everything is as in the last post except the servers. There are 100 of them, jobs arrive at random, mean job size is one service time, and the score is the mean time a job spends in the system. Job sizes come from the same mix of two exponentials, with spread measured by the squared coefficient of variation (SCV): 1 for exponential sizes, up to 30, where 1 job in 61 is a giant averaging 30 service times and the giants carry half the work.
The new part: each server now splits its capacity equally among the jobs it holds. With three jobs present, each runs at a third of full speed. Queueing people call this processor sharing. I ran 8 seeds of 2 million jobs for every point and compared against the first-come-first-served numbers from last time, at the same loads, spreads and staleness.
One check before trusting it. For a single sharing server with random arrivals, there's an exact result: the mean time in system is the mean job size divided by (1 − load), whatever the size distribution. With random dispatch every server is exactly that, so at 90% load the answer has to be 10. I got 9.98, 10.04, 10.03 and 9.89 for exponential, fixed-size, SCV-30 and Pareto jobs (8 seeds each, standard errors 0.03 to 0.18). The same result says a job of size x takes 10x on average, so time in system divided by size should average 10 too: 9.98 to 10.22 across the four spreads, within two standard errors. And with exponential sizes, a dispatcher that only looks at counts should see exactly the same thing under either discipline, because counts move the same way. Best of two came out at 2.64 both ways.
The spread stops mattering
| Job sizes | Random | Round robin | Best of two (live) |
|---|---|---|---|
| Exponential (SCV 1) | 10.0 · 10.0 | 5.2 · 5.2 | 2.6 · 2.6 |
| SCV 4 | 23.4 · 10.0 | 18.6 · 7.8 | 4.2 · 2.6 |
| SCV 10 | 51.1 · 10.2 | 45.5 · 8.8 | 6.8 · 2.6 |
| SCV 30 | 139.9 · 10.0 | 132.5 · 9.1 | 15.2 · 2.7 |
Mean time in system, in service times, at 90% load. Each cell: queueing servers · sharing servers.
Random doesn't move, which is the exact result above. The surprise is best of two: 2.64, 2.64, 2.64, 2.66. A live least-loaded dispatcher is just as flat at 1.07. Queueing theorists have seen this before: Gupta, Harchol-Balter, Sigman and Whitt analyzed join-the-shortest-queue with sharing servers in 2007 and found it nearly insensitive to the size distribution. Here I couldn't detect any sensitivity at all.
The intuition: under sharing, a job's speed depends only on how many jobs it shares the server with. A giant doesn't block anyone; it just takes one slot for a long time. Counting jobs is exactly the right signal, and job sizes never enter it.
That also flips which piece of information is best. With queueing servers, an oracle that knows how much work every server has left was the best policy I tried (1.18 at SCV 30, against 1.50 for least loaded by count). With sharing servers it loses: 1.21 against 1.07. A server halfway through one giant has a lot of work left but only one job, and a new small job sent there runs at half speed, not behind 15 units of waiting.
Round robin is the odd one. It still loses its edge as the spread grows, from half of random's time down to 9% better, but what it decays toward is random's 10, not 140. With sharing servers the worst it can do is merely bad.
Old information lasts even longer
The orange lines on the left are best of two reading a board refreshed every 100 service times. With queueing servers it gets worse as jobs spread out, from 21 to 45. With sharing servers it gets better, from 21 to 6.0, which beats live round robin. Across the whole sweep:
| Job sizes | Best of two worse than random once T is | …than round robin | Least loaded worse than round robin |
|---|---|---|---|
| Exponential | 20–50 | 10–20 | 1–2 |
| SCV 4 | 50–100 | 20–50 | 2–5 |
| SCV 10 | 100–200 | 100–200 | 5–10 |
| SCV 30 | 200–500 | 200–500 | 5–10 |
Sharing servers, 90% load. T is the time between board refreshes, in service times; ranges are the grid points where the curve crosses.
Against round robin, best of two's staleness budget is the same as with queueing servers or one grid step shorter, because round robin itself got better. Least loaded's budget shrank from "over 50" to 5–10 service times at SCV 30: its herd still costs something, and a round robin that doesn't collapse is harder to beat.
Last time I guessed why old information stays useful with heavy tails: the thing worth knowing is which servers are holding giants, and that changes on a giant's time scale. I hadn't tested it. The right panel does. Under random dispatch, so that the board can't steer anything, I correlated each server's count on an old board with its count now. With exponential jobs a 500-unit-old board is noise (correlation 0.05). At SCV 30 it's still 0.67. The giants carry half the work, and under sharing every job's time in the system is proportional to its size, so about half the jobs present at any moment are giants, each staying around 300 service times. Most of what a count measures is still true long after it was taken.
What changes
- The heavy-tail disaster in the last post was mostly a queueing disaster. If servers share, random and round robin stay near 10 at 90% load instead of reaching 140.
- If your servers share, count jobs. Live best of two and least loaded are unaffected by the size spread, and counting beats knowing the exact work left.
- Best of two is still the safe default: it beat round robin with boards 100 service times old at SCV 10 and 30, under both disciplines.
- Least loaded on a stale board gets less forgiving with sharing servers, because the baseline it has to beat stops collapsing.
Limits: perfect sharing is an idealization. Real time-slicing costs context switches, memory pressure grows with the number of jobs held, and many servers cap concurrency, which is a hybrid of the two disciplines I measured. Still one dispatcher, identical servers, sizes independent of everything else.