Nginx内置的负载均衡策略 加权轮询 (Weighted Round Robin)

Nginx中设置反向代理的时候，能够指定反向代理中每一个后端服务器所占的比重， 起到负载均衡的作用， 看一个反向代理的例子：

upstream backend {  
        server a weight=5;  
        server b weight=3;  
        server c weight=1;  
    }

例子中， 设置了三台后台服务器，所占的比重分别为5，3，1。 那么如何做到在收到请求的时候， 按照比例分配到后台的三台服务器呢。 能想到的最简单的方法当然是：如果当前权重大于0，就发往这台服务器，然后权重减1， 但是这种方法分发的请求结果就是[a,a,a,a,a,b,b,b,c]， 虽然达到了目标的比例，但是有一段时间请求都发往了a， 另一段都发往了b，这显然不是一种好的处理方式，对每台机器来说相当于忙一阵，闲一阵，并没有平均的收到请求。

那么nginx中是如何来做负载均衡，让每台机器收到的请求频率更为平均的呢。 答案是一个叫weighted round robin (WRR)的算法，对于算法的数据解释和证明， 有时间可以单独讨论一下，先直接看看nignx是如何实现这个算法的。 

nginx中从几台服务器中选取一台有效服务器的过程放在一个叫ngx_http_upstream_get_peer的函数中， 先直接看一下整体的函数：

/* 根据后端服务器的权重来选择一台后端服务器处理请求 */
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;
}

在函数中，nginx其实还做了其他很多检查之类的动作，比如查看当前服务器是否被选中过，是否有效等等。 如果单纯只关注选择算法，可以将其他过程剔除掉，只剩下：

/* 根据后端服务器的权重来选择一台后端服务器处理请求 */
static ngx_http_upstream_rr_peer_t *
ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
{
    ....
    best = NULL;
    total = 0;
 
    /* 遍历后端服务器列表 */
    for (i = 0; i < rrp->peers->number; i++) {
 
        ........
 
        /* 若当前后端服务器可能被选中，则计算其权重 */
 
        /*
         * 在上面初始化过程中 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;
    }
 
    ........
 
    /* 更新被选中后端服务器的权重 */
    best->current_weight -= total;
 
    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }
 
    /* 返回被选中的后端服务器 */
    return best;
}

每个后端peer都有三个权重变量

(1) weight

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

(2) effective_weight

后端的有效权重，初始值为weight。

为什么要出来一个effective_weight，而不是直接用weight呢？是因为如果当前的服务器发生了错误的时候，可以减小effective_weight，让这台机器被选中的概率降低。 当然，如果服务器都正常的话， effective_weight会一直等于weight。

如果发生过错误的服务器后来又恢复了正常， 在选取的过程中也会逐步增加effective_weight，最终又恢复到weight。

(3) current_weight

后端当前的权重，一开始为0，每次选择的时候都会调整， 对于每个后端，让它的current_weight增加它的effective_weight，

同时累加所有后端的effective_weight，保存为total。

如果该后端的current_weight是最大的，就选定这个后端，然后把它的current_weight减去total。

如果该后端没有被选定，那么current_weight不用减小。

弄清了三个weight字段的含义后，加权轮询算法可描述为：

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

    peer->current_weight += peer->effecitve_weight。

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

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

3.对于本次选定的后端，执行：peer->current_weight -= total。

可以直接对照上边的源代码理解。 

拿一开始的配置当例子

upstream backend {

    server a weight=5;

    server b weight=3;

    server c weight=1;

}

初始的时候 current_weight = { 0, 0, 0 }， effective_weight = { 5, 3, 1 }。假设服务器中途一直不发生故障，total一直是所有effective_weight的总和，即9.

可以看到9个请求是一个轮回，完整的序列是[a, b, a, c, a, b, a, b, a] ， 相对是一个很平均的过程，可以验证个算法的有效性。