5 ms·

A quick check on the documentation reveals instead of routing the requests to the first available or least loaded dynos, the dyno routing algorithm now routes r

A quick check on the documentation reveals instead of routing the requests to the first available or least loaded dynos, the dyno routing algorithm now routes requests to random dynos(Reference: https://devcenter.heroku.com/articles/how-heroku-works#dyno-manager https://devcenter.heroku.com/articles/how-heroku-works#dyno-...) Routing requests to random dyno is definitely not the smartest routing algorithm because it kind of defeats the purpose of having a routing layer. If you are not aware of the issue between Heroku and Rap Genius, I will think it is important enough for anybody who considers Heroku to be aware of. Here is the URL with relevant information: http://news.rapgenius.com/James-somers-herokus-ugly-secret-annotated http://news.rapgenius.com/James-somers-herokus-ugly-secret-a...

strmpnk 13y ago
While good for some dynos, it can be poor for others. Any system that handles singe requests serially is an irresponsible choice for anyone who might bother to look into queuing theory enough to blame the router but not be willing to blame their application server. There are systems that do benefit from other kinds of routing but there is very little margin to favor non-concurrent request handling in mostly state-less components like web servers. There are lots of responses on the web that take a much deeper look at the heroku router if you care to search. The conclusion is not so clear that Heroku is doing it wrong.
bgentry 13y ago
the dyno routing algorithm now routes requests to random dynos That's not a change; that's how routing on Cedar has always worked.
- thinkbohemian 13y ago
  Random routing is more or less industry standard. NGINX and ELB (what I would consider two gold standards for load balancing) both use Round Robin (non-inteligent, pseudo-random) routing variants: - http://wiki.nginx.org/LoadBalanceExample http://wiki.nginx.org/LoadBalanceExample - http://serverfault.com/questions/537450/what-algorithm-does-amazon-elb-use-to-balance-load http://serverfault.com/questions/537450/what-algorithm-does-...
  - ryderm 13y ago
    Round Robbin is certainly not equivalent to random, and is much much better for most applications. If all the requests take about the same amount of time, then round Robbin will give the request to the one that hasnt received a request in the longest amount of time, which is clearly the best choice in this situation. Randomized has a 1/n chance of handing the request to this less busy node, which is why the problem becomes worse as you scale.
    - mootpointer 13y ago
      The issue with round robin routing is that you can't do it in a distributed routing mesh. You need to share state between routers and that coordination overhead is non-trivial.
zrail 13y ago
This has been talked to death, but for the general case, for applications that can handle concurrent requests (like Rails with a rack server just a tiny bit smarter than Webrick), random routing works just as well as intelligent routing with far less coupling in the routing later, making it more robust and easier to manage and scale.
- sync 13y ago
  Rails servers like Unicorn can still only support ~4 concurrent requests on regular dynos (roughly 1 per virtualized core), lessening the problem but not solving it if you have many requests per second.
  - jules 13y ago
    Actually that makes a tremendous difference. It is a bit difficult to explain but even 2 concurrent requests per dyno is a lot better than 1. As you go up from 2 to 3 to 4 the difference quickly becomes minimal. I'll try to explain why, but warning: hand waving ahead! The problem with only 1 concurrent request is that if that request takes long to process then it can block other requests that are queued up in that dyno. Lets say that 1% of the requests take long. If a dyno can process only 1 request concurrently then at each request there is a 0.01 chance that that will block other requests. If however it can process 4 concurrent requests, then the dyno will only be blocked if it gets 4 long requests at the same time. So there is only a 0.01^4 = 0.00000001 chance that a dyno will be blocked.
    - adrianpike 13y ago
      Not quite. If you keep routing to a blocked backend, any requests that hit that backend will have unacceptable latencies. Since the routing is essentially random, you'll still be fielding about 1/4 of your requests to that backend, so one long request winds up making 1/4 of all your requests have unacceptable latencies.
      - jules 13y ago

strmpnk 13y ago

While good for some dynos, it can be poor for others. Any system that handles singe requests serially is an irresponsible choice for anyone who might bother to look into queuing theory enough to blame the router but not be willing to blame their application server. There are systems that do benefit from other kinds of routing but there is very little margin to favor non-concurrent request handling in mostly state-less components like web servers. There are lots of responses on the web that take a much deeper look at the heroku router if you care to search. The conclusion is not so clear that Heroku is doing it wrong.

bgentry 13y ago

the dyno routing algorithm now routes requests to random dynos That's not a change; that's how routing on Cedar has always worked.

thinkbohemian 13y ago
Random routing is more or less industry standard. NGINX and ELB (what I would consider two gold standards for load balancing) both use Round Robin (non-inteligent, pseudo-random) routing variants: - http://wiki.nginx.org/LoadBalanceExample http://wiki.nginx.org/LoadBalanceExample - http://serverfault.com/questions/537450/what-algorithm-does-amazon-elb-use-to-balance-load http://serverfault.com/questions/537450/what-algorithm-does-...
- ryderm 13y ago
  Round Robbin is certainly not equivalent to random, and is much much better for most applications. If all the requests take about the same amount of time, then round Robbin will give the request to the one that hasnt received a request in the longest amount of time, which is clearly the best choice in this situation. Randomized has a 1/n chance of handing the request to this less busy node, which is why the problem becomes worse as you scale.
  - mootpointer 13y ago
    The issue with round robin routing is that you can't do it in a distributed routing mesh. You need to share state between routers and that coordination overhead is non-trivial.

zrail 13y ago

This has been talked to death, but for the general case, for applications that can handle concurrent requests (like Rails with a rack server just a tiny bit smarter than Webrick), random routing works just as well as intelligent routing with far less coupling in the routing later, making it more robust and easier to manage and scale.

sync 13y ago
Rails servers like Unicorn can still only support ~4 concurrent requests on regular dynos (roughly 1 per virtualized core), lessening the problem but not solving it if you have many requests per second.
- jules 13y ago
  Actually that makes a tremendous difference. It is a bit difficult to explain but even 2 concurrent requests per dyno is a lot better than 1. As you go up from 2 to 3 to 4 the difference quickly becomes minimal. I'll try to explain why, but warning: hand waving ahead! The problem with only 1 concurrent request is that if that request takes long to process then it can block other requests that are queued up in that dyno. Lets say that 1% of the requests take long. If a dyno can process only 1 request concurrently then at each request there is a 0.01 chance that that will block other requests. If however it can process 4 concurrent requests, then the dyno will only be blocked if it gets 4 long requests at the same time. So there is only a 0.01^4 = 0.00000001 chance that a dyno will be blocked.
  - adrianpike 13y ago
    Not quite. If you keep routing to a blocked backend, any requests that hit that backend will have unacceptable latencies. Since the routing is essentially random, you'll still be fielding about 1/4 of your requests to that backend, so one long request winds up making 1/4 of all your requests have unacceptable latencies.
    - jules 13y ago