<div dir="ltr">The <span style="font-family:arial,sans-serif;font-size:14px">commented out locking is to protect </span><font face="arial, sans-serif"><span style="font-size:14px">rrp.peers as other load balancing modules. If one would like to move </span></font><span style="font-family:arial,sans-serif;font-size:14px">rrp.peers to share </span><font face="arial, sans-serif"><span style="font-size:14px">memory, than the comment should be removed.</span></font></div>
<div class="gmail_extra"><br><br><div class="gmail_quote">2014-05-08 23:23 GMT+08:00 Steven Hartland <span dir="ltr"><<a href="mailto:steven.hartland@multiplay.co.uk" target="_blank">steven.hartland@multiplay.co.uk</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Be good to see this in core, currently we use the 3rd party module to achieve this:<br>
<a href="http://wiki.nginx.org/HttpUpstreamRequestHashModule" target="_blank">http://wiki.nginx.org/<u></u>HttpUpstreamRequestHashModule</a><br>
<br>
One question on the patch, you appear to have some commented out locking is<br>
this an oversight?<br>
<br>
Regards<br>
Steve<br>
<br>
----- Original Message ----- From: "Jianjun Zheng" <<a href="mailto:codeeply@gmail.com" target="_blank">codeeply@gmail.com</a>><br>
To: <<a href="mailto:nginx-devel@nginx.org" target="_blank">nginx-devel@nginx.org</a>><br>
Sent: Thursday, May 08, 2014 8:52 AM<br>
Subject: [PATCH] Upstream: add consistent hash module<div><div class="h5"><br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
usage example: cons_hash $request_uri;<br>
<br>
Not only consistent hash is introduced as a load balancing, but also<br>
increase the hits of cache in upstream servers.<br>
<br>
This modules is written according to round_robin, ip_hash<br>
and least_conn modules for upstream. So it inherits all the<br>
essential logic from them.<br>
<br>
This implementation is simple but has a high performance,<br>
The time comlexity remains O(log(T)) with a low constant coefficient,<br>
even when half of servers get down,<br>
regardless of the weight of servers, as analysis below.<br>
<br>
Suppose there are N upstream servers, with D down servers,<br>
and the weights are W1,W2,...,W(N-1).<br>
V is the amount of virtual nodes per unit.<br>
P is the probability to get an alive server from all nodes at random.<br>
<br>
Let T = (W1+W2+...+W(N-1))*V.<br>
then the space complexity is O(T),<br>
and the time comlexity is O(log(T) + (1-P)*N/(N-D)),<br>
'N/(N-D)' of which is independent of W and V.<br>
<br>
<br>
# HG changeset patch<br>
# User Jianjun Zheng <<a href="mailto:codeeply@gmail.com" target="_blank">codeeply@gmail.com</a>><br>
# Date 1399531525 -28800<br>
# Thu May 08 14:45:25 2014 +0800<br>
# Node ID 063f37f1654ef6cc03bd311a7fe618<u></u>9b299ce2f2<br>
# Parent 48c97d83ab7f0a3f641987fb32ace8<u></u>af7720aefc<br>
Upstream: add consistent hash module<br>
<br>
diff -r 48c97d83ab7f -r 063f37f1654e auto/modules<br>
--- a/auto/modules Tue Apr 29 22:22:38 2014 +0200<br>
+++ b/auto/modules Thu May 08 14:45:25 2014 +0800<br>
@@ -381,6 +381,11 @@<br>
HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_LEAST_CONN_<u></u>SRCS"<br>
fi<br>
<br>
+if [ $HTTP_UPSTREAM_CONS_HASH = YES ]; then<br>
+ HTTP_MODULES="$HTTP_MODULES $HTTP_UPSTREAM_CONS_HASH_<u></u>MODULE"<br>
+ HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_CONS_HASH_SRCS"<br>
+fi<br>
+<br>
if [ $HTTP_UPSTREAM_KEEPALIVE = YES ]; then<br>
HTTP_MODULES="$HTTP_MODULES $HTTP_UPSTREAM_KEEPALIVE_<u></u>MODULE"<br>
HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_KEEPALIVE_SRCS"<br>
diff -r 48c97d83ab7f -r 063f37f1654e auto/options<br>
--- a/auto/options Tue Apr 29 22:22:38 2014 +0200<br>
+++ b/auto/options Thu May 08 14:45:25 2014 +0800<br>
@@ -100,6 +100,7 @@<br>
HTTP_GZIP_STATIC=NO<br>
HTTP_UPSTREAM_IP_HASH=YES<br>
HTTP_UPSTREAM_LEAST_CONN=YES<br>
+HTTP_UPSTREAM_CONS_HASH=YES<br>
HTTP_UPSTREAM_KEEPALIVE=YES<br>
<br>
# STUB<br>
diff -r 48c97d83ab7f -r 063f37f1654e auto/sources<br>
--- a/auto/sources Tue Apr 29 22:22:38 2014 +0200<br>
+++ b/auto/sources Thu May 08 14:45:25 2014 +0800<br>
@@ -504,6 +504,11 @@<br>
src/http/modules/ngx_http_<u></u>upstream_least_conn_module.c"<br>
<br>
<br>
+HTTP_UPSTREAM_CONS_HASH_<u></u>MODULE=ngx_http_upstream_cons_<u></u>hash_module<br>
+HTTP_UPSTREAM_CONS_HASH_SRCS=<u></u>" \<br>
+ src/http/modules/ngx_http_<u></u>upstream_cons_hash_module.c"<br>
+<br>
+<br>
HTTP_UPSTREAM_KEEPALIVE_<u></u>MODULE=ngx_http_upstream_<u></u>keepalive_module<br>
HTTP_UPSTREAM_KEEPALIVE_SRCS=" \<br>
src/http/modules/ngx_http_<u></u>upstream_keepalive_module.c"<br>
diff -r 48c97d83ab7f -r 063f37f1654e<br>
src/http/modules/ngx_http_<u></u>upstream_cons_hash_module.c<br>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000<br>
+++ b/src/http/modules/ngx_http_<u></u>upstream_cons_hash_module.c Thu May 08<br>
14:45:25 2014 +0800<br>
@@ -0,0 +1,591 @@<br>
+#include <ngx_core.h><br>
+#include <ngx_http.h><br>
+#include <ngx_config.h><br>
+<br>
+<br>
+#define NGX_HTTP_UPSTREAM_CH_VNODE_NUM 141<br>
+<br>
+<br>
+typedef struct {<br>
+ uint32_t hash;<br>
+<br>
+ ngx_uint_t index;<br>
+} ngx_http_upstream_cons_hash_<u></u>node_t;<br>
+<br>
+<br>
+typedef struct {<br>
+ ngx_array_t *values;<br>
+ ngx_array_t *lengths;<br>
+<br>
+ ngx_uint_t node_number;<br>
+ ngx_http_upstream_cons_hash_<u></u>node_t *nodes;<br>
+<br>
+ ngx_uint_t *nearest;<br>
+<br>
+ ngx_http_upstream_rr_peers_t *peers;<br>
+<br>
+ ngx_log_t *log;<br>
+<br>
+ ngx_pool_t *pool;<br>
+} ngx_http_upstream_cons_hash_<u></u>conf_t;<br>
+<br>
+<br>
+typedef struct {<br>
+ /* the round robin data must be first */<br>
+ ngx_http_upstream_rr_peer_<u></u>data_t rrp;<br>
+<br>
+ ngx_uint_t found;<br>
+<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf;<br>
+<br>
+ ngx_event_get_peer_pt get_rr_peer;<br>
+} ngx_http_upstream_ch_peer_<u></u>data_t;<br>
+<br>
+<br>
+static void *ngx_http_upstream_cons_hash_<u></u>create_conf(ngx_conf_t *cf);<br>
+static char *ngx_http_upstream_cons_hash(<u></u>ngx_conf_t *cf, ngx_command_t<br>
*cmd,<br>
+ void *conf);<br>
+static ngx_int_t ngx_http_upstream_init_cons_<u></u>hash(ngx_conf_t *cf,<br>
+ ngx_http_upstream_srv_conf_t *us);<br>
+<br>
+static ngx_int_t ngx_http_upstream_init_cons_<u></u>hash_peer(ngx_http_request_t<br>
*r,<br>
+ ngx_http_upstream_srv_conf_t *us);<br>
+static ngx_int_t ngx_http_upstream_get_cons_<u></u>hash_peer(<br>
+ ngx_peer_connection_t *pc, void *data);<br>
+<br>
+static ngx_uint_t ngx_http_upstream_find_cons_<u></u>hash_peer(<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf, uint32_t hash);<br>
+static int ngx_http_upstream_cons_hash_<u></u>cmp_dist(const void *one,<br>
+ const void *two);<br>
+static int ngx_http_upstream_cons_hash_<u></u>cmp_node(const void *one,<br>
+ const void *two);<br>
+static ngx_int_t ngx_http_upstream_cons_hash_<u></u>random(<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf, ngx_str_t value, ngx_uint_t<br>
id,<br>
+ uint32_t *ret);<br>
+static ngx_int_t ngx_http_upstream_cons_hash_<u></u>init_nearest(<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf);<br>
+<br>
+inline static ngx_int_t ngx_http_upstream_get_cons_<u></u>hash_try_peer(<br>
+ ngx_peer_connection_t *pc, void *data, ngx_uint_t index);<br>
+<br>
+<br>
+static ngx_command_t ngx_http_upstream_cons_hash_<u></u>commands[] = {<br>
+<br>
+ { ngx_string("cons_hash"),<br>
+ NGX_HTTP_UPS_CONF | NGX_CONF_TAKE1,<br>
+ ngx_http_upstream_cons_hash,<br>
+ 0,<br>
+ 0,<br>
+ NULL },<br>
+<br>
+ ngx_null_command<br>
+};<br>
+<br>
+<br>
+static ngx_http_module_t ngx_http_upstream_cons_hash_<u></u>module_ctx = {<br>
+ NULL, /* preconfiguration */<br>
+ NULL, /* postconfiguration */<br>
+<br>
+ NULL, /* create main configuration */<br>
+ NULL, /* init main configuration */<br>
+<br>
+ ngx_http_upstream_cons_hash_<u></u>create_conf, /* create server<br>
configuration*/<br>
+ NULL, /* merge server configuration */<br>
+<br>
+ NULL, /* create location configuration<br>
*/<br>
+ NULL /* merge location configuration<br>
*/<br>
+};<br>
+<br>
+<br>
+ngx_module_t ngx_http_upstream_cons_hash_<u></u>module = {<br>
+ NGX_MODULE_V1,<br>
+ &ngx_http_upstream_cons_hash_<u></u>module_ctx, /* module context */<br>
+ ngx_http_upstream_cons_hash_<u></u>commands, /* module directives */<br>
+ NGX_HTTP_MODULE, /* module type */<br>
+ NULL, /* init master */<br>
+ NULL, /* init module */<br>
+ NULL, /* init process */<br>
+ NULL, /* init thread */<br>
+ NULL, /* exit thread */<br>
+ NULL, /* exit process */<br>
+ NULL, /* exit master */<br>
+ NGX_MODULE_V1_PADDING<br>
+};<br>
+<br>
+<br>
+static void *<br>
+ngx_http_upstream_cons_hash_<u></u>create_conf(ngx_conf_t *cf)<br>
+{<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *conf;<br>
+<br>
+ conf = ngx_pcalloc(cf->pool,<br>
sizeof(ngx_http_upstream_cons_<u></u>hash_conf_t));<br>
+ if (conf == NULL) {<br>
+ return NULL;<br>
+ }<br>
+<br>
+ return conf;<br>
+}<br>
+<br>
+<br>
+static ngx_int_t<br>
+ngx_http_upstream_init_cons_<u></u>hash(ngx_conf_t *cf,<br>
+ ngx_http_upstream_srv_conf_t *us)<br>
+{<br>
+ uint32_t hash;<br>
+ ngx_int_t rc;<br>
+ ngx_str_t name;<br>
+ ngx_uint_t i, j, k, n, nn, m;<br>
+ ngx_http_upstream_rr_peers_t *peers;<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf;<br>
+<br>
+ if (ngx_http_upstream_init_round_<u></u>robin(cf, us) == NGX_ERROR) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ peers = us->peer.data;<br>
+<br>
+ n = peers->number;<br>
+ nn = 0;<br>
+<br>
+ for (i = 0; i < n; ++i) {<br>
+ nn += peers->peer[i].weight;<br>
+ }<br>
+<br>
+ nn *= (NGX_HTTP_UPSTREAM_CH_VNODE_<u></u>NUM + 1);<br>
+<br>
+ chcf = ngx_http_conf_upstream_srv_<u></u>conf(us,<br>
+<br>
ngx_http_upstream_cons_hash_<u></u>module);<br>
+<br>
+ /*<br>
+ * to guarantee nn % n == 0, there's no side effect,<br>
+ * but much more convenient to construct the 'nearest'<br>
+ */<br>
+<br>
+ nn = (nn + n - 1) / n * n;<br>
+ chcf->node_number = nn;<br>
+<br>
+ chcf->log = cf->log;<br>
+ chcf->pool = cf->pool;<br>
+ chcf->peers = peers;<br>
+<br>
+ chcf->nodes = ngx_pcalloc(cf->pool, nn *<br>
+ sizeof(ngx_http_upstream_cons_<u></u>hash_node_t));<br>
+ if (chcf->nodes == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ for (i = 0, k = 0; i < n; ++i) {<br>
+<br>
+ name = peers->peer[i].name;<br>
+ m = peers->peer[i].weight * (1 + NGX_HTTP_UPSTREAM_CH_VNODE_<u></u>NUM);<br>
+<br>
+ for (j = 0; j < m; ++j, ++k) {<br>
+<br>
+ chcf->nodes[k].index = i;<br>
+<br>
+ rc = ngx_http_upstream_cons_hash_<u></u>random(chcf, name, j, &hash);<br>
+ if (rc == NGX_ERROR) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ chcf->nodes[k].hash = hash;<br>
+ }<br>
+ }<br>
+<br>
+ for (i = 0; i < nn - k; ++i) {<br>
+ chcf->nodes[k + i].index = chcf->nodes[0].index;<br>
+ chcf->nodes[k + i].hash = chcf->nodes[0].hash;<br>
+ }<br>
+<br>
+ ngx_qsort(chcf->nodes, nn, sizeof(ngx_http_upstream_cons_<u></u>hash_node_t),<br>
+ ngx_http_upstream_cons_hash_<u></u>cmp_node);<br>
+<br>
+ rc = ngx_http_upstream_cons_hash_<u></u>init_nearest(chcf);<br>
+ if (rc == NGX_ERROR) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ us->peer.init = ngx_http_upstream_init_cons_<u></u>hash_peer;<br>
+<br>
+ return NGX_OK;<br>
+}<br>
+<br>
+<br>
+static ngx_int_t<br>
+ngx_http_upstream_init_cons_<u></u>hash_peer(ngx_http_request_t *r,<br>
+ ngx_http_upstream_srv_conf_t *us)<br>
+{<br>
+ uint32_t hash;<br>
+ ngx_str_t raw_value;<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf;<br>
+ ngx_http_upstream_ch_peer_<u></u>data_t *chp;<br>
+<br>
+ chcf = ngx_http_conf_upstream_srv_<u></u>conf(us,<br>
+<br>
ngx_http_upstream_cons_hash_<u></u>module);<br>
+ if (chcf == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ chp = ngx_pcalloc(r->pool, sizeof(ngx_http_upstream_ch_<u></u>peer_data_t));<br>
+ if (chp == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ r->upstream->peer.data = &chp->rrp;<br>
+<br>
+ if (ngx_http_upstream_init_round_<u></u>robin_peer(r, us) != NGX_OK) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ if (!chp->rrp.peers->single) {<br>
+<br>
+ /* raw_value.data is allocated in ngx_http_script_run from r->pool<br>
*/<br>
+<br>
+ if (ngx_http_script_run(r, &raw_value,<br>
+ chcf->lengths->elts, 0, chcf->values->elts) ==<br>
NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ hash = ngx_murmur_hash2(raw_value.<u></u>data, raw_value.len);<br>
+<br>
+ ngx_pfree(r->pool, raw_value.data);<br>
+<br>
+ chp->found = ngx_http_upstream_find_cons_<u></u>hash_peer(chcf, hash);<br>
+ }<br>
+<br>
+ r->upstream->peer.get = ngx_http_upstream_get_cons_<u></u>hash_peer;<br>
+<br>
+ chp->chcf = chcf;<br>
+ chp->get_rr_peer = ngx_http_upstream_get_round_<u></u>robin_peer;<br>
+<br>
+ return NGX_OK;<br>
+}<br>
+<br>
+<br>
+inline static ngx_int_t<br>
+ngx_http_upstream_get_cons_<u></u>hash_try_peer(ngx_peer_<u></u>connection_t *pc, void<br>
*data,<br>
+ ngx_uint_t index)<br>
+{<br>
+ ngx_http_upstream_ch_peer_<u></u>data_t *chp = data;<br>
+<br>
+ time_t now;<br>
+ ngx_int_t rc;<br>
+ ngx_uint_t n, m;<br>
+ ngx_http_upstream_rr_peer_t *peer;<br>
+<br>
+ n = index / (8 * sizeof(uintptr_t));<br>
+ m = (uintptr_t) 1 << index % (8 * sizeof(uintptr_t));<br>
+<br>
+ if (chp->rrp.tried[n] & m) {<br>
+ return NGX_AGAIN;<br>
+ }<br>
+<br>
+ rc = NGX_AGAIN;<br>
+<br>
+ now = ngx_time();<br>
+<br>
+ peer = &chp->chcf->peers->peer[index]<u></u>;<br>
+<br>
+ /* ngx_lock_mutex(chp->rrp.peers-<u></u>>mutex); */<br>
+<br>
+ if (!peer->down) {<br>
+ if (peer->max_fails == 0 || peer->fails < peer->max_fails) {<br>
+ rc = NGX_OK;<br>
+ }<br>
+<br>
+ if (now - peer->checked > peer->fail_timeout) {<br>
+ peer->checked = now;<br>
+ rc = NGX_OK;<br>
+ }<br>
+ }<br>
+<br>
+ if (rc == NGX_OK) {<br>
+ chp->rrp.current = index;<br>
+<br>
+ pc->sockaddr = peer->sockaddr;<br>
+ pc->socklen = peer->socklen;<br>
+ pc->name = &peer->name;<br>
+ }<br>
+<br>
+ /* ngx_unlock_mutex(chp->rrp.<u></u>peers->mutex); */<br>
+<br>
+ chp->rrp.tried[n] |= m;<br>
+<br>
+ return rc;<br>
+}<br>
+<br>
+<br>
+static ngx_int_t<br>
+ngx_http_upstream_get_cons_<u></u>hash_peer(ngx_peer_connection_<u></u>t *pc, void *data)<br>
+{<br>
+ ngx_http_upstream_ch_peer_<u></u>data_t *chp = data;<br>
+<br>
+ ngx_int_t rc;<br>
+ ngx_uint_t i, j, n, nn;<br>
+ ngx_uint_t *nearest;<br>
+ ngx_http_upstream_rr_peers_t *peers;<br>
+ ngx_http_upstream_cons_hash_<u></u>node_t *nodes;<br>
+<br>
+ if (chp->rrp.peers->single) {<br>
+ return chp->get_rr_peer(pc, &chp->rrp);<br>
+ }<br>
+<br>
+ pc->cached = 0;<br>
+ pc->connection = NULL;<br>
+<br>
+ peers = chp->chcf->peers;<br>
+ nodes = chp->chcf->nodes;<br>
+ nearest = chp->chcf->nearest;<br>
+<br>
+ n = peers->number;<br>
+ nn = chp->chcf->node_number;<br>
+<br>
+ for (i = chp->found; i % n != 0; i = (i + 1) % nn) {<br>
+<br>
+ rc = ngx_http_upstream_get_cons_<u></u>hash_try_peer(pc, data,<br>
+ nodes[i].index);<br>
+ if (rc == NGX_OK) {<br>
+ return NGX_OK;<br>
+ }<br>
+ }<br>
+<br>
+ for (j = (i + n) % nn; i != j; i = (i + 1) % nn) {<br>
+<br>
+ rc = ngx_http_upstream_get_cons_<u></u>hash_try_peer(pc, data,<br>
+ nearest[i]);<br>
+ if (rc == NGX_OK) {<br>
+ return NGX_OK;<br>
+ }<br>
+ }<br>
+<br>
+ /* all peers failed, mark them as live for quick recovery */<br>
+<br>
+ for (i = 0; i < peers->number; i++) {<br>
+ peers->peer[i].fails = 0;<br>
+ }<br>
+<br>
+ pc->name = peers->name;<br>
+<br>
+ return NGX_BUSY;<br>
+}<br>
+<br>
+<br>
+static ngx_uint_t<br>
+ngx_http_upstream_find_cons_<u></u>hash_peer(ngx_http_upstream_<u></u>cons_hash_conf_t<br>
*chcf,<br>
+ uint32_t hash)<br>
+{<br>
+ uint32_t mid_hash;<br>
+ ngx_int_t l, r, mid;<br>
+<br>
+ l = 0;<br>
+ r = chcf->node_number - 1;<br>
+<br>
+ while (l <= r) {<br>
+ mid = (l + r) >> 1;<br>
+ mid_hash = chcf->nodes[mid].hash;<br>
+<br>
+ if (mid_hash < hash) {<br>
+ l = mid + 1;<br>
+ } else {<br>
+ r = mid - 1;<br>
+ }<br>
+ }<br>
+<br>
+ if (l == (ngx_int_t)chcf->node_number) {<br>
+ l = 0;<br>
+ }<br>
+<br>
+ return l;<br>
+}<br>
+<br>
+<br>
+static char *<br>
+ngx_http_upstream_cons_hash(<u></u>ngx_conf_t *cf, ngx_command_t *cmd, void *conf)<br>
+{<br>
+ ngx_str_t *value;<br>
+ ngx_http_script_compile_t sc;<br>
+ ngx_http_upstream_srv_conf_t *uscf;<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf;<br>
+<br>
+ uscf = ngx_http_conf_get_module_srv_<u></u>conf(cf, ngx_http_upstream_module);<br>
+<br>
+ chcf = ngx_http_conf_upstream_srv_<u></u>conf(uscf,<br>
+<br>
ngx_http_upstream_cons_hash_<u></u>module);<br>
+ if (uscf->peer.init_upstream) {<br>
+ ngx_conf_log_error(NGX_LOG_<u></u>WARN, cf, 0,<br>
+ "load balancing method redefined");<br>
+ }<br>
+ uscf->peer.init_upstream = ngx_http_upstream_init_cons_<u></u>hash;<br>
+<br>
+ value = cf->args->elts;<br>
+ ngx_memzero(&sc, sizeof(ngx_http_script_<u></u>compile_t));<br>
+<br>
+ <a href="http://sc.cf" target="_blank">sc.cf</a> = cf;<br>
+ sc.source = &value[1];<br>
+ sc.lengths = &chcf->lengths;;<br>
+ sc.values = &chcf->values;<br>
+ sc.complete_lengths = 1;<br>
+ sc.complete_values = 1;<br>
+<br>
+ if (ngx_http_script_compile(&sc) != NGX_OK) {<br>
+ return NGX_CONF_ERROR;<br>
+ }<br>
+<br>
+ uscf->flags = NGX_HTTP_UPSTREAM_CREATE<br>
+ |NGX_HTTP_UPSTREAM_WEIGHT<br>
+ |NGX_HTTP_UPSTREAM_MAX_FAILS<br>
+ |NGX_HTTP_UPSTREAM_FAIL_<u></u>TIMEOUT<br>
+ |NGX_HTTP_UPSTREAM_DOWN;<br>
+<br>
+ return NGX_CONF_OK;<br>
+}<br>
+<br>
+<br>
+static ngx_int_t<br>
+ngx_http_upstream_cons_hash_<u></u>random(ngx_http_upstream_cons_<u></u>hash_conf_t<br>
*chcf,<br>
+ ngx_str_t value, ngx_uint_t id, uint32_t *ret)<br>
+{<br>
+ /* repeatable random with same (val, id) */<br>
+<br>
+ u_char *buf, *pos;<br>
+ ngx_uint_t total;<br>
+<br>
+ total = NGX_INT_T_LEN + value.len;<br>
+<br>
+ buf = ngx_calloc(total, chcf->log);<br>
+ if (buf == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ pos = ngx_snprintf(buf, total, "%i-%*s", id, value.len, value.data);<br>
+<br>
+ *ret = ngx_murmur_hash2(buf, pos - buf);<br>
+<br>
+ ngx_free(buf);<br>
+<br>
+ return NGX_OK;<br>
+}<br>
+<br>
+<br>
+static ngx_int_t<br>
+ngx_http_upstream_cons_hash_<u></u>init_nearest(<br>
+ ngx_http_upstream_cons_hash_<u></u>conf_t *chcf)<br>
+{<br>
+ ngx_int_t k;<br>
+ ngx_uint_t i, j, n, nn;<br>
+ ngx_uint_t *nearest, *temp;<br>
+ ngx_http_upstream_cons_hash_<u></u>node_t *nodes;<br>
+<br>
+ n = chcf->peers->number;<br>
+ nn = chcf->node_number;<br>
+<br>
+ nodes = chcf->nodes;<br>
+<br>
+ nearest = ngx_pcalloc(chcf->pool, nn * sizeof(ngx_uint_t));<br>
+ if (nearest == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ chcf->nearest = nearest;<br>
+<br>
+ temp = ngx_pcalloc(chcf->pool, n * sizeof(ngx_uint_t));<br>
+ if (temp == NULL) {<br>
+ return NGX_ERROR;<br>
+ }<br>
+<br>
+ for (i = 0; i < nn; ++i) {<br>
+ nearest[i] = nn;<br>
+ }<br>
+<br>
+ for (i = 0; i < nn; i += n) {<br>
+ for (j = 0; j < n; ++j) {<br>
+ temp[j] = nn;<br>
+ }<br>
+ for (k = n - 1; k >= 0; --k) {<br>
+ temp[nodes[i + k].index] = i + k;<br>
+ }<br>
+ for (j = 0; j < n; ++j) {<br>
+ nearest[i + j] = temp[j];<br>
+ }<br>
+ }<br>
+<br>
+ ngx_pfree(chcf->pool, temp);<br>
+<br>
+ /* update the 'nearest' twice */<br>
+<br>
+ for (i = 0; i < 2; ++i) {<br>
+ for (k = nn - n; k >= 0; k -= n) {<br>
+ for (j = 0; j < n; ++j) {<br>
+ if (nearest[k + j] == nn) {<br>
+ nearest[k + j] = nearest[(k + j + n) % nn];<br>
+ }<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ for (i = 0; i < nn; i += n) {<br>
+<br>
+ /* there is no elt equals to nn in the 'nearest' now */<br>
+<br>
+ for (j = 0; j < n; ++j) {<br>
+ if (nearest[i + j] < i) {<br>
+ nearest[i + j] += nn;<br>
+ }<br>
+ }<br>
+<br>
+ ngx_qsort(nearest + i, n, sizeof(ngx_uint_t),<br>
+ ngx_http_upstream_cons_hash_<u></u>cmp_dist);<br>
+<br>
+ for (j = 0; j < n; ++j) {<br>
+ if (nearest[i + j] >= nn) {<br>
+ nearest[i + j] -= nn;<br>
+ }<br>
+ }<br>
+ }<br>
+<br>
+ for (i = 0; i < nn; ++i) {<br>
+ nearest[i] = nodes[nearest[i]].index;<br>
+ }<br>
+<br>
+ return NGX_OK;<br>
+}<br>
+<br>
+<br>
+static int<br>
+ngx_http_upstream_cons_hash_<u></u>cmp_dist(const void *one, const void *two)<br>
+{<br>
+ ngx_uint_t first, second;<br>
+<br>
+ first = *(ngx_uint_t *)one;<br>
+ second = *(ngx_uint_t *)two;<br>
+<br>
+ if (first < second) {<br>
+ return -1;<br>
+ }<br>
+<br>
+ if (first > second) {<br>
+ return 1;<br>
+ }<br>
+<br>
+ return 0;<br>
+}<br>
+<br>
+<br>
+static int<br>
+ngx_http_upstream_cons_hash_<u></u>cmp_node(const void *one, const void *two)<br>
+{<br>
+ ngx_http_upstream_cons_hash_<u></u>node_t *first, *second;<br>
+<br>
+ first = (ngx_http_upstream_cons_hash_<u></u>node_t *) one;<br>
+ second = (ngx_http_upstream_cons_hash_<u></u>node_t *) two;<br>
+<br>
+ if (first->hash < second->hash) {<br>
+ return -1;<br>
+ }<br>
+<br>
+ if (first->hash > second->hash) {<br>
+ return 1;<br>
+ }<br>
+<br>
+ return 0;<br>
+}<br>
<br>
</blockquote>
<br>
<br></div></div>
------------------------------<u></u>------------------------------<u></u>--------------------<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
______________________________<u></u>_________________<br>
nginx-devel mailing list<br>
<a href="mailto:nginx-devel@nginx.org" target="_blank">nginx-devel@nginx.org</a><br>
<a href="http://mailman.nginx.org/mailman/listinfo/nginx-devel" target="_blank">http://mailman.nginx.org/<u></u>mailman/listinfo/nginx-devel</a><br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
nginx-devel mailing list<br>
<a href="mailto:nginx-devel@nginx.org" target="_blank">nginx-devel@nginx.org</a><br>
<a href="http://mailman.nginx.org/mailman/listinfo/nginx-devel" target="_blank">http://mailman.nginx.org/<u></u>mailman/listinfo/nginx-devel</a><br>
</blockquote></div><br></div>