深入浅出Nginx 负载均衡算法篇

Posted by HHP on October 14, 2019

前言

Nginx是一个高性能HTTP和反向代理web服务器。相比较于Apache,Nginx有轻量级、抗并发(Nginx 处理请求是异步非阻塞的,而Apache 则是阻塞型的,在高并发下Nginx 能保持低资源低消耗高性能、高度模块化的设计,编写模块相对简单的优点。所以现在使用Nginx的人越来越多了。

负载均衡(load balance)是处理高并发的一个常用手段,是一种将流量分配到不同后端服务器的技术。Nginx除了上面所说是一个好的HTTP和反向代理web服务器之外,还是一个很好的负载均衡器。我目前的工作就是做Nginx相关的负载均衡,下面给大家介绍一下原生Nginx里面的几种不同的负载均衡算法以及阿里巴巴tengine团队自研的一种新的负载均衡算法vnswrr

正文

平滑加权轮询(smooth weighted round robin)

round robin是用户使用最多的一种负载均衡策略,它的基本思路很简单,就是将用户的请求逐一的分配到不同的后端服务器。Nginx的轮询机制完整来讲叫平滑加权轮询(smooth weighted round robin),简称swrr。在配置文件里如果不写明确的负载均衡策略,Nginx默认就是使用swrr的。

举个例子说明一下swrr的机制和原理。

假设配置文件中的upstream块是这样写的:

upstream backend {

    server a weight=3;

    server b weight=2;

    server c weight=1;

}

按照这个配置,每6个客户端请求中,a会被选中3次、b会被选中2次、c会被选中1次,且分布平滑,即按如下的顺序分配请求:{a,b,a,c,b,a}。

这个算法中有三个重要的参数:

  • weight

    配置文件中指定的该后端的权重,这个值是固定不变的。

  • effective_weight

    后端的有效权重,初始值为weight。在释放后端时,如果发现和后端的通信过程中发生了错误,就减小effective_weight。此后有新的请求过来时,在选取后端的过程中,再逐步增加effective_weight,最终又恢复到weight。之所以增加这个字段,是为了当后端发生错误时,降低其权重。

  • current_weight

    后端目前的权重,一开始为0,之后会动态调整。那么是怎么个动态调整呢?每次选取后端时,会遍历集群中所有后端,对于每个后端,让它的current_weight增加它的effective_weight,同时累加所有后端的effective_weight,保存为total。如果该后端的current_weight是最大的,就选定这个后端,然后把它的current_weight减去total。如果该后端没有被选定,那么current_weight不用减小。

这个算法思路是这样:

  1. 对于每个请求,遍历集群中的所有可用后端,对于每个后端peer执行:

    peer->current_weight += peer->effecitve_weight

    同时累加所有peer的effective_weight,保存为total。

  2. 从集群中选出current_weight最大的peer,作为本次选定的后端

  3. 对于本次选定的后端,执行:peer->current_weight -= total

因为是轮询,所以这个算法的时间复杂度是O(n),轮询的维度是http请求,不是tcp连接。

我们根据这样的思路来简单验证一下:

根据上面所说,我们a,b,c三个upstream的初始current_weight都为{0,0,0},假设后端不发生错误。

序号 current_weight before selected select peer current_weight after selected
0 {0,0,0}    
1 {3,2,1} a {-3,2,1}
2 {0,4,2} b {0,-2,2}
3 {3,0,3} a {-3,0,3}
4 {0,2,4} c {0,2,-2}
5 {3,4,-1} b {3,-2,-1}
6 {6,0,0} a {0,0,0}

可以看到,在经过6次循环之后,三个后端的current_weight都变为零,即原始状态了。说明这个算法确实平滑轮询。

下面看一下nginx源码相关的函数和结构体:

  • ngx_http_upstream_rr_peer_t:

    每一个后端peer都由一个ngx_http_upstream_rr_peer_t结构体进行管理:

    struct ngx_http_upstream_rr_peer_s {
      
        struct sockaddr *sockaddr; /* 后端服务器的地址 */
        socklen_t socklen; /* 地址的长度*/
        ngx_str_t name; /* 后端服务器地址的字符串,server.addrs[i].name */
        ngx_str_t server; /* server的名称,server.name */
           
        ngx_int_t current_weight; /* 当前的权重,动态调整,初始值为0 */
        ngx_int_t effective_weight; /* 有效的权重,会因为失败而降低 */
        ngx_int_t weight; /* 配置项指定的权重,固定值 */
       
        ngx_uint_t conns; /* 当前连接数 */
       
        ngx_uint_t fails; /* "一段时间内",已经失败的次数 */
        time_t accessed; /* 最近一次失败的时间点 */
        time_t checked; /* 用于检查是否超过了"一段时间" */
       
        ngx_uint_t max_fails; /* "一段时间内",最大的失败次数,固定值 */
        time_t fail_timeout; /* "一段时间"的值,固定值 */
        ngx_uint_t down; /* 服务器永久不可用的标志 */
        ...
        ngx_http_upstream_rr_peer_t *next; /* 指向下一个后端,用于构成链表 */
      
        NGX_COMPAT_BEGIN(32)
        NGX_COMPAT_END
    };
    
  • ngx_http_upstream_rr_peers_t结构体:

    struct ngx_http_upstream_rr_peers_s {
        ngx_uint_t number; /* 后端服务器的数量 */
        ...
        ngx_uint_t total_weight; /* 所有后端服务器权重的累加值 */
       
        unsigned single:1; /* 是否只有一台后端服务器 */
        unsigned weighted:1; /* 是否使用权重 */
       
        ngx_str_t *name; /* upstream配置块的名称 */
       
        ngx_http_upstream_rr_peers_t *next; /* backup服务器集群 */
        ngx_http_upstream_rr_peer_t *peer; /* 后端服务器组成的链表 */
    };
      
    
  • ngx_http_upstream_rr_peer_data_t:

    typedef struct {
         ngx_http_upstream_rr_peers_t *peers; /* 后端集群 */
         ngx_http_upstream_rr_peer_t *current; /* 当前使用的后端服务器 */
         uintptr_t *tried; /* 指向后端服务器的位图 */
         uintptr_t data; /* 当后端服务器的数量较少时,用于存放其位图 */
    } ngx_http_upstream_rr_peer_data_t;
    
  • ngx_http_upstream_init_main_conf

    在解析完http块的配置之后,就会调用这个函数来进行每个upstrem块的调度算法选择。

    ngx_http_upstream_init_main_conf(ngx_conf_t *cf, void *conf)
    {
      ngx_http_upstream_main_conf_t  *umcf = conf;
    
      ngx_uint_t                      i;
      ngx_array_t                     headers_in;
      ngx_hash_key_t                 *hk;
      ngx_hash_init_t                 hash;
      ngx_http_upstream_init_pt       init;
      ngx_http_upstream_header_t     *header;
      ngx_http_upstream_srv_conf_t  **uscfp;
    
      uscfp = umcf->upstreams.elts;
    
      for (i = 0; i < umcf->upstreams.nelts; i++) {
          /* 在这里进行判断,若没有调度算法的选择,则使用swrr*/
          init = uscfp[i]->peer.init_upstream ? uscfp[i]->peer.init_upstream:
                                              ngx_http_upstream_init_round_robin;
          /* 执行上面选择的函数*/
          if (init(cf, uscfp[i]) != NGX_OK) {
              return NGX_CONF_ERROR;
          }
      }
      ...
     }
    
  • ngx_http_upstream_init_round_robin函数:

      ngx_int_t
      ngx_http_upstream_init_round_robin(ngx_conf_t *cf,
          ngx_http_upstream_srv_conf_t *us)
      {
          ngx_url_t                      u;
          ngx_uint_t                     i, j, n, w;
          ngx_http_upstream_server_t    *server;
          ngx_http_upstream_rr_peer_t   *peer, **peerp;
          ngx_http_upstream_rr_peers_t  *peers, *backup;
    
          /*ngx_http_upstream_init_request函数里会回调这个函数*/
          us->peer.init = ngx_http_upstream_init_round_robin_peer;
          /*对一个upstream块里的servers进行初始化*/
          if (us->servers) {
              server = us->servers->elts;
    
              n = 0;/* 总的servers数 */
              w = 0;/* total_weight */
    
              for (i = 0; i < us->servers->nelts; i++) {
                  if (server[i].backup) {
                      continue;
                  }
    
                  n += server[i].naddrs;
                  w += server[i].naddrs * server[i].weight;
              }
    
              if (n == 0) {
                  ngx_log_error(NGX_LOG_EMERG, cf->log, 0,
                                "no servers in upstream \"%V\" in %s:%ui",
                                &us->host, us->file_name, us->line);
                  return NGX_ERROR;
              }
    
              peers = ngx_pcalloc(cf->pool, sizeof(ngx_http_upstream_rr_peers_t));
              if (peers == NULL) {
                  return NGX_ERROR;
              }
    
              peer = ngx_pcalloc(cf->pool, sizeof(ngx_http_upstream_rr_peer_t) * n);
              if (peer == NULL) {
                  return NGX_ERROR;
              }
    
              peers->single = (n == 1);
              peers->number = n;
              peers->weighted = (w != n);
              peers->total_weight = w;
              peers->name = &us->host;
    
              n = 0;
              peerp = &peers->peer;
              /*在for循环里将server数组的值一个个复制到peer数值里*/
              for (i = 0; i < us->servers->nelts; i++) {
                  if (server[i].backup) {
                      continue;
                  }
    
                  for (j = 0; j < server[i].naddrs; j++) {
                      peer[n].sockaddr = server[i].addrs[j].sockaddr;
                      peer[n].socklen = server[i].addrs[j].socklen;
                      peer[n].name = server[i].addrs[j].name;
                      peer[n].weight = server[i].weight;
                      peer[n].effective_weight = server[i].weight;
                      peer[n].current_weight = 0;
                      peer[n].max_conns = server[i].max_conns;
                      peer[n].max_fails = server[i].max_fails;
                      peer[n].fail_timeout = server[i].fail_timeout;
                      peer[n].down = server[i].down;
                      peer[n].server = server[i].name;
    
      #if (NGX_HTTP_UPSTREAM_CHECK)
                      if (!server[i].down) {
                          peer[n].check_index =
                              ngx_http_upstream_check_add_peer(cf, us, &server[i].addrs[j]);
                      } else {
                          peer[n].check_index = (ngx_uint_t) NGX_ERROR;
                      }
      #endif
    
                      *peerp = &peer[n];
                      peerp = &peer[n].next;
                      n++;
                  }
              }
              /*保存指针*/
              us->peer.data = peers;
    
              /* backup servers */
    
              ...
    
          /* implicitly defined upstream has no backup servers */
    
          return NGX_OK;
      }
    
  • ngx_http_upstream_init_round_robin_peer:

    ngx_http_upstream_init_round_robin执行完之后,在ngx_http_upstream_init_request函数里执行这个回调。

    ngx_int_t
    ngx_http_upstream_init_round_robin_peer(ngx_http_request_t *r,
        ngx_http_upstream_srv_conf_t *us)
    {
        ngx_uint_t                         n;
        ngx_http_upstream_rr_peer_data_t  *rrp;
      
        rrp = r->upstream->peer.data;
        /*一般初始情况下rrp都为NULL*/
        if (rrp == NULL) {
            rrp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_rr_peer_data_t));
            if (rrp == NULL) {
                return NGX_ERROR;
            }
      		
            r->upstream->peer.data = rrp;
        }
          
    	/*将对应的upstream组挂载到 rrp->peers,关键!*/
        rrp->peers = us->peer.data;
        rrp->current = NULL;
        rrp->config = 0;
      	
        n = rrp->peers->number;
    	/*若多个相同名字的upstream块分开写,则找到最后解析的那个upstream块,里面记录的number是这些upstream块的总peer数*/
        if (rrp->peers->next && rrp->peers->next->number > n) {
            n = rrp->peers->next->number;
        }
          
    	/*如果peers数小于等于64(因为uintptr_t是64位unsigned long),直接将rrp->data的地址赋值给rrp->tried这个位图*/
        if (n <= 8 * sizeof(uintptr_t)) {
            rrp->tried = &rrp->data;
            rrp->data = 0;
    	/*当peers数大于64就开辟新的空间*/
        } else {
            n = (n + (8 * sizeof(uintptr_t) - 1)) / (8 * sizeof(uintptr_t));
      
            rrp->tried = ngx_pcalloc(r->pool, n * sizeof(uintptr_t));
            if (rrp->tried == NULL) {
                return NGX_ERROR;
            }
        }
      
        /*其中peer.get最为重要,在ngx_event_connect_peer
    函数里回调,实现的调度算法就在这个函数里面*/
        r->upstream->peer.get = ngx_http_upstream_get_round_robin_peer;
        /*free request的时候就会执行这个函数free掉内存*/
        r->upstream->peer.free = ngx_http_upstream_free_round_robin_peer;
        /*设置 ngx_peer_connection_t 结构体中 tries 重试连接的次数为非备用后端服务器的个数*/
        r->upstream->peer.tries = ngx_http_upstream_tries(rrp->peers);
    #if (NGX_HTTP_SSL)
        r->upstream->peer.set_session =
                                   ngx_http_upstream_set_round_robin_peer_session;
        r->upstream->peer.save_session =
                                   ngx_http_upstream_save_round_robin_peer_session;
    #endif
      
        return NGX_OK;
    }
    
  • ngx_http_upstream_get_round_robin_peer

    /* 选择一个后端服务器来处理请求 */
    ngx_int_t
    ngx_http_upstream_get_round_robin_peer(ngx_peer_connection_t *pc, void *data)
    {
        ngx_http_upstream_rr_peer_data_t  *rrp = data;
      
        ngx_int_t                      rc;
        ngx_uint_t                     i, n;
        ngx_http_upstream_rr_peer_t   *peer;
        ngx_http_upstream_rr_peers_t  *peers;
      
        ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get rr peer, try: %ui", pc->tries);
      
        /* ngx_lock_mutex(rrp->peers->mutex); */
      
        pc->cached = 0;
        pc->connection = NULL;
      
        /*
         * 检查 ngx_http_upstream_rr_peers_t 结构体中的 single 标志位;
         * 若 single 标志位为 1,表示只有一台非备用后端服务器,
         * 接着检查该非备用后端服务器的 down 标志位,若 down 标志位为 0,则选择该非备用后端服务器来处理请求;
         * 若 down 标志位为 1, 该非备用后端服务器表示不参与策略选择,
         * 则跳至 goto failed 步骤从备用后端服务器列表中选择后端服务器来处理请求;
         */
        if (rrp->peers->single) {
            peer = &rrp->peers->peer[0];
      
            if (peer->down) {
                goto failed;
            }
      
        } else {/* 若 single 标志位为 0,表示不止一台非备用后端服务器 */
      
            /* there are several peers */
      
            /* 根据非备用后端服务器的权重来选择一台后端服务器处理请求 */
            peer = ngx_http_upstream_get_peer(rrp);
      
            if (peer == NULL) {
                /*
                 * 若从非备用后端服务器列表中没有选择一台合适的后端服务器处理请求,
                 * 则 goto failed 从备用后端服务器列表中选择一台后端服务器来处理请求;
                 */
                goto failed;
            }
      
            ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                           "get rr peer, current: %ui %i",
                           rrp->current, peer->current_weight);
        }
      
        /*
         * 若从非备用后端服务器列表中已经选到了一台合适的后端服务器处理请求;
         * 则获取该后端服务器的地址信息;
         */
        pc->sockaddr = peer->sockaddr;/* 获取被选中的非备用后端服务器的地址 */
        pc->socklen = peer->socklen;/* 获取被选中的非备用后端服务器的地址长度 */
        pc->name = &peer->name;/* 获取被选中的非备用后端服务器的域名 */
      
        /* ngx_unlock_mutex(rrp->peers->mutex); */
      
        /*
         * 检查被选中的非备用后端服务器重试连接的次数为 1,且存在备用后端服务器列表,
         * 则将该非备用后端服务器重试连接的次数设置为 备用后端服务器个数加 1;
         * 否则不用重新设置;
         */
        if (pc->tries == 1 && rrp->peers->next) {
            pc->tries += rrp->peers->next->number;
        }
      
        /* 到此,表示已经选择到了一台合适的非备用后端服务器来处理请求,则成功返回 */
        return NGX_OK;
      
    failed:
          /*
           * 若从非备用后端服务器列表中没有选择到后端服务器处理请求,
           * 若存在备用后端服务器,则从备用后端服务器列表中选择一台后端服务器来处理请求;
           */
      
        peers = rrp->peers;
      
        /* 若存在备用后端服务器,则从备用后端服务器列表中选择一台后端服务器来处理请求;*/
        if (peers->next) {
      
            /* ngx_unlock_mutex(peers->mutex); */
      
            ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0, "backup servers");
      
            /* 获取备用后端服务器列表 */
            rrp->peers = peers->next;
            /* 把后端服务器重试连接的次数 tries 设置为备用后端服务器个数 number */
            pc->tries = rrp->peers->number;
      
            /* 计算备用后端服务器在位图中的位置 n */
            n = (rrp->peers->number + (8 * sizeof(uintptr_t) - 1))
                    / (8 * sizeof(uintptr_t));
      
            /* 初始化备用后端服务器在位图 rrp->tried[i] 中的值为 0 */
            for (i = 0; i < n; i++) {
                 rrp->tried[i] = 0;
            }
      
            /* 把备用后端服务器列表当前非备用后端服务器列表递归调用 ngx_http_upstream_get_round_robin_peer 选择一台后端服务器 */
            rc = ngx_http_upstream_get_round_robin_peer(pc, rrp);
      
            /* 若选择成功则返回 */
            if (rc != NGX_BUSY) {
                return rc;
            }
      
            /* ngx_lock_mutex(peers->mutex); */
        }
      
        /*
         * 若从备用后端服务器列表中也没有选择到一台后端服务器处理请求,
         * 则重新设置非备用后端服务器连接失败的次数 fails 为 0 ,以便重新被选择;
         */
        /* all peers failed, mark them as live for quick recovery */
      
        for (i = 0; i < peers->number; i++) {
            peers->peer[i].fails = 0;
        }
      
        /* ngx_unlock_mutex(peers->mutex); */
      
        pc->name = peers->name;
      
        /* 选择失败,则返回 */
        return NGX_BUSY;
    }
    
  • ngx_http_upstream_get_peer:

    这个函数是实现算法的关键,下面介绍一下实现流程:

    • for 循环遍历后端服务器列表,计算当前后端服务器在位图 tried 中的位置 n,判断当前服务器是否在位图中记录过,若已经记录过,则 continue 继续检查下一个后端服务器;若没有记录过则继续当前后端服务器检查;
    • 检查当前后端服务器的标志位 down,若该标志位为 1,表示该后端服务器不参与选择策略,则 continue 继续检查下一个后端服务器;若该标志位为 0,继续当前后端服务器的检查;
    • 若当前后端服务器的连接失败次数已到达 max_failes,且睡眠时间还没到 fail_timedout ,则 continue 继续检查下一个后端服务器;否则继续当前后端服务器的检查;
    • 计算当前后端服务器的权重,设置当前后端服务器的权重 current_weight 的值为原始值加上 effective_weight;设置总的权重 total 为原始值加上 effective_weight;
    • 判断当前后端服务器是否异常,若 effective_weight 小于 weight,表示正常,则调整 effective_weight 的值 effective_weight++;
    • 根据权重在后端服务器列表中选择权重最高的后端服务器 best;
    • 计算被选中后端服务器在服务器列表中的值为 i,记录被选中后端服务器在 ngx_http_upstream_rr_peer_data_t 结构体 current 成员的值,在释放后端服务器时会用到该值;
    • 计算被选中后端服务器在位图中的位置 n,并在该位置记录 best 后端服务器已经被选中过;
    • 更新被选中后端服务器的权重,并返回被选中的后端服务器 best;
     /* 根据后端服务器的权重来选择一台后端服务器处理请求 */
    static ngx_http_upstream_rr_peer_t *
    ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
    {
        time_t                        now;
        uintptr_t                     m;
        ngx_int_t                     total;
        ngx_uint_t                    i, n;
        ngx_http_upstream_rr_peer_t  *peer, *best;
      
        now = ngx_time();
      
        best = NULL;
        total = 0;
      
        /* 遍历后端服务器列表 */
        for (i = 0; i < rrp->peers->number; i++) {
      
            /* 计算当前后端服务器在位图中的位置 n */
            n = i / (8 * sizeof(uintptr_t));
            m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
      
            /* 当前后端服务器在位图中已经有记录,则不再次被选择,即 continue 检查下一个后端服务器 */
            if (rrp->tried[n] & m) {
                continue;
            }
      
            /* 若当前后端服务器在位图中没有记录,则可能被选中,接着计算其权重 */
            peer = &rrp->peers->peer[i];
      
            /* 检查当前后端服务器的 down 标志位,若为 1 表示不参与策略选择,则 continue 检查下一个后端服务器 */
            if (peer->down) {
                continue;
            }
      
            /*
             * 当前后端服务器的 down 标志位为 0,接着检查当前后端服务器连接失败的次数是否已经达到 max_fails;
             * 且睡眠的时间还没到 fail_timeout,则当前后端服务器不被选择,continue 检查下一个后端服务器;
             */
            if (peer->max_fails
                && peer->fails >= peer->max_fails
                && now - peer->checked <= peer->fail_timeout)
            {
                continue;
            }
      
            /* 若当前后端服务器可能被选中,则计算其权重 */
      
            /*
             * 在上面初始化过程中 current_weight = 0,effective_weight = weight;
             * 此时,设置当前后端服务器的权重 current_weight 的值为原始值加上 effective_weight;
             * 设置总的权重为原始值加上 effective_weight;
             */
            peer->current_weight += peer->effective_weight;
            total += peer->effective_weight;
      
            /* 服务器正常,调整 effective_weight 的值 */
            if (peer->effective_weight < peer->weight) {
                peer->effective_weight++;
            }
      
            /* 若当前后端服务器的权重 current_weight 大于目前 best 服务器的权重,则当前后端服务器被选中 */
            if (best == NULL || peer->current_weight > best->current_weight) {
                best = peer;
            }
        }
      
        if (best == NULL) {
            return NULL;
        }
      
        /* 计算被选中后端服务器在服务器列表中的位置 i */
        i = best - &rrp->peers->peer[0];
      
        /* 记录被选中后端服务器在 ngx_http_upstream_rr_peer_data_t 结构体 current 成员的值,在释放后端服务器时会用到该值 */
        rrp->current = i;
      
        /* 计算被选中后端服务器在位图中的位置 */
        n = i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
      
        /* 在位图相应的位置记录被选中后端服务器 */
        rrp->tried[n] |= m;
      
        /* 更新被选中后端服务器的权重 */
        best->current_weight -= total;
      
        if (now - best->checked > best->fail_timeout) {
            best->checked = now;
        }
      
        /* 返回被选中的后端服务器 */
        return best;
    }
    

IP哈希(IP hash)

ip哈希顾名思义就是将客户端的ip进行哈希,然后根据哈希值来选择后端real server。ip哈希能保证同一个客户端ip的请求能落到同一台后端机器。ip哈希的应用场景主要是在分布式缓存。在nginx里,ip哈希是带权重的,是使用了上面的roundrobin函数进行了一部份初始化,带权重的意思是在ip hash完成得到hash值之后,再根据权重计算一波,最后才决定将该请求发送到哪一台后端机器。由于同一个ip哈希得到的值和后端的权重是固定的,所以同一个ip落到哪一台后端机器都是唯一确定的。

Nginx 使用 IP 哈希负载均衡策略时,在进行策略选择之前由 ngx_http_upstream_init_ip_hash 函数进行全局初始化工作,其实该函数也是调用加权轮询策略的全局初始化函数。当一个客户端请求过来时,Nginx 将调用 ngx_http_upstream_init_ip_hash_peer() 为选择后端服务器处理该请求做初始化工作。

ngx_http_upstream_get_ip_hash_peer 函数会在选择后端服务器时计算客户端请求 IP 地址的哈希值,并利用哈希值,再根据权重计算一波,最后才决定将该请求发送到哪一台后端机器。得到被选中的后端服务器,判断其是否可用,如果可用则保存服务器地址,若不可用则在上次哈希选择结果基础上再次进行哈希选择。如果哈希选择失败次数达到 20 次以上,此时回退到采用轮询策略进行选择。

