<div dir="ltr"><div><div>usage example: cons_hash $request_uri;</div><div><br></div><div>Not only consistent hash is introduced as a load balancing, but also</div><div>increase the hits of cache in upstream servers.</div><div>
<br></div><div>This modules is written according to round_robin, ip_hash</div><div>and least_conn modules for upstream. So it inherits all the</div><div>essential logic from them.</div><div><br></div><div>This implementation is simple but has a high performance,</div>
<div>The time comlexity remains O(log(T)) with a low constant coefficient,</div><div>even when half of servers get down,</div><div>regardless of the weight of servers, as analysis below.</div><div><br></div><div>Suppose there are N upstream servers, with D down servers,</div>
<div>and the weights are W1,W2,...,W(N-1).</div><div>V is the amount of virtual nodes per unit.</div><div>P is the probability to get an alive server from all nodes at random.</div><div><br></div><div>Let T = (W1+W2+...+W(N-1))*V.</div>
<div>then the space complexity is O(T),</div><div>and the time comlexity is O(log(T) + (1-P)*N/(N-D)),</div><div>'N/(N-D)' of which is independent of W and V.</div></div><div><br></div><div><br></div><div><div># HG changeset patch</div>
<div># User Jianjun Zheng <<a href="mailto:codeeply@gmail.com">codeeply@gmail.com</a>></div><div># Date 1399531525 -28800</div><div># Thu May 08 14:45:25 2014 +0800</div><div># Node ID 063f37f1654ef6cc03bd311a7fe6189b299ce2f2</div>
<div># Parent 48c97d83ab7f0a3f641987fb32ace8af7720aefc</div><div>Upstream: add consistent hash module</div><div><br></div><div>diff -r 48c97d83ab7f -r 063f37f1654e auto/modules</div><div>--- a/auto/modules<span class="" style="white-space:pre"> </span>Tue Apr 29 22:22:38 2014 +0200</div>
<div>+++ b/auto/modules<span class="" style="white-space:pre"> </span>Thu May 08 14:45:25 2014 +0800</div><div>@@ -381,6 +381,11 @@</div><div> HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_LEAST_CONN_SRCS"</div><div>
fi</div><div> </div><div>+if [ $HTTP_UPSTREAM_CONS_HASH = YES ]; then</div><div>+ HTTP_MODULES="$HTTP_MODULES $HTTP_UPSTREAM_CONS_HASH_MODULE"</div><div>+ HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_CONS_HASH_SRCS"</div>
<div>+fi</div><div>+</div><div> if [ $HTTP_UPSTREAM_KEEPALIVE = YES ]; then</div><div> HTTP_MODULES="$HTTP_MODULES $HTTP_UPSTREAM_KEEPALIVE_MODULE"</div><div> HTTP_SRCS="$HTTP_SRCS $HTTP_UPSTREAM_KEEPALIVE_SRCS"</div>
<div>diff -r 48c97d83ab7f -r 063f37f1654e auto/options</div><div>--- a/auto/options<span class="" style="white-space:pre"> </span>Tue Apr 29 22:22:38 2014 +0200</div><div>+++ b/auto/options<span class="" style="white-space:pre"> </span>Thu May 08 14:45:25 2014 +0800</div>
<div>@@ -100,6 +100,7 @@</div><div> HTTP_GZIP_STATIC=NO</div><div> HTTP_UPSTREAM_IP_HASH=YES</div><div> HTTP_UPSTREAM_LEAST_CONN=YES</div><div>+HTTP_UPSTREAM_CONS_HASH=YES</div><div> HTTP_UPSTREAM_KEEPALIVE=YES</div><div>
</div><div> # STUB</div><div>diff -r 48c97d83ab7f -r 063f37f1654e auto/sources</div><div>--- a/auto/sources<span class="" style="white-space:pre"> </span>Tue Apr 29 22:22:38 2014 +0200</div><div>+++ b/auto/sources<span class="" style="white-space:pre"> </span>Thu May 08 14:45:25 2014 +0800</div>
<div>@@ -504,6 +504,11 @@</div><div> src/http/modules/ngx_http_upstream_least_conn_module.c"</div><div> </div><div> </div><div>+HTTP_UPSTREAM_CONS_HASH_MODULE=ngx_http_upstream_cons_hash_module</div><div>+HTTP_UPSTREAM_CONS_HASH_SRCS=" \</div>
<div>+ src/http/modules/ngx_http_upstream_cons_hash_module.c"</div><div>+</div><div>+</div><div> HTTP_UPSTREAM_KEEPALIVE_MODULE=ngx_http_upstream_keepalive_module</div><div> HTTP_UPSTREAM_KEEPALIVE_SRCS=" \</div>
<div> src/http/modules/ngx_http_upstream_keepalive_module.c"</div><div>diff -r 48c97d83ab7f -r 063f37f1654e src/http/modules/ngx_http_upstream_cons_hash_module.c</div><div>--- /dev/null<span class="" style="white-space:pre"> </span>Thu Jan 01 00:00:00 1970 +0000</div>
<div>+++ b/src/http/modules/ngx_http_upstream_cons_hash_module.c<span class="" style="white-space:pre"> </span>Thu May 08 14:45:25 2014 +0800</div><div>@@ -0,0 +1,591 @@</div><div>+#include <ngx_core.h></div><div>+#include <ngx_http.h></div>
<div>+#include <ngx_config.h></div><div>+</div><div>+</div><div>+#define NGX_HTTP_UPSTREAM_CH_VNODE_NUM 141</div><div>+</div><div>+</div><div>+typedef struct {</div><div>+ uint32_t hash;</div>
<div>+</div><div>+ ngx_uint_t index;</div><div>+} ngx_http_upstream_cons_hash_node_t;</div><div>+</div><div>+</div><div>+typedef struct {</div><div>+ ngx_array_t *values;</div>
<div>+ ngx_array_t *lengths;</div><div>+</div><div>+ ngx_uint_t node_number;</div><div>+ ngx_http_upstream_cons_hash_node_t *nodes;</div><div>+</div><div>+ ngx_uint_t *nearest;</div>
<div>+</div><div>+ ngx_http_upstream_rr_peers_t *peers;</div><div>+</div><div>+ ngx_log_t *log;</div><div>+</div><div>+ ngx_pool_t *pool;</div><div>+} ngx_http_upstream_cons_hash_conf_t;</div>
<div>+</div><div>+</div><div>+typedef struct {</div><div>+ /* the round robin data must be first */</div><div>+ ngx_http_upstream_rr_peer_data_t rrp;</div><div>+</div><div>+ ngx_uint_t found;</div>
<div>+</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf;</div><div>+</div><div>+ ngx_event_get_peer_pt get_rr_peer;</div><div>+} ngx_http_upstream_ch_peer_data_t;</div><div>+</div><div>+</div><div>
+static void *ngx_http_upstream_cons_hash_create_conf(ngx_conf_t *cf);</div><div>+static char *ngx_http_upstream_cons_hash(ngx_conf_t *cf, ngx_command_t *cmd,</div><div>+ void *conf);</div><div>+static ngx_int_t ngx_http_upstream_init_cons_hash(ngx_conf_t *cf,</div>
<div>+ ngx_http_upstream_srv_conf_t *us);</div><div>+</div><div>+static ngx_int_t ngx_http_upstream_init_cons_hash_peer(ngx_http_request_t *r,</div><div>+ ngx_http_upstream_srv_conf_t *us);</div><div>+static ngx_int_t ngx_http_upstream_get_cons_hash_peer(</div>
<div>+ ngx_peer_connection_t *pc, void *data);</div><div>+</div><div>+static ngx_uint_t ngx_http_upstream_find_cons_hash_peer(</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf, uint32_t hash);</div><div>+static int ngx_http_upstream_cons_hash_cmp_dist(const void *one,</div>
<div>+ const void *two);</div><div>+static int ngx_http_upstream_cons_hash_cmp_node(const void *one,</div><div>+ const void *two);</div><div>+static ngx_int_t ngx_http_upstream_cons_hash_random(</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf, ngx_str_t value, ngx_uint_t id,</div>
<div>+ uint32_t *ret);</div><div>+static ngx_int_t ngx_http_upstream_cons_hash_init_nearest(</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf);</div><div>+</div><div>+inline static ngx_int_t ngx_http_upstream_get_cons_hash_try_peer(</div>
<div>+ ngx_peer_connection_t *pc, void *data, ngx_uint_t index);</div><div>+</div><div>+</div><div>+static ngx_command_t ngx_http_upstream_cons_hash_commands[] = {</div><div>+</div><div>+ { ngx_string("cons_hash"),</div>
<div>+ NGX_HTTP_UPS_CONF | NGX_CONF_TAKE1,</div><div>+ ngx_http_upstream_cons_hash,</div><div>+ 0,</div><div>+ 0,</div><div>+ NULL },</div><div>+</div><div>+ ngx_null_command</div><div>+};</div>
<div>+</div><div>+</div><div>+static ngx_http_module_t ngx_http_upstream_cons_hash_module_ctx = {</div><div>+ NULL, /* preconfiguration */</div><div>+ NULL, /* postconfiguration */</div>
<div>+</div><div>+ NULL, /* create main configuration */</div><div>+ NULL, /* init main configuration */</div><div>+</div><div>+ ngx_http_upstream_cons_hash_create_conf, /* create server configuration*/</div>
<div>+ NULL, /* merge server configuration */</div><div>+</div><div>+ NULL, /* create location configuration */</div><div>+ NULL /* merge location configuration */</div>
<div>+};</div><div>+</div><div>+</div><div>+ngx_module_t ngx_http_upstream_cons_hash_module = {</div><div>+ NGX_MODULE_V1,</div><div>+ &ngx_http_upstream_cons_hash_module_ctx, /* module context */</div><div>+ ngx_http_upstream_cons_hash_commands, /* module directives */</div>
<div>+ NGX_HTTP_MODULE, /* module type */</div><div>+ NULL, /* init master */</div><div>+ NULL, /* init module */</div><div>+ NULL, /* init process */</div>
<div>+ NULL, /* init thread */</div><div>+ NULL, /* exit thread */</div><div>+ NULL, /* exit process */</div><div>+ NULL, /* exit master */</div>
<div>+ NGX_MODULE_V1_PADDING</div><div>+};</div><div>+</div><div>+</div><div>+static void *</div><div>+ngx_http_upstream_cons_hash_create_conf(ngx_conf_t *cf)</div><div>+{</div><div>+ ngx_http_upstream_cons_hash_conf_t *conf;</div>
<div>+</div><div>+ conf = ngx_pcalloc(cf->pool, sizeof(ngx_http_upstream_cons_hash_conf_t));</div><div>+ if (conf == NULL) {</div><div>+ return NULL;</div><div>+ }</div><div>+</div><div>+ return conf;</div>
<div>+}</div><div>+</div><div>+</div><div>+static ngx_int_t</div><div>+ngx_http_upstream_init_cons_hash(ngx_conf_t *cf,</div><div>+ ngx_http_upstream_srv_conf_t *us)</div><div>+{</div><div>+ uint32_t hash;</div>
<div>+ ngx_int_t rc;</div><div>+ ngx_str_t name;</div><div>+ ngx_uint_t i, j, k, n, nn, m;</div><div>+ ngx_http_upstream_rr_peers_t *peers;</div>
<div>+ ngx_http_upstream_cons_hash_conf_t *chcf;</div><div>+</div><div>+ if (ngx_http_upstream_init_round_robin(cf, us) == NGX_ERROR) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ peers = us->peer.data;</div>
<div>+</div><div>+ n = peers->number;</div><div>+ nn = 0;</div><div>+</div><div>+ for (i = 0; i < n; ++i) {</div><div>+ nn += peers->peer[i].weight;</div><div>+ }</div><div>+</div><div>+ nn *= (NGX_HTTP_UPSTREAM_CH_VNODE_NUM + 1);</div>
<div>+</div><div>+ chcf = ngx_http_conf_upstream_srv_conf(us,</div><div>+ ngx_http_upstream_cons_hash_module);</div><div>+</div><div>+ /*</div><div>+ * to guarantee nn % n == 0, there's no side effect,</div>
<div>+ * but much more convenient to construct the 'nearest'</div><div>+ */</div><div>+</div><div>+ nn = (nn + n - 1) / n * n;</div><div>+ chcf->node_number = nn;</div><div>+</div><div>+ chcf->log = cf->log;</div>
<div>+ chcf->pool = cf->pool;</div><div>+ chcf->peers = peers;</div><div>+</div><div>+ chcf->nodes = ngx_pcalloc(cf->pool, nn *</div><div>+ sizeof(ngx_http_upstream_cons_hash_node_t));</div>
<div>+ if (chcf->nodes == NULL) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ for (i = 0, k = 0; i < n; ++i) {</div><div>+</div><div>+ name = peers->peer[i].name;</div>
<div>+ m = peers->peer[i].weight * (1 + NGX_HTTP_UPSTREAM_CH_VNODE_NUM);</div><div>+</div><div>+ for (j = 0; j < m; ++j, ++k) {</div><div>+</div><div>+ chcf->nodes[k].index = i;</div><div>
+</div><div>+ rc = ngx_http_upstream_cons_hash_random(chcf, name, j, &hash);</div><div>+ if (rc == NGX_ERROR) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div>
<div>+ chcf->nodes[k].hash = hash;</div><div>+ }</div><div>+ }</div><div>+</div><div>+ for (i = 0; i < nn - k; ++i) {</div><div>+ chcf->nodes[k + i].index = chcf->nodes[0].index;</div>
<div>+ chcf->nodes[k + i].hash = chcf->nodes[0].hash;</div><div>+ }</div><div>+</div><div>+ ngx_qsort(chcf->nodes, nn, sizeof(ngx_http_upstream_cons_hash_node_t),</div><div>+ ngx_http_upstream_cons_hash_cmp_node);</div>
<div>+</div><div>+ rc = ngx_http_upstream_cons_hash_init_nearest(chcf);</div><div>+ if (rc == NGX_ERROR) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ us->peer.init = ngx_http_upstream_init_cons_hash_peer;</div>
<div>+</div><div>+ return NGX_OK;</div><div>+}</div><div>+</div><div>+</div><div>+static ngx_int_t</div><div>+ngx_http_upstream_init_cons_hash_peer(ngx_http_request_t *r,</div><div>+ ngx_http_upstream_srv_conf_t *us)</div>
<div>+{</div><div>+ uint32_t hash;</div><div>+ ngx_str_t raw_value;</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf;</div><div>+ ngx_http_upstream_ch_peer_data_t *chp;</div>
<div>+</div><div>+ chcf = ngx_http_conf_upstream_srv_conf(us,</div><div>+ ngx_http_upstream_cons_hash_module);</div><div>+ if (chcf == NULL) {</div><div>+ return NGX_ERROR;</div>
<div>+ }</div><div>+</div><div>+ chp = ngx_pcalloc(r->pool, sizeof(ngx_http_upstream_ch_peer_data_t));</div><div>+ if (chp == NULL) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>
+ r->upstream->peer.data = &chp->rrp;</div><div>+</div><div>+ if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>
+ if (!chp->rrp.peers->single) {</div><div>+</div><div>+ /* raw_value.data is allocated in ngx_http_script_run from r->pool */</div><div>+</div><div>+ if (ngx_http_script_run(r, &raw_value,</div>
<div>+ chcf->lengths->elts, 0, chcf->values->elts) == NULL) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ hash = ngx_murmur_hash2(raw_value.data, raw_value.len);</div>
<div>+</div><div>+ ngx_pfree(r->pool, raw_value.data);</div><div>+</div><div>+ chp->found = ngx_http_upstream_find_cons_hash_peer(chcf, hash);</div><div>+ }</div><div>+</div><div>+ r->upstream->peer.get = ngx_http_upstream_get_cons_hash_peer;</div>
<div>+</div><div>+ chp->chcf = chcf;</div><div>+ chp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;</div><div>+</div><div>+ return NGX_OK;</div><div>+}</div><div>+</div><div>+</div><div>+inline static ngx_int_t</div>
<div>+ngx_http_upstream_get_cons_hash_try_peer(ngx_peer_connection_t *pc, void *data,</div><div>+ ngx_uint_t index)</div><div>+{</div><div>+ ngx_http_upstream_ch_peer_data_t *chp = data;</div><div>+</div><div>+ time_t now;</div>
<div>+ ngx_int_t rc;</div><div>+ ngx_uint_t n, m;</div><div>+ ngx_http_upstream_rr_peer_t *peer;</div><div>+</div><div>+ n = index / (8 * sizeof(uintptr_t));</div><div>+ m = (uintptr_t) 1 << index % (8 * sizeof(uintptr_t));</div>
<div>+</div><div>+ if (chp->rrp.tried[n] & m) {</div><div>+ return NGX_AGAIN;</div><div>+ }</div><div>+</div><div>+ rc = NGX_AGAIN;</div><div>+</div><div>+ now = ngx_time();</div><div>+</div><div>
+ peer = &chp->chcf->peers->peer[index];</div><div>+</div><div>+ /* ngx_lock_mutex(chp->rrp.peers->mutex); */</div><div>+</div><div>+ if (!peer->down) {</div><div>+ if (peer->max_fails == 0 || peer->fails < peer->max_fails) {</div>
<div>+ rc = NGX_OK;</div><div>+ }</div><div>+</div><div>+ if (now - peer->checked > peer->fail_timeout) {</div><div>+ peer->checked = now;</div><div>+ rc = NGX_OK;</div>
<div>+ }</div><div>+ }</div><div>+</div><div>+ if (rc == NGX_OK) {</div><div>+ chp->rrp.current = index;</div><div>+</div><div>+ pc->sockaddr = peer->sockaddr;</div><div>+ pc->socklen = peer->socklen;</div>
<div>+ pc->name = &peer->name;</div><div>+ }</div><div>+</div><div>+ /* ngx_unlock_mutex(chp->rrp.peers->mutex); */</div><div>+</div><div>+ chp->rrp.tried[n] |= m;</div><div>+</div><div>
+ return rc;</div><div>+}</div><div>+</div><div>+</div><div>+static ngx_int_t</div><div>+ngx_http_upstream_get_cons_hash_peer(ngx_peer_connection_t *pc, void *data)</div><div>+{</div><div>+ ngx_http_upstream_ch_peer_data_t *chp = data;</div>
<div>+</div><div>+ ngx_int_t rc;</div><div>+ ngx_uint_t i, j, n, nn;</div><div>+ ngx_uint_t *nearest;</div><div>+ ngx_http_upstream_rr_peers_t *peers;</div>
<div>+ ngx_http_upstream_cons_hash_node_t *nodes;</div><div>+</div><div>+ if (chp->rrp.peers->single) {</div><div>+ return chp->get_rr_peer(pc, &chp->rrp);</div><div>+ }</div><div>+</div><div>
+ pc->cached = 0;</div><div>+ pc->connection = NULL;</div><div>+</div><div>+ peers = chp->chcf->peers;</div><div>+ nodes = chp->chcf->nodes;</div><div>+ nearest = chp->chcf->nearest;</div>
<div>+</div><div>+ n = peers->number;</div><div>+ nn = chp->chcf->node_number;</div><div>+</div><div>+ for (i = chp->found; i % n != 0; i = (i + 1) % nn) {</div><div>+</div><div>+ rc = ngx_http_upstream_get_cons_hash_try_peer(pc, data,</div>
<div>+ nodes[i].index);</div><div>+ if (rc == NGX_OK) {</div><div>+ return NGX_OK;</div><div>+ }</div><div>+ }</div><div>+</div><div>+ for (j = (i + n) % nn; i != j; i = (i + 1) % nn) {</div>
<div>+</div><div>+ rc = ngx_http_upstream_get_cons_hash_try_peer(pc, data,</div><div>+ nearest[i]);</div><div>+ if (rc == NGX_OK) {</div><div>+ return NGX_OK;</div>
<div>+ }</div><div>+ }</div><div>+</div><div>+ /* all peers failed, mark them as live for quick recovery */</div><div>+</div><div>+ for (i = 0; i < peers->number; i++) {</div><div>+ peers->peer[i].fails = 0;</div>
<div>+ }</div><div>+</div><div>+ pc->name = peers->name;</div><div>+</div><div>+ return NGX_BUSY;</div><div>+}</div><div>+</div><div>+</div><div>+static ngx_uint_t</div><div>+ngx_http_upstream_find_cons_hash_peer(ngx_http_upstream_cons_hash_conf_t *chcf,</div>
<div>+ uint32_t hash)</div><div>+{</div><div>+ uint32_t mid_hash;</div><div>+ ngx_int_t l, r, mid;</div><div>+</div><div>+ l = 0;</div><div>+ r = chcf->node_number - 1;</div><div>+</div><div>+ while (l <= r) {</div>
<div>+ mid = (l + r) >> 1;</div><div>+ mid_hash = chcf->nodes[mid].hash;</div><div>+</div><div>+ if (mid_hash < hash) {</div><div>+ l = mid + 1;</div><div>+ } else {</div>
<div>+ r = mid - 1;</div><div>+ }</div><div>+ }</div><div>+</div><div>+ if (l == (ngx_int_t)chcf->node_number) {</div><div>+ l = 0;</div><div>+ }</div><div>+</div><div>+ return l;</div>
<div>+}</div><div>+</div><div>+</div><div>+static char *</div><div>+ngx_http_upstream_cons_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)</div><div>+{</div><div>+ ngx_str_t *value;</div>
<div>+ ngx_http_script_compile_t sc;</div><div>+ ngx_http_upstream_srv_conf_t *uscf;</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf;</div><div>+</div><div>+ uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);</div>
<div>+</div><div>+ chcf = ngx_http_conf_upstream_srv_conf(uscf,</div><div>+ ngx_http_upstream_cons_hash_module);</div><div>+ if (uscf->peer.init_upstream) {</div><div>+ ngx_conf_log_error(NGX_LOG_WARN, cf, 0,</div>
<div>+ "load balancing method redefined");</div><div>+ }</div><div>+ uscf->peer.init_upstream = ngx_http_upstream_init_cons_hash;</div><div>+</div><div>+ value = cf->args->elts;</div>
<div>+ ngx_memzero(&sc, sizeof(ngx_http_script_compile_t));</div><div>+</div><div>+ <a href="http://sc.cf">sc.cf</a> = cf;</div><div>+ sc.source = &value[1];</div><div>+ sc.lengths = &chcf->lengths;;</div>
<div>+ sc.values = &chcf->values;</div><div>+ sc.complete_lengths = 1;</div><div>+ sc.complete_values = 1;</div><div>+</div><div>+ if (ngx_http_script_compile(&sc) != NGX_OK) {</div><div>+ return NGX_CONF_ERROR;</div>
<div>+ }</div><div>+</div><div>+ uscf->flags = NGX_HTTP_UPSTREAM_CREATE</div><div>+ |NGX_HTTP_UPSTREAM_WEIGHT</div><div>+ |NGX_HTTP_UPSTREAM_MAX_FAILS</div><div>+ |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT</div>
<div>+ |NGX_HTTP_UPSTREAM_DOWN;</div><div>+</div><div>+ return NGX_CONF_OK;</div><div>+}</div><div>+</div><div>+</div><div>+static ngx_int_t</div><div>+ngx_http_upstream_cons_hash_random(ngx_http_upstream_cons_hash_conf_t *chcf,</div>
<div>+ ngx_str_t value, ngx_uint_t id, uint32_t *ret)</div><div>+{</div><div>+ /* repeatable random with same (val, id) */</div><div>+</div><div>+ u_char *buf, *pos;</div><div>+ ngx_uint_t total;</div><div>
+</div><div>+ total = NGX_INT_T_LEN + value.len;</div><div>+</div><div>+ buf = ngx_calloc(total, chcf->log);</div><div>+ if (buf == NULL) {</div><div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div>
<div>+ pos = ngx_snprintf(buf, total, "%i-%*s", id, value.len, value.data);</div><div>+</div><div>+ *ret = ngx_murmur_hash2(buf, pos - buf);</div><div>+</div><div>+ ngx_free(buf);</div><div>+</div><div>
+ return NGX_OK;</div><div>+}</div><div>+</div><div>+</div><div>+static ngx_int_t</div><div>+ngx_http_upstream_cons_hash_init_nearest(</div><div>+ ngx_http_upstream_cons_hash_conf_t *chcf)</div><div>+{</div><div>+ ngx_int_t k;</div>
<div>+ ngx_uint_t i, j, n, nn;</div><div>+ ngx_uint_t *nearest, *temp;</div><div>+ ngx_http_upstream_cons_hash_node_t *nodes;</div><div>+</div><div>+ n = chcf->peers->number;</div>
<div>+ nn = chcf->node_number;</div><div>+</div><div>+ nodes = chcf->nodes;</div><div>+</div><div>+ nearest = ngx_pcalloc(chcf->pool, nn * sizeof(ngx_uint_t));</div><div>+ if (nearest == NULL) {</div>
<div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ chcf->nearest = nearest;</div><div>+</div><div>+ temp = ngx_pcalloc(chcf->pool, n * sizeof(ngx_uint_t));</div><div>+ if (temp == NULL) {</div>
<div>+ return NGX_ERROR;</div><div>+ }</div><div>+</div><div>+ for (i = 0; i < nn; ++i) {</div><div>+ nearest[i] = nn;</div><div>+ }</div><div>+</div><div>+ for (i = 0; i < nn; i += n) {</div>
<div>+ for (j = 0; j < n; ++j) {</div><div>+ temp[j] = nn;</div><div>+ }</div><div>+ for (k = n - 1; k >= 0; --k) {</div><div>+ temp[nodes[i + k].index] = i + k;</div><div>
+ }</div><div>+ for (j = 0; j < n; ++j) {</div><div>+ nearest[i + j] = temp[j];</div><div>+ }</div><div>+ }</div><div>+</div><div>+ ngx_pfree(chcf->pool, temp);</div><div>+</div>
<div>+ /* update the 'nearest' twice */</div><div>+</div><div>+ for (i = 0; i < 2; ++i) {</div><div>+ for (k = nn - n; k >= 0; k -= n) {</div><div>+ for (j = 0; j < n; ++j) {</div>
<div>+ if (nearest[k + j] == nn) {</div><div>+ nearest[k + j] = nearest[(k + j + n) % nn];</div><div>+ }</div><div>+ }</div><div>+ }</div><div>+ }</div>
<div>+</div><div>+ for (i = 0; i < nn; i += n) {</div><div>+</div><div>+ /* there is no elt equals to nn in the 'nearest' now */</div><div>+</div><div>+ for (j = 0; j < n; ++j) {</div><div>+ if (nearest[i + j] < i) {</div>
<div>+ nearest[i + j] += nn;</div><div>+ }</div><div>+ }</div><div>+</div><div>+ ngx_qsort(nearest + i, n, sizeof(ngx_uint_t),</div><div>+ ngx_http_upstream_cons_hash_cmp_dist);</div>
<div>+</div><div>+ for (j = 0; j < n; ++j) {</div><div>+ if (nearest[i + j] >= nn) {</div><div>+ nearest[i + j] -= nn;</div><div>+ }</div><div>+ }</div><div>+ }</div>
<div>+</div><div>+ for (i = 0; i < nn; ++i) {</div><div>+ nearest[i] = nodes[nearest[i]].index;</div><div>+ }</div><div>+</div><div>+ return NGX_OK;</div><div>+}</div><div>+</div><div>+</div><div>+static int</div>
<div>+ngx_http_upstream_cons_hash_cmp_dist(const void *one, const void *two)</div><div>+{</div><div>+ ngx_uint_t first, second;</div><div>+</div><div>+ first = *(ngx_uint_t *)one;</div><div>+ second = *(ngx_uint_t *)two;</div>
<div>+</div><div>+ if (first < second) {</div><div>+ return -1;</div><div>+ }</div><div>+</div><div>+ if (first > second) {</div><div>+ return 1;</div><div>+ }</div><div>+</div><div>+ return 0;</div>
<div>+}</div><div>+</div><div>+</div><div>+static int</div><div>+ngx_http_upstream_cons_hash_cmp_node(const void *one, const void *two)</div><div>+{</div><div>+ ngx_http_upstream_cons_hash_node_t *first, *second;</div>
<div>+</div><div>+ first = (ngx_http_upstream_cons_hash_node_t *) one;</div><div>+ second = (ngx_http_upstream_cons_hash_node_t *) two;</div><div>+</div><div>+ if (first->hash < second->hash) {</div><div>
+ return -1;</div><div>+ }</div><div>+</div><div>+ if (first->hash > second->hash) {</div><div>+ return 1;</div><div>+ }</div><div>+</div><div>+ return 0;</div><div>+}</div></div></div>