4 ms·
"The optimum routing is to have each dyno with 0 or 1 job at a time and a global queue of all incoming requests. But this is a latency problem then since it tak
by bradleyjg 14y ago
"The optimum routing is to have each dyno with 0 or 1 job at a time and a global queue of all incoming requests. But this is a latency problem then since it takes time for a dyno to tell that it is "ready". The net result is very bad performance and the global queue is a single point of failure. The solution is to queue because this removes the latency --- but with the price you see RG paying if a Dyno can only serve one request at a time."
You are right that there is an inherent latency hit using intelligent routing versus random routing. However in a resource constrained world, where no one can afford infinite dynos, there is also an average latency hit to random routing -- but rather than being largely fixed for all requests it is instead highly variable. While the magnitude of the two need to be factored in, ceteris paribus low variance in latency is better.
As for your single point of failure point, there are distributed queue algorithms that handle router failure gracefully.
- mononcqc 14y agoCould you point me to such distributed queue algorithms that can handle failure gracefully? I'm interested in reading on the topic.
- drusenko 14y agowhile not exactly what you're looking for, this might be a good starting point: http://en.wikipedia.org/wiki/Virtual_Router_Redundancy_Protocol http://en.wikipedia.org/wiki/Virtual_Router_Redundancy_Proto... there seems to be some more reading material linked to at the bottom.
- bradleyjg 14y agoSure. See http://research.microsoft.com/pubs/153348/idleq.pdf http://research.microsoft.com/pubs/153348/idleq.pdf, http://arxiv.org/ftp/arxiv/papers/1103/1103.2408.pdf http://arxiv.org/ftp/arxiv/papers/1103/1103.2408.pdf, and http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/spanner-osdi2012.pdf http://static.googleusercontent.com/external_content/untrust....
- jlouis 14y agoI really liked your links to mononcqc :) Because that are way better suggestions than just "intelligent routing" I only skimmed the first one, with Join-Idle-Queueing, but that sounds like a way better algorithm to apply.
- bradleyjg 14y agoYeah, Heroku's original method wasn't all that great, and random routing can give surprisingly decent performance in some workloads. Unfortunately the workload they were/are working with doesn't seem to be one of them. Happily this class of problems is very well studied, and so there is a ton of research out there on various options. I know it can be daunting to write a program directly from a research paper, but hey that's why they make the big bucks.