由于ngx_http_upstream_init_ip_hash函数和ngx_http_upstream_init_ip_hash_peer函数基本上是调用roundrobin函数和做一些简单的初始化,和上面分析roundrobin的情况大致相同,这里就不讲解这两个函数了。直接讲核心函数ngx_http_upstream_get_ip_hash_peer()。 这个函数同样是在ngx_int_t ngx_event_connect_peer(ngx_peer_connection_t *pc)里面被回调:

static ngx_int_t
ngx_http_upstream_get_ip_hash_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_ip_hash_peer_data_t  *iphp = data;

    time_t                        now;
    ngx_int_t                     w;
    uintptr_t                     m;
    ngx_uint_t                    i, n, p, hash;
    ngx_http_upstream_rr_peer_t  *peer;

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

    /* TODO: cached */

    ngx_http_upstream_rr_peers_wlock(iphp->rrp.peers);
	/* 如果同一请求尝试后端的次数超过20次,或者这个upstream块只有一个real server,则退化成使用round robin算法获取upstream */
    if (iphp->tries > 20 || iphp->rrp.peers->single) {
        ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);
        return iphp->get_rr_peer(pc, &iphp->rrp);
    }

    now = ngx_time();

    pc->cached = 0;
    pc->connection = NULL;
	/* 起始值为零 ,若出重新选择的情况,则这个值不为零,而是上次所选择的peer的hash值 */
    hash = iphp->hash;

    for ( ;; ) {
		/* 运行哈希函数,根据IP值计算出hash值 */
        for (i = 0; i < (ngx_uint_t) iphp->addrlen; i++) {
            hash = (hash * 113 + iphp->addr[i]) % 6271;
        }
        
		/* 根据peer各自的权重,利用上面获得的hash值进行计算,最后获知将请求分配到拿一台机器上面。对于同一个client IP而言,每次分配到的后端机器都是一样的,因为这里的权重其实是针对IP或者说是IP的哈希值来分配的。*/
        w = hash % iphp->rrp.peers->total_weight;
        peer = iphp->rrp.peers->peer;
        p = 0;

        while (w >= peer->weight) {
            w -= peer->weight;
            peer = peer->next;
            p++;
        }
        
		/* 获取peer在tried位图中的位置 */
        n = p / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
        
		/* 若在位图中发现选中的peer,则跳转到next,重新分配peer。*/
        if (iphp->rrp.tried[n] & m) {
            goto next;
        }

        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get ip hash peer, hash: %ui %04XL", p, (uint64_t) m);
        
		/* 若peer标记为down,也进行peer的重新选择 */
        if (peer->down) {
            goto next;
        }

#if (NGX_HTTP_UPSTREAM_CHECK)
        ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
            "get ip_hash peer, check_index: %ui",
             peer->check_index);
        if (ngx_http_upstream_check_peer_down(peer->check_index)) {
            goto next;
        }
#endif

        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            goto next;
        }

        if (peer->max_conns && peer->conns >= peer->max_conns) {
            goto next;
        }

        break;

    next:
		/* 若tries次数大于20次 ,则使用轮询算法 */
        if (++iphp->tries > 20) {
            ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);
            return iphp->get_rr_peer(pc, &iphp->rrp);
        }
    }

    iphp->rrp.current = peer;

    pc->sockaddr = peer->sockaddr;
    pc->socklen = peer->socklen;
    pc->name = &peer->name;

    peer->conns++;

    if (now - peer->checked > peer->fail_timeout) {
        peer->checked = now;
    }

    ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);
	/* 在tried位图中记录在本次请求中该peer已经被选择过,若出现connect失败等问题需要从新选择时,不会再选择这个peer */
    iphp->rrp.tried[n] |= m;
    iphp->hash = hash;

    return NGX_OK;
}

一致性哈希(consistant hash)

除了普通的ip哈希,nginx还提供一种一致性哈希的负载均衡算法。一致性哈希相比于普通的ip哈希来说,多了虚拟节点这个概念,实现的效果的话,理论上来讲,因为多了虚拟节点的概念,所以更加灵活。当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。

参考别人写的一个例子说明一下一致性哈希的好处:

假设后端集群包含三台缓存服务器,A、B、C。

请求r1、r2落在A上。

请求r3、r4落在B上。

请求r5、r6落在C上。

使用一致性哈希时,当缓存服务器B宕机时,r1/r2会仍然落在A上,r5/r6会仍然落在C上,

也就是说这两台服务器上的缓存都不会失效。r3/r4会被重新分配给A或者C,并产生回源。

使用其它算法,当缓存服务器B宕机时,r1/r2不再落在A上,r5/r6不再落在C上了。

也就是说A、B、C上的缓存都失效了,所有的请求都要回源。

nginx的普通的ip_hash算法,若需要增减upstream的数量然后reload,之前的请求就全部落到不同的机器上了。而用了一致性哈希后,增减机器然后reload,只会造成有小部分请求不能落到原来的机器上

使用一致性哈希的时候,我们一般会这样写配置 hash $host$uri consistent; ,这个配置说明使用的负载均衡算法为一致性哈希算法。

nginx实现的一致性哈希算法中,比较关键的几个点如下:

1、真实节点和虚拟节点是独立的。其中真实节点是用round robin来进行初始化的。虚拟节点的数量是根据权重值来决定的, niginx里,虚拟节点的个数为total_weight * 160。

2、一个真实节点对应 weight * 160 个虚拟节点。

3、一个虚拟节点里面包含两个变量分别是uint32_t hashngx_str_t serverhash是当前节点的哈希值,server是 server指令的第一个参数,就是HOST和PORT。

4、 每个虚拟节点的hash值都不同。

5、创建好虚拟节点之后,会根据每个虚拟节点的哈希值大小来进行排序,对于hash值相同的虚拟节点,只保留第一个。

经过上述步骤,我们得到一个所有虚拟节点组成的数组,其元素的hash值有序而不重复。也就是说,整个哈希环建立起来了。(严格来说他不是环,只是一个有序数组)

​ 虚拟节点数组图

  • 重要的数据结构

    typedef struct {
        uint32_t hash; /* 虚拟节点的哈希值 */
        ngx_str_t *server; /* 虚拟节点归属的真实节点,对应真实节点的server成员 */
    } ngx_http_upstream_chash_point_t;
      
    typedef struct {
        ngx_uint_t number; /* 虚拟节点的个数 */
        ngx_http_upstream_chash_point_t point[1]; /* 虚拟节点的数组 */
    } ngx_http_upstream_chash_points_t;
      
    typedef struct {
        ngx_http_complex_value_t key; /* 关联hash指令的第一个参数,用于计算请求的hash值 */
        ngx_http_upstream_chash_points_t *points; /* 虚拟节点的数组 */
    } ngx_http_upstream_chash_points_t;
    
  • 相关函数

    /* 配置初始化时调用 */
    static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)
    {
        u_char *host, *port, c;
        size_t host_len, port_len, size;
        uint32_t hash, base_hash;
        ngx_str_t *server;
        ngx_uint_t npoints, i, j;
        ngx_http_upstream_rr_peer_t *peer;
        ngx_http_upstream_rr_peers_t *peers;
        ngx_http_upstream_chash_points_t *points;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        union {
            uint32_t value;
            u_char byte[4];
        } prev_hash;
      
        /* 使用round robin的upstream块初始化函数,创建和初始化真实节点 */
        if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK)
            return NGX_ERROR:
      
        /* 重新设置per request的负载均衡初始化函数 */
        us->peer.init = ngx_http_upstream_init_chash_peer;
      
        peers = us->peer.data; /* 真实节点的集群 */
        npoints = peers->total_weight * 160;
      
        /* 一共创建npoints个虚拟节点 ,npoints - 1是因为ngx_http_upstream_chash_points_t里已经包含了一个ngx_http_upstream_chash_point_t*/
        size = sizeof(ngx_http_upstream_chash_points_t) + 
            sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);
      
        points = ngx_palloc(cf->pool, size);
        if (points == NULL)
            return NGX_ERROR;
      
        points->number = 0;
      
        /* 初始化所有的虚拟节点 */
        for (peer = peers->peer; peer; peer = peer->next) {
            server = &peer->server; /* server指令的第一个参数, server.name */
              
            /* Hash expression is compatible with Cache::Memcached::Fast:
             * crc32(HOST 0 PORT PREV_HASH).
             */
            if (server->len >= 5 && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)
            {
                host = server->data + 5;
                host_len = server->len - 5;
                port = NULL;
                port_len = 0;
                goto done;
            }
      
            /* 把每个peer的server成员,解析为HOST和PORT */
            for (j = 0; j < server->len; j++) {
                c = server->data[server->len - j - 1];
      
                if (c == ":") {
                    host = server->data;
                    host_len = server->len - j - 1;
                    port = server->data + server->len - j;
                    port_len = j;
                    goto done;
                }
      
                if (c < '0' || c > '9') /* 表示没有指定端口 */
                    break;
            }
      
            host = server->data;
            host_len = server->len;
            port = NULL;
            port_len = 0;
      
       done:
            /* 根据解析peer的server成员所得的HOST和PORT,计算虚拟节点的base_hash值 */
            ngx_crc32_init(base_hash);
            ngx_crc32_update(&base_hash, host, host_len);
            ngx_crc32_update(&base_hash, (u_char *) "", 1); /* 空字符串包含字符\0 */
            ngx_crc32_update(&base_hash, port, port_len);
              
            /* 对于归属同一个真实节点的虚拟节点,它们的base_hash值相同,而prev_hash不同 */
            prev_hash.value = 0;
            npoints = peer->weight * 160;
      
            for (j = 0; j < npoints; j++) {
                hash = base_hash;
                ngx_crc32_update(&hash, prev_hash.byte, 4);
                ngx_crc32_final(hash);
      
                points->point[points->number].hash = hash; /* 虚拟节点的哈希值 */
                points->point[points->number].server = server; /* 虚拟节点所归属的真实节点,对应真实节点的server成员 */
                points->number++;
      
    #if (NGX_HAVE_LITTLE_ENDIAN)
                /* hash赋值给prev_hash ,供下一个节点使用 */
               prev_hash.value = hash;
    #else
               prev_hash.byte[0] = (u_char) (hash & 0xff);
               prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);
               prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);
               prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);
    #endif
            }   
        }
      
        /* 使用快速排序,使虚拟节点数组的元素,按照其hash值从小到大有序 */
        ngx_qsort(points->point, points->number, sizeof(ngx_http_upstream_chash_point_t),
            ngx_http_upstream_chash_cmp_points);
      
        /* 如果虚拟节点数组中,有多个元素的hash值相同,只保留第一个 */
        for (i = 0, j = 1; j < points->number; j++)
            if (points->point[i].hash != points->point[j].hash)
                points->point[++i] = points->point[j];
      
        /* 经过上述步骤后,虚拟节点数组中的元素,有序而不重复 */
        points->number = i + 1;
         
        hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
        hcf->points = points; /* 保存虚拟节点数组 */
      
        return NGX_OK;
    }
    
    /* 快速排序的比较函数 */
    static int ngx_libc_cdel ngx_http_upstream_chash_cmp_points(const void *one, const void *two)
    {
        ngx_http_upstream_chash_point_t *first = (ngx_http_upstream_chash_point_t *) one;
        ngx_http_upstream_chash_point_t *second = (ngx_http_upstream_chash_point_t *) two;
      
        if (first->hash < second->hash)
            return -1;
        else if (first->hash > second->hash)
            return 1;c
        else
            return 0;
    }
    
    /* 初始化请求调用的函数 */
    static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us)
    {
        uint32_t hash;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        ngx_http_upstream_hash_peer_data_t *hp;
      
        /* 调用hash算法的per request负载均衡初始化函数,创建和初始化请求的负载均衡数据 */
        if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK)
            return NGX_ERROR;
      
        /* 重新指定peer.get,用于选取一个真实节点 */
        r->upstream->peer.get = ngx_http_upstream_get_chash_peer;
      
        hp = r->upstream->peer.data;
        hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);
      
        /* 根据获取的本请求对应的hash指令的第一个参数值,计算请求的hash值 */
        hash = ngx_crc32_long(hp->key.data, hp->key.len);
      
        /* 根据请求的hash值,找到顺时针方向最近的一个虚拟节点,hp->hash记录此虚拟节点
         * 在数组中的索引。
         */
        hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);
      
        return NGX_OK:
    }
    

    ngx_http_upstream_find_chash_point这个函数被上面的ngx_http_upstream_init_chash_peer函数调用,因为虚拟节点本来就是有序的,所以查找最快的方法就是二分查找了:

    static ngx_uint_t ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points, uint32_t hash)
    {
        ngx_uint_t i, j, k;
        ngx_http_upstream_chash_point_t *point;
          
        /* find first point >= hash */
      
        point = &points->point[0];
        i = 0;
        j = points->number;'
      
        while(i < j) {
            k = (i + j) / 2;
      
            if (hash > point[k].hash)
                i = k + 1;
            else if (hash < point[k].hash)
                j = k;
             else
                return k;
        }
    	/*比最大的值还要大,或者比最小的值还要小,则返回最大那个值或者最小那个值*/
        return i;
    }
    

    选取真实节点是调用下面的函数:

    static ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)
    {
        ngx_http_upstream_hash_peer_data_t *hp = data; /* 请求的负载均衡数据 */
        time_t now;
        intptr_t m;
        ngx_str_t *server;
        ngx_int_t total;
        ngx_uint_t i, n, best_i;
        ngx_http_upstream_rr_peer_t *peer, *best;
        ngx_http_upstream_chash_point_t *point;
        ngx_http_upstream_chash_points_t *points;
        ngx_http_upstream_hash_srv_conf_t *hcf;
        ...
        pc->cached = 0;
        pc->connection = NULL:
        now = ngx_time();
        hcf = hp->conf;
        points = hcf->points; /* 虚拟节点数组 */
        point = &points->point[0]; /* 指向第一个虚拟节点 */
      
        for ( ; ; ) {
            /* 在peer.init中,已根据请求的哈希值,找到顺时针方向最近的一个虚拟节点,
             * hash为该虚拟节点在数组中的索引。
             * 一开始hash值肯定小于number,之后每尝试一个虚拟节点后,hash++。取模是为了防止越界访问。
             */
            server = point[hp->hash % points->number].server;
            best = NULL;
            best_i = 0;
            total = 0;
      
            /* 遍历真实节点数组,寻找可用的、该虚拟节点归属的真实节点(server成员相同),
              * 如果有多个真实节点同时符合条件,那么使用轮询来从中选取一个真实节点。
              */
            for (peer = hp->rrp.peers->peer, i = 0; peer; peer = peer->next, i++) {
                /* 检查此真实节点在状态位图中对应的位,为1时表示不可用 */
                n = i / (8 * sizeof(uintptr_t));
                m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
                if (hp->rrp.tried[n] & m)
                    continue;            
      
                /* server指令中携带了down属性,表示后端永久不可用 */
                if (peer->down)
                    continue;
      
                /* 如果真实节点的server成员和虚拟节点的不同,表示虚拟节点不属于此真实节点 */
                if (peer->server.len != server->len || 
                    ngx_strncmp(peer->server.data, server->data, server->len) != 0)
                    continue;
      
               /* 在一段时间内,如果此真实节点的失败次数,超过了允许的最大值,那么不允许使用了 */
               if (peer->max_fails
                    && peer->fails >= peer->max_fails
                    && now - peer->checked <= peer->fail_timeout)
                    continue;
              
                peer->current_weight += peer->effective_weight; /* 对每个真实节点,增加其当前权重 */
                total += peer->effective_weight; /* 累加所有真实节点的有效权重 */
      
                /* 如果之前此真实节点发生了失败,会减小其effective_weight来降低它的权重。          
                 * 此后又通过增加其effective_weight来恢复它的权重。          
                 */        
                if (peer->effective_weight < peer->weight) 
                    peer->effective_weight++;
              
                /* 选取当前权重最大者,作为本次选定的真实节点 */
                if (best == NULL || peer->current_weight > best->current_weight) {
                    best = peer;
                    best_i = i;
                }
            }
      
            /* 如果选定了一个真实节点 */
            if (best) {
                best->current_weight -= total; /* 如果使用了轮询,需要降低选定节点的当前权重 */
                goto found;
            }
      
            hp->hash++; /* 增加虚拟节点的索引,即“沿着顺时针方向” */
            hp->tries++; /* 已经尝试的虚拟节点数 */
      
            /* 如果把所有的虚拟节点都尝试了一遍,还找不到可用的真实节点 */
            if (hp->tries >= points->number)
                return NGX_BUSY;
        }
      
    found: /* 找到了和虚拟节点相对应的、可用的真实节点了 */
        hp->rrp.current = best; /* 选定的真实节点 */
        /* 保存选定的后端服务器的地址,之后会向这个地址发起连接 */
        pc->sockaddr = peer->sockaddr;
        pc->socklen = peer->socklen;
        pc->name = &peer->name;
        best->conns++;
      
        /* 更新checked时间 */
        if (now - best->checked > best->fail_timeout)
            best->checked = now;
    	/* 更新位图 */
        n = best_i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));
      
        /* 对于本次请求,如果之后需要再次选取真实节点,不能再选取同一个了 */    
        hp->rrp->tried[n] |= m;
      
        return NGX_OK;
    }
    

