Hacker News Reader

Comment by zenazn | Hacker News Reader

Randomized routing isn't all bad. In fact, if Heroku were to switch from purely random routing to minimum-of-two random routing, they'd perform asymptotically better [1].

[1]: http://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.p...

View on HN

If Heroku had the data needed to do minimum-of-two random routing, they'd have the data needed to do intelligent routing. The problem is not the algorithm itself: "decrement and reheap" isn't going to be a performance bottleneck. The problem is tracking the number of requests queued on the dyno.

If Heroku had the data needed to do minimum-of-two random routing, they'd have the data needed to do intelligent routing.

Not strictly true; imagine that they can query the load state of a dyno, but at some non-zero cost. (For example, that it requires contacting the dyno, because the load-balancer itself is distributed and doesn't have a global view.)

Then, contacting 2, and picking the better of the 2, remains a possible win compared to contacting more/all.

See for example the 'hedged request' strategy, referenced in a sibling thread by nostradaemons from a Jeff Dean Google paper, where 2 redundant requests are issued and the slower-to-respond is discarded (or even actively cancelled, in the 'tiered request' variant).

I'm not familiar with minimum-of-two-random routing, but it does seem like assigning request to dynos in sequence would perform much better than assigning randomly (ie in a scenario with n dyno capacity, request 1 => dyno 1, request 2 => dyno 2, ... request n => dyno n, request n+1 => dyno 1, ..., repeat)

That'd be probably significantly better than the case of (request i => dyno picked out of hat) for all i

That's essentially round-robin, but it still requires syncing the data of which dyno is next, which is probably what they're trying to avoid.

Thanks! Very useful.

Reply on news.ycombinator.com