Re:Join-Idle-Queue: Load Balancing Algorithm for Scalable We...
by emfree on Friday December 09, 2016 @05:37PM
(#13142474)
> But in web services you often care more about the tail-end latency, the p90, p99 etc.
For sure. I think Theorem 2 in the paper implicitly addresses the latency distribution in this scheme. They're saying that in the limit of a large system, the queue length distribution at a single backend server depends only on the service time distribution (how long it takes to actually process each job) and the service discipline. So if for example job sizes are exponentially distributed and handled in FIFO order, then the wait time distribution is also exponential.
It would certainly be nice to see a more explicit discussion of the tail latency, especially in the simulations the authors did.
Another thing is I think this paper is assuming the latency for joining idle queues is zero. This is another simplification that makes the math easier, because otherwise you have to worry about a processor sending a message to join an idle queue, but before that message gets sent the processor gets more work and is no longer idle. It would be interesting to see what impact that might have on performance.
I'm not too familiar with queuing theory, can anyone point me to work has been done on long tail distribution for this or other load balancing strategies?