Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

net: fix probabilities in shuffleByWeight #7098

Closed
msolo opened this issue Jan 10, 2014 · 7 comments
Closed

net: fix probabilities in shuffleByWeight #7098

msolo opened this issue Jan 10, 2014 · 7 comments
Milestone

Comments

@msolo
Copy link
Contributor

msolo commented Jan 10, 2014

It's a bit hard to reproduce since this method isn't exposed and doesn't have test cases
I can see.

When you have a DNS SRV entries with identical priorities and small weights, you don't
get a uniform distribution.

Say you have:

server-a priority:0 weight:1
server-b priority:0 weight:1

I would expect that ~50% of the time in a large number of samples that I would get
server-a first in the list returned by LookupSRV.

That's not what happens here. It's more like a 70-30 split - consistently.

In dnsclient.go:

  for sum > 0 && len(addrs) > 1 {
    s := 0
    n := rand.Intn(sum + 1) <-- I believe this increment is not necessary.
    for i := range addrs {
      s += int(addrs[i].Weight)
@msolo
Copy link
Contributor Author

msolo commented Feb 19, 2014

Comment 1:

Anything I can do to move this along?

@msolo
Copy link
Contributor Author

msolo commented Feb 20, 2014

Comment 2:

Actually, this is more subtle. It's not a fencepost error as I had thought just looking
at the base case.  There is a whole class of degenerate results when the sum of the
weights is small. Naturally, the uniformity of the results improves measurable once the
sum of the weights increases to ~100.
Probably the best thing is to add a weight multiplier to minimize the error when the sum
of weights is small.

@rsc
Copy link
Contributor

rsc commented Mar 3, 2014

Comment 3:

It sounds like you are saying Intn sucks. It shouldn't suck that much. I do think the
sum+1 should be sum. Can you be more specific about what else you think is wrong?

Labels changed: added release-go1.3maybe.

Status changed to Accepted.

@msolo
Copy link
Contributor Author

msolo commented Mar 4, 2014

Comment 4:

Disregard my comment about degenerate results - I jumped to the wrong conclusion.
I believe this is the correct fix is this:
diff --git a/src/pkg/net/dnsclient.go b/src/pkg/net/dnsclient.go
--- a/src/pkg/net/dnsclient.go
+++ b/src/pkg/net/dnsclient.go
@@ -191,10 +191,10 @@
    }
    for sum > 0 && len(addrs) > 1 {
        s := 0
-       n := rand.Intn(sum + 1)
+       n := rand.Intn(sum)
        for i := range addrs {
            s += int(addrs[i].Weight)
-           if s >= n {
+           if s > n {
                if i > 0 {
                    t := addrs[i]
                    copy(addrs[1:i+1], addrs[0:i])
I attached a test case or two that satisfied me.

Attachments:

  1. dnssrv_test.go (1465 bytes)

@rsc
Copy link
Contributor

rsc commented Apr 3, 2014

Comment 5:

Labels changed: added release-go1.3, removed release-go1.3maybe.

@gopherbot
Copy link

Comment 6:

CL https://golang.org/cl/88900044 mentions this issue.

@bradfitz
Copy link
Contributor

Comment 7:

This issue was closed by revision c45392b.

Status changed to Fixed.

@rsc rsc added this to the Go1.3 milestone Apr 14, 2015
@rsc rsc removed the release-go1.3 label Apr 14, 2015
@golang golang locked and limited conversation to collaborators Jun 25, 2016
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants