4 ms·

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

by jlouis 14y ago

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.

rb12345 14y ago
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.
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 ago
  Could you point me to such distributed queue algorithms that can handle failure gracefully? I'm interested in reading on the topic.
  - drusenko 14y ago
    while 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 ago
    Sure. 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 ago
btilly 14y ago
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.
- mononcqc 14y ago
  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.
  - btilly 14y ago
    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.
jongraehl 14y ago
"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)

by jlouis 14y ago

rb12345 14y ago

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.

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 ago
Could you point me to such distributed queue algorithms that can handle failure gracefully? I'm interested in reading on the topic.
- drusenko 14y ago
  while 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 ago
  Sure. 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 ago

btilly 14y ago

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.

mononcqc 14y ago
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.
- btilly 14y ago
  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.

jongraehl 14y ago

"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)