[zdc1]

Tangential, but when dealing with queues, the first thing you want to do is have a basic grounding of queuing theory, and know whether you're optimising for throughput or worker utilisation (i.e. what are your SLAs and efficiency targets?). IME each goal involves fairly different metrics and scaling rules, so you'll want to know what you're prioritising.

[rienbdj]

Anyone know a good into to queuing theory?

[jph]

Queueing theory introduction for software developers:

http://github.com/joelparkerhenderson/queueing-theory

[mianos]

There are lots of good books and some great vids on youtube, but I'd start with this statement and work backward, because this is the non-obvious thing most bootcamp trained, promoted to CTO don't know:

The single most important lesson from queuing theory for software systems is the non-linear relationship between utilisation and latency.

As system utilisation approaches 1.0 (100% capacity), the average waiting time does not scale linearly, it scales hyperbolically. A system running at 95% utilisation is vastly more fragile and slow than one running at 80%, even though the load difference is minor.

[inigyou]

To explain this: if the system is 95% utilized, and a new request comes in, there's a 95% chance the system is already busy and the request has to wait. But after the currently in-progress request finishes, there's still a 95% chance the system is busy (with another request that was already queued behind it) and request X has to wait. After that one finishes, same thing. On average, request X has to wait for about 20 other requests at 95% utilisation - or 5 requests at 80% utilisation - or 10000 requests at 99.99% utilisation. And that's just the mean, not percentiles.

[thaumasiotes]

Your math doesn't make any sense.

[inigyou]

Which part? 95% utilisation means at any random point in time there's a 95% chance the system is utilized and a 5% chance it is not utilized at that moment, so on average you have to try 20 times to find an unutilised moment?

[thaumasiotes]

No, none of that is true.

Think about a secretarial pool with five secretaries. The pool is at 95% utilization. This might mean that one of the secretaries is at 100% utilization and the other four are at 93.75%. It might mean that all of the secretaries are at 95%. It might mean that four of them are at 100% and one is at 75%. It might mean something else.

Going back to that third case, we can easily see that with the system at 95% utilization, at any given moment in time there is a 75% chance that the system is busy and unable to begin a new task, and a 25% chance that the system has capacity to begin a new task right away.

In the full-average case where all five secretaries are at 95% utilization, the odds that the system has spare capacity at any given moment are 22.62% (= 1 - 0.95 ^ 5), not too different from the case where four secretaries are kept busy 100% of the time.