Hacker News Reader

Comment by tim_sw | Hacker News Reader

randomized routing is not necessarily bad if they look at 2 choices and pick the min. See http://en.wikipedia.org/wiki/2-choice_hashing and http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...

View on HN

This is a knee-jerk reply. I know, because my knee jerked as well. Think about the problem a little more: if you have the data necessary to pick the min-of-two, then you have the data you need to do intelligent routing.

Not necessarily. Heroku claims that a global request queue is hard to scale, and therefore they switched to random load balancing. The comment above shows that a global request queue is not necessary. Lets say that minimum-of-n scales up to 10 dynos. If your application requires 40 dynos, you can have one front load balancer which dispatches the requests to 4 back load balancers, each of which has 10 dynos assigned to them on which they perform min-of-10 routing. This gives you routing that's almost as good as min-of-40 but it scales up nonetheless.

> Heroku claims that a global request queue is hard to scale, and therefore they switched to random load balancing.

I wish Heroku would tell us more about what they tried. I can imagine a few cock-a-mimie schemes off the top of my head; it would be good to know whether they thought of those.

Assuming by intelligent, you mean minimally loaded, choice of 2 requires less bookkeeping than this. (choice of 2 requires only local (per-node level) info, where as most other intelligent load-balancing requires global info ie. the min, etc.)

Taking the case of minimally loaded, you need to keep track of how many active requests each node/replica is serving, as well as globally keeping track of the min. (which past a certain load, will suffer a lot of contention to update)

To do choice of 2, all you need is to keep track of active requests per node/replica.

Under spiky workloads, there is also a problem with choosing minimally loaded. The counter for numRequests of a node might not update fast enough, so that a bunch of requests will go to that node, quickly saturating its capacity.

Choice of 2 doesn't suffer this problem bec of its inherent randomization.

Reply on news.ycombinator.com