One Level Up Top Level

src/http/modules/ngx_http_upstream_hash_module.c - nginx-1.7.10

Global variables defined

Data types defined

Functions defined

Source code


  2. /*
  3. * Copyright (C) Roman Arutyunyan
  4. * Copyright (C) Nginx, Inc.
  5. */


  8. #include <ngx_config.h>
  9. #include <ngx_core.h>
  10. #include <ngx_http.h>


  13. typedef struct {
  14.     uint32_t                            hash;
  15.     ngx_str_t                          *server;
  16. ‌} ngx_http_upstream_chash_point_t;


  19. typedef struct {
  20.     ngx_uint_t                          number;
  21.     ngx_http_upstream_chash_point_t     point[1];
  22. ‌} ngx_http_upstream_chash_points_t;


  25. typedef struct {
  26.     ngx_http_complex_value_t            key;
  27.     ngx_http_upstream_chash_points_t   *points;
  28. ‌} ngx_http_upstream_hash_srv_conf_t;


  31. typedef struct {
  32.     /* the round robin data must be first */
  33.     ngx_http_upstream_rr_peer_data_t    rrp;
  34.     ngx_http_upstream_hash_srv_conf_t  *conf;
  35.     ngx_str_t                           key;
  36.     ngx_uint_t                          tries;
  37.     ngx_uint_t                          rehash;
  38.     uint32_t                            hash;
  39.     ngx_event_get_peer_pt               get_rr_peer;
  40. ‌} ngx_http_upstream_hash_peer_data_t;


  43. static ngx_int_t ngx_http_upstream_init_hash(ngx_conf_t *cf,
  44.     ngx_http_upstream_srv_conf_t *us);
  45. static ngx_int_t ngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
  46.     ngx_http_upstream_srv_conf_t *us);
  47. static ngx_int_t ngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc,
  48.     void *data);

  50. static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf,
  51.     ngx_http_upstream_srv_conf_t *us);
  52. static void ngx_http_upstream_add_chash_point(
  53.     ngx_http_upstream_chash_points_t *points, uint32_t hash, ngx_str_t *server);
  54. static ngx_uint_t ngx_http_upstream_find_chash_point(
  55.     ngx_http_upstream_chash_points_t *points, uint32_t hash);
  56. static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
  57.     ngx_http_upstream_srv_conf_t *us);
  58. static ngx_int_t ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc,
  59.     void *data);

  61. static void *ngx_http_upstream_hash_create_conf(ngx_conf_t *cf);
  62. static char *ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd,
  63.     void *conf);


  66. ‌static ngx_command_t  ngx_http_upstream_hash_commands[] = {

  68.     { ngx_string("hash"),
  69.       NGX_HTTP_UPS_CONF|NGX_CONF_TAKE12,
  70.       ngx_http_upstream_hash,
  71.       NGX_HTTP_SRV_CONF_OFFSET,
  72.       0,
  73.       NULL },

  75.       ngx_null_command
  76. };


  79. ‌static ngx_http_module_t  ngx_http_upstream_hash_module_ctx = {
  80.     NULL,                                  /* preconfiguration */
  81.     NULL,                                  /* postconfiguration */

  83.     NULL,                                  /* create main configuration */
  84.     NULL,                                  /* init main configuration */

  86.     ngx_http_upstream_hash_create_conf,    /* create server configuration */
  87.     NULL,                                  /* merge server configuration */

  89.     NULL,                                  /* create location configuration */
  90.     NULL                                   /* merge location configuration */
  91. };


  94. ‌ngx_module_t  ngx_http_upstream_hash_module = {
  95.     NGX_MODULE_V1,
  96.     &ngx_http_upstream_hash_module_ctx,    /* module context */
  97.     ngx_http_upstream_hash_commands,       /* module directives */
  98.     NGX_HTTP_MODULE,                       /* module type */
  99.     NULL,                                  /* init master */
  100.     NULL,                                  /* init module */
  101.     NULL,                                  /* init process */
  102.     NULL,                                  /* init thread */
  103.     NULL,                                  /* exit thread */
  104.     NULL,                                  /* exit process */
  105.     NULL,                                  /* exit master */
  106.     NGX_MODULE_V1_PADDING
  107. };


  110. static ngx_int_t
  111. ‌ngx_http_upstream_init_hash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
  112. {
  113.     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
  114.         return NGX_ERROR;
  115.     }

  117.     us->peer.init = ngx_http_upstream_init_hash_peer;

  119.     return NGX_OK;
  120. }


  123. static ngx_int_t
  124. ‌ngx_http_upstream_init_hash_peer(ngx_http_request_t *r,
  125.     ngx_http_upstream_srv_conf_t *us)
  126. {
  127.     ngx_http_upstream_hash_srv_conf_t   *hcf;
  128.     ngx_http_upstream_hash_peer_data_t  *hp;

  130.     hp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_hash_peer_data_t));
  131.     if (hp == NULL) {
  132.         return NGX_ERROR;
  133.     }

  135.     r->upstream->peer.data = &hp->rrp;

  137.     if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
  138.         return NGX_ERROR;
  139.     }

  141.     r->upstream->peer.get = ngx_http_upstream_get_hash_peer;

  143.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);

  145.     if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK) {
  146.         return NGX_ERROR;
  147.     }

  149.     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
  150.                    "upstream hash key:\"%V\"", &hp->key);

  152.     hp->conf = hcf;
  153.     hp->tries = 0;
  154.     hp->rehash = 0;
  155.     hp->hash = 0;
  156.     hp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;

  158.     return NGX_OK;
  159. }


  162. static ngx_int_t
  163. ‌ngx_http_upstream_get_hash_peer(ngx_peer_connection_t *pc, void *data)
  164. {
  165.     ngx_http_upstream_hash_peer_data_t  *hp = data;

  167.     time_t                        now;
  168.     u_char                        buf[NGX_INT_T_LEN];
  169.     size_t                        size;
  170.     uint32_t                      hash;
  171.     ngx_int_t                     w;
  172.     uintptr_t                     m;
  173.     ngx_uint_t                    i, n, p;
  174.     ngx_http_upstream_rr_peer_t  *peer;

  176.     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
  177.                    "get hash peer, try: %ui", pc->tries);

  179.     if (hp->tries > 20 || hp->rrp.peers->single) {
  180.         return hp->get_rr_peer(pc, &hp->rrp);
  181.     }

  183.     now = ngx_time();

  185.     pc->cached = 0;
  186.     pc->connection = NULL;

  188.     for ( ;; ) {

  190.         /*
  191.          * Hash expression is compatible with Cache::Memcached:
  192.          * ((crc32([REHASH] KEY) >> 16) & 0x7fff) + PREV_HASH
  193.          * with REHASH omitted at the first iteration.
  194.          */

  196.         ngx_crc32_init(hash);

  198.         if (hp->rehash > 0) {
  199.             size = ngx_sprintf(buf, "%ui", hp->rehash) - buf;
  200.             ngx_crc32_update(&hash, buf, size);
  201.         }

  203.         ngx_crc32_update(&hash, hp->key.data, hp->key.len);
  204.         ngx_crc32_final(hash);

  206.         hash = (hash >> 16) & 0x7fff;

  208.         hp->hash += hash;
  209.         hp->rehash++;

  211.         if (!hp->rrp.peers->weighted) {
  212.             p = hp->hash % hp->rrp.peers->number;

  214.         } else {
  215.             w = hp->hash % hp->rrp.peers->total_weight;

  217.             for (i = 0; i < hp->rrp.peers->number; i++) {
  218.                 w -= hp->rrp.peers->peer[i].weight;
  219.                 if (w < 0) {
  220.                     break;
  221.                 }
  222.             }

  224.             p = i;
  225.         }

  227.         n = p / (8 * sizeof(uintptr_t));
  228.         m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));

  230.         if (hp->rrp.tried[n] & m) {
  231.             goto next;
  232.         }

  234.         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
  235.                        "get hash peer, value:%uD, peer:%ui", hp->hash, p);

  237.         peer = &hp->rrp.peers->peer[p];

  239.         if (peer->down) {
  240.             goto next;
  241.         }

  243.         if (peer->max_fails
  244.             && peer->fails >= peer->max_fails
  245.             && now - peer->checked <= peer->fail_timeout)
  246.         {
  247.             goto next;
  248.         }

  250.         break;

  252.     next:

  254.         if (++hp->tries > 20) {
  255.             return hp->get_rr_peer(pc, &hp->rrp);
  256.         }
  257.     }

  259.     hp->rrp.current = p;

  261.     pc->sockaddr = peer->sockaddr;
  262.     pc->socklen = peer->socklen;
  263.     pc->name = &peer->name;

  265.     if (now - peer->checked > peer->fail_timeout) {
  266.         peer->checked = now;
  267.     }

  269.     hp->rrp.tried[n] |= m;

  271.     return NGX_OK;
  272. }


  275. static ngx_int_t
  276. ‌ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
  277. {
  278.     u_char                             *host, *port, c;
  279.     size_t                              host_len, port_len, size;
  280.     uint32_t                            hash, base_hash, prev_hash;
  281.     ngx_str_t                          *server;
  282.     ngx_uint_t                          npoints, i, j;
  283.     ngx_http_upstream_rr_peer_t        *peer;
  284.     ngx_http_upstream_rr_peers_t       *peers;
  285.     ngx_http_upstream_chash_points_t   *points;
  286.     ngx_http_upstream_hash_srv_conf_t  *hcf;

  288.     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
  289.         return NGX_ERROR;
  290.     }

  292.     us->peer.init = ngx_http_upstream_init_chash_peer;

  294.     peers = us->peer.data;
  295.     npoints = peers->total_weight * 160;

  297.     size = sizeof(ngx_http_upstream_chash_points_t)
  298.            + sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);

  300.     points = ngx_palloc(cf->pool, size);
  301.     if (points == NULL) {
  302.         return NGX_ERROR;
  303.     }

  305.     points->number = 0;

  307.     for (i = 0; i < peers->number; i++) {
  308.         peer = &peers->peer[i];
  309.         server = &peer->server;

  311.         /*
  312.          * Hash expression is compatible with Cache::Memcached::Fast:
  313.          * crc32(HOST \0 PORT PREV_HASH).
  314.          */

  316.         if (server->len >= 5
  317.             && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
  318.         {
  319.             host = server->data + 5;
  320.             host_len = server->len - 5;
  321.             port = NULL;
  322.             port_len = 0;
  323.             goto done;
  324.         }

  326.         for (j = 0; j < server->len; j++) {
  327.             c = server->data[server->len - j - 1];

  329.             if (c == ':') {
  330.                 host = server->data;
  331.                 host_len = server->len - j - 1;
  332.                 port = server->data + server->len - j;
  333.                 port_len = j;
  334.                 goto done;
  335.             }

  337.             if (c < '0' || c > '9') {
  338.                 break;
  339.             }
  340.         }

  342.         host = server->data;
  343.         host_len = server->len;
  344.         port = NULL;
  345.         port_len = 0;

  347.     done:

  349.         ngx_crc32_init(base_hash);
  350.         ngx_crc32_update(&base_hash, host, host_len);
  351.         ngx_crc32_update(&base_hash, (u_char *) "", 1);
  352.         ngx_crc32_update(&base_hash, port, port_len);

  354.         prev_hash = 0;
  355.         npoints = peer->weight * 160;

  357.         for (j = 0; j < npoints; j++) {
  358.             hash = base_hash;

  360.             ngx_crc32_update(&hash, (u_char *) &prev_hash, sizeof(uint32_t));
  361.             ngx_crc32_final(hash);

  363.             ngx_http_upstream_add_chash_point(points, hash, &peer->server);

  365.             prev_hash = hash;
  366.         }
  367.     }

  369.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
  370.     hcf->points = points;

  372.     return NGX_OK;
  373. }


  376. static void
  377. ‌ngx_http_upstream_add_chash_point(ngx_http_upstream_chash_points_t *points,
  378.     uint32_t hash, ngx_str_t *server)
  379. {
  380.     size_t                            size;
  381.     ngx_uint_t                        i;
  382.     ngx_http_upstream_chash_point_t  *point;

  384.     i = ngx_http_upstream_find_chash_point(points, hash);
  385.     point = &points->point[i];

  387.     if (point->hash == hash) {
  388.         return;
  389.     }

  391.     size = (points->number - i) * sizeof(ngx_http_upstream_chash_point_t);

  393.     ngx_memmove(point + 1, point, size);

  395.     points->number++;
  396.     point->hash = hash;
  397.     point->server = server;
  398. }


  401. static ngx_uint_t
  402. ‌ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points,
  403.     uint32_t hash)
  404. {
  405.     ngx_uint_t                        i, j, k;
  406.     ngx_http_upstream_chash_point_t  *point;

  408.     /* find first point >= hash */

  410.     point = &points->point[0];

  412.     i = 0;
  413.     j = points->number;

  415.     while (i < j) {
  416.         k = (i + j) / 2;

  418.         if (hash > point[k].hash) {
  419.             i = k + 1;

  421.         } else if (hash < point[k].hash) {
  422.             j = k;

  424.         } else {
  425.             return k;
  426.         }
  427.     }

  429.     return i;
  430. }


  433. static ngx_int_t
  434. ‌ngx_http_upstream_init_chash_peer(ngx_http_request_t *r,
  435.     ngx_http_upstream_srv_conf_t *us)
  436. {
  437.     uint32_t                             hash;
  438.     ngx_http_upstream_hash_srv_conf_t   *hcf;
  439.     ngx_http_upstream_hash_peer_data_t  *hp;

  441.     if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK) {
  442.         return NGX_ERROR;
  443.     }

  445.     r->upstream->peer.get = ngx_http_upstream_get_chash_peer;

  447.     hp = r->upstream->peer.data;
  448.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);

  450.     hash = ngx_crc32_long(hp->key.data, hp->key.len);
  451.     hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);

  453.     return NGX_OK;
  454. }


  457. static ngx_int_t
  458. ‌ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
  459. {
  460.     ngx_http_upstream_hash_peer_data_t  *hp = data;

  462.     time_t                              now;
  463.     intptr_t                            m;
  464.     ngx_str_t                          *server;
  465.     ngx_int_t                           total;
  466.     ngx_uint_t                          i, n;
  467.     ngx_http_upstream_rr_peer_t        *peer, *best;
  468.     ngx_http_upstream_chash_point_t    *point;
  469.     ngx_http_upstream_chash_points_t   *points;
  470.     ngx_http_upstream_hash_srv_conf_t  *hcf;

  472.     ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
  473.                    "get consistent hash peer, try: %ui", pc->tries);

  475.     pc->cached = 0;
  476.     pc->connection = NULL;

  478.     now = ngx_time();
  479.     hcf = hp->conf;

  481.     points = hcf->points;
  482.     point = &points->point[0];

  484.     for ( ;; ) {
  485.         server = point[hp->hash % points->number].server;

  487.         ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
  488.                        "consistent hash peer:%uD, server:\"%V\"",
  489.                        hp->hash, server);

  491.         best = NULL;
  492.         total = 0;

  494.         for (i = 0; i < hp->rrp.peers->number; i++) {

  496.             n = i / (8 * sizeof(uintptr_t));
  497.             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

  499.             if (hp->rrp.tried[n] & m) {
  500.                 continue;
  501.             }

  503.             peer = &hp->rrp.peers->peer[i];

  505.             if (peer->down) {
  506.                 continue;
  507.             }

  509.             if (peer->server.len != server->len
  510.                 || ngx_strncmp(peer->server.data, server->data, server->len)
  511.                    != 0)
  512.             {
  513.                 continue;
  514.             }

  516.             if (peer->max_fails
  517.                 && peer->fails >= peer->max_fails
  518.                 && now - peer->checked <= peer->fail_timeout)
  519.             {
  520.                 continue;
  521.             }

  523.             peer->current_weight += peer->effective_weight;
  524.             total += peer->effective_weight;

  526.             if (peer->effective_weight < peer->weight) {
  527.                 peer->effective_weight++;
  528.             }

  530.             if (best == NULL || peer->current_weight > best->current_weight) {
  531.                 best = peer;
  532.             }
  533.         }

  535.         if (best) {
  536.             best->current_weight -= total;

  538.             i = best - &hp->rrp.peers->peer[0];

  540.             hp->rrp.current = i;

  542.             n = i / (8 * sizeof(uintptr_t));
  543.             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

  545.             hp->rrp.tried[n] |= m;

  547.             if (now - best->checked > best->fail_timeout) {
  548.                 best->checked = now;
  549.             }

  551.             pc->sockaddr = best->sockaddr;
  552.             pc->socklen = best->socklen;
  553.             pc->name = &best->name;

  555.             return NGX_OK;
  556.         }

  558.         hp->hash++;
  559.         hp->tries++;

  561.         if (hp->tries >= points->number) {
  562.             return NGX_BUSY;
  563.         }
  564.     }
  565. }


  568. static void *
  569. ‌ngx_http_upstream_hash_create_conf(ngx_conf_t *cf)
  570. {
  571.     ngx_http_upstream_hash_srv_conf_t  *conf;

  573.     conf = ngx_palloc(cf->pool, sizeof(ngx_http_upstream_hash_srv_conf_t));
  574.     if (conf == NULL) {
  575.         return NULL;
  576.     }

  578.     conf->points = NULL;

  580.     return conf;
  581. }


  584. static char *
  585. ‌ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
  586. {
  587.     ngx_http_upstream_hash_srv_conf_t  *hcf = conf;

  589.     ngx_str_t                         *value;
  590.     ngx_http_upstream_srv_conf_t      *uscf;
  591.     ngx_http_compile_complex_value_t   ccv;

  593.     value = cf->args->elts;

  595.     ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));

  597.     ccv.cf = cf;
  598.     ccv.value = &value[1];
  599.     ccv.complex_value = &hcf->key;

  601.     if (ngx_http_compile_complex_value(&ccv) != NGX_OK) {
  602.         return NGX_CONF_ERROR;
  603.     }

  605.     uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);

  607.     if (uscf->peer.init_upstream) {
  608.         ngx_conf_log_error(NGX_LOG_WARN, cf, 0,
  609.                            "load balancing method redefined");
  610.     }

  612.     uscf->flags = NGX_HTTP_UPSTREAM_CREATE
  613.                   |NGX_HTTP_UPSTREAM_WEIGHT
  614.                   |NGX_HTTP_UPSTREAM_MAX_FAILS
  615.                   |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
  616.                   |NGX_HTTP_UPSTREAM_DOWN;

  618.     if (cf->args->nelts == 2) {
  619.         uscf->peer.init_upstream = ngx_http_upstream_init_hash;

  621.     } else if (ngx_strcmp(value[2].data, "consistent") == 0) {
  622.         uscf->peer.init_upstream = ngx_http_upstream_init_chash;

  624.     } else {
  625.         ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
  626.                            "invalid parameter \"%V\"", &value[2]);
  627.         return NGX_CONF_ERROR;
  628.     }

  630.     return NGX_CONF_OK;
  631. }

One Level Up Top Level