You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@zookeeper.apache.org by "Hadoop QA (JIRA)" <ji...@apache.org> on 2011/04/04 20:04:05 UTC
[jira] [Commented] (ZOOKEEPER-1018) The connection permutation in
get_addrs uses a weak and inefficient shuffle
[ https://issues.apache.org/jira/browse/ZOOKEEPER-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13015520#comment-13015520 ]
Hadoop QA commented on ZOOKEEPER-1018:
--------------------------------------
+1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12474749/ZOOKEEPER-1018.patch
against trunk revision 1087821.
+1 @author. The patch does not contain any @author tags.
+1 tests included. The patch appears to include 3 new or modified tests.
+1 javadoc. The javadoc tool did not generate any warning messages.
+1 javac. The applied patch does not increase the total number of javac compiler warnings.
+1 findbugs. The patch does not introduce any new Findbugs (version 1.3.9) warnings.
+1 release audit. The applied patch does not increase the total number of release audit warnings.
+1 core tests. The patch passed core unit tests.
+1 contrib tests. The patch passed contrib unit tests.
Test results: https://hudson.apache.org/hudson/job/PreCommit-ZOOKEEPER-Build/220//testReport/
Findbugs warnings: https://hudson.apache.org/hudson/job/PreCommit-ZOOKEEPER-Build/220//artifact/trunk/build/test/findbugs/newPatchFindbugsWarnings.html
Console output: https://hudson.apache.org/hudson/job/PreCommit-ZOOKEEPER-Build/220//console
This message is automatically generated.
> The connection permutation in get_addrs uses a weak and inefficient shuffle
> ---------------------------------------------------------------------------
>
> Key: ZOOKEEPER-1018
> URL: https://issues.apache.org/jira/browse/ZOOKEEPER-1018
> Project: ZooKeeper
> Issue Type: Improvement
> Components: c client
> Affects Versions: 3.3.2
> Reporter: Stephen Tyree
> Assignee: Stephen Tyree
> Priority: Minor
> Fix For: 3.4.0
>
> Attachments: ZOOKEEPER-1018.patch
>
> Original Estimate: 2h
> Remaining Estimate: 2h
>
> After determining all of the addresses in the get_addrs function in the C client, the connection is permuted using the following code:
> setup_random();
> /* Permute */
> for(i = 0; i < zh->addrs_count; i++) {
> struct sockaddr_storage *s1 = zh->addrs + random()%zh->addrs_count;
> struct sockaddr_storage *s2 = zh->addrs + random()%zh->addrs_count;
> if (s1 != s2) {
> struct sockaddr_storage t = *s1;
> *s1 = *s2;
> *s2 = t;
> }
> }
> Not only does this shuffle produce an uneven permutation, but it is half as efficient as the Fisher-Yates shuffle which produces an unbiased one. It seems like it would be a simple fix to increase the randomness and efficiency of the shuffle by switching over to using Fisher-Yates.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira