ZooKeeper
  1. ZooKeeper
  2. ZOOKEEPER-1018

The connection permutation in get_addrs uses a weak and inefficient shuffle

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 3.3.2
    • Fix Version/s: 3.4.0
    • Component/s: c client
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      Description

      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.

        Issue Links

          Activity

          No work has yet been logged on this issue.

            People

            • Assignee:
              Stephen Tyree
              Reporter:
              Stephen Tyree
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Time Tracking

                Estimated:
                Original Estimate - 2h
                2h
                Remaining:
                Remaining Estimate - 2h
                2h
                Logged:
                Time Spent - Not Specified
                Not Specified

                  Development