nginx least_conn　算法的解析

在之前的文章讲解了nginx的round_robin.ip_hash.constent_hash的负载均衡算法，再后面的学习上接触到了least_conn今天抽时间补上，,该模块就是每次选择最少连接负载均衡算法，简单来说就是每次选择的都是当前最少连接的一个server(这个最少连接不是全局的，是每个进程都有自己的一个统计列表)。　

看了这么多饿负载均衡算法，不知道你有什么体会（发现了没有?有很多的负载均衡都会去复用round_robin算法），是的优秀饿设计，的确很佩服．　　　

首先来看如何打开least_conn模块:

static ngx_command_t  ngx_http_upstream_least_conn_commands[] = {

    { ngx_string("least_conn"),
      NGX_HTTP_UPS_CONF|NGX_CONF_NOARGS,
      ngx_http_upstream_least_conn,
      0,
      0,
      NULL },

      ngx_null_command
};

可以看到命令很简单，就是在upstream块里面加上 least_conn就行了。

来看命令对应的回调，least_conn的入口就是在这个里面设置的.

static char *
ngx_http_upstream_least_conn(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ngx_http_upstream_srv_conf_t  *uscf;

    uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);

    uscf->peer.init_upstream = ngx_http_upstream_init_least_conn;

    uscf->flags = NGX_HTTP_UPSTREAM_CREATE
                  |NGX_HTTP_UPSTREAM_WEIGHT
                  |NGX_HTTP_UPSTREAM_MAX_FAILS
                  |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
                  |NGX_HTTP_UPSTREAM_DOWN
                  |NGX_HTTP_UPSTREAM_BACKUP;

    return NGX_CONF_OK;
}

可以看到很简单，就是设置了peer.init_upstream,然后设置了支持的flags。那么这里就有问题了， peer.init_upstream什么时候会被调用呢。

upstream 进行相应饿初始化饿时候

static char *
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++) {
//判断是否有设置 initupstream,默认是round robin算法.
        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;
        }
    }
}

上面的代码可以看到是在解析upstream命令的时候，调用init_upstream的，因此也就可以这么说，init_upstream 中初始化的的东西，每个进程都有自己的一份拷贝.（注意cow［写时拷贝技术］）

所以我们来看ngx_http_upstream_init_least_conn，这个函数主要就是初始化round robin(主要是为了初始化权重等参数，而且least conn中如果多个server有相同的连接数，则会使用round robin算法)以及设置peer的init回调.

还有一个要注意的就是conns数组［每个worker都有饿，不是全局饿］，这个数组每个slot保存了对应server的连接数

ngx_int_t
ngx_http_upstream_init_least_conn(ngx_conf_t *cf,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_uint_t                            n;
    ngx_http_upstream_rr_peers_t         *peers;
    ngx_http_upstream_least_conn_conf_t  *lcf;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, cf->log, 0,
                   "init least conn");
//初始化round robin
    if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK) {
        return NGX_ERROR;
    }

    peers = us->peer.data;

    n = peers->number;

    if (peers->next) {
        n += peers->next->number;
    }

    lcf = ngx_http_conf_upstream_srv_conf(us,
                                          ngx_http_upstream_least_conn_module);
//创建conns数组
    lcf->conns = ngx_pcalloc(cf->pool, sizeof(ngx_uint_t) * n);
    if (lcf->conns == NULL) {
        return NGX_ERROR;
    }
//设置init
    us->peer.init = ngx_http_upstream_init_least_conn_peer;

    return NGX_OK;
}

而us->peer.init是在upstream的request初始化的时候调用的，也就是说每个request都会调用这个函数来初始化：


static void
ngx_http_upstream_init_request(ngx_http_request_t *r)
{

found:

    if (uscf->peer.init(r, uscf) != NGX_OK) {
        ngx_http_upstream_finalize_request(r, u,
                                           NGX_HTTP_INTERNAL_SERVER_ERROR);
        return;
    }

    ngx_http_upstream_connect(r, u);
}

然后我们就来看peer.init回调ngx_http_upstream_init_least_conn_peer，在这个函数中，主要是用来初始化对应的数据结构,
然后挂载对应的回调(getpeer/freepeer).　　　


typedef struct {
    /* the round robin data must be first */
    ngx_http_upstream_rr_peer_data_t   rrp;
//连接信息保存
    ngx_uint_t                        *conns;
//对应的get和free连接的回调
    ngx_event_get_peer_pt              get_rr_peer;
    ngx_event_free_peer_pt             free_rr_peer;
} ngx_http_upstream_lc_peer_data_t;

