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. _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
