Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.15.12 ]​[ nginx-1.16.0 ]​

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_rlock(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_http_upstream_rr_peer_lock(hp->rrp.peers, peer);
0232 
0233         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0234                        "get hash peer, value:%uD, peer:%ui", hp->hash, p);
0235 
0236         if (peer->down) {
0237             ngx_http_upstream_rr_peer_unlock(hp->rrp.peers, peer);
0238             goto next;
0239         }
0240 
0241         if (peer->max_fails
0242             && peer->fails >= peer->max_fails
0243             && now - peer->checked <= peer->fail_timeout)
0244         {
0245             ngx_http_upstream_rr_peer_unlock(hp->rrp.peers, peer);
0246             goto next;
0247         }
0248 
0249         if (peer->max_conns && peer->conns >= peer->max_conns) {
0250             ngx_http_upstream_rr_peer_unlock(hp->rrp.peers, peer);
0251             goto next;
0252         }
0253 
0254         break;
0255 
0256     next:
0257 
0258         if (++hp->tries > 20) {
0259             ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0260             return hp->get_rr_peer(pc, &hp->rrp);
0261         }
0262     }
0263 
0264     hp->rrp.current = peer;
0265 
0266     pc->sockaddr = peer->sockaddr;
0267     pc->socklen = peer->socklen;
0268     pc->name = &peer->name;
0269 
0270     peer->conns++;
0271 
0272     if (now - peer->checked > peer->fail_timeout) {
0273         peer->checked = now;
0274     }
0275 
0276     ngx_http_upstream_rr_peer_unlock(hp->rrp.peers, peer);
0277     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0278 
0279     hp->rrp.tried[n] |= m;
0280 
0281     return NGX_OK;
0282 }
0283 
0284 
0285 static ngx_int_t
0286 ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
0287 {
0288     u_char                             *host, *port, c;
0289     size_t                              host_len, port_len, size;
0290     uint32_t                            hash, base_hash;
0291     ngx_str_t                          *server;
0292     ngx_uint_t                          npoints, i, j;
0293     ngx_http_upstream_rr_peer_t        *peer;
0294     ngx_http_upstream_rr_peers_t       *peers;
0295     ngx_http_upstream_chash_points_t   *points;
0296     ngx_http_upstream_hash_srv_conf_t  *hcf;
0297     union {
0298         uint32_t                        value;
0299         u_char                          byte[4];
0300     } prev_hash;
0301 
0302     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
0303         return NGX_ERROR;
0304     }
0305 
0306     us->peer.init = ngx_http_upstream_init_chash_peer;
0307 
0308     peers = us->peer.data;
0309     npoints = peers->total_weight * 160;
0310 
0311     size = sizeof(ngx_http_upstream_chash_points_t)
0312            + sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);
0313 
0314     points = ngx_palloc(cf->pool, size);
0315     if (points == NULL) {
0316         return NGX_ERROR;
0317     }
0318 
0319     points->number = 0;
0320 
0321     for (peer = peers->peer; peer; peer = peer->next) {
0322         server = &peer->server;
0323 
0324         /*
0325          * Hash expression is compatible with Cache::Memcached::Fast:
0326          * crc32(HOST \0 PORT PREV_HASH).
0327          */
0328 
0329         if (server->len >= 5
0330             && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
0331         {
0332             host = server->data + 5;
0333             host_len = server->len - 5;
0334             port = NULL;
0335             port_len = 0;
0336             goto done;
0337         }
0338 
0339         for (j = 0; j < server->len; j++) {
0340             c = server->data[server->len - j - 1];
0341 
0342             if (c == ':') {
0343                 host = server->data;
0344                 host_len = server->len - j - 1;
0345                 port = server->data + server->len - j;
0346                 port_len = j;
0347                 goto done;
0348             }
0349 
0350             if (c < '0' || c > '9') {
0351                 break;
0352             }
0353         }
0354 
0355         host = server->data;
0356         host_len = server->len;
0357         port = NULL;
0358         port_len = 0;
0359 
0360     done:
0361 
0362         ngx_crc32_init(base_hash);
0363         ngx_crc32_update(&base_hash, host, host_len);
0364         ngx_crc32_update(&base_hash, (u_char *) "", 1);
0365         ngx_crc32_update(&base_hash, port, port_len);
0366 
0367         prev_hash.value = 0;
0368         npoints = peer->weight * 160;
0369 
0370         for (j = 0; j < npoints; j++) {
0371             hash = base_hash;
0372 
0373             ngx_crc32_update(&hash, prev_hash.byte, 4);
0374             ngx_crc32_final(hash);
0375 
0376             points->point[points->number].hash = hash;
0377             points->point[points->number].server = server;
0378             points->number++;
0379 
0380 #if (NGX_HAVE_LITTLE_ENDIAN)
0381             prev_hash.value = hash;
0382 #else
0383             prev_hash.byte[0] = (u_char) (hash & 0xff);
0384             prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);
0385             prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);
0386             prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);
0387 #endif
0388         }
0389     }
0390 
0391     ngx_qsort(points->point,
0392               points->number,
0393               sizeof(ngx_http_upstream_chash_point_t),
0394               ngx_http_upstream_chash_cmp_points);
0395 
0396     for (i = 0, j = 1; j < points->number; j++) {
0397         if (points->point[i].hash != points->point[j].hash) {
0398             points->point[++i] = points->point[j];
0399         }
0400     }
0401 
0402     points->number = i + 1;
0403 
0404     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
0405     hcf->points = points;
0406 
0407     return NGX_OK;
0408 }
0409 
0410 
0411 static int ngx_libc_cdecl
0412 ngx_http_upstream_chash_cmp_points(const void *one, const void *two)
0413 {
0414     ngx_http_upstream_chash_point_t *first =
0415                                        (ngx_http_upstream_chash_point_t *) one;
0416     ngx_http_upstream_chash_point_t *second =
0417                                        (ngx_http_upstream_chash_point_t *) two;
0418 
0419     if (first->hash < second->hash) {
0420         return -1;
0421 
0422     } else if (first->hash > second->hash) {
0423         return 1;
0424 
0425     } else {
0426         return 0;
0427     }
0428 }
0429 
0430 
0431 static ngx_uint_t
0432 ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points,
0433     uint32_t hash)
0434 {
0435     ngx_uint_t                        i, j, k;
0436     ngx_http_upstream_chash_point_t  *point;
0437 
0438     /* find first point >= hash */
0439 
0440     point = &points->point[0];
0441 
0442     i = 0;
0443     j = points->number;
0444 
0445     while (i < j) {
0446         k = (i + j) / 2;
0447 
0448         if (hash > point[k].hash) {
0449             i = k + 1;
0450 
0451         } else if (hash < point[k].hash) {
0452             j = k;
0453 
0454         } else {
0455             return k;
0456         }
0457     }
0458 
0459     return i;
0460 }
0461 
0462 
0463 static ngx_int_t
0464 ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
0465     ngx_http_upstream_srv_conf_t *us)
0466 {
0467     uint32_t                             hash;
0468     ngx_http_upstream_hash_srv_conf_t   *hcf;
0469     ngx_http_upstream_hash_peer_data_t  *hp;
0470 
0471     if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK) {
0472         return NGX_ERROR;
0473     }
0474 
0475     r->upstream->peer.get = ngx_http_upstream_get_chash_peer;
0476 
0477     hp = r->upstream->peer.data;
0478     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
0479 
0480     hash = ngx_crc32_long(hp->key.data, hp->key.len);
0481 
0482     ngx_http_upstream_rr_peers_rlock(hp->rrp.peers);
0483 
0484     hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);
0485 
0486     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0487 
0488     return NGX_OK;
0489 }
0490 
0491 
0492 static ngx_int_t
0493 ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
0494 {
0495     ngx_http_upstream_hash_peer_data_t  *hp = data;
0496 
0497     time_t                              now;
0498     intptr_t                            m;
0499     ngx_str_t                          *server;
0500     ngx_int_t                           total;
0501     ngx_uint_t                          i, n, best_i;
0502     ngx_http_upstream_rr_peer_t        *peer, *best;
0503     ngx_http_upstream_chash_point_t    *point;
0504     ngx_http_upstream_chash_points_t   *points;
0505     ngx_http_upstream_hash_srv_conf_t  *hcf;
0506 
0507     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0508                    "get consistent hash peer, try: %ui", pc->tries);
0509 
0510     ngx_http_upstream_rr_peers_wlock(hp->rrp.peers);
0511 
0512     if (hp->tries > 20 || hp->rrp.peers->single) {
0513         ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0514         return hp->get_rr_peer(pc, &hp->rrp);
0515     }
0516 
0517     pc->cached = 0;
0518     pc->connection = NULL;
0519 
0520     now = ngx_time();
0521     hcf = hp->conf;
0522 
0523     points = hcf->points;
0524     point = &points->point[0];
0525 
0526     for ( ;; ) {
0527         server = point[hp->hash % points->number].server;
0528 
0529         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
0530                        "consistent hash peer:%uD, server:\"%V\"",
0531                        hp->hash, server);
0532 
0533         best = NULL;
0534         best_i = 0;
0535         total = 0;
0536 
0537         for (peer = hp->rrp.peers->peer, i = 0;
0538              peer;
0539              peer = peer->next, i++)
0540         {
0541             n = i / (8 * sizeof(uintptr_t));
0542             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
0543 
0544             if (hp->rrp.tried[n] & m) {
0545                 continue;
0546             }
0547 
0548             if (peer->down) {
0549                 continue;
0550             }
0551 
0552             if (peer->max_fails
0553                 && peer->fails >= peer->max_fails
0554                 && now - peer->checked <= peer->fail_timeout)
0555             {
0556                 continue;
0557             }
0558 
0559             if (peer->max_conns && peer->conns >= peer->max_conns) {
0560                 continue;
0561             }
0562 
0563             if (peer->server.len != server->len
0564                 || ngx_strncmp(peer->server.data, server->data, server->len)
0565                    != 0)
0566             {
0567                 continue;
0568             }
0569 
0570             peer->current_weight += peer->effective_weight;
0571             total += peer->effective_weight;
0572 
0573             if (peer->effective_weight < peer->weight) {
0574                 peer->effective_weight++;
0575             }
0576 
0577             if (best == NULL || peer->current_weight > best->current_weight) {
0578                 best = peer;
0579                 best_i = i;
0580             }
0581         }
0582 
0583         if (best) {
0584             best->current_weight -= total;
0585             goto found;
0586         }
0587 
0588         hp->hash++;
0589         hp->tries++;
0590 
0591         if (hp->tries > 20) {
0592             ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0593             return hp->get_rr_peer(pc, &hp->rrp);
0594         }
0595     }
0596 
0597 found:
0598 
0599     hp->rrp.current = best;
0600 
0601     pc->sockaddr = best->sockaddr;
0602     pc->socklen = best->socklen;
0603     pc->name = &best->name;
0604 
0605     best->conns++;
0606 
0607     if (now - best->checked > best->fail_timeout) {
0608         best->checked = now;
0609     }
0610 
0611     ngx_http_upstream_rr_peers_unlock(hp->rrp.peers);
0612 
0613     n = best_i / (8 * sizeof(uintptr_t));
0614     m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));
0615 
0616     hp->rrp.tried[n] |= m;
0617 
0618     return NGX_OK;
0619 }
0620 
0621 
0622 static void *
0623 ngx_http_upstream_hash_create_conf(ngx_conf_t *cf)
0624 {
0625     ngx_http_upstream_hash_srv_conf_t  *conf;
0626 
0627     conf = ngx_palloc(cf->pool, sizeof(ngx_http_upstream_hash_srv_conf_t));
0628     if (conf == NULL) {
0629         return NULL;
0630     }
0631 
0632     conf->points = NULL;
0633 
0634     return conf;
0635 }
0636 
0637 
0638 static char *
0639 ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
0640 {
0641     ngx_http_upstream_hash_srv_conf_t  *hcf = conf;
0642 
0643     ngx_str_t                         *value;
0644     ngx_http_upstream_srv_conf_t      *uscf;
0645     ngx_http_compile_complex_value_t   ccv;
0646 
0647     value = cf->args->elts;
0648 
0649     ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));
0650 
0651     ccv.cf = cf;
0652     ccv.value = &value[1];
0653     ccv.complex_value = &hcf->key;
0654 
0655     if (ngx_http_compile_complex_value(&ccv) != NGX_OK) {
0656         return NGX_CONF_ERROR;
0657     }
0658 
0659     uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);
0660 
0661     if (uscf->peer.init_upstream) {
0662         ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
0663                            "load balancing method redefined");
0664     }
0665 
0666     uscf->flags = NGX_HTTP_UPSTREAM_CREATE
0667                   |NGX_HTTP_UPSTREAM_WEIGHT
0668                   |NGX_HTTP_UPSTREAM_MAX_CONNS
0669                   |NGX_HTTP_UPSTREAM_MAX_FAILS
0670                   |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
0671                   |NGX_HTTP_UPSTREAM_DOWN;
0672 
0673     if (cf->args->nelts == 2) {
0674         uscf->peer.init_upstream = ngx_http_upstream_init_hash;
0675 
0676     } else if (ngx_strcmp(value[2].data, "consistent") == 0) {
0677         uscf->peer.init_upstream = ngx_http_upstream_init_chash;
0678 
0679     } else {
0680         ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
0681                            "invalid parameter \"%V\"", &value[2]);
0682         return NGX_CONF_ERROR;
0683     }
0684 
0685     return NGX_CONF_OK;
0686 }