# HG changeset patch # User Maxim Dounin # Date 1336989440 0 # Node ID c90801720a0c6f48d88d7a25dd667396c5866742 # Parent 204b780a89de4361bd1c6fe16f0e7c1fe90287d0 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). diff --git a/src/http/ngx_http_upstream_round_robin.c b/src/http/ngx_http_upstream_round_robin.c --- 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--; } diff --git a/src/http/ngx_http_upstream_round_robin.h b/src/http/ngx_http_upstream_round_robin.h --- 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;