Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.13.12 ]​[ nginx-1.12.2 ]​

0001 
0002 /*
0003  * Copyright (C) Roman Arutyunyan
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 #include <ngx_stream.h>
0011 
0012 
0013 typedef struct {
0014     uint32_t                              hash;
0015     ngx_str_t                            *server;
0016 } ngx_stream_upstream_chash_point_t;
0017 
0018 
0019 typedef struct {
0020     ngx_uint_t                            number;
0021     ngx_stream_upstream_chash_point_t     point[1];
0022 } ngx_stream_upstream_chash_points_t;
0023 
0024 
0025 typedef struct {
0026     ngx_stream_complex_value_t            key;
0027     ngx_stream_upstream_chash_points_t   *points;
0028 } ngx_stream_upstream_hash_srv_conf_t;
0029 
0030 
0031 typedef struct {
0032     /* the round robin data must be first */
0033     ngx_stream_upstream_rr_peer_data_t    rrp;
0034     ngx_stream_upstream_hash_srv_conf_t  *conf;
0035     ngx_str_t                             key;
0036     ngx_uint_t                            tries;
0037     ngx_uint_t                            rehash;
0038     uint32_t                              hash;
0039     ngx_event_get_peer_pt                 get_rr_peer;
0040 } ngx_stream_upstream_hash_peer_data_t;
0041 
0042 
0043 static ngx_int_t ngx_stream_upstream_init_hash(ngx_conf_t *cf,
0044     ngx_stream_upstream_srv_conf_t *us);
0045 static ngx_int_t ngx_stream_upstream_init_hash_peer(ngx_stream_session_t *s,
0046     ngx_stream_upstream_srv_conf_t *us);
0047 static ngx_int_t ngx_stream_upstream_get_hash_peer(ngx_peer_connection_t *pc,
0048     void *data);
0049 
0050 static ngx_int_t ngx_stream_upstream_init_chash(ngx_conf_t *cf,
0051     ngx_stream_upstream_srv_conf_t *us);
0052 static int ngx_libc_cdecl
0053     ngx_stream_upstream_chash_cmp_points(const void *one, const void *two);
0054 static ngx_uint_t ngx_stream_upstream_find_chash_point(
0055     ngx_stream_upstream_chash_points_t *points, uint32_t hash);
0056 static ngx_int_t ngx_stream_upstream_init_chash_peer(ngx_stream_session_t *s,
0057     ngx_stream_upstream_srv_conf_t *us);
0058 static ngx_int_t ngx_stream_upstream_get_chash_peer(ngx_peer_connection_t *pc,
0059     void *data);
0060 
0061 static void *ngx_stream_upstream_hash_create_conf(ngx_conf_t *cf);
0062 static char *ngx_stream_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd,
0063     void *conf);
0064 
0065 
0066 static ngx_command_t  ngx_stream_upstream_hash_commands[] = {
0067 
0068     { ngx_string("hash"),
0069       NGX_STREAM_UPS_CONF|NGX_CONF_TAKE12,
0070       ngx_stream_upstream_hash,
0071       NGX_STREAM_SRV_CONF_OFFSET,
0072       0,
0073       NULL },
0074 
0075       ngx_null_command
0076 };
0077 
0078 
0079 static ngx_stream_module_t  ngx_stream_upstream_hash_module_ctx = {
0080     NULL,                                  /* preconfiguration */
0081     NULL,                                  /* postconfiguration */
0082 
0083     NULL,                                  /* create main configuration */
0084     NULL,                                  /* init main configuration */
0085 
0086     ngx_stream_upstream_hash_create_conf,  /* create server configuration */
0087     NULL                                   /* merge server configuration */
0088 };
0089 
0090 
0091 ngx_module_t  ngx_stream_upstream_hash_module = {
0092     NGX_MODULE_V1,
0093     &ngx_stream_upstream_hash_module_ctx,  /* module context */
0094     ngx_stream_upstream_hash_commands,     /* module directives */
0095     NGX_STREAM_MODULE,                     /* module type */
0096     NULL,                                  /* init master */
0097     NULL,                                  /* init module */
0098     NULL,                                  /* init process */
0099     NULL,                                  /* init thread */
0100     NULL,                                  /* exit thread */
0101     NULL,                                  /* exit process */
0102     NULL,                                  /* exit master */
0103     NGX_MODULE_V1_PADDING
0104 };
0105 
0106 
0107 static ngx_int_t
0108 ngx_stream_upstream_init_hash(ngx_conf_t *cf,
0109     ngx_stream_upstream_srv_conf_t *us)
0110 {
0111     if (ngx_stream_upstream_init_round_robin(cf, us) != NGX_OK) {
0112         return NGX_ERROR;
0113     }
0114 
0115     us->peer.init = ngx_stream_upstream_init_hash_peer;
0116 
0117     return NGX_OK;
0118 }
0119 
0120 
0121 static ngx_int_t
0122 ngx_stream_upstream_init_hash_peer(ngx_stream_session_t *s,
0123     ngx_stream_upstream_srv_conf_t *us)
0124 {
0125     ngx_stream_upstream_hash_srv_conf_t   *hcf;
0126     ngx_stream_upstream_hash_peer_data_t  *hp;
0127 
0128     hp = ngx_palloc(s->connection->pool,
0129                     sizeof(ngx_stream_upstream_hash_peer_data_t));
0130     if (hp == NULL) {
0131         return NGX_ERROR;
0132     }
0133 
0134     s->upstream->peer.data = &hp->rrp;
0135 
0136     if (ngx_stream_upstream_init_round_robin_peer(s, us) != NGX_OK) {
0137         return NGX_ERROR;
0138     }
0139 
0140     s->upstream->peer.get = ngx_stream_upstream_get_hash_peer;
0141 
0142     hcf = ngx_stream_conf_upstream_srv_conf(us,
0143                                             ngx_stream_upstream_hash_module);
0144 
0145     if (ngx_stream_complex_value(s, &hcf->key, &hp->key) != NGX_OK) {
0146         return NGX_ERROR;
0147     }
0148 
0149     ngx_log_debug1(NGX_LOG_DEBUG_STREAM, s->connection->log, 0,
0150                    "upstream hash key:\"%V\"", &hp->key);
0151 
0152     hp->conf = hcf;
0153     hp->tries = 0;
0154     hp->rehash = 0;
0155     hp->hash = 0;
0156     hp->get_rr_peer = ngx_stream_upstream_get_round_robin_peer;
0157 
0158     return NGX_OK;
0159 }
0160 
0161 
0162 static ngx_int_t
0163 ngx_stream_upstream_get_hash_peer(ngx_peer_connection_t *pc, void *data)
0164 {
0165     ngx_stream_upstream_hash_peer_data_t *hp = data;
0166 
0167     time_t                          now;
0168     u_char                          buf[NGX_INT_T_LEN];
0169     size_t                          size;
0170     uint32_t                        hash;
0171     ngx_int_t                       w;
0172     uintptr_t                       m;
0173     ngx_uint_t                      n, p;
0174     ngx_stream_upstream_rr_peer_t  *peer;
0175 
0176     ngx_log_debug1(NGX_LOG_DEBUG_STREAM, pc->log, 0,
0177                    "get hash peer, try: %ui", pc->tries);
0178 
0179     ngx_stream_upstream_rr_peers_wlock(hp->rrp.peers);
0180 
0181     if (hp->tries > 20 || hp->rrp.peers->single) {
0182         ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0183         return hp->get_rr_peer(pc, &hp->rrp);
0184     }
0185 
0186     now = ngx_time();
0187 
0188     pc->connection = NULL;
0189 
0190     for ( ;; ) {
0191 
0192         /*
0193          * Hash expression is compatible with Cache::Memcached:
0194          * ((crc32([REHASH] KEY) >> 16) & 0x7fff) + PREV_HASH
0195          * with REHASH omitted at the first iteration.
0196          */
0197 
0198         ngx_crc32_init(hash);
0199 
0200         if (hp->rehash > 0) {
0201             size = ngx_sprintf(buf, "%ui", hp->rehash) - buf;
0202             ngx_crc32_update(&hash, buf, size);
0203         }
0204 
0205         ngx_crc32_update(&hash, hp->key.data, hp->key.len);
0206         ngx_crc32_final(hash);
0207 
0208         hash = (hash >> 16) & 0x7fff;
0209 
0210         hp->hash += hash;
0211         hp->rehash++;
0212 
0213         w = hp->hash % hp->rrp.peers->total_weight;
0214         peer = hp->rrp.peers->peer;
0215         p = 0;
0216 
0217         while (w >= peer->weight) {
0218             w -= peer->weight;
0219             peer = peer->next;
0220             p++;
0221         }
0222 
0223         n = p / (8 * sizeof(uintptr_t));
0224         m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
0225 
0226         if (hp->rrp.tried[n] & m) {
0227             goto next;
0228         }
0229 
0230         ngx_log_debug2(NGX_LOG_DEBUG_STREAM, pc->log, 0,
0231                        "get hash peer, value:%uD, peer:%ui", hp->hash, p);
0232 
0233         if (peer->down) {
0234             goto next;
0235         }
0236 
0237         if (peer->max_fails
0238             && peer->fails >= peer->max_fails
0239             && now - peer->checked <= peer->fail_timeout)
0240         {
0241             goto next;
0242         }
0243 
0244         if (peer->max_conns && peer->conns >= peer->max_conns) {
0245             goto next;
0246         }
0247 
0248         break;
0249 
0250     next:
0251 
0252         if (++hp->tries > 20) {
0253             ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0254             return hp->get_rr_peer(pc, &hp->rrp);
0255         }
0256     }
0257 
0258     hp->rrp.current = peer;
0259 
0260     pc->sockaddr = peer->sockaddr;
0261     pc->socklen = peer->socklen;
0262     pc->name = &peer->name;
0263 
0264     peer->conns++;
0265 
0266     if (now - peer->checked > peer->fail_timeout) {
0267         peer->checked = now;
0268     }
0269 
0270     ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0271 
0272     hp->rrp.tried[n] |= m;
0273 
0274     return NGX_OK;
0275 }
0276 
0277 
0278 static ngx_int_t
0279 ngx_stream_upstream_init_chash(ngx_conf_t *cf,
0280     ngx_stream_upstream_srv_conf_t *us)
0281 {
0282     u_char                               *host, *port, c;
0283     size_t                                host_len, port_len, size;
0284     uint32_t                              hash, base_hash;
0285     ngx_str_t                            *server;
0286     ngx_uint_t                            npoints, i, j;
0287     ngx_stream_upstream_rr_peer_t        *peer;
0288     ngx_stream_upstream_rr_peers_t       *peers;
0289     ngx_stream_upstream_chash_points_t   *points;
0290     ngx_stream_upstream_hash_srv_conf_t  *hcf;
0291     union {
0292         uint32_t                          value;
0293         u_char                            byte[4];
0294     } prev_hash;
0295 
0296     if (ngx_stream_upstream_init_round_robin(cf, us) != NGX_OK) {
0297         return NGX_ERROR;
0298     }
0299 
0300     us->peer.init = ngx_stream_upstream_init_chash_peer;
0301 
0302     peers = us->peer.data;
0303     npoints = peers->total_weight * 160;
0304 
0305     size = sizeof(ngx_stream_upstream_chash_points_t)
0306            + sizeof(ngx_stream_upstream_chash_point_t) * (npoints - 1);
0307 
0308     points = ngx_palloc(cf->pool, size);
0309     if (points == NULL) {
0310         return NGX_ERROR;
0311     }
0312 
0313     points->number = 0;
0314 
0315     for (peer = peers->peer; peer; peer = peer->next) {
0316         server = &peer->server;
0317 
0318         /*
0319          * Hash expression is compatible with Cache::Memcached::Fast:
0320          * crc32(HOST \0 PORT PREV_HASH).
0321          */
0322 
0323         if (server->len >= 5
0324             && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
0325         {
0326             host = server->data + 5;
0327             host_len = server->len - 5;
0328             port = NULL;
0329             port_len = 0;
0330             goto done;
0331         }
0332 
0333         for (j = 0; j < server->len; j++) {
0334             c = server->data[server->len - j - 1];
0335 
0336             if (c == ':') {
0337                 host = server->data;
0338                 host_len = server->len - j - 1;
0339                 port = server->data + server->len - j;
0340                 port_len = j;
0341                 goto done;
0342             }
0343 
0344             if (c < '0' || c > '9') {
0345                 break;
0346             }
0347         }
0348 
0349         host = server->data;
0350         host_len = server->len;
0351         port = NULL;
0352         port_len = 0;
0353 
0354     done:
0355 
0356         ngx_crc32_init(base_hash);
0357         ngx_crc32_update(&base_hash, host, host_len);
0358         ngx_crc32_update(&base_hash, (u_char *) "", 1);
0359         ngx_crc32_update(&base_hash, port, port_len);
0360 
0361         prev_hash.value = 0;
0362         npoints = peer->weight * 160;
0363 
0364         for (j = 0; j < npoints; j++) {
0365             hash = base_hash;
0366 
0367             ngx_crc32_update(&hash, prev_hash.byte, 4);
0368             ngx_crc32_final(hash);
0369 
0370             points->point[points->number].hash = hash;
0371             points->point[points->number].server = server;
0372             points->number++;
0373 
0374 #if (NGX_HAVE_LITTLE_ENDIAN)
0375             prev_hash.value = hash;
0376 #else
0377             prev_hash.byte[0] = (u_char) (hash & 0xff);
0378             prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);
0379             prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);
0380             prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);
0381 #endif
0382         }
0383     }
0384 
0385     ngx_qsort(points->point,
0386               points->number,
0387               sizeof(ngx_stream_upstream_chash_point_t),
0388               ngx_stream_upstream_chash_cmp_points);
0389 
0390     for (i = 0, j = 1; j < points->number; j++) {
0391         if (points->point[i].hash != points->point[j].hash) {
0392             points->point[++i] = points->point[j];
0393         }
0394     }
0395 
0396     points->number = i + 1;
0397 
0398     hcf = ngx_stream_conf_upstream_srv_conf(us,
0399                                             ngx_stream_upstream_hash_module);
0400     hcf->points = points;
0401 
0402     return NGX_OK;
0403 }
0404 
0405 
0406 static int ngx_libc_cdecl
0407 ngx_stream_upstream_chash_cmp_points(const void *one, const void *two)
0408 {
0409     ngx_stream_upstream_chash_point_t *first =
0410                                      (ngx_stream_upstream_chash_point_t *) one;
0411     ngx_stream_upstream_chash_point_t *second =
0412                                      (ngx_stream_upstream_chash_point_t *) two;
0413 
0414     if (first->hash < second->hash) {
0415         return -1;
0416 
0417     } else if (first->hash > second->hash) {
0418         return 1;
0419 
0420     } else {
0421         return 0;
0422     }
0423 }
0424 
0425 
0426 static ngx_uint_t
0427 ngx_stream_upstream_find_chash_point(ngx_stream_upstream_chash_points_t *points,
0428     uint32_t hash)
0429 {
0430     ngx_uint_t                          i, j, k;
0431     ngx_stream_upstream_chash_point_t  *point;
0432 
0433     /* find first point >= hash */
0434 
0435     point = &points->point[0];
0436 
0437     i = 0;
0438     j = points->number;
0439 
0440     while (i < j) {
0441         k = (i + j) / 2;
0442 
0443         if (hash > point[k].hash) {
0444             i = k + 1;
0445 
0446         } else if (hash < point[k].hash) {
0447             j = k;
0448 
0449         } else {
0450             return k;
0451         }
0452     }
0453 
0454     return i;
0455 }
0456 
0457 
0458 static ngx_int_t
0459 ngx_stream_upstream_init_chash_peer(ngx_stream_session_t *s,
0460     ngx_stream_upstream_srv_conf_t *us)
0461 {
0462     uint32_t                               hash;
0463     ngx_stream_upstream_hash_srv_conf_t   *hcf;
0464     ngx_stream_upstream_hash_peer_data_t  *hp;
0465 
0466     if (ngx_stream_upstream_init_hash_peer(s, us) != NGX_OK) {
0467         return NGX_ERROR;
0468     }
0469 
0470     s->upstream->peer.get = ngx_stream_upstream_get_chash_peer;
0471 
0472     hp = s->upstream->peer.data;
0473     hcf = ngx_stream_conf_upstream_srv_conf(us,
0474                                             ngx_stream_upstream_hash_module);
0475 
0476     hash = ngx_crc32_long(hp->key.data, hp->key.len);
0477 
0478     ngx_stream_upstream_rr_peers_rlock(hp->rrp.peers);
0479 
0480     hp->hash = ngx_stream_upstream_find_chash_point(hcf->points, hash);
0481 
0482     ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0483 
0484     return NGX_OK;
0485 }
0486 
0487 
0488 static ngx_int_t
0489 ngx_stream_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
0490 {
0491     ngx_stream_upstream_hash_peer_data_t *hp = data;
0492 
0493     time_t                                now;
0494     intptr_t                              m;
0495     ngx_str_t                            *server;
0496     ngx_int_t                             total;
0497     ngx_uint_t                            i, n, best_i;
0498     ngx_stream_upstream_rr_peer_t        *peer, *best;
0499     ngx_stream_upstream_chash_point_t    *point;
0500     ngx_stream_upstream_chash_points_t   *points;
0501     ngx_stream_upstream_hash_srv_conf_t  *hcf;
0502 
0503     ngx_log_debug1(NGX_LOG_DEBUG_STREAM, pc->log, 0,
0504                    "get consistent hash peer, try: %ui", pc->tries);
0505 
0506     ngx_stream_upstream_rr_peers_wlock(hp->rrp.peers);
0507 
0508     pc->connection = NULL;
0509 
0510     now = ngx_time();
0511     hcf = hp->conf;
0512 
0513     points = hcf->points;
0514     point = &points->point[0];
0515 
0516     for ( ;; ) {
0517         server = point[hp->hash % points->number].server;
0518 
0519         ngx_log_debug2(NGX_LOG_DEBUG_STREAM, pc->log, 0,
0520                        "consistent hash peer:%uD, server:\"%V\"",
0521                        hp->hash, server);
0522 
0523         best = NULL;
0524         best_i = 0;
0525         total = 0;
0526 
0527         for (peer = hp->rrp.peers->peer, i = 0;
0528              peer;
0529              peer = peer->next, i++)
0530         {
0531             n = i / (8 * sizeof(uintptr_t));
0532             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
0533 
0534             if (hp->rrp.tried[n] & m) {
0535                 continue;
0536             }
0537 
0538             if (peer->down) {
0539                 continue;
0540             }
0541 
0542             if (peer->server.len != server->len
0543                 || ngx_strncmp(peer->server.data, server->data, server->len)
0544                    != 0)
0545             {
0546                 continue;
0547             }
0548 
0549             if (peer->max_fails
0550                 && peer->fails >= peer->max_fails
0551                 && now - peer->checked <= peer->fail_timeout)
0552             {
0553                 continue;
0554             }
0555 
0556             if (peer->max_conns && peer->conns >= peer->max_conns) {
0557                 continue;
0558             }
0559 
0560             peer->current_weight += peer->effective_weight;
0561             total += peer->effective_weight;
0562 
0563             if (peer->effective_weight < peer->weight) {
0564                 peer->effective_weight++;
0565             }
0566 
0567             if (best == NULL || peer->current_weight > best->current_weight) {
0568                 best = peer;
0569                 best_i = i;
0570             }
0571         }
0572 
0573         if (best) {
0574             best->current_weight -= total;
0575             break;
0576         }
0577 
0578         hp->hash++;
0579         hp->tries++;
0580 
0581         if (hp->tries >= points->number) {
0582             pc->name = hp->rrp.peers->name;
0583             ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0584             return NGX_BUSY;
0585         }
0586     }
0587 
0588     hp->rrp.current = best;
0589 
0590     pc->sockaddr = best->sockaddr;
0591     pc->socklen = best->socklen;
0592     pc->name = &best->name;
0593 
0594     best->conns++;
0595 
0596     if (now - best->checked > best->fail_timeout) {
0597         best->checked = now;
0598     }
0599 
0600     ngx_stream_upstream_rr_peers_unlock(hp->rrp.peers);
0601 
0602     n = best_i / (8 * sizeof(uintptr_t));
0603     m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));
0604 
0605     hp->rrp.tried[n] |= m;
0606 
0607     return NGX_OK;
0608 }
0609 
0610 
0611 static void *
0612 ngx_stream_upstream_hash_create_conf(ngx_conf_t *cf)
0613 {
0614     ngx_stream_upstream_hash_srv_conf_t  *conf;
0615 
0616     conf = ngx_palloc(cf->pool, sizeof(ngx_stream_upstream_hash_srv_conf_t));
0617     if (conf == NULL) {
0618         return NULL;
0619     }
0620 
0621     conf->points = NULL;
0622 
0623     return conf;
0624 }
0625 
0626 
0627 static char *
0628 ngx_stream_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
0629 {
0630     ngx_stream_upstream_hash_srv_conf_t  *hcf = conf;
0631 
0632     ngx_str_t                           *value;
0633     ngx_stream_upstream_srv_conf_t      *uscf;
0634     ngx_stream_compile_complex_value_t   ccv;
0635 
0636     value = cf->args->elts;
0637 
0638     ngx_memzero(&ccv, sizeof(ngx_stream_compile_complex_value_t));
0639 
0640     ccv.cf = cf;
0641     ccv.value = &value[1];
0642     ccv.complex_value = &hcf->key;
0643 
0644     if (ngx_stream_compile_complex_value(&ccv) != NGX_OK) {
0645         return NGX_CONF_ERROR;
0646     }
0647 
0648     uscf = ngx_stream_conf_get_module_srv_conf(cf, ngx_stream_upstream_module);
0649 
0650     if (uscf->peer.init_upstream) {
0651         ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
0652                            "load balancing method redefined");
0653     }
0654 
0655     uscf->flags = NGX_STREAM_UPSTREAM_CREATE
0656                   |NGX_STREAM_UPSTREAM_WEIGHT
0657                   |NGX_STREAM_UPSTREAM_MAX_CONNS
0658                   |NGX_STREAM_UPSTREAM_MAX_FAILS
0659                   |NGX_STREAM_UPSTREAM_FAIL_TIMEOUT
0660                   |NGX_STREAM_UPSTREAM_DOWN;
0661 
0662     if (cf->args->nelts == 2) {
0663         uscf->peer.init_upstream = ngx_stream_upstream_init_hash;
0664 
0665     } else if (ngx_strcmp(value[2].data, "consistent") == 0) {
0666         uscf->peer.init_upstream = ngx_stream_upstream_init_chash;
0667 
0668     } else {
0669         ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
0670                            "invalid parameter \"%V\"", &value[2]);
0671         return NGX_CONF_ERROR;
0672     }
0673 
0674     return NGX_CONF_OK;
0675 }