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

Russell Bryant russell at ovn.org
Mon Oct 9 20:17:58 UTC 2017


On Mon, Oct 9, 2017 at 4:11 PM, Ben Pfaff <blp at ovn.org> 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 <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.

No, I got it wrong.  Sorry.

Acked-by: Russell Bryant <russell at ovn.org>

-- 
Russell Bryant


More information about the dev mailing list