Epsilon-Greedy seems an odd choice for a load-balancer

[dgryski]

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 .

[jehiah]

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.

[dgryski]

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.

[dgryski]

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..