Maybe this is a dumb question, but wouldn't straightforward Round Robin routing by Heroku restore their "one dyno = one more concurrent request" promise without incurring the scaling liabilities of tracking load across an arbitrarily large number of dynos?
For this specific issue round robin isn't really any different from random routing. Anything that stands a good chance of queueing a request while other machines sit idle is going to be a problem.
The only way that round robin would be arguably better than random routing is if your random selection is not evenly distributed.
Sure, but the real issue the article identifies is that, under random routing, they need to keep doubling the number of dynos to halve the odds of bad queueing, which leads to absurd factor of 50 requirements to get back to what they had before. With round robin, the increase should be much more linear.
Over many requests, both should average to N requests served to each instance assuming a uniform random distribution.
The real issue is being able to figure out instances to avoid when some requests end up being slow. To put it another way, ideal balancing in this case isn't about evenly splitting all requests, but evenly splitting all processing (or waiting) time.
If you can guarantee that requests tend to take pretty stable and uniform time, then random or round-robin distribution should give good results. If you can't, some requests will be stuck waiting behind others and their waiting time will accumulate. You'll see worse behaviour when two or more of the bad slow requests get queued one after the other.
With round robin it's going to chose the dynos most likely to have the shortest queue given the simple information available. (longest time since it got something) so it's biased to putting stuff on empty queues.
Where as random picks randomly, so there's no bias to empty queues, so random should be less efficient.
