go-hostpool
go-hostpool copied to clipboard
Epsilon-Greedy seems an odd choice for a load-balancer
I would have assumed "two random choices" would have given a better lower average load.
Given that you're already tracking latency information for epsilon-greedy, implementing two random choices should be fairly straight-forward.
For more information on "two random choices", see http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf .
Interesting. This does sounds like it might have some useful properties. I'd love to see how this works out if you get a prototype implemented.
The Epsilon-Greedy is certainly an experiment, and it's on our to-do list to describe some of how that has worked in a few select cases at bitly. There are lots of cases where it's useless, but we've found at least one where it's very valuable.
Since epsilon greedy already has all the time tracking, the 'easiest' way to prototype this is just to directly replace the loop that does the selection that begins "if len(possibleHosts) != 0" near epsilon_greedy.go:130 . Note this is completely untested, but it does compile :)
switch n := len(possibleHosts); n {
case 0:
hostToUse = nil
case 1:
hostToUse = possibleHosts[0]
default: // n > 0
idx1 := rand.Intn(n)
h1 := possibleHosts[idx1]
// remove h1 from list of hosts -- sample without replacement
n--
possibleHosts[idx1] = possibleHosts[n]
possibleHosts = possibleHosts[:n]
idx2 := rand.Intn(n)
h2 := possibleHosts[idx2]
if h1.epsilonValue > h2.epsilonValue {
hostToUse = h1
} else {
hostToUse = h2
}
}
I'll unfortunately be unable to tes this further right now. I won't have time to play with this until closer to the end of May.
Just realized I never came back to play with this. I still think this change makes sense. Not sure how to test this to see if it actually gives more evenly distributed load though..