最少连接(least_conn)

这个算法就很好理解了。就是每次选取后端的时候选择活跃连接数最少的那个后端rs来进行请求的分配。如果有多个后端的conns/weight值同为最小的,那么对它们采用加权轮询算法。其中ngx_http_upstream_init_least_connngx_http_upstream_init_least_conn_peer函数很简单,大体上也是调用round robin的函数初始化一下。

下面分析一下ngx_http_upstream_get_least_conn_peer函数:

static ngx_int_t ngx_http_upstream_get_least_conn_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_rr_peer_data_t *rrp = data; /* 请求的负载均衡数据 */
    time_t now;
    uintptr_t m;
    ngx_int_t rc, total;
    ngx_uint_t i, n, p, many;
    ngx_http_upstream_rr_peer_t *peer, *best;
    ngx_http_upstream_rr_peers_t *peers;
    ...
    /* 如果集群只包含一台后端,那么就不用选了 */
    if (rrp->peers->single)
        return ngx_http_upstream_get_round_robin_peer(pc, rrp);

    pc->cached = 0;
    pc->connection = NULL;
    now = ngx_time();
    peers = rrp->peers; /* 后端集群 */
    best = NULL;
    total = 0;
    ...
    /* 遍历后端集群 */
    for (peer = peers->peer, i = 0; peer; peer = peer->next, i++)
    {
        /* 检查此后端在状态位图中对应的位,为1时表示不可用 */ 
        n = i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

        if (rrp->tried[n] & m)
           continue;

        /* server指令中携带了down属性,表示后端永久不可用 */
        if (peer->down)
            continue;

        /* 在一段时间内,如果此后端服务器的失败次数,超过了允许的最大值,那么不允许使用此后端了 */
         if (peer->max_fails && peer->fails >= peer->max_fails
             && now - peer->checked <= peer->fail_timeout)
            continue;

        /* select peer with least number of connections; if there are multiple peers
         * with the same number of connections, select based on round-robin.
         */
        
        /* 比较各个后端的conns/weight,选取最小者;
         * 如果有多个最小者,记录第一个的序号p,且设置many标志。核心关键!!!
         * 其中peer->conns记录这个后端rs的活跃连接数,成功连接之后加一,关闭连接后减一
         */
        if (best == NULL || peer->conns * best->weight < best->conns * peer->weight)
        {
            best = peer;
            many = 0;
            p = i;
        } else if (peer->conns * best->weight == best->conns * peer->weight)
            many = 1;
    }

    /* 找不到可用的后端 */
    if (best == NULL)
        goto failed;

    /* 如果有多个后端的conns/weight同为最小者,则对它们使用轮询算法 */
    if (many) {
        for (peer = best, i = p; peer; peer->peer->next, i++)
        {
            /* 检查此后端在状态位图中对应的位,为1时表示不可用 */ 
            n = i / (8 * sizeof(uintptr_t));
            m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

           /* server指令中携带了down属性,表示后端永久不可用 */
            if (peer->down)
                continue;

           /* conns/weight必须为最小的 */
            if (peer->conns * best->weight != best->conns * peer->weight)
                continue;

           /* 在一段时间内,如果此后端服务器的失败次数,超过了允许的最大值,那么不允许使用此后端了 */
            if (peer->max_fails && peer->fails >= peer->max_fails
                && now - peer->checked <= peer->fail_timeout)
               continue;

            peer->current_weight += peer->effective_weight; /* 对每个后端,增加其当前权重 */
            total += peer->effective_weight; /* 累加所有后端的有效权重 */

           /* 如果之前此后端发生了失败,会减小其effective_weight来降低它的权重。          
              * 此后在选取后端的过程中,又通过增加其effective_weight来恢复它的权重。          
              */        
            if (peer->effective_weight < peer->weight) 
                peer->effective_weight++;
        
            /* 选取当前权重最大者,作为本次选定的后端 */
            if (best == NULL || peer->current_weight > best->current_weight) {
                best = peer;
                p = i;
            }
        }
    }

    best->current_weight -= total; /* 如果使用轮询,要降低选定后端的当前权重 */

    /* 更新checked时间 */
    if (now - best->checked > best->fail_timeout)
         best->checked = now;

    /* 保存选定的后端服务器的地址,之后会向这个地址发起连接 */
    pc->sockaddr = best->sockaddr;
    pc->socklen = best->socklen;
    pc->name = &best->name;

    best->conns++; /* 增加选定后端的当前连接数 */    

    n = p / (8 * sizeof(uintptr_t));
    m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
    rrp->tried[n] |= m; /* 对于此请求,如果之后需要再次选取后端,不能再选取这个后端了 */

    return NGX_OK;

failed:
    /* 如果不能从集群中选取一台后端,那么尝试备用集群 */
    if (peers->next) {
        ...        
        rrp->peers = peers->next;
        n = (rrp->peers->number + (8 * sizeof(uintptr_t) - 1))
                / (8 * sizeof(uintptr_t));
        for (i = 0; i < n; i++)
             rrp->tried[i] = 0;
       
        /* 重新调用本函数 */        
        rc = ngx_http_upstream_get_least_conn_peer(pc, rrp);

        if (rc != NGX_BUSY)
            return rc;
    }

    /* all peers failed, mark them as live for quick recovery */
    for (peer = peers->peer; peer; peer = peer->next) {
        peer->fails = 0;
    }
    pc->name = peers->name;
    return NGX_BUSY;
}

附:虚拟节点平滑加权轮询(virtual node smooth weighted round robin)

这个vnswrr算法不是原生nginx的负载均衡算法,是阿里tengine团队开发的一个新负载均衡算法。这个算法是在前面说的平滑加权轮询(swrr)上的改进版。

这个改进的地方主要有两点:

  • 原生nginx的swrr模块在当nginx reload之后会首先选择weight值最大的那一台后端real server进行转发。这就造成一个问题,reload之后接入层 nignx 都会将第一个请求转发到权重被调高的机器上,造成一开始所有流量都分配到那台权重最大的机器上,导致一开始看起来流量分配并不是按照既定的权重来进行分配。vnswrr采用了随便分配起点的方法,第一个请求不是转发到权重被调高的机器上,而是随机选取一个起点,这样的话流量就会比较均匀。当然,这种效果在接入层nginx实例很多的情况下才会比较明显。

  • 原生nginx的轮询算法的时间复杂度是O(n),而在n,即后端rs比较多的情况下,轮询算法占用的cpu时间是不可忽略的,造成很大的性能瓶颈。vnswrr则是使用了虚拟节点的方式,说白了就是事前把轮询的顺序加载好,每次选取后端的时候直接跳转到下一个rs就好,使得时间复杂度降为O(1)。其实就是一种典型的空间换时间的思想。这个vnswrr算法在upstrem很多的情况下效果非常明显。

算法的关键点有两个:

  • 虚拟节点初始化顺序严格按照 SWRR 算法选取,保证初始化列表里的机器能够分布足够散列;

  • 虚拟节点运行时分批初始化,避免密集型计算集中。每批次虚拟节点使用完后再进行下一批次虚拟节点列表初始化,每次只初始化 min(n, max) 个虚拟节点;

算法描述:

  • 程序启动或者运行时感知后端机器信息变化时,则构建 TW 个虚拟节点且第一次只初始化 N 个节点(注:TW 代表后端机器权重之和,N 代表后端机器数);
  • 各个进程设置随机起点轮询位置,如下图的 Step 1 对应的列表其起点位置指向 B;
  • 当请求到达后从设置的随机起点 B 位置轮询虚拟节点列表,若轮询到已经初始化的虚拟节点数组的末尾(如下图的 Step2 红色箭头指向的位置),则初始化第二批虚拟节点(如下图 Step2 对应的红色节点),当所有虚拟节点初始化完后将不再做初始化工作(如下图的 Step3 对应的状态);

此方案不仅将算法时间复杂度从 O(N) 优化到 O(1) ,而且也避免了权重调高场景下带来的问题。

相关函数:

ngx_http_upstream_init_vnswrr函数是配置初始化时执行的函数:

static ngx_int_t
ngx_http_upstream_init_vnswrr(ngx_conf_t *cf,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_http_upstream_rr_peers_t           *peers, *backup;
    ngx_http_upstream_vnswrr_srv_conf_t    *uvnscf, *ubvnscf;


    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, cf->log, 0, "init vnswrr");
	/* 同样采用round robin函数初始 */
    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
        return NGX_ERROR;
    }

    uvnscf = ngx_http_conf_upstream_srv_conf(us,
                                ngx_http_upstream_vnswrr_module);
    if (uvnscf == NULL) {
        return NGX_ERROR;
    }

    uvnscf->init_number = NGX_CONF_UNSET_UINT;
    uvnscf->last_number = NGX_CONF_UNSET_UINT;
    uvnscf->last_peer = NULL;
    uvnscf->next = NULL;
	
    us->peer.init = ngx_http_upstream_init_vnswrr_peer;

    peers = (ngx_http_upstream_rr_peers_t *) us->peer.data;
    
    /* 则构建 total_weight 个虚拟节点 */
    if (peers->weighted) {
        uvnscf->vpeers = ngx_pcalloc(cf->pool,
                                    sizeof(ngx_http_upstream_rr_vpeers_t)
                                    * peers->total_weight);
        if (uvnscf->vpeers == NULL) {
            return NGX_ERROR;
        }
		/* 在这个函数里面对虚拟节点列表初始化 后端机器数量 个peer */
        ngx_http_upstream_init_virtual_peers(peers, uvnscf, 0, peers->number);

    }

    /* backup peers */
    backup = peers->next;
    if (backup) {
        ubvnscf = ngx_pcalloc(cf->pool,
                              sizeof(ngx_http_upstream_vnswrr_srv_conf_t));
        if (ubvnscf == NULL) {
            return NGX_ERROR;
        }

        ubvnscf->init_number = NGX_CONF_UNSET_UINT;
        ubvnscf->last_number = NGX_CONF_UNSET_UINT;
        ubvnscf->last_peer = NULL;

        uvnscf->next = ubvnscf;

        if (!backup->weighted) {
            return NGX_OK;
        }

        ubvnscf->vpeers = ngx_pcalloc(cf->pool,
                                      sizeof(ngx_http_upstream_rr_vpeers_t)
                                      * backup->total_weight);
        if (ubvnscf->vpeers == NULL) {
            return NGX_ERROR;
        }

        ngx_http_upstream_init_virtual_peers(backup, ubvnscf, 0, backup->number);
    }

    return NGX_OK;
}

下面的函数用于初始化一批节点:

static void 
ngx_http_upstream_init_virtual_peers(ngx_http_upstream_rr_peers_t *peers,
                                     ngx_http_upstream_vnswrr_srv_conf_t *uvnscf,
                                     ngx_uint_t s, ngx_uint_t e)
{
    ngx_uint_t                              i;
    ngx_int_t                               rindex;
    ngx_http_upstream_rr_peer_t            *peer;
    ngx_http_upstream_rr_vpeers_t          *vpeers;

    if (uvnscf == NULL || peers == NULL) {
        return;
    }

    vpeers = uvnscf->vpeers;
    
    for (i = s; i < e; i++) {
        rindex = ngx_http_upstream_get_rr_peer(peers, &peer);
        if (rindex == NGX_ERROR) {
            ngx_log_error(NGX_LOG_ERR, ngx_cycle->log, 0,
                          "get rr peer is null in upstream \"%V\" ",
                          peers->name);
            if (i != 0) {
                i--;
            }
    
            continue;
        }
    	/* 在虚拟节点列表里存好轮询的peer顺序 */
        vpeers[i].vpeer = peer;
        vpeers[i].rindex = rindex;
    }
    
    uvnscf->vnumber = i;

    return;
}

下面这个函数在请求来到的时候调用,也是和前面讲到初始化请求的函数套路一样:

static ngx_int_t
ngx_http_upstream_init_vnswrr_peer(ngx_http_request_t *r,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_http_upstream_vnswrr_srv_conf_t    *uvnscf;
    ngx_http_upstream_vnswrr_peer_data_t   *vnsp;

    uvnscf = ngx_http_conf_upstream_srv_conf(us,
                                          ngx_http_upstream_vnswrr_module);

    vnsp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_vnswrr_peer_data_t));
    if (vnsp == NULL) {
        return NGX_ERROR;
    }

    vnsp->uvnscf = uvnscf;
    r->upstream->peer.data = &vnsp->rrp;
	/* 也是用round robin初始化一波 */
    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
        return NGX_ERROR;
    }
	/* 注册 get peer函数 */
    r->upstream->peer.get = ngx_http_upstream_get_vnswrr_peer;

    return NGX_OK;
}

