负载均衡之轮循算法

1：普通加权轮询算法

         

         这种算法的原理是：在服务器数组S中，首先计算所有服务器权重的最大值max(S)，以及所有服务器权重的最大公约数gcd(S)。

         index表示本次请求到来时，选择的服务器的索引，初始值为-1；current_weight表示当前调度的权值，初始值为max(S)。

         当请求到来时，从index+1开始轮询服务器数组S，找到其中权重大于current_weight的第一个服务器，用于处理该请求。记录其索引到结果序列中。

　　在轮询服务器数组时，如果到达了数组末尾，则重新从头开始搜索，并且减小current_weight的值：current_weight -= gcd(S)。如果current_weight等于0，则将其重置为          max(S)。

　　第1次调用该函数时，i(index)为-1，cw(current_weight)为0，进入循环后，i首先被置为0，因此cw被置为maxweight。从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是c，因此，i被置为2，并返回其值。

　　第2次调用该函数时，i为2，cw为maxweight。进入循环后，i首先被置为0，因此cw被置为cw-gcd，也就是3。从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器还是c，因此，i被置为2，并返回其值。

　　第3次调用该函数时，i为2，cw为3。进入循环后，i首先被置为0，因此cw被置为cw-gcd，也就是2。从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是b，因此，i被置为1，并返回其值。

　　第4次调用该函数时，i为1，cw为2。进入循环后，i首先被置为2，从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是c，因此，i被置为2，并返回其值。

　　第5次调用该函数时，i为2，cw为2。进入循环后，i首先被置为0，因此cw被置为cw-gcd，也就是1。从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是a，因此，i被置为0，并返回其值。

　　第6次调用该函数时，i为0，cw为1。进入循环后，i首先被置为1，从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是b，因此，i被置为1，并返回其值。

　　第7次调用该函数时，i为1，cw为1。进入循环后，i首先被置为2，从i开始轮询服务器数组ss，第一个权重大于等于cw的服务器是c，因此，i被置为2，并返回其值。

　　经过7（1+2+4）次调用之后，每个服务器被选中的次数正好是其权重值。

1. server a weight=5;    
2. server b weight=1;    
3. server c weight=1; 
4. 生成的序列是这样的：{a,a, a, a, a, c, b}。会有5个连续的请求落在后端a上，分布不太均匀。

          

    2、平滑的加权轮询    

在Nginx源码中，实现了一种叫做平滑的加权轮询（smooth weighted round-robin balancing）的算法，它生成的序列更加均匀。比如前面的例子，它生成的序列为{ a, a, b, a, c, a, a}，转发给后端a的5个           请求现在分散开来，不再是连续的。

　　该算法的原理如下：

　　每个服务器都有两个权重变量：

　　a：weight，配置文件中指定的该服务器的权重，这个值是固定不变的；

　　b：current_weight，服务器目前的权重。一开始为0，之后会动态调整。

　　每次当请求到来，选取服务器时，会遍历数组中所有服务器。对于每个服务器，让它的current_weight增加它的weight；同时累加所有服务器的weight，并保存为total。

　　遍历完所有服务器之后，如果该服务器的current_weight是最大的，就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total