[PATCH] Random peer selection for implicit upstream defined by proxy_pass

[Anton Jouline]

Hello,
thanks for your response. Please see comments below.

On Wed, Sep 19, 2012 at 8:24 AM, Maxim Dounin <mdounin at mdounin.ru> wrote:
> Hello!
>
> ...
>
> Just enforcing random order of peers as originally suggested
> should be enough here.  The code in ngx_http_upstream_get_peer()
> will then select first one, which will be random one.

That's true, if you actually re-order the addresses in ctx->addrs array.
Perhaps, i was trying to solve it the wrong way, by instead initializing
the rrp->current to a random index. Because of that, i needed to modify
the ngx_http_upstream_get_peer(). If instead ctx->addrs already
contains items in random order, then it is not necessary.

> No, no, no.  I mean - always return names in random order from a
> resolver, even if DNS response is cached.  This should do the same
> as (1) but will cover other cases as well.
>

ah, ok. Thanks for clarification. Yes, this would work quite well.
The latest version of my patch (see below), now implements this
approach.

>> +    /* start at random index */
>> +    j = (int) ( (float)(peers->number) * (rand() / (RAND_MAX + 1.0)));
>> +
>>      rrp->peers = peers;
>> -    rrp->current = 0;
>> +    rrp->current = j;
>
> This looks overcomplicated.  The same thing can be done with
>
>        rrp->current = ngx_random() % peers->number.
>
> which is much more readable.

Agreed.

>>      for (i = 0; i < rrp->peers->number; i++) {
>>
>> -        n = i / (8 * sizeof(uintptr_t));
>> -        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
>> +        j = (i + rrp->current) % rrp->peers->number;
>> +        n = j / (8 * sizeof(uintptr_t));
>> +        m = (uintptr_t) 1 << j % (8 * sizeof(uintptr_t));
>
> Note this might affect peer selection in some situations.  If
> there are two peers with identical effective weight, peer
> selection now depends on rrp->current (previous peer tried in a
> normal case), while with previous code selection was stable and
> always used first one.

Yes, thanks for catching that. Possibly, other scenarios
were affected too... Which is not good.

Tried to fix that problem, but after various experiments, realized
that it all essentially comes down to the need to reorder items
in the addrs array in-place. Which is ok..., but again felt like
it was the wrong place to do that.

So, i decided instead to take a look at ngx_resolver code and
it turned out that it's actually very simple to randomize there,
since there is code already that copies the array from one place
in memory to another. Looked like that was ideal place for
changing the order via simple rotation.
Here is the new patch:



--- a/src/core/ngx_resolver.c
+++ b/src/core/ngx_resolver.c
@@ -88,6 +88,8 @@ static void *ngx_resolver_calloc(ngx_resolver_t *r,
size_t size);
 static void ngx_resolver_free(ngx_resolver_t *r, void *p);
 static void ngx_resolver_free_locked(ngx_resolver_t *r, void *p);
 static void *ngx_resolver_dup(ngx_resolver_t *r, void *src, size_t size);
+static in_addr_t *ngx_resolver_dup_rotated(ngx_resolver_t *r, in_addr_t *src,
+    u_short n);
 static u_char *ngx_resolver_log_error(ngx_log_t *log, u_char *buf, size_t len);


@@ -445,8 +447,8 @@ ngx_resolve_name_locked(ngx_resolver_t *r,
ngx_resolver_ctx_t *ctx)

                 if (naddrs != 1) {
                     addr = 0;
-                    addrs = ngx_resolver_dup(r, rn->u.addrs,
-                                             naddrs * sizeof(in_addr_t));
+                    addrs = ngx_resolver_dup_rotated(r, rn->u.addrs,
+                                             naddrs);
                     if (addrs == NULL) {
                         return NGX_ERROR;
                     }
@@ -1381,8 +1383,7 @@ ngx_resolver_process_a(ngx_resolver_t *r, u_char
*buf, size_t last,

             rn->u.addrs = addrs;

-            addrs = ngx_resolver_dup(r, rn->u.addrs,
-                                     naddrs * sizeof(in_addr_t));
+            addrs = ngx_resolver_dup_rotated(r, rn->u.addrs, naddrs);
             if (addrs == NULL) {
                 return;
             }
@@ -2134,6 +2135,32 @@ ngx_resolver_dup(ngx_resolver_t *r, void *src,
size_t size)
     return dst;
 }

+static in_addr_t *
+ngx_resolver_dup_rotated(ngx_resolver_t *r, in_addr_t *src, u_short n)
+{
+    in_addr_t  *dst;
+    int        j;
+
+    dst = ngx_resolver_alloc(r, n * sizeof(in_addr_t));
+
+    if (dst == NULL) {
+        return dst;
+    }
+
+    j = ngx_random() % n;
+
+#if (NGX_DEBUG)
+    ngx_log_debug1(NGX_LOG_DEBUG_CORE, ngx_cycle->log, 0,
+                   "random rotation of addrs: %d", j);
+#endif
+
+    ngx_memcpy(dst, src + j, (n - j) * sizeof(in_addr_t));
+    if (j > 0) {
+        ngx_memcpy(dst + (n - j), src, j * sizeof(in_addr_t));
+    }
+
+    return dst;
+}

 char *
 ngx_resolver_strerror(ngx_int_t err)