static ngx_int_t
ngx_http_upstream_init_least_conn_peer(ngx_http_request_t *r,
    ngx_http_upstream_srv_conf_t *us)
{
    ngx_http_upstream_lc_peer_data_t     *lcp;
    ngx_http_upstream_least_conn_conf_t  *lcf;

    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
                   "init least conn peer");

    lcf = ngx_http_conf_upstream_srv_conf(us,
                                          ngx_http_upstream_least_conn_module);

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

    lcp->conns = lcf->conns;

    r->upstream->peer.data = &lcp->rrp;
//初始化round robin
    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
        return NGX_ERROR;
    }
//设置回调
    r->upstream->peer.get = ngx_http_upstream_get_least_conn_peer;
    r->upstream->peer.free = ngx_http_upstream_free_least_conn_peer;

    lcp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;
    lcp->free_rr_peer = ngx_http_upstream_free_round_robin_peer;

    return NGX_OK;
}

上面可以看到每个lcp都有自己的get peer和free回调，这是什么原因呢，和upstream->peer的get和free的区别在哪里，这个是这样的原因，主要是least conn算法中，如果多个server都有相同的连接数，那么就需要使用round robin算法了，所以就保存了round robin的peer回调。　　　

然后来看对应的peer get回调在那里调用的，首先通过前面的blog 我们知道每次当要和upstream建立连接的时候，我们都需要调用ngx_event_connect_peer，最终这个函数会创建连接，然后再去connect upstream，而我们的get 回调也就是在这个函数中调用的。　　　　

ngx_int_t
ngx_event_connect_peer(ngx_peer_connection_t *pc)
{
    int                rc;
    ngx_int_t          event;
    ngx_err_t          err;
    ngx_uint_t         level;
    ngx_socket_t       s;
    ngx_event_t       *rev, *wev;
    ngx_connection_t  *c;
//调用get
    rc = pc->get(pc, pc->data);
    if (rc != NGX_OK) {
        return rc;
    }

}

其实nginx的load balance模块中，最核心的就是peer.get回调了，基本上核心的算法都在get回调里面实现，所以我们来看ngx_http_upstream_get_least_conn_peer,首先是选择最少连接的server，这里要注意，其实不仅仅是最少连接，还要加上权重，这里nginx使用的是连接数和权重的乘积。［其实这里使用了一个交叉相乘的公式进行比较］

还有一个要注意的，就是对于每一个请求，Nginx保存了一个位图，这个位图保存了所有server是否已经被当前request 使用过的状态，如果使用过则对应的位是1，否则为0，这个主要是为了处理失败的情况，而重复进行连接。

    for (i = 0; i < peers->number; i++) {
//一个字节8位，所以计算当前peer所处的位置
        n = i / (8 * sizeof(uintptr_t));
//得到当前peer的状态
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));
//如果已经服务过，则跳过
        if (lcp->rrp.tried[n] & m) {
            continue;
        }

        peer = &peers->peer[i];

        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
         */
//选择server
        if (best == NULL
            || lcp->conns[i] * best->weight < lcp->conns[p] * peer->weight)
        {
            best = peer;
//many表示是否有多个server满足条件.
            many = 0;
//p为best的位置
            p = i;

        } else if (lcp->conns[i] * best->weight
                   == lcp->conns[p] * peer->weight)
        {
//相等则说明有多个server满足条件.
            many = 1;
        }
    }

接下来这段就是当有多个server满足条件的时候的处理，这里是如果多个server满足条件，则进入round robin的处理逻辑。
下面的代码和round robin的get peer回调中算法是一模一样的。就是根据权重选择一个合适的server，这里Nginx还调整过
round robin算法．



if (many) {
    ngx_log_debug0(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "get least conn peer, many");

    for (i = p; i < peers->number; i++) {

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

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

        peer = &peers->peer[i];

        if (peer->down) {
            continue;
        }

        if (lcp->conns[i] * best->weight != lcp->conns[p] * 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;

        if (peer->effective_weight < peer->weight) {
            peer->effective_weight++;
        }

        if (peer->current_weight > best->current_weight) {
            best = peer;
            p = i;
        }
    }
}

best->current_weight -= total;
best->checked = now;

最后就是更新一些状态位，比如更新server的连接数等　　

最后回顾下：　　 (1).该模块其实就是每次选择连接数最少(当然还和自己当前的权值相关,其实是当前连接数除以自己的权重的值作比较, 看谁小就选择谁.但是权值有可能是 0,所以做了等价对换,即交叉相乘)的server,其中有一个全局的conns数组用于记录每个server的连接数.　　　　　　 (2).还有就是一种情况,当出现了多个server都满足条件的时候,则此时采用round_robin.　　　　　　　

欢迎一起交流学习

在使用中有任何问题，欢迎反馈给我，可以用以下联系方式跟我交流

邮件(1031379296#qq.com, 把#换成@)
QQ: 1031379296
weibo: @王发康

Thx

chunshengsterATgmail.com

Author

Linux\nginx\golang\c\c++爱好者
欢迎一起交流一起学习#
Others say good and Others good