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_http.h>
0011 
0012 
0013 typedef struct {
0014     uint32_t                            hash;
0015     ngx_str_t                          *server;
0016 } ngx_http_upstream_chash_point_t;
0017 
0018 
0019 typedef struct {
0020     ngx_uint_t                          number;
0021     ngx_http_upstream_chash_point_t     point[1];
0022 } ngx_http_upstream_chash_points_t;
0023 
0024 
0025 typedef struct {
0026     ngx_http_complex_value_t            key;
0027     ngx_http_upstream_chash_points_t   *points;
0028 } ngx_http_upstream_hash_srv_conf_t;
0029 
0030 
0031 typedef struct {
0032     /* the round robin data must be first */
0033     ngx_http_upstream_rr_peer_data_t    rrp;
0034     ngx_http_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_http_upstream_hash_peer_data_t;
0041 
0042 
0043 static ngx_int_t ngx_http_upstream_init_hash(ngx_conf_t *cf,
0044     ngx_http_upstream_srv_conf_t *us);
0045 static ngx_int_t ngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
0046     ngx_http_upstream_srv_conf_t *us);
0047 static ngx_int_t ngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc,
0048     void *data);
0049 
0050 static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf,
0051     ngx_http_upstream_srv_conf_t *us);
0052 static int ngx_libc_cdecl
0053     ngx_http_upstream_chash_cmp_points(const void *one, const void *two);
0054 static ngx_uint_t ngx_http_upstream_find_chash_point(
0055     ngx_http_upstream_chash_points_t *points, uint32_t hash);
0056 static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
0057     ngx_http_upstream_srv_conf_t *us);
0058 static ngx_int_t ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc,
0059     void *data);
0060 
0061 static void *ngx_http_upstream_hash_create_conf(ngx_conf_t *cf);
0062 static char *ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd,
0063     void *conf);
0064 
0065 
0066 static ngx_command_t  ngx_http_upstream_hash_commands[] = {
0067 
0068     { ngx_string("hash"),
0069       NGX_HTTP_UPS_CONF|NGX_CONF_TAKE12,
0070       ngx_http_upstream_hash,
0071       NGX_HTTP_SRV_CONF_OFFSET,
0072       0,
0073       NULL },
0074 
0075       ngx_null_command
0076 };
0077 
0078 
0079 static ngx_http_module_t  ngx_http_upstream_hash_module_ctx = {
0080     NULL,                                  /* preconfiguration */
0081     NULL,                                  /* postconfiguration */
0082 
0083     NULL,                                  /* create main configuration */
0084     NULL,                                  /* init main configuration */
0085 
0086     ngx_http_upstream_hash_create_conf,    /* create server configuration */
0087     NULL,                                  /* merge server configuration */
0088 
0089     NULL,                                  /* create location configuration */
0090     NULL                                   /* merge location configuration */
0091 };
0092 
0093 
0094 ngx_module_t  ngx_http_upstream_hash_module = {
0095     NGX_MODULE_V1,
0096     &ngx_http_upstream_hash_module_ctx,    /* module context */
0097     ngx_http_upstream_hash_commands,       /* module directives */
0098     NGX_HTTP_MODULE,                       /* module type */
0099     NULL,                                  /* init master */
0100     NULL,                                  /* init module */
0101     NULL,                                  /* init process */
0102     NULL,                                  /* init thread */
0103     NULL,                                  /* exit thread */
0104     NULL,                                  /* exit process */
0105     NULL,                                  /* exit master */
0106     NGX_MODULE_V1_PADDING
0107 };
0108 
0109 
0110 static ngx_int_t
0111 ngx_http_upstream_init_hash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
0112 {
0113     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
0114         return NGX_ERROR;
0115     }
0116 
0117     us->peer.init = ngx_http_upstream_init_hash_peer;
0118 
0119     return NGX_OK;
0120 }
0121 
0122 
0123 static ngx_int_t
0124 ngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
0125     ngx_http_upstream_srv_conf_t *us)
0126 {
0127     ngx_http_upstream_hash_srv_conf_t   *hcf;
0128     ngx_http_upstream_hash_peer_data_t  *hp;
0129 
0130     hp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_hash_peer_data_t));
0131     if (hp == NULL) {
0132         return NGX_ERROR;
0133     }
0134 
0135     r->upstream->peer.data = &hp->rrp;
0136 
0137     if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
0138         return NGX_ERROR;
0139     }
0140 
0141     r->upstream->peer.get = ngx_http_upstream_get_hash_peer;
0142 
0143     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
0144 
0145     if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK) {
0146         return NGX_ERROR;
0147     }
0148 
0149     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->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_http_upstream_get_round_robin_peer;
0157 
0158     return NGX_OK;
0159 }
0160 
0161 
0162 static ngx_int_t
0163 ngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc, void *data)
0164 {
0165     ngx_http_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_http_upstream_rr_peer_t  *peer;
0175 
0176     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0177                    "get hash peer, try: %ui", pc->tries);
0178 
0179     ngx_http_upstream_rr_peers_wlock(hp->rrp.peers);
0180 
0181     if (hp->tries > 20 || hp->rrp.peers->single) {
0182         ngx_http_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->cached = 0;
0189     pc->connection = NULL;
0190 
0191     for ( ;; ) {
0192 
0193         /*
0194          * Hash expression is compatible with Cache::Memcached:
0195          * ((crc32([REHASH] KEY) >> 16) & 0x7fff) + PREV_HASH
0196          * with REHASH omitted at the first iteration.
0197          */
0198 
0199         ngx_crc32_init(hash);
0200 
0201         if (hp->rehash > 0) {
0202             size = ngx_sprintf(buf, "%ui", hp->rehash) - buf;
0203             ngx_crc32_update(&hash, buf, size);
0204         }
0205 
0206         ngx_crc32_update(&hash, hp->key.data, hp->key.len);
0207         ngx_crc32_final(hash);
0208 
0209         hash = (hash >> 16) & 0x7fff;
0210 
0211         hp->hash += hash;
0212         hp->rehash++;
0213 
0214         w = hp->hash % hp->rrp.peers->total_weight;
0215         peer = hp->rrp.peers->peer;
0216         p = 0;
0217 
0218         while (w >= peer->weight) {
0219             w -= peer->weight;
0220             peer = peer->next;
0221             p++;
0222         }
0223 
0224         n = p / (8 * sizeof(uintptr_t));
0225         m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
0226 
0227         if (hp->rrp.tried[n] & m) {
0228             goto next;
0229         }
0230 
0231         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0232                        "get hash peer, value:%uD, peer:%ui", hp->hash, p);
0233 
0234         if (peer->down) {
0235             goto next;
0236         }
0237 
0238         if (peer->max_fails
0239             && peer->fails >= peer->max_fails
0240             && now - peer->checked <= peer->fail_timeout)
0241         {
0242             goto next;
0243         }
0244 
0245         if (peer->max_conns && peer->conns >= peer->max_conns) {
0246             goto next;
0247         }
0248 
0249         break;
0250 
0251     next:
0252 
0253         if (++hp->tries > 20) {
0254             ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0255             return hp->get_rr_peer(pc, &hp->rrp);
0256         }
0257     }
0258 
0259     hp->rrp.current = peer;
0260 
0261     pc->sockaddr = peer->sockaddr;
0262     pc->socklen = peer->socklen;
0263     pc->name = &peer->name;
0264 
0265     peer->conns++;
0266 
0267     if (now - peer->checked > peer->fail_timeout) {
0268         peer->checked = now;
0269     }
0270 
0271     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0272 
0273     hp->rrp.tried[n] |= m;
0274 
0275     return NGX_OK;
0276 }
0277 
0278 
0279 static ngx_int_t
0280 ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_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_http_upstream_rr_peer_t        *peer;
0288     ngx_http_upstream_rr_peers_t       *peers;
0289     ngx_http_upstream_chash_points_t   *points;
0290     ngx_http_upstream_hash_srv_conf_t  *hcf;
0291     union {
0292         uint32_t                        value;
0293         u_char                          byte[4];
0294     } prev_hash;
0295 
0296     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
0297         return NGX_ERROR;
0298     }
0299 
0300     us->peer.init = ngx_http_upstream_init_chash_peer;
0301 
0302     peers = us->peer.data;
0303     npoints = peers->total_weight * 160;
0304 
0305     size = sizeof(ngx_http_upstream_chash_points_t)
0306            + sizeof(ngx_http_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_http_upstream_chash_point_t),
0388               ngx_http_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_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
0399     hcf->points = points;
0400 
0401     return NGX_OK;
0402 }
0403 
0404 
0405 static int ngx_libc_cdecl
0406 ngx_http_upstream_chash_cmp_points(const void *one, const void *two)
0407 {
0408     ngx_http_upstream_chash_point_t *first =
0409                                        (ngx_http_upstream_chash_point_t *) one;
0410     ngx_http_upstream_chash_point_t *second =
0411                                        (ngx_http_upstream_chash_point_t *) two;
0412 
0413     if (first->hash < second->hash) {
0414         return -1;
0415 
0416     } else if (first->hash > second->hash) {
0417         return 1;
0418 
0419     } else {
0420         return 0;
0421     }
0422 }
0423 
0424 
0425 static ngx_uint_t
0426 ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points,
0427     uint32_t hash)
0428 {
0429     ngx_uint_t                        i, j, k;
0430     ngx_http_upstream_chash_point_t  *point;
0431 
0432     /* find first point >= hash */
0433 
0434     point = &points->point[0];
0435 
0436     i = 0;
0437     j = points->number;
0438 
0439     while (i < j) {
0440         k = (i + j) / 2;
0441 
0442         if (hash > point[k].hash) {
0443             i = k + 1;
0444 
0445         } else if (hash < point[k].hash) {
0446             j = k;
0447 
0448         } else {
0449             return k;
0450         }
0451     }
0452 
0453     return i;
0454 }
0455 
0456 
0457 static ngx_int_t
0458 ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
0459     ngx_http_upstream_srv_conf_t *us)
0460 {
0461     uint32_t                             hash;
0462     ngx_http_upstream_hash_srv_conf_t   *hcf;
0463     ngx_http_upstream_hash_peer_data_t  *hp;
0464 
0465     if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK) {
0466         return NGX_ERROR;
0467     }
0468 
0469     r->upstream->peer.get = ngx_http_upstream_get_chash_peer;
0470 
0471     hp = r->upstream->peer.data;
0472     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
0473 
0474     hash = ngx_crc32_long(hp->key.data, hp->key.len);
0475 
0476     ngx_http_upstream_rr_peers_rlock(hp->rrp.peers);
0477 
0478     hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);
0479 
0480     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0481 
0482     return NGX_OK;
0483 }
0484 
0485 
0486 static ngx_int_t
0487 ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
0488 {
0489     ngx_http_upstream_hash_peer_data_t  *hp = data;
0490 
0491     time_t                              now;
0492     intptr_t                            m;
0493     ngx_str_t                          *server;
0494     ngx_int_t                           total;
0495     ngx_uint_t                          i, n, best_i;
0496     ngx_http_upstream_rr_peer_t        *peer, *best;
0497     ngx_http_upstream_chash_point_t    *point;
0498     ngx_http_upstream_chash_points_t   *points;
0499     ngx_http_upstream_hash_srv_conf_t  *hcf;
0500 
0501     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0502                    "get consistent hash peer, try: %ui", pc->tries);
0503 
0504     ngx_http_upstream_rr_peers_wlock(hp->rrp.peers);
0505 
0506     pc->cached = 0;
0507     pc->connection = NULL;
0508 
0509     now = ngx_time();
0510     hcf = hp->conf;
0511 
0512     points = hcf->points;
0513     point = &points->point[0];
0514 
0515     for ( ;; ) {
0516         server = point[hp->hash % points->number].server;
0517 
0518         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0519                        "consistent hash peer:%uD, server:\"%V\"",
0520                        hp->hash, server);
0521 
0522         best = NULL;
0523         best_i = 0;
0524         total = 0;
0525 
0526         for (peer = hp->rrp.peers->peer, i = 0;
0527              peer;
0528              peer = peer->next, i++)
0529         {
0530             n = i / (8 * sizeof(uintptr_t));
0531             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
0532 
0533             if (hp->rrp.tried[n] & m) {
0534                 continue;
0535             }
0536 
0537             if (peer->down) {
0538                 continue;
0539             }
0540 
0541             if (peer->server.len != server->len
0542                 || ngx_strncmp(peer->server.data, server->data, server->len)
0543                    != 0)
0544             {
0545                 continue;
0546             }
0547 
0548             if (peer->max_fails
0549                 && peer->fails >= peer->max_fails
0550                 && now - peer->checked <= peer->fail_timeout)
0551             {
0552                 continue;
0553             }
0554 
0555             if (peer->max_conns && peer->conns >= peer->max_conns) {
0556                 continue;
0557             }
0558 
0559             peer->current_weight += peer->effective_weight;
0560             total += peer->effective_weight;
0561 
0562             if (peer->effective_weight < peer->weight) {
0563                 peer->effective_weight++;
0564             }
0565 
0566             if (best == NULL || peer->current_weight > best->current_weight) {
0567                 best = peer;
0568                 best_i = i;
0569             }
0570         }
0571 
0572         if (best) {
0573             best->current_weight -= total;
0574             goto found;
0575         }
0576 
0577         hp->hash++;
0578         hp->tries++;
0579 
0580         if (hp->tries >= points->number) {
0581             pc->name = hp->rrp.peers->name;
0582             ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0583             return NGX_BUSY;
0584         }
0585     }
0586 
0587 found:
0588 
0589     hp->rrp.current = best;
0590 
0591     pc->sockaddr = best->sockaddr;
0592     pc->socklen = best->socklen;
0593     pc->name = &best->name;
0594 
0595     best->conns++;
0596 
0597     if (now - best->checked > best->fail_timeout) {
0598         best->checked = now;
0599     }
0600 
0601     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0602 
0603     n = best_i / (8 * sizeof(uintptr_t));
0604     m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));
0605 
0606     hp->rrp.tried[n] |= m;
0607 
0608     return NGX_OK;
0609 }
0610 
0611 
0612 static void *
0613 ngx_http_upstream_hash_create_conf(ngx_conf_t *cf)
0614 {
0615     ngx_http_upstream_hash_srv_conf_t  *conf;
0616 
0617     conf = ngx_palloc(cf->pool, sizeof(ngx_http_upstream_hash_srv_conf_t));
0618     if (conf == NULL) {
0619         return NULL;
0620     }
0621 
0622     conf->points = NULL;
0623 
0624     return conf;
0625 }
0626 
0627 
0628 static char *
0629 ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
0630 {
0631     ngx_http_upstream_hash_srv_conf_t  *hcf = conf;
0632 
0633     ngx_str_t                         *value;
0634     ngx_http_upstream_srv_conf_t      *uscf;
0635     ngx_http_compile_complex_value_t   ccv;
0636 
0637     value = cf->args->elts;
0638 
0639     ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));
0640 
0641     ccv.cf = cf;
0642     ccv.value = &value[1];
0643     ccv.complex_value = &hcf->key;
0644 
0645     if (ngx_http_compile_complex_value(&ccv) != NGX_OK) {
0646         return NGX_CONF_ERROR;
0647     }
0648 
0649     uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);
0650 
0651     if (uscf->peer.init_upstream) {
0652         ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
0653                            "load balancing method redefined");
0654     }
0655 
0656     uscf->flags = NGX_HTTP_UPSTREAM_CREATE
0657                   |NGX_HTTP_UPSTREAM_WEIGHT
0658                   |NGX_HTTP_UPSTREAM_MAX_CONNS
0659                   |NGX_HTTP_UPSTREAM_MAX_FAILS
0660                   |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
0661                   |NGX_HTTP_UPSTREAM_DOWN;
0662 
0663     if (cf->args->nelts == 2) {
0664         uscf->peer.init_upstream = ngx_http_upstream_init_hash;
0665 
0666     } else if (ngx_strcmp(value[2].data, "consistent") == 0) {
0667         uscf->peer.init_upstream = ngx_http_upstream_init_chash;
0668 
0669     } else {
0670         ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
0671                            "invalid parameter \"%V\"", &value[2]);
0672         return NGX_CONF_ERROR;
0673     }
0674 
0675     return NGX_CONF_OK;
0676 }