On Mon, Oct 9, 2017 at 4:11 PM, Ben Pfaff <[email protected]> wrote: > On Mon, Oct 09, 2017 at 03:57:18PM -0400, Russell Bryant wrote: >> On Fri, Oct 6, 2017 at 8:44 PM, Ben Pfaff <[email protected]> wrote: >> > The implementation cycles through the remotes in random order. This allows >> > clients to perform some load balancing across alternative implementations >> > of a service. >> > >> > Signed-off-by: Ben Pfaff <[email protected]> >> > --- >> > lib/jsonrpc.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++----- >> > lib/jsonrpc.h | 6 +++++- >> > lib/svec.c | 18 ++++++++++++++++++ >> > lib/svec.h | 1 + >> > 4 files changed, 72 insertions(+), 6 deletions(-) >> >> > diff --git a/lib/svec.c b/lib/svec.c >> > index 297a60ce14f9..c1b986bab108 100644 >> > --- a/lib/svec.c >> > +++ b/lib/svec.c >> > @@ -20,6 +20,7 @@ >> > #include <stdlib.h> >> > #include <string.h> >> > #include "openvswitch/dynamic-string.h" >> > +#include "random.h" >> > #include "util.h" >> > #include "openvswitch/vlog.h" >> > >> > @@ -174,6 +175,23 @@ svec_compact(struct svec *svec) >> > svec->n = j; >> > } >> > >> > +static void >> > +swap_strings(char **a, char **b) >> > +{ >> > + char *tmp = *a; >> > + *a = *b; >> > + *b = tmp; >> > +} >> > + >> > +void >> > +svec_shuffle(struct svec *svec) >> > +{ >> > + for (size_t i = 0; i < svec->n; i++) { >> > + size_t j = i + random_range(svec->n - i); >> > + swap_strings(&svec->names[i], &svec->names[j]); >> > + } >> > +} >> > + >> >> I'm not sure this is as random as we'd like. >> >> Even if there are 10 elements, the first element has a 50% chance of >> staying there, since it's only considered for a swap when i == 0. >> That extends to the general behavior that the closer an element is to >> the beginning, the better chance it has of staying near the beginning. >> >> Or am I reading it wrong? > > I don't think that's right. When 'n' is 10 and 'i' == 0, the first > element is swapped with a randomly chosen element, whose index is > random_range(10). > > This is the standard shuffling algorithm (unless I implemented it wrong, > which is possible). When 'i' is 0, it randomly selects any of the > elements in the array and makes that the first element. When 'i' is 1, > it randomly select any of the remaining elements in the array and makes > that the second element. In general, at each step, it randomly chooses > any of the elements that haven't been chosen yet as the next element. > > Did I get it wrong? It's easy to do that since shuffles are difficult > to test.
No, I got it wrong. Sorry. Acked-by: Russell Bryant <[email protected]> -- Russell Bryant _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
