[jira] [Updated] (ZOOKEEPER-1018) The connection permutation in get_addrs uses a weak and inefficient shuffle

["Stephen Tyree (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/ZOOKEEPER-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Stephen Tyree updated ZOOKEEPER-1018:
-------------------------------------

    Attachment: ZOOKEEPER-1018.patch

The reason the unit tests failed was due to the change in how random numbers impacted the order of servers. The code for shuffling addresses is correct, and making everything work just required changing a few numbers in the Mock_random generator.

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