Mercurial > hg > nginx

changeset 4621:c90801720a0c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Upstream: smooth weighted round-robin balancing. For edge case weights like { 5, 1, 1 } we now produce { a, a, b, a, c, a, a } sequence instead of { c, b, a, a, a, a, a } produced previously. Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers. In case of { 5, 1, 1 } weights this gives the following sequence of current_weight's: a b c 0 0 0 (initial state) 5 1 1 (a selected) -2 1 1 3 2 2 (a selected) -4 2 2 1 3 3 (b selected) 1 -4 3 6 -3 4 (a selected) -1 -3 4 4 -2 5 (c selected) 4 -2 -2 9 -1 -1 (a selected) 2 -1 -1 7 0 0 (a selected) 0 0 0 To preserve weight reduction in case of failures the effective_weight variable was introduced, which usually matches peer's weight, but is reduced temporarily on peer failures. This change also fixes loop with backup servers and proxy_next_upstream http_404 (ticket #47), and skipping alive upstreams in some cases if there are multiple dead ones (ticket #64).
author Maxim Dounin <mdounin@mdounin.ru>
date Mon, 14 May 2012 09:57:20 +0000
parents 204b780a89de
children 0dfdc3f732cb
files src/http/ngx_http_upstream_round_robin.c src/http/ngx_http_upstream_round_robin.h
diffstat 2 files changed, 74 insertions(+), 171 deletions(-) [+]
line wrap: on
line diff
--- a/src/http/ngx_http_upstream_round_robin.c
+++ b/src/http/ngx_http_upstream_round_robin.c
@@ -12,8 +12,8 @@
 
 static ngx_int_t ngx_http_upstream_cmp_servers(const void *one,
     const void *two);
-static ngx_uint_t
-ngx_http_upstream_get_peer(ngx_http_upstream_rr_peers_t *peers);
+static ngx_http_upstream_rr_peer_t *ngx_http_upstream_get_peer(
+    ngx_http_upstream_rr_peer_data_t *rrp);
 
 #if (NGX_HTTP_SSL)
 
@@ -81,7 +81,8 @@ ngx_http_upstream_init_round_robin(ngx_c
                 peers->peer[n].fail_timeout = server[i].fail_timeout;
                 peers->peer[n].down = server[i].down;
                 peers->peer[n].weight = server[i].down ? 0 : server[i].weight;
-                peers->peer[n].current_weight = peers->peer[n].weight;
+                peers->peer[n].effective_weight = peers->peer[n].weight;
+                peers->peer[n].current_weight = 0;
                 n++;
             }
         }
@@ -131,7 +132,8 @@ ngx_http_upstream_init_round_robin(ngx_c
                 backup->peer[n].socklen = server[i].addrs[j].socklen;
                 backup->peer[n].name = server[i].addrs[j].name;
                 backup->peer[n].weight = server[i].weight;
-                backup->peer[n].current_weight = server[i].weight;
+                backup->peer[n].effective_weight = server[i].weight;
+                backup->peer[n].current_weight = 0;
                 backup->peer[n].max_fails = server[i].max_fails;
                 backup->peer[n].fail_timeout = server[i].fail_timeout;
                 backup->peer[n].down = server[i].down;
@@ -190,7 +192,8 @@ ngx_http_upstream_init_round_robin(ngx_c
         peers->peer[i].socklen = u.addrs[i].socklen;
         peers->peer[i].name = u.addrs[i].name;
         peers->peer[i].weight = 1;
-        peers->peer[i].current_weight = 1;
+        peers->peer[i].effective_weight = 1;
+        peers->peer[i].current_weight = 0;
         peers->peer[i].max_fails = 1;
         peers->peer[i].fail_timeout = 10;
     }
@@ -306,7 +309,8 @@ ngx_http_upstream_create_round_robin_pee
         peers->peer[0].socklen = ur->socklen;
         peers->peer[0].name = ur->host;
         peers->peer[0].weight = 1;
-        peers->peer[0].current_weight = 1;
+        peers->peer[0].effective_weight = 1;
+        peers->peer[0].current_weight = 0;
         peers->peer[0].max_fails = 1;
         peers->peer[0].fail_timeout = 10;
 
@@ -338,7 +342,8 @@ ngx_http_upstream_create_round_robin_pee
             peers->peer[i].name.len = len;
             peers->peer[i].name.data = p;
             peers->peer[i].weight = 1;
-            peers->peer[i].current_weight = 1;
+            peers->peer[i].effective_weight = 1;
+            peers->peer[i].current_weight = 0;
             peers->peer[i].max_fails = 1;
             peers->peer[i].fail_timeout = 10;
         }
