details: http://hg.nginx.org/nginx/rev/435ee290c2e1
branches:
changeset: 5991:435ee290c2e1
user: Roman Arutyunyan <arut@nginx.com>
date: Mon Mar 02 18:41:29 2015 +0300
description:
Upstream hash: speedup consistent hash init.

Repeatedly calling ngx_http_upstream_add_chash_point() to create
the points array in sorted order, is O(n^2) to the total weight.
This can cause nginx startup and reconfigure to be substantially
delayed. For example, when total weight is 1000, startup takes
5s on a modern laptop.

Replace this with a linear insertion followed by QuickSort and
duplicates removal. Startup for total weight of 1000 reduces to 40ms.

Based on a patch by Wai Keen Woon.

diffstat:

src/http/modules/ngx_http_upstream_hash_module.c | 52 ++++++++++++++---------
1 files changed, 31 insertions(+), 21 deletions(-)

diffs (85 lines):

diff -r 6a7c6973d6fc -r 435ee290c2e1 src/http/modules/ngx_http_upstream_hash_module.c
--- a/src/http/modules/ngx_http_upstream_hash_module.c Fri Feb 27 16:28:31 2015 +0300
+++ b/src/http/modules/ngx_http_upstream_hash_module.c Mon Mar 02 18:41:29 2015 +0300
@@ -49,8 +49,8 @@ static ngx_int_t ngx_http_upstream_get_h

static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf,
ngx_http_upstream_srv_conf_t *us);
-static void ngx_http_upstream_add_chash_point(
- ngx_http_upstream_chash_points_t *points, uint32_t hash, ngx_str_t *server);
+static int ngx_libc_cdecl
+ ngx_http_upstream_chash_cmp_points(const void *one, const void *two);
static ngx_uint_t ngx_http_upstream_find_chash_point(
ngx_http_upstream_chash_points_t *points, uint32_t hash);
static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
@@ -360,12 +360,27 @@ ngx_http_upstream_init_chash(ngx_conf_t
ngx_crc32_update(&hash, (u_char *) &prev_hash, sizeof(uint32_t));
ngx_crc32_final(hash);

- ngx_http_upstream_add_chash_point(points, hash, &peer->server);
+ points->point[points->number].hash = hash;
+ points->point[points->number].server = server;
+ points->number++;

prev_hash = hash;
}
}

+ ngx_qsort(points->point,
+ points->number,
+ sizeof(ngx_http_upstream_chash_point_t),
+ ngx_http_upstream_chash_cmp_points);
+
+ for (i = 0, j = 1; j < points->number; j++) {
+ if (points->point[i].hash != points->point[j].hash) {
+ points->point[++i] = points->point[j];
+ }
+ }
+
+ points->number = i + 1;
+
hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
hcf->points = points;

@@ -373,28 +388,23 @@ ngx_http_upstream_init_chash(ngx_conf_t
}


-static void
-ngx_http_upstream_add_chash_point(ngx_http_upstream_chash_points_t *points,
- uint32_t hash, ngx_str_t *server)
+static int ngx_libc_cdecl
+ngx_http_upstream_chash_cmp_points(const void *one, const void *two)
{
- size_t size;
- ngx_uint_t i;
- ngx_http_upstream_chash_point_t *point;
+ ngx_http_upstream_chash_point_t *first =
+ (ngx_http_upstream_chash_point_t *) one;
+ ngx_http_upstream_chash_point_t *second =
+ (ngx_http_upstream_chash_point_t *) two;

- i = ngx_http_upstream_find_chash_point(points, hash);
- point = &points->point[i];
+ if (first->hash < second->hash) {
+ return -1;

- if (point->hash == hash) {
- return;
+ } else if (first->hash > second->hash) {
+ return 1;
+
+ } else {
+ return 0;
}
-
- size = (points->number - i) * sizeof(ngx_http_upstream_chash_point_t);
-
- ngx_memmove(point + 1, point, size);
-
- points->number++;
- point->hash = hash;
- point->server = server;
}



_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel