[ovs-dev] [PATCH 07/13] jsonrpc: Allow jsonrpc_session to have more than one remote.

[Ben Pfaff]

On Mon, Oct 09, 2017 at 03:57:18PM -0400, Russell Bryant wrote:
> On Fri, Oct 6, 2017 at 8:44 PM, Ben Pfaff <blp at ovn.org> 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 <blp at ovn.org>
> > ---
> >  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.