[PATCH] Upstream hash: speedup consistent hash init

[Roman Arutyunyan]

Hello,

On 18 Feb 2015, at 15:07, Wai Keen Woon <waikeen.woon at onapp.com> wrote:

> # 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.

Thanks, we’ll look into this.

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

This is the intended behaviour.  Consistent hash array is build over
server entries, but not addresses resolved from them.  Duplicate points
are ignored since most likely they refer to multiple addresses of
the same host.

[..]

--
Roman Arutyunyan