[PATCH] Upstream hash: speedup consistent hash init

[Wai Keen Woon]

# HG changeset patch
# User Wai Keen Woon <waikeen.woon at onapp.com>
# Date 1424259253 -28800
#      Wed Feb 18 19:34:13 2015 +0800
# Node ID 34578fd8055e08db2e7bf1e6637b26e92bb1a89b
# Parent  3f568dd68af147b5ba259a27fdc6645f99e87aa7
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 4s.

Replace this with a linear any-order insertion followed by qsort().
Startup time for total weight of 1000 reduces to 40ms.

Note that in the original implementation, if there are points
with duplicate hash, only the first is kept. In this change, all
are included.

diff -r 3f568dd68af1 -r 34578fd8055e 
src/http/modules/ngx_http_upstream_hash_module.c
--- a/src/http/modules/ngx_http_upstream_hash_module.c    Tue Feb 17 
16:27:52 2015 +0300
+++ b/src/http/modules/ngx_http_upstream_hash_module.c    Wed Feb 18 
19:34:13 2015 +0800
@@ -49,10 +49,10 @@

  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 ngx_uint_t ngx_http_upstream_find_chash_point(
      ngx_http_upstream_chash_points_t *points, uint32_t hash);
+static int ngx_libc_cdecl
+    ngx_http_upstream_chash_cmp(const void *one, const void *two);
  static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
      ngx_http_upstream_srv_conf_t *us);
  static ngx_int_t 
ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc,
@@ -360,12 +360,19 @@
              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);
+
+
      hcf = ngx_http_conf_upstream_srv_conf(us, 
ngx_http_upstream_hash_module);
      hcf->points = points;

@@ -373,31 +380,6 @@
  }


-static void
-ngx_http_upstream_add_chash_point(ngx_http_upstream_chash_points_t *points,
-    uint32_t hash, ngx_str_t *server)
-{
-    size_t                            size;
-    ngx_uint_t                        i;
-    ngx_http_upstream_chash_point_t  *point;
-
-    i = ngx_http_upstream_find_chash_point(points, hash);
-    point = &points->point[i];
-
-    if (point->hash == hash) {
-        return;
-    }
-
-    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;
-}
-
-
  static ngx_uint_t
  ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t 
*points,
      uint32_t hash)
@@ -430,6 +412,21 @@
  }


+static int ngx_libc_cdecl
+ngx_http_upstream_chash_cmp(const void *one, const void *two)
+{
+    if (((ngx_http_upstream_chash_point_t *) one)->hash <
+        ((ngx_http_upstream_chash_point_t *) two)->hash) {
+        return -1;
+    } else if (((ngx_http_upstream_chash_point_t *) one)->hash >
+               ((ngx_http_upstream_chash_point_t *) two)->hash) {
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+
  static ngx_int_t
  ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
      ngx_http_upstream_srv_conf_t *us)