@@ -378,8 +383,6 @@ ngx_http_upstream_get_round_robin_peer(n
 {
     ngx_http_upstream_rr_peer_data_t  *rrp = data;
 
-    time_t                         now;
-    uintptr_t                      m;
     ngx_int_t                      rc;
     ngx_uint_t                     i, n;
     ngx_connection_t              *c;
@@ -389,8 +392,6 @@ ngx_http_upstream_get_round_robin_peer(n
     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                    "get rr peer, try: %ui", pc->tries);
 
-    now = ngx_time();
-
     /* ngx_lock_mutex(rrp->peers->mutex); */
 
     if (rrp->peers->last_cached) {
@@ -423,118 +424,15 @@ ngx_http_upstream_get_round_robin_peer(n
 
         /* there are several peers */
 
-        if (pc->tries == rrp->peers->number) {
-
-            /* it's a first try - get a current peer */
-
-            i = pc->tries;
-
-            for ( ;; ) {
-                rrp->current = ngx_http_upstream_get_peer(rrp->peers);
-
-                ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
-                               "get rr peer, current: %ui %i",
-                               rrp->current,
-                               rrp->peers->peer[rrp->current].current_weight);
-
-                n = rrp->current / (8 * sizeof(uintptr_t));
-                m = (uintptr_t) 1 << rrp->current % (8 * sizeof(uintptr_t));
-
-                if (!(rrp->tried[n] & m)) {
-                    peer = &rrp->peers->peer[rrp->current];
-
-                    if (!peer->down) {
-
-                        if (peer->max_fails == 0
-                            || peer->fails < peer->max_fails)
-                        {
-                            break;
-                        }
-
-                        if (now - peer->checked > peer->fail_timeout) {
-                            peer->checked = now;
-                            break;
-                        }
-
-                        peer->current_weight = 0;
-
-                    } else {
-                        rrp->tried[n] |= m;
-                    }
-
-                    pc->tries--;
-                }
-
-                if (pc->tries == 0) {
-                    goto failed;
-                }
-
-                if (--i == 0) {
-                    ngx_log_error(NGX_LOG_ALERT, pc->log, 0,
-                                  "round robin upstream stuck on %ui tries",
-                                  pc->tries);
-                    goto failed;
-                }
-            }
+        peer = ngx_http_upstream_get_peer(rrp);
 
-            peer->current_weight--;
-
-        } else {
-
-            i = pc->tries;
-
-            for ( ;; ) {
-                n = rrp->current / (8 * sizeof(uintptr_t));
-                m = (uintptr_t) 1 << rrp->current % (8 * sizeof(uintptr_t));
-
-                if (!(rrp->tried[n] & m)) {
-
-                    peer = &rrp->peers->peer[rrp->current];
-
-                    if (!peer->down) {
-
-                        if (peer->max_fails == 0
-                            || peer->fails < peer->max_fails)
-                        {
-                            break;
-                        }
-
-                        if (now - peer->checked > peer->fail_timeout) {
-                            peer->checked = now;
-                            break;
-                        }
-
-                        peer->current_weight = 0;
-
-                    } else {
-                        rrp->tried[n] |= m;
-                    }
-
-                    pc->tries--;
-                }
-
-                rrp->current++;
-
-                if (rrp->current >= rrp->peers->number) {
-                    rrp->current = 0;
-                }
-
-                if (pc->tries == 0) {
-                    goto failed;
-                }
-
-                if (--i == 0) {
-                    ngx_log_error(NGX_LOG_ALERT, pc->log, 0,
-                                  "round robin upstream stuck on %ui tries",
-                                  pc->tries);
-                    goto failed;
-                }
-            }
-
-            peer->current_weight--;
+        if (peer == NULL) {
+            goto failed;
         }
 
-        rrp->tried[n] |= m;
+        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
+                       "get rr peer, current: %ui %i",
+                       rrp->current, peer->current_weight);
     }
 
     pc->sockaddr = peer->sockaddr;
@@ -545,11 +443,6 @@ ngx_http_upstream_get_round_robin_peer(n
 
     if (pc->tries == 1 && rrp->peers->next) {
         pc->tries += rrp->peers->next->number;
-
-        n = rrp->peers->next->number / (8 * sizeof(uintptr_t)) + 1;
-        for (i = 0; i < n; i++) {
-             rrp->tried[i] = 0;
-        }
     }
 
     return NGX_OK;
@@ -595,56 +488,71 @@ failed:
 }
 
 
-static ngx_uint_t
-ngx_http_upstream_get_peer(ngx_http_upstream_rr_peers_t *peers)
+static ngx_http_upstream_rr_peer_t *
+ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
 {
-    ngx_uint_t                    i, n, reset = 0;
-    ngx_http_upstream_rr_peer_t  *peer;
-
-    peer = &peers->peer[0];
-
-    for ( ;; ) {
+    time_t                        now;
+    uintptr_t                     m;
+    ngx_int_t                     total;
+    ngx_uint_t                    i, n;
+    ngx_http_upstream_rr_peer_t  *peer, *best;
 
-        for (i = 0; i < peers->number; i++) {
+    now = ngx_time();
 
-            if (peer[i].current_weight <= 0) {
-                continue;
-            }
-
-            n = i;
-
-            while (i < peers->number - 1) {
+    best = NULL;
+    total = 0;
 
-                i++;
+    for (i = 0; i < rrp->peers->number; i++) {
 
-                if (peer[i].current_weight <= 0) {
-                    continue;
-                }
+        n = i / (8 * sizeof(uintptr_t));
+        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
 
-                if (peer[n].current_weight * 1000 / peer[i].current_weight
-                    > peer[n].weight * 1000 / peer[i].weight)
-                {
-                    return n;
-                }
+        if (rrp->tried[n] & m) {
+            continue;
+        }
 
-                n = i;
-            }
+        peer = &rrp->peers->peer[i];
 
-            if (peer[i].current_weight > 0) {
-                n = i;
-            }
-
-            return n;
+        if (peer->down) {
+            continue;
         }
 
-        if (reset++) {
-            return 0;
+        if (peer->max_fails
+            && peer->fails >= peer->max_fails
+            && now - peer->checked <= peer->fail_timeout)
+        {
+            continue;
+        }
+
+        peer->current_weight += peer->effective_weight;
+        total += peer->effective_weight;
+
+        if (peer->effective_weight < peer->weight) {
+            peer->effective_weight++;
         }
 
-        for (i = 0; i < peers->number; i++) {
-            peer[i].current_weight = peer[i].weight;
+        if (best == NULL || peer->current_weight > best->current_weight) {
+            best = peer;
         }
     }
+
+    if (best == NULL) {
+        return NULL;
+    }
+
+    i = best - &rrp->peers->peer[0];
+
+    rrp->current = i;
+
+    n = i / (8 * sizeof(uintptr_t));
+    m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
+
+    rrp->tried[n] |= m;
+
+    best->current_weight -= total;
+    best->checked = now;
+
+    return best;
 }
 
 
@@ -683,15 +591,15 @@ ngx_http_upstream_free_round_robin_peer(
         peer->checked = now;
 
         if (peer->max_fails) {
-            peer->current_weight -= peer->weight / peer->max_fails;
+            peer->effective_weight -= peer->weight / peer->max_fails;
         }
 
         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                        "free rr peer failed: %ui %i",
-                       rrp->current, peer->current_weight);
+                       rrp->current, peer->effective_weight);
 
-        if (peer->current_weight < 0) {
-            peer->current_weight = 0;
+        if (peer->effective_weight < 0) {
+            peer->effective_weight = 0;
         }
 
         /* ngx_unlock_mutex(rrp->peers->mutex); */
@@ -705,12 +613,6 @@ ngx_http_upstream_free_round_robin_peer(
         }
     }
 
-    rrp->current++;
-
-    if (rrp->current >= rrp->peers->number) {
-        rrp->current = 0;
-    }
-
     if (pc->tries) {
         pc->tries--;
     }
--- a/src/http/ngx_http_upstream_round_robin.h
+++ b/src/http/ngx_http_upstream_round_robin.h
@@ -20,6 +20,7 @@ typedef struct {
     ngx_str_t                       name;
 
     ngx_int_t                       current_weight;
+    ngx_int_t                       effective_weight;
     ngx_int_t                       weight;
 
     ngx_uint_t                      fails;