Hacker News new | ask | show | jobs
by rienbdj 13 days ago
Anyone know a good into to queuing theory?
2 comments

Queueing theory introduction for software developers:

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

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.

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.
Your math doesn't make any sense.
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?
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.