News for hackers. Stuff that matters.
Re:Money Trees – Rap Genius Response to Heroku by jlouis on Monday February 18, 2013 @09:10AM (#5238318)
There are still some important points missing from the discussion:

1. Operating at scale with parallel routing. 2. Handle faults while operating at scale with parallel routing 3. Providing correct statistical models for the situation. The one we have right now is a crude approximation. 4. Measuring on the real system for problems.

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.

If a dyno does not report "ready" to the routing mesh, then you can't route optimally:

Queue length doesn't work since a request in queue may take 7000ms while still having a length of 1. Another queue with length 5 consisting of 5 70ms requests is better to route to.

The time the last request spent in queue is not useful either because the very next message may be a 7000ms one.

So to solve this problem, you must do something else. You cannot use "intelligent routing" unless you can describe how it will work distributed with, say, 8 routing machines while avoiding latency. And while you are at it, you better measure your solution in a real-world scenario.

Re:Money Trees – Rap Genius Response to Heroku by bradleyjg on Monday February 18, 2013 @10:08AM (#5238584)
"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.

Re:Money Trees – Rap Genius Response to Heroku by mononcqc on Monday February 18, 2013 @11:14AM (#5238921)
Could you point me to such distributed queue algorithms that can handle failure gracefully? I'm interested in reading on the topic.
Re:Money Trees – Rap Genius Response to Heroku by drusenko on Monday February 18, 2013 @12:23PM (#5239341)
while not exactly what you're looking for, this might be a good starting point: http://en.wikipedia.org/wiki/Virtual_Router_Redundancy_Proto...

there seems to be some more reading material linked to at the bottom.

Re:Money Trees – Rap Genius Response to Heroku by jlouis on Monday February 18, 2013 @07:13PM (#5241728)
I 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.
Re:Money Trees – Rap Genius Response to Heroku by bradleyjg on Tuesday February 19, 2013 @01:08PM (#5245906)
Yeah, 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.

Re:Money Trees – Rap Genius Response to Heroku by rb12345 on Monday February 18, 2013 @09:46AM (#5238475)
If I understand the articles and your comment correctly:

The issue here is that you have N routers all with their own estimates of free vs. in-use. Selecting a random free dyno is fine with one router because you can guarantee that it is truly free. With N routers, each will randomly distribute its work amongst the dynos in the pool, so each now has 0-N queued requests. This means that even with fixed-length response times, you get a dyno-queue-time of N*response_time under full load and some potential jitter even at low loads. Add in huge variations of response time and this gets far worse since the queue length in time is unknown. (There's probably a half-decent bufferbloat analogy hiding in this somewhere...)

It sounds like modern Rails is OK with handling multiple requests simultaneously as long as you're I/O bound and using non-blocking database IO. Would it be possible to use Node-like callbacks within Rails to break up CPU-bound tasks? It would not be an ideal solution, but might help work around this without resorting to Go and the like.

Re:Money Trees – Rap Genius Response to Heroku by jongraehl on Monday February 18, 2013 @07:43PM (#5241845)
"The solution is to queue because this removes the latency" - what? Queueing when your workers aren't at capacity surely adds latency.

Agreed that routers need to be aware of whether workers are busy. This might be really simple if the dispatcher receives the worker's reply and forwards it, or you could have the worker explicitly signal.

Why would you have a single global dispatch? While it is "optimum" if the dispatch were instant and infallible, presumably you'd have random assignment to any of a handful of independent dispatchers, each perhaps with dedicated workers, perhaps not.

(also agreed that fault tolerance is tricky if your operations aren't idempotent, and costly in any case)

Re:Money Trees – Rap Genius Response to Heroku by btilly on Monday February 18, 2013 @12:13PM (#5239286)
I suggested an intermediate solution to them.

The front line router picks a random appropriate dyno, then hands off the request to the router responsible. That router does intelligent routing to the dynos it is responsible for.

As long as you cluster dynos for a given app behind a set of routers, this essentially solves the problem on Bamboo for the cost of an extra step at the start of each request.

Re:Money Trees – Rap Genius Response to Heroku by mononcqc on Monday February 18, 2013 @12:30PM (#5239383)
What's unclear for this kind of scheme is what impact it has on stacks or dynos that can actually take concurrent requests. There's the distinct possibility that a concurrent server will see its average time get worse under such circumstances.

People simulate their stack quite quickly, but do not necessarily simulate what might happen to other ones.

Otherwise, it also means that you'll possibly have twice the data flying around your network due to the overhead of routing from one layer to the other one. Effects of these may be hard to predict.

It's also difficult to know what the impact would be of a router that handles a lot of traffic for an app being cycled or replaced, or crashing. Does this mean you create single point of failure for apps? Do you go for redundancy, failovers, sharding or anything else to fix this? What about netsplits between units across layers? Random distribution has the advantage of generally being pretty reliable across all of these scenarios.

Re:Money Trees – Rap Genius Response to Heroku by btilly on Monday February 18, 2013 @01:01PM (#5239555)
Bamboo is explicitly for stacks that can't take concurrent requests.

The data issues are not so bad. You just do as load balancers do and do the handoff in the initial TCP handshake. Only a small fraction of packets go through the first router.

As for the rest, the architectural issues are similar to the ones that Heroku was dealing with in 2009, except that each router has a constrained set of dynos it is responsible for. You would have standard health checks for routers, and the ability to migrate dynos from one router to another. There are issues to solve, but they are fairly reasonable.