下面这个函数是重点,其中里面调用的ngx_http_upstream_get_vnswrr函数是核心:

static ngx_int_t
ngx_http_upstream_get_vnswrr_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_vnswrr_peer_data_t  *vnsp = data;

    ngx_int_t                              rc;
    ngx_uint_t                             i, n;
    ngx_http_upstream_rr_peer_t           *peer;
    ngx_http_upstream_rr_peers_t          *peers;
    ngx_http_upstream_rr_peer_data_t      *rrp;

    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "get vnswrr peer, try: %ui", pc->tries);

    pc->cached = 0;
    pc->connection = NULL;

    rrp = &vnsp->rrp;

    peers = rrp->peers;
    ngx_http_upstream_rr_peers_wlock(peers);

    if (peers->single) {
        peer = peers->peer;

        if (peer->down) {
            goto failed;
        }

#if defined(nginx_version) && nginx_version >= 1011005
        if (peer->max_conns && peer->conns >= peer->max_conns) {
            goto failed;
        }
#endif

#if (NGX_HTTP_UPSTREAM_CHECK)
        if (ngx_http_upstream_check_peer_down(peer->check_index)) {
            goto failed;
        }
#endif
        rrp->current = peer;

    } else {

        /* there are several peers */
		/* 重点核心函数 */
        peer = ngx_http_upstream_get_vnswrr(vnsp);

        if (peer == NULL) {
            goto failed;
        }

        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get vnswrr peer, current: %p %i",
                       peer, peer->current_weight);
    }

    pc->sockaddr = peer->sockaddr;
    pc->socklen = peer->socklen;
    pc->name = &peer->name;

    peer->conns++;

    ngx_http_upstream_rr_peers_unlock(peers);

    return NGX_OK;

failed:

    if (peers->next) {

        ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0, "backup servers");

        rrp->peers = peers->next;

        vnsp->uvnscf = vnsp->uvnscf ? vnsp->uvnscf->next : vnsp->uvnscf;

        n = (rrp->peers->number + (8 * sizeof(uintptr_t) - 1))
                / (8 * sizeof(uintptr_t));

        for (i = 0; i < n; i++) {
            rrp->tried[i] = 0;
        }

        ngx_http_upstream_rr_peers_unlock(peers);

        rc = ngx_http_upstream_get_vnswrr_peer(pc, vnsp);

        if (rc != NGX_BUSY) {
            return rc;
        }

        ngx_http_upstream_rr_peers_wlock(peers);
    }

    ngx_http_upstream_rr_peers_unlock(peers);

    pc->name = peers->name;

    return NGX_BUSY;
}

下面这个函数是整套算法的核心:

static ngx_http_upstream_rr_peer_t *
ngx_http_upstream_get_vnswrr(ngx_http_upstream_vnswrr_peer_data_t  *vnsp)
{
    time_t                                  now;
    uintptr_t                               m;
    ngx_uint_t                              i, n, p, flag, begin_number;
    ngx_http_upstream_rr_peer_t            *peer, *best;
    ngx_http_upstream_rr_peers_t           *peers;
    ngx_http_upstream_rr_vpeers_t          *vpeers;
    ngx_http_upstream_rr_peer_data_t       *rrp;
    ngx_http_upstream_vnswrr_srv_conf_t    *uvnscf;

    now = ngx_time();

    best = NULL;

#if (NGX_SUPPRESS_WARN)
    p = 0;
#endif

    rrp = &vnsp->rrp;
    peers = rrp->peers;
    uvnscf = vnsp->uvnscf;
    vpeers = uvnscf->vpeers;
    
	/* 一开始会进入这个分支 */
    if (uvnscf->last_number == NGX_CONF_UNSET_UINT) {
        /* 一开始先随机选取一个peer,记录number */
        uvnscf->init_number = ngx_random() % peers->number;

        if (peers->weighted) {
            /* 在虚拟列表里找到对应number的peer */
            peer = vpeers[uvnscf->init_number].vpeer;

        } else {
            for (peer = peers->peer, i = 0; i < uvnscf->init_number; i++) {
                peer = peer->next;
            }
        }
		/* 记录number */
        uvnscf->last_number = uvnscf->init_number;
        uvnscf->last_peer = peer;
    }

    if (peers->weighted) {
        /* batch initialization vpeers at runtime. */
        
        /* 如果还没初始化完这个列表,若轮询到已经初始化的虚拟节点数组的末尾,初始化下一批节点 */
        if (uvnscf->vnumber != peers->total_weight
            && (uvnscf->last_number + 1 == uvnscf->vnumber))
        {
            /* 得到这一批初始化需要初始化的节点数量n */
            n = peers->total_weight - uvnscf->vnumber;
            if (n > peers->number) {
                n = peers->number;
            }
			/* 初始化节点函数 */
            ngx_http_upstream_init_virtual_peers(peers, uvnscf, uvnscf->vnumber,
			                         n + uvnscf->vnumber);

        }
		/* 无论需不需要初始化一批节点,每次get peer函数执行的时候都会更新begin_number,这里的到的peer就是这次希望选择的peer */
        begin_number = (uvnscf->last_number + 1) % uvnscf->vnumber;
        peer = vpeers[begin_number].vpeer;

    } else {
        if (uvnscf->last_peer && uvnscf->last_peer->next) {
            begin_number = (uvnscf->last_number + 1) % peers->number;
            peer = uvnscf->last_peer->next;

        } else {
            begin_number = 0;
            peer = peers->peer;
        }
    }
    
	/* 找到best的节点 ,和轮询差不多套路,虽然这里是个for循环,但是如果前面选择的peer(或者说begin number)不出现意外的话,就是一轮过,直接break出循环了。for循环是检查前面所选择的peer,防止前面选择的peer出现问题之后选择其他的peer */
    for (i = begin_number, flag = 1; i != begin_number || flag;
         i = peers->weighted
         ? ((i + 1) % uvnscf->vnumber) : ((i + 1) % peers->number),
         peer = peers->weighted
         ? vpeers[i].vpeer : (peer->next ? peer->next : peers->peer))
    {

        flag = 0;
        if (peers->weighted) {

            n = peers->total_weight - uvnscf->vnumber;
            if (n > peers->number) {
                n = peers->number;
            }

            ngx_http_upstream_init_virtual_peers(peers, uvnscf, uvnscf->vnumber,
			                         n + uvnscf->vnumber);

            n = vpeers[i].rindex / (8 * sizeof(uintptr_t));
            m = (uintptr_t) 1 << vpeers[i].rindex % (8 * sizeof(uintptr_t));

        } else {
            n =  i / (8 * sizeof(uintptr_t));
            m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
        }

        if (rrp->tried[n] & m) {
            continue;
        }

        if (peer->down) {
            continue;
        }

        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            continue;
        }

#if defined(nginx_version) && nginx_version >= 1011005
        if (peer->max_conns && peer->conns >= peer->max_conns) {
            continue;
        }
#endif

#if (NGX_HTTP_UPSTREAM_CHECK)
        if (ngx_http_upstream_check_peer_down(peer->check_index)) {
            continue;
        }
#endif

        best = peer;
        uvnscf->last_peer = peer;
        uvnscf->last_number = i;
        p = i;
        break;
    }

    if (best == NULL) {
        return NULL;
    }

    rrp->current = best;

    if (peers->weighted) {
        n = vpeers[p].rindex / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << vpeers[p].rindex % (8 * sizeof(uintptr_t));

    } else {
        n = p / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
    }

    rrp->tried[n] |= m;

    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }

    return best;
}

–END–