Uploaded image for project: 'ZooKeeper'
  1. ZooKeeper
  2. ZOOKEEPER-1018

The connection permutation in get_addrs uses a weak and inefficient shuffle

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: 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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                tyree731 Stephen Tyree
                Reporter:
                tyree731 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