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

Comments

Projects
None yet
4 participants
@msolo
Copy link
Contributor

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

This comment has been minimized.

Copy link
Contributor Author

commented Feb 19, 2014

Comment 1:

Anything I can do to move this along?
@msolo

This comment has been minimized.

Copy link
Contributor Author

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

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link
Contributor Author

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

This comment has been minimized.

Copy link
Contributor

commented Apr 3, 2014

Comment 5:

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

@gopherbot

This comment has been minimized.

Copy link

commented Apr 17, 2014

Comment 6:

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

This comment has been minimized.

Copy link
Member

commented Apr 17, 2014

Comment 7:

This issue was closed by revision c45392b.

Status changed to Fixed.

@msolo msolo added fixed labels Apr 17, 2014

@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.
You can’t perform that action at this time.